Ashely86
05-04-2007, 19:09
Devo costruire una classe albero 2-3-4 che implementa i metodi della struttura dati ADT Dizionario ordinato con appunto un albero 234 e fare la classe di test.
Il prof mi ha dato tempo fino al 10 luglio, giorno in cui devo spedirgli tutto in uno zip.
Credo debba costruire un oggetto comparatore nuovo ed usare i suoi metodi per fare i confronti altrimenti dice che sono tipi incompatibili e doovrei creare un oggetto iteratore per i metodi che lo richiedono. Nella classe test non è specificato che tipi specificare io ho messo string visto che puoi usare qualsiasi tipo, ma credo possano essere anche key int e value int nella classe di test.
Qualcuno sa come farla, è da giorni che ci provo vengono fuori sempre nuovi errori.
Codice:
package Tree;
import java.util.Iterator;
/** @(#)Dictionary.java
* ADT Dizionario ordinato. Un interfaccia per un dizionario ordinato che immagazzina
* key, value (k,v)di qualsiasi tipo di oggetto. Più entry possono avere la stessa chiave.
* Essendo un dizionario ordinato, è definito un ordine totale per le chiavi.
* @author Elisabetta Scaggion
*/
//begin#fragment Dictionary
public interface Dictionary<K,V> {
//end#fragment Dictionary
/** Ritorna il numero di entry contenute nel dizionario.*/
//begin#fragment Dictionary
public int size();
//end#fragment Dictionary
/** Ritorna se il dizionario è vuoto. */
//begin#fragment Dictionary
public boolean isEmpty();
//end#fragment Dictionary
/** Ritorna un entry contenente la data chiave,o null se tale entry non esiste. */
//begin#fragment Dictionary
public Entry<K,V> find(K key)
throws InvalidKeyException1;
//end#fragment Dictionary
/** Ritorna un iteratore che contiene tutte le entry con la data chiave, o
* o un iteratore vuoto se tali entries non esistono. */
//begin#fragment Dictionary
public Iterable<Entry<K,V>> findAll(K key)
throws InvalidKeyException1;
//end#fragment Dictionary
/** Inserisci un oggetto nel dizionario. Ritorna la nuova entry creata. */
//begin#fragment Dictionary
public Entry<K,V> insert(K key, V value)
throws InvalidKeyException1;
//end#fragment Dictionary
/** Rimuovi e ritorna la data entry dal dizionario. */
//begin#fragment Dictionary
public Entry<K,V> remove(Entry<K,V> e)
throws InvalidEntryException1;
/** Ritorna l'entry con la più piccola chiave. */
public Entry<K,V> first() ;
/** Return entry with the largest key */
public Entry<K,V> last();
/** Ritorna un iteratore delle entries con chiavi più grandi di o uguali a k, in non decrescente ordine*/
public Iterable<Entry<K,V>> successor(K Key)
throws InvalidKeyException1;
/**Ritorna un iterator delle entries con chiavi meno di o uguali a k, in non decrescente ordine*/
public Iterable<Entry<K,V>> predecessor(K Key)
throws InvalidKeyException1 ;
//end#fragment Dictionary
/** Ritorna un iteratore contenente tutte le entries nel dizionario. */
//begin#fragment Dictionary
public Iterable<Entry<K,V>> entries();
}
//end#fragment Dictionary
Classe albero 2-3-4 che deve implementare i metodi di Dictionary<K,V>:
package Tree;
/**
* @(#)Tree2341.java
*
*
* @author
* @version 1.00 2007/3/11
*/
public class Tree234<K,V> implements Dictionary<K,V> {
private Tree234Node<K,V> root = new Tree234Node<K,V>();
/**
* keys è il numero di chiavi nel dizionario.
* root è la radice del 2-3-4 tree.
*
**/
K key;
V value;
protected int numeroEntries =0;
public Tree234() {
root = null;
keys = 0;
}
public Entry<K,V> insert(K key, V Value) throws InvalidKeyException1; {}
// -------------------------------------------------------------
public Entry<K,V> find(K key)
{
Tree234Node<K,V> curNode = root;
int childNumber;
while(true)
{
if(( childNumber=curNode.find(key) ) != -1)
return childNumber; // trovala
else if( curNode.isLeaf() )
return -1; // non la trova
else // cerca più profondo
curNode = getNextChild(curNode, key);
}
}
// -------------------------------------------------------------
// inserisci un Entry
public Entry<K,V> insert(K dValue)
{
} // end insert()
}
// -------------------------------------------------------------
/** split il nodo*/
public void split(Tree234Node<K,V> thisNode)
{
DataItem<K,V> itemB, itemC;
Tree234Node<K,V> parent, child2, child3;
int itemIndex;
itemC = thisNode.removeItem();
itemB = thisNode.removeItem();
child2 = thisNode.disconnectChild(2);
child3 = thisNode.disconnectChild(3);
Tree234Node<K,V> newRight = new Tree234Node<K,V>();
if(thisNode==root)
{
root = new Tree234Node<K,V>();
parent = root;
root.connectChild(0, thisNode);
}
else
parent = thisNode.getParent();
// deal with parent
itemIndex = parent.insertItem(itemB);
int n = parent.getNumItems();
for(int j=n-1; j>itemIndex; j--)
{
Tree234Node<K,V> temp = parent.disconnectChild(j);
parent.connectChild(j+1, temp);
}
parent.connectChild(itemIndex+1, newRight);
// deal with newRight
newRight.insertItem(itemC);
newRight.connectChild(0, child2);
newRight.connectChild(1, child3);
} // end split()
// -------------------------------------------------------------
/** prendi l'appropriato figlio del nodo durante la ricerca per valore*/
public Tree234Node<K,V> getNextChild(Tree234Node<K,V> theNode, V value)
{
int j;
// assumi il nodo non vuoto, non pieno, non una foglia
int numItems = theNode.getNumItems();
for(j=0; j<numItems; j++)
{
if( value < theNode.getItem(j).dData )
return theNode.getChild(j);
} // end for
return theNode.getChild(j);
}
// -------------------------------------------------------------\
public Entry<K,V> delete() {
}
/** */
public final boolean isEmpty() {
return size()==0;
}
/** */
public int size(){ return numeroEntries;
}
/**
*@param key la chiave da ritornare nell'iteratore */
public Iterable<Entry<K,V>> findAll(K key)throws InvalidKeyException1{
}
/** Ritorna un iteratore contenente le entries */
public Iterable<Entry<K,V>> entries(){
}
/** Ritorna entry con chiave più piccola */
public Entry<K,V> first(){
}
/** Ritorna entry con chiave più grande */
public Entry<K,V> last(){
}
/**
*@param key */
public Iterable<Entry<K,V>> successor(K Key)
throws InvalidKeyException1{
}
/**
*@param key */
public Iterable<Entry<K,V>> predecessor(K Key)
throws InvalidKeyException1 {
}
/** Mostra l'albero come è fatto
* Esempio: A (
B
C (
D
)
E
)
radice A
A ha tre figli B C E
c ha un figlio D */
public <K,V>String rappresentazioneParenteticaIdentata( ){
}
}
Classe che nodo del 2-3-4 che contengono le key, value:
/* Tree234Node.java */
package Tree;
/**
* A Tree234Node è un nodo in un 2-3-4 tree.
*
**/
public class Tree234Node<K,V> {
/**
* keys è il numero di chiavi nel nodo.Sempre 1, 2, o 3.
* key1 a key3 sono le chiavi di questo nodo. Se keys == 1, the value
* of key2 doesn't matter. Se keys < 3, the value of key3 doesn't matter.
* parent è il genitore di questo nodo; null se questo è root.
* child1 a child4 sono i figli di questo nodo. Se questo è un nodo foglia,
* essi devono essere messi a null. Se questo nodo non ha 3 e/o 4 figli,
* child3 e/o child4 devono essere messi a null.
**/
private int keys;
private K key1;
private K key2;
private K key3;
private V value1;
private V value2;
private V value3;
private Tree234Node<K,V> parent;
private Tree234Node<K,V> child1;
private Tree234Node<K,V> child2;
private Tree234Node<K,V> child3;
private Tree234Node<K,V> child4;
public Tree234Node<K,V>(Tree234Node<K,V> p, K key) {
keys = 1;
key1 = key;
parent = p;
child1 = null;
child2 = null;
child3 = null;
child4 = null;
}
}
Interfaccia Entry<K,V>
package Tree;
/**
* @(#)Entry.java
*
*
* @author Elisabetta Scaggion
* @version 1.00 2007/3/12
*/
/** Interfaccia per chiave, valore generiche **/
public interface Entry<K,V> {
/**@return K ritorna la chiave in questo entry. */
public K key();
/**@return V ritorna il valore immagazzinato in questo entry. */
public V value();
}
Classe DataItem che implementa Entry:
package Tree;
/**
* @(#)DataItem.java
* Implementazione dell'interfaccia Entry<K,V>
*
* @author Elisabetta Scaggion
*
*/
class DataItem implements Entry<K,V>
{
public <K,V>entry; // un data item
//--------------------------------------------------------------
public DataItem(<K,V> dd) // costruttore
{ entry = dd; }
/** ritorna il valore
*@return key*/
public V value(){return value;
}
/**ritorna il valore della chiave
*@return key */
public K key(){return key;
}
Classi InvalidKeyException1 e InvalidEntryException1:
package Tree;
/**
* @(#)InvalidKeyException1.java
*
*
* @author Elisabetta Scaggion
* @version 1.00 2007/3/12
*/
public class InvalidKeyException1 extends RuntimeException {
/**Costruttore */
public InvalidKeyException1(String message)
{super(message);
} public static final long serialVersionUID = 424242L;
}
package Tree;
/**
* @(#)InvalidEntryException1.java
*
*
* @author Elisabetta Scaggion
* @version 1.00 2007/3/7
*/
public class InvalidEntryException1 extends RuntimeException {
/** Costruttore */
public InvalidEntryException1 (String message) {
super (message);
}
}
Il prof mi ha dato tempo fino al 10 luglio, giorno in cui devo spedirgli tutto in uno zip.
Credo debba costruire un oggetto comparatore nuovo ed usare i suoi metodi per fare i confronti altrimenti dice che sono tipi incompatibili e doovrei creare un oggetto iteratore per i metodi che lo richiedono. Nella classe test non è specificato che tipi specificare io ho messo string visto che puoi usare qualsiasi tipo, ma credo possano essere anche key int e value int nella classe di test.
Qualcuno sa come farla, è da giorni che ci provo vengono fuori sempre nuovi errori.
Codice:
package Tree;
import java.util.Iterator;
/** @(#)Dictionary.java
* ADT Dizionario ordinato. Un interfaccia per un dizionario ordinato che immagazzina
* key, value (k,v)di qualsiasi tipo di oggetto. Più entry possono avere la stessa chiave.
* Essendo un dizionario ordinato, è definito un ordine totale per le chiavi.
* @author Elisabetta Scaggion
*/
//begin#fragment Dictionary
public interface Dictionary<K,V> {
//end#fragment Dictionary
/** Ritorna il numero di entry contenute nel dizionario.*/
//begin#fragment Dictionary
public int size();
//end#fragment Dictionary
/** Ritorna se il dizionario è vuoto. */
//begin#fragment Dictionary
public boolean isEmpty();
//end#fragment Dictionary
/** Ritorna un entry contenente la data chiave,o null se tale entry non esiste. */
//begin#fragment Dictionary
public Entry<K,V> find(K key)
throws InvalidKeyException1;
//end#fragment Dictionary
/** Ritorna un iteratore che contiene tutte le entry con la data chiave, o
* o un iteratore vuoto se tali entries non esistono. */
//begin#fragment Dictionary
public Iterable<Entry<K,V>> findAll(K key)
throws InvalidKeyException1;
//end#fragment Dictionary
/** Inserisci un oggetto nel dizionario. Ritorna la nuova entry creata. */
//begin#fragment Dictionary
public Entry<K,V> insert(K key, V value)
throws InvalidKeyException1;
//end#fragment Dictionary
/** Rimuovi e ritorna la data entry dal dizionario. */
//begin#fragment Dictionary
public Entry<K,V> remove(Entry<K,V> e)
throws InvalidEntryException1;
/** Ritorna l'entry con la più piccola chiave. */
public Entry<K,V> first() ;
/** Return entry with the largest key */
public Entry<K,V> last();
/** Ritorna un iteratore delle entries con chiavi più grandi di o uguali a k, in non decrescente ordine*/
public Iterable<Entry<K,V>> successor(K Key)
throws InvalidKeyException1;
/**Ritorna un iterator delle entries con chiavi meno di o uguali a k, in non decrescente ordine*/
public Iterable<Entry<K,V>> predecessor(K Key)
throws InvalidKeyException1 ;
//end#fragment Dictionary
/** Ritorna un iteratore contenente tutte le entries nel dizionario. */
//begin#fragment Dictionary
public Iterable<Entry<K,V>> entries();
}
//end#fragment Dictionary
Classe albero 2-3-4 che deve implementare i metodi di Dictionary<K,V>:
package Tree;
/**
* @(#)Tree2341.java
*
*
* @author
* @version 1.00 2007/3/11
*/
public class Tree234<K,V> implements Dictionary<K,V> {
private Tree234Node<K,V> root = new Tree234Node<K,V>();
/**
* keys è il numero di chiavi nel dizionario.
* root è la radice del 2-3-4 tree.
*
**/
K key;
V value;
protected int numeroEntries =0;
public Tree234() {
root = null;
keys = 0;
}
public Entry<K,V> insert(K key, V Value) throws InvalidKeyException1; {}
// -------------------------------------------------------------
public Entry<K,V> find(K key)
{
Tree234Node<K,V> curNode = root;
int childNumber;
while(true)
{
if(( childNumber=curNode.find(key) ) != -1)
return childNumber; // trovala
else if( curNode.isLeaf() )
return -1; // non la trova
else // cerca più profondo
curNode = getNextChild(curNode, key);
}
}
// -------------------------------------------------------------
// inserisci un Entry
public Entry<K,V> insert(K dValue)
{
} // end insert()
}
// -------------------------------------------------------------
/** split il nodo*/
public void split(Tree234Node<K,V> thisNode)
{
DataItem<K,V> itemB, itemC;
Tree234Node<K,V> parent, child2, child3;
int itemIndex;
itemC = thisNode.removeItem();
itemB = thisNode.removeItem();
child2 = thisNode.disconnectChild(2);
child3 = thisNode.disconnectChild(3);
Tree234Node<K,V> newRight = new Tree234Node<K,V>();
if(thisNode==root)
{
root = new Tree234Node<K,V>();
parent = root;
root.connectChild(0, thisNode);
}
else
parent = thisNode.getParent();
// deal with parent
itemIndex = parent.insertItem(itemB);
int n = parent.getNumItems();
for(int j=n-1; j>itemIndex; j--)
{
Tree234Node<K,V> temp = parent.disconnectChild(j);
parent.connectChild(j+1, temp);
}
parent.connectChild(itemIndex+1, newRight);
// deal with newRight
newRight.insertItem(itemC);
newRight.connectChild(0, child2);
newRight.connectChild(1, child3);
} // end split()
// -------------------------------------------------------------
/** prendi l'appropriato figlio del nodo durante la ricerca per valore*/
public Tree234Node<K,V> getNextChild(Tree234Node<K,V> theNode, V value)
{
int j;
// assumi il nodo non vuoto, non pieno, non una foglia
int numItems = theNode.getNumItems();
for(j=0; j<numItems; j++)
{
if( value < theNode.getItem(j).dData )
return theNode.getChild(j);
} // end for
return theNode.getChild(j);
}
// -------------------------------------------------------------\
public Entry<K,V> delete() {
}
/** */
public final boolean isEmpty() {
return size()==0;
}
/** */
public int size(){ return numeroEntries;
}
/**
*@param key la chiave da ritornare nell'iteratore */
public Iterable<Entry<K,V>> findAll(K key)throws InvalidKeyException1{
}
/** Ritorna un iteratore contenente le entries */
public Iterable<Entry<K,V>> entries(){
}
/** Ritorna entry con chiave più piccola */
public Entry<K,V> first(){
}
/** Ritorna entry con chiave più grande */
public Entry<K,V> last(){
}
/**
*@param key */
public Iterable<Entry<K,V>> successor(K Key)
throws InvalidKeyException1{
}
/**
*@param key */
public Iterable<Entry<K,V>> predecessor(K Key)
throws InvalidKeyException1 {
}
/** Mostra l'albero come è fatto
* Esempio: A (
B
C (
D
)
E
)
radice A
A ha tre figli B C E
c ha un figlio D */
public <K,V>String rappresentazioneParenteticaIdentata( ){
}
}
Classe che nodo del 2-3-4 che contengono le key, value:
/* Tree234Node.java */
package Tree;
/**
* A Tree234Node è un nodo in un 2-3-4 tree.
*
**/
public class Tree234Node<K,V> {
/**
* keys è il numero di chiavi nel nodo.Sempre 1, 2, o 3.
* key1 a key3 sono le chiavi di questo nodo. Se keys == 1, the value
* of key2 doesn't matter. Se keys < 3, the value of key3 doesn't matter.
* parent è il genitore di questo nodo; null se questo è root.
* child1 a child4 sono i figli di questo nodo. Se questo è un nodo foglia,
* essi devono essere messi a null. Se questo nodo non ha 3 e/o 4 figli,
* child3 e/o child4 devono essere messi a null.
**/
private int keys;
private K key1;
private K key2;
private K key3;
private V value1;
private V value2;
private V value3;
private Tree234Node<K,V> parent;
private Tree234Node<K,V> child1;
private Tree234Node<K,V> child2;
private Tree234Node<K,V> child3;
private Tree234Node<K,V> child4;
public Tree234Node<K,V>(Tree234Node<K,V> p, K key) {
keys = 1;
key1 = key;
parent = p;
child1 = null;
child2 = null;
child3 = null;
child4 = null;
}
}
Interfaccia Entry<K,V>
package Tree;
/**
* @(#)Entry.java
*
*
* @author Elisabetta Scaggion
* @version 1.00 2007/3/12
*/
/** Interfaccia per chiave, valore generiche **/
public interface Entry<K,V> {
/**@return K ritorna la chiave in questo entry. */
public K key();
/**@return V ritorna il valore immagazzinato in questo entry. */
public V value();
}
Classe DataItem che implementa Entry:
package Tree;
/**
* @(#)DataItem.java
* Implementazione dell'interfaccia Entry<K,V>
*
* @author Elisabetta Scaggion
*
*/
class DataItem implements Entry<K,V>
{
public <K,V>entry; // un data item
//--------------------------------------------------------------
public DataItem(<K,V> dd) // costruttore
{ entry = dd; }
/** ritorna il valore
*@return key*/
public V value(){return value;
}
/**ritorna il valore della chiave
*@return key */
public K key(){return key;
}
Classi InvalidKeyException1 e InvalidEntryException1:
package Tree;
/**
* @(#)InvalidKeyException1.java
*
*
* @author Elisabetta Scaggion
* @version 1.00 2007/3/12
*/
public class InvalidKeyException1 extends RuntimeException {
/**Costruttore */
public InvalidKeyException1(String message)
{super(message);
} public static final long serialVersionUID = 424242L;
}
package Tree;
/**
* @(#)InvalidEntryException1.java
*
*
* @author Elisabetta Scaggion
* @version 1.00 2007/3/7
*/
public class InvalidEntryException1 extends RuntimeException {
/** Costruttore */
public InvalidEntryException1 (String message) {
super (message);
}
}