Tree Utilities Library 1.0.0

Delphi 6, 7 and Kylix Implementation

by Dieter Köhler

Introduction

The Tree Utilities Library contains general classes to build a hierarchical list of items, a so-called object tree. The original Delphi VCL classes TTreeNodes and TTreeNode were often too specific for my tasks. When I realized that I was repeatedly implementing special purpose trees which more or less do the same job, it was time to look for a more general approach and to implement basic tree-structure classes, which make it easy to derive new specialized ones. The result of this project is the Tree Utilities Library. The latest version of this software is available at <http://www.philo.de/xml/>.

Using the unit

The Tree Utilities Library does not contain any components to be registered. So using it from inside your own projects is very simple: Add "TreeUtils" to the uses clause of your unit and make sure that the path to the location of the TreeUtils.pas file is included in Delphi's list of library paths. To include it go to the Library section of Delphi's Environment Options dialog (see the menu item: "Tools/Environment Options ...").

Exceptions

All exceptions raised inside the TreeUtils Library are derived from Delphi's EListError exception.

• EHierarchyRequestError = class(EListError);
• ENoModificationAllowedError = class(EListError);
• ENotAssignedError = class(EListError);
• ENotFoundError = class(EListError);
• EWrongOwnerError = class(EListError);

Defined Resourcestrings

These strings are used for the error messages of the corresponding exceptions.

• SHierarchyRequestError = 'Hierarchy Request Error';
• SNoModificationAllowedError = 'No Modification Allowed Error';
• SNotAssignedError = 'Parameter Node Not Assigned Error';
• SNotFoundError = 'Node Not Found Error.';
• SWrongOwnerError = 'Wrong Owner Error';

TCustomOwnedObject = class(TPersistent)

TCustomOwnedObject is a simple extension of the TPersistent class for maintaining a set of owned objects. The owner of a newly created TCustomOwnedObject object (if any) is specified in the new object's constructor and is then automatically added to the specified TCustomOwnedObject object's list of owned objects. When a TCustomOwnedObject object is freed, all of its owned objects are (recursively) freed too and it is automatically removed from is owner object's list of owned objects. It is also possible to specify nil as the owner parameter of a node's constructor. In this case the node has no owner node and the application is responsibly of correctly freeing it.

Do not create instances of TCustomOwnedObject. Instead use it to define your own descendant classes. Most of the properties and methods defined in TCustomOwnedObject are protected so that you can choose whether to hide or publish them in your own classes.

Protected Properties

OwnedObject[Index: Integer]: TCustomOwnedObject (readonly)

Lists all owned object. The first item has an index of 0, the second an index of 1, and so on.

OwnedObjectsCount: Integer (readonly)

The number of owned objects.

Public Methods

constructor Create(const AOwner: TCustomOwnedObject);

Constructs and initializes an instance of TCustomOwnedObject. If an owner node was specified, the new object is added to the specified owner's list of owned objects.

Parameters:

• AOwner
  The object that owns the new instance of TCustomOwnedObject or nil if the new instance has no owner.

destructor Destroy; override;

Destroys an instance of TCustomOwnedObject and removes it from its owner's list of owned objects. Do not call Destroy directly in an application. Instead, call Free. Free verifies that the TCustomOwnedObject reference is not nil, and only then calls Destroy.

Protected Methods

procedure Adopt(const Obj: TCustomOwnedObject); virtual;

Adopts an owned object from another owned object to this owned object, i.e. it changes the owner of the specified owned object.

Parameters:

• Obj
  The owned object to adopt.

procedure Clear; virtual;

This procedure (recursively) frees all owned objects and removes them from the list of owned objects.

function GetOwner: TPersistent; override;

This function returns the owner of the given object. If the given node has no owner, nil is returned.

Return Value:

• The owner of the given object or nil if the given object has no owner.

TCustomOwnedNode = class(TCustomOwnedObject)

TCustomOwnedNode represents a single node in a tree structure which also maintains a list of sub-nodes. Do not create instances of TCustomOwnedNode. Instead use it to define your own descendant classes. Most of the properties and methods defined in TCustomOwnedNode are protected so that you can choose whether to hide or publish them in your own classes.

