Java Reference
In-Depth Information
at the beginning of the program, and is never removed. The node class recognizes
from the pointer value that the flyweight is being accessed, and acts accordingly.
Note that when using the Flyweight design pattern, you cannot store coordi-
nates for the node in the node. This is an example of the concept of intrinsic versus
extrinsic state. Intrinsic state for an object is state information stored in the ob-
ject. If you stored the coordinates for a node in the node object, those coordinates
would be intrinsic state. Extrinsic state is state information about an object stored
elsewhere in the environment, such as in global variables or passed to the method.
If your recursive calls that process the tree pass in the coordinates for the current
node, then the coordinates will be extrinsic state. A flyweight can have in its intrin-
sic state only information that is accurate for all instances of the flyweight. Clearly
coordinates do not qualify, because each empty leaf node has its own location. So,
if you want to use a flyweight, you must pass in coordinates.
Another design choice is: Who controls the work, the node class or the tree
class? For example, on an insert operation, you could have the tree class control
the flow down the tree, looking at (querying) the nodes to see their type and reacting
accordingly. This is the approach used by the BST implementation in Section 5.4.
An alternate approach is to have the node class do the work. That is, you have an
insert method for the nodes. If the node is internal, it passes the city record to the
appropriate child (recursively). If the node is a flyweight, it replaces itself with a
new leaf node. If the node is a full node, it replaces itself with a subtree. This is
an example of the Composite design pattern, discussed in Section 5.3.1. Use of the
composite design would be difficult if
null
pointers are used to represent empty
leaf nodes. It turns out that the PR quadtree insert and delete methods are easier to
implement when using the composite design.
13.3.3
Other Point Data Structures
The differences between the k-d tree and the PR quadtree illustrate many of the
design choices encountered when creating spatial data structures. The k-d tree pro-
vides an object space decomposition of the region, while the PR quadtree provides
a key space decomposition (thus, it is a trie). The k-d tree stores records at all
nodes, while the PR quadtree stores records only at the leaf nodes. Finally, the two
trees have different structures. The k-d tree is a binary tree (and need not be full),
while the PR quadtree is a full tree with 2
d
branches (in the two-dimensional case,
2
2
= 4). Consider the extension of this concept to three dimensions. A k-d tree for
three dimensions would alternate the discriminator through the x, y, and z dimen-
sions. The three-dimensional equivalent of the PR quadtree would be a tree with
2
3
or eight branches. Such a tree is called an octree.
We can also devise a binary trie based on a key space decomposition in each
dimension, or a quadtree that uses the two-dimensional equivalent to an object
space decomposition. The bintree is a binary trie that uses keyspace decomposition
