{$MODE OBJFPC}
{$MODESWITCH AUTODEREF}
{$MODESWITCH TYPEHELPERS}
{$MODESWITCH ADVANCEDRECORDS}
unit dhashtable;

interface

type
THash64 = QWord;
THash32 = Cardinal;
THashValue = THash32;

// THashFunc должен иметь статичечкий метод GetHash(const Key: TKey): THash

generic THashSet<TKey, THashFunc> = object
public type
  TPtr = ^THashSet;
  TElement = TKey;
protected
  FTable: array of array of TKey;
public
  constructor Init(Initial: LongInt = 16 * 1024);
  destructor Done;
  procedure Clear;
  procedure Insert(const Key: TKey);
  function Has(const Key: TKey): Boolean;
end;

generic THashPair<TKey, TValue, THashFunc> = record
public type
  TPtr = ^THashPair;
public
  Key: TKey;
  Value: TValue;
  function GetHash: THash32;
  class operator = (const A, B: THashPair): Boolean; inline;
end;

generic THashMap<TKey, TValue, THashFunc> = object
public type
  TPtr = ^THashMap;
  TPair = specialize THashPair<TKey, TValue, THashFunc>;
  PElement = ^TElement;
  TElement = TPair;
protected
  FTable: array of array of TPair;
public
  constructor Init(Initial: LongInt = 16*1024);
  destructor Done;
  procedure Clear;
  procedure Insert(const Key: TKey; const Value: TValue);
  function Has(const Key: TKey): Boolean;
  function Find(const Key: TKey; out Value: TValue): Boolean;
  function FindElement(const Key: TKey; out Element: PElement): Boolean;
  function GetMaxCollisions: LongInt;
end;

THashDjb2ForAnsiString = object
  function GetHash(const Key: AnsiString): THash32; inline; static;
end;

function Djb2(P: PByte; Size: Int64): THash64;

implementation

constructor THashSet.Init(Initial: LongInt);
begin
  SetLength(FTable, Initial);
end;

destructor THashSet.Done;
begin
end;

procedure THashSet.Clear;
var
  H: THash32;
begin
  for H := 0 to High(FTable) do
    SetLength(FTable[H], 0);
end;

procedure THashSet.Insert(const Key: TKey);
var
  H: THash32;
begin
  H := THashFunc.GetHash(Key) mod Length(FTable);
  SetLength(FTable[H], Length(FTable[H]) + 1);
  FTable[H][High(FTable[H])] := Key;
end;

function THashSet.Has(const Key: TKey): Boolean;
var
  H: THash32;
  I: LongInt;
begin
  H := THashFunc.GetHash(Key) mod Length(FTable);
  for I := 0 to High(FTable[H]) do
    if FTable[H][I] = Key then
      Exit(True);
  Exit(False);
end;

function THashPair.GetHash: THash32;
begin
  Result := THashFunc.GetHash(Key);
end;

class operator THashPair.= (const A, B: THashPair): Boolean;
begin
  Result := A.Key = B.Key;
end;

constructor THashMap.Init(Initial: LongInt);
begin
  SetLength(FTable, Initial);
end;

destructor THashMap.Done;
begin
end;

procedure THashMap.Clear;
begin
  // TODO
end;

procedure THashMap.Insert(const Key: TKey; const Value: TValue);
var
  H: THash32;
begin
  H := THashFunc.GetHash(Key) mod Length(FTable);
  SetLength(FTable[H], Length(FTable[H]) + 1);
  FTable[H][High(FTable[H])].Key := Key;
  FTable[H][High(FTable[H])].Value := Value;
end;

function THashMap.Has(const Key: TKey): Boolean;
var
  H: THash32;
  I: LongInt;
begin
  H := THashFunc.GetHash(Key) mod Length(FTable);
  for I := 0 to High(FTable[H]) do
    if FTable[H][I].Key = Key then
      Exit(True);
  Exit(False);
end;

function THashMap.Find(const Key: TKey; out Value: TValue): Boolean;
var
  Element: PElement;
begin
  Result := FindElement(Key, Element);
  if Result then
    Value := Element^.Value;
end;

function THashMap.FindElement(const Key: TKey; out Element: PElement): Boolean;
var
  H: THash32;
  I: LongInt;
begin
  H := THashFunc.GetHash(Key) mod Length(FTable);
  for I := 0 to High(FTable[H]) do
    if FTable[H][I].Key = Key then begin
      Element := @FTable[H][I];
	  Exit(True);
    end;
  Exit(False);
end;

function THashMap.GetMaxCollisions: LongInt;
var
  H: THash32;
begin
  Result := 0;
  for H := 0 to High(FTable) do
    if Length(FTable[H]) > Result then
      Result := Length(FTable[H]);
end;

function Djb2(P: PByte; Size: Int64): THash64;
begin
  Result := 5381;
  while Size > 0 do begin
    Result := ((Result shl 5) + Result) + P^;
    Inc(P);
	Dec(Size);
  end;
end;

function THashDjb2ForAnsiString.GetHash(const Key: AnsiString): THash32;
begin
  Result := Djb2(PByte(@Key[1]), Length(Key));
end;

end.
