unit LinearF;
//*******************************************************
// Example program demonstrating a hash table with open
// addressing and linear probing.
//*******************************************************
// Copyright (C) 1998 John Wiley & Sons, Inc.
// All rights reserved. See additional copyright
// information in Readme.txt.
//*******************************************************

interface

uses
  Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,
  Menus, StdCtrls,
  LinearC;

type
  TLinearForm = class(TForm)
    Frame2: TGroupBox;
    Label1_0: TLabel;
    NewItemText: TEdit;
    CmdAdd: TButton;
    CmdFind: TButton;
    Frame3: TGroupBox;
    Label1_6: TLabel;
    Label1_2: TLabel;
    NumItemsText: TEdit;
    MaxValueText: TEdit;
    CmdCreateItems: TButton;
    Frame1: TGroupBox;
    Label1_3: TLabel;
    CmdCreateTable: TButton;
    TableSizeText: TEdit;
    StatusLabel: TLabel;
    MainMenu1: TMainMenu;
    mnuFile: TMenuItem;
    mnuFileExit: TMenuItem;
    mnuHelp: TMenuItem;
    mnuHelpAbout: TMenuItem;
    procedure FormCreate(Sender: TObject);
    procedure mnuFileExitClick(Sender: TObject);
    procedure mnuHelpAboutClick(Sender: TObject);
    procedure CmdCreateTableClick(Sender: TObject);
    procedure CmdCreateItemsClick(Sender: TObject);
    procedure CmdAddClick(Sender: TObject);
    procedure CmdFindClick(Sender: TObject);
    procedure DisplayStatus(msg : String; probes : Integer);
    procedure ComputeAverageProbe(var ave_succ, ave_unsucc : Single);
    procedure TableSizeTextChange(Sender: TObject);
    procedure NewItemTextChange(Sender: TObject);
    procedure FormPaint(Sender: TObject);
  private
    { Private declarations }
    MaxValue     : TTableData;
    HashTable    : TLinearHashTable;
    SelectedItem : TTableData;
  public
    { Public declarations }
    destructor Destroy; override;
  end;

var
  LinearForm: TLinearForm;

implementation

{$R *.DFM}

// Create the hash table.
procedure TLinearForm.FormCreate(Sender: TObject);
begin
    Randomize;

    HashTable := TLinearHashTable.Create;
end;

// Free the hash table.
destructor TLinearForm.Destroy;
begin
    HashTable.Free;
    inherited Destroy;
end;

procedure TLinearForm.mnuFileExitClick(Sender: TObject);
begin
    Close;
end;

procedure TLinearForm.mnuHelpAboutClick(Sender: TObject);
const
    CRCR = #13#10#13#10;
begin
    MessageDlg(
        'This program demonstrates open addressing with linear probing. The main areas on the form are:' + CRCR +
        'Table Creation: Enter the size of the table and click the Create Table button to create a new hash table.' + CRCR +
        'Random Items: Enter the number and maximum value of the random items you want and click the Create Items button.' + CRCR +
        'Search: Enter a value and click the Add button to add the value to the table. Click the Find button to locate the value.' + CRCR +
        'To see the primary clustering effect, create a 100 entry table and add 50 random items. Note that most of the the items are grouped in clusters.'
        , mtInformation, [mbOK], 0);
end;

// Create a new hash table.
procedure TLinearForm.CmdCreateTableClick(Sender: TObject);
begin
    Screen.Cursor := crHourGlass;

    // This makes the HashTable create the lists.
    HashTable.CreateTable(StrToInt(TableSizeText.Text));

    MaxValue := 1;
    StatusLabel.Caption := 'Table created.';
    CmdCreateItems.Enabled := True;
    Screen.Cursor := crDefault;
    SelectedItem := -1;
    Refresh;
end;

// Add random items to the hash table.
procedure TLinearForm.CmdCreateItemsClick(Sender: TObject);
var
    num, created, probes : Integer;
    value, max_value     : TTableData;
begin
    max_value := StrToInt(MaxValueText.Text);
    num := StrToInt(NumItemsText.Text);
    if (max_value < num) then
    begin
        ShowMessage('Max Value is too small.');
        exit;
    end;

    Screen.Cursor := crHourGlass;
    created := 0; // The number we have created.
    while (created < num) do
    begin
        value := Trunc(Random(max_value) + 1);
        if (value > MaxValue) then MaxValue := value;
        case HashTable.InsertItem(value, probes) of
            linInserted:
                created := created + 1;
            linTableFull:
                break;
        end;
    end;
    DisplayStatus('Done.', probes);

    Screen.Cursor := crDefault;
    SelectedItem := -1;
    Refresh;
end;

// Add an item to the hash table.
procedure TLinearForm.CmdAddClick(Sender: TObject);
var
    probes : Integer;
    value  : TTableData;
    status : TLinearReturnValue;
