causerie

Introduction

Units

Class Hierarchy

Classes, Interfaces, Objects and Records

Types

Variables

Constants

Functions and Procedures

Identifiers

Classes hierarchy graph

Class ABinaryTree

DescriptionHierarchyFieldsMethodsProperties

Unit

classwork

Declaration

type ABinaryTree = class(ABinaryLeaf, CanIterate)

Description

This class represents a basic binary tree which contains nodes that are sorted by an integer key. The tree can manage ABinaryLeaf and its descendants. Binary trees are declared as instances of ABinaryLeaf so that they can be themselves entered into binary trees and managed as lists of binary trees.

To allow for iteration, instances of ABinaryTree maintain both a tree structure and a simple list structure. The tree structure is used to search for nodes with a specific sort key; the list structure is used to iterate through nodes sequentially. ABinaryTree.Root refers to the both the base of the tree structure and the first node in the list structure. ABinaryTree.YoungestNode refers to the last node in the list structure.

Since ABinaryTree serves as the basis for a variety of tree-like structures, instances of ABinaryTree are designed to be as flexible as possible and can manage any descendant of ABinaryLeaf. ABinaryTree.LeafType indicates the class of node managed by the tree.

By default, binary trees do not allow duplicate entries; this behavior can be changed by calling ABinaryTree.setDuplicateEntriesAllowed.

Hierarchy

Overview

Fields

Protected MyLeafType: ANodeClass;
Protected MyRoot: ABinaryLeaf;
Protected myDuplicateEntriesAllowed: boolean;

Methods

Public function init: boolean; override;
Public function FetchLeaf(const thisKey: TSortKey): ABinaryLeaf; virtual;
Public function FetchLeaf(const thisKey: string): ABinaryLeaf; virtual;
Public function LeafAtIndex(thisindex: TNodeRelativeIndex): ABinaryLeaf; virtual;
Public function hasLeafWithKey(const thisKey: TSortKey): boolean; virtual;
Public function hasLeafWithKey(const thisKey: string): boolean; virtual;
Public function InsertLeaf(const Leaf: ABinaryLeaf): ABinaryLeaf; virtual;
Public function addLeaf(const Leaf: ABinaryLeaf; const freeOnFailure: boolean = true): boolean; virtual;
Public function RemoveLeaf(const thisKey: TSortKey; const updateIndices: boolean = true): ABinaryLeaf; virtual;
Public function RemoveLeaf(const thisKey: string; const updateIndices: boolean = true): ABinaryLeaf; virtual;
Public function deleteLeaf(const thisKey: TSortKey; const updateIndices: boolean = true): boolean; virtual;
Public function deleteLeaf(const thisKey: string; const updateIndices: boolean = true): boolean; virtual;
Public procedure reindex; virtual;
Public function shallowCopyFrom(const Other: AnObject): boolean; override;
Public function selfStreamingLength: TStreamIOSize; override;
Public function writeSelfTo(const Dest: AStream): TStreamIOSize; override;
Public function printSelfTo(const Dest: ATextOutputStream; prefix: AnsiString = ''; suffix: AnsiString = ''): TStreamIOSize; override;
Public function readFrom(const Source: AStream): TStreamIOSize; override;
Public function toString: AnsiString; override;
Public function printTo(const Dest: ATextOutputStream; prefix: AnsiString = ''; suffix: AnsiString = ''): TStreamIOSize; override;
Public function Iterator: AnIterator; virtual;
Public function LeafType: ANodeClass; virtual;
Public function Root: ABinaryLeaf; virtual;
Public function YoungestNode: ABinaryLeaf; virtual;
Public function duplicateEntriesAllowed: boolean; virtual;
Public function setDuplicateEntriesAllowed(const flag: boolean): boolean; virtual;

Description

Fields

Protected MyLeafType: ANodeClass;

Indicates the type of binary leaf managed by the tree

Protected MyRoot: ABinaryLeaf;

Refers to the oldest node in the tree

Protected myDuplicateEntriesAllowed: boolean;

Indicates whether or not the tree allows duplicate entries

Methods

Public function init: boolean; override;

Initializer

Public function FetchLeaf(const thisKey: TSortKey): ABinaryLeaf; virtual;

Searches the root node and its subtrees for the leaf which has the sort key that matches the one specified by thisKey.

This method operates only on the current tree. It simply calls ABinaryLeaf.fetch on its root node and returns the result.

