Classe tree234
import java.util.Iterator;
import java.util.Comparator;
public class Tree24<E extends OrderedDictionary,K,V extends Value> implements Tree<E>,Dictionary<K,V>{
/**Costruttore principale*/
public Tree24(){
root=(Position24<E>)addRoot(null);
size=0;
}
/** Restituisce il numero di elementi dell'albero
@return int dimensione dell'albero*/
public int size(){ return size; }
/** Informa se l'albero è vuoto
@return true se l'labero è vuoto false altrimenti */
public boolean isEmpty(){ return (size==0); }
/** Restituisce un iteratore di elementi immagazzinati nell'albero
@return iteratore contenente gli elementi immagazzinati nell'albero */
public Iterator<E> iterator(){
PositionList<E> p=new NodePositionList<E>();
iterator(root,p);
return p.iterator();
}
private void iterator(Position24 v,PositionList<E> p){
//caso base foglia
if (v==null) return;
//caso base nodo esterno
E dict=(E)v.element();
if(isExternal(v)){
p.addLast(dict);
return;
}
for(int i=0;i<dict.size();i++){
Entry temp=dict.getEntry(i);
iterator(dict.getChildAt(i),p);
}
p.addLast(dict);
}
/** Restituisce una collezzione iterabile dei nodi
@return Iterable<Position<E>> collezzione iterabile dei nodi */
public Iterable<Position<E>> positions(){
PositionList<Position<E>> p=new NodePositionList<Position<E>>();
positions(root,p);
return p;
}
/** Crea un collezzione iterabile dei nodi */
private void positions(Position24 v,PositionList<Position<E>> p){
E dict=(E)v.element();
//caso base foglia
if (v==null) return;
//caso base nodo esterno
if(isExternal(v)){
p.addLast(v);
return;
}
for(int i=0;i<dict.size();i++){
Entry temp=dict.getEntry(i);
positions(dict.getChildAt(i),p);
}
p.addLast(v);
}
/** Modifica un elemento posizionato a un determinato nodo
@param v nodo di cui si desidera modificare l'elemento
@param E elemento da modificare
@return E elemento modificato
@exception InvalidPositionException se la posizione del nodo non è valida
*/
public E replace(Position<E> v, E e)throws InvalidPositionException{
Position24<E> temp=checkPosition(v);
E t=temp.element(); //Dizionario precedente
temp.setElement(e);
return t;
}
/** Ritorna il nodo root dell'albero
@return Position<E> nodo root dell'abero
@exception EmptyTreeException se l'albero è vuoto
*/
public Position<E> root() throws EmptyTreeException{
if(root==null)
throw new EmptyTreeException("Albero vuoto");
return root;
}
/** Ritorna il padre di un determinato nodo
@param v nodo di cui si vuole conoscere il padre
@return Position<E> posizione del nodo padre
@exception InvalidPositionException se la posizione del nodo non è valida
*/
public Position<E> parent(Position<E> v)
throws InvalidPositionException, BoundaryViolationException{
Position24<E> temp=checkPosition(v);
return temp.getParent();
}
/** Ritorna una collezzione iterabile di figli di un determinato nodo
@param v posizione del nodo
@return Iterable<Position<E> collezzione iterabile dei figli del nodo v
@exception InvalidPositionException se la posizione del nodo non è valida
*/
public Iterable<Position<E>> children(Position<E> v) throws InvalidPositionException{
Position24 pos=checkPosition(v);
PositionList<Position<E>> p=new NodePositionList<Position<E>>();
E dict=(E)pos.element();
for(int i=0;i<dict.size();i++)
p.addLast(dict.getChildAt(i));
return p;
}
/** Informa se il nodo è interno
@param v nodo dell'albero
@return true se il nodo ha dei figli false altrimenti
@exception InvalidPositionException se la posizione del nodo non è valida
*/
//E' internal se ha figli e quindi se il riferimento al primo figlio non è vuoto
public boolean isInternal(Position<E> v) throws InvalidPositionException{
Position24<E> temp=checkPosition(v);
//So che l'elemento estratto è di tipo Value
Value x=(Value)temp.element().getEntry(0).getValue();
return (x.getChild()!=null);
}
/** Informa se il nodo è esterno
@param v nodo dell'albero
@return true se il nodo non ha figli false altrimenti
*/
public boolean isExternal(Position<E> v)
throws InvalidPositionException{ return (!isInternal(v)); }
/** Informa se un determinato nodo è il nodo root dell'albero
@param v nodo dell'albero
@return true se il nodo è il root dell'albero false altrimenti
@exception InvalidPositionException se la posizione del nodo non è valida
*/
public boolean isRoot(Position<E> v) throws InvalidPositionException{
checkPosition(v);
return (v==root());
}
/**Aggiunge una radice
@param e elemento da inserire nel nodo
@exception NonEmptyTreeException se la radice è già presente
@return posizione della nuova radice creata
*/
public Position<E> addRoot(E e) throws NonEmptyTreeException{
if(!isEmpty())
throw new NonEmptyTreeException("L'alberto ha già una radice");
size=1;
root=createNode(e,null);
return root;
}
/**Crea un nuovo nodo
@param element elemento del nodo
@param posizone del padre
@return Position24<E> posizione del nuovo nodo
*/
//se non passo nulla come argomento o un dizionario vuoto inserisco un infinito come elemento
public Position24<E> createNode(E element,Position24<E> parent){
//Nodo vuoto
E temp=element;
if(element==null||temp.size()==0){
if(element==null)
temp=(E)new ArrayDictionary();
//inserisco l'elemento con chiave infinita
temp.insert(Integer.MAX_VALUE,new Value());
}
return new Node24(temp,parent);
}
/**crea un nuovo nodo con padre settato a null
@param element elemento da inserire nel nodo
@return posizione del nuovo nodeo creato*/
private Position24<E> createNode(E element){
return createNode(element,null);
}
/**Converte un riferimento di Position in Position24
@param v nodo da convertire
@return Position24<E> posizione convertita del nodo
@exception InvalidPositionException se v punta a null o non è di tipo Position24*/
private Position24<E> checkPosition(Position<E> v) throws InvalidPositionException{
if(v==null || !(v instanceof Position24))
throw new InvalidPositionException("Posizione non valida");
return (Position24<E>)v;
}
/** Ritorna una voce contente con la chiave indicata o null se la voce non esiste
@param key chiva con cui effettuare la ricerca
@return Entry<K,V> voce del dizionario con la data chiva o null se non l'ho trovata */
public Entry<K,V> find(K key) throws InvalidKeyException{
//chiamo un metodo ricorsivo
return search(root(),key);
}
/** metodo ricorsivo che trova la voce riferita alla chiave corrispondente */
private Entry<K,V> search(Position<E> v,K key) throws InvalidKeyException{
//converto in Position24
v=checkPosition(v);
//dizionario riferito al nodo
OrderedDictionary dict=v.element();
//cerco la chiave in tutto il nodo se la trovo restituisco la voce del dizionario
Entry<K,V> x=dict.find(key);
if(x!=null){
currentPos=checkPosition(v);
return x;
}
//caso base nodo è una foglia
if(isExternal(v)){
currentPos=checkPosition(v);
return null;
}
//se non l'ho trovato cerco la chiave nel figlio del primo successore di k
return search(dict.successorChild(key),key);
}
/** Inserisce una voce nell'albero
@param key chiave della voce da inserire
@param value valore della voce da inserire
@return voce inserita nell'albero */
public Entry<K,V> insert(K key, V value) throws InvalidKeyException{
return insertTree(root,key,value);
}
/** Inserisce un elemento nell'albero o l'elemento già inserito se è già presente un
elemento con la stessa chiave
@param node posizione del nodo su cui effettuare l'inserimento
@param key chiave della voce
@param value valore della voce
@return Entry<K,V> voce inserita nell'albero
@exception InvalidKeyException se la chiave non è valida*/
private Entry<K,V> insertTree(Position<E> node,K key, V value) throws InvalidKeyException{
Entry e=find(key);
if(!isExternal(currentPos))
return e;
Position24<E> v=checkPosition(currentPos);
e=new Entry24(key,new Value(value));
OrderedDictionary dict=v.element();
dict.insert(key,value);
//controllo se c'è overflow: in caso affermativo esegui l'operazione di split
if(dict.isFull())
split(v);
size++;
return e;
}
/**Effettua l'operazione di split
@param v posizione del nodo da splittare*/
private void split(Position24<E> v){
//Prendo l'elemento memerizzato precedentemente
E oldDict=v.element();
//Nuovi dizionari che saranno gli elementi dei nodi
E dict1=(E)new ArrayDictionary();
E dict2=(E)new ArrayDictionary();
//creo i due nodi v1 e v2
Position24<E> v1=createNode(dict1);
Position24<E> v2=createNode(dict2);
//INSERIMENTO NEI FIGLI
//Inserisci nel primo figlio
dict1.insert(oldDict.getEntry(0));
dict1.insert(oldDict.getEntry(1));
//Inserisci nel secondo figlio
dict2.insert(oldDict.getEntry(3));
//INSERIMENTO NEL PADRE
//setto nella voce corrispondente il riferimento al figlio
Position24<E> parent=v.getParent();
E parentDict;
//caso base root
if(parent==null){
parentDict=(E)new ArrayDictionary();
root=createNode(parentDict,null);
v1.setParent(root);
v2.setParent(root);
}
else{ //padre esistente
parentDict=parent.element();
v1.setParent(parent);
v2.setParent(parent);
}
//Estrai l'elemento di mezzo dal dizionario del figlio
Entry<K,V> middle=oldDict.getEntry(2);
//Aggiorno i riferimenti dei figli ai due nuovi nodi creati
oldDict.updateParentChild(0,v1);
oldDict.updateParentChild(1,v1);
oldDict.updateParentChild(2,v1);
oldDict.updateParentChild(3,v2);
oldDict.updateParentChild(4,v2);
//SO CHE L'INFINITO E' L'ULTIMA VOCE DEL DIZIONARIO
//prendo l'infinito del primo nodo e gli salvo il riferimento di middle
dict1.updateChild(dict1.size()-1,oldDict.getChildAt(2));
/*setto il figlio riferito all'infinito del secondo creato con il figlio dell'infinito del nodo che
vado a sostituire*/
dict2.updateChild(dict2.size()-1,oldDict.getChildLast());
//trova la posizione del i-esimo figlio
int pos=parentDict.findPos(v);
//Nel caso di root non trovo la posizione del vecchio nodo (ne è stato creato uno nuovo)
if(pos==-1)
pos=0;
//inserisci l'elemento di mezzo nel padre
parentDict.insert(middle);
parentDict.updateChild(pos,v1);
parentDict.updateChild(pos+1,v2);
//controllo se devo effettuare lo split multiplo
if(parentDict.isFull())
split(parent);
}
/** Visualizza gli elementi dell'albero in ordine */
public void print(){
print(root);
}
/** Visualizza gli elementi dell'albero in ordine a partire dal nodo v
@param v root del sottoalbero da visualizzare */
private void print(Position<E> v){
OrderedDictionary dict=v.element();
//caso base foglia
if (v==null) return;
//caso base nodo esterno
if(isExternal(v)){
for(int i=0;i<dict.size()-1;i++)
System.out.print(dict.getEntry(i)+" ");
System.out.print("Infinito,[null]");
System.out.println();
return;
}
for(int i=0;i<dict.size();i++){
Entry temp=dict.getEntry(i);
print(dict.getChildAt(i));
//visualizzazione di Infinito al posto di Integer.MAX_VALUE
if(i==dict.size()-1)
System.out.println("Infinito,[null]");
else System.out.println(temp);
}
}
/** Returns an iterator containing all the entries containing the
* given key, or an empty iterator if no such entries exist. */
//begin#fragment Dictionary
public Iterable<Entry<K,V>> findAll(K key) throws InvalidKeyException{}
/** Removes and returns the given entry from the dictionary. */
//begin#fragment Dictionary
public Entry<K,V> remove(Entry<K,V> e) throws InvalidEntryException{}
//end#fragment Dictionary
/** Returns an iterator containing all the entries in the dictionary. */
//begin#fragment Dictionary
public Iterable<Entry<K,V>> entries(){}
/** Ritorna la voce del dizionario con la chiave più piccola
@return voce del dizionario con la chiave più piccola null se il dizionario è vuoto*/
public Entry<K,V> first(){}
/** Ritorna la voce del dizionario con la chiave più grande
@return voce del dizionario con la chiave più grande null se il dizionario è vuoto*/
public Entry<K,V> last(){}
/** Ritorna la prima voce del dizionario successiva a key
@param key chiave che permette di selezionario la prima voce del dizionario successiva
@return voce del dizionario successiva a key o null se non c'è una voce
successiva
@exception InvalidKeyException se la chiave non è valida*/
public Entry<K,V> successor(K key) throws InvalidKeyException{}
/** Ritorna la voce del dizionario successiva a key
@param key chiave che permette di selezionario la voce del dizionario successiva
@return voce del dizionario successiva a key o null se non c'è una voce
precedente
@exception InvalidKeyException se la chiave non è valida*/
public Entry<K,V> predecessor(K key) throws InvalidKeyException{}
private Position24<E> currentPos; //utilizzo questa variabile per memorizzare il nodo nella ricerca
private Position24<E> root;
private int size;
private Comparator<K> C;
}
Classe per i nodi dell'albero:
public interface OrderedDictionary<K,V> extends Dictionary<K,V>{
/** Ritorna la voce del dizionario con la chiave più piccola
@return voce del dizionario con la chiave più piccola null se il dizionario è vuoto*/
public Entry<K,V> first();
/** Ritorna la voce del dizionario con la chiave più grande
@return voce del dizionario con la chiave più grande null se il dizionario è vuoto*/
public Entry<K,V> last();
/** Ritorna la prima voce del dizionario successiva a key
@param key chiave che permette di selezionario la prima voce del dizionario successiva
@return voce del dizionario successiva a key o null se non c'è una voce
successiva
@exception InvalidKeyException se la chiave non è valida*/
public Entry<K,V> successor(K key) throws InvalidKeyException;
/** Ritorna la voce del dizionario successiva a key
@param key chiave che permette di selezionario la voce del dizionario successiva
@return voce del dizionario successiva a key o null se non c'è una voce
precedente
@exception InvalidKeyException se la chiave non è valida*/
public Entry<K,V> predecessor(K key) throws InvalidKeyException;
/** Rimuovi l'ultima voce del dizionario */
public void removeLast();
/** Inserisci una voce nel dizionario
@return voce nel dizionario inserita */
public Entry<K,V> insert(Entry<K,V> e);
/** Ritorna la chiave nella posizione specifica del dizionario
@param i posizione dove estrarre la voce
@return voce nel dizionario nella posizione selezionata */
public Entry<K,V> getEntry(int i);
/** Trova la posizione il numero del figlio v
@param pos posizione del figlio
@return int posizione del figlio se non l'ho trovato restituisce -1*/
public int findPos(Position24 pos);
/** Setta il padre del figlio riferito alla voce nella posizione pos
@param pos posizione della voce del dizionario
@param parent posizione del padre */
public void updateParentChild(int pos,Position24 parent);
/** Setta il figlio riferito alla voce del dizionario nella posizione pos
@param pos posizione della voce del dizionario
@param v posizione del figlio*/
public void updateChild(int pos,Position24 v);
/** Restituisce il figlio riferito alla voce del dizionario nella posizione pos
@param pos posizione della voce nella quale cercare il figlio
@return Position24 posizione del figlio */
public Position24 getChildAt(int pos);
/** Restituisce il figlio riferito all'ultima voce del dizionario
@return Position24 posizione del figlio all'ultima voce del dizionario*/
public Position24 getChildLast();
/** Restituisce il figlio della voce successore di quella con la chiave specificata
@param key chiave della voce
@return Position24 voce successore di quella con la chiave specificata
@exception InvalidKeyException se la chiave non è valida*/
public Position24 successorChild(K key) throws InvalidEntryException;
/**controlla se il dizionario è pieno
@return true se è pieno false altrimenti*/
public boolean isFull();
}
Classe che implementa entry:
//V extends Value
public class Entry24<K,V extends Value> implements Entry<K,V>{
/**Costruttore principale*/
public Entry24(K k,V v){
key=k;
value=v;
}
/** Restituisce la chiave della voce
*@return chiave della voce */
public K getKey(){ return key; }
/** Restituisce il valore della voce
*@return valore della voce */
public V getValue(){ return value; }
public String toString() { return "("+key+","+value+")"; }
private K key;
private V value;
}
Classe che implementa Position:
//Interfaccia nodo dell'albero (2,4)
public interface Position24<E> extends Position<E>{
/**Restituisce il padre del nodo
*@return Position24 padre del nodo*/
public Position24<E> getParent();
/**setta il padre
*@param padre del nodo*/
public void setParent(Position24<E> par);
/*Setta l'elemento (dizionario) nel nodo
*@param e dizionario**/
public void setElement(E e);
}
Classe node24:
//realizzazione del nodo il dizionario è l'elemento del nodo
public class Node24<E extends OrderedDictionary> implements Position24<E>{
//costruttore principale
public Node24(E elem,Position24<E> par){
element=elem;
parent=par;
}
public Node24(Position24<E> par){ this(null,par); }
public Node24(E e){ this(e,null); }
public Node24(){ this(null,null); }
/**Restituisce l'elemento del nodo
*@return elemento del nodo*/
public E element(){ return element; }
/*Setta l'elemento nel nodo
*@param e dizionario**/
public void setElement(E o){ element=o; }
/**Restituisce il padre del nodo
*@return Position24 padre del nodo*/
public Position24<E> getParent(){ return parent; }
/**setta il padre
*@param padre del nodo*/
public void setParent(Position24<E> v){ parent=v; }
private Position24<E> parent;
private E element;
}
Classe mycomparator:
import java.util.Comparator;
import java.io.Serializable;
public class MyComparator<E> implements Comparator<E>{
//Se il secondo elemento è Integer.MAX_VALUE restuisci -1
/**Esegue il confronto fra due oggetti
*@return 1 se il 1° oggetto> 2° oggetto -1 se il 2° oggetto> 1° oggetto 0 se son uguali*/
public int compare(E a, E b) throws ClassCastException {
if(b instanceof Integer){
int temp=(Integer)b;
if(temp==Integer.MAX_VALUE)
return -1;
}
return ((Comparable<E>) a).compareTo(b);
}
}
bettina86
!