_hashtable.inc_pas

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

  end;
end;

procedure _THashTableBase.Erase(const ItPos: _IIterator);
begin
  self.DeleteNode(_PtmpHashIt_Data(@ItPos).FNodeIt.pPNode);
  DecCapacity();
end;


function _THashTableBase.EraseKey(const Key: _HashKeyType): integer;
var
  pPHashNode: _PPHashNode ;
begin
  pPHashNode:=self.FindItem(Key).pPNode;
  result:=0;
  {$ifdef _DGL_Compare_Key}
  while (pPHashNode^<>nil) and (_IsEqual_Key(pPHashNode^.Key,Key))  do
  {$else}
  while (pPHashNode^<>nil) and (pPHashNode^.Key=Key)  do
  {$endif}
  begin
    self.DeleteNode(pPHashNode);
    inc(result);
  end;

  DecCapacity();
end;

function _THashTableBase.EraseValue(const Value: _HashValueType): integer;
var
  pPNode : _PPHashNode;
  i : integer;
begin
  result:=0;
  for i:=low(self.FDataList) to high(self.FDataList) do
  begin
    if self.FDataList[i]<>nil then
    begin
      pPNode:=@self.FDataList[i];
      while pPNode^<>nil do
      begin
        {$ifdef _DGL_Compare_Value}
        if _IsEqual_Value(pPNode^.Value,Value) then
        {$else}
        if pPNode^.Value=Value then
        {$endif}
        begin
          self.DeleteNode(pPNode);
          inc(result);
        end
        else
          pPNode:=@(pPNode^).PNext;
      end;
    end;
  end;
  DecCapacity();
end;

function  _THashTableBase.EraseValue(const Key: _HashKeyType;const Value: _HashValueType): integer;
var
  pPHashNode: _PPHashNode ;
begin
  pPHashNode:=self.FindItem(Key).pPNode;
  result:=0;
  while (pPHashNode^<>nil) and
    {$ifdef _DGL_Compare_Key} (_IsEqual_Key(pPHashNode^.Key,Key)) {$else} (pPHashNode^.Key=Key) {$endif}
    do
  begin
    if {$ifdef _DGL_Compare} (_IsEqual(pPHashNode^.Value,Value))
    {$else} (pPHashNode^.Value=Value) {$endif} then
    begin
      self.DeleteNode(pPHashNode);
      inc(result);
    end
    else
      pPHashNode:=@(pPHashNode^).PNext;
  end;

  DecCapacity();
end;


function _THashTableBase.FindKey(const Key: _HashKeyType): _TTagHashIterator;
begin
  result:=self.FindItem(Key);
  if result.pPNode^=nil then
    result:=self.ItEnd;
end;

function _THashTableBase.LowerBound(const Key: _HashKeyType): _TTagHashIterator;
begin
  result:=FindKey(Key);
end;

function _THashTableBase.UpperBound(const Key: _HashKeyType): _TTagHashIterator;
var
  ItBegin: _TTagHashIterator;
begin
  self.EqualRange(Key,ItBegin,result);
end;

class procedure  _THashTableBase.Previous(const HashTable:_THashTableBase;var It: _TTagHashIterator);
var
  i     : integer;
  tmppPNode : _PPHashNode;
  tmpPNodeOld : _PHashNode;
begin
  if (It.pPNode<>nil) and (HashTable.FDataList[It.ArrayIndex]<>It.pPNode^) then
  begin
    //还在本节点(Node)
    tmpPPNode:=@HashTable.FDataList[It.ArrayIndex];
    tmppNodeOld:=It.pPNode^;
    while tmppPNode^.PNext<>tmpPNodeOld do
    begin
      tmppPNode:=@tmppPNode^.PNext;
    end;
    It.pPNode:=tmppPNode;
  end
  else
  begin
    //跳到上一个节点(Node)寻找
    for i:=(It.ArrayIndex-1) downto 0 do
    begin
      if (HashTable.FDataList[i]<>nil) then
      begin
        tmppPNode:=@HashTable.FDataList[i];
        while tmppPNode^.PNext<>nil do
        begin
          tmppPNode:=@tmppPNode^.PNext;
        end;
        It.ArrayIndex:=i;
        It.pPNode:=tmppPNode;
        exit;
      end;
    end;
    //raise EHashIteratorRangeError.Create(csHashIterator_Error);
    Assert(false);
  end;
