Domanda Implementazione di una libreria con strutture dati

Carmela bb

Utente Iron
31 Maggio 2021
3
2
0
7
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
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?