views:

190

answers:

4

Hi all!

I'm working on an AVL Tree. The tree itself seems to be working but I need a iterator to walk through the values of the tree. Therefore I tried to implement the IEnumerator interace. Unfortunately I get a compile time error implementing IEnumerator and IComparable. First the code and below that the error.

class AvlTreePreOrderEnumerator<T> : IEnumerator<T> where T :IComparable<T>
{
    private AvlTreeNode<T> current = default(T);
    private AvlTreeNode<T> tree = null;
    private Queue<AvlTreeNode<T>> traverseQueue = null;

    public AvlTreePreOrderEnumerator(AvlTreeNode<T> tree)
    {
        this.tree = tree;

        //Build queue
        traverseQueue = new Queue<AvlTreeNode<T>>();
        visitNode(this.tree.Root);
    }

    private void visitNode(AvlTreeNode<T> node)
    {
        if (node == null)
            return;
        else
        {
            traverseQueue.Enqueue(node);
            visitNode(node.LeftChild);
            visitNode(node.RightChild);
        }
    }

    public T Current
    {
        get { return current.Value; }
    }

    object IEnumerator.Current
    {
        get { return Current; }
    }

    public void Dispose()
    {
        current = null;
        tree = null;
    }

    public void Reset()
    {
        current = null;
    }

    public bool MoveNext()
    {
        if (traverseQueue.Count > 0)
            current = traverseQueue.Dequeue();
        else
            current = null;

        return (current != null);
    }
}

The error given by VS2008: Error 1 The type 'T' cannot be used as type parameter 'T' in the generic type or method 'Opdr2_AvlTreeTest_Final.AvlTreeNode'. There is no boxing conversion or type parameter conversion from 'T' to 'System.IComparable'.

This error is given on the following lines:

    //members
    private AvlTreeNode<T> current = default(T);  //current highlighted
    private AvlTreeNode<T> tree = null;   //tree highlighted
    private Queue<AvlTreeNode<T>> traverseQueue = null;   //traverseQueue highlighted  

    //Constructor
    public AvlTreePreOrderEnumerator(AvlTreeNode<T> tree)  // AvlTreePreOrderEnumerator highlighted  
    //Method
    private void visitNode(AvlTreeNode<T> node)   //visitNode highlighted  

For now I've not included the tree and node logic. I anybody thinks it is necessary to resolve this problem, just say so!

Thx!

+1  A: 

While you haven't posted the actual code causing the error (Opdr2_AvlTreeTest_Final.AvlTreeNode) yet, I strongly suspect the problem is that you are using this class in a generic method/type with a type parameter that's not constrained to implement IComparable<T>.

You can reproduce a similar error with a simple example:

// no problem here at definition site:
void IsLarger<T>(T a, T b) where T : IComparable<T> {
   return a.CompareTo(b) > 0;
}

void Test<T>(T arg) { // note: T is not necessarily IComparable<T>
   Console.WriteLine(IsLarger(arg, arg)); // The compiler shouldn't allow this.
}
Mehrdad Afshari
+2  A: 

Could you try changing it to this

class AvlTreePreOrderEnumerator<T> : IEnumerator<T> where T :IComparable

Lester
This was the solution, after I removed the <T> behind IComarable the compiler showed me another error. That error pointed me on the fact that I've made a stupid mistake. From the three members: private AvlTreeNode<T> current = default(T); private AvlTreeNode<T> tree = null; private Queue<AvlTreeNode<T>> traverseQueue = null; the second member shouldn't be AvlTreeNode<T> but AvlTree<T> instead. After I changed it, everything was ok :) Thanks for your help guys!
+1  A: 

As pointed out already, you haven't included all the code, but you only constrained T to IComparable<T>, whereas the error you've listed is that it want's T to implement IComparable (i.e. the non-generic form of IComparable)

Richard Mason
+3  A: 

I suspect you declared your node class as this:

public class AvlTreeNode<T> where T : IComparable<AvlTreeNode<T>> {
    public AvlTreeNode<T> Root;
    public AvlTreeNode<T> LeftChild {get;set;}
    public AvlTreeNode<T> RightChild {get;set;}
    public T Value { get; set;}
}

Try this (changed IComparable parameter type):

public class AvlTreeNode<T> where T : IComparable<T> {
    public AvlTreeNode<T> Root;
    public AvlTreeNode<T> LeftChild {get;set;}
    public AvlTreeNode<T> RightChild {get;set;}
    public T Value { get; set;}
}

You also have to change your current field to this:

private AvlTreeNode<T> current = new AvlTreeNode<T>();
Fernando