deque.inc_pas

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

  result:=( (integer(EndPos.PPNode)-integer(BeginPos.PPNode) ) div (sizeof(_PPDequeNode)))*csDequeNodeCount
          +( (integer(EndPos.PCurValue)-integer(EndPos.PPNode^))
            -(integer(BeginPos.PCurValue)-integer(BeginPos.PPNode^)) )  div sizeof(_ValueType) ;
end;

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

procedure _TDeque.ExtendCapabilityFront;
var
  i : integer;
  L : integer;
  dL : integer;
  aPPNode : _PPDequeNode;
  OldBeginPPNode : _PPDequeNode;
  OldFrontIndex,OldEndIndex : integer;
begin
  OldBeginPPNode:=@FNodeArray[0];
  if longword(self.FFrontPos.PPNode)>longword(OldBeginPPNode) then
  begin
    aPPNode:=self.FFrontPos.PPNode;
    if aPPNode^=nil then   //new node
      aPPNode^:=self.NewNode();
    dec(aPPNode);
    if aPPNode^=nil then   //new node
      aPPNode^:=self.NewNode();
  end
  else
  begin
    OldFrontIndex:=longword(integer(self.FFrontPos.PPNode)-integer(OldBeginPPNode)) div sizeof(_PPDequeNode);
    OldEndIndex:=longword(integer(self.FEndPos.PPNode)-integer(OldBeginPPNode)) div sizeof(_PPDequeNode);

    L:=length(self.FNodeArray);
    Assert(L>=4);

    dL:=(L shr 2) + csDeultCapability;
    setlength(self.FNodeArray,L+dL);
    for i:=L-1 downto 0 do
      FNodeArray[i+dL]:=FNodeArray[i];
    for i:=0 to dL-1 do
      FNodeArray[i]:=nil;

    FNodeArray[dL-1]:=self.NewNode();

    self.FFrontPos.PPNode:=@FNodeArray[OldFrontIndex+dL];
    self.FEndPos.PPNode:=@FNodeArray[OldEndIndex+dL];
    Assert(FNodeArray[OldEndIndex+dL+1]=nil);
  end;

  if self.FFrontPos.PCurValue=nil then
  begin
    Assert(self.FFrontPos.PEndValue=nil);
    Assert(self.FEndPos.PCurValue=nil);
    self.FFrontPos.PCurValue:={$ifdef _DGL_ClassFunction_Specific}_TDeque_Get_ClassFunction_Address{$else}@{$endif}(self.FFrontPos.PPNode^[csDequeNodeCount shr 1]);
    self.FFrontPos.PEndValue:={$ifdef _DGL_ClassFunction_Specific}_TDeque_Get_ClassFunction_Address{$else}@{$endif}(self.FFrontPos.PPNode^[csDequeNodeCount]);
    self.FEndPos:=self.FFrontPos;
  end;
end;

procedure _TDeque.ExtendCapabilityBack;
var
  L : integer;
  dL : integer;
  aPPNode,aTmpPPNode :_PPDequeNode;
  OldBeginPPNode : _PPDequeNode;
  OldFrontIndex,OldEndIndex : integer;
