//
//  Map: Hash table using separate chaining
//
//          Collection stores pointer to an array of buckets. Each bucket
//          contains linked list of values.
//

{$I d_checks.inc}

{$IF Defined(D_INTERFACE)}
type
{$IFDEF D_USE_GENERIC}
generic D_COLLECTION<
  {$IFDEF D_KEY_SIZE_STATIC}TKey,{$ENDIF}
  {$IFDEF D_VALUE_SIZE_STATIC}TValue,{$ENDIF}
  {$IFDEF D_HASH_STATIC}THash,{$ENDIF}
  {$IFDEF D_ALLOCATOR_STATIC}TAllocator,{$ENDIF}
  TDummy> = object
{$ELSE}
D_COLLECTION = object
{$ENDIF}
public type
  // Pointer to the structure
  TPtr = ^D_COLLECTION;
  // Pointers to keys and values
  PKey = ^TKey;
  PValue = ^TValue;
  // Generic hash function
  THashValue = D_HASH_TYPE;
  THashFunc = function(Key: Pointer; KeyLength: SizeUInt): THashValue;
  // Buckets as linked list
  PBucket = ^TBucket;
  TBucket = record
    Hash: THashValue;
    Key: TKey;
    {$IF Defined(D_KEY_SIZE_DYNAMIC)} KeyLength: SizeUInt{$ENDIF}
    Value: TValue;
    {$IF Defined(D_VALUE_SIZE_DYNAMIC)} ValueLength: SizeUInt{$ENDIF}
    Next: PBucket;
  end;
  TIterator = object
  private
    FBucketCursor: PBucket;
    FBucketEnd: PBucket;
    FPair: PBucket;
  public
    procedure Init(Map: TPtr);
    procedure Done; inline;
    function Key: PKey; inline;
    function Value: PValue; inline;
    function MoveNext: Boolean; inline;
  end;
private
  FBuckets: PBucket;
  FBucketsCount: SizeUInt;
  {$IF Defined(D_ALLOCATOR_STATIC)}FAllocator: Pointer;{$ENDIF}
  function AllocPair: PBucket; inline;
  procedure FreePair(Bucket: PBucket); inline;
public
  procedure Init(
    {$IF Defined(D_ALLOCATOR_STATIC)}AllocatorData: Pointer;{$ENDIF}
    Dummy: Pointer = nil
  );
  procedure Done;
  function Insert({$IF Defined(D_HASH_EXTERNAL)}Hash: THashValue;{$ENDIF}
               const Key: TKey;
                {$IF Defined(D_KEY_SIZE_DYNAMIC)}KeyLength: SizeUInt;{$ENDIF}
               const Value: TValue
                {$IF Defined(D_KEY_SIZE_DYNAMIC)}; ValueLength: SizeUInt{$ENDIF}): Boolean;
  function Find({$IF Defined(D_HASH_EXTERNAL)}Hash: THashValue;{$ENDIF}
                const Key: TKey;
                {$IF Defined(D_KEY_SIZE_DYNAMIC)}KeyLength: SizeUInt;{$ENDIF}
                out Value: PValue
                {$IF Defined(D_KEY_SIZE_DYNAMIC)}; out ValueLength: SizeUInt{$ENDIF}): Boolean;
  function Delete({$IF Defined(D_HASH_EXTERNAL)}Hash: THashValue;{$ENDIF}
                  const Key: TKey
                  {$IF Defined(D_KEY_SIZE_DYNAMIC)}; KeyLength: SizeUInt{$ENDIF}): Boolean;
end;
{$ENDIF}

{$IF Defined(D_IMPLEMENTATION)}
procedure D_COLLECTION.TIterator.Init(Map: TPtr);
begin
end;

procedure D_COLLECTION.TIterator.Done;
begin
end;

function D_COLLECTION.TIterator.Key: PKey;
begin
  Exit(nil);
end;

function D_COLLECTION.TIterator.Value: PValue;
begin
  Exit(nil);
end;

function D_COLLECTION.TIterator.MoveNext: Boolean;
begin
  Exit(False);
end;

function D_COLLECTION.AllocPair: PBucket;
begin
  New(Result);
end;

procedure D_COLLECTION.FreePair(Bucket: PBucket);
begin
  Dispose(Bucket);
end;

procedure D_COLLECTION.Init(
    {$IF Defined(D_ALLOCATOR_STATIC)}AllocatorData: Pointer;{$ENDIF}
    Dummy: Pointer = nil
  );
begin
  {$IF Defined(D_ALLOCATOR_STATIC)}FAllocator.Init(AllocatorData);{$ENDIF}
  FBuckets := nil;
  FBucketsCount := 0;
end;

procedure D_COLLECTION.Done;
begin
  {$IF Defined(D_ALLOCATOR_STATIC)}FAllocator.Done;{$ENDIF}
end;

function D_COLLECTION.Insert({$IF Defined(D_HASH_EXTERNAL)}Hash: THashValue;{$ENDIF}
             const Key: TKey;
             const Value: TValue): Boolean;
begin
  Result := True;
end;

function D_COLLECTION.Find({$IF Defined(D_HASH_EXTERNAL)}Hash: THashValue;{$ENDIF}
              const Key: TKey;
              {$IF Defined(D_KEY_SIZE_DYNAMIC)}; KeyLength: SizeUInt{$ENDIF}
              out Value: PValue): Boolean;
begin
  Result := False;
end;

function D_COLLECTION.Delete({$IF Defined(D_HASH_EXTERNAL)}Hash: THashValue;{$ENDIF}
                             const Key: TKey
                             {$IF Defined(D_KEY_SIZE_DYNAMIC)}; KeyLength: SizeUInt{$ENDIF}): Boolean;
var
  Bucket, Prev: PBucket;
begin
  if FBucketsCount = 0 then
    Exit(False);
  Bucket := FBuckets + (
      {$IF Defined(D_HASH_EXTERNAL)}
        Hash
      {$ELSEIF Defined(D_HASH_STATIC}
        THash.GetHash(Key, SizeOf(Key))
      {$ELSEIF Defined(D_HASH_PARAMETRIC}
        FHash.GetHash(Key, SizeOf(Key))
      {$ENDIF}
    and (FBucketsCount - 1));
  Prev := nil;
  while Bucket <> nil do begin
    if Bucket^.Key = Key then begin
      FreePair(Bucket);
      Exit(True);
    end;
  end;
  Exit(False);
end;
{$ENDIF}
