|
|
| (One intermediate revision by the same user not shown) |
| Line 1: |
Line 1: |
| − |
| |
| − |
| |
| − |
| |
| | Return to [[Unit_UltiboClasses|Unit UltiboClasses]] | | Return to [[Unit_UltiboClasses|Unit UltiboClasses]] |
| | | | |
| Line 45: |
Line 42: |
| | |- | | |- |
| | | <code>function PropogateDrop(AEntry:TBtreeObject):Boolean;</code> | | | <code>function PropogateDrop(AEntry:TBtreeObject):Boolean;</code> |
| − | |
| |
| − | |-
| |
| − | | <code>function PropogateDropOld(AEntry:TBtreeObject):Boolean;</code>
| |
| − | |
| |
| − | |-
| |
| − | | <code>function PropogateDropOldOld(AEntry:TBtreeObject):Boolean;</code>
| |
| | | | | | |
| | |- | | |- |
| Line 171: |
Line 162: |
| | |- | | |- |
| | | <code>function Drop(AEntry,ADrop,ATarget:TBtreeObject; ALeft:Boolean):Boolean;</code> | | | <code>function Drop(AEntry,ADrop,ATarget:TBtreeObject; ALeft:Boolean):Boolean;</code> |
| − | |
| |
| − | |-
| |
| − | | <code>function DropOld(AEntry,ADrop:TBtreeObject; ALeft:Boolean):Boolean;</code>
| |
| − | |
| |
| − | |-
| |
| − | | <code>function DropOldOld(AEntry,ADrop:TBtreeObject; ALeft:Boolean):Boolean;</code>
| |
| − | |
| |
| − | |-
| |
| − | | <code>function DropOldOldOld(AEntry,ADrop:TBtreeObject; ALeft:Boolean):Boolean;</code>
| |
| | | | | | |
| | |- | | |- |
| Line 221: |
Line 203: |
| | |- | | |- |
| | | <code>function DropNode(AEntry,ADrop,ATarget:TBtreeObject; ALeft:Boolean):Boolean; virtual;</code> | | | <code>function DropNode(AEntry,ADrop,ATarget:TBtreeObject; ALeft:Boolean):Boolean; virtual;</code> |
| − | | Allows descendants to monitor node drop
| |
| − | |-
| |
| − | | <code>function DropNodeOld(AEntry,ADrop:TBtreeObject; ALeft:Boolean):Boolean; virtual;</code>
| |
| | | Allows descendants to monitor node drop | | | Allows descendants to monitor node drop |
| | |- | | |- |
| Line 321: |
Line 300: |
| | |- | | |- |
| | | <code>function Remove(AEntry:TBtreeObject):Boolean;</code> | | | <code>function Remove(AEntry:TBtreeObject):Boolean;</code> |
| − | |
| |
| − | |-
| |
| − | | <code>function RemoveOld(AEntry:TBtreeObject):Boolean;</code>
| |
| − | |
| |
| − | |-
| |
| − | | <code>function RemoveOldOld(AEntry:TBtreeObject):Boolean;</code>
| |
| | | | | | |
| | |- | | |- |
Latest revision as of 05:25, 21 June 2023
Return to Unit UltiboClasses
Description
To be documented
Class definitions
[Expand]
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
[Expand]
constructor TLinkedBtree.Create;
Description: To be documented
[Expand]
destructor TLinkedBtree.Destroy;
Description: To be documented
[Expand]
procedure TLinkedBtree.SetOrder(AOrder:LongWord);
Description: Set a new Order and calculate a new Median value
| Note
|
Minimum Order is 5 and minimum Median is 3
|
[Expand]
function TLinkedBtree.PropogateDrop(AEntry:TBtreeObject):Boolean;
Description: To be documented
[Expand]
function TLinkedBtree.PropogateMerge(AEntry:TBtreeObject):Boolean;
Description: To be documented
[Expand]
function TLinkedBtree.PropogateSplit(AEntry:TBtreeObject):Boolean;
Description: To be documented
| Note
|
This is currently not used by insert and must be tested before use
|
[Expand]
function TLinkedBtree.GetCount(AEntry:TBtreeObject):LongWord;
Description: Get the count of entries in the node of the supplied entry
| Note
|
Does not include the blank key
|
[Expand]
function TLinkedBtree.GetDepth(AEntry:TBtreeObject):LongWord;
Description: Get the depth of the supplied entry in the btree
[Expand]
function TLinkedBtree.GetEnd(AEntry:TBtreeObject):TBtreeObject;
Description: Get the end entry in the node of the supplied entry
| Note
|
Includes the blank key which may be the only key
|
[Expand]
function TLinkedBtree.GetStart(AEntry:TBtreeObject):TBtreeObject;
Description: Get the start entry in the node of the supplied entry
| Note
|
Includes the blank key which may be the only key
|
[Expand]
function TLinkedBtree.GetBlank(AEntry:TBtreeObject):TBtreeObject;
Description: Get the blank entry in the node of the supplied entry
| Note
|
Blank entry is always the last entry in every node
|
[Expand]
function TLinkedBtree.GetMedian(AEntry:TBtreeObject):TBtreeObject;
Description: Get the median entry in the node of the supplied entry
| Note
|
Does not include the blank key
|
[Expand]
function TLinkedBtree.GetDrop(AEntry:TBtreeObject; var ALeft:Boolean):TBtreeObject;
Description: Get the neighbour with appropriate number of keys to drop
| Note
|
Always drop with the Righthand neighbour if available
Only supported by descendant classes with non balanced nodes
|
[Expand]
function TLinkedBtree.GetMerge(AEntry:TBtreeObject):TBtreeObject;
Description: Get the neighbour with appropriate number of keys to merge
| Note
|
Always merge with the Righthand neighbour if available
|
[Expand]
function TLinkedBtree.GetBorrow(AEntry:TBtreeObject):TBtreeObject;
Description: Get the neighbour with sufficient keys to borrow one
| Note
|
Always borrow from the Righthand neighbour if available
|
[Expand]
function TLinkedBtree.GetTarget(ADrop:TBtreeObject; ALeft:Boolean):TBtreeObject;
Description: Get the actual target within the neighbour that is appropriate to drop
| Note
|
Only supported by descendant classes with non balanced nodes
|
[Expand]
function TLinkedBtree.SetParent(AEntry,AParent:TBtreeObject):Boolean;
Description: Set the parent for all entries in a node and set the child of the parent
| Note
|
Includes the blank key which may be the only key
|
[Expand]
function TLinkedBtree.GetLefthand(AEntry:TBtreeObject):TBtreeObject;
Description: Get the lefthand neighbour (Node) of the supplied entries node
[Expand]
function TLinkedBtree.GetRighthand(AEntry:TBtreeObject):TBtreeObject;
Description: Get the righthand neighbour (Node) of the supplied entries node
[Expand]
function TLinkedBtree.GetLeftmost(AEntry:TBtreeObject):TBtreeObject;
Description: Get the leftmost entry in the tree of the supplied entry
[Expand]
function TLinkedBtree.GetRightmost(AEntry:TBtreeObject):TBtreeObject;
Description: Get the rightmost entry in the tree of the supplied entry
| Note
|
Does not include the blank key
|
[Expand]
function TLinkedBtree.GetSuccessor(AEntry:TBtreeObject):TBtreeObject;
Description: Get the successor (Right) entry of the supplied entry
| Note
|
The returned entry may be a blank key or a real key
|
[Expand]
function TLinkedBtree.GetPredecessor(AEntry:TBtreeObject):TBtreeObject;
Description: Get the predecessor (Left) entry of the supplied entry
| Note
|
The returned entry may be a blank key or a real key
|
[Expand]
function TLinkedBtree.GetPosition(AStart,AEntry:TBtreeObject):TBtreeObject;
Description: Get the position where entry should be inserted into the btree
| 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
|
[Expand]
function TLinkedBtree.Push(AEntry:TBtreeObject):Boolean;
Description: Push the node containing the supplied entry
| Note
|
Will create a new blank as root
All keys will be parented by new blank root
Push can only occur on the root node
|
[Expand]
function TLinkedBtree.Split(AEntry:TBtreeObject):Boolean;
Description: Split the node containing the supplied entry
| Note
|
Will promote the median entry to the parent
Keys left of median will be parented by median
Keys right of median will retain current parent
Child of median will parent to new blank on left
Median will be attached to the left of the parent
Split can propogate all the way to root since median is promoted
|
[Expand]
function TLinkedBtree.Swap(AEntry,ASwap:TBtreeObject; ALeft:Boolean):Boolean;
Description: Swap the supplied entries directly from node to node
| 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
|
[Expand]
function TLinkedBtree.Drop(AEntry,ADrop,ATarget:TBtreeObject; ALeft:Boolean):Boolean;
Description: Drop the nodes of the supplied entries into one
| Note
|
Will demote the parent entry to the drop node
Drop with Right (Entry has no child)
Parent of left node will become part of target node (start)
Parent of right node will remain as parent of drop node
Left node will be deleted
Drop with Right (Entry has a child)
Node will be deleted
Child of node will be parented by parent of node
Drop with Left (Entry has no child)
Parent of left node will become part of target node (last before blank)
Parent of right node will become parent of drop node
Right node will be deleted
Drop with Left (Entry has a child)
Node will be deleted
Child of node will be parented by parent of node
Drop with no Neighbour
Node will be deleted
Child of node will be parented by parent of node
Drop can propogate all the way to root since parent is demoted
|
[Expand]
function TLinkedBtree.Merge(AEntry,AMerge:TBtreeObject):Boolean;
Description: Merge the nodes of the supplied entries into one
| Note
|
Will demote the parent entry to the merged node
Merge with Right
Parent of left node will become part of child node (Between last of left and start of right)
Parent of right node will become parent of merged child
Merge with Left
Convert to merge with right by calling itself with swapped parameters
Merge can propogate all the way to root since parent is demoted
|
[Expand]
function TLinkedBtree.Borrow(AEntry,ABorrow:TBtreeObject):Boolean;
Description: Borrow an entry from the supplied node to balance the tree
| Note
|
Will demote the parent and premote the successor
Borrow from Right
Start key of right node will become the parent key of left node
Parent key of left node will become the last key of left node
Borrow from Left
Last key of left node will become the parent key of left node
Parent key of left node will become the start key of right node
Borrow does not propogate to parent since their is a promote and a demote
Borrow can occur in non leaf nodes due to merge of child nodes which demotes
Borrow with Child
Child of promoted key will go to blank key of left node
Child of blank key of left node will go to demoted key
|
[Expand]
function TLinkedBtree.Link(AEntry,ANext:TBtreeObject):Boolean;
Description: Link the object to Prev/Next in linked list
| Note
|
If Next is nil then link as last
|
[Expand]
function TLinkedBtree.Unlink(AEntry:TBtreeObject):Boolean;
Description: Unlink the object from Prev/Next in linked list
[Expand]
function TLinkedBtree.LinkBlank(AEntry:TBtreeObject):Boolean;
Description: Link the object to Prev/Next in blank key list
[Expand]
function TLinkedBtree.UnlinkBlank(AEntry:TBtreeObject):Boolean;
Description: Unlink the object from Prev/Next in blank key list
[Expand]
function TLinkedBtree.Attach(AParent,AEntry,ARight:TBtreeObject):Boolean;
Description: Attach the object to Parent/Left/Right in btree
| Note
|
If Right is nil then attach as last
If Parent is nil then attach at root
|
[Expand]
function TLinkedBtree.Detach(AEntry:TBtreeObject):Boolean;
Description: Detach the object from Parent/Left/Right in btree
[Expand]
function TLinkedBtree.PushNode(AEntry:TBtreeObject):Boolean;
Description: Called before a node is pushed following insert of an entry
[Expand]
function TLinkedBtree.SplitNode(AEntry:TBtreeObject):Boolean;
Description: Called before a node is split following insert of an entry
[Expand]
function TLinkedBtree.DropNode(AEntry,ADrop,ATarget:TBtreeObject; ALeft:Boolean):Boolean;
Description: Called before a node is dropped following removal of an entry
[Expand]
function TLinkedBtree.MergeNode(AEntry,AMerge:TBtreeObject):Boolean;
Description: Called before a node is merged following removal of an entry
[Expand]
function TLinkedBtree.BorrowEntry(AEntry,ABorrow:TBtreeObject):Boolean;
Description: Called before an entry is borrowed following removal of an entry
[Expand]
function TLinkedBtree.SwapEntry(AEntry,ASwap:TBtreeObject; ALeft:Boolean):Boolean;
Description: Called before an entry is swapped during a merge or borrow
[Expand]
function TLinkedBtree.SetParentEntry(AEntry,AParent:TBtreeObject):Boolean;
Description: Called after an entry is reparented during a push, split, merge, borrow or swap
[Expand]
function TLinkedBtree.CreateBlank:TBtreeObject;
Description: Create a blank key when a node is added (Split/Empty)
[Expand]
function TLinkedBtree.DeleteBlank(ABlank:TBtreeObject):Boolean;
Description: Delete a blank key when a node is removed (Merge)
[Expand]
function TLinkedBtree.AttachBlank(ABlank:TBtreeObject):Boolean;
Description: Called after a blank entry is attached to a node during split or merge
[Expand]
function TLinkedBtree.DetachBlank(ABlank:TBtreeObject):Boolean;
Description: Called before a blank entry is detached from a node during split or merge
[Expand]
function TLinkedBtree.AttachEntry(AEntry:TBtreeObject):Boolean;
Description: Called after a non blank entry is attached to a node during insert or remove
[Expand]
function TLinkedBtree.DetachEntry(AEntry:TBtreeObject):Boolean;
Description: Called before a non blank entry is detached from a node during insert or remove
[Expand]
function TLinkedBtree.RequirePush(AEntry:TBtreeObject):Boolean;
Description: Called after an entry is inserted to determine if a push is required
| 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
|
[Expand]
function TLinkedBtree.RequireSplit(AEntry:TBtreeObject):Boolean;
Description: Called after an entry is inserted to determine if a split is required
| Entry
|
Entry is the key that was inserted
Or a key in a parent node of the node where the entry was inserted
|
[Expand]
function TLinkedBtree.RequireDrop(AEntry:TBtreeObject):Boolean;
Description: Called after an entry is removed to determine if a drop is required
| 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
|
[Expand]
function TLinkedBtree.RequireMerge(AEntry:TBtreeObject):Boolean;
Description: Called after an entry is removed to determine if a merge is required
| 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
|
[Expand]
function TLinkedBtree.RequireBorrow(AEntry:TBtreeObject):Boolean;
Description: Called after an entry is removed to determine if a borrow is required
| 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
|
[Expand]
function TLinkedBtree.Compare(AEntry1,AEntry2:TBtreeObject):Integer;
Description: Always returns greater than unless the second entry is a blank key
| Note
|
This means keys will end up in added order if no compare is provided
|
[Expand]
function TLinkedBtree.Add(AParent,AEntry:TBtreeObject):Boolean;
Description: Add an entry to the btree without doing the full insert
| 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
|
[Expand]
function TLinkedBtree.Insert(AEntry:TBtreeObject):Boolean;
Description: Insert an entry in the btree by finding its position
| Note
|
Rebalances the tree after inserting the new entry
Blank keys cannot be inserted
Entry must be created by the caller
|
[Expand]
function TLinkedBtree.Remove(AEntry:TBtreeObject):Boolean;
Description: Remove an entry from the btree by deleting it
| Note
|
Rebalances the tree after deleting the entry
Blank keys cannot be removed
Entry must be destroyed by the caller
|
[Expand]
procedure TLinkedBtree.Clear;
Description: Removes all entries from the btree
[Expand]
procedure TLinkedBtree.Empty;
Description: Removes all entries from the btree and adds a blank root key
[Expand]
procedure TLinkedBtree.Rebuild;
Description: Empties the btree and rebuilds from the linked list
Return to Unit Reference