The design principle behind the memory management of TCustomOwnedNode is to distinguish between owned nodes and child nodes. Each node can be associated with an owner node in its constructor and contains an ordered list of a (virtually) infinite number of direct child nodes. Each node can only be the child of at most one other node. If a node is the direct child of another node the other node is called "the parent node" of the given node. All direct or indirect parent nodes of a given node are called "its ancestors". This list of child nodes is maintained by the Append(), Insert(), and Remove() methods of the given nodes. Each child node must either have the same owner node as its parent node or the parent node must be identical with the owner node, and an attempt to add a node directly or indirectly as a child node is forbidden.

Each node contains a readonly list of owned nodes which is automatically updated when a node is created with the given node as its owner or if an owned node is freed. When a node is freed, it is removed from its parent node (no matter whether the parent node is readonly or not) and all its child nodes and owned nodes are recursively freed, too. Calling the Clear method of a node recursively frees all of its child nodes (but not the given node itself). It is also possible to specify nil as the owner parameter of a node's constructor. In this case the node has no owner node and the application is responsibly of correctly freeing it.

Protected Properties

Count: Integer (readonly)

Indicates the number of nodes maintained by the given node.

FirstChild: TCustomOwnedNode (readonly)

The first node maintained by the given node or nil if there is no such node.

Item[Index: Integer]: TCustomOwnedNode (readonly) (default)

Lists all nodes maintained by the given node. The first node has an index of 0, the second an index of 1, and so on. Item is the default property for TCustomOwnedNode. So the name of the Item property can be omitted when indexing into the set of nodes.

Items: TList (readonly)

Provides access to the list of nodes maintained by the given node.

LastChild: TCustomOwnedNode (readonly)

The last node maintained by the given node or nil if there is no such node.

NextSibling: TCustomOwnedNode (readonly)

The node immediately following the given node. If there is no such node, nil is returned.

OwnedObject[Index: Integer]: TCustomOwnedObject (readonly) (inherited from TCustomOwnedObject)

Lists all owned object. The first item has an index of 0, the second an index of 1, and so on.

OwnedObjectsCount: Integer (readonly) (inherited from TCustomOwnedObject)

The number of owned objects.

Parent: TCustomOwnedNode (readonly)

The parent of the given node or nil if the given node has no parent.

PreviousSibling: TCustomOwnedNode (readonly)

The node immediately preceding the given node. If there is no such node, nil is returned.

ReadOnly: Boolean

Determines whether the given node is readonly. If the node is readonly any attempt to modify the list of child nodes raises an exception.

Public Methods

constructor Create(const AOwner: TCustomOwnedNode);

Constructs and initializes an instance of TCustomOwnedNode. If an owner node was specified, Create internally calls the AttachNode() procedure of the specified owner node. During creation the Initializing property of the given node is 'true'.

Parameters:

• AOwner
  The node that owns the new node or nil if the new node has no owner.

destructor Destroy; override;

Destroys an instance of TCustomOwnedNode. Before a node is destroyed it is removed from its parent node, then it is cleared, and finally the DetachNode() procedure its owner node (if any) is called. Do not call Destroy directly in an application. Instead, call Free. Free verifies that the TCustomOwnedNode reference is not nil, and only then calls Destroy.

Protected Methods

procedure Adopt(const Node: TCustomOwnedNode); reintroduce; virtual;

Adopts a node from another owned object to this node, i.e. it changes the owner of the specified node and all of its children to this node. If the source node has a parent it is first removed from the child list of its parent.

Parameters:

• Node
  The node to adopt.

Exceptions:

• ENotAssignedError
  Raised via the RaiseException() method if Node is nil.

function Append(const NewChild: TCustomOwnedNode): TCustomOwnedNode; virtual;

Appends a child node to the end of the list of children for this node. If the new child is already in the tree, it is first removed.

Parameters:

• NewChild
  The node to append.

Return Value:

• The node appended.

Exceptions:

• ENotAssignedError
  Raised if NewChild is nil.
• EWrongOwnerError
  Raised if the given node is neither the owner of NewChild nor has the same owner than NewChild.
• EHierarchyRequestError
  Raised if NewChild is one of the given node's ancestors or the given node itself.
• ENoModificationAllowedError
  Raised if the given node is readonly or if the previous parent of the node being appended is readonly.

procedure CheckAssigned(const Node: TCustomOwnedNode);

This procedure is called by other methods of TCustomOwnedNode to check whether the specified node is assigned.

Parameters:

• Node
  The node to check.

Exceptions:

• ENotAssignedError
  Raised via the RaiseException() method if Node is nil.

procedure CheckDissimilarity(const Node_1, Node_2: TCustomOwnedNode);

This procedure is called by other methods of TCustomOwnedNode to check whether the specified nodes are different.

