markh@csd4.milw.wisc.edu (Mark William Hopkins) (03/04/88)
This is an example of a structure that solves a long standing problem of
organising memory in an efficient manner to allow for quick multiple accessing.
The structure uses the Sort Tree, which is something that is easily represented
as a recursively defined data type. However, an additional subtilty complicates
the issue as far as data type recursion applies.
The underlying memory contains a set of records of type:
BasicData = RECORD
Key1 : <ORDINAL TYPE 1>;
Key2 : <ORDINAL TYPE 2>;
Data : ...
END;
The sort tree is a binary tree of Nodes:
SortTree = POINTER TO Node;
Node = RECORD
Center : BasicData;
Left,Right : SortTree
END;
So far, we have a structure that can be equally well represented through
data type recursion or through pointers. However, we come to the insight
that one could have only gotten by considering what pointers do.
A pointer is only a reference to the data it points to. It is not the data
itself. What this means is that two or more pointers can point to exactly
the same thing. THE CHANGES MADE TO THE DATA THROUGH ONE POINTER WILL APPLY
TO THE OTHER POINTER.
In particular, one can have two or more sort trees accessing the SAME under-
lying memory:
var Tree1, Tree2 : SortTree;
The first tree would order its nodes by Key1, and the second by Key2. Yet
both trees point to the SAME set of nodes. The procedure Insert will insert
the same node into both trees (using binary search), likewise Delete will
remove the node from both trees (again, using binary search).
What we gain is that we can access the same set of nodes through Key1 or Key2
using Tree1 or Tree2. This marks an ESSENTIAL use of pointers.