Lezione 11
Strutture dati dinamiche
Programmazione per la Musica | Prof. Luca A. Ludovico
Strutture dati dinamiche
• I tipi primitivi (int, char, …) e i tipi strutturati (array)
visti finora hanno dimensioni predefinite.
• Nel caso degli array, nella dichiarazione è necessario:
– stabilire il tipo base per gli elementi del vettore
– stabilire il numero di elementi complessivi
Una volta fissati questi aspetti, non possono più
essere modificati.
Esistono invece strutture dati dinamiche, le cui
dimensioni possono variare «dinamicamente» a
seconda delle esigenze.
Programmazione per la Musica - Prof. Luca A. Ludovico
11. Strutture dati dinamiche
La classe public class Vector<E>
• La classe Vector<E> (obsoleta) implementa un array di
dimensioni variabili. Ai suoi elementi si accede
tramite indice, come negli array non ridimensionabili.
• Richiede: import java.util.Vector;
• Costruttori:
– Vector()
– Vector(Collection<? extends E> c)
costruisce un vettore che contiene gli elementi della
collezione specificata, nel loro ordine originario.
– Vector(int initialCapacity)
– Vector(int initialCapacity, int capacityIncrement)
Programmazione per la Musica - Prof. Luca A. Ludovico
11. Strutture dati dinamiche
Type inference e classi generiche
• L’inferenza di tipo è la capacità del compilatore di valutare
l’invocazione di un metodo rispetto alla dichiarazione per
determinare il tipo degli argomenti che rendono applicabile
l’invocazione.
• Nell’invocazione del costruttore di una classe generica, è
possibile sostituire il tipo richiesto con un insieme vuoto denotato
da parentesi angolari <>, dette informalmente diamond, purché il
compilatore sia in grado di ricostruire il tipo dall’invocazione.
• Tra parentesi angolari deve essere specificata una classe e non un
tipo base. Ad esempio, String è una classe mentre int è un tipo
primitivo.
Per i tipi primitivi esiste sempre una classe “equivalente”.
Programmazione per la Musica - Prof. Luca A. Ludovico
11. Strutture dati dinamiche
Esempi di type inference
• Esempio 1: sequenza di valori di pitch class
ArrayList<Integer> arrayListPC1 = new ArrayList<Integer>();
ArrayList<Integer> arrayListPC2 = new ArrayList<>();
ArrayList<Integer> arrayListPC3 = new ArrayList();
La prima sintassi solleva un warning “redundant type arguments”.
Si osservi che è richiesto di specificare una classe per gli elementi e non un tipo,
quindi int non è ammissibile (è un tipo primitivo), mentre Integer sì (è una classe).
• Esempio 2: dizionario che mette in corrispondenza la stringa del
cognome di un compositore con l’elenco (di lunghezza variabile) dei
titoli delle sue composizioni
Map<String, List<String>> composerWorks1 = new HashMap<String, List<String>>();
Map<String, List<String>> composerWorks2 = new HashMap<>();
Map<String, List<String>> composerWorks3 = new HashMap();
Programmazione per la Musica - Prof. Luca A. Ludovico
11. Strutture dati dinamiche
Aggiunta, inserimento e ricerca di elementi
• public boolean add(E e)
aggiunge l’elemento e in coda al vettore.
• public E set(int index, E element)
rimpiazza l’elemento all’indice specificato con element.
• public E get(int index)
public E elementAt(int index)
restituiscono l’elemento alla posizione specificata.
• public int indexOf(Object o)
public int indexOf(Object o, int index)
public int lastIndexOf(Object o)
restituiscono l’indice corrispondente rispettivamente alla prima
occorrenza, alla prima occorrenza a partire da un dato indice e
all’ultima occorrenza dell’oggetto o, oppure -1 se l’oggetto non viene
trovato.
Programmazione per la Musica - Prof. Luca A. Ludovico
11. Strutture dati dinamiche
Rimozione di elementi
• public void clear()
public void removeAllElements()
rimuovono tutti gli elementi del vettore e ne impostano la dimensione a 0.
• public E remove(int index)
public void removeElementAt(int index)
rimuovono l’elemento all’indice dato.
• public boolean remove(Object o)
public boolean removeElement(Object o)
rimuove la prima occorrenza dell’oggetto o.
• protected void removeRange(int fromIndex, int toIndex)
rimuove tutti gli elementi il cui indice sta tra fromIndex (incluso) e toIndex
(escluso).
Programmazione per la Musica - Prof. Luca A. Ludovico
11. Strutture dati dinamiche
Metodi per il dimensionamento di un Vector
• public void trimToSize()
riduce la capacità del vettore a quella corrente, minimizzando
l’occupazione di spazio in memoria.
• public void ensureCapacity(int minCapacity)
incrementa se necessario la capacità per supportare il numero minimo di
elementi specificato.
• public void setSize(int newSize)
imposta le dimensioni del vettore: se superiori a quelle attuali il vettore
viene riempito alla fine di elementi null, se inferiori si scartano gli
elementi in eccesso.
• public int capacity()
restituisce la capacità corrente del vettore (cioè la lunghezza dell’array
di dati, indipendentemente dal suo effettivo riempimento).
• public int size()
restituisce il numero di elementi del vettore.
• public boolean isEmpty()
verifica se il vettore non abbia elementi.
Programmazione per la Musica - Prof. Luca A. Ludovico
11. Strutture dati dinamiche
Size e capacity
• Istanza di un nuovo Vector
size = 0, capacity = 10
• Dopo due operazioni di add
size = 2, capacity = 10
Ab
Ki
• Dopo un’operazione di trimToSize
size = 2, capacity = 2
Ab
Ki
Programmazione per la Musica - Prof. Luca A. Ludovico
11. Strutture dati dinamiche
La classe public class ArrayList<E>
• La classe ArrayList<E> implementa un array di
dimensioni variabili, in modo molto simile a
Vector<E>. Ai suoi elementi si accede tramite indice,
come negli array non ridimensionabili.
• Richiede: import java.util.ArrayList;
• Differenze rispetto a Vector:
– Non è sincronizzata, quindi in caso di accesso concorrente deve
essere il codice a gestire la sincronizzazione per quanto riguarda
alterazioni strutturali alla struttura dati (aggiunta o eliminazione di
elementi).
– Ha una gestione differente delle politiche di ridimensionamento
quando è necessario allocare più spazio (Vector aumenta le proprie
dimensioni del 100%, ArrayList del 50%) .
Programmazione per la Musica - Prof. Luca A. Ludovico
11. Strutture dati dinamiche
ESEMPI
VectorExample.java
Operazioni generiche sulle strutture dati dinamiche, con particolare riferimento
alla classe Vector.
CpcArrayList.java
Lettura dai parametri di ingresso di una sequenza di valori in notazione Continuous
Pitch Code (cpc), e assegnamento a una struttura dati di classe ArrayList.
Gestione di eventuali valori non riconosciuti.
Conversione dei valori in scrittura di pitch, alterazione e ottava in notazione
anglosassone.
Eliminazione dalla struttura dati di tutti i valori che soddisfano una data
condizione (ad esempio tutti i Do della quinta ottava, ossia cpc = 60)
Programmazione per la Musica - Prof. Luca A. Ludovico
11. Strutture dati dinamiche
ESERCIZIO
Si implementi la classe Melody, che contiene un elenco dinamico di istanze delle
classi Note e Rest.
La classe metterà a disposizione metodi basilari di analisi della melodia, quali un
contatore delle pause e delle note attualmente contenute, un metodo che
restituisce il pitch più alto e più basso (se esistono…), un metodo che restituisce la
durata più lunga e breve per i simboli musicali.
Osservazione: per la descrizione di note e pause è possibile ripartire dall’esempio Note.java
della lezione scorsa.
Programmazione per la Musica - Prof. Luca A. Ludovico
11. Strutture dati dinamiche