deque.inc_pas

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

    _MiddleInsert(ItPos, ItPos, ItPos,num,Value);
end;

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

procedure _TDeque._MiddleInsert(const ItPos, ItBegin, ItEnd: _IIterator;num: integer;const Value: _ValueType);
var
  Index: integer;
  BeginPos,EndPos,DestPos : _TDequePos;
  IsItInsert : boolean;
{$ifdef  _DGL_ObjValue}
var
  _Default_Value : _ValueType;
{$endif}
begin
  Index:=_TDeque_Distance(self.FFrontPos,_PDequeIt(@ItPos).Pos);
  begin
    IsItInsert:=(num=0);
    if IsItInsert then
      num:=ItBegin.Distance(ItEnd);
    if Index >=_TDeque_Distance(self.FFrontPos,self.FEndPos) div 2 then
    begin
      {$ifdef  _DGL_ObjValue}
        _Default_Value:=_CreateNew();
        self.PushBack(num,_Default_Value);
        _Free(_Default_Value);
      {$else}
        self.PushBack(num,_NULL_Value);
      {$endif}
      BeginPos:=self.GetPos(Index); //move begin
      EndPos:=self.GetPos(_TDeque_Distance(FFrontPos,FEndPos)-num); //move end
      DestPos:=self.GetPos(Index+num);   //move dest
      self.ReCopy(BeginPos,EndPos,DestPos);
      if IsItInsert  then
        self.Fill(BeginPos,DestPos,ItBegin)
      else
        self.Fill(BeginPos,DestPos,Value);
    end
    else
    begin
      {$ifdef  _DGL_ObjValue}
        _Default_Value:=_CreateNew();
        self.PushFront(num,_Default_Value);
        _Free(_Default_Value);
      {$else}
        self.PushFront(num,_NULL_Value);
      {$endif}
      BeginPos:=self.GetPos(num);//move bedin
      EndPos:=self.GetPos(Index+num); //move end
      self.Copy(BeginPos,EndPos,self.FFrontPos);
      BeginPos:=self.GetPos(Index);
      if IsItInsert  then
        self.Fill(BeginPos,EndPos,ItBegin)
      else
        self.Fill(BeginPos,EndPos,Value);
    end;
  end;
end;

function _TDeque.ItEnd: _IIterator;
begin
  _TDequeIterator.ItCreate(result,self.FEndPos);
end;

class function _TDeque.NewNode: _PDequeNode;
begin
  system.New(_PMemDequeNode(result));
end;

procedure _TDeque.PopBack;
var
  PValue : _PValueType;
begin
  Assert(self.FFrontPos.PCurValue<>self.FEndPos.PCurValue);
  PValue:=(self.FEndPos.PCurValue);
  if longword(PValue)=longword(integer(FEndPos.PPNode^)) then
  begin
    _TDeque_DecPos(FEndPos);
    PValue:=(self.FEndPos.PCurValue);
    {$ifdef  _DGL_ObjValue}  _Free(PValue^); {$endif}
    PValue^:=_NULL_Value;

    ReduceCapabilityBack();
  end
  else
  begin
    dec(PValue);
    {$ifdef  _DGL_ObjValue} _Free(PValue^); {$endif}
    PValue^:=_NULL_Value;
    FEndPos.PCurValue:=PValue;
  end;
end;

procedure _TDeque.PopFront;
var
  PValue : _PValueType;
begin
  Assert(self.FFrontPos.PCurValue<>self.FEndPos.PCurValue);
  PValue:=(self.FFrontPos.PCurValue);
  {$ifdef  _DGL_ObjValue}
    _Free(PValue^);
  {$endif}
  PValue^:=_NULL_Value;
  inc(PValue);
  if PValue<>FFrontPos.PEndValue then
    FFrontPos.PCurValue:=PValue
  else
  begin
    _TDeque_IncPos(FFrontPos);
    ReduceCapabilityFront();
  end;
end;

procedure _TDeque.PushFront(const num:integer;Value: _ValueType);
var
  i: integer;
begin
  for i:=0 to num-1 do
    self.PushFront(Value);
end;

procedure _TDeque.PushFront(const ItBegin,ItEnd: _IIterator);
var
  i,num: integer;
  It: _IIterator;
begin
  num:=ItBegin.Distance(ItEnd);
  It:=ItBegin.Clone();
  for i:=0 to num-1 do
  begin
    self.PushFront(It.Value);
    It.Next();
  end;
end;

procedure _TDeque.PushBack(const Value: _ValueType);
var
  PValue : _PValueType;
