_rb_tree.inc_pas

Delphi Generic Algorytms library - Maps, Lists, Hashmaps, Datastructures.

  Inti();
end;

destructor _TRB_Tree.Destroy;
begin
  self.Clear();
  system.Dispose(FHeader);
  FHeader:=nil;
  inherited;
end;

procedure _TRB_Tree.DisposeAll(EraseNode:_PRB_TreeNode);
  procedure _DisposeAll(EraseNode:_PRB_TreeNode);
  begin
    if (EraseNode.Left<>nil) then
      _DisposeAll(EraseNode.Left);
    if (EraseNode.Right<>nil) then
      _DisposeAll(EraseNode.Right);
    self.DisposeNode(EraseNode);
  end;
begin
  // erase without rebalancing
  if (EraseNode<>nil) then
    _DisposeAll(EraseNode);
end;

procedure _TRB_Tree.Clear();
begin
  if (self.FNodeCount>0) then
  begin
    self.DisposeAll(self.FHeader.Parent);
    Inti();
  end;
end;

function _TRB_Tree.ItBegin: _TRB_TreeIterator;
begin
  result.Node:=self.FHeader.Left;
end;

function _TRB_Tree.ItEnd: _TRB_TreeIterator;
begin
  result.Node:=self.FHeader;
end;

function _TRB_Tree.IsEmpty: boolean;
begin
  result:=self.FNodeCount=0;
end;

function _TRB_Tree.Size: integer;
begin
  result:=self.FNodeCount;
end;

function _TRB_Tree.FindInsertNodeParent(
  const Key: _RB_Tree_KeyType;const pIsInsertLeftNode:PBoolean): _PRB_TreeNode;
var
  pNodePos: _PRB_TreeNode;
  resultComp : boolean;
begin
  result:=self.FHeader;
  pNodePos :=self.FHeader.Parent;
  resultComp:=true;
  while (pNodePos<>nil) do
  begin
    result:=pNodePos;
    {$ifdef _DGL_Compare_Key}
    resultComp:=_IsLess_Key(Key,pNodePos.Key);
    {$else}
    resultComp:=(Key<pNodePos.Key); 
    {$endif}
    if resultComp then
      pNodePos:=pNodePos.Left
    else
      pNodePos:=pNodePos.Right;
  end;
  if pIsInsertLeftNode<>nil then
    pIsInsertLeftNode^:=resultComp;
end;

procedure _TRB_Tree.privateAddNode(pNodeNew, pNodePos,
  pNodeParent: _PRB_TreeNode; const Key: _RB_Tree_KeyType);
begin
  if (pNodeParent=self.FHeader)or(pNodePos<>nil) or
    {$ifdef _DGL_Compare_Key}
    (_IsLess_Key(Key,pNodeParent.Key))
    {$else}
    (Key<pNodeParent.Key)
    {$endif}
     then
  begin
    pNodeParent.Left := pNodeNew;

    if (pNodeParent = self.FHeader) then
    begin
      self.FHeader.Parent := pNodeNew;
      self.FHeader.Right := pNodeNew;
    end
    else if (pNodeParent = self.FHeader.Left) then
      self.FHeader.left := pNodeNew;
  end
  else
  begin
    pNodeParent.Right := pNodeNew;
    if (pNodeParent = self.FHeader.Right) then
      self.FHeader.Right := pNodeNew;
  end;
  pNodeNew.Parent := pNodeParent;
  pNodeNew.Left := nil;
  pNodeNew.Right := nil;
  _RB_Tree_ReBalance(pNodeNew, self.FHeader.Parent);
  inc(self.FNodeCount);
end;

procedure _TRB_Tree.AddNode(pNodePos: _PRB_TreeNode;pNodeParent: _PRB_TreeNode;
  const Key: _RB_Tree_KeyType;const Value:_RB_Tree_ValueType);
begin
  privateAddNode(self.getNewNode(Key,Value),pNodePos,pNodeParent,Key);
end;

procedure _TRB_Tree.AddNode(pNodePos: _PRB_TreeNode;pNodeParent: _PRB_TreeNode;
  const Key: _RB_Tree_KeyType);
begin
  privateAddNode(self.getNewNode(Key),pNodePos,pNodeParent,Key);
end;

procedure _TRB_Tree.MultiInsert(const Key: _RB_Tree_KeyType);
begin
  AddNode(nil,FindInsertNodeParent(Key),Key);
end;

procedure _TRB_Tree.MultiInsert(const Key: _RB_Tree_KeyType;
  const Value: _RB_Tree_ValueType);
begin
  AddNode(nil,FindInsertNodeParent(Key),Key,Value);
end;

procedure _TRB_Tree.UniqueInsert(const Key: _RB_Tree_KeyType);
var
  IsInsertLeftNode : Boolean;
  InsertNodeParent : _PRB_TreeNode;
  ItInsert : _TRB_TreeIterator;
