Class ABinaryLeaf

Refers to the left subtree of the node.

Refers to the right subtree of the node.

Manages the number of occurrences of this node.

Stores the key used to sort the node.

Stores the index of the node

Construct a new node that uses the specified value as its sort key.

Construct a new node that uses the hash value of the specified string as its sort key.

Initializer

Destroy the node.

This method frees ABinaryLeaf.Occurrences and then calls the inherited routine.

Determine whether or not the specified sort key is contained within the node or one of its subtrees.

This method first checks to see whether thisKey matches the sort key of the current node; if so, it returns True immediately. Otherwise, the method performs a recursive search of either the left or right subtree of the node, depending upon whether the value of thisKey is greater than or less than the sort key of the current node.

The recursive nature of the search means that the entire tree is searched if this method is called on the root node of a binary tree.

Returns

True if thisKey is found within the node or one of its subtrees; False if not.

Determine whether or not a sort key with the same value as the hash value of thisKey is contained within the node or its subtrees.

This method takes the hash value of thisKey, as calculated by a call to Charstring.hashValueOf, and then calls the integer version of ABinaryLeaf.hasKey on Self.

Returns

True if a sort key that matches the hash value of thisKey is found within the node or one of its subtrees; False if not.

Retrieves a reference to the node that has the specified sort key.

This method first checks to see whether thisKey matches the sort key of the current node; if so, it returns Self. Otherwise, the method performs a recursive search of either the left or right subtree of the node, depending upon whether the value of thisKey is greater than or less than the sort key of the current node.

The recursive nature of the search means that the entire tree is searched if this method is called on the root node of a binary tree.

Returns

A reference to the node that contains the specified sort key, if found within the node or one of its subtrees; Nil otherwise.

Retrieves a reference to the node that has a sort key which matches the hash value of the specified string.

This method takes the hash value of thisKey, as calculated by a call to Charstring.hashValueOf, and then calls the integer version of ABinaryLeaf.fetch on Self.

Returns

A reference to the node that contains a sort key which matches the hash value of thisKey, if found within the node or one of its subtrees; Nil otherwise.

Inserts ThisLeaf into one of the subtrees of the current node.

This method compares the sort key of ThisLeaf with its own sort key. If the sort key of ThisLeaf is greater than the sort key of the current leaf, then ThisLeaf is inserted into the right subtree of the current node. If the sort key of ThisLeaf is less than the sort key of the current leaf, then ThisLeaf is inserted into the left subtree of the current node.

If thisKey matches the value of Self.sortKey and allowDuplicates is False, then this routine returns a reference to Self and NO INSERTION OCCURS.

If the values match and allowDuplicates is True, then this routine will insert a reference to ThisLeaf into its list of occurrences, constructing such a list if necessary. However, ThisLeaf is still not inserted into the tree structure, which means it cannot itself be directly found by searching the tree. An instance of ABinaryTree which has called this method as part of its own insertion method may insert ThisLeaf as part of its list structure, so that the node can still be found by a linear search of the list. Otherwise, the node can be found as one of the occurrences in the list returned by ABinaryLeaf.Occurrences.

If this method is called on the root node of a binary tree, it will ensure that the new leaf is inserted at the appropriate position within the tree.

Returns

A reference to ThisLeaf if the new node was successfully inserted. If a node already exists with the same sort key as ThisLeaf, then a reference to that node is returned. To determine whether the call successfully inserted ThisLeaf, the calling routine should check to see whether the return value of this function points to the same location as ThisLeaf.

Determine the insertion point of a node that has the specified sort key.

This method compares the sort key of the current node against thisKey. If the sort key of the current node is less than thisKey and ABinaryLeaf.RightTree is Nil when called on Self OR the sort key of the node referred to by the right subtree matches thisKey, then a pointer to that node is returned.

Similarly, if the sort key of the current node is greater than thisKey and ABinaryLeaf.LeftTree is Nil when called on Self OR the sort key of the node referred to by the left subtree matches thisKey, then a pointer to that node is returned.

Otherwise, the method is called recursively on either the left or right subtree until a match or Nil subtree reference is found. If this method is called on the only node in a tree, Nil will be returned.

The fact that a pointer to ABinaryLeaf is returned allows the caller to directly manipulate the point at which a node containing thisKey is inserted into the overall tree. This behavior is used by ABinaryTree.removeLeaf to unlink a given node from its position within the tree.

