/**
* La classe ArrayOrdinato
implementa il tipo di dato Dizionario
* mantenendo le coppie (elemento, chiave) in un array S in modo
* tale che coppie consecutive abbiano chiavi non decrescenti,
* cioè che l'array sia ordinato in base alle chiavi.
*/
public class ArrayOrdinato implements Dizionario {
// array di coppie (elem,chiave)
private Coppia[] S= new Coppia[0];
/**
* Classe definita localmente alla classe ArrayOrdinato
* per il mantenimento delle coppie (elemento, chiave)
*
*/
private class Coppia {
public Object elem;
public Comparable chiave;
public Coppia(Object e, Comparable k) {
this.elem = e;
this.chiave = k;
}
public String toString(){
return chiave.toString()+ ":"+elem.toString();
}
}
/**
* Rimuove dal dizionario l'elemento con chiave k
(Tempo O(n)).
* In caso di duplicati, l'elemento cancellato
* è scelto arbitrariamente tra quelli con chiave k
.
* La ricerca dell'elemento da cancellare avviene
* mediante una scansione binaria dell'array.
*
* @param k chiave dell'elemento da cancellare
* @throws EccezioneChiaveNonValida se la chiave ricercata non è presente nel dizionario
*/
public void delete(Comparable k) {
// TODO Auto-generated method stub
}
/**
* Aggiunge al dizionario la coppia (e,k)
(Tempo O(n)).
* L'inserimento viene realizzato incrementando
* di uno la taglia dell'array e collocando la nuova
* coppia in modo tale da rispettare la relazione
* di ordinamento.
*
* @param e elemento da mantenere nel dizionario
* @param k chiave associata all'elemento
*/
public void insert(Object e, Comparable k) {
int i, j;
//creare un vettore temp di dimensione S.length+1
Coppia[] temp = new Coppia[S.length + 1];
//copiare in temp S
for (i = 0; i < S.length; i++)
temp[i] = S[i];
//assegnare ad S temp
S = temp;
//ricercale la posizione in cui inserire l'elemento e
for (i = 0; i < S.length - 1; i++)
if (k.compareTo(S[i].chiave) <= 0)
break; // i corrisponde alla posizione in cui deve essere inserito e
for (j = S.length - 1; j > i; j--)
S[j] = S[j - 1]; //shiftare a destra
S[i] = new Coppia(e, k);
}
/**
* Restituisce l'elemento e
con chiave k
(Tempo O(log(n)).
* In caso di duplicati, l'elemento restituito
* è scelto arbitrariamente tra quelli con chiave k
.
* La ricerca dell'elemento con chiave k
* avviene utilizzando l'algoritmo di ricerca binaria.
*
* @param k chiave dell'elemento da ricercare
* @return elemento di chiave k
, null
se assente
*/
public Object search(Comparable k) {
// TODO Auto-generated method stub
int i=0;
int j=S.length;
while (i