A VERY early draft of an API for the parallel oct-tree library.
I've left a lot out - some intentionally, and some not.  PLEASE DO NOT
DISTRIBUTE!

The basic functionality is to create a parallel, distributed, adaptive
oct-tree data structure.  Once created, the tree is considered
"read-only" and may not be changed by the application.  It
may be traversed, in parallel, as many times as one wishes.

The basic element in a tree is a 'cell'.  This is represented in the


This document and the library it describes are evolving.  It is a
virtual certainty that the details of the language bindings will
change over time.  Basic functionality may also be added, and some
features may not survive.

Peano-Hilbert curves and keys.
------------------------------

Before we get into tree creation and usage it's important to understand
Peano-Hilbert curves and keys.  <NEED A FIGURE>.  

Consider some particular level, l, in an oct-tree.  There are 2^{3l}
potential cells in this level, so we can uniquely identify them with a
3l-bit binary number, or an l-digit octal number.  (Note, the tree
library works equally well with one, two and four-dimensional trees,
but it just obscures the main issues to express that arbitrariness in
this document.)  We can distinguish one level from another by
prepending a single bit to the 3l-bits that make up the number.  Thus,
01530 is on level two, while 0100530 is a different cell on level four
(counting from the root at level 0).

There are many possible ways to number the cells in each level.  One
obvious one is to just take the x, y and z binary coordinates (each an
l-bit number) and concatenate them.  Another way is to take x, y and z
and interleave the bits.  A slight generalization is to take one bit at a
time from x, y and z and permute them in groups of three bits at a
time.  Numberings generated this way are called Keys in the treecode.
If we are careful about the permutations we use, then the key will 
have the useful property that the
mapping from keys (considered as a 3l-bit number) to 3-space
(considered as a triple of l-bit numbers) is continuous.  Neighbors in
key-space are neighbors in 3-space.  A number of other very useful
properties result as well.  The key of the parent of a cell is easily
obtained by right-shifting the key of the cell.  The keys of the
daughters of a cell are obtained by left-shifting the key of the cell
and filling in 0-7 in the low three bits.  Cartesian neighbors are not
so simple, but can also be obtained by bitwise manipulations.

The tree library has a sub-library for working with multi-word keys,
including functions for creating keys, shifting, arithmetic and
comparison.  These functions are defined in "key.h", and have names
like KeyInt, KeyRshift, KeyAdd, KeyEQ, etc.  They are usually
inlined and pretty fast.

There are also functions for converting from 3-dimensional
floating-point coordinates to a key representation and back.  These
functions need additional arguments describing a bounding box in the
floating-point coordinate system, so that the floating point coords
can first be integerized, and then interleaved into a key.  They
are in "keycvt.h".

Although the trees are in principal adaptive and infinitely deep, it
is convenient to assume that there is a maximum depth that will not be
exceeded.  In practice, we have not had trouble with 21 levels
(corresponding to 64-bit keys), but we could easily switch over to
96-bit (on 32-bit architectures) or 128-bit (on 64-bit architectures)
giving us essentially unlimited adaptivity.  Note that 21 levels gives
a dynamic range in length-scales of 2million, or a dynamic range in
densities of nearly 10^{19}.  Note also that there are only 24 bits of
mantissa in an IEEE single-precision floating-point number.

When we convert floating point coords into keys, we convert them into
keys that correspond to the maximum depth of the tree.  That is, the
functions that convert float triples into keys always produce keys
that are fully 64-bits long.  We call these "body keys", in contrast
to "cell keys", which are 3l+1 bits long, for l<L (L=21 in practice).

Tree Creation: 
--------------

--------------
void TreeBuildStart(tree_t *tp, int ndim, int m, BuildFuncs_t *Bfuncs);

Trees carry a small number of immutable properties.  First of all,
they have a specific dimensionality.  Ndim is typically either 2 or 3,
but 1 or 4 ought to work.  The library currently doesn't deal with
higher dimensional trees, but it could be made to do so.

