testalgorithms.pas

在Delphi上实现的数据结构

  TIntAlgorithms.RandomShuffle(IntVector.ItBegin,IntVector.ItEnd);
  IntVector1 :=TIntVector.Create(IntVector.Size);
  TIntAlgorithms.Copy(IntVector.ItBegin,IntVector.ItEnd,IntVector1.ItBegin);
  CheckEquals(True,TIntAlgorithms.IsEquals(IntVector.ItBegin,IntVector.ItEnd,IntVector1.ItBegin,IntVector1.ItEnd));

  //Tansfrom
  IntVector :=TIntVector.Create();
  for i:=0 to num-1 do
      IntVector.PushBack(i);
  TIntAlgorithms.Tansfrom(IntVector.ItBegin,IntVector.ItEnd,self.TansfromAdd1);
  FSumCount:=0;
  TIntAlgorithms.ForEach(IntVector.ItBegin,IntVector.ItEnd,self.SumCount);
  CheckEquals(FSumCount-num,(0+(num-1))*num div 2);
  TIntAlgorithms.Tansfrom(IntVector.ItBegin,IntVector.ItEnd,gpTansfromAdd1);
  FSumCount:=0;
  TIntAlgorithms.ForEach(IntVector.ItBegin,IntVector.ItEnd,self.SumCount);
  CheckEquals(FSumCount-num*2,(0+(num-1))*num div 2);
 
  //Tansfrom to
  IntVector :=TIntVector.Create();
  for i:=0 to num-1 do
      IntVector.PushBack(i);
  IntVector1 :=TIntVector.Create(IntVector.Size);
  TIntAlgorithms.Tansfrom(IntVector.ItBegin,IntVector.ItEnd,IntVector1.ItBegin,self.TansfromAdd1);
  FSumCount:=0;
  TIntAlgorithms.ForEach(IntVector1.ItBegin,IntVector1.ItEnd,self.SumCount);
  CheckEquals(FSumCount-num,(0+(num-1))*num div 2);
  TIntAlgorithms.Tansfrom(IntVector.ItBegin,IntVector.ItEnd,IntVector1.ItBegin,gpTansfromAdd1);
  FSumCount:=0;
  TIntAlgorithms.ForEach(IntVector1.ItBegin,IntVector1.ItEnd,self.SumCount);
  CheckEquals(FSumCount-num,(0+(num-1))*num div 2);

  //Tansfrom 2 to 1
  IntVector :=TIntVector.Create();
  for i:=0 to num-1 do
      IntVector.PushBack(i);
  IntVector1 :=TIntVector.Create(IntVector.ItBegin,IntVector.ItEnd);
  TIntAlgorithms.Tansfrom(IntVector1.ItBegin,IntVector1.ItEnd,self.TansfromAdd1);
  IntVector2:=TIntVector.Create(IntVector.Size);

  TIntAlgorithms.Tansfrom(IntVector.ItBegin,IntVector.ItEnd,IntVector1.ItBegin,IntVector2.ItBegin,self.TansfromAdd);
  FSumCount:=0;
  TIntAlgorithms.ForEach(IntVector2.ItBegin,IntVector2.ItEnd,self.SumCount);
  CheckEquals((FSumCount-num) div 2,(0+(num-1))*num div 2);
  TIntAlgorithms.Tansfrom(IntVector1.ItBegin,IntVector1.ItEnd,IntVector1.ItBegin,IntVector2.ItBegin,gpTansfromAdd);
  FSumCount:=0;
  TIntAlgorithms.ForEach(IntVector2.ItBegin,IntVector2.ItEnd,self.SumCount);
  CheckEquals((FSumCount-num*2) div 2,(0+(num-1))*num div 2);


  //SwapRanges
  IntVector :=TIntVector.Create();
  for i:=0 to num-1 do
      IntVector.PushBack(i);
  IntVector1 :=TIntVector.Create(IntVector.ItBegin,IntVector.ItEnd);
  TIntAlgorithms.Tansfrom(IntVector1.ItBegin,IntVector1.ItEnd,self.TansfromAdd1);
  TIntAlgorithms.SwapRanges(IntVector.ItBegin,IntVector.ItEnd,IntVector1.ItBegin);
  FSumCount:=0;
  TIntAlgorithms.ForEach(IntVector.ItBegin,IntVector.ItEnd,self.SumCount);
  CheckEquals((FSumCount-num),(0+(num-1))*num div 2);
   //}
end;

function TTest_Algorithms.Get10():integer;
begin
  result:=10;
end;

function gpGet11():integer;
begin
  result:=11;
end;

