|
Junior Member
Iscritto dal: Apr 2007
Messaggi: 8
|
Di nuovo aiuto tree234 cambiato
 Ho rifatto la classe però mi mancano ancora dei metodi da implementare come vedete, voi sapete come farli?
Il metodo print secondo voi fa una rappresentazione parentetica identata dell'albero se no come farlo? Ditemi se devo cambiare qualcosa e se è giusto per il progetto di implementare i metodi dell'ADT dizionario ordinato con l'albero 2-3-4.
Codice:
package Tree;
import java.util.Iterator;
import java.util.Comparator;
public class Tree241<E extends OrderedDictionary,K,V extends Value> implements Tree<E>,Dictionary<K,V>{
/**Costruttore principale*/
public Tree241(){
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;
}
Ho rifatto la classe di test anche se devo ancora finirla ditemi se è giusta e seè lostesso per gli altri metodi. Poi la il compilatore nella creazione degli oggetti mi dice wrong type arguments:3 e in node24 1 come devo correggerlo?
Codice:
package Tree;
import java.io.*;
import java.util.Scanner;
/**
* @(#)Tree234Test.java
*
* Tree234 application
*
* @author Scaggion Elisabetta
* @version 1.00 2007/3/5
*/
public class Tree234Test {
public static void main(String[] args) {
String value;
Tree241<Integer,String> theTree = new Tree241<Integer,String>();
Scanner in = new Scanner(System.in);
System.out.println("Comincia il test:");
int scelta;
do{
menu();
scelta = in.nextInt();
lancia(scelta, theTree);
} while(scelta !=0);
System.out.println("Arrivederci");
}
private static void menu(){
System.out.println(" [0] uscita");
System.out.println(" [1] Inserisci un elemento");
System.out.println(" [2] Elimina un elemento");
System.out.println(" [3] Trova un elemento");
System.out.println(" [4] Trova tutti gli elementi");
System.out.println(" [5] Trova tutti gli elementi con una certa chiave");
System.out.println(" [6] Rappresentazione dell'albero");
System.out.println(" [8] first");
System.out.println(" [9] last");
System.out.println(" [10] seccessore");
System.out.println(" [11] predecessore");
}
private static void lancia (int s, Tree241<Integer,String> a){
Tree241<Integer,String> theTree = new Tree241<Integer,String>();
Scanner in = new Scanner(System.in);
Node24<Integer,String> node;
switch(s) {
case 1:
System.out.print("Entra value da inserire: ");
String valu = in.nextLine();
theTree.insert(valu);
break;
case 2:
System.out.println("Elemento?");
int key = in.nextInt();
theTree.remove(valu);
System.out.println("Fatto");
break;
case 3:
System.out.print("Entra value da trovare: ");
String value = in.nextLine();
int found = theTree.find(valu);
if(found != -1)
System.out.println("Found "+valu);
else
System.out.println("Could not find "+valu);
break;
case 4:
System.out.println("Gli Elementi nell'albero");
theTree.positions();
break;
case 5:
int ky = in.nextInt();
theTree.find(ky);
break;
case 6: System.out.println("Mostra l'albero");
theTree.print();
break;
case 7:
System.out.println("Elementi" + a.size());
break;
case 8:
break;
case 9:
break;
case 10:
break;
case 11:
break;
}
}
//--------------------------------------------------------------
public static String getString() throws IOException
{
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader br = new BufferedReader(isr);
String s = br.readLine();
return s;
}
//--------------------------------------------------------------
public static char getChar() throws IOException
{
String s = getString();
return s.charAt(0);
}
//-------------------------------------------------------------
public static int getInt() throws IOException
{
String s = getString();
return Integer.parseInt(s);
}
//--------------------------------------------
}
Queste sono le altre classi già compilate:
Ditemi se devo cambiare qualcosa e se è giusto per il progetto di implementare i metodi del dizionario ordinato con l'albero 2-3-4.
Codice:
package Tree;
//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;
}
package Tree;
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);
}
}
package Tree;
//begin#fragment Entry
/** Interface for a key-value pair entry **/
public interface Entry<K,V> {
/** Returns the key stored in this entry. */
public K getKey();
/** Returns the value stored in this entry. */
public V getValue();
}
//end#fragment Entry
package Tree;
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.lang.UnsupportedOperationException;
/**
* A simple iterator class for lists. The elements of a list are
* returned by this iterator. No copy of the list is made, so any
* changes to the list are reflected in the iterator.
*
* @author Michael Goodrich, Eric Zamore, Roberto Tamassia
*/
//begin#fragment Iterator
public class ElementIterator<E> implements Iterator<E> {
protected PositionList<E> list; // the underlying list
protected Position<E> cursor; // the next position
/** Creates an element iterator over the given list. */
public ElementIterator(PositionList<E> L) {
list = L;
cursor = (list.isEmpty())? null : list.first();
}
//end#fragment Iterator
/** Returns whether the iterator has a next object. */
//begin#fragment Iterator
public boolean hasNext() { return (cursor != null); }
//end#fragment Iterator
/** Returns the next object in the iterator. */
//begin#fragment Iterator
public E next() throws NoSuchElementException {
if (cursor == null)
throw new NoSuchElementException("No next element");
E toReturn = cursor.element();
cursor = (cursor == list.last())? null : list.next(cursor);
return toReturn;
}
//end#fragment Iterator
/** Throws an {@link UnsupportedOperationException} in all cases,
* because removal is not a supported operation in this iterator.
*/
public void remove() throws UnsupportedOperationException {
throw new UnsupportedOperationException("remove");
}
//begin#fragment Iterator
}
//end#fragment Iterator
package Tree;
//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;
}
package Tree;
/**
* A simple node class for a doubly-linked list. Each DNode has a
* reference to a stored element, a previous node, and a next node.
*
* @author Roberto Tamassia
*/
//begin#fragment DNode
public class DNode<E> implements Position<E> {
private DNode<E> prev, next; // References to the nodes before and after
private E element; // Element stored in this position
/** Constructor */
public DNode(DNode<E> newPrev, DNode<E> newNext, E elem) {
prev = newPrev;
next = newNext;
element = elem;
}
// Method from interface Position
public E element() throws InvalidPositionException {
if ((prev == null) && (next == null))
throw new InvalidPositionException("Position is not in a list!");
return element;
}
// Accessor methods
public DNode<E> getNext() { return next; }
public DNode<E> getPrev() { return prev; }
// Update methods
public void setNext(DNode<E> newNext) { next = newNext; }
public void setPrev(DNode<E> newPrev) { prev = newPrev; }
public void setElement(E newElement) { element = newElement; }
}
//end#fragment DNode
package Tree;
import java.util.Iterator;
/**
* An interface for a dictionary storing (key-value) pairs.
* @author Michael Goodrich
*/
//begin#fragment Dictionary
public interface Dictionary<K,V> {
//end#fragment Dictionary
/** Returns the number of entries in the dictionary. */
//begin#fragment Dictionary
public int size();
//end#fragment Dictionary
/** Returns whether the dictionary is empty. */
//begin#fragment Dictionary
public boolean isEmpty();
//end#fragment Dictionary
/** Returns an entry containing the given key, or <tt>null</tt> if
* no such entry exists. */
//begin#fragment Dictionary
public Entry<K,V> find(K key)
throws InvalidKeyException;
//end#fragment Dictionary
/** 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;
//end#fragment Dictionary
/** Inserts an item into the dictionary. Returns the newly created
* entry. */
//begin#fragment Dictionary
public Entry<K,V> insert(K key, V value)
throws InvalidKeyException;
//end#fragment Dictionary
/** 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;
}
//end#fragment Dictionary
package Tree;
import java.util.Comparator;
import java.util.*;
public class ArrayDictionary<K,V extends Value> implements OrderedDictionary<K,V>,Iterable<Entry<K,V>>{
/**iteratore del dizionario*/
private class IteratorDictionary<K,V> implements Iterator<Entry<K,V>>{
public IteratorDictionary(){ current=0; }
public boolean hasNext(){ return (current<size); }
public Entry<K,V> next(){ return (Entry<K,V>)v[current++]; }
public void remove(){}
private int current;
}
public Iterator<Entry<K,V>> iterator(){
return new IteratorDictionary();
}
//Costruttore
public ArrayDictionary(){
size=0;
v=new Entry24[MAX_SIZE];
comp=new MyComparator<K>();
}
/** Ritorna il numero di voci nel dizionario
@return numero delle voci del dizionario*/
public int size(){ return size; }
/** Ritorna se il dizionario è vuoto
@return true se il dizionario è vuoto false altrimenti */
public boolean isEmpty(){ return (size==0); }
/**controlla se il dizionario è pieno
@return true se è pieno false altrimenti*/
public boolean isFull(){ return (size==MAX_SIZE); }
/** Trova una voce nel dizionario
@param key chiave della voce da ricercare
@return voce con la chiave cercata*/
public Entry<K,V> find(K key) throws InvalidKeyException{
check(key);
for(int i=0;i<size;i++)
if(comp.compare(key,v[i].getKey())==0)
return v[i];
return null;
}
/** Ritorna un iteratore contenente tutte le voci contenenti una data chiave o un iteratore vuoto
*se non esiste nessuna voce
@param chiave delle voci da ricercare
@return iteratore contenente tutte le voci con una data chiave
@exception InvalidKeyException se la chiave non è valida*/
public Iterable<Entry<K,V>> findAll(K key) throws InvalidKeyException{
PositionList<Entry<K,V>> P=new NodePositionList<Entry<K,V>>();
for(int i=0;i<size;i++)
if(comp.compare(key,v[i].getKey())==0)
P.addLast(v[i]);
return P;
}
/** Inserisce un oggetto nel dizionario. Ritorna la voce appena
*creata
@param key chiave della voce da inserire
@param value valore della voce da inserire
@return voce inserita nel dizionario
@exception InvalidKeyException se la chiave non è valida*/
public Entry<K,V> insert(K key, V value) throws InvalidKeyException{
check(key);
//Il nostro dizionario può contenere fino a 4 voci
if(size>=MAX_SIZE)
return null;
Entry<K,V> temp=new Entry24<K,V>(key,value);
v[size++]=temp;
sort();
return temp;
}
/** Rimuove e retuisce una voce dal dizionario
@param e voce da rimuovere
@return voce eliminata
@exception InvalidKeyException se la chiave non è valida */
public Entry<K,V> remove(Entry<K,V> e) throws InvalidEntryException{
Entry<K,V> temp=null;
for(int i=0;i<size;i++)
if(comp.compare(e.getKey(),v[i].getKey())==0){
temp=v[i];
compact(i);
size--;
}
return temp;
}
/** Ritorna un iteratore contenente tutte le voci del dizionario o un iteratore vuoto se non vi son voci
*nel dizionario
@return iteratore contenente tutte le voci del dizionario */
public Iterable<Entry<K,V>> entries(){
PositionList<Entry<K,V>> P=new NodePositionList<Entry<K,V>>();
for(int i=0;i<size;i++)
P.addLast(v[i]);
return P;
}
/** 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(){
if(isEmpty())
return null;
return v[0];
}
/** 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(){
if(isEmpty())
return null;
return v[size-1];
}
/** 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){
if(i>=size)
return null;
return v[i];
}
/** 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{
check(key);
for(int i=0;i<size;i++)
if(comp.compare(key,v[i].getKey())<0)
return v[i];
//non ho trovato un successore
return null;
}
/** 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{
check(key);
for(int i=0;i<size;i++)
if(comp.compare(key,v[i].getKey())>0)
return v[i];
//non ho trovato un predecessore
return null;
}
/**controlla che la chiave non contega null altrimenti lancia un'eccezzione*/
private void check(K k) throws InvalidKeyException{
if(k==null)
throw new InvalidKeyException("Chiave non valida");
}
/**Compatta il dizionario per tenerlo ordinato*/
private void compact(int i){
for(int j=i;j<size-1;j++)
v[j]=v[j+1];
}
/**ordina le voci del dizionario in ordine crescente tramite InsertionSort*/
private void sort(){
//solo l'ultimo elemento inserito non è ordinato
int i=size-1;
Entry<K,V> temp=v[i];
int j;
for(j=i;j>0 && comp.compare((K)temp.getKey(),v[j-1].getKey())<0;j--)
v[j]=v[j-1];
v[j]=temp;
}
/** 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){
for(int i=0;i<size;i++)
if(v[i].getValue().getChild()==pos)
return i;
return -1;
}
/** Inserice una voce nel dizionario
@param e voce da inserire nel dizionario
@return voce del dizionario inserita*/
public Entry<K,V> insert(Entry<K,V> e){
return insert(e.getKey(),e.getValue());
}
/** 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){
Entry<K,V> temp=getEntry(pos);
if(temp!=null){
V tempVal= temp.getValue();
Position24 child=tempVal.getChild();
// se il il nodo non ha figli, altrimenti non ci sono figli da aggiornare
if (child!= null)
tempVal.getChild().setParent(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){ updateChild(getEntry(pos),v); }
/** Setta il figlio riferito alla voce del dizionario nella posizione pos
@param elemente voce del dizionario da settare
@param v posizione del figlio*/
private void updateChild(Entry<K,V> element, Position24 v){
if(element!=null){
V tempVal= element.getValue();
// se il il nodo non ha figli, altrimenti non ci sono figli da aggiornare
tempVal.setChild(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){
Position24 child=null;
Entry<K,V> temp=getEntry(pos);
if(temp!=null){
V tempVal= temp.getValue();
child=tempVal.getChild();
}
return child;
}
/** Restituisce il figlio riferito all'ultima voce del dizionario
@return Position24 posizione del figlio all'ultima voce del dizionario*/
public Position24 getChildLast(){ return getChildAt(size-1); }
/** 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{
check(key);
Entry<K,V> entry=successor(key);
V val=entry.getValue();
return val.getChild();
}
/** Rimuovi l'ultima voce del dizionario */
public void removeLast(){
compact(--size);
}
private int size;
public final int MAX_SIZE=5;
private Entry<K,V>[] v;
private MyComparator<K> comp;
}
package Tree;
import java.util.Iterator;
//begin#fragment Tree
/**
* An interface for a tree where nodes can have an arbitrary number of children.
//end#fragment Tree
* @author Michael Goodrich
//begin#fragment Tree
*/
public interface Tree<E> {
/** Returns the number of nodes in the tree. */
public int size();
/** Returns whether the tree is empty. */
public boolean isEmpty();
/** Returns an iterator of the elements stored in the tree. */
public Iterator<E> iterator();
/** Returns an iterable collection of the the nodes. */
public Iterable<Position<E>> positions();
/** Replaces the element stored at a given node. */
public E replace(Position<E> v, E e)
throws InvalidPositionException;
/** Returns the root of the tree. */
public Position<E> root() throws EmptyTreeException;
/** Returns the parent of a given node. */
public Position<E> parent(Position<E> v)
throws InvalidPositionException, BoundaryViolationException;
/** Returns an iterable collection of the children of a given node. */
public Iterable<Position<E>> children(Position<E> v)
throws InvalidPositionException;
/** Returns whether a given node is internal. */
public boolean isInternal(Position<E> v)
throws InvalidPositionException;
/** Returns whether a given node is external. */
public boolean isExternal(Position<E> v)
throws InvalidPositionException;
/** Returns whether a given node is the root of the tree. */
public boolean isRoot(Position<E> v)
throws InvalidPositionException;
}
//end#fragment Tree
package Tree;
/*classe che contiene il valore da inserire nel dizionario composto dall'oggetto
associato alla chiave (V object)e al riferimento ai figli (C child di tipo Position24)*/
public class Value<V,C extends Position24,E extends OrderedDictionary>{
/**Costruttore principale*/
public Value(V val,C c){
child=c;
object=val;
}
public Value(V val){ this(val,null); }
public Value() { this(null,null); }
/**Restituisce il dato satellite associato alla voce del dizionario
*@return oggetto associato alla voce*/
public V getObject(){ return object; }
/**Restituisce il figlio associato alla voce del dizionario
*@return figlio associato alla voce del dizionario*/
public Position24 getChild(){ return child; }
/**Setta il figlio associato alla voce del dizionario
*@param c figlio da associare alla voce del dizionario*/
public void setChild(Position24<E> c){ child=c; }
//visualizza solo il valore associato alla chiave non il riferimento al nodo succesivo
public String toString(){ return ""+object; }
private V object;
private Position24 child;
}
package Tree;
import java.util.Iterator;
/**
* An interface for positional lists.
* @author Roberto Tamassia, Michael Goodrich
*/
//begin#fragment Header
public interface PositionList<E> extends Iterable<E> {
//end#fragment Header
//begin#fragment List
/** Returns the number of elements in this list. */
public int size();
/** Returns whether the list is empty. */
public boolean isEmpty();
/** Returns the first node in the list. */
public Position<E> first();
/** Returns the last node in the list. */
public Position<E> last();
/** Returns the node after a given node in the list. */
public Position<E> next(Position<E> p)
throws InvalidPositionException, BoundaryViolationException;
/** Returns the node before a given node in the list. */
public Position<E> prev(Position<E> p)
throws InvalidPositionException, BoundaryViolationException;
/** Inserts an element at the front of the list, returning new position. */
public void addFirst(E e);
/** Inserts and element at the back of the list, returning new position. */
public void addLast(E e);
/** Inserts an element after the given node in the list. */
public void addAfter(Position<E> p, E e)
throws InvalidPositionException;
/** Inserts an element before the given node in the list. */
public void addBefore(Position<E> p, E e)
throws InvalidPositionException;
/** Removes a node from the list, returning the element stored there. */
public E remove(Position<E> p) throws InvalidPositionException;
/** Replaces the element stored at the given node, returning old element. */
public E set(Position<E> p, E e) throws InvalidPositionException;
//end#fragment List
//begin#fragment Positions
/** Returns an iterable collection of all the nodes in the list. */
public Iterable<Position<E>> positions();
//end#fragment Positions
//begin#fragment Iterator
/** Returns an iterator of all the elements in the list. */
public Iterator<E> iterator();
//end#fragment Iterator
//begin#fragment Tail
}
//end#fragment Tail
package Tree;
/**
* An interface for a position, which is a holder object storing a
* single element.
* @author Roberto Tamassia, Michael Goodrich
*/
//begin#fragment All
public interface Position<E> {
/** Return the element stored at this position. */
E element();
}
//end#fragment All
package Tree;
//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);
}
package Tree;
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();
}
package Tree;
import java.util.Iterator;
/**
* Realization of a PositionList using a doubly-linked list of nodes.
*
* @author Michael Goodrich, Natasha Gelfand, Roberto Tamassia, Eric Zamore
*/
//begin#fragment Header
public class NodePositionList<E> implements PositionList<E> {
//end#fragment Header
//begin#fragment Listvars
protected int numElts; // Number of elements in the list
protected DNode<E> header, trailer; // Special sentinels
//end#fragment Listvars
//begin#fragment checkPosition
/** Constructor that creates an empty list; O(1) time */
public NodePositionList() {
numElts = 0;
header = new DNode<E>(null, null, null); // create header
trailer = new DNode<E>(header, null, null); // create trailer
header.setNext(trailer); // make header and trailer point to each other
}
/** Checks if position is valid for this list and converts it to
* DNode if it is valid; O(1) time */
protected DNode<E> checkPosition(Position<E> p)
throws InvalidPositionException {
if (p == null)
throw new InvalidPositionException
("Null position passed to NodeList");
if (p == header)
throw new InvalidPositionException
("The header node is not a valid position");
if (p == trailer)
throw new InvalidPositionException
("The trailer node is not a valid position");
try {
DNode<E> temp = (DNode<E>) p;
if ((temp.getPrev() == null) || (temp.getNext() == null))
throw new InvalidPositionException
("Position does not belong to a valid NodeList");
return temp;
} catch (ClassCastException e) {
throw new InvalidPositionException
("Position is of wrong type for this list");
}
}
//end#fragment checkPosition
//begin#fragment first
/** Returns the number of elements in the list; O(1) time */
public int size() { return numElts; }
/** Returns whether the list is empty; O(1) time */
public boolean isEmpty() { return (numElts == 0); }
/** Returns the first position in the list; O(1) time */
public Position<E> first()
throws EmptyListException {
if (isEmpty())
throw new EmptyListException("List is empty");
return header.getNext();
}
//end#fragment first
/** Returns the last position in the list; O(1) time */
public Position<E> last()
throws EmptyListException {
if (isEmpty())
throw new EmptyListException("List is empty");
return trailer.getPrev();
}
//begin#fragment first
/** Returns the position before the given one; O(1) time */
public Position<E> prev(Position<E> p)
throws InvalidPositionException, BoundaryViolationException {
DNode<E> v = checkPosition(p);
DNode<E> prev = v.getPrev();
if (prev == header)
throw new BoundaryViolationException
("Cannot advance past the beginning of the list");
return prev;
}
//end#fragment first
/** Returns the position after the given one; O(1) time */
public Position<E> next(Position<E> p)
throws InvalidPositionException, BoundaryViolationException {
DNode<E> v = checkPosition(p);
DNode<E> next = v.getNext();
if (next == trailer)
throw new BoundaryViolationException
("Cannot advance past the end of the list");
return next;
}
//begin#fragment first
/** Insert the given element before the given position;
* O(1) time */
public void addBefore(Position<E> p, E element)
throws InvalidPositionException {
DNode<E> v = checkPosition(p);
numElts++;
DNode<E> newNode = new DNode<E>(v.getPrev(), v, element);
v.getPrev().setNext(newNode);
v.setPrev(newNode);
}
//end#fragment first
/** Insert the given element after the given position;
* O(1) time */
public void addAfter(Position<E> p, E element)
throws InvalidPositionException {
DNode<E> v = checkPosition(p);
numElts++;
DNode<E> newNode = new DNode<E>(v, v.getNext(), element);
v.getNext().setPrev(newNode);
v.setNext(newNode);
}
//begin#fragment remove
/** Insert the given element at the beginning of the list, returning
* the new position; O(1) time */
public void addFirst(E element) {
numElts++;
DNode<E> newNode = new DNode<E>(header, header.getNext(), element);
header.getNext().setPrev(newNode);
header.setNext(newNode);
}
//end#fragment remove
/** Insert the given element at the end of the list, returning
* the new position; O(1) time */
public void addLast(E element) {
numElts++;
DNode<E> oldLast = trailer.getPrev();
DNode<E> newNode = new DNode<E>(oldLast, trailer, element);
oldLast.setNext(newNode);
trailer.setPrev(newNode);
}
//begin#fragment remove
/**Remove the given position from the list; O(1) time */
public E remove(Position<E> p)
throws InvalidPositionException {
DNode<E> v = checkPosition(p);
numElts--;
DNode<E> vPrev = v.getPrev();
DNode<E> vNext = v.getNext();
vPrev.setNext(vNext);
vNext.setPrev(vPrev);
E vElem = v.element();
// unlink the position from the list and make it invalid
v.setNext(null);
v.setPrev(null);
return vElem;
}
/** Replace the element at the given position with the new element
* and return the old element; O(1) time */
public E set(Position<E> p, E element)
throws InvalidPositionException {
DNode<E> v = checkPosition(p);
E oldElt = v.element();
v.setElement(element);
return oldElt;
}
//end#fragment remove
//begin#fragment Iterator
/** Returns an iterator of all the elements in the list. */
public Iterator<E> iterator() { return new ElementIterator<E>(this); }
//end#fragment Iterator
//begin#fragment PIterator
/** Returns an iterable collection of all the nodes in the list. */
public Iterable<Position<E>> positions() { // create a list of posiitons
PositionList<Position<E>> P = new NodePositionList<Position<E>>();
if (!isEmpty()) {
Position<E> p = first();
while (true) {
P.addLast(p); // add position p as the last element of list P
if (p == last())
break;
p = next(p);
}
}
return P; // return P as our Iterable object
}
//end#fragment PIterator
// Convenience methods
/** Returns whether a position is the first one; O(1) time */
public boolean isFirst(Position<E> p)
throws InvalidPositionException {
DNode<E> v = checkPosition(p);
return v.getPrev() == header;
}
/** Returns whether a position is the last one; O(1) time */
public boolean isLast(Position<E> p)
throws InvalidPositionException {
DNode<E> v = checkPosition(p);
return v.getNext() == trailer;
}
/** Swap the elements of two give positions; O(1) time */
public void swapElements(Position<E> a, Position<E> b)
throws InvalidPositionException {
DNode<E> pA = checkPosition(a);
DNode<E> pB = checkPosition(b);
E temp = pA.element();
pA.setElement(pB.element());
pB.setElement(temp);
}
/** Returns a textual representation of a given node list using for-each */
public static <E> String forEachToString(PositionList<E> L) {
String s = "[";
int i = L.size();
for (E elem: L) {
s += elem; // implicit cast of the element to String
i--;
if (i > 0)
s += ", "; // separate elements with a comma
}
s += "]";
return s;
}
//begin#fragment toString
/** Returns a textual representation of a given node list */
public static <E> String toString(PositionList<E> l) {
Iterator<E> it = l.iterator();
String s = "[";
while (it.hasNext()) {
s += it.next(); // implicit cast of the next element to String
if (it.hasNext())
s += ", ";
}
s += "]";
return s;
}
//end#fragment toString
/** Returns a textual representation of the list */
public String toString() {
return toString(this);
}
}
package Tree;
/**
* Runtime exception thrown when one tries to create the root of a
* tree that is not empty.
*/
public class NonEmptyTreeException extends RuntimeException {
public NonEmptyTreeException(String err) {
super(err);
}
}
package Tree;
/**
* Thrown when a position is determined to be invalid.
* @author Roberto Tamassia, Michael Goodrich
*/
//begin#fragment InvalidPositionException
// A run-time exception for invalid positions
public class InvalidPositionException extends RuntimeException {
public InvalidPositionException(String err) {
super(err);
}
//end#fragment InvalidPositionException
public InvalidPositionException() {
/* default constructor */
}
//begin#fragment InvalidPositionException
}
//end#fragment InvalidPositionException
package Tree;
/**
* Thrown when a key is determined to be invalid.
* @author Roberto Tamassia
*/
public class InvalidKeyException extends RuntimeException {
public InvalidKeyException (String message) {
super (message);
}
public static final long serialVersionUID = 424242L;
}
package Tree;
/**
* Thrown when an entry is discovered to be invalid.
* @author Eric Zamore
*/
public class InvalidEntryException extends RuntimeException {
public InvalidEntryException (String message) {
super (message);
}
}
package Tree;
/**
* Runtime exception thrown when one tries to access the root of an
* empty tree.
*/
public class EmptyTreeException extends RuntimeException {
public EmptyTreeException(String err) {
super(err);
}
}
|
11-04-2007, 11:47