end;

class procedure _THashTableBase.Next(const HashTable:_THashTableBase;var It: _TTagHashIterator);
var
  i     : integer;
begin
  Assert(It.pPNode<>nil);
  
  if (It.pPNode^.PNext<>nil) then
  begin
    It.pPNode:=@It.pPNode^.PNext;
    exit;
  end
  else
  begin
    //跳到下一个节点(Node)寻找
    for i:=(It.ArrayIndex+1) to HashTable.FCapacity-1 do
    begin
      if (HashTable.FDataList[i]<>nil) then
      begin
        It.ArrayIndex:=i;
        It.pPNode:=@HashTable.FDataList[i];
        exit;
      end;
    end;
    It.ArrayIndex:=HashTable.FCapacity-1;
    It.pPNode:=nil;
  end;
end;

class function _THashTableBase.IsEndIt(
  const It: _TTagHashIterator): boolean;
begin
  result:=(It.pPNode=nil);//or(It.pPNode^=nil);
end;

function _THashTableBase.CountRange(const Key: _HashKeyType; out ItBegin,
  ItEnd: _TTagHashIterator): integer;
begin
  ItBegin:=self.LowerBound(Key);
  if self.IsEndIt(ItBegin) then
  begin
    result:=0;
    ItEnd:=ItBegin;
    exit;
  end;

  ItEnd:=ItBegin;
  self.Next(self,ItEnd);
  result:=1;
  {$ifdef _DGL_Compare_Key}
  while (not self.IsEndIt(ItEnd) and (_IsEqual_Key(ItEnd.pPNode^.Key,Key))) do
  {$else}
  while (not self.IsEndIt(ItEnd) and (ItEnd.pPNode^.Key=Key)) do
  {$endif}
  begin
    inc(result);
    self.Next(self,ItEnd);
  end;
end;

class function _THashTableBase.IsEqualIt(const It0,
  It1: _TTagHashIterator): boolean;
begin
  result:=(It0.pPNode=It1.pPNode);// and (it0.ArrayIndex=it1.ArrayIndex);
end;

function _THashTableBase.FindValue(
  const Value: _HashValueType): _TTagHashIterator;
begin
  result:=self.ItBegin;
  while not self.IsEndIt(result) do
  begin
    {$ifdef _DGL_Compare_Value}
    if _IsEqual_Value(result.pPNode^.Value,Value) then exit;
    {$else}
    if result.pPNode^.Value=Value then exit;
    {$endif}
    self.Next(self,result);
  end;
end;

function _THashTableBase.getNewNode(const Key: _HashKeyType;const Value: _HashValueType): _PHashNode;
begin
  result:=getNewNode(Key);
  try
    {$ifdef _DGL_ObjValue_Key}
      result.Key:=_CopyCreateNew_Key(Key);
    {$else}
      result.Key:=Key;
    {$endif}

    if (not F_DGL_OnlySet) then
    begin
      {$ifdef _DGL_ObjValue_Value}
        result.Value:=_CopyCreateNew_Value(Value);
      {$else}
        result.Value:=Value;
      {$endif}
    end;
  except
    self.DisposeNode(result);
    raise;
  end;
end;

function _THashTableBase.getNewNode(const Key: _HashKeyType): _PHashNode;
begin
  //asm int 3 end;
  if F_DGL_OnlySet then
    system.New(_PHashNode_OnlySet(result))
  else
    system.New(_PHashNode(result));

  try
    {$ifdef _DGL_ObjValue_Key}
      result.Key:=_CopyCreateNew_Key(Key);
    {$else}
      result.Key:=Key;
    {$endif}
  except
    self.DisposeNode(result);
    raise;
  end;
end;

procedure _THashTableBase.UniqueInsertNode(pPHashNode: _PPHashNode;
    const Key: _HashKeyType;const Value: _HashValueType);
