4.2. Accessing an Existing Interface

In this section we implement a generic binary tree that holds node values of any type. As you know by now, the way we do that in C# is to declare the node to be of type object. As an additional wrinkle, a node value is inserted only once within a tree. If it occurs another time, we increment an occurrence count. This gives us the chance to look at the IComparable interface. The node class is called TreeNode:

public sealed class TreeNode
{
      private int       m_occurs;
      private object    m_nval;
      private TreeNode  m_lchild, m_rchild;

      // ...
}

For our tree we'll implement several policies that provide opportunities for exercising some of the interfaces defined within the .NET framework. For example, we want to fix the type of the tree after inserting the first element. The tree class is called BinaryTree:

public class BinaryTree
{
   public delegate void Action( ref TreeNode node);
   private Type      m_elemType;
   private TreeNode  m_root;
   private Action    m_nodeAction;
   // ...
}

When the user creates a BinaryTree object, we want it to be able to hold a value of any type. We support that capability by using the type object. Once the user inserts a value, however, we want all the remaining values inserted in that tree to be of the same type. The insertion of a first value locks the type of that tree.

For example, here is how our tree must behave. When we create a new tree, it can hold objects of any type. Once we have inserted an element, however, the tree can store only other elements of that type. For example, when we write

BinaryTree bt = new BinaryTree();

bt can potentially store elements of any type. However, once we write

bt.insert( "Piglet" );

bt becomes a binary tree that holds elements of type string. Subsequent insertions of string elements, such as

bt.insert( "Eeyore" );
bt.insert( "Roo" );

are fine. Each element is inserted within the tree according to the ordering supported by the IComparable interface.

What we want to prevent is a subsequent attempt by the user, after having inserted an object of one type, to insert an object of a different type. For example, if the user writes

bt.insert( 1024);

we want to recognize and flag that the type being inserted is different from the type to which we've previously bound our tree. To do this, we'll throw an exception.

We'll make no further constraints on objects in order for them to be accepted as tree node values. Only types that implement the IComparable interface are accepted. Why? Because each element is passed to us through the object parameter, so we have lost all compile-time type information. The interface provides an ordering service that is type independent—for example,

private IComparable confirm_comparable( object elem )
{
    IComparable ic = elem as IComparable;
    if ( ic == null ){
         string msg = "Element type must support IComparable -- "
                    + elem.GetType().Name
                    + " does not currently do so!";
         throw new ArgumentException( msg );
    }
    return ic;
}

Here is how we might invoke confirm_comparable():

public void insert( object elem )
{
   // if this is the first element
   if ( m_root == null ){
          confirm_comparable( elem );
         m_elemType = elem.GetType();
         m_root = new TreeNode( elem );
   }
   else
   {
          confirm_type( elem );
          m_root.insert_value( elem );
   }
}

insert() checks the element's suitability only with the first insertion of an object of that type. Subsequently, it simply confirms that the new object is of the same type as the initial object. If it is, we insert the element within the tree, as shown here:

public void insert_value( object val )
{
    // assumption is that BinaryTree has confirmed this ...
    IComparable ic = val as IComparable;

    // OK: zero means the two objects are equal
    if ( ic.CompareTo( m_nval ) == 0 ){
         m_occurs++;
         return;
    }

    // OK: less than; insert within left subtree
    if ( ic.CompareTo( m_nval ) < 0 ){
         if ( m_lchild == null )
              m_lchild = new TreeNode( val );
         else m_lchild.insert_value( val );
    }
    else { // insert within right subtree
       if ( m_rchild == null )
            m_rchild = new BTreeNode( val );
       else m_rchild.insert_value( val );
    }
}

When we manipulate an object's actual type, we can pretty much ignore whatever interfaces that type implements. When we manipulate an entity of type object, however, the discovery and use of an interface becomes critical because all compile-time type information is lost. (Alternatively, we can query the object at runtime as to its actual type. We look at type reflection in Section 8.2.)