unit HeadedQF;
//*******************************************************
// Example program demonstrating multi-headed versus
// single-headed queues.
//*******************************************************
// 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, ExtCtrls,
  HeadedQC;

type
    TLabelArray = array[1..100000000] of TLabel;
    PLabelArray = ^TLabelArray;
    TQueueArray = array[1..100000000] of TMultiQueue;
    PQueueArray = ^TQueueArray;
    TCustomerArray = array[1..100000000] of PCustomer;
    PCustomerArray = ^TCustomerArray;

  THeadedQForm = class(TForm)
    GroupBox1: TGroupBox;
    Label1: TLabel;
    MainMenu1: TMainMenu;
    File1: TMenuItem;
    mnuExit: TMenuItem;
    Help1: TMenuItem;
    mnuAbout: TMenuItem;
    Label2: TLabel;
    Label3: TLabel;
    Label4: TLabel;
    CPHEdit: TEdit;
    MinTimeEdit: TEdit;
    MaxTimeEdit: TEdit;
    ClerksEdit: TEdit;
    Pause: TLabel;
    IntervalEdit: TEdit;
    CmdBuildQueues: TButton;
    CmdStart: TButton;
    TimeLabel: TLabel;
    Label5: TLabel;
    MultiGroup: TGroupBox;
    SingleGroup: TGroupBox;
    MClerkHeader: TLabel;
    MCustHeader: TLabel;
    SCustHeader: TLabel;
    SClerkHeader: TLabel;
    Label10: TLabel;
    SWaitHeader: TLabel;
    MWaitLabel: TLabel;
    Label6: TLabel;
    MAveLabel: TLabel;
    MMaxLabel: TLabel;
    Label8: TLabel;
    Label11: TLabel;
    MBusyLabel: TLabel;
    Label13: TLabel;
    SAveLabel: TLabel;
    SMaxLabel: TLabel;
    Label16: TLabel;
    Label17: TLabel;
    SBusyLabel: TLabel;
    QueueTimer: TTimer;
    MNumWaitingLabel: TLabel;
    SNumWaitingLabel: TLabel;
    procedure mnuExitClick(Sender: TObject);
    procedure CPHEditKeyPress(Sender: TObject; var Key: Char);
    procedure CmdBuildQueuesClick(Sender: TObject);
    procedure CPHEditChange(Sender: TObject);
    procedure AllocateLabels(group : TGroupBox;
        var arr : PLabelArray; num, l, w, t : Integer;
        the_alignment : TAlignment);
    procedure CmdStartClick(Sender: TObject);
    procedure QueueTimerTimer(Sender: TObject);
    procedure FormCreate(Sender: TObject);
    procedure mnuAboutClick(Sender: TObject);
  private
    { Private declarations }
  public
    { Public declarations }
  end;

var
  HeadedQForm: THeadedQForm;

implementation

var
    max_clerks, num_clerks                 : Integer;
    min_time, time_range                   : Integer;
    cust_prob                              : Single;
    MClerkLabels, MCustLabels              : PLabelArray;
    SClerkLabels, SCustLabels, SWaitLabels : PLabelArray;
    Running                                : Boolean;

    // Simulation variables.
    EllapsedTime  : Longint; // The simulated ellapsed time in minutes.
    NextCustId    : Integer; // Id of next customer.

    // For the multi-headed queue:
    MQueue       : TMultiQueue;    // The queue.
    MBeingServed : PCustomerArray; // The customers being served.
    MNumServed   : Longint;        // Total customers served.
    MTotalWait   : Longint;        // Total wait of served customers.
    MMaxWait     : Longint;        // Longest wait of served customers.
    MClerkBusy   : Longint;        // Total time clerks are busy.

    // For the single-headed queues:
    SQueue       : PQueueArray;    // The queues.
    SBeingServed : PCustomerArray; // The customers being served.
    SNumServed   : Longint;        // Total customers served.
    STotalWait   : Longint;        // Total wait of served customers.
    SMaxWait     : Longint;        // Longest wait of served customers.
    SClerkBusy   : Longint;        // Total time clerks are busy.

{$R *.DFM}

procedure THeadedQForm.mnuExitClick(Sender: TObject);
begin
     Close;
end;