Returns

A reference to the node with the sort key that matches thisKey, if found; Nil otherwise. This routine will also return Nil if the tree has no nodes.

Public function FetchLeaf(const thisKey: string): ABinaryLeaf; virtual;

Searches the root node and its subtrees for the leaf which has a sort key that matches the hash value of thisKey.

This method operates only on the current tree. It simply calls ABinaryLeaf.fetch on its root node and returns the result.

Returns

A reference to the node with the sort key that has a sort key which matches the hash value of thisKey, if found; Nil otherwise. This method will also return Nil if the tree has no nodes.

Public function LeafAtIndex(thisindex: TNodeRelativeIndex): ABinaryLeaf; virtual;

Retrieves the node at the specified index.

Unlike instances of ALinkedList, index must be an absolute offset – that is, an offset relative to the root node of the tree. The root node will always be at index zero (0). If index specifies a value that is greater than or equal to ABinaryTree.census, then the last node in the tree is returned.

This method searches sequentially through the nodes in the tree and so may be inefficient for large trees.

.

Returns

A reference to the node with the specified index, if found; Nil otherwise

Public function hasLeafWithKey(const thisKey: TSortKey): boolean; virtual;

Determine whether or not the root node or its subtrees contain a node with a sort key that matches thisKey.

This method operates only on the current tree. It simply calls ABinaryLeaf.hasKey on its root node and returns the result.

Returns

True if a node is found that has a sort key which matches the value of thisKey; False if not. This method will also return False if the tree is empty.

Public function hasLeafWithKey(const thisKey: string): boolean; virtual;

Determine whether or not the root node or its subtrees contain a node with a sort key that matches the hash value of thisKey.

This method operates only on the current tree. It simply calls ABinaryLeaf.hasKey on its root node and returns the result.

Returns

True if a node is found that has a sort key which matches the hash value of thisKey; False if not. This method will also return False if the tree is empty.

Public function InsertLeaf(const Leaf: ABinaryLeaf): ABinaryLeaf; virtual;

Inserts Leaf into the tree, provided that a node with the sort key specified by Leaf does not already exist therein.

This method simply calls ABinaryLeaf.insert on the root node of the tree and returns the result. If the tree does not yet have a root node, then Leaf becomes the root node.

To determine whether the insertion was successful, the caller can compare the reference returned by this routine with that of Leaf itself; if the two match, then the insertion was successful; if not, then it failed. For example: 


        var
          MyNode: ABinaryLeaf;

        begin
          // Construct the node
          MyNode := ABinaryLeaf.withKey(42);

          // We assume that 'MyTree' has already been constructed somewhere
          if MyTree.insertLeaf(MyNode) = MyNode then
          begin
            // Insertion succeeded
          end

          else begin
            // Insertion failed, most likely because '42' is already in the tree
            MyNode.free;
          end;

Alternatively, you can call ABinaryTree.addLeaf, which will return True or False to indicate whether the new node was successfully inserted.

If the insertion succeeded, the tree assumes control of the node and the caller should not attempt to free it, as this will cause the program to crash when the tree is freed.

Returns

A reference to Leaf, if the insertion succeeded. If a node with the same sort key as Leaf already exists in the tree, then a reference to that node is returned.

Public function addLeaf(const Leaf: ABinaryLeaf; const freeOnFailure: boolean = true): boolean; virtual;

Add a new node to the tree, provided that a node with sort key specified by Leaf does not already exist in the tree.

This method simply calls ABinaryTree.insertLeaf to insert Leaf into the tree. It then checks to see whether the return value of that call matches Leaf; if so, the new node was inserted successfully. Otherwise, the insertion failed.

If freeOnFailure is True, then the new node will be destroyed by this routine if the insertion fails. This behavior is designed to allow this method to be called with a node constructor as the leaf to be inserted: 

          if MyTree.addLeaf(ABinaryLeaf.withKey(42), true) then ...

Returns

True if Leaf was successfully inserted into the tree; False if not.

Public function RemoveLeaf(const thisKey: TSortKey; const updateIndices: boolean = true): ABinaryLeaf; virtual;

Removes, but does not free, the node with the specified key from the tree.

This method searches the root node and its subtrees for a node with a sort key that matches thisKey; if the node is found, it is detached from its subtrees and returned. The subtrees are reinserted into the tree.