procedure TTest_Algorithms.testAlgorithms3;
const
  num = 100;
var
  IntVector : IIntVector;
  IntVector1,IntVector2 : IIntVector;
  it,it1 :IIntIterator;
  i,j: integer;
begin
  //test Replace\Fill\Generate\Remove

  //Replace
  IntVector :=TIntVector.Create();
  for i:=0 to num-1 do
      IntVector.PushBack(i mod 10);
  CheckEquals(num div 10,TIntAlgorithms.Count(IntVector.ItBegin,IntVector.ItEnd,3));
  TIntAlgorithms.Replace(IntVector.ItBegin,IntVector.ItEnd,3,5);
  CheckEquals(0,TIntAlgorithms.Count(IntVector.ItBegin,IntVector.ItEnd,3));
  CheckEquals((num div 10)*2,TIntAlgorithms.Count(IntVector.ItBegin,IntVector.ItEnd,5));

  //Replace if
  IntVector :=TIntVector.Create();
  for i:=0 to num-1 do
      IntVector.PushBack(i mod 10);
  FFindIfValue:=5;
  TIntAlgorithms.ReplaceIf(IntVector.ItBegin,IntVector.ItEnd,self.FindIf1b,7);
  CheckEquals(0,TIntAlgorithms.Count(IntVector.ItBegin,IntVector.ItEnd,5));
  CheckEquals((num div 10)*2,TIntAlgorithms.Count(IntVector.ItBegin,IntVector.ItEnd,7));
  IntVector :=TIntVector.Create();
  for i:=0 to num-1 do
      IntVector.PushBack(i mod 10);
  gFindIfValue:=9;
  TIntAlgorithms.ReplaceIf(IntVector.ItBegin,IntVector.ItEnd,gpFindIf1b,7);
  CheckEquals(0,TIntAlgorithms.Count(IntVector.ItBegin,IntVector.ItEnd,9));
  CheckEquals((num div 10)*2,TIntAlgorithms.Count(IntVector.ItBegin,IntVector.ItEnd,7));

  //Fill
  IntVector :=TIntVector.Create(num);
  TIntAlgorithms.Fill(IntVector.ItBegin,IntVector.ItEnd,5);
  FSumCount:=0;
  TIntAlgorithms.ForEach(IntVector.ItBegin,IntVector.ItEnd,self.SumCount);
  CheckEquals(FSumCount,(num*5));
  TIntAlgorithms.Fill(IntVector.ItBegin,num,7);
  FSumCount:=0;
  TIntAlgorithms.ForEach(IntVector.ItBegin,IntVector.ItEnd,self.SumCount);
  CheckEquals(FSumCount,(num*7));

  //Generate
  IntVector :=TIntVector.Create(num);
  TIntAlgorithms.Generate(IntVector.ItBegin,IntVector.ItEnd,self.Get10);
  FSumCount:=0;
  TIntAlgorithms.ForEach(IntVector.ItBegin,IntVector.ItEnd,self.SumCount);
  CheckEquals(FSumCount,(num*10));
  TIntAlgorithms.Generate(IntVector.ItBegin,IntVector.ItEnd,gpGet11);
  FSumCount:=0;
  TIntAlgorithms.ForEach(IntVector.ItBegin,IntVector.ItEnd,self.SumCount);
  CheckEquals(FSumCount,(num*11));
  TIntAlgorithms.Generate(IntVector.ItBegin,num,self.Get10);
  FSumCount:=0;
  TIntAlgorithms.ForEach(IntVector.ItBegin,IntVector.ItEnd,self.SumCount);
  CheckEquals(FSumCount,(num*10));
  TIntAlgorithms.Generate(IntVector.ItBegin,num,gpGet11);
  FSumCount:=0;
  TIntAlgorithms.ForEach(IntVector.ItBegin,IntVector.ItEnd,self.SumCount);
  CheckEquals(FSumCount,(num*11));

  //Remove
  IntVector :=TIntVector.Create();
  for i:=0 to num-1 do
      IntVector.PushBack(i mod 4);
  TIntAlgorithms.RandomShuffle(IntVector.ItBegin,IntVector.ItEnd);
  it:=TIntAlgorithms.Remove(IntVector.ItBegin,IntVector.ItEnd,2);
  FSumCount:=0;
  TIntAlgorithms.ForEach(IntVector.ItBegin,It,self.SumCount);
  CheckEquals(FSumCount,(num div 4)*(1+3));
  CheckEquals(num,IntVector.Size);

  //Remove if
  IntVector :=TIntVector.Create();
  for i:=0 to num-1 do
      IntVector.PushBack(i mod 10);
  TIntAlgorithms.RandomShuffle(IntVector.ItBegin,IntVector.ItEnd);
  FFindIfValue:=3;
  it:=TIntAlgorithms.RemoveIf(IntVector.ItBegin,IntVector.ItEnd,self.FindIf1b);
  gFindIfValue:=8;
  it:=TIntAlgorithms.RemoveIf(IntVector.ItBegin,it,gpFindIf1b);
  FSumCount:=0;
  TIntAlgorithms.ForEach(IntVector.ItBegin,It,self.SumCount);
  CheckEquals(FSumCount,(num div 10)*(1+2+4+5+6+7+9));
  CheckEquals(num,IntVector.Size);

