testdeque.pas

在Delphi上实现的数据结构

unit TestDeque;

interface
uses
  Classes, SysUtils,
  TestFramework,
  TestExtensions,

  DGL_Pointer,DGL_String,DGL_Interface,
  _DGL_Object,_DGL_Point;

type
  TTest_Deque = class(TTestCase)
  private
  public
    procedure Setup; override;
    procedure TearDown; override;
  published
    procedure testDeque();
    procedure testIterator();
    procedure testIntfDeque();
    procedure testStrDeque();
    procedure testObjDeque();
    procedure testRecordDeque();
  end;

implementation

{ TTest_Deque }

procedure TTest_Deque.Setup;
begin
  inherited;
end;

procedure TTest_Deque.TearDown;
begin
  inherited;
end;



procedure TTest_Deque.testIntfDeque;
var
    FDeque        : IIntfDeque;
    tmpDeque        : IIntfDeque;
    i : integer;
    tmpIntf : IInterface;
    tmpIntf2 : IInterface;
    It0,It1 :IIntfIterator;
begin
  FDeque :=TIntfDeque.Create();
  Check(FDeque.IsEmpty());

  tmpIntf:=TInterfacedObject.Create();
  FDeque.Insert(FDeque.ItBegin,tmpIntf);
  CheckEquals(FDeque.Size,1);
  Check(FDeque.Back=tmpIntf);

  Check(FDeque.ItBegin.Value=tmpIntf);

  FDeque.Clear();
  Check(FDeque.IsEmpty);

  tmpDeque:=IIntfDeque(FDeque.Clone());
  tmpIntf:=TInterfacedObject.Create();
  tmpDeque.PushBack(tmpIntf);
  Check(FDeque.IsEmpty);
  Check(tmpDeque.ItBegin.Value=tmpIntf);

  tmpIntf:=TInterfacedObject.Create();
  FDeque.PushBack(tmpIntf);
  tmpDeque:=TIntfDeque.Create(FDeque.ItBegin,FDeque.ItEnd);
  Check(tmpDeque.Back=tmpIntf);

  FDeque.Clear();
  for i:=2 to 50 do
    FDeque.PushBack(TInterfacedObject.Create());
  tmpDeque.Clear();
  tmpDeque.PushBack(TInterfacedObject.Create());
  tmpDeque.Insert(tmpDeque.ItBegin,FDeque.ItBegin,FDeque.ItEnd);

  CheckEquals(FDeque.Size,49);
  FDeque.Items[5]:= tmpIntf;
  CheckEquals(FDeque.IndexOf(tmpIntf),5);
  tmpDeque.Items[31]:= tmpIntf;
  CheckEquals(tmpDeque.IndexOf(tmpIntf),31);

  Check(not FDeque.IsEquals(tmpDeque));
  FDeque.Clear();
  FDeque.PushBack(tmpDeque.ItBegin,tmpDeque.ItEnd);
  Check(FDeque.IsEquals(tmpDeque));

  FDeque.Clear();
  for i:=0 to 50-1 do
    FDeque.PushBack(TInterfacedObject.Create());
  FDeque.Items[4]:=tmpIntf;
  FDeque.Items[12]:=tmpIntf;
  FDeque.Items[17]:=tmpIntf;
  CheckEquals(FDeque.EraseValue(tmpIntf),3);
  CheckEquals(FDeque.Size,47);

  //
  tmpIntf:=TInterfacedObject.Create();
  FDeque.PushFront(tmpIntf);
  Check(FDeque.Front=tmpIntf);
  tmpIntf2:=TInterfacedObject.Create();
  FDeque.PushFront(tmpIntf2);
  Check(FDeque.Front=tmpIntf2);
  FDeque.PopFront();
  Check(FDeque.Front=tmpIntf);

  FDeque.Assign(10,tmpIntf);
  CheckEquals(FDeque.size,10);
  Check(FDeque.Items[3]=tmpIntf);
  tmpDeque.Assign(FDeque.ItBegin,FDeque.ItEnd);
  CheckEquals(tmpDeque.size,10);
  Check(tmpDeque.Items[3]=tmpIntf);
  CheckEquals(FDeque.size,10);
  FDeque.Reserve(1000);
  CheckEquals(FDeque.size,10);
  FDeque.Resize(7);
  CheckEquals(FDeque.size,7);

  FDeque.Erase(FDeque.ItBegin,FDeque.ItEnd);
  CheckEquals(FDeque.size,0);
  for i:=0 to 15-1 do
    FDeque.Insert(FDeque.ItEnd,TInterfacedObject.Create());
  It0:=FDeque.ItBegin.Clone(5);
  it1:=FDeque.ItEnd.Clone(-5);
  FDeque.Erase(It0,it1);
  CheckEquals(FDeque.size,10);
  It0:=FDeque.ItBegin.Clone(5);
  FDeque.Erase(It0);
  CheckEquals(FDeque.size,9);

  tmpIntf:=TInterfacedObject.Create();
  It0:=FDeque.ItBegin.Clone(5);
  FDeque.Insert(It0,tmpIntf);
  CheckEquals(FDeque.size,10);
  Check(FDeque.Items[5]=tmpIntf);

  tmpIntf:=TInterfacedObject.Create();
  It0:=FDeque.ItBegin.Clone(5);
  FDeque.Insert(It0,tmpIntf);
  CheckEquals(FDeque.size,11);
  Check(FDeque.Items[5]=tmpIntf);

  //
  tmpIntf:=TInterfacedObject.Create();
  tmpIntf2:=TInterfacedObject.Create();
  FDeque.Clear();
  FDeque.PushFront(3,tmpIntf);
  CheckEquals(FDeque.size,3);
  Check(FDeque.Items[2]=tmpIntf);

  FDeque.PushFront(5,tmpIntf2);
  CheckEquals(FDeque.size,8);
  Check(FDeque.Items[0]=tmpIntf2);
  Check(FDeque.Items[4]=tmpIntf2);
  Check(FDeque.Items[5]=tmpIntf);
  Check(FDeque.Items[7]=tmpIntf);
  //}
