class EXT_CLASS tBalTree : public zSerial
tBalTree is the abstract base class for balanced binary trees, and contains all of the actual tree-handling logic.
Before deriving a class from tBalTree, it is highly recommended that you read the Deriving Specialized Classes section.
Public Interface
tBalTree provides a default constructor, and a virtual destructor.
(public) int Balance(int force = 0);
The Balance() member performs a "manual" balance operation on the entire tree if necessary. The balance operation is considered necessary if the number of nodes to the left and right of the root differs by more than the maximum allowable imbalance (default 15 nodes, may be modified by SetAutoBalance() if desired). NOTE that it is possible for subtrees on the left and right side of the node to be highly imbalanced but for the root to appear balanced; matching localized imbalances like this are unusual but possible if autobalance has been disabled. If the force parameter is nonzero, the balance operation is performed regardless of the balance state of the root.
Calling the Balance() member is unnecessary if autobalance is enabled; it is provided for cases where autobalance has been disabled for a period of time during which items have been added to the tree.
(public) void DumpStatistics(void);
The DumpStatistics() member is operational only in debug builds; in release builds, it is a no-op.
Calling DumpStatistics() cause a number of TRACE statements to be issued which output statistics that can be used to verify that the application is behaving as expected. The statistics displayed are:
number of Set operations
number of Get operations
number of Balance operations (auto)
number of Balance operations (manual)
See DumpStructure() and ResetStatistics() for related information.
(public) void DumpStructure(void);
The DumpStructure() member causes the tree's structure to be output as TRACE statements. It is only operational in debug builds; in release builds it is a no-op.
The display begins with the rightmost node of the tree, and ends with its leftmost node. Each level of the tree is differentiated from others by indentation. Elements are identified by their key name; if the derived class implements onGetKeyName() its result is used; the default implementation of onGetKeyName() simply returns the ASCII value of the key pointer.
See DumpStatistics() and ResetStatistics() for related information.
(public) POSITION First(void);
The First() member returns a POSITION value that describes the first (leftmost, lowest valued) item in the tree. If the tree is empty, the result is zero.
The GetCount() member returns the number of items stored in the tree.
(public) POSITION GetItem(long item);
The GetItem() member allows the tree to be accessed as an array, by 0-based index. The item parameter specifies the item number, which is expected to be greater than or equal to zero, and less than the result of GetCount(). The result is a POSITION value that describes the indicated item; if an invalid index is passed, the result will be zero.
(public) long GetItemIndex(POSITION node);
The GetItemIndex() member returns the item-index of the specified element. The leftmost item of the tree (the item with the key having the lowest value) has a position number of zero.
The Last() member returns a POSITION value that describes the last (rightmost, highest valued) item in the tree. If the tree is empty, the result is zero.
(public virtual) int Load(istream* istrm);
The Load() member ensures that the tree is empty by calling RemoveAll(), then loads the tree from the serialized data in the istream passed as the istrm parameter. Autobalance is disabled during the Load() operation; when a serialized tree is loaded, it has exactly the same structure it had when it was serialized to the stream. When the Load() operation is complete, autobalance is restored to its previous state.
(public) POSITION Next(POSITION node);
The Next() member moves from the node passed to the item in the tree with the next higher key value. If the node value passed represents the last node in the tree, the result is zero.
(public) POSITION Prev(POSITION node);
The Prev() member moves from the node passed to the item in the tree with the next lower key value. If the node value passed represents the first node in the tree, the result is zero.
(public) void RemoveAll(void);
The RemoveAll() member empties the tree, including the deletion of any dynamically allocated data stored as either key or data values. It is important to note that derived classes must call the RemoveAll() member in their virtual destructor, because RemoveAll() relies on pure virtual members to perform deallocation; once the derived class destructor exits these virtuals are no longer available. Failure to call RemoveAll() in a derived class destructor can result in memory leaks or in some cases GPFs.
(public) void ResetStatistics(void);
The ResetStatistics() member resets (zeroes) the tree statistics that are displayed by the DumpStatistics() member. It is operational in debug builds only; in release builds it is a no-op.
(public) long SetAutoBalance(long maxImbalance);
The SetAutoBalance() member allows the programmer to control the level of imbalance that is tolerated before the tree is automatically rebalanced. The maxImbalance parameter specifies the number of nodes imbalance that is allowable without rebalancing. A value of 1 means that if a node is more than 1 item out of balance it will be rebalanced. To disable autobalance, supply a value of zero. It is important to note that autobalance occurs only when a node is added to or removed from the tree; simple accesses or data modification do not cause a rebalance.
(public virtual) int Store(ostream* ostrm);
The Store() member causes the current contents of the tree to be serialized to the output stream specified by the ostrm parameter. During a Store() operation, the onStore() virtual is called once for each node in the tree; the order in which nodes are processed is implementation dependant.
Protected Interface
(protected) enum relativeKeyValue
The relativeKeyValue enum defines the result values from the onCompareKeys() virtual. The enum contains 4 values, the fourth of which is intended for use internally (ie, onCompareKeys() should not return it). These values are:
less
equal
greater
undefined
The StrmHdr typedef defines the structure that the tBalTree::Store() member uses during serialization. For details refer to the Store() and Load() member source code. The structure contains two members as follows:
long segLength; // total length of data segment incl hdr
long segBufReqd; // size to hold largest data item in segment
This member is used to determine the largest buffer-size that is needed in order to serialize the tree from a standard stream. It is initialized to 0 at the start of the Store() member, which then calls the storeTree() helper, which in turn calls the onStore() virtual once for each node in the tree. It is expected that derived class onStore() members will update the m_bufSize variable each time data is stored that is larger than the current value of m_bufSize. At the end of Store() processing, the contents of m_bufSize is stored in the StrmHdr.segBufReqd variable and the stream header is updated.
The m_dataBuf member points to space allocated at the start of a Load() operation for use by derived class onLoad() virtuals in serializing from a standard stream. The amount of space allocated is determined by the m_bufSize variable which is obtained from the stream header value StrmHdr.segBufReqd at the start of the Load() operation.
The m_keyBuf member points to space allocated at the start of a Load() operation for use by derived class onLoad() virtuals in serializing from a standard stream. The amount of space allocated is determined by the m_bufSize variable which is obtained from the stream header value StrmHdr.segBufReqd at the start of the Load() operation.
(protected) POSITION find(void* key);
The find() member searches the tree for a node with a matching key. The void* key pointer is passed to the virtual onCompareKeys() during the search to determine the relative key values.
(protected) void* getData(POSITION node);
The getData() member returns the data pointer of the specified node. If the POSITION value passed is zero, the result is zero.
(protected) void* getKey(POSITION node);
The getKey() member returns the key pointer of the specified node. If the POSITION value passed is zero, the result is zero.
(protected virtual) relativeKeyValue onCompareKeys(void* key1, void* key2) = 0;
The onCompareKeys() virtual performs the key comparison necessary to search the tree or insert a new element into the tree. It returns a relativeKeyValue and should never return undefined or searches will malfunction.
All classes directly derived from tBalTree must implement this pure virtual.
(protected virtual) void onDeleteData(void*& dataPtr) = 0;
The onDeleteData() virtual is passed a reference to a void pointer. Its function is to delete any dynamically allocated data associated with this void pointer. It need not zero the pointer after deleting any dynamically allocated data associated with the pointer. Note that tBalTree does not define whether this void* is used by derived classes as a pointer to dynamically allocated or other data, or whether it is used to store the data itself. For example, derived classes whose data values are unsigned long may store the data value in the void pointer rather than performing any allocation/deallocation.
All classes directly derived from tBalTree must implement this pure virtual.
(protected virtual) void onDeleteKey(void*& keyPtr) = 0;
The onDeleteKey() virtual is passed a reference to a void pointer. Its function is to delete any dynamically allocated data associated with this void pointer. It need not zero the pointer after deleting any dynamically allocated data associated with the pointer. Note that tBalTree does not define whether this void* is used by derived classes as a pointer to dynamically allocated or other key data, or whether it is used to store the key data itself. For example, derived classes whose key values are unsigned long may store the key value in the void pointer rather than performing any allocation/deallocation.
All classes directly derived from tBalTree must implement this pure virtual.
(protected virtual) const char* onGetKeyName(void* keyPtr);
The onGetKeyName() virtual returns a pointer to a buffer which contains the ASCII name of the key. This buffer may be static or it may be member data of a derived class. If this virtual is not overridden in a derived class the result will be the value returned by the tBalTree class implementation, which is the ASCII representation of the void* contents in hexadecimal.
(protected virtual) int onLoad(void* where);
The onLoad() virtual is called by tBalTree during the processing of the Load() member. The onLoad() virtual should obtain one key,data pairing from the input source specified by the where parameter and use set() to add the new element to the tree. The Load() member continues to call the onLoad() virtual until the stream's get-pointer indicates that the stream segment occupied by serialized tree data has been completely processed.
As called by tBalTree, the void* can always be cast to an istream*. Derived classes may pass other types cast to a void*.
You should examine the implementation of Load() before overriding this member. Examining the implementation of derived classes provided in this product is also recommended.
The result from onLoad() is nonzero if successful, otherwise zero.
(protected virtual) int onSetData(void*& dataPtr, void* data) = 0;
The onSetData() virtual is passed a reference to a void pointer which is the node's data-pointer, and a void* which refers to the actual data. The derived class determines whether the data value itself is stored in the dataPtr, or whether some dynamically allocated data is constructed using the data pointer, and its address is stored in the dataPtr variable. For example, a class whose data is unsigned long would probably pass the data itself as the data parameter, and store it directly in the dataPtr variable; on the other hand, a class whose data is a string would probably use strdup() or equivalent to make a copy of the string pointed to by the data parameter and then store its address in the dataPtr variable.
All classes directly derived from tBalTree must implement this pure virtual.
The result is nonzero if successful, otherwise zero (for example on storage allocation failure)
(protected virtual) int onSetKey(void*& keyPtr, void* key) = 0;
The onSetKey() virtual is passed a reference to a void pointer which is the node's key-pointer, and a void* which refers to the actual key. The derived class determines whether the key value itself is stored in the keyPtr, or whether some dynamically allocated data is constructed using the key pointer, and its address is stored in the keyPtr variable. For example, a class whose key is unsigned long would probably pass the key itself as the key parameter, and store it directly in the keyPtr variable; on the other hand, a class whose key is a string would probably use strdup() or equivalent to make a copy of the string pointed to by the key parameter and then store its address in the keyPtr variable.
All classes directly derived from tBalTree must implement this pure virtual.
The result is nonzero if successful, otherwise zero (for example on storage allocation failure)
(protected virtual) int onStore(void* where, POSITION node);
The onStore() virtual is called by the storeTree() helper during the execution of the Store() member function. It is called once for each node in the tree, and should write the key,data pairing for the node specified to the medium indicated by the where parameter. The order in which individual nodes are passed to onStore() is implementation dependent.
If the storeTree() helper is called by the Store() member, the void* passed as where can always be cast to an ostream*.
Derived classes may cause onStore() to be called by calling the storeTree() helper and passing it something other than an ostream*. For example, the MFC-oriented classes included in this product call storeTree() from within their Serialize() member and pass a CArchive* instead of an ostream* in that case. Since most of the MFC-oriented classes support serialization to both streams and CArchive objects, the type of data actually passed as the where argument is highly dependent on the class implementation. Examining the implementation of Serialize() in the MFC-oriented classes is highly recommended prior to implementing a derived class.
The result is nonzero if successful, otherwise zero.
(protected) void remove(POSITION& node);
The remove() member removes a single item from the tree, as indicated by the node parameter. An automatic balance operation may occur if the tree is taken sufficiently out of balance by the removal of the specified node. The node parameter (which is a reference) is set to zero before control returns to the caller.
(protected) int set(void* key, void* data);
The set() member sets the node identified by the key parameter to the specified data value.
The onSetData() and onSetKey() virtuals are called by this member. If the node's data pointer is nonzero, the onDeleteData() member is called prior to calling the onSetData() member.
The result is nonzero if the operation succeeds, otherwise zero. The only failure cause is storage allocation failure.
(protected) int setData(POSITION node, void* data);
The setData() member modifies the data value of the node whose POSITION is passed. If the node's data pointer is nonzero the onDeleteData() member is called; then the onSetData() member is called.
The result is nonzero if the operation succeeds, otherwise zero. The only failure cause is storage allocation failure.
(protected) int storeTree(void* where);
The storeTree() member is a helper function provided for serialization of the tree to a storage medium. The storeTree() member traverses the entire tree, and calls the onStore() virtual once for each node encountered. The order in which nodes are processed is implementation dependant. The value passed as the where argument is propagated to the onStore() member each time it is called. The operation completes when all nodes of the tree have been processed, or when the onStore() member returns zero to indicate a failure.
The result is nonzero if successful, otherwise zero.