_testrbtree.pas

delphi的范型代码库

unit _TestRBTree;

interface
uses
  Classes, SysUtils,
  TestFramework,
  TestExtensions,
  _RB_Tree;

type

  TTest_RBTree = class(TTestCase)
  public
    procedure Setup; override;
    procedure TearDown; override;
  published
    procedure testRBTree();
    procedure testRBTreeIterator();
    procedure testMultiRBTree();
  end;

implementation

{ TTest_RBTree }

procedure TTest_RBTree.Setup;
begin
  inherited;

end;

procedure TTest_RBTree.TearDown;
begin
  inherited;

end;

procedure TTest_RBTree.testMultiRBTree;
  function GetStr(const c:_TRB_Tree):string;
  var
    it,itEnd: _TRB_TreeIterator;
  begin
    it:=c.ItBegin;
    itEnd:=c.ItEnd;
    result:='';
    while not (it.Node=itEnd.Node) do begin
      //result := result+inttostr((it.Value))+' ';
      result := result+((it.Key))+' ';
      it.Next();
    end;
  end;
var
  st  : _TRB_Tree;
  it : _TRB_TreeIterator;
  i : integer;
begin
  st:=_TRB_Tree.Create(false);

  CheckEquals(st.Size,0);
  for i:=0 to 10000-1 do
    st.MultiInsert(inttostr(i div 10),((i div 10)*3+1));
  CheckEquals(st.Size,10000);

  it:=st.ItBegin() ;
  for i:=0 to st.Size-1 do
  begin
    CheckEquals(StrToInt(it.Key)*3+1,(it.Value));
    it.Next();
  end;

  st.Clear();

  for i:=0 to 1000-1 do
    st.MultiInsert(inttostr(i div 3),((i div 7)*3+1));

  i:=st.Size();
  CheckEquals(1000,i);


  CheckEquals(st.Count(inttostr(8)),3);


  it:=st.FindKey(inttostr(8));
  st.Erase(it);
  CheckEquals(st.Count(inttostr(8)),2);
  CheckEquals(st.Size,i-1);

  CheckEquals(st.EraseValue((12*3+1)),7);
  CheckEquals(st.EraseValue((12*3+1)),0);

  st:=_TRB_Tree.Create(false);
  for i:=0 to 1000-1 do
    st.MultiInsert(inttostr(i),((i div 11)*7+1));
  CheckEquals(st.EraseValue((25*7+1)),11);
  //}

end;

procedure TTest_RBTree.testRBTree;
var
  st  : _TRB_Tree;
  it : _TRB_TreeIterator;
  i : integer;
begin
  st:=_TRB_Tree.Create(false);
  CheckEquals(st.Size,0);

  for i:=0 to 10000-1 do
    st.UniqueInsert(inttostr(i div 10),((i div 10)*3+1));
  CheckEquals(st.Size,10000 div 10);

  it:=st.ItBegin() ;
  for i:=0 to st.Size-1 do
  begin
    CheckEquals(StrToInt(it.Key)*3+1,(it.Value));
    it.Next();
  end;

  st.Clear();
  for i:=0 to 1000-1 do
    st.UniqueInsert(inttostr(i div 3),((i div 7)*3+1));

  i:=st.Size();
  CheckEquals(((1000-1) div 3)+1,i);

  CheckEquals(st.Count(inttostr(8)),1);
 
  it:=st.FindKey(inttostr(8));
  st.Erase(it);
  CheckEquals(st.Count(inttostr(8)),0);
  CheckEquals(st.Size,i-1);

  st.EraseValue((12*3+1));
  CheckEquals(st.EraseValue((12*3+1)),0);

  st:=_TRB_Tree.Create(false);
  for i:=0 to 1000-1 do
    st.UniqueInsert(inttostr(i),((i div 11)*7+1));
  CheckEquals(st.EraseValue((25*7+1)),11);
 //}
end;

procedure TTest_RBTree.testRBTreeIterator;
var
    st  : _TRB_Tree;
    i   : integer;
    It0,It1   : _TRB_TreeIterator;

begin
  st :=_TRB_Tree.Create(false);
  CheckEquals(st.size,0);

  st.MultiInsert(inttostr(7),(7*7));
  st.MultiInsert(inttostr(13),(13*13));

  it0:=st.ItBegin();
  it1:=st.ItEnd();
  //CheckEquals(It0.Distance(It1),2);
  it1.Previous();
  CheckEquals((It0.Value)+(It1.Value),7*7+13*13);

  it0:=st.ItBegin();
  it1:=st.ItEnd();
  it0.Next();
  it0.Next();
  it1.Previous();
  it1.Previous();
  //CheckEquals(It1.Distance(It0),2);
  it0.Previous();
  CheckEquals((It0.Value)-(It1.Value),7*7-13*13);
  CheckEquals(StrToInt(It0.Key)*StrToInt(It1.Key),7*13);

  st.Clear();
  for i:=0 to 10000 do
    st.MultiInsert(inttostr(i div 37),(i*i));
  st.EqualRange(inttostr(25),It0,It1);
 // CheckEquals(It0.Distance(It1),37);
 { it0.Next(20);
  it1.Next(-7-8);
  CheckEquals(It0.Distance(It1),2);
  st.Erase(it0,it1); //}
end;

initialization
  RegisterTest(TTest_RBTree.Suite);
end.