begin
    Screen.Cursor := crHourGlass;

    value := StrToInt(NewItemText.Text);
    if (value > MaxValue) then MaxValue := value;

    // Insert the item.
    status := HashTable.InsertItem(value, probes);
    case status of
        linFound:
            DisplayStatus('Found.', probes);
        linInserted:
            DisplayStatus('Inserted.', probes);
        linTableFull:
            DisplayStatus('Table full.', probes);
    end;

    Screen.Cursor := crDefault;
    SelectedItem := value;
    Refresh;
end;

// Findn an item in the hash table.
procedure TLinearForm.CmdFindClick(Sender: TObject);
var
    value  : TTableData;
    probes : Integer;
    status : TLinearReturnValue;
begin
    Screen.Cursor := crHourGlass;

    value := StrToInt(NewItemText.Text);
    if (value > MaxValue) then MaxValue := value;

    status := HashTable.LocateItem(value, probes);
    case status of
        linNotFound:
            DisplayStatus('Not found.', probes);
        linFound:
            DisplayStatus('Found.', probes);
    end;

    Screen.Cursor := crDefault;
    SelectedItem := value;
    Refresh;
end;

// Display a status message.
procedure TLinearForm.DisplayStatus(msg : String; probes : Integer);
const
    CR = #13#10;
var
    ave_succ, ave_unsucc : single;
begin
    ComputeAverageProbe(ave_succ, ave_unsucc);
    StatusLabel.Caption := msg + CR +
        Format('This probe: %d.', [probes]) + CR +
        Format('Ave successful probe: %.2f.', [ave_succ]) + CR +
        Format('Ave unsuccessful probe: %.2f.', [ave_unsucc]);
end;

// Compute the average lengths of probe sequences.
procedure TLinearForm.ComputeAverageProbe(var ave_succ, ave_unsucc : Single);
var
    status                         : TLinearReturnValue;
    trial, probes                  : Integer;
    succ_searches, succ_probes     : Integer;
    unsucc_searches, unsucc_probes : Integer;
begin
    succ_searches := 0;
    succ_probes := 0;
    unsucc_searches := 0;
    unsucc_probes := 0;
    for trial := 1 to MaxValue do
    begin
        status := HashTable.LocateItem(trial, probes);
        if (status = linFound) then
        begin
            succ_searches := succ_searches + 1;
            succ_probes := succ_probes + probes;
        end else begin
            unsucc_searches := unsucc_searches + 1;
            unsucc_probes := unsucc_probes + probes;
        end;
    end;

    if (succ_searches > 0) then
        ave_succ := succ_probes / succ_searches
    else
        ave_succ := 0;
    if (unsucc_searches > 0) then
        ave_unsucc := unsucc_probes / unsucc_searches
    else
        ave_unsucc := 0;
end;

procedure TLinearForm.TableSizeTextChange(Sender: TObject);
begin
    CmdCreateTable.Enabled := (TableSizeText.Text <> '');
end;

procedure TLinearForm.NewItemTextChange(Sender: TObject);
begin
    CmdAdd.Enabled := (NewItemText.Text <> '');
    CmdFind.Enabled := CmdAdd.Enabled;
end;

// Display the table highlighting SelectedItem.
procedure TLinearForm.FormPaint(Sender: TObject);
const
    WID = 27;
    HGT = 17;
var
    i, x0, x, y, bx, by : Integer;
    value               : TTableData;
    txt                 : String;
    rect                : TRect;
    size                : TSize;
begin
    rect.Left := 0;
    rect.Right := ClientWidth;
    rect.Top := 0;
    rect.Bottom := ClientHeight;
    Canvas.Brush.Color := Brush.Color;
    Canvas.FillRect(rect);

    if (HashTable.NumItems < 1) then exit;

    // Draw headings for the columns.
    x0 := Frame1.Left + Frame1.Width + 5;
    x := x0;
    y := 0;
    for i := 0 to 9 do
    begin
        Canvas.TextOut(x, y, Format('%3d', [i]));
        x := x + WID;
    end;

    // Display the table values.
    x := x0;
    y := y + Round(1.5 * HGT);
    for i := 0 to HashTable.NumItems - 1 do
    begin
        value := HashTable.TableValue(i);
        if (value = UNUSED) then
            txt := '---'
        else
            txt := Format('%3d', [value]);

        // Draw a box around it if it's selected.
        if (value = SelectedItem) then
        begin
            size := Canvas.TextExtent(txt);
            bx := x + (size.cx - WID) div 2;
            by := y + (size.cy - HGT) div 2;
            Canvas.Rectangle(bx, by, bx + WID, by + HGT);
        end;

        Canvas.TextOut(x, y, txt);

        if (i mod 10 = 9) then
        begin
            x := x0;
            y := y + HGT;
        end else
            x := x + WID;
    end;
end;

end.
