[java] Aiuto per Dizionario ordinato su albero 234

Condivisione e sviluppo di conoscenze sulle alternative a Microsoft

Moderatore: Moderatori

Rispondi
Avatar utente
bettina86
Paralizzato
Paralizzato
Messaggi: 1
behance Kuchnie Warszawa
Iscritto il: 09 giu 2007 02:00

[java] Aiuto per Dizionario ordinato su albero 234

Messaggio da bettina86 »

Devo finire per l'8 luglio un progetto di dati e algoritmi 1 dell'università di Padova prof. Ferrari.
Devo implementare i metodi di un dizionario ordinato con un albero 234.
Ho già fatto quasi tutto mi manca di fare i metodi entries, findall, last, first, predecessor e successor che magari sono anche una cavolata ma non mi viene in mente niente su questi.
La classe di test, ora funziona non guardate quella del file è ancora vecchia.
Se qualcuno è così gentile da aiutarmi a finirla e a coreggerla dove è sbagliato, grazie.
La rappresentazone dell'albero deve essere parentetica identata cioè il metodo print deve mostrare l'albero con i suoi elementi dei nodi così, con spazi e parentesi.

Codice: Seleziona tutto


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);
  }
	
}

Nel file rar ci sono tutte le altre classi con l'interfaccia commentate.
http://bettina86.altervista.org/progtree24.rar

Aiutatemi, grazie.
Avatar utente
Google
Supporter
Supporter
Messaggi: Tanti
Iscritto il: 17/11/2008, 1:00