/// unit obsahujuci implementacie hasovacich tabuliek
unit hashmap;

interface

uses
  Windows,constants;

type
  /// record obsahujuci jeden prvok pre hasovaciu tabulku typu TStringIntHashMap
  TStringIntEntry = record
    key: xString;
    value: Integer;
    pos: Integer;
    regexp: xString;
  end;

  /// record obsahujuci jeden bucket pre hasovaciu tabulku typu TStringIntHashMap
  TStringIntBucket = record
    count: Integer;
    allocated: Integer;
    entries: array of TStringIntEntry;
  end;

  /// trieda implementujuca hasovaciu tabulku, kde sa hasuje podla kluca, ktorym je string
  TStringIntHashMap = class
  private
    FCapacity: Integer;
    FCount: Integer;
    FBuckets: array of TStringIntBucket;
  public
    constructor create; overload;
    constructor create(cap: Integer; icap: Integer); overload;
    function hash(const str: xString): DWORD;
    function findByKey(const key: xString; var bFound: boolean): Integer;
    function findByValue(value: Integer; var bFound: boolean): xString;
//    procedure add(const key: xString; value: Integer); overload;
    function getByKey(const key: xString; var value: Integer; var pos: Integer; var regexp: xString): Boolean;
    function getByValue(const value: Integer; var key: xString; var pos: Integer; var regexp: xString): Boolean;
    procedure add(const key: xString; value: Integer; pos: Integer; const regexp: xString); overload;
    procedure remove(const key: xString);
    function getSize: Integer;
    procedure clear;
    destructor Destroy; override;
    function toString(bComplex: Boolean = false): xString;
    function fillArray(var a: array of TStringIntEntry): Boolean;  //[in/out] a - [in] setlength to corrent size; [out] filled with values
                                                                //!TODO! zlepsit na in - inic/neinic premenna / out - inic pole s hodnotami
  end;

  /// record obsahujuci jeden prvok pre hasovaciu tabulku typu TIntIntHashMap
  TIntIntEntry = record
    key: Integer;
    value: Integer;
  end;

  /// record obsahujuci jeden bucket pre hasovaciu tabulku typu TIntIntHashMap
  TIntIntBucket = record
    count: Integer;
    allocated: Integer;
    entries: array of TIntIntEntry;
  end;

  /// trieda implementujuca hasovaciu tabulku, kde sa hasuje podla kluca, ktorym je string
  TIntIntHashMap = class
  private
    FCapacity: Integer;
    FCount: Integer;
    FBuckets: array of TIntIntBucket;
  public
    constructor create; overload;
    constructor create(cap: Integer; icap: Integer); overload;
    function hash(key: Integer): DWORD;
    function findByKey(key: Integer; var bFound: boolean): Integer;
    function findByValue(value: Integer; var bFound: boolean): Integer;
    procedure add(key: Integer; value: Integer);
    procedure remove(key: Integer);
    function getSize: Integer;
    procedure clear;
    destructor Destroy; override;
    function toString(bComplex: Boolean = false): xString;
    function fillArray(var a: array of TIntIntEntry): Boolean;
  end;

  PIntHashSetItem = ^TIntHashSetItem;
  /// record obsahujuci jeden prvok pre hasovaciu mnozinu celych cisiel typu TIntHashSet, kde kluc je cele cislo
  /// kolizie su riesene zretazenim
  TIntHashSetItem = record
    key: Integer;
    next: PIntHashSetItem;
  end;

  /// trieda implementujuca hasovaciu mnozinu, kde sa hasuje podla kluca, ktorym je integer
  TIntHashSet = class
    FCapacity: Integer;
    FLoadFactor: Integer;
    FGrowthFactor: Integer;
    FCount: Integer;
    FUnique: Boolean;
    FBuckets: array of PIntHashSetItem;
    FCurrentItem: PIntHashSetItem;
    FCurrentBucket: Integer;
  private
  public
    tag: Integer;
    tag2: Integer;
    procedure rehash(newcapacity: Integer);
    constructor create(bUnique: Boolean = true); overload;
    constructor createEx(cap: Integer; loadfactor: Integer = 2; growthfactor: Integer = 4; bUnique: Boolean = true); overload;
    constructor create(symbol: Integer; bUnique: Boolean = true); overload;
    function clone: TIntHashSet;
    function hash(key: Integer): DWORD;
    function contains(key: Integer): boolean;
    function count(key: Integer): Integer;  //return number of keys = key :)
    function add(key: Integer): Boolean; overload; //true if added; false if not (was not unique)
    function add(hashset: TIntHashSet): Boolean; overload;
    function addorget(var key: Integer): Boolean;
    function addNonEpsilon(hashset: TIntHashSet): Boolean;
    function remove(key: Integer): Boolean; //true if removed; false if not found
    function removeAll(key: Integer): Boolean; //true if removed; false if not found
    function getSize: Integer;
    function isEmpty: Boolean;
    procedure clear;
    destructor Destroy; override;
    procedure getNextReset;
    function getFirst(var key: Integer): Boolean;
    function getNext(var key: Integer): Boolean;
    function toString(bComplex: Boolean = false): xString;
  end;

  PIntIntHashSetItem = ^TIntIntHashSetItem;
  /// record obsahujuci jeden prvok pre hasovaciu mnozinu celych cisiel typu TIntIntHashSet,
  /// kde kluc je typu Integer (key), dalej je v kazdom prvku aj hodnota typu Integer (data)
  /// kolizie su riesene zretazenim
  TIntIntHashSetItem = record
    key: Integer;
    next: PIntIntHashSetItem;
    data: Integer;
  end;

  /// prototyp hasovacej funkcie
  THashFunc = function (key: Integer; capacity: Integer): DWORD;
  /// prototyp porovnavacej funkcie
  TCompareFunc = function (key1: Integer; key2: Integer): Boolean;

  /// trieda implementujuca hasovaciu mnozinu, kde sa hasuje podla kluca, ktorym je integer
  TIntIntHashSet = class
    FCapacity: Integer;
    FLoadFactor: Integer;
    FGrowthFactor: Integer;
    FCount: Integer;
    FUnique: Boolean;
    FBuckets: array of PIntIntHashSetItem;
    FCurrentItem: PIntIntHashSetItem;
    FCurrentBucket: Integer;
    FHashFunction: THashFunc;
    FCompareFunction: TCompareFunc;
  private
  public
    tag: Integer;
    procedure rehash(newcapacity: Integer);
    constructor create(bUnique: Boolean = true;hashfunction: THashFunc = nil; comparefunction: TCompareFunc = nil); overload;
    constructor createEx(cap: Integer; loadfactor: Integer = 2; growthfactor: Integer = 4; bUnique: Boolean = true; hashfunction: THashFunc = nil; comparefunction: TCompareFunc = nil); overload;
    function clone: TIntIntHashSet;
    function hash(key: Integer): DWORD;
    function equal(key1, key2: Integer): Boolean;
    function contains(key: Integer): boolean;
    function count(key: Integer): Integer;  //return number of keys = key :)
    function add(key: Integer; data: Integer): Boolean;  //true if added; false if not (was not unique)
    function addorget(var key: Integer; var data: Integer): Boolean;  //returns data of the existing item, if exists; true if added; false if not (was not unique)
    function remove(key: Integer): Boolean; //true if removed; false if not found
    function removeandget(key: Integer;var data: Integer): Boolean; //true if removed; false if not found & returns current data item in data
    function get(key: Integer; var data: Integer): Boolean;  //true if found, false otherwise
    function removeAll(key: Integer): Boolean; //true if removed; false if not found
    function getSize: Integer;
    function isEmpty: Boolean;
    procedure clear;
    destructor Destroy; override;
    procedure getNextReset;
    function getFirst(var key: Integer;var data: Integer): Boolean;
    function getNext(var key: Integer; var data: Integer): Boolean;
    function toString(bComplex: Boolean = false): xString;
  end;

  PStrIntEntry = ^TStrIntEntry;
  /// record obsahujuci jeden prvok pre hasovaciu mnozinu celych cisiel typu TStrIntHashMap,
  /// kde kluc je typu String (key), dalej je v kazdom prvku aj hodnota typu Integer (data)
  /// kolizie su riesene zretazenim
  TStrIntEntry = record
    key: xString;
    value: Integer;
    pos: Integer;
    regexp: xString;
  end;

  PStrIntBucket = ^TStrIntBucket;
  /// record obsahujuci jeden bucket pre hasovaciu mnozinu celych cisiel typu TStrIntHashMap
  TStrIntBucket = record
    count: Integer;
    allocated: Integer;
    entries: array of PStrIntEntry;
  end;

  /// trieda implementujuca hasovaciu mnozinu, kde sa hasuje podla kluca, ktorym je String
  /// obsahuje aj hasovaciu mnozinu na hasovanie podla hodnoty typu Integer
  TStrIntHashMap = class
  private
    FCapacity: Integer;
    FCount: Integer;
    FBuckets: array of PStrIntBucket;
  public
    FHashSet: TIntIntHashSet;
    constructor create; overload;
    constructor create(cap: Integer; icap: Integer); overload;
    function hash(str: xString): DWORD;
    function findByKey(key: xString; var bFound: boolean): Integer;
    function findByValue(value: Integer; var bFound: boolean): xString;
    function getByValue(value: Integer; var key: xString; var pos: Integer): Boolean; overload;
    procedure add(key: xString; value: Integer;pos: Integer); overload;
    procedure add(value: Integer; key: xString); overload;

    function getByKey(const key: xString; var value: Integer; var pos: Integer; var regexp: xString): Boolean; overload;
    function getByValue(const value: Integer; var key: xString; var pos: Integer; var regexp: xString): Boolean; overload;
    function replaceByValue(const value: Integer; var key: xString; var pos: Integer; var regexp: xString): Boolean;
    procedure add(const key: xString; value: Integer; pos: Integer; const regexp: xString); overload;

    procedure remove(key: xString);
    function getSize: Integer;
    procedure clear;
    destructor Destroy; override;
    function toString(bComplex: Boolean = false): xString;
    function fillArray(var a: array of TStrIntEntry): Boolean;  //[in/out] a - [in] setlength to corrent size; [out] filled with values
                                                                //!TODO! zlepsit na in - inic/neinic premenna / out - inic pole s hodnotami
  end;

