deque.inc_pas

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

(*
 * DGL(The Delphi Generic Library)
 *
 * Copyright (c) 2004
 * [e-mail]
 *
 * This material is provided "as is", with absolutely no warranty expressed
 * or implied. Any use is at your own risk.
 *
 * Permission to use or copy this software for any purpose is hereby granted
 * without fee, provided the above notices are retained on all copies.
 * Permission to modify the code and to distribute modified code is granted,
 * provided the above notices are retained, and a notice that the code was
 * modified is included with the above copyright notice.
 *
 *)

//------------------------------------------------------------------------------
// _TDeque的实现
// Create by HouSisong, 2004.09.02
//------------------------------------------------------------------------------

{$ifndef  __Deque_inc_pas_}
{$define  __Deque_inc_pas_}              
//Deque.inc_h , Deque.inc_pas

{$I DGLIntf.inc_pas}


{ _TDeque }
const
  csDeultCapability =8;
  
{$ifdef _DGL_ClassFunction_Specific}  //if TValueType=TNotifyEvent then do;
    function _TDeque_Get_ClassFunction_Address(var Value):_PValueType;  {$ifdef _DGL_Inline} inline; {$endif}
    begin
      result:=@Value;
    end;
{$endif}

function  _TDeque.GetSelfObj():TObject;
begin
  result:=self;
end;

function  _TDeque.IsEmpty(): Boolean;
begin
  result:=(self.FFrontPos.PCurValue=self.FEndPos.PCurValue);
end;


function _TDeque.GetBackValue: _ValueType;
var
  PValue : _PValueType;
  FBackPos : _TDequePos;
begin
  Assert(self.FFrontPos.PCurValue<>self.FEndPos.PCurValue);
  PValue:=FEndPos.PCurValue;
  if Pointer(PValue)=Pointer(FEndPos.PPNode^) then
  begin
    FBackPos:=FEndPos;
    _TDeque_DecPos(FBackPos);
    PValue:=FBackPos.PCurValue;
  end
  else
    Dec(PValue);
  result:=PValue^;
end;

procedure _TDeque.SetBackValue(const aValue:_ValueType);
var
  PValue : _PValueType;
  FBackPos : _TDequePos;
begin
  Assert(self.FFrontPos.PCurValue<>self.FEndPos.PCurValue);
  PValue:=FEndPos.PCurValue;
  if Pointer(PValue)=Pointer(FEndPos.PPNode^) then
  begin
    FBackPos:=FEndPos;
    _TDeque_DecPos(FBackPos);
    PValue:=FBackPos.PCurValue;
  end
  else
    Dec(PValue);

  {$ifdef _DGL_ObjValue}
    _Assign(PValue^,aValue);
  {$else}
    PValue^:=aValue;
  {$endif}
end;

{$ifdef  _DGL_ObjValue}
procedure _Deque_Free_ObjValue(ADeque:_TDeque;PBegin,PEnd:_TDequePos);
var
  PValue : _PValueType;
begin
  while (PBegin.PCurValue<>PEnd.PCurValue) do
  begin
    PValue:=(PBegin.PCurValue);
    _Free(PValue^);
    PValue^:=_Null_Value;
    _TDeque_IncPos(PBegin);
  end;
end;
{$endif}

procedure _TDeque.DestroyClear();
var
  i : integer;      
begin
  {$ifdef  _DGL_ObjValue}
    _Deque_Free_ObjValue(self,FFrontPos,FEndPos);
  {$endif}
  for i:=low(FNodeArray) to high(FNodeArray) do
    self.DeleteNode(FNodeArray[i]);
  FNodeArray:=nil;
  self.FFrontPos.PPNode:=nil;
  self.FFrontPos.PCurValue:=nil;
  self.FFrontPos.PEndValue:=nil;
  self.FEndPos.PPNode:=nil;
  self.FEndPos.PCurValue:=nil;
  self.FEndPos.PEndValue:=nil;
end;

procedure _TDeque.Clear;
begin
  DestroyClear();
  setlength(FNodeArray,csDeultCapability);
  self.FFrontPos.PPNode:=@FNodeArray[csDeultCapability shr 1];
  self.FEndPos.PPNode:=self.FFrontPos.PPNode;
end;

procedure _TDeque.Swap(ADeque:_TDeque);
var
  tmpNodeArray  : _TPDequeNodeDArray;
  tmpPos  : _TDequePos;