begin

  if (self.FFrontPos.PCurValue=nil)then
    self.ExtendCapabilityFront();

  L:=length(self.FNodeArray);
  Assert(self.FEndPos.PPNode<>nil);

  if longword(self.FEndPos.PPNode)+sizeof(_PPDequeNode)<longword(@FNodeArray[L-1]) then
  begin
    aPPNode:=self.FEndPos.PPNode;
    if aPPNode^=nil then
    begin
      aTmpPPNode:=aPPNode;
      inc(aTmpPPNode);
      if (aTmpPPNode^<>nil) then
      begin  //swap node
        aPPNode^:=aTmpPPNode^;
        aTmpPPNode^:=nil;
      end
      else  //new node
        aPPNode^:=self.NewNode();
    end
    else
    begin
      inc(aPPNode);
      Assert(aPPNode^=nil);
      aPPNode^:=self.NewNode();
    end;
  end
  else
  begin
    OldBeginPPNode:=@FNodeArray[0];
    OldFrontIndex:=longword(integer(self.FFrontPos.PPNode)-integer(OldBeginPPNode)) div sizeof(_PPDequeNode);
    OldEndIndex:=longword(integer(self.FEndPos.PPNode)-integer(OldBeginPPNode)) div sizeof(_PPDequeNode);

    dL:=(L shr 2) + csDeultCapability;
    setlength(self.FNodeArray,L + dL);

    self.FFrontPos.PPNode:=@FNodeArray[OldFrontIndex];
    self.FEndPos.PPNode:=@FNodeArray[OldEndIndex];

    aPPNode:=self.FEndPos.PPNode;
    if aPPNode^=nil then
      aPPNode^:=self.NewNode()
    else
    begin
      inc(aPPNode);
      Assert(aPPNode^=nil);
      aPPNode^:=self.NewNode();
    end;
  end;

  Assert(self.FFrontPos.PCurValue<>nil);
  if FEndPos.PCurValue=nil then
  begin
    Assert(self.FEndPos.PPNode^<>nil);
    Assert(self.FEndPos.PEndValue=nil);
    self.FEndPos.PCurValue:={$ifdef _DGL_ClassFunction_Specific}_TDeque_Get_ClassFunction_Address{$else}@{$endif}(self.FEndPos.PPNode^[0]);
    self.FEndPos.PEndValue:={$ifdef _DGL_ClassFunction_Specific}_TDeque_Get_ClassFunction_Address{$else}@{$endif}(self.FEndPos.PPNode^[csDequeNodeCount]);
  end;
end;

procedure _TDeque.ReduceCapabilityFront;
var
  i : integer;
  L : integer;
  DelCount : integer;
  OldBeginPPNode : _PPDequeNode;
  OldFrontIndex,OldEndIndex : integer;
begin
  L:=length(self.FNodeArray);
  OldBeginPPNode:=@FNodeArray[0];
  OldFrontIndex:=longword(integer(self.FFrontPos.PPNode)-integer(OldBeginPPNode)) div sizeof(_PPDequeNode);
  
  if OldFrontIndex>=2 then  
  begin
    self.DeleteNode(FNodeArray[OldFrontIndex-2]);//hold 1 empty node: FNodeArray[OldFrontIndex-1] ;

    DelCount:=OldFrontIndex-2-(csDeultCapability shr 1);
    if DelCount*3>L then
    begin
      OldEndIndex:=longword(integer(self.FEndPos.PPNode)-integer(OldBeginPPNode)) div sizeof(_PPDequeNode);
      for i:=0 to L-DelCount-1 do
        FNodeArray[i]:=FNodeArray[i+DelCount];
      //for i:=L-DelCount to L-1 do
      //  FNodeArray[i]:=nil;
      setlength(self.FNodeArray,L-DelCount);

      self.FFrontPos.PPNode:=@FNodeArray[OldFrontIndex-DelCount];
      self.FEndPos.PPNode:=@FNodeArray[OldEndIndex-DelCount];
    end;
  end;
end;

procedure _TDeque.ReduceCapabilityBack;
var
  L : integer;
  DelCount : integer;
  OldBeginPPNode : _PPDequeNode;
  OldFrontIndex,OldEndIndex : integer;
begin
  OldBeginPPNode:=@FNodeArray[0];
  OldEndIndex:=longword(integer(self.FEndPos.PPNode)-integer(OldBeginPPNode)) div sizeof(_PPDequeNode);
  L:=length(self.FNodeArray);

  Assert(FEndPos.PPNode^<>nil);
  Assert(OldEndIndex+2<=L);
  Assert( ((OldEndIndex+1<L)and(FNodeArray[OldEndIndex+1]=nil)) or ((OldEndIndex+2<L)and(FNodeArray[OldEndIndex+1]<>nil)and(FNodeArray[OldEndIndex+2]=nil))  );

  if (FNodeArray[OldEndIndex+1]<>nil) then
  begin
    FNodeArray[OldEndIndex+2]:=FNodeArray[OldEndIndex+1];
    FNodeArray[OldEndIndex+1]:=nil;
  end;
  if (OldEndIndex+2=L) or (OldEndIndex+3=L) then
  begin
    exit
  end
  else
  begin
    self.DeleteNode(FNodeArray[OldEndIndex+3]);//hold 1 empty node: FNodeArray[OldEndIndex+2] ;

    OldFrontIndex:=longword(integer(self.FFrontPos.PPNode)-integer(OldBeginPPNode)) div sizeof(_PPDequeNode);

    DelCount:=L-(OldEndIndex+3)-(csDeultCapability shr 1);
    if DelCount*3>L then
    begin
      setlength(self.FNodeArray,L-DelCount);
      self.FFrontPos.PPNode:=@FNodeArray[OldFrontIndex];
      self.FEndPos.PPNode:=@FNodeArray[OldEndIndex];
    end;
  end;
