Misunderstanding, silly error, or compiler bug?

[Derek Parnell]

On Fri, 10 Aug 2007 09:08:21 -0400, Peter C. Chapin wrote:

> I'm using dmd v1.020 and I'm trying to write a simple binary tree
> template as an exercise. 

I had a go at a different implementation ...

// --- tree.d ----
class Tree(T) {
    private {

        // Nodes are handled by reference.
        class Node {
            private{
                Node left;
                Node right;
                Node parent;
                T    data;
            }
                this(T new_item, Node p = null)
                {
                    data  = new_item;
                    parent = p;
                    ++count;
                }
        };

        Node  root;
        uint  count;
    }

    this( )
    {
        root  = null;
        count = 0;
    }

    uint size()
    {
        return count;
    }

    // Adds a copy of the new_item to the tree.
    void insert( T new_item )
    {
        Node current;

        if (root is null)
        {
            root = new Node(new_item);
            return;
        }

        current = root;
        while( current !is null )
        {
            Node* p;
            if( new_item < current.data )
            {
                p = &current.left;
            }
            else if( new_item > current.data )
            {
                p = &current.right;
            }
            else return; // Duplicates not permitted

            if ((*p) is null)
            {
                (*p) = new Node(new_item, current);
                current = null;
            }
            else
            {
                current = (*p);
            }
        }
    }

    T[] list()
    {
        return list(root);
    }

    T[] list( Node x )
    {
        T[] l;
        if (x !is null)
        {
            l ~= list(x.left);
            l ~= x.data;
            l ~= list(x.right);
        }
        return l;
    }
}

// -- tree_driver.d
import tree;
import std.stdio;
void main( )
{
    auto my_tree = new Tree!(string);
    my_tree.insert( "david" );
    my_tree.insert( "john" );
    my_tree.insert( "colleen" );
    my_tree.insert( "debra" );
    my_tree.insert( "rosie" );
    my_tree.insert( "bevan" );
    my_tree.insert( "eric" );
    my_tree.insert( "roger" );
    my_tree.insert( "anne" );
    my_tree.insert( "michael" );

    writefln("Tree has %s elements", my_tree.size);
    writefln("Tree contains %s", my_tree.list);
}



-- 
Derek Parnell
Melbourne, Australia
skype: derek.j.parnell