begin
  InsertNodeParent:=FindInsertNodeParent(Key,@IsInsertLeftNode);

  ItInsert.Node:=InsertNodeParent;
  if (IsInsertLeftNode) then
  begin
    if (ItInsert.Node=self.ItBegin.Node) then
    begin
      AddNode(nil,InsertNodeParent,Key);
      exit;
    end
    else
      _TRB_TreeIt_Previous(ItInsert);
  end;

  {$ifdef _DGL_Compare_Key}
  if (_IsLess_Key(ItInsert.Node.Key,Key)) then
  {$else}
  if (ItInsert.Node.Key<Key) then
  {$endif}
    AddNode(nil,InsertNodeParent,Key);
  //else  do noting
end;

procedure _TRB_Tree.UniqueInsert(const Key: _RB_Tree_KeyType;
  const Value: _RB_Tree_ValueType);
var
  IsInsertLeftNode : Boolean;
  InsertNodeParent : _PRB_TreeNode;
  ItInsert : _TRB_TreeIterator;
begin
  InsertNodeParent:=FindInsertNodeParent(Key,@IsInsertLeftNode);

  ItInsert.Node:=InsertNodeParent;
  if (IsInsertLeftNode) then
  begin
    if (ItInsert.Node=self.ItBegin.Node) then
    begin
      AddNode(nil,InsertNodeParent,Key,Value);
      exit;
    end
    else
      _TRB_TreeIt_Previous(ItInsert);
  end;

  {$ifdef _DGL_Compare_Key}
  if (_IsLess_Key(ItInsert.Node.Key,Key)) then
  {$else}
  if (ItInsert.Node.Key<Key) then 
  {$endif}
    AddNode(nil,InsertNodeParent,Key,Value);
  //else  do noting
end;

function  _TRB_Tree.CountRange(const Key:_RB_Tree_KeyType;out ItBegin,ItEnd:_TRB_TreeIterator):integer;
var
  it :_TRB_TreeIterator;
begin
  EqualRange(Key,ItBegin,ItEnd);

  result:=0;
  it.Node:=ItBegin.Node;
  while (It.Node<>ItEnd.Node) do
  begin
    inc(result);
    _TRB_TreeIt_Next(It);
  end;
end;

function _TRB_Tree.Count(const Key: _RB_Tree_KeyType): integer;
var
  ItBegin,ItEnd: _TRB_TreeIterator;
begin
  result:=self.CountRange(Key,ItBegin,ItEnd);
end;

procedure _TRB_Tree.EqualRange(const Key: _RB_Tree_KeyType; out ItBegin,
  ItEnd: _TRB_TreeIterator);
begin
  ItBegin:=self.LowerBound(Key);
  ItEnd:=self.UpperBound(Key);
end;

procedure _TRB_Tree.Erase(const ItPos: _TRB_TreeIterator);
var
  tmpPNode : _PRB_TreeNode;
begin
  tmpPNode:= _Rb_Tree_Rebalance_For_Erase(ItPos.Node,
                                          self.FHeader.Parent,
                                          self.FHeader.Left,
                                          self.FHeader.Right);
  self.DisposeNode(tmpPNode);
  dec(self.FNodeCount);
end;

procedure _TRB_Tree.Erase(const ItBegin, ItEnd: _TRB_TreeIterator);
var
  it     : _TRB_TreeIterator;
  itBack : _TRB_TreeIterator;
begin
  it.Node:=ItBegin.Node;
  while (it.Node<>ItEnd.Node) do
  begin
    itBack:=it;
    _TRB_TreeIt_Next(it);
    Erase(itBack);
  end;
end;

function _TRB_Tree.EraseKey(const Key: _RB_Tree_KeyType): integer;
var
  ItBegin,ItEnd: _TRB_TreeIterator;
begin
  result:=self.CountRange(Key,ItBegin,ItEnd);
  if result>0 then
    self.Erase(ItBegin,ItEnd);
end;

function _TRB_Tree.EraseValue(const Key: _RB_Tree_KeyType;
  const Value: _RB_Tree_ValueType): integer;
var
  It: _TRB_TreeIterator;
begin
  result:=0;
  It:=self.FindKey(Key);
  while It.Node<>self.ItEnd.Node do
  begin
    self.Erase(It);
    inc(result);
    It:=self.FindKey(Key);
  end;
end;

function _TRB_Tree.EraseValue(const Value: _RB_Tree_ValueType): integer;
var
  It: _TRB_TreeIterator;
begin
  result:=0;
  It:=self.FindValue(Value);
  while It.Node<>self.ItEnd.Node do
  begin
    self.Erase(It);
    inc(result);
    It:=self.FindValue(Value);
  end;
end;