implementation

uses
  SysUtils, Dialogs;

{ TStringIntHashMap }

/// konstruktor vytvarajuci objekt typu TStringIntHashMap
constructor TStringIntHashMap.create;
begin
  create(16,4);
end;

/// konstruktor vytvarajuci objekt typu TStringIntHashMap so vstupnymi parametrami;
/// cap je pocet bucketov, icap je kapacity v ramci jedneho bucketu
constructor TStringIntHashMap.create(cap: Integer; icap: Integer);
var I: Integer;
begin
  inherited create;
  FCount := 0;
  FCapacity := cap;
  SetLength(FBuckets,FCapacity);
  for I := 0 to Pred(FCapacity) do begin
    SetLength(FBuckets[I].entries,icap);
    FBuckets[I].allocated := icap;
  end;
end;

/// procedura na vyprazdnenie tejto hasovacej tabulky
procedure TStringIntHashMap.clear;
var I: Integer;
begin
  for I := 0 to Pred(FCapacity) do begin
    FBuckets[I].entries := nil;
  end;
end;

/// destruktor uvolnujuci objekt z pamate
destructor TStringIntHashMap.Destroy;
begin
  clear;
  FBuckets := nil;

  inherited Destroy;
end;

/// funkcia hladajuca podla hodnoty (value), v bFound vrati, ci sa podarilo nieco najst
/// a vysledkom je kluc najdenej hodnoty - cize string
function TStringIntHashMap.findByValue(value: Integer; var bFound: boolean): xString;
var h: Integer;
    lastentry: Integer;
    I: Integer;
begin
  bFound := false;
  for h := 0 to Pred(FCapacity) do begin
    lastentry := FBuckets[h].count - 1;
    if lastentry >= 0 then begin
      for I := 0 to lastentry do begin
        if FBuckets[h].entries[i].value = value then begin
          result := FBuckets[h].entries[i].key;
          bFound := true;
          exit;
        end;
      end;
    end;
  end;
  result := '';
end;

/// funkcia hladajuca podla kluca (key), v bFound vrati, ci sa podarilo nieco najst
/// a vysledkom je hodnota najdeneho kluca
function TStringIntHashMap.findByKey(const key: xString; var bFound: boolean): Integer;
var h: Integer;
    lastentry: Integer;
    I: Integer;
begin
  bFound := false;
  h := hash(key);
  lastentry := FBuckets[h].count - 1;
  for I := 0 to lastentry do begin
    if FBuckets[h].entries[i].key = key then begin
      result := FBuckets[h].entries[i].value;
      bFound := true;
      exit;
    end;
  end;
  result := 0
end;

/// funkcia hladajuca podla kluca, vrati hodnotu, poziciu, regularny vyraz ak su nastavene
/// vysledkom je ci sa takyto kluc podarilo najst v tabulke, alebo nie
function TStringIntHashMap.getByKey(const key: xString; var value: Integer; var pos: Integer; var regexp: xString): Boolean;
var h: Integer;
    lastentry: Integer;
    I: Integer;
begin
  result := false;
  h := hash(key);
  lastentry := FBuckets[h].count - 1;
  for I := 0 to lastentry do begin
    if FBuckets[h].entries[i].key = key then begin
      value := FBuckets[h].entries[i].value;
      pos := FBuckets[h].entries[i].pos;
      regexp := FBuckets[h].entries[i].regexp;
      result := true;
      Exit;
    end;
  end;
  value := -1;
  pos := -1;
  regexp := '';
end;

/// funkcia hladajuca podla hodnoty, vrati kluc, poziciu, regularny vyraz ak su nastavene
/// vysledkom je ci sa takuto hodnotu podarilo najst v tabulke, alebo nie
function TStringIntHashMap.getByValue(const value: Integer; var key: xString; var pos: Integer; var regexp: xString): Boolean;
var h: Integer;
    lastentry: Integer;
    I: Integer;
begin
  result := false;
  for h := 0 to Pred(FCapacity) do begin
    lastentry := FBuckets[h].count - 1;
    if lastentry >= 0 then begin
      for I := 0 to lastentry do begin
        if FBuckets[h].entries[i].value = value then begin
          key := FBuckets[h].entries[i].key;
          pos := FBuckets[h].entries[i].pos;
          regexp := FBuckets[h].entries[i].regexp;
          result := true;
          exit;
        end;
      end;
    end;
  end;
  key := '';
  pos := -1;
  regexp := '';
end;

/// funkcia pocitajuca hash pre dany string, vystupom je DWORD obsahujuci tuto vypocitanu hasovaciu hodnotu
function TStringIntHashMap.hash(const str: xString): DWORD;
var I: Integer;
begin
  result := 5381;
  for I := 1 to length(str) do begin
    result := result shl 5 + result + ord(str[I]);
  end;
  result := result mod DWORD(FCapacity);
end;
(*
procedure TStringIntHashMap.add(const key: xString; value: Integer);
var h: Integer;
begin
  h := hash(key);
  FBuckets[h].entries[FBuckets[h].count].key := key;
  FBuckets[h].entries[FBuckets[h].count].value := value;
  FBuckets[h].entries[FBuckets[h].count].pos := -1;
  FBuckets[h].count := FBuckets[h].count + 1;
  FCount := FCount + 1;
  if FBuckets[h].count = FBuckets[h].allocated then begin
    FBuckets[h].allocated := FBuckets[h].allocated * 2;
    SetLength(FBuckets[h].entries, FBuckets[h].allocated);
  end;
end;
*)

/// funkcia pridavajuca novy kluc s hodnotou, poziciou, regularnym vyrazom (string) do tabulky
procedure TStringIntHashMap.add(const key: xString; value: Integer; pos: Integer; const regexp: xString);
var h: Integer;
begin
  h := hash(key);
  FBuckets[h].entries[FBuckets[h].count].key := key;
  FBuckets[h].entries[FBuckets[h].count].value := value;
  FBuckets[h].entries[FBuckets[h].count].pos := pos;
  FBuckets[h].entries[FBuckets[h].count].regexp := regexp;
  FBuckets[h].count := FBuckets[h].count + 1;
  FCount := FCount + 1;
  if FBuckets[h].count = FBuckets[h].allocated then begin
    FBuckets[h].allocated := FBuckets[h].allocated * 2;
    SetLength(FBuckets[h].entries, FBuckets[h].allocated);
  end;
end;

