unit RandC;
//*******************************************************
// Hash table with open addressing and pseudo-random
// 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
    TRandomReturnValue =
        (rndInserted, rndFound, rndNotFound, rndTableFull);

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

    TRandomHashTable = 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) : TRandomReturnValue;

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

implementation

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

// Create a new hash table.
procedure TRandomHashTable.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 rndFound if the
// item is already in the table, rndInserted if we insert
// the value, and rndTableFull if there is no room.
function TRandomHashTable.InsertItem(value : TTableData; var probes : Integer) : TRandomReturnValue;
begin
    Result := FindOrInsert(value, probes, True);
end;

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

// Find the item if it is present. Otherwise insert it if
// insert is true.
function TRandomHashTable.FindOrInsert(value : TTableData; var probes : Integer; insert : Boolean) : TRandomReturnValue;
var
    new_value : TTableData;
    pos       : Integer;
begin
    // Seed the random number generator.
    RandSeed := value;

    probes := 0;
    repeat // Repeat infinitely.
        // Generate the next value in the pseudo-random
        // probe sequence.
        pos := Random(TableSize);
        probes := probes + 1;
        new_value := HashTable^[pos];

        // If we found the value, we're done.
        if (new_value = value) then
        begin
            Result := rndFound;
            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 := rndInserted;
                NumUnused := NumUnused - 1;
            end else begin
                Result := rndNotFound;
            end;
            exit;
        end;

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

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

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

end.