end;


function  _TDeque.Clone():_IContainer;
begin
  result:=_IDeque(_TDeque.Create(self));
end;

procedure _TDeque.CloneToInterface(out NewContainer);
begin
  _IDeque(NewContainer):=_TDeque.Create(self);
end;

procedure _TDeque.Assign(const num:integer;const Value: _ValueType);
begin
  self.Clear();
  self.PushBack(num,Value);
end;

procedure _TDeque.Assign(const ItBegin,ItEnd:_IIterator);
begin
  self.Clear();
  self.PushBack(ItBegin,ItEnd);
end;



/////////////////////

{ _TDequeIterator }

class procedure _TDequeIterator.ItCreate(var SelfItData:_IIterator;const aDequePos:_TDequePos);
begin
  SelfItData._ObjIteratorClass:=_TDequeIterator;
  _PDequeIt(@SelfItData).Pos:=aDequePos;
end;

class procedure _TDequeIterator.ItCreate(var SelfItData:_IIterator;const ADeque: _TDeque;const Index:integer);
begin
  SelfItData._ObjIteratorClass:=_TDequeIterator;
  _PDequeIt(@SelfItData).Pos:=ADeque.GetPos(Index);
end;

class function _TDequeIterator.Distance(const SelfItData:_IIterator;const Iterator: _IIterator): integer;
begin
  result:=_TDeque_Distance(_PDequeIt(@SelfItData).Pos,_PDequeIt(@Iterator).Pos);
end;

class function _TDequeIterator.GetValue(const SelfItData:_IIterator): _ValueType;
begin
  result:=_PDequeIt(@SelfItData).Pos.PCurValue^;
end;

class function _TDequeIterator.IsEqual(const SelfItData:_IIterator;const Iterator: _IIterator): boolean;
begin
  result:=_PDequeIt(@SelfItData).Pos.PCurValue=_PDequeIt(@Iterator).Pos.PCurValue;
end;

class procedure _TDequeIterator.Next(var SelfItData:_IIterator);
var
  pPos : _PDequePos;
  PValue : _PValueType;
begin
  pPos:=@_PDequeIt(@SelfItData).pos;
  PValue:=ppos.PCurValue;
  inc(PValue);
  if longword(PValue)<longword(pPos.PEndValue) then
    ppos.PCurValue:=PValue
  else
    _TDeque_IncPos(pPos^);
end;

class procedure _TDequeIterator.Next(var SelfItData:_IIterator;const Step:integer);
begin
  _TDeque_IncPos(_PDequeIt(@SelfItData).Pos,Step);
end;

class procedure _TDequeIterator.Previous(var SelfItData:_IIterator);
var
  pPos : _PDequePos;
begin
  pPos:=@_PDequeIt(@SelfItData).pos;
  if Pointer(pPos.PCurValue)<>Pointer(pPos.PPNode^) then
    dec(pPos.PCurValue)
  else
    _TDeque_DecPos(pPos^);
end;

class procedure _TDequeIterator.SetValue(const SelfItData:_IIterator;const aValue: _ValueType);
begin
    {$ifdef  _DGL_ObjValue}
      _Assign(_PDequeIt(@SelfItData).Pos.PCurValue^,aValue);
    {$else}
      _PDequeIt(@SelfItData).Pos.PCurValue^:=aValue;
    {$endif}
end;

class function _TDequeIterator.GetNextValue(const SelfItData:_IIterator;const Step:integer): _ValueType;
var
  nPos : _TDequePos;
begin
  nPos:=_PDequeIt(@SelfItData).Pos;
  _TDeque_IncPos(nPos,Step);
  result:=nPos.PCurValue^;