Use this method with care! Because ABinaryTree relies on the current value of ABinaryTree.census to determine the index of new nodes that are inserted into the tree, removing and then adding nodes could result in nodes with duplicate indices in the same tree. If you rely on indices being constant and unique, you should ensure that updateIndices is True, so that ABinaryTree.reindex is called after the node is deleted.

Returns

A reference to the node with a sort key that matches the one specified, if found; Nil otherwise. If the node is found, the caller is given responsibility for freeing it, as it will no longer be part of the tree.

Public function RemoveLeaf(const thisKey: string; const updateIndices: boolean = true): ABinaryLeaf; virtual;

Removes from the tree, but does not free, the node with a key that matches the hash value of thisKey.

This method searches the root node and its subtrees for a node with a sort key that matches the hash value of thisKey; if the node is found, it is detached from its subtrees and returned. The subtrees are reinserted into the tree.

Use this method with care! Because ABinaryTree relies on the current value of ABinaryTree.census to determine the index of new nodes that are inserted into the tree, removing and then adding nodes could result in nodes with duplicate indices in the same tree. If you rely on indices being constant and unique, you should ensure that updateIndices is True, so that ABinaryTree.reindex is called after the node is deleted.

Returns

A reference to the node with a sort key that matches the one specified, if found; Nil otherwise. If the node is found, the caller is given responsibility for freeing it, as it will no longer be part of the tree.

Public function deleteLeaf(const thisKey: TSortKey; const updateIndices: boolean = true): boolean; virtual;

Deletes the node with the specified key from the tree.

This method calls ABinaryTree.removeLeaf to find the node that has thisKey. If it is found, then the node is freed.

Use this method with care! Because ABinaryTree relies on the current value of ABinaryTree.census to determine the index of new nodes that are inserted into the tree, removing and then adding nodes could result in nodes with duplicate indices in the same tree. If you rely on indices being constant and unique, you should call ensure that updateIndices is True, so that ABinaryTree.reindex is called after the node is deleted.

Returns

True if the node was found and freed; False otherwise.

Public function deleteLeaf(const thisKey: string; const updateIndices: boolean = true): boolean; virtual;

Deletes the node with a key that matches the hash value of thisKey.

This method calls ABinaryTree.removeLeaf to find the node that has a hash value which matches thisKey. If it is found, then the node is freed.

Use this method with care! Because ABinaryTree relies on the current value of ABinaryTree.census to determine the index of new nodes that are inserted into the tree, removing and then adding nodes could result in nodes with duplicate indices in the same tree. If you rely on indices being constant and unique, you should ensure that updateIndices is True, so that ABinaryTree.reindex is called after the node is deleted.

Returns

True if the node was found and freed; False otherwise.

Public procedure reindex; virtual;

Reindex the tree.

This method loops through each leaf in the tree, beginning with the root node, and assigns it an index starting from zero (0). When the loop completes, the value of ANode.census as applied to the tree is updated to contain the most current count of the nodes in the tree.

You will only need to call this method if you have removed nodes from the tree, but you expect each node index to be unique. Because instances of ABinaryTree rely on the current value of ANode.census when assigning indices to new nodes, it is possible that a new node inserted into the tree, after one has been removed, will have the same index as another node in the tree. This method will resolve such a scenario; however, since it proceeds sequentially through the tree, it can be inefficient for very large trees.

Public function shallowCopyFrom(const Other: AnObject): boolean; override;

Construct a shallow copy of the other item.

This method overrides the behavior inherited from AnObject.shallowCopyFrom: it calls that method, then checks to see whether Other is an instance of ABinaryTree. If so, it constructs a copy of the other tree by calling ABinaryLeaf.shallowCopyFrom on each node. The copied nodes are then inserted into the tree.

Note that the behavior of this method allows a copy of a tree to be added to an existing tree, so long as the nodes to be copied do not have sort keys that are identical to those in the existing tree.

Public function selfStreamingLength: TStreamIOSize; override;

Calculate the number of bytes required to stream the tree and its nodes.

This method overrides the behavior inherited from ABinaryLeaf. It calls ABinaryLeaf.selfStreamingLength on its root node, which causes all nodes in the tree to calculate their streaming sizes. It then adds the number of bytes required to stream the total number of nodes in the tree and returns this result.

Public function writeSelfTo(const Dest: AStream): TStreamIOSize; override;

Write the tree and its nodes to the specified stream.