Parameters:

• Node_1
  The first node to check.
• Node_2
  The second node to check.

Exceptions:

• EHierarchyRequestError
  Raised via the RaiseException() method if Node_1 is the same object as Node_2.

procedure CheckHasChild(const Node: TCustomOwnedNode);

This procedure is called by other methods of TCustomOwnedNode to check whether the specified node is a child of the given node.

Parameters:

• Node
  The child node to check.

Exceptions:

• ENotFoundError
  Raised via the RaiseException() method if the specified node is not a child of the given node.

procedure CheckNotAncestorOrSelf(const Node: TCustomOwnedNode);

This procedure is called by other methods of TCustomOwnedNode to check whether the specified node is neither an ancestor of the given node nor the given node itself.

Parameters:

• Node
  The node to check.

Exceptions:

• EHierarchyRequestError
  Raised via the RaiseException() method if the specified node is an ancestor of the given node or the given node itself.

procedure CheckNotReadOnly;

This procedure is called by other methods of TCustomOwnedNode to check whether the given node is not readonly.

Exceptions:

• ENoModificationAllowedError
  Raised via the RaiseException() method if the given is readonly.

procedure CheckParentNotReadOnly(const Node: TCustomOwnedNode);

This procedure is called by other methods of TCustomOwnedNode to check whether the parent node of the specified node is not readonly.

Parameters:

• Node
  The node to check.

Exceptions:

• ENoModificationAllowedError
  Raised via the RaiseException() method if the specified node has a parent node and this parent node is readonly.

procedure CheckSameOwner(const Node: TCustomOwnedNode);

This procedure is called by other methods of TCustomOwnedNode to check whether the specified node has the same owner as the given node or the given node is the owner of the specified node.

Parameters:

• Node
  The node to check.

Exceptions:

• EWrongOwnerError
  Raised via the RaiseException() method if the given node is neither the owner of the specified node nor has the same owner than the specified node.

procedure Clear; virtual;

This procedure (recursively) frees all child nodes and all owned objects.

Exceptions:

• ENoModificationAllowedError
  Raised if the given node is readonly.

procedure DoAfterAddition(const Node: TCustomOwnedNode); virtual;

This procedure is called by other methods of TCustomOwnedNode after a child node was appended or inserted. By default this method does nothing. Descendant classes can override it to implement specific reactions, for example triggering an event.

Parameters:

• Node
  The node that was added as a child node.

procedure DoAfterClear; virtual;

This procedure is called by other methods of TCustomOwnedNode after the given node was cleared. By default this method does nothing. Descendant classes can override it to implement specific reactions, for example triggering an event.

procedure DoAfterRemoval(const Node: TCustomOwnedNode); virtual;

This procedure is called by other methods of TCustomOwnedNode after a child node was removed. By default this method does nothing. Descendant classes can override it to implement specific reactions, for example triggering an event.

Parameters:

• Node
  The child node that was removed.

procedure DoBeforeAddition(const Node: TCustomOwnedNode); virtual;

This procedure is called by other methods of TCustomOwnedNode before a child node is appended or inserted. By default this method does nothing. Descendant classes can override it to implement specific reactions, for example triggering an event.

Parameters:

• Node
  The node that is about to be added as a child node.

procedure DoBeforeClear; virtual;

This procedure is called by other methods of TCustomOwnedNode before the given node is cleared. By default this method does nothing. Descendant classes can override it to implement specific reactions, for example triggering an event.

procedure DoBeforeRemoval(const Node: TCustomOwnedNode); virtual;

This procedure is called by other methods of TCustomOwnedNode before a child node is removed. By default this method does nothing. Descendant classes can override it to implement specific reactions, for example triggering an event.

Parameters:

• Node
  The child node that is about to be removed.

function GetCount: Integer; virtual;

This function is called by the Count property to get the number of child nodes maintained by the given node.

Return Value:

• The number of nodes maintained by the given node.

function GetFirstChild: TCustomOwnedNode; virtual;

This function is called by the FirstChild property to get the first node maintained by the given node or nil if there is no such node.

Return Value:

• The first node maintained by the given node or nil if there is no such node.

function GetLastChild: TCustomOwnedNode; virtual;

This function is called by the LastChild property to get the last node maintained by the given node or nil if there is no such node.

Return Value:

• The last node maintained by the given node or nil if there is no such node.

function GetNextSibling: TCustomOwnedNode; virtual;