end;

class procedure  _TDequeIterator.SetNextValue(const SelfItData:_IIterator;const Step:integer;const aValue: _ValueType);
var
  nPos : _TDequePos;
begin
  nPos:=_PDequeIt(@SelfItData).Pos;
  _TDeque_IncPos(nPos,Step);

    {$ifdef  _DGL_ObjValue}
      _Assign(nPos.PCurValue^,aValue);
    {$else}
      nPos.PCurValue^:=aValue;
    {$endif}

end;


class function _TDequeIterator.IteratorTraits():TIteratorTraits;
begin
  result:=itRandomAccessTag;
end;

{ _IDequeIterator }

procedure _IDequeIterator.SetValue(const aValue: _ValueType);
begin
    {$ifdef  _DGL_ObjValue}
      _Assign(_PDequeIt(@Self).Pos.PCurValue^,aValue);
    {$else}
      _PDequeIt(@Self).Pos.PCurValue^:=aValue;
    {$endif}
end;
function  _IDequeIterator.GetValue(): _ValueType;
begin
  result:=_PDequeIt(@Self).Pos.PCurValue^;
end;
function  _IDequeIterator.GetNextValue(const Step:integer): _ValueType;
var
  nPos : _TDequePos;
begin
  nPos:=_PDequeIt(@Self).Pos;
  _TDeque_IncPos(nPos,Step);
  result:=nPos.PCurValue^;
end;
procedure _IDequeIterator.SetNextValue(const Step:integer;const aValue:_ValueType);
var
  nPos : _TDequePos;
begin
  nPos:=_PDequeIt(@Self).Pos;
  _TDeque_IncPos(nPos,Step);
  
    {$ifdef  _DGL_ObjValue}
      _Assign(nPos.PCurValue^,aValue);
    {$else}
      nPos.PCurValue^:=aValue;
    {$endif}
end;
function  _IDequeIterator.IsEqual(const Iterator:_IIterator):boolean;
begin
  result:=_PDequeIt(@Self).Pos.PCurValue=_PDequeIt(@Iterator).Pos.PCurValue;
end;
function  _IDequeIterator.Distance(const Iterator:_IIterator):integer;
begin
  result:=_TDeque_Distance(_PDequeIt(@Self).Pos,_PDequeIt(@Iterator).Pos);
end;
procedure _IDequeIterator.Assign (const Iterator:_IIterator);
begin
  Self._ObjIteratorClass:=Iterator._ObjIteratorClass;
  _PDequeIt(@Self).Pos:=_PDequeIt(@Iterator).Pos;
end;
procedure _IDequeIterator.Next();
var
  pPos : _PDequePos;
  PValue : _PValueType;
begin
  pPos:=@_PDequeIt(@Self).pos;
  PValue:=ppos.PCurValue;
  inc(PValue);
  if longword(PValue)<longword(pPos.PEndValue) then
    ppos.PCurValue:=PValue
  else
    _TDeque_IncPos(pPos^);
end;
procedure _IDequeIterator.Next(const Step:integer);
begin
  _TDeque_IncPos(_PDequeIt(@Self).Pos,Step);
end;
procedure _IDequeIterator.Previous();
var
  pPos : _PDequePos;
begin
  pPos:=@_PDequeIt(@Self).pos;
  if Pointer(pPos.PCurValue)<>Pointer(pPos.PPNode^) then
    dec(pPos.PCurValue)
  else
    _TDeque_DecPos(pPos^);
end;
function  _IDequeIterator.Clone():_IIterator;
begin
  result._ObjIteratorClass:=self._ObjIteratorClass;
  _PDequeIt(@result).Pos:=_PDequeIt(@Self).Pos;
end;
function  _IDequeIterator.Clone(const NextStep:integer):_IIterator;
begin
  result._ObjIteratorClass:=self._ObjIteratorClass;
  _PDequeIt(@result).Pos:=_PDequeIt(@Self).Pos;
  _TDeque_IncPos(_PDequeIt(@result).Pos,NextStep);
end;

function _IDequeIterator.IteratorTraits():TIteratorTraits;
begin
  result:=itRandomAccessTag;
end;


{$endif } //  __Deque_inc_pas_