begin
  if (pPHashNode^<>nil) then   //replace
    {$ifdef _DGL_ObjValue_Value}
    _Assign_Value((pPHashNode^)^.Value,Value)
    {$else}
    (pPHashNode^)^.Value:=Value
    {$endif}
  else          //new
    self.MultiInsertNode(pPHashNode,Key,Value);
end;

procedure _THashTableBase.MultiInsertNode(pPHashNode: _PPHashNode;
  const Key: _HashKeyType; const Value: _HashValueType);
var
  pHashNode : _PHashNode;
begin
  pHashNode:=getNewNode(Key,Value);
  pHashNode.PNext:=pPHashNode^;
  pPHashNode^:=pHashNode;

  //inc(testTHashNodeCount);

  inc(self.FCount);
  if (self.FCount=self.FCapacity) then
  begin
    self.SetCapacityIndex(FCapacityIndex+1);
  end;
end;

procedure _THashTableBase.MultiInsertNode(pPHashNode: _PPHashNode;
  const Key: _HashKeyType);
var
  pHashNode : _PHashNode;
begin
  pHashNode:=getNewNode(Key);
  pHashNode.PNext:=pPHashNode^;
  pPHashNode^:=pHashNode;

  //inc(testTHashNodeCount);

  inc(self.FCount);
  if (self.FCount=self.FCapacity) then
  begin
    self.SetCapacityIndex(FCapacityIndex+1);
  end;
end;

procedure _THashTableBase.DecCapacity;
begin
  if (self.FCount*4<self.FCapacity) and (self.FCount>_csHashCapacityList[_csDefaultHashCapacityIndex]) then
  begin
    if ((FCapacityIndex - 1)>=self.FAlwaysReserveIndex) and (FCapacityIndex>_csDefaultHashCapacityIndex) then
      self.SetCapacityIndex(FCapacityIndex-1);
  end;
end;

{ _THashBaseIterator }

class function _THashBaseIterator.Map_GetKey(const SelfItData:_IIterator): _HashKeyType;
begin
  result:=_PtmpHashIt_Data(@SelfItData).FNodeIt.pPNode^.Key;
end;

class function _THashBaseIterator.GetValue(const SelfItData:_IIterator): _HashValueType;
begin
  result:=_PtmpHashIt_Data(@SelfItData).FNodeIt.pPNode^.Value;
end;

class function _THashBaseIterator.IsEqual(const SelfItData:_IIterator;const Iterator:_IIterator): boolean;
begin
  result:=(_PtmpHashIt_Data(@Iterator).FNodeIt.pPNode=_PtmpHashIt_Data(@SelfItData).FNodeIt.pPNode);
end;

class procedure _THashBaseIterator.Next(var SelfItData:_IIterator);
begin
  _PtmpHashIt_Data(@SelfItData).FBase.Next(
    _PtmpHashIt_Data(@SelfItData).FBase,
    _PtmpHashIt_Data(@SelfItData).FNodeIt);
end;

class procedure _THashBaseIterator.SetValue(const SelfItData:_IIterator;const Value: _HashValueType);
begin
  _PtmpHashIt_Data(@SelfItData).FNodeIt.pPNode^.Value:=Value;
end;


class procedure _THashBaseIterator.Previous(var SelfItData:_IIterator);
begin
  _PtmpHashIt_Data(@SelfItData).FBase.Previous(
    _PtmpHashIt_Data(@SelfItData).FBase,
    _PtmpHashIt_Data(@SelfItData).FNodeIt);
end;

class procedure _THashBaseIterator.ItCreate(var SelfItData:_IIterator;const base: _THashTableBase;
  const NodeIt:_TTagHashIterator);
begin
  SelfItData._ObjIteratorClass:=_THashBaseIterator;
  _PtmpHashIt_Data(@SelfItData).FBase:=base;
  _PtmpHashIt_Data(@SelfItData).FNodeIt:=NodeIt;
end;



class function _THashBaseIterator.IteratorTraits():TIteratorTraits;
begin
  result:=itBidirectionalTag;
end;


{$endif } // __HashTable_inc_pas_