Second, trees are defined in terms of a "terminal occupancy"
parameter.  This is a (small) positive integer that gives the maximum
number of 'bodies' that can exist within a cell before we subdivide
further.  That is, if the terminal occupancy is 'm', then any cubical
cell with more than m bodies will be represented as a 'sib_group' in
the tree.  Cubical regions with fewer than 'm' bodies are not
explicitly represented in the tree.  Rather, the bodies are members of
some sib_group representing a larger cube.  (We'll return later to a
discussion of exactly how and where the data in the tree is
represented.)

The Callbacks are intentionally vague at this point.  They are in a
state of flux.  Basically, they tell the tree-building routines how to
attach data to internal nodes of the tree based on data from lower
down.  These caller-supplied functions are called by the tree-building
library at appropriate times in the tree-building process.  For
example, when it can be guaranteed that all the bodies in a given
volume have been encountered, it is appropriate to call a function
that computes their center of mass (or whatever the physics requires)
and stores it in the cell that represents those bodies.  The Callbacks
are complicated by the fact that memory consumption is often a
limiting factor for whether a given problem can be run.  Therefore, a
simple interface has given way to one that distinguishes between
"intermediate" and "permanent" forms of cell-based data.

A concrete example may be helpful.  In a simple Coulomb evaluator we
need the dipole moment of the charges associated with a cell to
compute the approximate field created by that cell.  We also need one
or two additional values (called B2 and B3 - the details are
irrelevant) to provide error bounds on the approximation.  These are
the "permanent" data associated with a cell.  But in order to compute
B2 and B3 for a cell, we need all the quadrupole moments of the charge
distribution.  Therefore, the "temporary" data includes the quadrupole
moments, and is considerably larger than the permanent data.  Since
the tree library only needs storage for O(log(N)) "temporary" data
items, whereas it needs storage for O(N) "permanant" data items, the
savings can be substantial if the temporary state is much larger than
the permanent state.  A side effect of reducing memory consumption is
more effective use of limited memory bandwidth, which often manifests
itself as improved overall performance.

The Callbacks include a function for aggregating the descendents of a
cell ("temporary" cell-data plus bodies) into a new "temporary"
object.  There is another function that converts a temporary object
into a permanent object.  Some other functions that return size
information may also be included.  This part of the library is still
in a state of flux.

--------------------
TreeBuildAdd(tree_t *tp, Key_t key, void *data, size_t datasz);

  TreeBuildAdd adds a new "body" do the tree.  Bodies are the terminal
objects in the tree.  The caller may attach any data whatsoever to the
body.  The data need not even be the same size from one body to the
next.  All the bodies in a given cell will be copied into contiguous
storage and can be accessed when the cell is visited during a tree
traversal.  The copy is made by TreeBuildAdd itself, so alterations to
the contents of 'data' made after calling TreeBuildAdd will NOT BE
REFLECTED in the data stored in the tree.  This restriction allows a
major performance gain: the contents of the tree are 'read-only' and
caching is straightforward and effective.

MAJOR RESTRICTION:  Currently, the tree library requires that bodies
be added with strictly increasing keys.  That is, within any one
processor, the keys must be sorted in increasing order, and processors
may not have overlapping key ranges.  This restriction
allows the library to know when a cell is "complete", and to issue
callbacks as quickly as possible.  This restriction is crucial to the
memory-saving associated with "permanent" and "temporary" cells.
It >>MAY<< be possible to relax this restriction, but it would entail a
significant overhead in terms of memory.

-------------------------
TreeBuildFinish(tree_t *tp);

 Called after the last "body" has been added to the tree.  This function
must be called in every processor.  It generates all the necessary
interprocessor communication so that every processor "agrees" on the
contents of the upper levels of the tree.  Neither the topology of
the tree, nor its contents may be altered after this function is called.
The reason is that various pieces will be distributed and "cached" remotely
to avoid unnecessary re-communication.  Without the read-only assumption 
it would be difficult or impossible to efficiently access the contents
of the tree in parallel.

-------------------
TreeModify(tree_t *tp) / TreeFreeze(tree_t *tp)

UNIMPLEMENTED!: It's possible that a limited re-write ability would be
useful.  Between calls to TreeModify and TreeFreeze, one would be
allowed to alter the contents of the user-defined data in the tree.
The overall structure would not change (i.e., the number and
relationships of parents and children), but the data would be mutable.
In effect, TreeModify would flush all caches and TreeFreeze would
declare that it is again safe to cache data remotely.


--------------------