ADTDictionary

Dictionary which implementes an extensible hash table.

Two types are implemented

DictionaryStrInt (STRING key and LONGINT value)
DictionaryStrStr (STRING key and STRING value)

Other types can be implemented by method of type extension. Note that this solution comes with a overhead (~2x) and if speed is needed it should be implemented as stand alone.

Adapted from Ben Hoyt article about hash tables. License is MIT.

Const

INITIAL_CAPACITY* = 32;

Types

DictionaryEntry* = POINTER TO DictionaryEntryDesc;

DictionaryEntryDesc* = RECORD
        deleted* : BOOLEAN;
    END;

DictionaryEntryStorage* = POINTER TO ARRAY OF DictionaryEntry;

Dictionary* = POINTER TO DictionaryDesc;

DictionaryDesc* = RECORD
        storage : DictionaryEntryStorage;
        capacity : LONGINT;
        size : LONGINT;
    END;

DictionaryIterator* = POINTER TO DictionaryIteratorDesc;

DictionaryIteratorDesc* = RECORD
        dictionary* : Dictionary;
        entry* : DictionaryEntry;
        index* : LONGINT;
    END;

StringIntEntry* = POINTER TO StringIntEntryDesc;

DictionaryStrInt* = POINTER TO DictionaryStrIntDesc;

DictionaryStrIntIterator* = POINTER TO DictionaryStrIntIteratorDesc;

StrStrEntry* = POINTER TO StrStrEntryDesc;

DictionaryStrStr* = POINTER TO DictionaryStrStrDesc;

DictionaryStrStrIterator* = POINTER TO DictionaryStrStrIteratorDesc;

Procedures

Dictionary.Init

Initialize dictionary storage to given capacity. Default to INITIAL_CAPACITY. Capacity will be rounded up to nearest exponent of 2 size, 64, 256, 512 etc.

PROCEDURE (this : Dictionary) Init*(capacity := INITIAL_CAPACITY : LONGINT);

Dictionary.IHasKey

Internal HasKey method. Implemented with concrete entry types in subclass.

PROCEDURE (this : Dictionary) IHasKey*(VAR entry : DictionaryEntryDesc): BOOLEAN;

Dictionary.IGet

Internal get method. Implemented with concrete entry types in subclass.

PROCEDURE (this : Dictionary) IGet*(VAR entry : DictionaryEntryDesc): BOOLEAN;

Dictionary.Clear

Clear entries without deallocation

PROCEDURE (this : Dictionary) Clear*();

Dictionary.ISet

Internal set method. Implemented with concrete entry types in subclass.

PROCEDURE (this : Dictionary) ISet*(VAR entry : DictionaryEntryDesc): BOOLEAN;

Dictionary.IDeleteEntry

Internal delete method. Implemented with concrete entry types in subclass. https://en.wikipedia.org/wiki/Linear_probing#Deletion

PROCEDURE (this : Dictionary) IDeleteEntry*(VAR entry : DictionaryEntryDesc): BOOLEAN;

DictionaryIterator.Next

Advance iterator. Return FALSE if end is reached.

PROCEDURE (this : DictionaryIterator) Next*() : BOOLEAN;

DictionaryIterator.Reset

Reset iterator to start of dictionary.

PROCEDURE (this : DictionaryIterator) Reset*();

DictionaryStrInt.HasKey

Return TRUE if dictionary has given key

PROCEDURE (this : DictionaryStrInt) HasKey*(key- : ARRAY OF CHAR): BOOLEAN;

DictionaryStrInt.SetEntry

Set or update entry

PROCEDURE (this : DictionaryStrInt) SetEntry*(entry : StringIntEntry): BOOLEAN;

DictionaryStrInt.Set

Set or update key with value

PROCEDURE (this : DictionaryStrInt) Set*(key- : ARRAY OF CHAR; value : LONGINT): BOOLEAN;

DictionaryStrInt.GetEntry

Get entry. Return TRUE if entry exists

PROCEDURE (this : DictionaryStrInt) GetEntry*(entry : StringIntEntry): BOOLEAN;

DictionaryStrInt.Get

Get value from key. Return TRUE if entry exists

PROCEDURE (this : DictionaryStrInt) Get*(key- : ARRAY OF CHAR; VAR value : LONGINT): BOOLEAN;

DictionaryStrInt.Delete

Mark entry as deleted. Return TRUE if entry exists

PROCEDURE (this : DictionaryStrInt) Delete*(key- : ARRAY OF CHAR): BOOLEAN;

DictionaryStrInt.Iterator

Get dictionary iterator

PROCEDURE (this : DictionaryStrInt) Iterator*(): DictionaryStrIntIterator;

DictionaryStrIntIterator.Key

Get current iterator entry’s key

PROCEDURE (this : DictionaryStrIntIterator) Key*(): S.STRING;

DictionaryStrIntIterator.Value

Get current iterator entry’s value

PROCEDURE (this : DictionaryStrIntIterator) Value*(): LONGINT;

DictionaryStrInt.Keys

Return Vector of keys

PROCEDURE (this : DictionaryStrInt) Keys*(): Vector.VectorOfString;

DictionaryStrStr.HasKey

Return TRUE if dictionary has given key

PROCEDURE (this : DictionaryStrStr) HasKey*(key- : ARRAY OF CHAR): BOOLEAN;

DictionaryStrStr.SetEntry

Set or update entry

PROCEDURE (this : DictionaryStrStr) SetEntry*(entry : StrStrEntry): BOOLEAN;

DictionaryStrStr.Set

Set or update key with value

PROCEDURE (this : DictionaryStrStr) Set*(key- : ARRAY OF CHAR; value- : ARRAY OF CHAR): BOOLEAN;

DictionaryStrStr.GetEntry

Get entry. Return TRUE if entry exists

PROCEDURE (this : DictionaryStrStr) GetEntry*(entry : StrStrEntry): BOOLEAN;

DictionaryStrStr.Get

Get value from key. Return TRUE if entry exists

PROCEDURE (this : DictionaryStrStr) Get*(key- : ARRAY OF CHAR; VAR value : S.STRING): BOOLEAN;

DictionaryStrStr.Delete

Mark entry as deleted. Return TRUE if entry exists

PROCEDURE (this : DictionaryStrStr) Delete*(key- : ARRAY OF CHAR): BOOLEAN;

DictionaryStrStr.Iterator

Get dictionary iterator

PROCEDURE (this : DictionaryStrStr) Iterator*(): DictionaryStrStrIterator;

DictionaryStrStrIterator.Key

Get current iterator entry’s key

PROCEDURE (this : DictionaryStrStrIterator) Key*(): S.STRING;

DictionaryStrStrIterator.Value

Get current iterator entry’s value

PROCEDURE (this : DictionaryStrStrIterator) Value*(): S.STRING;

DictionaryStrStr.Keys

Return Vector of keys

PROCEDURE (this : DictionaryStrStr) Keys*(): Vector.VectorOfString;