Determine the insertion point of a node that has a sort key which matches the hash value of thisKey.

This method takes the hash value of thisKey, as calculated by a call to Charstring.hashValueOf, and then calls the TSortKey implementation of ABinaryLeaf.insertionPointOf.

Detach the node from its associated tree.

This method does little more than nullify the references to the left and right subtrees of the node before calling the inherited routine. It is called by ABinaryTree.removeLeaf as part of the process involved in removing a specific node from the overall tree.

Construct a shallow copy of the other object.

This method overrides the behavior inherited from AnObject.shallowCopyFrom: it calls that method, then checks to see whether Other is an instance of ABinaryLeaf. If so, it copies the values of

• ABinaryLeaf.sortKey and

• ABinaryLeaf.index

from Other to Self, overwriting any values in Self.

Note that this method does NOT copy any sibling or child nodes and so cannot be used to create a full copy of any descendant of ANode. Likewise, it does NOT copy the left or right subtrees and so cannot be used to create a full copy of any descendant of ABinaryLeaf. The copy will NOT be automatically placed in the binary tree to which Other belongs, if any, but the caller is free to do so, so long as the node's sort key does not match one that already exists in the tree.

Calculate the number of bytes required to stream the node, and just the node.

This method overrides the behavior inherited from ANode.selfStreamingLength; it returns the number of bytes required to stream the sort key and index of the node.

Write the node, and just the node, to the specified stream. For more information on this routine, see ANode.writeSelfTo.

This method overrides the behavior inherited from ANode.writeTo; instead of writing the number of children of the node, it writes the sort key and index of the node. It is assumed that instances of ABinaryLeaf and its descendants will not have child nodes.

Returns

The total number of bytes written to Dest.

Read the node from the specified stream.

This method overrides the behavior inherited from ANode.readFrom; instead of attempting to read all children of the node, it simply reads the sort key and index of the node. It is assumed that instances of ABinaryLeaf and its descendants will have no child nodes.

Returns

The total number of bytes read from Source.

Construct and return a string representation of the node, suitable for printing to a text-based console or device.

In accordance with the criteria described by APrintingObject.toString, this method returns a string that contains the value of the node's sort key and its index. The format of the string returned is controlled by bnlfStringRepresentation.

Retrieve a reference to the first node in the left subtree which branches from this node.

As implemented within ABinaryLeaf, the left subtree contains all nodes with values that are LESS than that of Self, as determined by comparing their sort keys.

If there are no nodes in the left subtree, this routine will return Nil.

Retrieve a reference to the first node in the right subtree which branches from this node.

As implemented within ABinaryLeaf, the right subtree contains all nodes with values that are GREATER than that of Self, as determined by comparing their sort keys.

If there are no nodes in the right subtree, this routine will return Nil.

Retrieve a reference to the list of occurrences maintained by the node.

The list of occurrences is used in the event that an attempt is made to insert a node with the same sort key as the current key into a tree. The list maintains the number of occurrences of that sort key.

The first occurrence in the list will always refer to the current node.

Note that list is constructed the first time ABinaryLeaf.insert is called with allowDuplicates set to True. If such a call is never made, this routine will always return Nil.

The caller should NOT attempt to free the reference returned by this routine; that will be done when the node itself is freed.

Retrieve a reference to a specific occurrence of the node.

The node maintains a list of occurrences, which is used in the even that more than one node with the same sort key exists in the tree. In such cases, only the first node with that sort key will be found by searching the tree (unless a linear search is performed), and so that node is responsible for maintaining a list of references to all other nodes with the same sort key.

thisIndex should specify a value of zero (0) or more. If zero is specified, this method simply returns a reference to the node on which the method was called. If thisIndex is larger than the value of Occurrences.length, then this method will return Nil. Otherwise, a reference to the specified occurrence is returned.

The caller should NOT attempt to free the reference returned by this routine.

Retrieve the value of the sort key associated with this node. This is the value that is used in calls to ABinaryLeaf.insert and others, in order to determine where the node is placed in the tree to which it belongs.

Retrieve the present index of the node. This value represents the sequence in which the node was entered into its parent tree and may change if nodes are removed from the tree.

The primary purpose of this value is to use when serializing the parent tree to which the node belongs, usually for storage in a stream and later recall by an instance of AVector. One scenario where this behavior would be used is in the creation and storage of a symbol table.