/// funkcia obstranujuca dany kluc z tabulky
procedure TStringIntHashMap.remove(const key: xString);
var h: Integer;
    lastentry: Integer;
    I,J: Integer;
begin
  h := hash(key);
  lastentry := FBuckets[h].count - 1;
  for I := 0 to lastentry do begin
    if FBuckets[h].entries[i].key = key then begin
      //Move(FBuckets[h].entries[i+1],FBuckets[h].entries[i],(lastentry - I) * SizeOf(TStrIntEntry));
      for J := I to lastentry - 1 do begin
        FBuckets[h].entries[J] := FBuckets[h].entries[J+1];
      end;
//      FBuckets[h].entries[lastentry] := nil;
      FBuckets[h].count := FBuckets[h].count - 1;
      FCount := FCount - 1;
      exit;
    end;
  end;
end;

/// funkcia vypisujuca tuto tabulku do stringu, bComplex urcuje, ci sa bude vypisovat
/// este detailnejsie
function TStringIntHashMap.toString(bComplex:Boolean = false): xString;
var h: Integer;
    lastentry: Integer;
    I: Integer;
begin
  result := '';
  for h := 0 to Pred(FCapacity) do begin
    if bComplex then
      result := result + '[' + IntToStr(h) + ']' + EOL;
    lastentry := FBuckets[h].count - 1;
    if lastentry >= 0 then begin
      for I := 0 to lastentry do begin
        if bComplex then
          result := result + '  (' + IntToStr(I) + ')  ' + FBuckets[h].entries[i].key + ' - ' + IntToStr(FBuckets[h].entries[i].value) + EOL
        else
          result := result + FBuckets[h].entries[i].key + ' - ' + IntToStr(FBuckets[h].entries[i].value) + ' ';
      end;
    end;
  end;
end;

/// funkcia, ktora prvkami z hasovacej tabulky naplni vstupne pole a o dlzke = velkost hashovacej tabulky
function TStringIntHashMap.fillArray(var a: array of TStringIntEntry): Boolean;
var h: Integer;
    lastentry: Integer;
    I: Integer;
    index: Integer;
begin
  if Length(a) < getSize then begin
    result := false;
    Exit;
  end;
  index := 0;
  for h := 0 to Pred(FCapacity) do begin
    lastentry := FBuckets[h].count - 1;
    if lastentry >= 0 then begin
      for I := 0 to lastentry do begin
          a[index].key := FBuckets[h].entries[i].key;
          a[index].value := FBuckets[h].entries[i].value;
          Inc(index);
      end;
    end;
  end;
  result := true;
end;

/// funkcia, ktora vrati velkost hasovacej tabulky (pocet prvkov v nej)
function TStringIntHashMap.getSize: Integer;
begin
  result := FCount;
end;

{ TStrIntHashMap }

/// konstruktor vytvarajuci objekt typu TStrIntHashMap
constructor TStrIntHashMap.create;
begin
  create(16,4);
end;

/// konstruktor vytvarajuci objekt typu TStrIntHashMap so vstupnymi parametrami;
/// cap je pocet bucketov, icap je kapacity v ramci jedneho bucketu
constructor TStrIntHashMap.create(cap: Integer; icap: Integer);
var I: Integer;
begin
  inherited create;
  FCount := 0;
  FCapacity := cap;
  SetLength(FBuckets,FCapacity);
  for I := 0 to Pred(FCapacity) do begin
    new(FBuckets[I]);
    SetLength(FBuckets[I].entries,icap);
    FBuckets[I].count := 0;
    FBuckets[I].allocated := icap;
  end;
  FHashSet := TIntIntHashSet.createEx(16*4,2,4,true,nil,nil);
end;

/// procedura na vyprazdnenie tejto hasovacej tabulky
procedure TStrIntHashMap.clear;
var I,J: Integer;
begin
  for I := 0 to Pred(FCapacity) do begin
    for J := 0 to Pred(FBuckets[I].count) do begin
      dispose(FBuckets[I].entries[J]);
    end;
    FBuckets[I].entries := nil;
    dispose(FBuckets[I]);
  end;
  FHashSet.clear;
end;

/// destruktor uvolnujuci objekt z pamate
destructor TStrIntHashMap.Destroy;
begin
  clear;
  FBuckets := nil;
  FHashSet.Free;

  inherited Destroy;
end;

/// funkcia hladajuca podla hodnoty (value), v bFound vrati, ci sa podarilo nieco najst
/// a vysledkom je kluc najdenej hodnoty - cize string
function TStrIntHashMap.findByValue(value: Integer; var bFound: boolean): xString;
var pentry: PStrIntEntry;
begin
  if FHashSet.get(value,Integer(pentry)) then begin
    result := pentry.key;
    bFound := true;
  end
  else begin
    result := '';
    bFound := false;
  end;
end;

/// funkcia hladajuca podla hodnoty, vrati kluc, poziciu ak su nastavene
/// vysledkom je ci sa takuto hodnotu podarilo najst v tabulke, alebo nie
function TStrIntHashMap.getByValue(value: Integer; var key: xString; var pos: Integer): Boolean;
var pentry: PStrIntEntry;
begin
  if FHashSet.get(value,Integer(pentry)) then begin
    key := pentry.key;
    pos := pentry.pos;
    result := true;
  end
  else begin
    key := '';
    pos := -1;
    result := false;
  end;
end;

/// funkcia hladajuca podla kluca (key), v bFound vrati, ci sa podarilo nieco najst
/// a vysledkom je hodnota najdeneho kluca
function TStrIntHashMap.findByKey(key: xString; var bFound: boolean): Integer;
var h: Integer;
    lastentry: Integer;
    I: Integer;
begin
  bFound := false;
  h := hash(key);
  lastentry := FBuckets[h].count - 1;
  for I := 0 to lastentry do begin
    if FBuckets[h].entries[i].key = key then begin
      result := FBuckets[h].entries[i].value;
      bFound := true;
      exit;
    end;
  end;
  result := -1;
end;

/// funkcia hladajuca podla kluca, vrati hodnotu, poziciu, regularny vyraz ak su nastavene
/// vysledkom je ci sa takyto kluc podarilo najst v tabulke, alebo nie
function TStrIntHashMap.getByKey(const key: xString; var value: Integer; var pos: Integer; var regexp: xString): Boolean;
var h: Integer;
    lastentry: Integer;
    I: Integer;
begin
  result := false;
  h := hash(key);
  lastentry := FBuckets[h].count - 1;
  for I := 0 to lastentry do begin
    if FBuckets[h].entries[i].key = key then begin
      value := FBuckets[h].entries[i].value;
      pos := FBuckets[h].entries[i].pos;
      regexp := FBuckets[h].entries[i].regexp;
      result := true;
      Exit;
    end;
  end;
  value := -1;
  pos := -1;
  regexp := '';
end;

/// funkcia hladajuca podla hodnoty, vrati kluc, poziciu, regularny vyraz ak su nastavene
/// vysledkom je ci sa takuto hodnotu podarilo najst v tabulke, alebo nie
function TStrIntHashMap.getByValue(const value: Integer; var key: xString; var pos: Integer; var regexp: xString): Boolean;
var pentry: PStrIntEntry;
begin
  if FHashSet.get(value,Integer(pentry)) then begin
    key := pentry.key;
    pos := pentry.pos;
    regexp := pentry.regexp;
    result := true;
  end
  else begin
    key := '';
    pos := -1;
    regexp := '';
    result := false;
  end;
end;

/// funkcia hladajuca podla hodnoty, ktora zmeni kluc, poziciu, regularny vyraz pre danu hodnotu
/// vysledkom je ci sa takuto hodnotu podarilo najst a zmenit, alebo nie
function TStrIntHashMap.replaceByValue(const value: Integer; var key: xString; var pos: Integer; var regexp: xString): Boolean;
var pentry: PStrIntEntry;
begin
  if FHashSet.get(value,Integer(pentry)) then begin
    pentry.key := key;
    pentry.pos := pos;
    pentry.regexp := regexp;
    result := true;
  end
  else begin
    result := false;
  end;
end;

