Problem mit meiner generischen Klasse

[sidex]

hallo leute ich hab folgendes problem.

ich muss ein AVL baum schreiben das Comparable implementiert und generisch ist.
nun so sehen meine zwei Klassen aus:

import java.lang.*;

public class AVLnode implements Comparable<Integer>
{
	public AVLnode left;   //Referenz auf das linke Kindknoten
	public AVLnode right;  //Referenz auf das rechte Kindknoten
	AVLnode top;     //Referenz auf das Elternknoten
	int level;
	int data;
    
	public AVLnode (AVLnode left, AVLnode right, int data)
	{
		this.left = left;
		this.right = right;
		this.data = data;
		
		AVLnode puffer = null;
		
		if ( left != null )
			puffer = left;
		else
			puffer = right;
			
		if ( puffer != null )
		{
			while ( puffer != null )
			{
				++level;
				puffer = puffer.top;
			}
		}
		else
			level = 0;
	}
	
	public int slope (int n1, int n2)
	{
		return Math.abs(n1 - n2);
	}
	
    public int compareTo(Integer n1)
    {
        if (this.data == n1)
            return 0;
        else 
            if ( this.data < n1)
                return -1;
            else 
                return   1;
    }
		
}

public class AVLtree<T extends AVLnode & Comparable<Integer>>
{
	private T root;
	int Llevel;
	int Rlevel;
	int compData;
	
	public AVLtree()
	{
		root = null;
	}
	
	public void search(int value)
	{
		search2( root, value );
	}
	
	private T search2( T root, int value)
	{
		if ( root == null )
			return null;
		else
			compData = root.compareTo( value );
			switch ( compData )
			{
				case  1 :		return search2(root.right, value);
								break;
				case-1 :	return search2(root.left, value);
								break;
				case  0 :		return root;
								break;
			}
	}
	
	public void rebalance()
	{
		
	}
	
	public void depth( T root)
	{
		
	}
	
	public void insert()
	{
		
	}
}

beim build bekomm ich folgende fehlerausgabe:

Compiling 3 source files to /Users/sidex/Stree/bin
/Users/sidex/Stree/src/AVLtree.java:26: search2(T,int) in AVLtree<T> cannot be applied to (AVLnode,int)
				case  1 :		return search2(root.right, value);
                                                               ^
/Users/sidex/Stree/src/AVLtree.java:28: search2(T,int) in AVLtree<T> cannot be applied to (AVLnode,int)
				case-1 :	return search2(root.left, value);
                                                       ^
2 errors

kann mir bitte einer sagen wo der fehler ist? ich raff generics einfach nicht
ich hab schon alles mögliche ausprobiert.
also bitte hilft mir.

mfg sidex

edit: was ich vergessen habe zu sagen. eigentlich sollte die AVLtree klasse so aussehen:

AVLtree<T extends Comparable<Integer>

aber dann bekomm ich bei build ne meldung dass er das Objekt root.right und root.left nicht kennt.
aber wieso meldet der das? werden bei den generischen sachen die Typen nicht erst während der Laufzeit bekannt gegeben?

 

[kama]

Hi,

deine Implementierung arbeitet mit "Integer" und der Aufruf verwendet "int" ?

MfG
Karl Heinz

 

[sidex]

joa hab ich auch gesehen. aber seit der 1.5er version ist es kein problem mehr

 

[Beni]

"search2" erwartet ein T (eine Subklasse von AVLNode), und kein AVLNode. AVLNode.left (oder right) ist aber ein AVLNode und kein T.

Es ist dieselbe Situation wie wenn du einer Methode "setName( String name )" lediglich ein Object übergeben möchtest.

Der ganze Widerspruch kann aufgelöst werden, wenn der AVLNode auch noch ein bisschen generischer wird:

package forum;

public class AVLNode<T extends AVLNode<T>> implements Comparable<Integer>
{
   public T left;   //Referenz auf das linke Kindknoten
   public T right;  //Referenz auf das rechte Kindknoten
   T top;     //Referenz auf das Elternknoten
   int level;
   int data;
   
   public AVLNode (T left, T right, int data)
   {
      this.left = left;
      this.right = right;
      this.data = data;
      
      T puffer = null;
      
      if ( left != null )
         puffer = left;
      else
         puffer = right;
         
      if ( puffer != null )
      {
         while ( puffer != null )
         {
            ++level;
            puffer = puffer.top;
         }
      }
      else
         level = 0;
   }
   
   public int slope (int n1, int n2)
   {
      return Math.abs(n1 - n2);
   }
   
    public int compareTo(Integer n1)
    {
        if (this.data == n1)
            return 0;
        else
            if ( this.data < n1)
                return -1;
            else
                return   1;
    }
      
}

package forum;

public class AVLTree<T extends AVLNode<T> & Comparable<Integer>>
{
   private T root;
   int Llevel;
   int Rlevel;
   int compData;
   
   public AVLTree()
   {
      root = null;
   }
   
   public void search(int value)
   {
      search2( root, value );
   }
   
   private T search2( T root, int value)
   {
      if ( root == null )
         return null;
      else
         compData = root.compareTo( value );
         switch ( compData )
         {
            case  1 : return search2(root.right, value);
            case -1 : return search2(root.left, value);
            case  0 : return root;
            default: throw new IllegalStateException( "Offenbar würde ich hier besser < 0, > 0 und == 0 testen..." );
         }
   }
   
   public void rebalance()
   {
      
   }
   
   public void depth( T root)
   {
      
   }
   
   public void insert()
   {
      
   }
}

----------
Ich frage mich allerdings, wieso es für den Benutzer wichtig sein sollte, welcher Typ Node der Tree verwendet? Das Interface "Comparable" könnte allgemeiner, eleganter eingesetzt werden, so dass der Baum mehr Datentypen speichern kann.
Hier nur ein Überblick, wie das aussehen könnte:

public class AVLTree<T extends Comparable<T>>{
    private AVLNode<T> root;
    
    public boolean search( T value ){
        return search( root, value );
    }
    
    private boolean search( AVLNode<T> node, T value ){
        if( node == null )
            return false;
        
        int compare = node.getValue().compareTo( value );
        if( compare == 0 )
            return true;
        
        if( compare < 0 )
            return search( node.getLeft(), value );
        else
            return search( node.getRight(), value );
    }
}


public class AVLNode<T extends Comparable<T>>{
    private T value;
    private AVLNode<T> left, right;
    
    public AVLNode<T> getLeft() {
        return left;
    }
    public AVLNode<T> getRight() {
        return right;
    }
    public T getValue() {
        return value;
    }
}

 

[Guest]

hi danke schon mal! aber was muss ich dann als Typ an AVLnode übergeben? muss ich dann neue node-Klasse erstellen die von AVLnode erbt und diese an an AVLnode übergeben oder wie?

was wenn ich statt extends super schreibe? dann sollte er doch AVLnode erwarten? und stattdessen bekomm ich ne meldung dass ein < und { fehlt.

gibt es eigentlich irgendwo ein artikel wo generics gut erklärt ist? weil generics ist bis jetzt meine größte schwäche.

mfg sidex

 

[Beni]

Der Node benötigt denselben Typ den schon der Tree hat.

public class Tree<T>{
  public void blabla( T value ){
    root = new AVLNode<T>( value ); // << hier der Typ vom Tree verwenden
  }
}

Der Witz an all den Generics ist, dass hier gerade keine Unterklassen notwendig sind :wink:

Ich denke, das Tutorial hier wird so ziemlich all deine Fragen beantworten (auch das mit super oder extends).