end;


var
  datas : array [0..9] of integer=(9,8,7,6,5,4,3,2,1,0);

procedure TTest_Algorithms.testAlgorithms4;
const
  num = 100;
var
  IntVector : IIntVector;
  IntVector1,IntVector2 : IIntVector;
  it,it1 :IIntIterator;
  i,j: integer;
begin
  //test: Reverse\RandomShuffle\Sort\IsSorted

  //Reverse
  IntVector :=TIntVector.Create();
  for i:=0 to num-1 do
      IntVector.PushBack(i);
  TIntAlgorithms.Reverse(IntVector.ItBegin,IntVector.ItEnd);
  for i:=0 to num-1 do
    CheckEquals(num-1-i,IntVector.Items[i]);

  //RandomShuffle
  TIntAlgorithms.RandomShuffle(DGL_integer.PointerBox(@datas[0]),DGL_integer.PointerBox(@datas[0],length(datas)));
  TIntAlgorithms.Sort(DGL_integer.PointerBox(@datas[0]),DGL_integer.PointerBox(@datas[0],length(datas)));
  TIntAlgorithms.RandomShuffle(DGL_integer.PointerBox(@datas[0]),
    DGL_integer.PointerBox(@datas[0],length(datas)),self.RandomGenerate);
  TIntAlgorithms.Sort(DGL_integer.PointerBox(@datas[0]),DGL_integer.PointerBox(@datas[0],length(datas)));
  TIntAlgorithms.RandomShuffle(DGL_integer.PointerBox(@datas[0]),
    DGL_integer.PointerBox(@datas[0],length(datas)),gpRandomGenerate);

  
  //Sort , IsSorted
  TIntAlgorithms.RandomShuffle(DGL_integer.PointerBox(@datas[0]),DGL_integer.PointerBox(@datas[0],length(datas)));
  TIntAlgorithms.Sort(DGL_integer.PointerBox(@datas[0]),DGL_integer.PointerBox(@datas[0],length(datas)));
  //TIntAlgorithms.Sort(@datas[0],@DGL_integer._PValueType_Iterator(@datas[0])[length(datas)]);
  CheckEquals(true,TIntAlgorithms.IsSorted(DGL_integer.PointerBox(@datas[0]),DGL_integer.PointerBox(@datas[0],length(datas))));
   TIntAlgorithms.RandomShuffle(DGL_integer.PointerBox(@datas[0]),DGL_integer.PointerBox(@datas[0],length(datas)));
  TIntAlgorithms.Sort(DGL_integer.PointerBox(@datas[0]),DGL_integer.PointerBox(@datas[0],length(datas)),self.great);
  CheckEquals(true,TIntAlgorithms.IsSorted(DGL_integer.PointerBox(@datas[0]),DGL_integer.PointerBox(@datas[0],length(datas)),self.great));
  CheckEquals(false,TIntAlgorithms.IsSorted(DGL_integer.PointerBox(@datas[0]),DGL_integer.PointerBox(@datas[0],length(datas)),gpLess));
  TIntAlgorithms.RandomShuffle(DGL_integer.PointerBox(@datas[0]),DGL_integer.PointerBox(@datas[0],length(datas)));
  TIntAlgorithms.Sort(DGL_integer.PointerBox(@datas[0]),DGL_integer.PointerBox(@datas[0],length(datas)),gpLess);
  CheckEquals(true,TIntAlgorithms.IsSorted(DGL_integer.PointerBox(@datas[0]),DGL_integer.PointerBox(@datas[0],length(datas)),gpLess));
  
  //SortHeap ...
  TIntAlgorithms.RandomShuffle(DGL_integer.PointerBox(@datas[0]),DGL_integer.PointerBox(@datas[0],length(datas)));
  TIntAlgorithms.SortHeap(DGL_integer.PointerBox(@datas[0]),DGL_integer.PointerBox(@datas[0],length(datas)));
  CheckEquals(true,TIntAlgorithms.IsSorted(DGL_integer.PointerBox(@datas[0]),DGL_integer.PointerBox(@datas[0],length(datas))));
  TIntAlgorithms.RandomShuffle(DGL_integer.PointerBox(@datas[0]),DGL_integer.PointerBox(@datas[0],length(datas)));
  TIntAlgorithms.SortHeap(DGL_integer.PointerBox(@datas[0]),DGL_integer.PointerBox(@datas[0],length(datas)),self.great);
  CheckEquals(true,TIntAlgorithms.IsSorted(DGL_integer.PointerBox(@datas[0]),DGL_integer.PointerBox(@datas[0],length(datas)),self.great));
  CheckEquals(false,TIntAlgorithms.IsSorted(DGL_integer.PointerBox(@datas[0]),DGL_integer.PointerBox(@datas[0],length(datas)),gpLess));
  TIntAlgorithms.RandomShuffle(DGL_integer.PointerBox(@datas[0]),DGL_integer.PointerBox(@datas[0],length(datas)));
  TIntAlgorithms.SortHeap(DGL_integer.PointerBox(@datas[0]),DGL_integer.PointerBox(@datas[0],length(datas)),gpLess);
  CheckEquals(true,TIntAlgorithms.IsSorted(DGL_integer.PointerBox(@datas[0]),DGL_integer.PointerBox(@datas[0],length(datas)),gpLess));

    //}