/// funkcia pridavajuca novy kluc s hodnotou, poziciou, regularnym vyrazom (string) do tabulky
procedure TStrIntHashMap.add(const key: xString; value: Integer; pos: Integer; const regexp: xString);
var h: Integer;
begin
  //!WARNING! non unique
  h := hash(key);
  new(FBuckets[h].entries[FBuckets[h].count]);
  FBuckets[h].entries[FBuckets[h].count].key := key;
  FBuckets[h].entries[FBuckets[h].count].value := value;
  FBuckets[h].entries[FBuckets[h].count].pos := pos;
  FBuckets[h].entries[FBuckets[h].count].regexp := regexp;
  FBuckets[h].count := FBuckets[h].count + 1;
  FCount := FCount + 1;
  if FBuckets[h].count = FBuckets[h].allocated then begin
    FBuckets[h].allocated := FBuckets[h].allocated * 2;
    SetLength(FBuckets[h].entries, FBuckets[h].allocated);
  end;
  FHashSet.add(value,Integer(FBuckets[h].entries[FBuckets[h].count - 1]));
end;

/// funkcia pridavajuca novy kluc s hodnotou do tabulky
procedure TStrIntHashMap.add(value: Integer; key: xString);
begin
  add(key,value,-1);
end;

/// funkcia pocitajuca hash pre dany string, vystupom je DWORD obsahujuci tuto vypocitanu hasovaciu hodnotu
function TStrIntHashMap.hash(str: xString): DWORD;
var I: Integer;
begin
  result := 5381;
  for I := 1 to length(str) do begin
    result := result shl 5 + result + ord(str[I]);
  end;
  result := result mod DWORD(FCapacity);
end;

/// funkcia pridavajuca novy kluc s hodnotou, poziciou do tabulky
procedure TStrIntHashMap.add(key: xString; value: Integer; pos: Integer);
var h: Integer;
begin
  //!WARNING! non unique
  h := hash(key);
  new(FBuckets[h].entries[FBuckets[h].count]);
  FBuckets[h].entries[FBuckets[h].count].key := key;
  FBuckets[h].entries[FBuckets[h].count].value := value;
  FBuckets[h].entries[FBuckets[h].count].pos := pos;
  FBuckets[h].entries[FBuckets[h].count].regexp := '';
  FBuckets[h].count := FBuckets[h].count + 1;
  FCount := FCount + 1;
  if FBuckets[h].count = FBuckets[h].allocated then begin
    FBuckets[h].allocated := FBuckets[h].allocated * 2;
    SetLength(FBuckets[h].entries, FBuckets[h].allocated);
  end;
  FHashSet.add(value,Integer(FBuckets[h].entries[FBuckets[h].count - 1]));
end;

/// funkcia obstranujuca dany kluc z tabulky
procedure TStrIntHashMap.remove(key: xString);
var h: Integer;
    lastentry: Integer;
    I,J: Integer;
begin
  h := hash(key);
  lastentry := FBuckets[h].count - 1;
  for I := 0 to lastentry do begin
    if FBuckets[h].entries[i].key = key then begin
      FHashSet.remove(FBuckets[h].entries[i].value);
      dispose(FBuckets[h].entries[i]);
      //Move(FBuckets[h].entries[i+1],FBuckets[h].entries[i],(lastentry - I) * SizeOf(TStrIntEntry));
      for J := I to lastentry - 1 do begin
        FBuckets[h].entries[J] := FBuckets[h].entries[J+1];
      end;
//      FBuckets[h].entries[lastentry] := nil;
      FBuckets[h].count := FBuckets[h].count - 1;
      FCount := FCount - 1;
      exit;
    end;
  end;
end;

/// funkcia vypisujuca tuto tabulku do stringu, bComplex urcuje, ci sa bude vypisovat
/// este detailnejsie
function TStrIntHashMap.toString(bComplex:Boolean = false): xString;
var h: Integer;
    lastentry: Integer;
    I: Integer;
begin
  result := '';
  for h := 0 to Pred(FCapacity) do begin
    if bComplex then
      result := result + '[' + IntToStr(h) + ']' + EOL;
    lastentry := FBuckets[h].count - 1;
    if lastentry >= 0 then begin
      for I := 0 to lastentry do begin
        if bComplex then begin
          result := result + '  (' + IntToStr(I) + ')  ' + FBuckets[h].entries[i].key + ' - ' + IntToStr(FBuckets[h].entries[i].value) + EOL;
          result := result + '         @' + IntToStr(FBuckets[h].entries[i].value) + ' : ' + FBuckets[h].entries[i].regexp + EOL;
        end
        else
          result := result + FBuckets[h].entries[i].key + ' - ' + IntToStr(FBuckets[h].entries[i].value) + ' ';
      end;
    end;
  end;
end;

/// funkcia, ktora prvkami z hasovacej tabulky naplni vstupne pole a o dlzke = velkost hashovacej tabulky
function TStrIntHashMap.fillArray(var a: array of TStrIntEntry): Boolean;
var h: Integer;
    lastentry: Integer;
    I: Integer;
    index: Integer;
begin
  if Length(a) < getSize then begin
    result := false;
    Exit;
  end;
  index := 0;
  for h := 0 to Pred(FCapacity) do begin
    lastentry := FBuckets[h].count - 1;
    if lastentry >= 0 then begin
      for I := 0 to lastentry do begin
          a[index].key := FBuckets[h].entries[i].key;
          a[index].value := FBuckets[h].entries[i].value;
          Inc(index);
      end;
    end;
  end;
  result := true;
end;

/// funkcia, ktora vrati velkost hasovacej tabulky (pocet prvkov v nej)
function TStrIntHashMap.getSize: Integer;
begin
  result := FCount;
end;

{ TIntIntHashMap }

/// konstruktor vytvarajuci objekt typu TIntIntHashMap
constructor TIntIntHashMap.create;
begin
  create(16,4);
end;

/// konstruktor vytvarajuci objekt typu TIntIntHashMap so vstupnymi parametrami;
/// cap je pocet bucketov, icap je kapacity v ramci jedneho bucketu
constructor TIntIntHashMap.create(cap: Integer; icap: Integer);
var I: Integer;
begin
  inherited create;
  FCount := 0;
  FCapacity := cap;
  SetLength(FBuckets,FCapacity);
  for I := 0 to Pred(FCapacity) do begin
    SetLength(FBuckets[I].entries,icap);
    FBuckets[I].allocated := icap;
  end;
end;

/// procedura na vyprazdnenie tejto hasovacej tabulky
procedure TIntIntHashMap.clear;
var I: Integer;
begin
  for I := 0 to Pred(FCapacity) do begin
    FBuckets[I].entries := nil;
  end;
end;

/// destruktor uvolnujuci objekt z pamate
destructor TIntIntHashMap.Destroy;
begin
  clear;
  FBuckets := nil;

  inherited Destroy;
end;


/// funkcia hladajuca podla hodnoty (value), v bFound vrati, ci sa podarilo nieco najst
/// a vysledkom je kluc najdenej hodnoty - cize string
function TIntIntHashMap.findByValue(value: Integer; var bFound: boolean): Integer;
var h: Integer;
    lastentry: Integer;
    I: Integer;
begin
  bFound := false;
  for h := 0 to Pred(FCapacity) do begin
    lastentry := FBuckets[h].count - 1;
    if lastentry >= 0 then begin
      for I := 0 to lastentry do begin
        if FBuckets[h].entries[i].value = value then begin
          result := FBuckets[h].entries[i].key;
          bFound := true;
          exit;
        end;
      end;
    end;
  end;
  result := -1;
end;

/// funkcia hladajuca podla kluca (key), v bFound vrati, ci sa podarilo nieco najst
/// a vysledkom je hodnota najdeneho kluca
function TIntIntHashMap.findByKey(key: Integer; var bFound: boolean): Integer;
var h: Integer;
    lastentry: Integer;
    I: Integer;
begin
  bFound := false;
  h := hash(key);
  lastentry := FBuckets[h].count - 1;
  for I := 0 to lastentry do begin
    if FBuckets[h].entries[i].key = key then begin
      result := FBuckets[h].entries[i].value;
      bFound := true;
      exit;
    end;
  end;
  result := -1;
end;

/// funkcia pocitajuca hash pre dany integer, vystupom je DWORD obsahujuci tuto vypocitanu hasovaciu hodnotu
function TIntIntHashMap.hash(key: Integer): DWORD;
const
  A = 0.6180339887; // (sqrt(5) - 1) / 2
begin
  Result := Abs(Trunc(FCapacity * (Frac(Key * A))));
end;

