More cyclic pointers

More cyclic pointers

[mips!zaphod.mps.ohio-state.edu!hobbes.physics.uiowa.edu!ns-mx!pyrite.cs.u]

>From article <26232@darkstar.ucsc.edu>, by karplus@cse.ucsc.edu (Kevin Karplus
):
> Someone (sorry, I don't have the name in front of me) asked for
> examples where cyclic pointer structures were necessary for efficiency.
> 
I also have an application that may qualify.

I have a simulation that involves a number of objects (in the physical
sense).  There are, among other things, people and places.  Each place
may contain a set of people, and each person is in some place.

Two operations are important enough to require efficient implementation:

  1) Find what place a person is in.  This is easily implemented by
      storing a (never null) pointer to the place as part of the data
      associated with each person.

  2) Find all people in a certain place, and find if some particular
      person is in some particular place.  These are easily implemented
      with a (possibly empty) linked list of people rooted at each place.

Of course, the simulation code is strongly encapsulated, so there is a
package Geography that knows all about places but as little as possible
about people, and another package Population that knows almost nothing
about places and everything about people.  Both the types person and
place are private types with implementations hidden in these packages.

I use the usual Ada trick to handle this:

   package POPULATION
   package GEOGRAPHY       -- imports public interface to POPULATION
   package body POPULATION -- imports public interface to GEOGRAPHY

The above lists compilation units in the order that they must be
compiled to correctly allow for the circularity I described.

I should  note that the separation of Population into a separate package
definition and package body may be modelled as a use of inheritance in
an object oriented language.  This separation is essential in this
context, but there is no need to separate the definition and body of
Geography here.

I should note that my simulation has a number of other circularities,
some of which were intermeshed in ways that required more effort to
solve.
				Doug Jones
				jones@cs.uiowa.edu