TLinkedBtree
Return to Unit UltiboClasses
Description
To be documented
Class definitions
TLinkedBtree = class(TObject)
Note: A B-Tree of TBtreeObjects with automatic Left/Right etc Links
Linked B-Tree which does not Free nodes on Destroy | |
Note: Search/Find should be implemented by descendants. Compare must always be implemented by descendants. Blank keys are not included in the linked list. Blank key always compares as higher than anything. Linked list allows easy traversal in either direction. Also allows implementation of the rebalance function. | |
constructor Create;
|
|
destructor Destroy; override;
|
|
private
| |
procedure SetOrder(AOrder:LongWord);
|
|
function PropogateDrop(AEntry:TBtreeObject):Boolean;
|
|
function PropogateMerge(AEntry:TBtreeObject):Boolean;
|
|
function PropogateSplit(AEntry:TBtreeObject):Boolean;
|
|
protected
| |
FOrder:LongWord;
|
Order N of B-Tree (N - 1 Keys per Node) |
FMedian:LongWord;
|
Ceil(N / 2) (Median - 1 Keys as Minimum) |
FSwapLeft:Boolean;
|
If True then Remove will Swap with Left not Right |
FRoot:TBtreeObject;
|
Root Node of B-Tree |
FFirst:TBtreeObject;
|
First object in Linked List (Sorted) |
FLast:TBtreeObject;
|
Last object in Linked List (Sorted) |
FFirstBlank:TBtreeObject;
|
First blank key in Linked List (Not Sorted) |
FLastBlank:TBtreeObject;
|
Last blank key in Linked List (Not Sorted) |
function GetCount(AEntry:TBtreeObject):LongWord; virtual;
|
|
function GetDepth(AEntry:TBtreeObject):LongWord; virtual;
|
|
function GetEnd(AEntry:TBtreeObject):TBtreeObject; virtual;
|
|
function GetStart(AEntry:TBtreeObject):TBtreeObject; virtual;
|
|
function GetBlank(AEntry:TBtreeObject):TBtreeObject; virtual;
|
|
function GetMedian(AEntry:TBtreeObject):TBtreeObject; virtual;
|
|
function GetDrop(AEntry:TBtreeObject; var ALeft:Boolean):TBtreeObject; virtual;
|
|
function GetMerge(AEntry:TBtreeObject):TBtreeObject; virtual;
|
|
function GetBorrow(AEntry:TBtreeObject):TBtreeObject; virtual;
|
|
function GetTarget(ADrop:TBtreeObject; ALeft:Boolean):TBtreeObject; virtual;
|
|
function SetParent(AEntry,AParent:TBtreeObject):Boolean;
|
|
function GetLefthand(AEntry:TBtreeObject):TBtreeObject;
|
|
function GetRighthand(AEntry:TBtreeObject):TBtreeObject;
|
|
function GetLeftmost(AEntry:TBtreeObject):TBtreeObject;
|
|
function GetRightmost(AEntry:TBtreeObject):TBtreeObject;
|
|
function GetSuccessor(AEntry:TBtreeObject):TBtreeObject;
|
|
function GetPredecessor(AEntry:TBtreeObject):TBtreeObject;
|
|
function GetPosition(AStart,AEntry:TBtreeObject):TBtreeObject;
|
|
function Push(AEntry:TBtreeObject):Boolean;
|
|
function Split(AEntry:TBtreeObject):Boolean;
|
|
function Swap(AEntry,ASwap:TBtreeObject; ALeft:Boolean):Boolean;
|
|
function Drop(AEntry,ADrop,ATarget:TBtreeObject; ALeft:Boolean):Boolean;
|
|
function Merge(AEntry,AMerge:TBtreeObject):Boolean;
|
|
function Borrow(AEntry,ABorrow:TBtreeObject):Boolean;
|
|
function Link(AEntry,ANext:TBtreeObject):Boolean;
|
|
function Unlink(AEntry:TBtreeObject):Boolean;
|
|
function LinkBlank(AEntry:TBtreeObject):Boolean;
|
|
function UnlinkBlank(AEntry:TBtreeObject):Boolean;
|
|
function Attach(AParent,AEntry,ARight:TBtreeObject):Boolean;
|
|
function Detach(AEntry:TBtreeObject):Boolean;
|
|
function PushNode(AEntry:TBtreeObject):Boolean; virtual;
|
Allows descendants to monitor node pus |
function SplitNode(AEntry:TBtreeObject):Boolean; virtual;
|
Allows descendants to monitor node split |
function DropNode(AEntry,ADrop,ATarget:TBtreeObject; ALeft:Boolean):Boolean; virtual;
|
Allows descendants to monitor node drop |
function MergeNode(AEntry,AMerge:TBtreeObject):Boolean; virtual;
|
Allows descendants to monitor node merge |
function BorrowEntry(AEntry,ABorrow:TBtreeObject):Boolean; virtual;
|
Allows descendants to monitor entry borrow |
function SwapEntry(AEntry,ASwap:TBtreeObject;ALeft:Boolean):Boolean; virtual;
|
Allows descendants to monitor entry swap |
function SetParentEntry(AEntry,AParent:TBtreeObject):Boolean; virtual;
|
Allows descendants to monitor entry parent |
function CreateBlank:TBtreeObject; virtual;
|
Allows descendants to monitor node creation |
function DeleteBlank(ABlank:TBtreeObject):Boolean; virtual;
|
Allows descendants to monitor node deletion |
function AttachBlank(ABlank:TBtreeObject):Boolean; virtual;
|
Allows descendants to monitor node modification |
function DetachBlank(ABlank:TBtreeObject):Boolean; virtual;
|
Allows descendants to monitor node modification |
function AttachEntry(AEntry:TBtreeObject):Boolean; virtual;
|
Allows descendants to monitor node modification |
function DetachEntry(AEntry:TBtreeObject):Boolean; virtual;
|
Allows descendants to monitor node modification |
function RequirePush(AEntry:TBtreeObject):Boolean; virtual;
|
Allows descendants to modify balancing behaviour |
function RequireSplit(AEntry:TBtreeObject):Boolean; virtual;
|
Allows descendants to modify balancing behaviour |
function RequireDrop(AEntry:TBtreeObject):Boolean; virtual;
|
Allows descendants to modify balancing behaviour |
function RequireMerge(AEntry:TBtreeObject):Boolean; virtual;
|
Allows descendants to modify balancing behaviour |
function RequireBorrow(AEntry:TBtreeObject):Boolean; virtual;
|
Allows descendants to modify balancing behaviour |
function Compare(AEntry1,AEntry2:TBtreeObject):Integer; virtual;
|
|
public
| |
property Order:LongWord read FOrder write SetOrder;
|
|
property Median:LongWord read FMedian;
|
|
property SwapLeft:Boolean read FSwapLeft;
|
|
property Root:TBtreeObject read FRoot;
|
|
property First:TBtreeObject read FFirst;
|
|
property Last:TBtreeObject read FLast;
|
|
function Add(AParent,AEntry:TBtreeObject):Boolean;
|
|
function Insert(AEntry:TBtreeObject):Boolean;
|
|
function Remove(AEntry:TBtreeObject):Boolean;
|
|
procedure Clear;
|
|
procedure Empty;
|
|
procedure Rebuild;
|
Function declarations
constructor TLinkedBtree.Create;
Note | None documented |
---|
destructor TLinkedBtree.Destroy;
Note | None documented |
---|
procedure TLinkedBtree.SetOrder(AOrder:LongWord);
Note | Minimum Order is 5 and minimum Median is 3 |
---|
function TLinkedBtree.PropogateDrop(AEntry:TBtreeObject):Boolean;
Note | None documented |
---|
function TLinkedBtree.PropogateMerge(AEntry:TBtreeObject):Boolean;
Note | None documented |
---|
function TLinkedBtree.PropogateSplit(AEntry:TBtreeObject):Boolean;
Note | This is currently not used by insert and must be tested before use |
---|
function TLinkedBtree.GetCount(AEntry:TBtreeObject):LongWord;
Note | Does not include the blank key |
---|
function TLinkedBtree.GetDepth(AEntry:TBtreeObject):LongWord;
Note | None documented |
---|
function TLinkedBtree.GetEnd(AEntry:TBtreeObject):TBtreeObject;
Note | Includes the blank key which may be the only key |
---|
function TLinkedBtree.GetStart(AEntry:TBtreeObject):TBtreeObject;
Note | Includes the blank key which may be the only key |
---|
function TLinkedBtree.GetBlank(AEntry:TBtreeObject):TBtreeObject;
Note | Blank entry is always the last entry in every node |
---|
function TLinkedBtree.GetMedian(AEntry:TBtreeObject):TBtreeObject;
Note | Does not include the blank key |
---|
function TLinkedBtree.GetDrop(AEntry:TBtreeObject; var ALeft:Boolean):TBtreeObject;
Note | Always drop with the Righthand neighbour if available
Only supported by descendant classes with non balanced nodes |
---|
function TLinkedBtree.GetMerge(AEntry:TBtreeObject):TBtreeObject;
Note | Always merge with the Righthand neighbour if available |
---|
function TLinkedBtree.GetBorrow(AEntry:TBtreeObject):TBtreeObject;
Note | Always borrow from the Righthand neighbour if available |
---|
function TLinkedBtree.GetTarget(ADrop:TBtreeObject; ALeft:Boolean):TBtreeObject;
Note | Only supported by descendant classes with non balanced nodes |
---|
function TLinkedBtree.SetParent(AEntry,AParent:TBtreeObject):Boolean;
Note | Includes the blank key which may be the only key |
---|
function TLinkedBtree.GetLefthand(AEntry:TBtreeObject):TBtreeObject;
Note | None documented |
---|
function TLinkedBtree.GetRighthand(AEntry:TBtreeObject):TBtreeObject;
Note | None documented |
---|
function TLinkedBtree.GetLeftmost(AEntry:TBtreeObject):TBtreeObject;
Note | None documented |
---|
function TLinkedBtree.GetRightmost(AEntry:TBtreeObject):TBtreeObject;
Note | Does not include the blank key |
---|
function TLinkedBtree.GetSuccessor(AEntry:TBtreeObject):TBtreeObject;
Note | The returned entry may be a blank key or a real key |
---|
function TLinkedBtree.GetPredecessor(AEntry:TBtreeObject):TBtreeObject;
Note | The returned entry may be a blank key or a real key |
---|
function TLinkedBtree.GetPosition(AStart,AEntry:TBtreeObject):TBtreeObject;
Note | The returned entry will be the entry to the right in insert node
The returned entry may be the blank key or may be a real key |
---|
function TLinkedBtree.Push(AEntry:TBtreeObject):Boolean;
Note | Will create a new blank as root
All keys will be parented by new blank root
|
---|
function TLinkedBtree.Split(AEntry:TBtreeObject):Boolean;
Note | Will promote the median entry to the parent
Keys left of median will be parented by median
|
---|
function TLinkedBtree.Swap(AEntry,ASwap:TBtreeObject; ALeft:Boolean):Boolean;
Note | Entry is always a parent and Swap is always a leaf
No balancing is done as the entry is to be deleted or borrowed |
---|
function TLinkedBtree.Drop(AEntry,ADrop,ATarget:TBtreeObject; ALeft:Boolean):Boolean;
Note | Will demote the parent entry to the drop node
Drop with Right (Entry has no child)
|
---|
function TLinkedBtree.Merge(AEntry,AMerge:TBtreeObject):Boolean;
Note | Will demote the parent entry to the merged node
Merge with Right
|
---|
function TLinkedBtree.Borrow(AEntry,ABorrow:TBtreeObject):Boolean;
Note | Will demote the parent and premote the successor
Borrow from Right
|
---|
function TLinkedBtree.Link(AEntry,ANext:TBtreeObject):Boolean;
Note | If Next is nil then link as last |
---|
function TLinkedBtree.Unlink(AEntry:TBtreeObject):Boolean;
Note | None documented |
---|
function TLinkedBtree.LinkBlank(AEntry:TBtreeObject):Boolean;
Note | Always link as last |
---|
function TLinkedBtree.UnlinkBlank(AEntry:TBtreeObject):Boolean;
Note | None documented |
---|
function TLinkedBtree.Attach(AParent,AEntry,ARight:TBtreeObject):Boolean;
Note | If Right is nil then attach as last
If Parent is nil then attach at root |
---|
function TLinkedBtree.Detach(AEntry:TBtreeObject):Boolean;
Note | None documented |
---|
function TLinkedBtree.PushNode(AEntry:TBtreeObject):Boolean;
Note | None documented |
---|
function TLinkedBtree.SplitNode(AEntry:TBtreeObject):Boolean;
Note | None documented |
---|
function TLinkedBtree.DropNode(AEntry,ADrop,ATarget:TBtreeObject; ALeft:Boolean):Boolean;
Note | None documented |
---|
function TLinkedBtree.MergeNode(AEntry,AMerge:TBtreeObject):Boolean;
Note | None documented |
---|
function TLinkedBtree.BorrowEntry(AEntry,ABorrow:TBtreeObject):Boolean;
Note | None documented |
---|
function TLinkedBtree.SwapEntry(AEntry,ASwap:TBtreeObject; ALeft:Boolean):Boolean;
Note | None documented |
---|
function TLinkedBtree.SetParentEntry(AEntry,AParent:TBtreeObject):Boolean;
Note | None documented |
---|
function TLinkedBtree.CreateBlank:TBtreeObject;
Note | None documented |
---|
function TLinkedBtree.DeleteBlank(ABlank:TBtreeObject):Boolean;
Note | None documented |
---|
function TLinkedBtree.AttachBlank(ABlank:TBtreeObject):Boolean;
Note | None documented |
---|
function TLinkedBtree.DetachBlank(ABlank:TBtreeObject):Boolean;
Note | None documented |
---|
function TLinkedBtree.AttachEntry(AEntry:TBtreeObject):Boolean;
Note | None documented |
---|
function TLinkedBtree.DetachEntry(AEntry:TBtreeObject):Boolean;
Note | None documented |
---|
function TLinkedBtree.RequirePush(AEntry:TBtreeObject):Boolean;
Entry | Entry is the key that was inserted
Or a key in a parent node of the node where the entry was inserted |
---|---|
Note | Only supported by descendant classes with non balanced nodes |
function TLinkedBtree.RequireSplit(AEntry:TBtreeObject):Boolean;
Entry | Entry is the key that was inserted
Or a key in a parent node of the node where the entry was inserted |
---|
function TLinkedBtree.RequireDrop(AEntry:TBtreeObject):Boolean;
Entry | Entry is the start key of the node where the entry was removed
Or a key in a parent node of the node where the entry was removed |
---|---|
Note | Only supported by descendant classes with non balanced nodes |
function TLinkedBtree.RequireMerge(AEntry:TBtreeObject):Boolean;
Entry | Entry is the start key of the node where the entry was removed
Or a key in a parent node of the node where the entry was removed |
---|
function TLinkedBtree.RequireBorrow(AEntry:TBtreeObject):Boolean;
Entry | Entry is the start key of the node where the entry was removed
Or a key in a parent node of the node where the entry was removed |
---|
function TLinkedBtree.Compare(AEntry1,AEntry2:TBtreeObject):Integer;
Note | This means keys will end up in added order if no compare is provided |
---|
function TLinkedBtree.Add(AParent,AEntry:TBtreeObject):Boolean;
Entry | Entries must be added in btree order to obtain final order |
---|---|
Note | Both real and blank keys can be added
No events are triggered by Add |
function TLinkedBtree.Insert(AEntry:TBtreeObject):Boolean;
Note | Rebalances the tree after inserting the new entry
Blank keys cannot be inserted
|
---|
function TLinkedBtree.Remove(AEntry:TBtreeObject):Boolean;
Note | Rebalances the tree after deleting the entry
Blank keys cannot be removed
|
---|
procedure TLinkedBtree.Clear;
Note | None documented |
---|
procedure TLinkedBtree.Empty;
Note | None documented |
---|
procedure TLinkedBtree.Rebuild;
Note | None documented |
---|
Return to Unit Reference