package dependence question

package dependence question

[Carl Banks]

Okay, when I program, I like to construct large, dynamic tree
structures.  I like my trees to be traversible in any direction, so if
you're sitting on a node, you can access its parent or any of its
branches.

So let's say that a particular tree has a different type of node at
each level.  For example, type A is the root of the tree.  Its
branches are of type B.  B's branches are of type C, and so on.

Let's also say that A, B, and C are not really similar (they are only
similar in that they are in the same tree structure, but bear no
internal resemblance to each other).  A, B, and C really belong in
separate packages.

However, packages can't with each other, meaning that types A and B
can't store access types to each other if they are defined in separate
packages.  It seems that I have to choose between making the tree
traversible in only one direction, or defining A, B, and C in the same
package.

The best solution I could come up with myself is to make A, B, and C
child packages of a package such as Node, and declaring the types A,
B, and C (and their access types) in the Node package, while declaring
functions and procedures in the child packages Node.A, Node.B, and
Node.C.  This is somewhat messy, as it leaves the fields of type A
open to package Node.B, but at least it isolates the functions and
procedures.

My question is, is there a better way to define such a doubly-
traversible tree, so that different node types need not be defined in
the same package?

Thanks.

 
-- 
        ___\___         ____\___
    \  /      .\    \  /       .\
    |><  Carl  <    |><  Banks  <
    /  \_____)_/    /  \______)_/

RE: package dependence question

[Antonio Dur�n Dom�nguez]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 2431 bytes --]

There are different forms for aproaching to the solution. I think the most
flexible is
the object oriented way so that the nodes of the tree are classes (tagged
types) that
inherit from a common class. This provides flexibility (new classes are
easily added) and
separates the tree handling from tree-node handling.

Another approach could be using a variant record to hold the node
information and a
single access type to handle the tree links. This is pretty much Ada 83
style but has the limitation that
the types of nodes must be known at compile time and new types of nodes are
not
easily incorporated to the code.

Carl Banks <oaf@psu.edu> escribi� en el mensaje de noticias
8gt19i$1cm8@r02n01.cac.psu.edu...
> Okay, when I program, I like to construct large, dynamic tree
> structures.  I like my trees to be traversible in any direction, so if
> you're sitting on a node, you can access its parent or any of its
> branches.
>
> So let's say that a particular tree has a different type of node at
> each level.  For example, type A is the root of the tree.  Its
> branches are of type B.  B's branches are of type C, and so on.
>
> Let's also say that A, B, and C are not really similar (they are only
> similar in that they are in the same tree structure, but bear no
> internal resemblance to each other).  A, B, and C really belong in
> separate packages.
>
> However, packages can't with each other, meaning that types A and B
> can't store access types to each other if they are defined in separate
> packages.  It seems that I have to choose between making the tree
> traversible in only one direction, or defining A, B, and C in the same
> package.
>
> The best solution I could come up with myself is to make A, B, and C
> child packages of a package such as Node, and declaring the types A,
> B, and C (and their access types) in the Node package, while declaring
> functions and procedures in the child packages Node.A, Node.B, and
> Node.C.  This is somewhat messy, as it leaves the fields of type A
> open to package Node.B, but at least it isolates the functions and
> procedures.
>
> My question is, is there a better way to define such a doubly-
> traversible tree, so that different node types need not be defined in
> the same package?
>
> Thanks.
>
>
> --
>         ___\___         ____\___
>     \  /      .\    \  /       .\
>     |><  Carl  <    |><  Banks  <
>     /  \_____)_/    /  \______)_/

Re: package dependence question

[Robert Dewar]

In article <8gt19i$1cm8@r02n01.cac.psu.edu>,
  Carl Banks <oaf@psu.edu> wrote:
> However, packages can't with each other, meaning that types A
> and B can't store access types to each other if they are
> defined in separate packages.

This is wrong, or at least over broad. It is fine to have
two packages A and B, where the body of each package with's
the other package and uses its declared types.


Sent via Deja.com http://www.deja.com/
Before you buy.

Re: package dependence question

[Jeff Carter]

Carl Banks wrote:
> 
> Okay, when I program, I like to construct large, dynamic tree
> structures.  I like my trees to be traversible in any direction, so if
> you're sitting on a node, you can access its parent or any of its
> branches.
> 
> So let's say that a particular tree has a different type of node at
> each level.  For example, type A is the root of the tree.  Its
> branches are of type B.  B's branches are of type C, and so on.

Then this isn't really a tree; it's a hierarchy. Trees have the same
type everywhere a value is stored. Hierarchies are shaped like trees,
but are used differently.

I often see people using trees when other structures would be better.
There are certainly ways to achieve what you want, but without a better
understanding of what you are trying to use this structure to achieve I
can't tell which, if any, would be appropriate for your needs.

-- 
Jeff Carter
"Your mother was a hamster and your father smelt of elderberries."
Monty Python & the Holy Grail

Re: package dependence question

[Ray Blaak]