begin
  if self=ADeque then exit;
  
  tmpNodeArray:=FNodeArray;  FNodeArray:=ADeque.FNodeArray;  ADeque.FNodeArray:=tmpNodeArray;
  tmpPos:=FFrontPos;  FFrontPos:=ADeque.FFrontPos;  ADeque.FFrontPos:=tmpPos;
  tmpPos:=FEndPos;  FEndPos:=ADeque.FEndPos;  ADeque.FEndPos:=tmpPos;
end;



constructor _TDeque.Create(const num: integer; const Value: _ValueType);
begin
  inherited Create();
  Clear();
  self.PushBack(num,Value);
end;

constructor _TDeque.Create(const num: integer);
{$ifdef  _DGL_ObjValue}
var
  _Default_Value : _ValueType;
{$endif}
begin
  inherited Create();
  Clear();
  {$ifdef  _DGL_ObjValue}
    _Default_Value:=_CreateNew();
    self.PushBack(num,_Default_Value);
    _Free(_Default_Value);
  {$else}
    self.PushBack(num,_NULL_Value);
  {$endif}
end;

constructor _TDeque.Create;
begin
  inherited;
  Clear();
end;

procedure _TDeque.Copy(PBegin, PEnd, PDest: _TDequePos);
begin
  while (PBegin.PCurValue<>PEnd.PCurValue) do
  begin
    {$ifdef  _DGL_ObjValue}
      _Assign((PDest.PCurValue)^,(PBegin.PCurValue)^);
    {$else}
      (PDest.PCurValue)^:=(PBegin.PCurValue)^;
    {$endif}
    _TDeque_IncPos(PBegin);
    _TDeque_IncPos(PDest);
  end;
end;

constructor _TDeque.Create(const ADeque: _TDeque);
begin
  inherited Create();
  Clear();
  self.PushBack(ADeque.ItBegin,ADeque.ItEnd);
end;

constructor _TDeque.Create(const ItBegin, ItEnd: _IIterator);
begin
  inherited Create();
  Clear();
  self.PushBack(ItBegin, ItEnd);
end;

procedure _TDeque.Resize(const num: integer; const Value: _ValueType);
var
  i : integer;
  OldCount : integer;
begin
  OldCount:=_TDeque_Distance(FFrontPos,FEndPos);
  if num<OldCount then
  begin
    for i:=num to OldCount-1 do
      PopBack();
  end
  else
  begin
    for i:=OldCount to num-1 do
      PushBack(Value);
  end;
end;

procedure _TDeque.Resize(const num:integer);
{$ifdef  _DGL_ObjValue}
var
  _Default_Value : _ValueType;
{$endif}
begin
  {$ifdef  _DGL_ObjValue}
    _Default_Value:=_CreateNew();
    self.Resize(num,_Default_Value);
    _Free(_Default_Value);
  {$else}
    self.Resize(num,_NULL_Value);
  {$endif}
end;

procedure _TDeque.EraseByIndex(const Index: integer);
begin
  Erase(NewIterator(Index));
end;

procedure _TDeque.InsertByIndex(const Index: Integer;const Value: _ValueType);
begin
  Insert(NewIterator(Index),Value);
end;

class procedure _TDeque.DeleteNode(var pNode: _PDequeNode);
begin
  if pNode<>nil then
  begin
    system.Dispose(_PMemDequeNode(pNode));
    pNode:=nil;
  end;
end;

destructor _TDeque.Destroy;
begin
  self.DestroyClear();
  inherited;
end;

procedure _TDeque.Erase(const ItBegin, ItEnd: _IIterator);
var
  Index: integer;
  BeginPos,EndPos,DestPos : _TDequePos;
  num:integer;
  i : integer;
  EndIndex : integer;
  OldCount : integer;
begin
  Index:=_TDeque_Distance(self.FFrontPos,_PDequeIt(@ItBegin).Pos);
  EndIndex:=_TDeque_Distance(self.FFrontPos,_PDequeIt(@ItEnd).Pos);
  num:=ItBegin.Distance(ItEnd);
  if num<=0 then exit;

  OldCount:=_TDeque_Distance(FFrontPos,FEndPos);
  if Index=0 then
  begin
    for i:=0 to num-1 do self.PopFront();
  end
  else if (EndIndex)=OldCount then
  begin
    for i:=0 to num-1 do self.PopBack();
  end
  else
  begin
    if Index+(num  div 2)>=OldCount div 2 then
    begin
      DestPos:=self.GetPos(Index);
      BeginPos:=DestPos;
      _TDeque_IncPos(BeginPos,num);
      self.Copy(BeginPos,FEndPos,DestPos);
      for i:=0 to num-1 do self.PopBack();
    end
    else
    begin
      EndPos:=self.GetPos(Index);
      DestPos:= self.FFrontPos;
      _TDeque_IncPos(DestPos,num);
      self.ReCopy(FFrontPos,EndPos,DestPos);
      for i:=0 to num-1 do self.PopFront();
    end;
  end;