/// funkcia pridavajuca novy kluc s hodnotou, poziciou, regularnym vyrazom (string) do tabulky
procedure TIntIntHashMap.add(key: Integer; value: Integer);
var h: Integer;
begin
  h := hash(key);
  FBuckets[h].entries[FBuckets[h].count].key := key;
  FBuckets[h].entries[FBuckets[h].count].value := value;
  FBuckets[h].count := FBuckets[h].count + 1;
  FCount := FCount + 1;
  if FBuckets[h].count = FBuckets[h].allocated then begin
    FBuckets[h].allocated := FBuckets[h].allocated * 2;
    SetLength(FBuckets[h].entries, FBuckets[h].allocated);
  end;
end;

/// funkcia obstranujuca dany kluc z tabulky
procedure TIntIntHashMap.remove(key: Integer);
var h: Integer;
    lastentry: Integer;
    I,J: Integer;
begin
  h := hash(key);
  lastentry := FBuckets[h].count - 1;
  for I := 0 to lastentry do begin
    if FBuckets[h].entries[i].key = key then begin
      //Move(FBuckets[h].entries[i+1],FBuckets[h].entries[i],(lastentry - I) * SizeOf(TStrIntEntry));
      for J := I to lastentry - 1 do begin
        FBuckets[h].entries[J] := FBuckets[h].entries[J+1];
      end;
//      FBuckets[h].entries[lastentry] := nil;
      FBuckets[h].count := FBuckets[h].count - 1;
      FCount := FCount - 1;
      exit;
    end;
  end;
end;

/// funkcia vypisujuca tuto tabulku do stringu, bComplex urcuje, ci sa bude vypisovat
/// este detailnejsie
function TIntIntHashMap.toString(bComplex:Boolean = false): xString;
var h: Integer;
    lastentry: Integer;
    I: Integer;
begin
  result := '';
  for h := 0 to Pred(FCapacity) do begin
    if bComplex then
      result := result + '[' + IntToStr(h) + ']' + EOL;
    lastentry := FBuckets[h].count - 1;
    if lastentry >= 0 then begin
      for I := 0 to lastentry do begin
        if bComplex then
          result := result + '  (' + IntToStr(I) + ')  ' + IntToStr(FBuckets[h].entries[i].key) + ' - ' + IntToStr(FBuckets[h].entries[i].value) + EOL
        else
          result := result + IntToStr(FBuckets[h].entries[i].key) + ' - ' + IntToStr(FBuckets[h].entries[i].value) + ' ';
      end;
    end;
  end;
end;

/// funkcia, ktora vrati velkost hasovacej tabulky (pocet prvkov v nej)
function TIntIntHashMap.getSize: Integer;
begin
  result := FCount;
end;

/// funkcia, ktora prvkami z hasovacej tabulky naplni vstupne pole a o dlzke = velkost hashovacej tabulky
function TIntIntHashMap.fillArray(var a: array of TIntIntEntry): Boolean;
var h: Integer;
    lastentry: Integer;
    I: Integer;
    index: Integer;
begin
  if Length(a) < getSize then begin
    result := false;
    Exit;
  end;
  index := 0;
  for h := 0 to Pred(FCapacity) do begin
    lastentry := FBuckets[h].count - 1;
    if lastentry >= 0 then begin
      for I := 0 to lastentry do begin
          a[index].key := FBuckets[h].entries[i].key;
          a[index].value := FBuckets[h].entries[i].value;
          Inc(index);
      end;
    end;
  end;
  result := true;
end;

{ TIntHashSet }

/// konstruktor vytvarajuci objekt typu TIntHashSet so vstupnymi parametrami;
/// cap je pocet bucketov, loadfactor je pomer naplnenia prvkami, pri
/// ktorom sa zacne prepracovavat tabulky (rehash), growthfactor je
/// nasobok povodnej hodnoty na ktory velkost hasovacej tabulky narastie;
/// bUnique urcuje ci sa v tabulke mozu nachadzat dva prvky s rovnakym klucom
constructor TIntHashSet.createEx(cap: Integer; loadfactor: Integer = 2; growthfactor: Integer = 4; bUnique: Boolean = true);
var I: Integer;
begin
  inherited create;
  FUnique := bUnique;
  FCount := 0;
  FCapacity := cap;
  FLoadFactor := loadfactor;
  FGrowthFactor := growthfactor;
  SetLength(FBuckets,FCapacity);
  for I := 0 to Pred(FCapacity) do begin
    FBuckets[I] := nil;
  end;
end;

/// konstruktor vytvarajuci objekt typu TIntHashSet so standardnymi hodnotami
constructor TIntHashSet.create(bUnique: Boolean = true);
begin
  createEx(32,2,4,bUnique);
end;

/// konstruktor vytvarajuci objekt typu TIntHashSet so standardnymi hodnotami a
/// sucasne vlozi prvok typu Integer - symbol do mnoziny
constructor TIntHashSet.create(symbol: Integer; bUnique: Boolean = true);
begin
  create(bUnique);
  add(symbol);
end;

/// funkcia vytvarajuca presnu kopiu tejto hasovaej tabulky (klon)
function TIntHashSet.clone: TIntHashSet;
var I: Integer;
    item,previtem: PIntHashSetItem;
begin
  result := TIntHashSet.createEx(FCapacity,FLoadFactor,FGrowthFactor,FUnique);
  for I := 0 to Pred(FCapacity) do begin
    item := FBuckets[I];
    previtem := nil;
    while (item <> nil) do begin
      if previtem <> nil then begin
        new(previtem.next);
        previtem.next^ := item^;
        previtem := previtem.next;
      end
      else begin
        new(result.FBuckets[I]);
        result.FBuckets[I]^ := item^;
        previtem := result.FBuckets[I];
      end;
      if item = FCurrentItem then begin
        result.FCurrentItem := previtem;
        result.FCurrentBucket := I;
      end;
      item := item.next;
    end;
  end;
  result.FCount := FCount;

(*
  result := TIntHashSet.create(FCapacity,4);
  for I := 0 to Pred(FCapacity) do begin
    item := FBuckets[I];
    while (item <> nil) do begin
      result.add(item.key);
      item := item.next;
    end;
  end;
 *)
end;


/// funkcia pridavajuca novy kluc do tabulky
function TIntHashSet.add(key: Integer): Boolean;
var h: Integer;
    item: PIntHashSetItem;
begin
  result := false;
  h := hash(key);
  item := FBuckets[h];
  if item <> nil then begin
    while (item.next <> nil) and ((item.key <> key) or (not FUnique)) do begin
      item := item.next;
    end;
    if ((item.key <> key) or (not FUnique)) then begin
      item.next := new(PIntHashSetItem);
      item.next.key := key;
      item.next.next := nil;
      FCount := FCount + 1;
      result := true;
    end;
  end
  else begin
    FBuckets[h] := new(PIntHashSetItem);
    FBuckets[h].key := key;
    FBuckets[h].next := nil;
    FCount := FCount + 1;
    result := true;
  end;
end;

/// funkcia pridavajuca novy kluc do tabulky, ak taky kluc uz existuje,
/// tak vrati false a tento kluc v premennej key, inak vrati true
function TIntHashSet.addorget(var key: Integer): Boolean;
var h: Integer;
    item: PIntHashSetItem;
begin
  result := false;
  h := hash(key);
  item := FBuckets[h];
  if item <> nil then begin
    while (item.next <> nil) and ((item.key <> key) or (not FUnique)) do begin
      item := item.next;
    end;
    if ((item.key <> key) or (not FUnique)) then begin
      item.next := new(PIntHashSetItem);
      item.next.key := key;
      item.next.next := nil;
      FCount := FCount + 1;
      result := true;
    end
    else begin
      key := item.key;
    end;
  end
  else begin
    FBuckets[h] := new(PIntHashSetItem);
    FBuckets[h].key := key;
    FBuckets[h].next := nil;
    FCount := FCount + 1;
    result := true;
  end;
end;

/// funkcia pridavajuca prvky z danej hasovacej tabulky (mnoziny) - hashset do tejto tabulky
function TIntHashSet.add(hashset: TIntHashSet): Boolean;
var k: Integer;
    olditem: PIntHashSetItem;
    oldbucket: Integer;
