unit SparseC;
//*******************************************************
// 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];

    PSparseCell = ^TSparseCell;
    TSparseCell = Record
        Col      : Longint;
        Value    : String10;
        NextCell : PSparseCell;
    end;
    TCellArray = array[0..100000000] of TSparseCell;
    PCellArray = ^TCellArray;

    TSparseArray = class(TObject)
        private
            RowSentinel : PCellArray;
            Max_Row     : Longint;

        public
            constructor Create;
            destructor Destroy; override;
            procedure SetValue(r, c : Longint; new_value : String10);
            function GetValue(r, c : Longint) : String10;
            function MaxRow : Longint;
            function MaxCol : Longint;
    end;

implementation

// Create row zero.
constructor TSparseArray.Create;
begin
    // Make it resize the first time it's used.
    Max_Row := -1;

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

// Free the array memory.
destructor TSparseArray.Destroy;
var
    i                : Longint;
    cell_ptr, target : PSparseCell;
begin
    // Free the cells.
    for i := 0 to Max_Row do
    begin
        cell_ptr := RowSentinel^[i].NextCell;
        while (cell_ptr <> nil) do
        begin
            target := cell_ptr;
            cell_ptr := cell_ptr.NextCell;
            Dispose(target);
        end;
    end;

    // Free the row sentinels.
    FreeMem(RowSentinel);

    inherited Destroy;
end;

// Set an array entry's value.
procedure TSparseArray.SetValue(r, c : Longint; new_value : String10);
var
    cell_ptr, next_ptr : PSparseCell;
    i                  : Longint;
    new_array          : PCellArray;
    bottom_sentinel    : PSparseCell;
begin
    if ((r < 0) or (c < 0)) then
        raise EInvalidOperation.Create(
            'Row and column must be at least zero.');

    // See if we need to make the sentinel array bigger.
    if (r > Max_Row) then
    begin
        // Copy the old values into a new array.
        GetMem(new_array, (r + 1) * SizeOf(TSparseCell));
        for i := 0 to Max_Row do
            new_array^[i] := RowSentinel^[i];

        // Free the old array.
        if (Max_Row >= 0) then FreeMem(RowSentinel);
        RowSentinel := new_array;

        // Create new sentinels.
        for i := Max_Row + 1 to r do
        begin
            New(bottom_sentinel);
            bottom_sentinel^.Col := 2147483647;
            bottom_sentinel^.NextCell := nil;
            RowSentinel^[i].NextCell := bottom_sentinel;
            RowSentinel^[i].Col := -1;
        end;
        Max_Row := r;
    end;

    // Find a cell with column >= c.
    cell_ptr := @RowSentinel^[r];
    next_ptr := cell_ptr^.NextCell;
    while (next_ptr^.Col < c) do
    begin
        cell_ptr := next_ptr;
        next_ptr := cell_ptr^.NextCell;
    end;

    // If the value is the default value...
    if (new_value = DEFAULT_VALUE) then
    begin
        // If we found a cell for this column, remove it.
        if (next_ptr^.Col = c) then
        begin
            cell_ptr^.NextCell := next_ptr^.NextCell;
            Dispose(next_ptr);
        end;
    end else begin
        // The value is not the default value.
        // If we did not find the cell, create a new cell.
        if (next_ptr^.Col <> c) then
        begin
            New(next_ptr);
            next_ptr^.Col := c;
            next_ptr^.NextCell := cell_ptr^.NextCell;
            cell_ptr^.NextCell := next_ptr;
        end;

        // Save the new value.
        next_ptr^.Value := new_value;
    end;
end;

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

    // See if we have a sentinel for this row.
    if (r > Max_Row) then
        GetValue := DEFAULT_VALUE
    else begin
        // Find a cell with column >= c.
        cell_ptr := RowSentinel^[r].NextCell;
        while (cell_ptr^.Col < c) do
            cell_ptr := cell_ptr^.NextCell;

        // If we did not find it, return DEFAULT_VALUE.
        if (cell_ptr^.Col = c) then
            GetValue := cell_ptr.Value
        else
            GetValue := DEFAULT_VALUE;
    end;
end;

// Return the largest row number.
function TSparseArray.MaxRow : Longint;
begin
    MaxRow := Max_Row;
end;

// Return the largest column number.
function TSparseArray.MaxCol : Longint;
var
    r, c     : Longint;
    cell_ptr : PSparseCell;
begin
    Result := 0;
    for r := 0 to Max_Row do
    begin
        cell_ptr := @RowSentinel^[r];
        while (cell_ptr^.NextCell^.NextCell <> nil) do
            cell_ptr := cell_ptr^.NextCell;

        c := cell_ptr^.Col;
        if (Result < c) then Result := c;
    end;
end;

end.
