Salve a tutti, vorrei implementare una libreria con carrello virtuale con il linguaggio Python utilizzando le strutture dati.
Nello specifico vorrei che all'avvio del programma, l'utente debba scegliere una tra le tre opzioni del menù:
1.Aggiungere nuovi prodotti
2.Ricerca un libro tramite il codice ISBN
3.Calcolare il costo totale
Supponendo di avere già un file in cui sono elencati i vari prodotti disponibili, vorrei utilizzare per:
- il punto 1 la coda prioritaria implementata mediante una lista posizionale;
- il punto 2 una tabella hash implementata mediante una mappa;
- il punto 3 un albero implementato mediante un heap
Se il prodotto ricercato dall'utente è disponibile il suo prezzo verrà inserito nel "carrello" (pensato come un ulteriore file) se non disponibile si inviterà l'utente a fare una nuova scelta. Una volta aver aggiunto tutti i prodotti necessari, si farà la somma degli articoli nel "carrello".
Ho implementato le varie strutture dati:
Una coda doppiamente contatenata e una lista posizionale che mi permetterà di implementare una coda prioritaria con lista ordinata
Lista posizionale:
L'implementazione della coda prioritaria è la seguente:
La coda prioritaria con lista :
Dove Empty è:
L'implementazione della mappa è:
Quindi la tabella hash è:
Infine l'implementazione dell'albero è:
Adesso il problema che mi sorge è come faccio a implementare il resto del programma e a richiamare le funzioni in un eventuale main?
Nello specifico vorrei che all'avvio del programma, l'utente debba scegliere una tra le tre opzioni del menù:
1.Aggiungere nuovi prodotti
2.Ricerca un libro tramite il codice ISBN
3.Calcolare il costo totale
Supponendo di avere già un file in cui sono elencati i vari prodotti disponibili, vorrei utilizzare per:
- il punto 1 la coda prioritaria implementata mediante una lista posizionale;
- il punto 2 una tabella hash implementata mediante una mappa;
- il punto 3 un albero implementato mediante un heap
Se il prodotto ricercato dall'utente è disponibile il suo prezzo verrà inserito nel "carrello" (pensato come un ulteriore file) se non disponibile si inviterà l'utente a fare una nuova scelta. Una volta aver aggiunto tutti i prodotti necessari, si farà la somma degli articoli nel "carrello".
Ho implementato le varie strutture dati:
Una coda doppiamente contatenata e una lista posizionale che mi permetterà di implementare una coda prioritaria con lista ordinata
Python:
class _DoublyLinkedBase:
"""Una classe base che fornisce una rappresentazione di lista doppiamente concatenata"""
#-----------------------classe _Node innestata------------------------
class _Node:
"""Classe leggera, non pubblica per la memorizzazione di un nodo collegato singolarmente"""
__slots__ = '_element', '_prev', '_next' #per la gestione ottimizzata della memoria
def __init__(self, element, prev, next):
"""Inizializza i campi del nodo"""
self._element = element
self._prev = prev
self._next = next
#--------------------metodi della lista-------------------------
def __init__(self):
"""Crea una lista vuota"""
self._header = self._Node(None, None, None)
self._trailer = self._Node(None, None, None)
self._header._next = self._trailer
self._trailer._prev = self._header
self._size = 0
def __len__(self):
"""Restituisce il numero di elementi nella lista"""
return self._size
def is_empty( self ):
"""Restituisce True se la lista è vuota"""
return self._size == 0
def _insert_between( self, e, predecessor, successor ):
"""Aggiunge l'elemento 'e' tra due nodi esistenti e restituisce un nuovo nodo"""
newest = self._Node(e, predecessor, successor) #collegato ai vicini
predecessor._next = newest
successor._prev = newest
self._size += 1
return newest
def _delete_node( self, node ):
"""Elimina il nodo non-sentinella dalla lista e restituisce il suo elemento"""
predecessor = node._prev
successor = node._next
predecessor._next = successor
successor._prev = predecessor
self._size -= 1
element = node._element #registra l'elemento eliminato
node._prev = node._next = node._element = None #nodo deprecato
return element
Lista posizionale:
Python:
from lista_doppiamente_concatenata import _DoublyLinkedBase
class PositionalList(_DoublyLinkedBase):
"""Contenitore sequenziale di elementi che consente l'accesso poizionale"""
#----------------------classe innestata Position----------------------------------
class Position:
"""Astrazione che rappresenta la posizione di un singolo elemento"""
def __init__(self, container, node) :
"""Costruttore"""
self._container = container
self._node = node
def element( self ):
"""Restituisce l'elemento memorizzato in questa posizione"""
return self._node._element
def __eq__(self, other):
"""Restituisce True se 'other' è una posizione che rappresenta la stessa posizione"""
return type(other) is type(self) and other._node is self._node
def __ne__(self, other):
"""Restituisce True se 'other' è una posizione che rappresenta la stessa posizione"""
return not (self == other) #opposto di __eq__
#-----------------metodi di utilità-----------------------------
def _validate( self, p ):
"""Restituisci la posiione del nodo o solleva l'errore appropriato se non valido"""
if not isinstance(p, self.Position):
raise TypeError("p deve esseredi tipo Position")
if p._container is not self:
raise ValueError("p non appartiene a questo contenitore")
if p._node._next is None:
raise ValueError("p non è più valida")
return p._node
def _make_position( self, node ):
"""Restituisce l'istanza Position per il nodo dato"""
if node is self._header or node is self._trailer:
return None
else:
return self.Position(self,node)
#----------------------metodi accessori---------------------------------
def first( self ):
"""Restituisce la prima Position nella lista"""
return self._make_position(self._header._next)
def last( self ):
"""Restituisce l'ultima Position nella lista"""
return self._make_position(self._trailer._prev)
def before( self, p ):
"""Restituisce la Position prima della Position p"""
node = self._validate(p)
return self._make_position(node._prev)
def after( self, p ):
"""Restituisce la Position dopo la Position p"""
node = self._validate(p)
return self._make_position(node._next)
def __iter__(self):
"""Genera un'iterazione in avanti degli elementi della lista"""
cursor = self.first()
while cursor is not None:
yield cursor.element()
cursor = self.after(cursor)
#------------------mutuatori-----------------------------------------------
#override la versione ereditata per restituire Position, anzichè Node
def _insert_between( self, e, predecessor, successor ):
"""Aggiunge un elemento tra nodi esistenti e restituisce Position"""
node = super()._insert_between(e, predecessor, successor)
return self._make_position(node)
def add_first( self, e ):
"""Aggiunge l'elemento all'inizio della lista e restituisce Position"""
return self._insert_between(e, self._header, self._header._next)
def add_last( self, e ):
"""Aggiunge l'elemento alla fine della lista e restituisce Position"""
return self._insert_between(e, self._trailer._prev, self._trailer)
def add_before( self, p, e ):
"""Inserisce l'elemento 'e' nella lista prima della Position 'p e restituisce nuova Position"""
original = self._validate(p)
return self._insert_between(e, original._prev, original)
def add_after( self, p, e ):
"""Inserisce l'elemento 'e' nella lista dopo Position 'p' e restituisce nuove Position"""
original = self._validate(p)
return self._insert_between(e, original, original._next)
def delete( self, p ):
"""Rimuove e restituisce l'elemento in Position p"""
original = self._validate(p)
return self._delete_node(original)
def replace( self, p, e ):
"""Sostituisce l'elemento nella Position 'p' con l'elemento 'e'.
Restituisce l'elemento precedentemente in Position p"""
original = self._validate(p)
old_value = original._element
original._element = e
return old_value
L'implementazione della coda prioritaria è la seguente:
Python:
class PriorityQueueBase:
"""Classe di base astratta per una coda prioritaria"""
#------------------classe Item innestata--------------
class _Item:
"""Composito leggero per archiviare elemtni della coda coda prioritaria"""
__slots__ = 'key', '_value'
def __init__(self, k, v):
self._key = k
self._value = v
def __lt__(self, other):
return self._key < other._key
#---------------------------------------------------------------
def is_empty( self ):
"""Restituisce True se la coda di priorità è vuota"""
return len(self) == 0
La coda prioritaria con lista :
Python:
from empty import Empty
from lista_posizionale import PositionalList
from coda_prioritaria import PriorityQueueBase
class SortedPriorityQueue(PriorityQueueBase):
"""Coda con priorità min-oriented implementata con una lista ordinata"""
def __init__(self):
"""Crea una nuova coda prioritaria vuota"""
self._data = PositionalList()
def __len__(self):
"""Restituisce il numero di elementi nella coda prioritaria"""
return len(self._data)
def add( self, key, value ):
"""Aggiunge una coppia chiave-valore"""
newest = self._Item(key, value) #crea una nuova istanza di _Item
walk = self._data.last() #'cammina' all'indietro per cercare una chaive più piccola
while walk is not None and newest < walk.element():
walk = self._data.before(walk)
if walk is None:
self._data.add_first(newest)
else:
self._data.add_after(walk, newest)
def min( self ):
"""Restituisce ma non rimuove la tupla (k, v) con chiave minima"""
if self.is_empty():
raise Empty("La coda prioritaria è vuota")
p = self._data.first()
item = p.element()
return (item._key, item._value)
def remove_min( self ):
"""Restituisce e rimuove la tupla (k, v) con chiave minima"""
if self.is_empty():
raise Empty("La coda prioritaria è vuota")
item = self._data.delete(self._data.first())
return (item._key, item._value)
Dove Empty è:
Python:
class Empty(Exception):
"""Errore nel tentativo di accedere ad un elemento da un contenitore vuoto"""
pass
L'implementazione della mappa è:
Python:
from _collections_abc import MutableMapping
class MapBase(MutableMapping):
"""Classe base astratta che include una classe _Item non pubblica"""
#--------------------------classe _Item innestata-----------------------------------
class _Item:
"""Composito leggero per archiviare le coppie chiave-valore come elementi della mappa"""
__slots__ = '_key', '_value'
def __init__(self, k, v):
self._key = k
self._value = v
def __eq__(self, other):
return self._key == other._key #confronta gli elementi in base alle loro chiavi
def __ne__(self, other):
return not (self == other) #opposto di __eq__
def __lt__(self, other):
return self._key < other._key #confronta gli elementi in base alle loro chiavi
Quindi la tabella hash è:
Python:
from random import randrange
from mappa import MapBase
class HashMapBase(MapBase):
"""Classe astratta di base per la mappa che usa la tabella hash con compressione MAD"""
def __init__(self, cap=11, p=109345121):
"""Crea una mappa tabella hash vuota"""
self._table = cap * [None]
self._n = 0 #numero di voci nella mappa
self._prime = p #numero primo per compressione MAD
self._scale = 1 + randrange(p - 1) #scala da 1 a p - 1 a MAD
self._shift = randrange(p) #shift da 0 a p-1 per MAD
def _hash_function( self, k ):
"""Calcola hash per il valore k"""
return (hash(k) * self._scale + self._shift) % self._prime % len(self._table)
def __len__(self):
"""Restituisce il numero di elementi distinit attualmente memorizzati nella tabella hash"""
return self._n
def __getitem__(self, k):
j = self._hash_function(k)
return self._bucket_getitem(j, k) #può sollevare un KeyError
def __setitem__(self, k, v):
j = self._hash_function(k)
self._bucket_setitem(j, k, v) #la sottoroutine aggiorna self._n
if self._n > len(self._table) // 2: # mantiene il fattore di carico <= 0.5
self._resize(2 * len(self._table) - 1) #il numero 2^x - 1 è spesso primo
def __delitem__(self, k):
j = self._hash_function(k)
self._bucket_delitem(j,k) #può sollevare un KeyError
self._n -= 1
def _resize( self, c ):
"""Ridimensiona l'array di bucket alla capcità c"""
old = list(self.items()) #si usa l'iterazione per registrare elementi esistenti
self._table = c * [None] #ripristina la tabella alla capacità desiderata
self._n = 0 # _n è ricalcolato durante le aggiunte successive
for(k,v) in old:
self[k] = v #re-inserisce le vecchie copie chiave-valore
Infine l'implementazione dell'albero è:
Python:
class Tree:
"""Classe base astratta che rappresenta una struttura ad albero"""
#--------------------class Position innestata-------------------------
class Position:
"""Un'astrazione che rappresenta la posizione di un singolo elemento"""
def element( self ):
"""Restituisce l'elemento memorizzato in questa Position"""
raise NotImplementedError("Deve essere implementato dalla sottoclasse")
def __eq__(self, other):
"""Restituisce True se 'other' Position rappresenta la stessa posizione"""
raise NotImplementedError("Deve essere implementato dall sottoclasse")
def __ne__(self, other):
"""Restituisce True se 'other' non rappresenta la stessa posizione"""
return not (self == other) #opposto a __eq__
#-----------------------metodi astratti che la sottoclasse concreta deve supportare--------------------------
def root( self ):
"""Restitusice Position che rappresenta la radice dell'albero"""
raise NotImplementedError("Deve essere implementato dalla sottoclasse")
def parent( self, p ):
"""Restituisce Position che rappresenta il genitore di 'p'"""
raise NotImplementedError("Deve essere implementato dalla sottoclasse")
def num_children( self, p ):
"""Restituisce il numero di figli della Position p"""
raise NotImplementedError("Deve essere implementato dalla sottoclasse")
def children( self, p ):
"""Restituisce un contenitore iterabile con i figli della posizione 'p'"""
raise NotImplementedError("Deve essere implementato dalla sottoclasse")
def __len__(self):
"""Restituisce il numero totale di elementi nell'albero"""
raise NotImplementedError("Deve essere implementato dalla sottoclasse")
#---------------metodi concreti implementati in quetsa classe-------------------------------------
def is_root( self, p ):
"""Restituisce True se la Position 'p' è la radice dell'albero"""
return self.root() == p
def is_leaf( self, p ):
"""Restituisce True se la Position 'p' non ha figli"""
return self.num_children(p) == 0
def is_empty( self ):
"""Restituisce True se l'albero è vuoto"""
return len(self) == 0
Adesso il problema che mi sorge è come faccio a implementare il resto del programma e a richiamare le funzioni in un eventuale main?