begin
  result := false;
  if hashset = nil then
    Exit;
  olditem := hashset.FCurrentItem;
  oldbucket := hashset.FCurrentBucket;
  hashset.getNextReset;
  while hashset.getNext(k) do begin
      result := add(k) or result;
  end;
  hashset.FCurrentItem := olditem;
  hashset.FCurrentBucket := oldbucket;
end;

/// funkcia pridavajuca neepsilonove prvky z danej hasovacej tabulky (mnoziny) - hashset do tejto tabulky
function TIntHashSet.addNonEpsilon(hashset: TIntHashSet): Boolean;
var k: Integer;
    olditem: PIntHashSetItem;
    oldbucket: Integer;
begin
  result := false;
  olditem := hashset.FCurrentItem;
  oldbucket := hashset.FCurrentBucket;
  hashset.getNextReset;
  while hashset.getNext(k) do begin
      if k <> L_EPSILON then
        result := add(k) or result;
  end;
  hashset.FCurrentItem := olditem;
  hashset.FCurrentBucket := oldbucket;
end;

/// funkcia pocitajuca hash pre dany integer, vystupom je DWORD obsahujuci tuto vypocitanu hasovaciu hodnotu
function TIntHashSet.hash(key: Integer): DWORD;
const
  A = 0.6180339887; // (sqrt(5) - 1) / 2
begin
  Result := Abs(Trunc(FCapacity * (Frac(Key * A))));
end;

/// funkcia, ktora vrati velkost hasovacej tabulky (pocet prvkov v nej)
function TIntHashSet.getSize: Integer;
begin
  result := FCount;
end;

/// funkcia vrati true ak tato hasovacia tabulka obsahuje dany kluc
function TIntHashSet.contains(key: Integer): Boolean;
var h: Integer;
    item: PIntHashSetItem;
begin
  result := false;
  h := hash(key);
  item := FBuckets[h];
  while item <> nil do begin
    if item.key = key then begin
      result := true;
      exit;
    end;
    item := item.next;
  end;
end;

/// funkcia vracajuca pocet prvkov v tabulke s danym klucom
function TIntHashSet.count(key: Integer): Integer;
var h: Integer;
    item: PIntHashSetItem;
    c: Integer;
begin
  c := 0;
  h := hash(key);
  item := FBuckets[h];
  while item <> nil do begin
    if item.key = key then begin
      c := c + 1;
    end;
    item := item.next;
  end;
  result := c;
end;

/// funkcia obstranujuca dany kluc z tabulky
function TIntHashSet.remove(key: Integer): Boolean;
var h: Integer;
    item: PIntHashSetItem;
    previtem: PIntHashSetItem;
begin
  result := false;
  h := hash(key);
  item := FBuckets[h];
//  previtem := item;
  if item <> nil then begin
    while (item.key = key) do begin
      result := true;
      previtem := item;
      FBuckets[h] := item.next;
//      item := item.next;
      dispose(previtem);
      FCount := FCount - 1;
      Exit;
    end;
  end;
  if item <> nil then begin
    while item.next <> nil do begin
      while item.next.key = key do begin
        result := true;
        previtem := item.next;
        item.next := item.next.next;
        dispose(previtem);
        FCount := FCount - 1;
        Exit;
      end;
      item := item.next;
    end;
  end;
end;

/// funkcia obstranujuca vsetky prvky z klucom rovnym key z tabulky
function TIntHashSet.removeAll(key: Integer): Boolean;
var h: Integer;
    item: PIntHashSetItem;
    previtem: PIntHashSetItem;
begin
  result := false;
  h := hash(key);
  item := FBuckets[h];
//  previtem := item;
  if item <> nil then begin
    while (item.key = key) do begin
      result := true;
      previtem := item;
      FBuckets[h] := item.next;
      item := item.next;
      dispose(previtem);
      FCount := FCount - 1;
      if item = nil then break;
    end;
  end;
  if item <> nil then begin
    while item.next <> nil do begin
      while item.next.key = key do begin
        result := true;
        previtem := item.next;
        item.next := item.next.next;
        dispose(previtem);
        FCount := FCount - 1;
        if item.next = nil then exit;
      end;
      item := item.next;
    end;
  end;
end;

/// funkcia obstranujuca vsetky prvky z tabulky
procedure TIntHashSet.clear;
var I: Integer;
    item,previtem: PIntHashSetItem;
(*    fullcount: Integer;
begin
  fullcount := 0;
  for I := 0 to Pred(FCapacity) do begin
    item := FBuckets[I];
    while (item <> nil) do begin
      item := item.next;
      fullcount := fullcount + 1;
    end;
  end;

  if fullcount <> FCount then begin
    writeln(fullcount,'~~~~~~~~~~~~~~~~~~~~',FCount);
  end;
*)
begin
  for I := 0 to Pred(FCapacity) do begin
    item := FBuckets[I];
    while (item <> nil) and (FCount > 0) do begin
      previtem := item;
      item := item.next;
      dispose(previtem);
      FCount := FCount - 1;
    end;
    FBuckets[I] := nil;
  end;
  FCount := 0;
end;

/// destruktor uvolnujuci tento objekt z pamate
destructor TIntHashSet.Destroy;
begin
  clear;
  FBuckets := nil;

//  if FCount <> 0 then begin
//    ShowMessage('Assert: Memory leak - HashSet - ' + IntToStr(FCount) + ' items unallocated');
//  end;
end;

/// funkcia vypisujuca tuto tabulku do stringu, bComplex urcuje, ci sa bude vypisovat
/// este detailnejsie
function TIntHashSet.toString(bComplex: Boolean = false): xString;
var h: Integer;
    I: Integer;
    item: PIntHashSetItem;
begin
  result := '';
  for h := 0 to Pred(FCapacity) do begin
    if bComplex then
      result := result + '[' + IntToStr(h) + ']' + EOL;
    item := FBuckets[h];
    I := 0;
    while item <> nil do begin
      if bComplex then
        result := result + '  (' + IntToStr(I) + ')  ' + IntToStr(item.key) + EOL
      else
        result := result + IntToStr(item.key) + ' ';
      item := item.next;
      I := I + 1;
    end;
  end;
end;

/// funkcia vracajuca prvy prvok  v poradi z hasovacej tabulky
function TIntHashSet.getFirst(var key: Integer): Boolean;
var I: Integer;
    item: PIntHashSetItem;
begin
  FCurrentItem := nil;
  FCurrentBucket := -1;
  result := false;

  for I := 0 to Pred(FCapacity) do begin
    item := FBuckets[I];
    if (item <> nil) then begin
      FCurrentItem := item;
      FCurrentBucket := I;
      key := FCurrentItem.key;
      result := true;
      exit;
    end;
  end;
end;

/// funkcia vracajuca nasledovny prvok  v poradi z hasovacej tabulky
function TIntHashSet.getNext(var key: Integer): Boolean;
var I: Integer;
    item: PIntHashSetItem;
begin
  result := false;

  if (FCurrentItem = nil) or (FCurrentBucket = -1) then begin
    result := getFirst(key);
    exit;
  end
(*
  item := FBuckets[FCurrentBucket];
  while (item <> nil) do begin
    if item = FCurrentItem then begin
      if item.next <> nil then begin
        FCurrentItem := item.next;
//          FCurrentBucket := FCurrentBucket;
        result := true;
        exit;
      end;
    end;
    item := item.next;
  end;
*)
  else if FCurrentItem.next <> nil then begin
    FCurrentItem := FCurrentItem.next;
    key := FCurrentItem.key;
    result := true;
    exit;
  end
  else begin
    for I := FCurrentBucket + 1 to Pred(FCapacity) do begin
      item := FBuckets[I];
      if item <> nil then begin
        FCurrentItem := item;
        FCurrentBucket := I;
        key := FCurrentItem.key;
        result := true;
        exit;
      end;
    end;
  end;
end;

/// funkcia vrati true, ak je hasovacia tabulka prazdna, inak false
function TIntHashSet.isEmpty: Boolean;
begin
  result := getSize = 0;
end;

/// funkcia restartujuca ziskavanie prvkov z hasovacej tabulky v poradi za sebou (restartuje iteraciu prvkov)
procedure TIntHashSet.getNextReset;
begin
  FCurrentItem := nil;
  FCurrentBucket := -1;
end;

/// procedura, ktora meni velkost tabulky (na growthfactor nasobok terajsej hodnoty) a
/// prepocitava hasovacie hodnoty vsetkych prvkov v novej tabulke (rehash)
procedure TIntHashSet.rehash(newcapacity: Integer);
var tempset: TIntHashSet;
    I: Integer;
    item: PIntHashSetItem;