This method overrides the behavior inherited from ABinaryLeaf. It first writes the number of nodes in the tree, then calls ABinaryLeaf.writeTo on its root node, which causes all nodes in the tree to be written to the stream.

Returns

The total number of bytes written to Dest.

Public function printSelfTo(const Dest: ATextOutputStream; prefix: AnsiString = ''; suffix: AnsiString = ''): TStreamIOSize; override;

Print the tree and its nodes to the specified stream.

This method overrides the behavior inherited from ANode. It first writes a string representation of itself, as obtained by calling ABinaryTree.toString, then writes the value of suffix. After that, it calls ABinaryLeaf.printTo on its root node, which causes all other nodes in the tree to be printed.

Returns

The total number of bytes printed to Dest.

Public function readFrom(const Source: AStream): TStreamIOSize; override;

Reads the tree and its nodes from the specified stream.

This method overrides the behavior inherited from ABinaryLeaf. It first reads the number of nodes from the stream, then iterates through a loop which constructs a new instance of ABinaryTree.LeafType for each node, before calling ABinaryLeaf.readFrom on that instance and inserting the result into the tree.

Returns

The total number of bytes read from Source.

Public function toString: AnsiString; override;

Constructs and returns a string representation of the tree, suitable for printing to a display or text-based device.

The representation returned will contain the name of the class and the number of nodes presently in the tree. This representation is controlled by bntrStringRepresentationSingular and bntrStringRepresentationPlural, depending on the number of nodes presently in the tree.

Public function printTo(const Dest: ATextOutputStream; prefix: AnsiString = ''; suffix: AnsiString = ''): TStreamIOSize; override;

Prints a string representation of the tree and its nodes to the specified stream.

This method overrides the behavior inherited from ANode: it first calls ABinaryTree.printTo on its left subtree, if any; then prints the string representation returned by a call to ABinaryTree.toString and calls ABinaryLeaf.printTo on its root node to recursively print a representation of every node in the tree. Finally, it calls ABinaryTree.printTo on its right subtree, if any.

prefix is not used by this routine, but it is passed to the root node and can be used there to specify a delimiter for each node that is printed. If prefix is not specified, then this routine passes bntrDefaultNodePrintingPrefix to the root node.

If suffix is not otherwise specified, this routine uses the value of bntrDefaultPrintingSuffix as its own suffix and passes the value of bntrDefaultNodePrintingSuffix to the root node.

Returns

The total number of bytes printed to Dest.

Public function Iterator: AnIterator; virtual;

Constructs and returns an iterator that is suitable for iterating through the nodes in the tree.

For more information on this routine, see CanIterate.iterator.

As implemented in ABinaryTree, this method returns an instance of ABinaryTreeIterator. Descendant classes may override this method to return a different class instance instead.

Public function LeafType: ANodeClass; virtual;

Retrieve the the type of node that is managed by the tree. This will be a reference to ABinaryLeaf or one of its descendants.

Public function Root: ABinaryLeaf; virtual;

Retrieve a reference to the root node of the tree. This is the node that was first inserted into the tree.

The reference returned by this method should NOT be freed by the caller.

If the tree has no nodes, this routine will return Nil.

Public function YoungestNode: ABinaryLeaf; virtual;

Retrieve a reference to the youngest node in the tree. This is the node that was most recently added to the tree.

The reference returned by this method should NOT be freed by the caller.

If the tree has no nodes, this routine will return Nil.

Public function duplicateEntriesAllowed: boolean; virtual;

Retrieve whether or not the tree allows duplicate entries: that is, nodes that have the same sort key.

By default, instances of ABinaryTree do not allow duplicate entries, but this behavior can be changed by calling ABinaryTree.setDuplicateEntriesAllowed.

If duplicate entries are not allowed, attempts to call ABinaryTree.InsertLeaf with a node that has a sort key that matches one already present in the tree will fail.

Public function setDuplicateEntriesAllowed(const flag: boolean): boolean; virtual;

Set whether or not the tree allows duplicate entries: that is, whether it allows nodes that have the same sort key.

By default, instances of ABinaryTree do not allow duplicate entries, but by calling this method with a value of True, duplicate entries will be allowed when calling ABinaryTree.InsertLeaf.

Returns

The previous value of ABinaryTree.duplicateEntriesAllowed.

Generated by PasDoc 0.13.0 on 2015-01-10 17:13:18