end;

procedure TTest_Deque.testIterator;
var
    FDeque        : IPointerDeque;
    i : integer;
    It : IPointerIterator;
    tmpIt : IPointerIterator;
begin
  FDeque :=TPointerDeque.Create(10,Pointer(3));
  CheckEquals(FDeque.size,10);

  CheckEquals(integer(FDeque.items[5]),(3));

  FDeque.Clear();
  for i:=0 to 50-1 do
    FDeque.PushBack(Pointer(i));

  It:=FDeque.ItBegin.Clone(1);
  CheckEquals(integer(It.Value),(1));
  It.Next(4);
  CheckEquals(integer(It.Value),(5));
  CheckEquals(FDeque.ItBegin.Distance(It),(5));
  It:=FDeque.ItEnd;
  It.Previous();
  CheckEquals(integer(It.Value),(49));
  It.Next(-2);
  CheckEquals(integer(It.Value),(47));

  tmpIt:=It.Clone();
  CheckEquals(integer(tmpIt.Value),integer(It.Value));
  Check(tmpIt.IsEqual(It));
  tmpIt.Value:=pointer(integer(It.Value)+1);
  CheckEquals(integer(tmpIt.Value),integer(It.Value));

  tmpIt.Previous;
  CheckNotEquals(integer(tmpIt.Value),integer(It.Value));

  it.Assign(tmpIt);
  CheckEquals(integer(tmpIt.Value),integer(It.Value));
  tmpIt.Previous;
  CheckNotEquals(integer(tmpIt.Value),integer(It.Value));

end;
procedure TTest_Deque.testObjDeque;
var
  ov : IObjDeque;
  ovtmp : IObjDeque;
  it : IObjIterator;
  it0,it1 : IObjIterator;
  ob : TTestObj;
  ob0 : TTestObj;
  i : integer;
