From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me
X-Spam-Level: 
X-Spam-Status: No, score=-1.3 required=5.0 tests=BAYES_00,INVALID_MSGID
	autolearn=no autolearn_force=no version=3.4.4
X-Google-Language: ENGLISH,ASCII-7-bit
X-Google-Thread: 103376,9dc3ec65f25a921e,start
X-Google-Attributes: gid103376,public
From: Chris Jones <cbj1329@is2.nyu.edu>
Subject: Digital Search Tree in Multiple Packages.
Date: 1996/04/04
Message-ID: <3164A1FA.41C67EA6@is2.nyu.edu>#1/1
X-Deja-AN: 145902905
cc: cbj1329@is2.nyu.edu
content-type: text/plain; charset=us-ascii
organization: New York University
mime-version: 1.0
newsgroups: comp.lang.ada
x-mailer: Mozilla 2.0 (X11; I; SunOS 4.1.3_U1 sun4m)
Date: 1996-04-04T00:00:00+00:00
List-Id: <comp.lang.ada>

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.