Digital Search Tree in Multiple Packages.

Digital Search Tree in Multiple Packages.

[Chris Jones]

I wanted to create a digital search tree (trie) from the following
components:

1.  Character_Node: essentially a character, and a pointer to 
an Alphabet_Node containing a list of valid letters following it.

2.  Alphabet_Node : an ordered list of character_nodes

3.  Digital_Search_Tree: Just a pointer to a top level Alphabet_Node.

I thought it would be nice to create a generic Linked_List package,
(admittedly with some characteristics unique to Digital Search Tree
needs) and instantiate it to create Alphabet_Node.  The generic
declaration was as follows:

generic

  type Element_Type is private;
  type Element_Ptr  is access Element_Type;

  type Key_Type is ( <> );
  with function Get_Key( Element: Element_Type ) return Key_Type;

package Linked_List is

  type List_Type is limited private; 

-- sensible list operations here.
...

Now, I wanted to instantiate this package and declare my digital search
tree as follows:

private -- declarations in my Digital_Search_Tree spec

  type Char_Node_Ptr is access Character_Node;

  function Get_Char
    ( Node: Character_Node ) return Character;

  package Alphabet_Node is new
    Linked_List( Element_Type => Character_Node,
		 Element_Ptr  => Char_Node_Ptr,
		 Key_Type     => Character,
		 Get_Key      => Get_Char );

  type Alphabet_Node_Ptr is access Alphabet_Node.List_Type;

  type Character_Node is
    record

      Char             : Character;    
      Remaining_Letters: Alphabet_Node_Ptr;
      Is_Valid_Ending  : Boolean := False;

    end record;

  -- each character must keep track of the list of
  -- characters which can follow it (Remaining_Letters is not
  -- optional)

  type Digital_Search_Tree is new Alphabet_Node_Ptr;

...

The point is that Character_Node must appear in the instantiation of
Linked_List, but it must contain a pointer to a type (list_type) in the
package which it is instantiating.

The question: how can I spread my digital search tree over multiple
packages?  Since Character_Node must be a component in the linked list
type (Alphabet_Node), but it must also contain a pointer to the linked
list type, I don't see how to do this.  

Is the problem that I have mutually recursive types across packages?  

1.  Character_Node contains a pointer to List_Type

2.  (the tricky one) List_Type contains a pointer to the generic formal
parameter Element_Type, but Element_Type is Character_Node after
instantiation, So it effectively contains a pointer to Character_Node

3. List_Type and Character_Node are in different packages.

So, the types are mutually recursive across packages???

Can someone suggest an elegant work around (not just "put all
declarations in the Digital_Search_Tree package" ).

thanks for your time (long post ;-)
chris jones.