unit LinearC;
//*******************************************************
// Hash table with open addressing hash and linear
// 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
    TLinearReturnValue =
        (linInserted, linFound, linNotFound, linTableFull);

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

    TLinearHashTable = 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) : TLinearReturnValue;

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

implementation

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

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

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

// Find the item if it is present. Otherwise insert it if
// insert is true.
function TLinearHashTable.FindOrInsert(value : TTableData; var probes : Integer; insert : Boolean) : TLinearReturnValue;
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 := linFound;
            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 := linInserted;
                NumUnused := NumUnused - 1;
            end else begin
                Result := linNotFound;
            end;
            exit;
        end;

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

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

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

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

end.