end;

function TTest_Algorithms.great(const x0, x1: integer): boolean;
begin
  result:=x0>x1;
end;

procedure TTest_Algorithms.testAlgorithms5;
const
  num = 100;
var
  IntVector : IIntVector;
  IntVector1,IntVector2 : IIntVector;
  it,it1 :IIntIterator;
  i,j: integer;
begin
  //test: BinarySearch\LowerBound

  //BinarySearch
  IntVector :=TIntVector.Create();
  for i:=0 to num-1 do
    for j:=0 to 10-1 do
      IntVector.PushBack(i);
  CheckEquals(true,TIntAlgorithms.IsSorted(IntVector.ItBegin,IntVector.ItEnd));
  it:=TIntAlgorithms.BinarySearch(IntVector.ItBegin,IntVector.ItEnd,17,gpLess);
  CheckEquals(17,it.Value);
  it:=TIntAlgorithms.BinarySearch(IntVector.ItBegin,IntVector.ItEnd,num+1);
  CheckEquals(true,it.IsEqual(IntVector.ItEnd));

  //BinarySearch .
  TIntAlgorithms.Sort(IntVector.ItBegin,IntVector.ItEnd,self.great);
  it:=TIntAlgorithms.BinarySearch(IntVector.ItBegin,IntVector.ItEnd,21,self.great);
  CheckEquals(21,it.Value);
  IntVector.EraseValue(21);
  it:=TIntAlgorithms.BinarySearch(IntVector.ItBegin,IntVector.ItEnd,21,self.great);
  CheckEquals(true,it.IsEqual(IntVector.ItEnd));
  it:=TIntAlgorithms.BinarySearch(IntVector.ItBegin,IntVector.ItEnd,num+1,self.great);
  CheckEquals(true,it.IsEqual(IntVector.ItEnd));

  //LowerBound
  IntVector :=TIntVector.Create();
  for i:=0 to num-1 do
    for j:=0 to 10-1 do
      IntVector.PushBack(i);
  TIntAlgorithms.Sort(IntVector.ItBegin,IntVector.ItEnd);
  it:=TIntAlgorithms.LowerBound(IntVector.ItBegin,IntVector.ItEnd,35);
  CheckEquals(35,it.Value);
  CheckEquals(35,it.Clone(10-1).Value);
  CheckEquals(34,it.Clone(-1).Value);
  CheckEquals(36,it.Clone(10).Value);
  IntVector.EraseValue(35);
  it:=TIntAlgorithms.LowerBound(IntVector.ItBegin,IntVector.ItEnd,35,self.Less);
  CheckEquals(36,it.Value);
  CheckEquals(36,it.Clone(10-1).Value);
  CheckEquals(34,it.Clone(-1).Value);
  CheckEquals(37,it.Clone(10).Value);
  it:=TIntAlgorithms.LowerBound(IntVector.ItBegin,IntVector.ItEnd,num+1);
  CheckEquals(true,it.IsEqual(IntVector.ItEnd));
  it:=TIntAlgorithms.LowerBound(IntVector.ItBegin,IntVector.ItEnd,-1,gpLess);
  CheckEquals(true,it.IsEqual(IntVector.ItBegin));

end;

initialization
  RegisterTest(TTest_Algorithms.Suite);
end.