procedure THeadedQForm.CPHEditKeyPress(Sender: TObject; var Key: Char);
begin
    if (Key = #8) then exit; // Backspace.
    if ((Key >= '0') and (Key <= '9')) then exit;
    Key := #0;
end;

// Create dynamic controls.
procedure THeadedQForm.CmdBuildQueuesClick(Sender: TObject);
var
    i : Integer;
begin
    // Free memory from the last run.
    if (num_clerks > 0) then
    begin
        // Free customers currently being served.
        for i := 1 to num_clerks do
            if (MBeingServed^[i] <> nil) then
                FreeMem(MBeingServed^[i]);
        for i := 1 to num_clerks do
            if (SBeingServed^[i] <> nil) then
                FreeMem(SBeingServed^[i]);
        FreeMem(MBeingServed);
        FreeMem(SBeingServed);

        // Free the single-headed queues.
        for i := 1 to num_clerks do
            SQueue^[i].Free;
        // Destroy the single-headed queue array.
        FreeMem(SQueue);
    end;

    // Get the new parameters.
    cust_prob  := StrToInt(CPHEdit.Text) / 60;
    min_time   := StrToInt(MinTimeEdit.Text);
    time_range := StrToInt(MaxTimeEdit.Text) - min_time + 1;
    num_clerks := StrToInt(ClerksEdit.Text);

    // Create new labels if necessary.
    AllocateLabels(MultiGroup, MClerkLabels, num_clerks,
        MClerkHeader.Left, MClerkHeader.Width,
        MClerkHeader.Top + MClerkHeader.Height, taCenter);
    AllocateLabels(MultiGroup, MCustLabels, num_clerks,
        MCustHeader.Left, MCustHeader.Width,
        MCustHeader.Top + MCustHeader.Height, taCenter);
    AllocateLabels(SingleGroup, SClerkLabels, num_clerks,
        SClerkHeader.Left, SClerkHeader.Width,
        SClerkHeader.Top + SClerkHeader.Height, taCenter);
    AllocateLabels(SingleGroup, SCustLabels, num_clerks,
        SCustHeader.Left, SCustHeader.Width,
        SCustHeader.Top + SCustHeader.Height, taCenter);
    AllocateLabels(SingleGroup, SWaitLabels, num_clerks,
        SWaitHeader.Left, SWaitHeader.Width,
        SWaitHeader.Top + SWaitHeader.Height, taLeftJustify);
    if (max_clerks < num_clerks) then
        max_clerks := num_clerks;

    // Label the clerks.
    for i := 1 to num_clerks do
    begin
        SClerkLabels^[i].Caption := IntToStr(i);
        MClerkLabels^[i].Caption := IntToStr(i);
    end;

    // Allocate new arrays and queues.
    GetMem(MBeingServed, num_clerks * SizeOf(PCustomer));
    GetMem(SBeingServed, num_clerks * SizeOf(PCustomer));
    for i := 1 to num_clerks do
    begin
        MBeingServed^[i] := nil;
        SBeingServed^[i] := nil;
    end;

    // Create the single-headed queues.
    GetMem(SQueue, num_clerks * SizeOf(TMultiQueue));
    for i := 1 to num_clerks do
        SQueue^[i] := TMultiQueue.Create;

    // Initialize simulation variables.
    MQueue.ClearQueue;
    MNumServed := 0;
    MTotalWait := 0;
    MMaxWait := 0;
    MClerkBusy := 0;

    SNumServed := 0;
    STotalWait := 0;
    SMaxWait := 0;
    SClerkBusy := 0;

    MNumWaitingLabel.Caption := '0';
    MAveLabel.Caption := '0.00';
    MMaxLabel.Caption := '0.00';
    MBusyLabel.Caption := '100';
    SNumWaitingLabel.Caption := '0';
    SAveLabel.Caption := '0.00';
    SMaxLabel.Caption := '0.00';
    SBusyLabel.Caption := '100';
    NextCustId := 1;
    EllapsedTime := 1;

    CmdStart.Enabled := True;
end;

procedure THeadedQForm.CPHEditChange(Sender: TObject);
begin
    CmdBuildQueues.Enabled := (
        (CPHEdit.Text     <> '') and
        (MinTimeEdit.Text <> '') and
        (MaxTimeEdit.Text <> '') and
        (ClerksEdit.Text  <> ''));
    CmdStart.Enabled := False;
end;

procedure THeadedQForm.AllocateLabels(group : TGroupBox;
    var arr : PLabelArray; num, l, w, t : Integer;
    the_alignment : TAlignment);
var
    new_array : PLabelArray;
    i         : Integer;
begin
    // If we need more labels, make them.
    if (num > max_clerks) then
    begin
        // Allocate space for the new array.
        GetMem(new_array, num_clerks * SizeOf(TLabel));

        // Copy the old labels.
        for i := 1 to max_clerks do new_array^[i] := arr^[i];

        // Create the new labels.
        if (max_clerks > 0) then
            t := arr^[max_clerks].Top +
                 arr^[max_clerks].Height;

        for i := max_clerks + 1 to num do
        begin
            new_array^[i] := TLabel.Create(group);
            with new_array^[i] do
            begin
                Parent := group;
                AutoSize := False;
                Left := l;
                Width := w;
                Top := t;
                Alignment := the_alignment;
                t := t + Height;
            end;
        end;

        // Free the previously allocated memory.
        if (max_clerks > 0) then FreeMem(arr);

        // Make arr point at the new array.
        arr := new_array;
    end;

    // Make the right labels visible.
    for i := 1 to num do
    begin
        arr^[i].Caption := '';
        arr^[i].Visible := True;
    end;
    for i := num + 1 to max_clerks do
        arr^[i].Visible := False;
end;

procedure THeadedQForm.CmdStartClick(Sender: TObject);
begin
    if (Running) then
        CmdStart.Caption := 'Start'
    else begin
        CmdStart.Caption := 'Stop';
        QueueTimer.Interval := StrToInt(IntervalEdit.Text);
    end;
    Running := (not Running);
    CmdBuildQueues.Enabled := not Running;
    QueueTimer.Enabled := Running;
end;

// Run for 1 simulated minute.
procedure THeadedQForm.QueueTimerTimer(Sender: TObject);
var
    q, best_q, best_len, num_waiting : Integer;
    m_cust, s_cust                   : PCustomer;
    cust_wait                        : Longint;
begin
    // See if a new customer arrives.
    if (Random > cust_prob) then
    begin
        // Add a customer to the multi-headed queue.
        New(m_cust);
        m_cust^.Id := NextCustId;
        m_cust^.WaitStart := EllapsedTime;
        m_cust^.TimeNeeded := min_time + Random(time_range);
        MQueue.EnterQueue(m_cust);

        // Add a customer to the single-headed queues.
        New(s_cust);
        s_cust^.Id := NextCustId;
        s_cust^.WaitStart := EllapsedTime;
        s_cust^.TimeNeeded := m_cust^.TimeNeeded;

        // Find the shortest single-headed queue.
        best_q := 1;
        best_len := SQueue^[1].Count;
        for q := 2 to num_clerks do
        begin
            if (best_len > SQueue^[q].Count) then
            begin
                best_len := SQueue^[q].Count;
                best_q := q;
            end;
        end;

        // Add the customer to this queue.
        SQueue^[best_q].EnterQueue(s_cust);

        NextCustId := NextCustId + 1;
    end;

    // Check the multi-headed queue clerks.
    for q := 1 to num_clerks do
    begin
        // See if this clerk's customer is done.
        if (MBeingServed^[q] <> nil) then
        begin
            // This clerk is busy.
            MClerkBusy := MClerkBusy + 1;

            with (MBeingServed^[q])^ do
            begin
                TimeNeeded := TimeNeeded - 1; // Tick the clock.
                if (TimeNeeded < 1) then
                begin
                    // This customer is done.
                    MNumServed := MNumServed + 1;
                    cust_wait := WaitEnd - WaitStart;
                    MTotalWait := MTotalWait + cust_wait;
                    if (MMaxWait < cust_wait) then
                        MMaxWait := cust_wait;

                    // Remove this customer.
                    Dispose(MBeingServed^[q]);
                    MBeingServed^[q] := nil;
                end; // End this customer is done.
            end; // End working with this customer.
        end; // End the customer is not nil.

        // See if this clerk needs a new customer.
        if (MBeingServed^[q] = nil) then
        begin
            // Give this clerk a new customer.
            if (MQueue.Count < 1) then
            begin
                MCustLabels^[q].Caption := '';
            end else begin
                MBeingServed^[q] := MQueue.LeaveQueue;
                MBeingServed^[q].WaitEnd := EllapsedTime;
                MCustLabels^[q].Caption :=
                    IntToStr(MBeingServed^[q].Id);
            end;
        end;
    end; // End checking multi-headed queue clerks.

    // Display customers waiting in the multi-headed queue.
    MWaitLabel.Caption := MQueue.TextValue;
    
    // Check the single-headed queue clerks.
    for q := 1 to num_clerks do
    begin
        // See if this clerk's customer is done.
        if (SBeingServed^[q] <> nil) then
        begin
            // This clerk is busy.
            SClerkBusy := SClerkBusy + 1;

            with (SBeingServed^[q])^ do
            begin
                TimeNeeded := TimeNeeded - 1; // Tick the clock.
                if (TimeNeeded < 1) then
                begin
                    // This customer is done.
                    SNumServed := SNumServed + 1;
                    cust_wait := WaitEnd - WaitStart;
                    STotalWait := STotalWait + cust_wait;
                    if (SMaxWait < cust_wait) then
                        SMaxWait := cust_wait;

                    // Remove this customer.
                    Dispose(SBeingServed^[q]);
                    SBeingServed^[q] := nil;
                end; // End this customer is done.
            end; // End working with this customer.
        end; // End the customer is not nil.

        // See if this clerk needs a new customer.
        if (SBeingServed^[q] = nil) then
        begin
            // Give this clerk a new customer.
            if (SQueue^[q].Count < 1) then
            begin
                SCustLabels^[q].Caption := '';
            end else begin
                SBeingServed^[q] := SQueue^[q].LeaveQueue;
                SBeingServed^[q].WaitEnd := EllapsedTime;
                SCustLabels^[q].Caption :=
                    IntToStr(SBeingServed^[q].Id);
            end;
        end;

        // Display customers waiting for this clerk.
        SWaitLabels^[q].Caption := SQueue^[q].TextValue;
    end; // End checking multi-headed queue customers.

    // Display statistics.
    if (MNumServed > 0) then
        MAveLabel.Caption :=
            Format('%.2f', [MTotalWait / MNumServed]);
    MMaxLabel.Caption := IntToStr(MMaxWait);
    MBusyLabel.Caption := Format('%d',
        [Round(100 * MClerkBusy / EllapsedTime / num_clerks)]);
    MNumWaitingLabel.Caption := IntToStr(MQueue.Count);

    if (SNumServed > 0) then
        SAveLabel.Caption :=
            Format('%.2f', [STotalWait / SNumServed]);
    SMaxLabel.Caption := IntToStr(SMaxWait);
    SBusyLabel.Caption := Format('%d',
        [Round(100 * SClerkBusy / EllapsedTime / num_clerks)]);
    num_waiting := 0;
    for q := 1 to num_clerks do
        num_waiting := num_waiting + SQueue^[q].Count;
    SNumWaitingLabel.Caption := IntToStr(num_waiting);

    TimeLabel.Caption := Format('%.02d:%.02d',
        [EllapsedTime div 60, EllapsedTime mod 60]);

    // Click the simulation clock.
    EllapsedTime := EllapsedTime + 1;
end; // End procedure QueueTimerTimer.

// Create MQueue.
procedure THeadedQForm.FormCreate(Sender: TObject);
begin
    MQueue := TMultiQueue.Create;
    Randomize;
end;

procedure THeadedQForm.mnuAboutClick(Sender: TObject);
const
    CR = #13#10;
    CRCR = #13#10#13#10;
begin
    MessageDlg(
        'This program simulates a single multi-headed queue and multiple single-headed queues. You can specify:' + CR +
        '    - Cust/hr: Approximate number of customers that arrive per hour.' + CR +
        '    - Min Time: Minimum service time needed by each customer.' + CR +
        '    - Max Time: Maximum service time needed by each customer.' + CR +
        '    - # Clerks: The number of clerks available.' + CR +
        '    - Interval: Milliseconds between simulation steps.' + CRCR +
        'Output data items include:' + CR +
        '    - Time: The ellapsed simulated time.' + CR +
        '    - Ave Wait: Average time customers waited for service.' + CR +
        '    - Max Wait: Longest time a customer waited for service.' + CR +
        '    - % Clerk Busy: Percentage of time the clerks are busy.'
        , mtInformation, [mbOK], 0);
end;


end.