Jeff Carter <jrcarter@acm.org> writes:
> Carl Banks wrote:
> > So let's say that a particular tree has a different type of node at
> > each level.  For example, type A is the root of the tree.  Its
> > branches are of type B.  B's branches are of type C, and so on.
> 
> Then this isn't really a tree; it's a hierarchy. Trees have the same
> type everywhere a value is stored. Hierarchies are shaped like trees,
> but are used differently.

I disagree. A tree is simply a directed graph without cycles. There is no
requirement that all nodes must be of the same type. In particular, a
hierarchy is a tree.

However, in an OO implementation of a tree, all nodes will usually be of a
common type so that one can specify parent/child relationships in one
place. There can certainly be more specialized types for different kinds of
nodes. 

E.g.

 type TreeNode is tagged record
 end record;

 -- common stuff for all nodes, especially knowledge of the parent, child
 -- containers, etc.
 function ParentOf(n : TreeNode) : TreeNode;
 function ChildCount(n : TreeNode) : Natural;
 function ChildAt(n : TreeNode; index : Natural) : TreeNode;
 procedure InsertChild(child : in out TreeNode; intoParent : in out TreeNode);

 -- root node specialization
 type A is new TreeNode with ... end record;

 type B is new TreeNode with ... end record;

 -- leaf nodes?
 type C is new TreeNode with ... end record;

In this case the nodes are simultaneously of the same type (i.e. TreeNode) and
yet are different types (A, B, C, ...).

-- 
Cheers,                                        The Rhythm is around me,
                                               The Rhythm has control.
Ray Blaak                                      The Rhythm is inside me,
blaak@infomatch.com                            The Rhythm has my soul.

Re: package dependence question

[Robert A Duff]

Carl Banks <oaf@psu.edu> writes:

> My question is, is there a better way to define such a doubly-
> traversible tree, so that different node types need not be defined in
> the same package?

There is no ideal solution to this problem in Ada 95 (although the ARG
is currently working on a language modification that will solve the
problem nicely).

One thing you can do is declare tagged type Node, and then "type
Node_Ptr is access all Node'Class;".  Make types A, B, and C derive from
Node.  Then B can have a component like "Parent: Node_Ptr;".  You lose
type checking -- the parent of a B is always an A, but the code doesn't
say so, except in a comment.

Another way to have mutually-recursive types is to create a dummy parent
type for one or more of the types.  Eg, if you have X and Y that point
to each other, you can declare Dummy_X and Dummy_Y as null records, and
point to Dummy_X'Class and Dummy_Y'Class.  Then X is derived from
Dummy_X, adding the actual record components.  Similarly for Y.

- Bob

Re: package dependence question

[Brian Rogoff]

On Tue, 30 May 2000, Robert A Duff wrote:
> Carl Banks <oaf@psu.edu> writes:
> 
> > My question is, is there a better way to define such a doubly-
> > traversible tree, so that different node types need not be defined in
> > the same package?
> 
> There is no ideal solution to this problem in Ada 95 (although the ARG
> is currently working on a language modification that will solve the
> problem nicely).

Would you be willing to elaborate further? Is this a variant of Tucker
Taft's "with type" proposal from a few years back?

-- Brian

Re: package dependence question

[Ray Blaak]

Robert A Duff <bobduff@world.std.com> writes:
> One thing you can do is declare tagged type Node, and then "type
> Node_Ptr is access all Node'Class;".  Make types A, B, and C derive from
> Node.  Then B can have a component like "Parent: Node_Ptr;".  You lose
> type checking -- the parent of a B is always an A, but the code doesn't
> say so, except in a comment.

Put the Parent : Node_Ptr in the Node type. Full type checking can be achieved
by making the constructors for a B node require an A node as a parent
parameter (and in general, a arbitrary node's constructor has a signature in
terms of the required parent node). Safety by construction!

-- 
Cheers,                                        The Rhythm is around me,
                                               The Rhythm has control.
Ray Blaak                                      The Rhythm is inside me,
blaak@infomatch.com                            The Rhythm has my soul.

Re: package dependence question

[Robert I. Eachus]

"Antonio Durán Domínguez" wrote:
 
> There are different forms for aproaching to the solution. I think the most
> flexible is the object oriented way so that the nodes of the tree are
> classes (tagged types) that inherit from a common class. This provides
> flexibility (new classes are easily added) and separates the tree handling > from tree-node handling.

  I think that an even better approach is to use mix-ins.  You create a
tree
type and a node classe in a library package. Then in a nested or child
generic package, you create a specific node type that contains an object
of
the generic formal type:

  generic
    type Content is {tagged} {limited} private;
   {Node_Name: in String;}
  package Tree.Specific_Node is

    type New_Node is new Tree.Node with private;

    generic
      type Data is private;
      with procedure Action(Object: in out New_Node; D: in Data);
    procedure Update(Object: in out New_Node; D: in Data);
   
  private
    -- overridings go here. 
  end Tree.Specific_Node;

  Part of the magic of doing this right is that most of the operations
on a node need to be written once, in the proper place--either as an
operation of the Node type or of the Content type.  The one exception is
that operations that change the value of the contents of the node
require the addition of a generic instance of Update.  If different node
types have lots of different update operations, this can begin to get
painful, especially if you have to create new record types to collect
parameters in.