unit VSparseC;
//*******************************************************
// Very sparse array class.
//*******************************************************
// Copyright (C) 1998 John Wiley & Sons, Inc.
// All rights reserved. See additional copyright
// information in Readme.txt.
//*******************************************************

interface

uses
    Dialogs, SysUtils, Classes,
    ExtCtrls, Windows, Graphics;

const
    DEFAULT_VALUE = '';

type
    String10 = String[10];

    PRowCell = ^TRowCell;
    PSparseCell = ^TSparseCell;

    TRowCell = Record
        Row       : Longint;
        FirstCell : PSparseCell;
        NextRow   : PRowCell;
    end;
    TSparseCell = Record
        Col      : Longint;
        Value    : String10;
        NextCell : PSparseCell;
    end;

    TVerySparseArray = class(TObject)
        private
            TopSentinel : PRowCell;

        public
            constructor Create;
            destructor Destroy; override;
            procedure SetValue(r, c : Longint; new_value : String10);
            function GetValue(r, c : Longint) : String10;
            procedure DrawArray(cvs : TCanvas; h, t, l : Integer);
    end;

implementation

// Create row sentinels.
constructor TVerySparseArray.Create;
var
    bottom_sentinel : PRowCell;
begin
    // Create the top row sentinel.
    New(TopSentinel);
    TopSentinel^.Row := -1;
    TopSentinel^.FirstCell := nil;

    // Create the bottom row sentinel.
    New(bottom_sentinel);
    bottom_sentinel^.Row := 2147483647;
    bottom_sentinel^.NextRow := nil;
    bottom_sentinel^.FirstCell := nil;
    TopSentinel^.NextRow := bottom_sentinel;

    // Allocate memory and perform inherited initialization.
    inherited Create;
end;

// Free the array memory.
destructor TVerySparseArray.Destroy;
var
    row_ptr, target_row   : PRowCell;
    cell_ptr, target_cell : PSparseCell;
begin
    // Free the rows.
    row_ptr := TopSentinel;
    while (row_ptr <> nil) do
    begin
        // Free this row's column cells.
        cell_ptr := row_ptr^.FirstCell;
        while (cell_ptr <> nil) do
        begin
            target_cell := cell_ptr;
            cell_ptr := cell_ptr^.NextCell;
            Dispose(target_cell);
        end;

        // Free the row header itself.
        target_row := row_ptr;
        row_ptr := row_ptr^.NextRow;
        Dispose(target_row);
    end;

    inherited Destroy;
end;

// Set an array entry's value.
procedure TVerySparseArray.SetValue(r, c : Longint; new_value : String10);
var
    row_ptr, next_row : PRowCell;
    col_ptr, next_col : PSparseCell;
begin
    if ((r < 0) or (c < 0)) then
        raise EInvalidOperation.Create(
            'Row and column must be at least zero.');

    // Find the row cell.
    row_ptr := TopSentinel;
    next_row := row_ptr^.NextRow;
    while (next_row^.Row < r) do
    begin
        row_ptr := next_row;
        next_row := next_row^.NextRow;
    end;

    // See if we found the row we need.
    if (next_row^.Row <> r) then
    begin
        // We did not. If the value is DEFAULT_VALUE,
        // then we are done. The value is already not
        // in the array.
        if (new_value = DEFAULT_VALUE) then exit;

        // Otherwise create a new row.
        New(next_row);
        next_row^.Row := r;
        next_row^.NextRow := row_ptr^.NextRow;
        row_ptr^.NextRow := next_row;

        // Create sentinels for the new row.
        New(col_ptr);  // Create the top sentinel.
        col_ptr^.Col := -1;

        New(next_col); // Create the bottom sentinel.
        next_col^.Col := 2147483647;
        next_col^.NextCell := nil;
        col_ptr^.NextCell := next_col;
        next_row^.FirstCell := col_ptr;
    end;

    // next_row is the row we want. Find the column cell.
    col_ptr := next_row^.FirstCell;
    next_col := col_ptr^.NextCell;
    while (next_col^.Col < c) do
    begin
        col_ptr := next_col;
        next_col := next_col^.NextCell;
    end;

    // See if we found the column we need.
    if (next_col^.Col <> c) then
    begin
        // We did not. If the value is DEFAULT_VALUE,
        // then we are done. The value is already not
        // in the array.
        if (new_value = DEFAULT_VALUE) then exit;

        // Otherwise create a new column cell.
        New(next_col);
        next_col^.Col := c;
        next_col^.NextCell := col_ptr^.NextCell;
        col_ptr^.NextCell := next_col;
    end;

    // The cell we need is in next_col.
    if (new_value = DEFAULT_VALUE) then
    begin
        // If we get here, we know we found a cell for
        // this value. Remove it.
        col_ptr^.NextCell := next_col^.NextCell;
        Dispose(next_col);

        // If this was the only cell in the row, remove it.
        next_col := col_ptr^.NextCell;
        if ((next_row^.FirstCell = col_ptr) and
            (next_col^.NextCell = nil)) then
        begin
            // Free the column sentinels.
            Dispose(col_ptr);
            Dispose(next_col);

            // Free the row.
            row_ptr^.NextRow := next_row^.NextRow;
            Dispose(next_row);
        end;
    end else begin
        // The value is not the default value. Save it.
        next_col^.Value := new_value;
    end;
end;

// Return an array entry's value.
function TVerySparseArray.GetValue(r, c : Longint) : String10;
var
    row_ptr : PRowCell;
    col_ptr : PSparseCell;
begin
    if ((r < 0) or (c < 0)) then
        raise EInvalidOperation.Create(
            'Row and column must be at least zero.');

    // Find the row cell.
    row_ptr := TopSentinel^.NextRow;
    while (row_ptr^.Row < r) do
        row_ptr := row_ptr^.NextRow;

    // See if we found the row we need.
    Result := DEFAULT_VALUE;
    if (row_ptr^.Row <> r) then exit;

    // Find the column cell.
    col_ptr := row_ptr^.FirstCell^.NextCell;
    while (col_ptr^.Col < c) do
        col_ptr := col_ptr^.NextCell;

    // See if we found the column we need.
    if (col_ptr^.Col <> c) then exit;

    // We found it.
    Result := col_ptr^.Value;
end;

procedure TVerySparseArray.DrawArray(cvs : TCanvas; h, t, l : Integer);
var
    row_ptr : PRowCell;
    col_ptr : PSparseCell;
begin
    // Draw the rows.
    cvs.Brush.Color := clWhite;
    row_ptr := TopSentinel^.NextRow;
    while (row_ptr.Row < 2147483647) do
    begin
        cvs.Font.Style := [fsBold];
        cvs.TextOut(l, t, '' + IntToStr(row_ptr.Row) + ':');

        col_ptr := row_ptr^.FirstCell.NextCell;
        while (col_ptr.Col < 2147483647) do
        begin
            cvs.Font.Style := [fsBold];
            cvs.TextOut(cvs.PenPos.X + 5, t,
                IntToStr(col_ptr.Col) + ':');
            cvs.Font.Style := [];
            cvs.TextOut(cvs.PenPos.X, cvs.PenPos.Y,
               col_ptr.Value + ' ');

            col_ptr := col_ptr^.NextCell;
        end;
        t := t + h;
        row_ptr := row_ptr^.NextRow;
    end;
end;

end.