begin
  //_refCount:=0; //for test
  
  ov:=TObjDeque.Create(5);
  CheckEquals(_refCount,5);
  ov:=nil;
  CheckEquals(_refCount,0);
  
  ov:=TObjDeque.Create();
  ov.Resize(3000);
  CheckEquals(_refCount,3000);
  ov.CloneToInterface(ovtmp);
  CheckEquals(_refCount,6000);
  it0:=ovtmp.ItBegin; it1:=ovtmp.ItEnd;
  ov.PushBack(it0,it1);
  CheckEquals(_refCount,9000);
  ovtmp:=nil;
  CheckEquals(_refCount,6000);


  it:=ov.ItBegin.Clone(6);
  it0:=ov.ItEnd;
  ov.Erase(it,it0);
  CheckEquals(_refCount,6);
  ov.Clear();
  CheckEquals(_refCount,0);
  
  ob :=TTestObj.Create();
  ov.PushBack(Ob);
  ov.PushBack(Ob);
  ov.PushBack(Ob);
  CheckEquals(_refCount,4);
  FreeAndNil(ob);
  ov.PopBack();
  ov.PopFront();
  CheckEquals(_refCount,1);
  
  ob :=TTestObj.Create();
  it.SetIteratorNil;
  it0.SetIteratorNil;
  it1.SetIteratorNil;
  ov:=TObjDeque.Create(4,ob);
  CheckEquals(ov.Size,4);
  CheckEquals(_refCount,5);

  ob0 :=TTestObj.Create();
  ov.PushBack(ob0);
  ov.PushFront(ob0);
  ov.EraseValue(ob);
  CheckEquals(ov.Size,2);
  CheckEquals(_refCount,4);
  ov.EraseValue(ob0);
  CheckEquals(_refCount,2);

  ov.PushBack(ob);
  ov.PushFront(ob);
  CheckEquals(ov.Items[0].FValue,ob.FValue);
  it:=ov.ItBegin;
  it.Value:=ob0;
  CheckEquals(ov.Items[0].FValue,ob0.FValue);
  FreeAndNil(ob);
  FreeAndNil(ob0);

  ov.resize(10000);
  CheckEquals(_refCount,10000);
  for i:=0 to 10000-1 do
    ov.PopBack();
  CheckEquals(_refCount,0);

  ov.resize(10000);
  for i:=0 to 10000-1 do
    ov.PopFront();
  CheckEquals(_refCount,0);


  ov:=nil;


  //}
end;

procedure TTest_Deque.testDeque;
var
    FDeque        : IPointerDeque;
    tmpDeque        : IPointerDeque;
    i : integer;
    It0,It1:IPointerIterator;
begin
  FDeque :=TPointerDeque.Create();
  Check(FDeque.IsEmpty());

  //FDeque.Clear();
  for i:=2 to 5 do
  begin
    FDeque.PushBack(Pointer(i));
    CheckEquals(integer(FDeque.Front),2);
    CheckEquals(integer(FDeque.Back),i);
  end;
  FDeque.Clear;

  FDeque.Insert(FDeque.ItBegin,pointer(5));
  CheckEquals(FDeque.Size,1);
  Check(FDeque.Back=pointer(5));

  Check(FDeque.ItBegin.Value=pointer(5));
 
  FDeque.Clear();
  Check(FDeque.IsEmpty);

  tmpDeque:=IPointerDeque(FDeque.Clone());
  tmpDeque.PushBack(Pointer(13));
  Check(FDeque.IsEmpty());
  Check(tmpDeque.ItBegin.Value=Pointer(13));


  FDeque.PushBack(Pointer(31));
  tmpDeque:=TPointerDeque.Create(FDeque.ItBegin,FDeque.ItEnd);
  Check(tmpDeque.Back=Pointer(31));
  
  FDeque.Clear();
  for i:=2 to 50 do
    FDeque.PushBack(Pointer(i));

  CheckEquals(integer(FDeque.Front),2);
  CheckEquals(integer(FDeque.Back),50);
  CheckEquals(FDeque.ItBegin.Distance(FDeque.ItEnd),49);

  tmpDeque.Clear();
  tmpDeque.PushBack(Pointer(1));