unit QuadC;
//*******************************************************
// Hash table with open addressing and quadratic probing
// class.
//*******************************************************
// Copyright (C) 1998 John Wiley & Sons, Inc.
// All rights reserved. See additional copyright
// information in Readme.txt.
//*******************************************************

interface

uses
    SysUtils;

const
    UNUSED = -2147483647;

type
    TQuadraticReturnValue =
        (qInserted, qFound, qNotFound, qTableFull);

    // The table's data type.
    TTableData = Longint;
    TDataArray = array [0..1000000] of TTableData;
    PDataArray = ^TDataArray;

    TQuadraticHashTable = class(TObject)
        private
            TableSize : Integer;    // Total number allocated.
            NumUnused : Integer;    // Number still unused.
            HashTable : PDataArray; // The hash table array.
            function FindOrInsert(value : TTableData; var probes : Integer; insert : Boolean) : TQuadraticReturnValue;

        public
            destructor Destroy; override;
            procedure CreateTable(table_size : Integer);
            function InsertItem(value : TTableData; var probes : Integer) : TQuadraticReturnValue;
            function LocateItem(value : TTableData; var probes : Integer) : TQuadraticReturnValue;
            function NumItems : Integer;
            function TableValue(pos : Integer) : TTableData;
    end;

implementation

// Free dynamically allocated memory.
destructor TQuadraticHashTable.Destroy;
begin
    if (TableSize > 0) then FreeMem(HashTable);
    inherited Destroy;
end;

// Create a new hash table.
procedure TQuadraticHashTable.CreateTable(table_size : Integer);
var
    i : Integer;
begin
    // Free old memory.
    if (TableSize > 0) then FreeMem(HashTable);

    TableSize := table_size;
    GetMem(HashTable, TableSize * SizeOf(TTableData));

    // Set all entries to UNUSED.
    for i := 0 to TableSize - 1 do HashTable^[i] := UNUSED;
    NumUnused := TableSize;
end;

// Insert an item in a hash table. Return qFound if the
// item is already in the table, qInserted if we insert
// the value, and qTableFull if there is no room.
function TQuadraticHashTable.InsertItem(value : TTableData; var probes : Integer) : TQuadraticReturnValue;
begin
    Result := FindOrInsert(value, probes, True);
end;

// Locate an item in a hash table.
function TQuadraticHashTable.LocateItem(value : TTableData; var probes : Integer) : TQuadraticReturnValue;
begin
    Result := FindOrInsert(value, probes, False);
end;

// Find the item if it is present. Otherwise insert it if
// insert is true.
function TQuadraticHashTable.FindOrInsert(value : TTableData; var probes : Integer; insert : Boolean) : TQuadraticReturnValue;
var
    new_value : TTableData;
    pos       : Integer;
begin
    probes := 1;
    pos := (value mod TableSize);
    repeat // Repeat infinitely.
        new_value := HashTable^[pos];

        // If we found the value, we're done.
        if (new_value = value) then
        begin
            Result := qFound;
            exit;
        end;

        // If the entry is unused, the value belongs here.
        if (new_value = UNUSED) then
        begin
            if (insert) then
            begin
                HashTable^[pos] := value;
                Result := qInserted;
                NumUnused := NumUnused - 1;
            end else begin
                Result := qNotFound;
            end;
            exit;
        end;

        // Try the next location in the probe sequence.
        pos := (value + probes * probes) mod TableSize;
        probes := probes + 1;

        // See if we have checked every entry.
        if (probes > TableSize) then
        begin
            if (insert) then
                Result := qTableFull
            else
                Result := qNotFound;
            exit;
        end;
    until (False); // End infinite loop looking for the value.
end;

// Return the number of items in the hash table.
function TQuadraticHashTable.NumItems : Integer;
begin
    Result := TableSize;
end;

// Return the value in the indicated position.
function TQuadraticHashTable.TableValue(pos : Integer) : TTableData;
begin
    Result := HashTable^[pos];
end;

end.