begin                  
  PValue:=FEndPos.PCurValue;
  if longword(PValue)+sizeof(_ValueType)>=longword(FEndPos.PEndValue) then
  begin
    if longword(PValue)>=longword(FEndPos.PEndValue) then
      ExtendCapabilityBack();
    PValue:=FEndPos.PCurValue;
    _TDeque_IncPos(self.FEndPos);
  end
  else
    FEndPos.PCurValue:=_PValueType(longword(PValue)+sizeof(_ValueType)); //==  inc(FEndPos.PCurValue);


  {$ifdef  _DGL_ObjValue}
    PValue^:=_CopyCreateNew(Value);
  {$else}
    PValue^:=Value;
  {$endif}
end;

procedure _TDeque.PushBack(const num:integer;Value: _ValueType);
var
  i: integer;
begin
  for i:=0 to num-1 do
    self.PushBack(Value);
end;

procedure _TDeque.PushBack(const ItBegin,ItEnd: _IIterator);
var
  i,num: integer;
  It: _IIterator;
begin
  num:=ItBegin.Distance(ItEnd);
  It:=ItBegin.Clone();
  for i:=0 to num-1 do
  begin
    self.PushBack(It.Value);
    It.Next();
  end;
end;

procedure _TDeque.PushFront(const Value: _ValueType);
var
  PValue : _PValueType;
begin
  PValue:=FFrontPos.PCurValue;
  if ( Pointer(PValue)=Pointer(FFrontPos.PPNode^) ) then
  begin
    ExtendCapabilityFront();
    _TDeque_DecPos(self.FFrontPos);
    PValue:=FFrontPos.PCurValue;
  end
  else
  begin
    dec(PValue);
    FFrontPos.PCurValue:=PValue;
  end;
    
  {$ifdef  _DGL_ObjValue}
    PValue^:=_CopyCreateNew(Value);
  {$else}
    PValue^:=Value;
  {$endif}
end;


function _TDeque.IsEquals(const AContainer: _IContainer): Boolean;
var
  i : integer;
  it : _IIterator;
begin
  if self.Size()<>AContainer.Size() then
  begin
    result:=false;
    exit;
  end;

  it:=AContainer.ItBegin();
  for i:=0 to _TDeque_Distance(FFrontPos,FEndPos)-1 do
  begin
    {$ifdef  _DGL_Compare}
    if (not _IsEqual((self.GetAItemAddress(i))^,it.Value)) then
    {$else}
    if (not ((self.GetAItemAddress(i))^=it.Value)) then
    {$endif}
    begin
      result:=false;
      exit;
    end
    else
      it.Next();
  end;
  result:=true;
end;

function _TDeque.IsLess(const AContainer: _IContainer): Boolean;
var
  i : integer;
  selfSize,ACSize,MinSize : integer;
  it : _IIterator;
begin
  selfSize:=_TDeque_Distance(FFrontPos,FEndPos);
  ACSize:=AContainer.Size();
  MinSize:=ACSize;
  if selfSize<MinSize then MinSize:=selfSize;

  it:=AContainer.ItBegin();
  for i:=0 to MinSize-1 do
  begin
    {$ifdef  _DGL_Compare}
    if (_IsLess(it.Value,(self.GetAItemAddress(i))^)) then
    {$else}
    if it.Value<(self.GetAItemAddress(i))^ then
    {$endif}
    begin
      result:=false;
      exit;
    end
    else
      it.Next();
  end;
  result:=(selfSize<ACSize);
end;


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

    _TDeque_DecPos(PEnd);
    _TDeque_DecPos(PDest);
  end;
end;

function _TDeque.EraseValue(const Value: _ValueType): integer;
var
  iRead  : _TDequePos;
  iWrite : _TDequePos;
  fIndex : integer;
  i  : integer;
  {$ifdef _DGL_ObjValue}
    tmpValue : _ValueType;
  {$endif}
begin
  fIndex:=IndexOf(Value);
  if fIndex<0 then
  begin
    result:=0;
    exit;
  end;

  result:=1;
  iWrite:=self.GetPos(fIndex);
  iRead:=iWrite;
  _TDeque_IncPos(iRead);
  for i:=fIndex+1 to _TDeque_Distance(FFrontPos,FEndPos)-1 do
  begin
    {$ifdef  _DGL_Compare}
    if (_IsEqual((iRead.PCurValue)^,Value)) then
    {$else}
    if ((iRead.PCurValue)^)=Value then
    {$endif}
    begin
      inc(result);
    end
    else
    begin
      {$ifdef _DGL_ObjValue}
        tmpValue:=(iWrite.PCurValue)^;
      {$endif}

      iWrite.PCurValue^:=iRead.PCurValue^;

      {$ifdef _DGL_ObjValue} //swap
        (iRead.PCurValue)^:= tmpValue;
      {$endif}

      _TDeque_incPos(iWrite);
    end;
    _TDeque_incPos(iRead);
  end;
  for i:=0 to result-1 do self.PopBack();