This function is called by the NextSibling property to get the node immediately following the given node. If there is no such node, nil is returned.

Return Value:

• The node immediately following the given node or nil if there is no such node.

function GetOwner: TPersistent; override; (inherited from TCustomOwnedObject)

This function returns the owner of the given node. If the given node has no owner, nil is returned.

Return Value:

• The owner of the given node or nil if the given node has no owner.

function GetParent: TCustomOwnedNode; virtual;

This function is called by the Parent property to get the parent of the given node. If the given node has no parent, nil is returned.

Return Value:

• The parent node of the given node or nil if the given node has no parent.

function GetPreviousSibling: TCustomOwnedNode; virtual;

This function is called by the PreviousSibling property to get the node immediately preceding the given node. If there is no such node, nil is returned.

Return Value:

• The node immediately preceding the given node or nil if there is no such node.

function GetReadOnly: Boolean; virtual;

This function is called by the ReadOnly property to determine whether the given node is readonly.

Return Value:

• 'True' if the given node is readonly, 'False' otherwise.

function HasAsAncestor(Node: TCustomOwnedNode): Boolean; virtual;

This is a convenience method to allow easy determination of whether a node is an ancestor of this node.

Parameters:

• Node
  The node to test whether it is an ancestor of the given node.

Return Value:

• 'True' if the specified node is an ancestor of the given node, 'False' otherwise.

function HasChildren: Boolean; virtual;

This is a convenience method to allow easy determination of whether the given node has any child nodes.

Return Value:

• 'True' if the specified node has one or more child nodes, 'False' otherwise.

function IndexOf(Node: TCustomOwnedNode): Integer; virtual;

Returns the index of the specified node in the Items list.

Parameters:

• Node
  The node whose index is being retrieved.

Return Value:

• The index position of the node in the Items list. The first node in the list has index 0, the second node has index 1, and so on. If a node is not in the list, IndexOf returns -1.

function InsertBefore(const NewChild, RefChild: TCustomOwnedNode): TCustomOwnedNode; virtual;

Inserts the node NewChild before the existing child node RefChild. If RefChild is nil, NewChild is inserted at the end of the list of children.

Parameters:

• NewChild
  The node to insert.
• RefChild
  The reference node, i.e., the node before which the new node must be inserted.

Return Value:

• The node being inserted.

Exceptions:

• ENotAssignedError
  Raised if NewChild is nil.
• EWrongOwnerError
  Raised if the given node is neither the owner of NewChild nor has the same owner than NewChild.
• EHierarchyRequestError
  Raised if NewChild is one of the given node's ancestors or the given node itself, or if NewChild and RefChild are identical.
• ENoModificationAllowedError
  Raised if the given node is readonly or if the previous parent of the node being appended is readonly.

procedure RaiseException(const E: ExceptClass); virtual;

Raises an exception of the specified class. Descendants may override this procedure to implement specific exception handling, for example to raise a different exception than the specified.

Parameters:

• E
  The class of the exception to be raised.

function Remove(const OldChild: TCustomOwnedNode): TCustomOwnedNode; virtual;

Removes the child node indicated by OldChild from the list of children and returns it.

Parameters:

• OldChild
  The node being removed.

Return Value:

• The node removed.

Exceptions:

• ENotAssignedError
  Raised if OldChild is nil.
• ENoModificationAllowedError
  Raised if the given node is readonly.
• ENotFoundError
  Raised if RefChild is not a child of the given node.

function Replace(const NewChild, OldChild: TCustomOwnedNode): TCustomOwnedNode; virtual;

Replaces the child node OldChild with NewChild in the set of children of the given node, and returns the OldChild node. If NewChild is already in the tree, it is first removed.

Parameters:

• NewChild
  The node to put in the child list.
• OldChild
  The node to being replaced in the child list.

Return Value:

• The node replaced.

Exceptions:

• ENotAssignedError
  Raised if NewChild or OldChild is nil.
• EWrongOwnerError
  Raised if NewChild has a different owner than the given node.
• EHierarchyRequestError
  Raised if NewChild is one of the given node's ancestors or the given node itself.
• ENoModificationAllowedError
  Raised if the given node is readonly or if the previous parent of NewChild is readonly.
• ENotFoundError
  Raised if RefChild is not a child of the given node.

procedure SetReadonly(const Value: Boolean); virtual;

This procedure is called by the ReadOnly property to specify whether the given node is readonly.

Parameters:

• Value
  'True' if the given node should be readonly, 'False' otherwise.