begin
  if newcapacity < 1 then
    newcapacity := 1;
  tempset := clone;
  clear;
  FCapacity := newcapacity;
  SetLength(FBuckets,FCapacity);
  for I := 0 to Pred(FCapacity) do begin
    FBuckets[I] := nil;
  end;
  for I := 0 to Pred(tempset.FCapacity) do begin
    item := tempset.FBuckets[I];
    while (item <> nil) do begin
      add(item.key);
      item := item.next;
    end;
  end;
  tempset.Free;
end;

{ TIntIntHashSet }

/// funkcia, ktora splna prototyp hashovacej funkcie, je pouzita v IntIntHashSet objekte,
/// ak nie je definovane inak
function HF_simple(key: Integer; capacity: Integer): DWORD; inline;
const
  A = 0.6180339887; // (sqrt(5) - 1) / 2
begin
  result := Abs(Trunc(capacity * (Frac(key * A))));
end;

/// funkcia, ktora splna prototyp porovnavacej funkcie, je pouzita v IntIntHashSet objekte,
/// ak nie je definovane inak
function CF_simple(key1: Integer; key2: Integer): Boolean; inline;
begin
  result := key1 = key2;
end;

/// konstruktor vytvarajuci objekt typu TIntIntHashSet so vstupnymi parametrami;
/// cap je pocet bucketov, loadfactor je pomer naplnenia prvkami, pri
/// ktorom sa zacne prepracovavat tabulky (rehash), growthfactor je
/// nasobok povodnej hodnoty na ktory velkost hasovacej tabulky narastie;
/// bUnique urcuje ci sa v tabulke mozu nachadzat dva prvky s rovnakym klucom;
/// hashfunction urcuje funkciu splnajucu prototyp hashovacej funkcie, alebo nil (je pouzita standardna);
/// comparefunction urcuje funkciu splnajucu prototyp porovnavacej funkcie, alebo nil (je pouzita standardna)
constructor TIntIntHashSet.createEx(cap: Integer; loadfactor: Integer = 2; growthfactor: Integer = 4; bUnique: Boolean = true; hashfunction: THashFunc = nil; comparefunction: TCompareFunc = nil);
var I: Integer;
begin
  inherited create;
  FUnique := bUnique;
  FCount := 0;
  FCapacity := cap;
  FLoadFactor := loadfactor;
  FGrowthFactor := growthfactor;
  SetLength(FBuckets,FCapacity);
  for I := 0 to Pred(FCapacity) do begin
    FBuckets[I] := nil;
  end;
  if Addr(hashfunction) <> nil then begin
    FHashFunction := hashfunction;
  end
  else begin
    FHashFunction := @HF_simple;
  end;
  if Addr(comparefunction) <> nil then begin
    FCompareFunction := comparefunction;
  end
  else begin
    FCompareFunction := @CF_simple;
  end;
//  FHashFunction(5,FCapacity);
//  HF_simple(5,FCapacity);
end;

/// konstruktor vytvarajuci objekt typu TIntIntHashSet so standardnymi hodnotami
constructor TIntIntHashSet.create(bUnique: Boolean = true; hashfunction: THashFunc = nil; comparefunction: TCompareFunc = nil);
begin
  createEx(32,4,2,bUnique,hashfunction,comparefunction);
end;

/// funkcia pridavajuca novy kluc (key) s hodnotou (data) do tabulky
function TIntIntHashSet.add(key: Integer; data: Integer): Boolean;
var h: Integer;
    item: PIntIntHashSetItem;
begin
  result := false;

  if FCount >= FCapacity * 2 then begin
    rehash(FCapacity * 4);
  end;

  h := hash(key);
  item := FBuckets[h];
  if item <> nil then begin
    while (item.next <> nil) and ((not FUnique) or (not equal(item.key,key))) do begin
      item := item.next;
    end;
    if ((not FUnique) or (not equal(item.key,key))) then begin
      item.next := new(PIntIntHashSetItem);
      item.next.key := key;
      item.next.data := data;
      item.next.next := nil;
      FCount := FCount + 1;
      result := true;
    end
    else begin
//      data := item.data;
    end;
  end
  else begin
    FBuckets[h] := new(PIntIntHashSetItem);
    FBuckets[h].key := key;
    FBuckets[h].data := data;
    FBuckets[h].next := nil;
    FCount := FCount + 1;
    result := true;
  end;
end;

/// funkcia pridavajuca novy kluc (key) s hodnotou (data) do tabulky, ak taky kluc uz existuje,
/// tak vrati false a tento kluc v premennej key a jeho hodnotu v premennej data, inak vrati true
function TIntIntHashSet.addorget(var key: Integer; var data: Integer): Boolean;
var h: Integer;
    item: PIntIntHashSetItem;
begin
  result := false;

  if FCount >= FCapacity * 2 then begin
    rehash(FCapacity * 4);
  end;

  h := hash(key);
  item := FBuckets[h];
  if item <> nil then begin
    while (item.next <> nil) and ((not FUnique) or (not equal(item.key,key))) do begin
      item := item.next;
    end;
    if ((not FUnique) or (not equal(item.key,key))) then begin
      item.next := new(PIntIntHashSetItem);
      item.next.key := key;
      item.next.data := data;
      item.next.next := nil;
      FCount := FCount + 1;
      result := true;
    end
    else begin
      key := item.key;
      data := item.data;
    end;
  end
  else begin
    FBuckets[h] := new(PIntIntHashSetItem);
    FBuckets[h].key := key;
    FBuckets[h].data := data;
    FBuckets[h].next := nil;
    FCount := FCount + 1;
    result := true;
  end;
end;

/// funkcia pocitajuca hash pre dany kluc, vola funkciu pre hasovanie definovanu pri
/// vytvarani objektu
function TIntIntHashSet.hash(key: Integer): DWORD;
begin
  result := FHashFunction(key,FCapacity);
end;

/// funkcia pocitajuca zhodu pre dane kluce, vola funkciu pre porovnavanie definovanu pri
/// vytvarani objektu
function TIntIntHashSet.equal(key1: Integer; key2: Integer): Boolean;
begin
  result := FCompareFunction(key1,key2);
end;

/// funkcia, ktora vrati velkost hasovacej tabulky (pocet prvkov v nej)
function TIntIntHashSet.getSize: Integer;
begin
  result := FCount;
end;

/// funkcia vrati true ak tato hasovacia tabulka obsahuje dany kluc
function TIntIntHashSet.contains(key: Integer): Boolean;
var h: Integer;
    item: PIntIntHashSetItem;
begin
  result := false;
  h := hash(key);
  item := FBuckets[h];
  while item <> nil do begin
    if equal(item.key,key) then begin
      result := true;
      exit;
    end;
    item := item.next;
  end;
end;

/// funkcia vracajuca pocet prvkov v tabulke s danym klucom
function TIntIntHashSet.count(key: Integer): Integer;
var h: Integer;
    item: PIntIntHashSetItem;
    c: Integer;
begin
  c := 0;
  h := hash(key);
  item := FBuckets[h];
  while item <> nil do begin
    if equal(item.key,key) then begin
      c := c + 1;
    end;
    item := item.next;
  end;
  result := c;
end;

/// funkcia obstranujuca dany kluc z tabulky
function TIntIntHashSet.remove(key: Integer): Boolean;
var h: Integer;
    item: PIntIntHashSetItem;
    previtem: PIntIntHashSetItem;
begin
  result := false;
  h := hash(key);
  item := FBuckets[h];
//  previtem := item;
  if item <> nil then begin
    while (equal(item.key,key)) do begin
      result := true;
      previtem := item;
      FBuckets[h] := item.next;
//      item := item.next;
      dispose(previtem);
      FCount := FCount - 1;
      Exit;
    end;
  end;
  if item <> nil then begin
    while item.next <> nil do begin
      while equal(item.next.key,key) do begin
        result := true;
        previtem := item.next;
        item.next := item.next.next;
        dispose(previtem);
        FCount := FCount - 1;
        Exit;
      end;
      item := item.next;
    end;
  end;
end;