end;

procedure _TDeque.Reserve(const ReserveSize: integer);
begin
  //ok! do nothing
end;

procedure _TDeque.SetItemValue(const Index: Integer; const Value: _ValueType);
begin
  Assert(Index>=0);
  Assert(Index<_TDeque_Distance(FFrontPos,FEndPos));
  {$ifdef  _DGL_ObjValue}
    _Assign((self.GetAItemAddress(Index))^,Value);
  {$else}
    (self.GetAItemAddress(Index))^:=Value;
  {$endif}
end;

function _TDeque.Size: Integer;
begin
  result:=_TDeque_Distance(FFrontPos,FEndPos);
end;

procedure _TDeque_DecPos(var Pos: _TDequePos);
var
  PValue : _PValueType;
begin
  PValue:=Pos.PCurValue;
  if Pointer(PValue)=Pointer(Pos.PPNode^) then
  begin
    dec(Pos.PPNode);
    Assert(Pos.PPNode^<>nil);
    Pos.PCurValue:={$ifdef _DGL_ClassFunction_Specific}_TDeque_Get_ClassFunction_Address{$else}@{$endif}(Pos.PPNode^[csDequeNodeCount-1]);
    Pos.PEndValue:={$ifdef _DGL_ClassFunction_Specific}_TDeque_Get_ClassFunction_Address{$else}@{$endif}(Pos.PPNode^[csDequeNodeCount]);
  end
  else
    Dec(Pos.PCurValue);
end;

procedure _TDeque_IncPos(var Pos: _TDequePos);
begin
  Inc(Pos.PCurValue);
  if longword(Pos.PCurValue)>=longword(Pos.PEndValue) then
  begin
    inc(Pos.PPNode);
    if (Pos.PPNode^<>nil) then
    begin
      Pos.PCurValue:={$ifdef _DGL_ClassFunction_Specific}_TDeque_Get_ClassFunction_Address{$else}@{$endif}(Pos.PPNode^[0]);
      Pos.PEndValue:={$ifdef _DGL_ClassFunction_Specific}_TDeque_Get_ClassFunction_Address{$else}@{$endif}(Pos.PPNode^[csDequeNodeCount]);
    end
    else
    begin
      Pos.PCurValue:=nil;
      Pos.PEndValue:=nil;
    end;
  end;
end;

procedure _TDeque_IncPos(var Pos: _TDequePos; const dxIndex: integer);
var
  nIndex,nodeCount : integer;
  ValueIndex: integer;
begin
  ValueIndex:=(integer(Pos.PCurValue)-integer(Pos.PPNode^)) div (sizeof(_ValueType));
  nIndex:=ValueIndex+dxIndex;
  if nIndex>=0 then
  begin
    nodeCount:=(nIndex div csDequeNodeCount);
    inc(Pos.PPNode,nodeCount);
    if Pos.PPNode^<>nil then
    begin
      Pos.PCurValue:={$ifdef _DGL_ClassFunction_Specific}_TDeque_Get_ClassFunction_Address{$else}@{$endif}(Pos.PPNode^[(nIndex - nodeCount*csDequeNodeCount)]);
      Pos.PEndValue:={$ifdef _DGL_ClassFunction_Specific}_TDeque_Get_ClassFunction_Address{$else}@{$endif}(Pos.PPNode^[csDequeNodeCount]);
    end
    else
    begin
      Assert((nIndex - nodeCount*csDequeNodeCount)=0);
      Pos.PCurValue:=nil;
      Pos.PEndValue:=nil;
    end;
  end
  else
  begin
    nIndex:=(-nIndex)-1;
    nodeCount:=((nIndex) div csDequeNodeCount);
    dec(Pos.PPNode,nodeCount+1);
    Assert(Pos.PPNode^<>nil);
    Pos.PEndValue:={$ifdef _DGL_ClassFunction_Specific}_TDeque_Get_ClassFunction_Address{$else}@{$endif}(Pos.PPNode^[csDequeNodeCount]);
    Pos.PCurValue:=_PValueType(integer(Pos.PEndValue)-((nIndex -nodeCount*csDequeNodeCount)+1)*sizeof(_ValueType));
  end;
end;

function _TDeque_Distance(const BeginPos, EndPos: _TDequePos): integer;
begin