function _TRB_Tree.FindKey(const Key: _RB_Tree_KeyType): _TRB_TreeIterator;
begin
  result:=LowerBound(Key);
  if (result.Node=self.FHeader) or
    {$ifdef _DGL_Compare_Key}
    (_IsLess_Key(Key,result.Node.Key))
    {$else}
    (Key<result.Node.Key)
    {$endif}
    then
      result.Node:=_PRB_TreeNode(self.FHeader);
end;

function _TRB_Tree.FindValue(
  const Value: _RB_Tree_ValueType): _TRB_TreeIterator;
var
  iEnd : _TRB_TreeIterator;
begin
  iEnd:=self.ItEnd();
  result:=self.itBegin();
  while (result.Node<>iEnd.Node) do
  begin
    {$ifdef _DGL_Compare_Value}
    if _IsEqual_Value(result.Node.Value,Value) then
    {$else}
    if result.Node.Value=Value then
    {$endif}
      exit
    else
      _TRB_TreeIt_Next(result);
  end;
end;

function _TRB_Tree.GetItemValue(
  const Key: _RB_Tree_KeyType): _RB_Tree_ValueType;
var
  It : _TRB_TreeIterator;
begin
  It:=FindKey(Key);
  if it.Node<>self.FHeader then
    result:=It.Node.Value
  else
    raise ERBTreeKeyRangeError.Create(csRBTreeKey_Error);
end;

function _TRB_Tree.LowerBound(
  const Key: _RB_Tree_KeyType): _TRB_TreeIterator;
var
  x,y : _PRB_TreeNode;
begin
  y := self.FHeader;
  x := self.FHeader.Parent;

  while (x <> nil)  do
  begin
    {$ifdef _DGL_Compare_Key}
    if (not (_IsLess_Key(x.Key,Key))) then
    {$else}
    if (not (x.Key<Key)) then
    {$endif}
    begin
      y := x;
      x := x.Left;
    end
    else
      x := x.Right;
  end;
  result.Node:=y;
end;

function _TRB_Tree.UpperBound(
  const Key: _RB_Tree_KeyType): _TRB_TreeIterator;
var
  x,y: _PRB_TreeNode;
begin
  y := self.FHeader;
  x := self.FHeader.Parent;

  while (x <> nil) do
  begin
    {$ifdef _DGL_Compare_Key}
    if (_IsLess_Key(Key,x.Key)) then
    {$else}
    if ((Key<x.Key)) then
    {$endif}
    begin
      y := x;
      x := x.Left;
    end
    else
      x := x.Right;
  end;
  result.Node:=(y);
end;


procedure _TRB_Tree.Swap(RBTree: _TRB_Tree);
var
  tmpInt     : integer;
  tmpPNode   : _PRB_TreeNode;
begin
  if self=RBTree then exit;

  Assert(F_DGL_OnlySet=RBTree.F_DGL_OnlySet);

  tmpInt:=self.FNodeCount;
  self.FNodeCount:=RBTree.FNodeCount;
  RBTree.FNodeCount:=tmpInt;

  tmpPNode:=self.FHeader;
  self.FHeader:=RBTree.FHeader;
  RBTree.FHeader:=tmpPNode;
end;


 { _TRBTreeBaseIterator }

class procedure _TRBTreeBaseIterator.ItCreate(var SelfItData:_IIterator;const NodeIt:_TRB_TreeIterator);
begin
  SelfItData._ObjIteratorClass:=_TRBTreeBaseIterator;
  _TRB_TreeIterator(SelfItData._Data0):=NodeIt;
end;

class function  _TRBTreeBaseIterator.GetValue(const SelfItData:_IIterator): _ValueType;
begin
  result:=_TRB_TreeIterator(SelfItData._Data0).Node.Value;
end;

class procedure _TRBTreeBaseIterator.SetValue(const SelfItData:_IIterator;const Value: _ValueType);
begin
  _TRB_TreeIterator(SelfItData._Data0).Node.Value:=Value;
end;

class function _TRBTreeBaseIterator.Map_GetKey(const SelfItData:_IIterator): _KeyType;
begin
  result:=_TRB_TreeIterator(SelfItData._Data0).Node.Key;
end;


class function  _TRBTreeBaseIterator.IsEqual(const SelfItData:_IIterator;const Iterator:_IIterator):boolean;
begin
  result:=(SelfItData._Data0=Iterator._Data0);
end;

class procedure _TRBTreeBaseIterator.Next(var SelfItData:_IIterator);
begin
  _TRB_TreeIt_Next(_TRB_TreeIterator(SelfItData._Data0));
end;

class procedure _TRBTreeBaseIterator.Previous(var SelfItData:_IIterator);
begin
  _TRB_TreeIt_Previous(_TRB_TreeIterator(SelfItData._Data0));
end;

class function _TRBTreeBaseIterator.IteratorTraits():TIteratorTraits;
begin
  result:=itBidirectionalTag;
end;


{$endif } // __RB_Tree_inc_pas_