/// funkcia obstranujuca dany kluc z tabulky a vracajuca jeho hodnotu v data
/// celkovo funkcia vrati true ak bol dany kluc najdeny a vymazany, inak vrati false
function TIntIntHashSet.removeandget(key: Integer;var data: Integer): Boolean;
var h: Integer;
    item: PIntIntHashSetItem;
    previtem: PIntIntHashSetItem;
begin
  result := false;
  h := hash(key);
  item := FBuckets[h];
//  previtem := item;
  if item <> nil then begin
    while (equal(item.key,key)) do begin
      result := true;
      previtem := item;
      FBuckets[h] := item.next;
//      item := item.next;
      data := previtem.data;
      dispose(previtem);
      FCount := FCount - 1;
      Exit;
    end;
  end;
  if item <> nil then begin
    while item.next <> nil do begin
      while equal(item.next.key,key) do begin
        result := true;
        previtem := item.next;
        item.next := item.next.next;
        data := previtem.data;
        dispose(previtem);
        FCount := FCount - 1;
        Exit;
      end;
      item := item.next;
    end;
  end;
end;

/// funkcia obstranujuca vsetky prvky z klucom rovnym key z tabulky
function TIntIntHashSet.removeAll(key: Integer): Boolean;
var h: Integer;
    item: PIntIntHashSetItem;
    previtem: PIntIntHashSetItem;
begin
  result := false;
  h := hash(key);
  item := FBuckets[h];
//  previtem := item;
  if item <> nil then begin
    while (equal(item.key,key)) do begin
      result := true;
      previtem := item;
      FBuckets[h] := item.next;
      item := item.next;
      dispose(previtem);
      FCount := FCount - 1;
      if item = nil then break;
    end;
  end;
  if item <> nil then begin
    while item.next <> nil do begin
      while equal(item.next.key,key) do begin
        result := true;
        previtem := item.next;
        item.next := item.next.next;
        dispose(previtem);
        FCount := FCount - 1;
        if item.next = nil then exit;
      end;
      item := item.next;
    end;
  end;
end;

/// funkcia obstranujuca vsetky prvky z tabulky
procedure TIntIntHashSet.clear;
var I: Integer;
    item,previtem: PIntIntHashSetItem;
begin
  for I := 0 to Pred(FCapacity) do begin
    item := FBuckets[I];
    while (item <> nil) and (FCount > 0) do begin
      previtem := item;
      item := item.next;
      dispose(previtem);
      FCount := FCount - 1;
    end;
    FBuckets[I] := nil;
  end;
  FCount := 0;
end;

/// destruktor uvolnujuci tento objekt z pamate
destructor TIntIntHashSet.Destroy;
begin
  clear;
  FBuckets := nil;

//  if FCount <> 0 then begin
//    ShowMessage('Assert: Memory leak - HashSet - ' + IntToStr(FCount) + ' items unallocated');
//  end;
end;

/// funkcia vypisujuca tuto tabulku do stringu, bComplex urcuje, ci sa bude vypisovat
function TIntIntHashSet.toString(bComplex: Boolean = false): xString;
var h: Integer;
    I: Integer;
    item: PIntIntHashSetItem;
begin
  result := '';
  for h := 0 to Pred(FCapacity) do begin
    if bComplex then
      result := result + '[' + IntToStr(h) + ']' + EOL;
    item := FBuckets[h];
    I := 0;
    while item <> nil do begin
      if bComplex then
        result := result + '  (' + IntToStr(I) + ')  ' + IntToStr(item.key) + ' - ' + IntToStr(item.data) + EOL
      else
        result := result + IntToStr(item.key) + ' - ' + IntToStr(item.data) + ' ';
      item := item.next;
      I := I + 1;
    end;
  end;
end;

/// funkcia vracajuca prvy prvok (jeho kluc a hodnotu) v poradi z hasovacej tabulky
function TIntIntHashSet.getFirst(var key: Integer;var data: Integer): Boolean;
var I: Integer;
    item: PIntIntHashSetItem;
begin
  FCurrentItem := nil;
  FCurrentBucket := -1;
  result := false;

  for I := 0 to Pred(FCapacity) do begin
    item := FBuckets[I];
    if (item <> nil) then begin
      FCurrentItem := item;
      FCurrentBucket := I;
      key := FCurrentItem.key;
      data := FCurrentItem.data;
      result := true;
      exit;
    end;
  end;
end;

/// funkcia vracajuca nasledovny prvok (jeho kluc a hodnotu) v poradi z hasovacej tabulky
function TIntIntHashSet.getNext(var key: Integer;var data: Integer): Boolean;
var I: Integer;
    item: PIntIntHashSetItem;
begin
  result := false;

  if (FCurrentItem = nil) or (FCurrentBucket = -1) then begin
    result := getFirst(key,data);
    exit;
  end
(*
  item := FBuckets[FCurrentBucket];
  while (item <> nil) do begin
    if item = FCurrentItem then begin
      if item.next <> nil then begin
        FCurrentItem := item.next;
//          FCurrentBucket := FCurrentBucket;
        result := true;
        exit;
      end;
    end;
    item := item.next;
  end;
*)
  else if FCurrentItem.next <> nil then begin
    FCurrentItem := FCurrentItem.next;
    key := FCurrentItem.key;
    data := FCurrentItem.data;
    result := true;
    exit;
  end
  else begin
    for I := FCurrentBucket + 1 to Pred(FCapacity) do begin
      item := FBuckets[I];
      if item <> nil then begin
        FCurrentItem := item;
        FCurrentBucket := I;
        key := FCurrentItem.key;
        data := FCurrentItem.data;
        result := true;
        exit;
      end;
    end;
  end;
end;

/// funkcia vrati true, ak je hasovacia tabulka prazdna, inak false
function TIntIntHashSet.isEmpty: Boolean;
begin
  result := getSize = 0;
end;

/// funkcia restartujuca ziskavanie prvkov z hasovacej tabulky v poradi za sebou (restartuje iteraciu prvkov)
procedure TIntIntHashSet.getNextReset;
begin
  FCurrentItem := nil;
  FCurrentBucket := -1;
end;

/// funkcia vracajuca hodnotu daneho kluca, ak sa dany kluc v tabulke nenachadza vrati false, inak true
function TIntIntHashSet.get(key: Integer; var data: Integer): Boolean;
var h: Integer;
    item: PIntIntHashSetItem;
begin
  result := false;
  h := hash(key);
  item := FBuckets[h];
  while (item <> nil) do begin
    if equal(item.key,key) then begin
      data := item.data;
      result := true;
      exit;
    end;
    item := item.next;
  end;
end;

/// funkcia vytvarajuca presnu kopiu tejto hasovaej tabulky (klon)
function TIntIntHashSet.clone: TIntIntHashSet;
var I: Integer;
    item,previtem: PIntIntHashSetItem;
begin
  result := TIntIntHashSet.createEx(FCapacity,FLoadFactor,FGrowthFactor,FUnique,FHashFunction,FCompareFunction);
  for I := 0 to Pred(FCapacity) do begin
    item := FBuckets[I];
    previtem := nil;
    while (item <> nil) do begin
      if previtem <> nil then begin
        new(previtem.next);
        previtem.next^ := item^;
        previtem := previtem.next;
      end
      else begin
        new(result.FBuckets[I]);
        result.FBuckets[I]^ := item^;
        previtem := result.FBuckets[I];
      end;
      if item = FCurrentItem then begin
        result.FCurrentItem := previtem;
        result.FCurrentBucket := I;
      end;
      item := item.next;
    end;
  end;
  result.FCount := FCount;
end;

/// procedura, ktora meni velkost tabulky (na growthfactor nasobok terajsej hodnoty) a
/// prepocitava hasovacie hodnoty vsetkych prvkov v novej tabulke (rehash)
procedure TIntIntHashSet.rehash(newcapacity: Integer);
var tempset: TIntIntHashSet;
    I: Integer;
    item: PIntIntHashSetItem;
begin
  if newcapacity < 1 then
    newcapacity := 1;
  tempset := clone;
  clear;
  FCapacity := newcapacity;
  SetLength(FBuckets,FCapacity);
  for I := 0 to Pred(FCapacity) do begin
    FBuckets[I] := nil;
  end;
  for I := 0 to Pred(tempset.FCapacity) do begin
    item := tempset.FBuckets[I];
    while (item <> nil) do begin
      add(item.key,item.data);
      item := item.next;
    end;
  end;
  tempset.Free;
end;

end.