end;

procedure _TDeque.Erase(const ItPos: _IIterator);
var
  ItEnd : _IIterator;
begin
  ItEnd:=ItPos.Clone;
  ItEnd.Next;
  Erase(ItPos,ItEnd);
end;

procedure _TDeque.Fill(PBegin, PEnd: _TDequePos; const Value: _ValueType);
begin
  while (PBegin.PCurValue<>PEnd.PCurValue) do
  begin
    {$ifdef  _DGL_ObjValue}
    _Assign((PBegin.PCurValue)^,Value);
    {$else}
    (PBegin.PCurValue)^:=Value;
    {$endif}
    _TDeque_IncPos(PBegin);
  end;
end;

function _TDeque.ItBegin: _IIterator;
begin
  _TDequeIterator.ItCreate(result,FFrontPos);
end;

function  _TDeque.NewIterator(const Index: Integer):_IIterator;
begin
  _TDequeIterator.ItCreate(result,self,Index);
end;

function _TDeque.GetFrontValue: _ValueType;
begin
  Assert(self.FFrontPos.PCurValue<>self.FEndPos.PCurValue);
  result:=(FFrontPos.PCurValue)^;
end;

procedure _TDeque.SetFrontValue(const aValue:_ValueType);
begin
  Assert(self.FFrontPos.PCurValue<>self.FEndPos.PCurValue);
  {$ifdef _DGL_ObjValue}
    _Assign((FFrontPos.PCurValue)^,aValue);
  {$else}
    (FFrontPos.PCurValue)^:=aValue;
  {$endif}
end;

function _TDeque.GetItemValue(const Index: Integer): _ValueType;
begin
  Assert(Index>=0);
  Assert(Index<_TDeque_Distance(FFrontPos,FEndPos));
  result:=self.GetAItemAddress(Index)^;
end;

function _TDeque.GetPos(const Index: integer): _TDequePos;
begin
  result:=FFrontPos;
  _TDeque_IncPos(result,Index);
end;

function _TDeque.GetAItemAddress(const ItemIndex:integer): _PValueType;
var
  ValueIndex,NodeCount:integer;
  ppNode : _PPDequeNode;
begin
  ValueIndex:=ItemIndex+(csDequeNodeCount) + (integer(FFrontPos.PCurValue)-integer(FFrontPos.PEndValue)) div (sizeof(_ValueType));
  NodeCount:=ValueIndex div csDequeNodeCount;
  ppNode:=_PPDequeNode(integer(FFrontPos.PPNode)+NodeCount*sizeof(_PPDequeNode));
  ValueIndex:=ValueIndex-NodeCount*csDequeNodeCount;
  result:={$ifdef _DGL_ClassFunction_Specific}_TDeque_Get_ClassFunction_Address{$else}@{$endif}(ppNode^[ValueIndex]);
end;

function _TDeque.IndexOf(const Value: _ValueType): Integer;
var
  i : integer;
  Pos : _TDequePos;
  OldCount : integer;
begin
  Pos:=self.FFrontPos;
  OldCount:=_TDeque_Distance(FFrontPos,FEndPos);
  for i:=0 to OldCount-1 do
  begin
    {$ifdef  _DGL_Compare}
      if (_IsEqual(Value,(Pos.PCurValue)^)) then
    {$else}
      if Value=(Pos.PCurValue)^ then
    {$endif}
    begin
      result:=i;
      exit;
    end;
    _TDeque_IncPos(Pos);
  end;
  result:=-1;
end;

procedure _TDeque.Insert(const ItPos: _IIterator; const Value: _ValueType);
var
  Index: integer;
begin
  Index:=_TDeque_Distance(self.FFrontPos,_PDequeIt(@ItPos).Pos);
  if Index=0 then
    self.PushFront(Value)
  else if (Index>=_TDeque_Distance(FFrontPos,FEndPos)) then
    self.PushBack(Value)
  else
    Insert(ItPos,1,Value);
end;

procedure _TDeque.Insert(const Value:_ValueType);
begin
  self.PushBack(Value);
end;

procedure _TDeque.Insert(const ItPos: _IIterator; const num: integer;
  const Value: _ValueType);
var
  Index: integer;
begin
  if num<=0 then exit;
  
  Index:=_TDeque_Distance(self.FFrontPos,_PDequeIt(@ItPos).Pos);
  if Index=0 then
    self.PushFront(num,Value)
  else if (Index>=_TDeque_Distance(FFrontPos,FEndPos)) then
    self.PushBack(num,Value)
  else