Branch data Line data Source code
1 : : //-------------------------------------------------------------------------
2 : : // Filename : OctTreeCell.hpp
3 : : //
4 : : // Purpose : Oct-tree node used by OctTree
5 : : //
6 : : // Special Notes : OctTree handles all memory allocation for this
7 : : // class.
8 : : //
9 : : // Creator : Jason Kraftcheck
10 : : //
11 : : // Creation Date : 01/30/02
12 : : //-------------------------------------------------------------------------
13 : :
14 : : #ifndef OCT_TREE_CELL_HPP
15 : : #define OCT_TREE_CELL_HPP
16 : :
17 : : template <class X, class E> class OctTreeCell;
18 : : class CubitVector;
19 : : template <class X> class DLIList;
20 : :
21 : : // Linked-list node used to hold CubitNodes in each box.
22 : : template <class X, class E> struct OctTreeEntry
23 : : {
24 : : X* node;
25 : : OctTreeEntry<X,E>* next;
26 : : };
27 : :
28 : : // A node in the oct-tree.
29 : : template <class X, class E> class OctTreeCell
30 : : {
31 : : private:
32 : :
33 : : union {
34 : : OctTreeEntry<X,E>* head_; // head of linked-list of CubitNodes
35 : : OctTreeCell<X,E>* children_; // array of 8 child boxes
36 : : };
37 : : // union of both the head pointer for the linked-list
38 : : // of CubitNodes in a leaf node and a pointer to the
39 : : // array of child boxes.
40 : : //
41 : : // This node is a leaf node iff node_count_ is non-zero
42 : : // or both values in the data union are null.
43 : :
44 : : int node_count_;
45 : : // Number of nodes contained in a leaf node. If zero,
46 : : // need to check if data.children is null to determine
47 : : // if this is a leaf node.
48 : :
49 : : void add_nodes( OctTreeEntry<X,E>* node );
50 : : // Join the passed linked-list to the data list.
51 : : // asserts if not a leaf node.
52 : :
53 : : public:
54 : :
55 : : OctTreeCell( OctTreeEntry<X,E> array[], int size );
56 : : // create a root node
57 : : // calling code provides storage for linked-list
58 : : // nodes by providing 'array'. Do not delete
59 : : // 'array' until this OctTreeCell and all its
60 : : // children are destroyed.
61 : :
62 : 0 : inline OctTreeCell( ) : children_(0), node_count_(0) {}
63 : : // Construct unused child node. This is provieded
64 : : // for the cexternal memory allocator.
65 : :
66 [ # # ][ # # ]: 0 : bool leaf() const { return node_count_ || !children_; }
67 : : // Is this box a leaf in the tree?
68 : :
69 : : bool split( const CubitVector& my_center, OctTreeCell<X,E>* memory );
70 : : // Change from leaf box to non-leaf. Splits nodes amongst 8 new
71 : : // child boxes using the value of 'my_center'. May fail (return
72 : : // false) if two few nodes are contained for a split to be sensible.
73 : : //
74 : : // Calling application provides memory for use in holding child
75 : : // nodes. memory must be freed by the caller AFTER the destruction
76 : : // of this object.
77 : :
78 : : void append_nodes( DLIList<X*>& list );
79 : : // If this node is a leaf node, append all contained CubitNodes
80 : :
81 : : void append_all_nodes( DLIList<X*>& list );
82 : : // If this node is a leaf node, append all contained CubitNodes.
83 : : // Otherwise descend oct-tree getting CubitNodes contained in
84 : : // all child leaf nodes.
85 : :
86 : : enum {
87 : : X_MIN = 0,
88 : : Y_MIN = 0,
89 : : Z_MIN = 0,
90 : : X_MAX = 1,
91 : : Y_MAX = 2,
92 : : Z_MAX = 4
93 : : };
94 : : // Constants for selecting one of 8 child boxes.
95 : : // Can be either bitwise-or'ed (|) or added (+).
96 : : // MAX values take precedence over MIN values
97 : : // if both are specified. (MIN is just the
98 : : // absense of MAX).
99 : :
100 : : OctTreeCell<X,E>* child( int quadrant );
101 : : // quadrant should be a bitwise OR (or sum) of
102 : : // the constants above. If both a MIN and MAX
103 : : // value is specified for a given principal
104 : : // direction, the M : children_(0),
105 : :
106 : : void node_locations( CubitVector& box_min,
107 : : CubitVector& box_max,
108 : : CubitVector& average,
109 : : CubitVector* std_dev = 0 );
110 : : // Get information about CubitNodes contained in
111 : : // this box. Method does nothing when called on
112 : : // non-leaf boxes.
113 : :
114 : 0 : int node_count() { return node_count_; }
115 : : // CubitNodes contained in this box.
116 : : // Always zero for non-leaf boxes.
117 : :
118 : : };
119 : :
120 : : #include "OctTreeCell.cpp"
121 : :
122 : : #endif
123 : :
|
