unit SparseC;
//*******************************************************
// Sparse array class.
//*******************************************************
// Copyright (C) 1998 John Wiley & Sons, Inc.
// All rights reserved. See additional copyright
// information in Readme.txt.
//
// Revised (C) 1999 Andrzej Grażyński, HELION Publ.
//*******************************************************

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;

    TSparseArray = class(TObject)
        private
            //RowSentinel : PCellArray;
            RowSentinel : array of TSparseCell;
            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

// utwórz wiersz zerowy
constructor TSparseArray.Create;
begin
    // Poniższa wartosć spowoduje zmianę rozmiarów tablicy przy pierwszym użyciu
    Max_Row := -1;

    inherited Create;
end;

// Zwolnij pamięć przydzieloną dla tablicy
destructor TSparseArray.Destroy;
var
    i                : Longint;
    cell_ptr, target : PSparseCell;
begin
    // Zwolnij komórki
    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;

    // zwolnij wartowników wierszowych
    RowSentinel := NIL;

    inherited Destroy;
end;

// Przypisz wartosć elementowi tablicy
procedure TSparseArray.SetValue(r, c : Longint; new_value : String10);
var
  cell_ptr, next_ptr : PSparseCell;
  i                  : Longint;
  bottom_sentinel    : PSparseCell;
begin
  if ((r < 0) or (c < 0))
  then
    raise EInvalidOperation.Create(
            'Numer wiersza/kolumny nie może być ujemny.');

  // Sprawdź, czy należy poszerzyć tablicę wartowników
  if (r > Max_Row) then
  begin
    SetLength(RowSentinel, r+1);

    // twórz wartowników końcowych
    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;

  // Znajdź komórkę reprezentującą kolumnę >= 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;

  // Jeśli podano wartosć domyślną...
  if (new_value = DEFAULT_VALUE) then
  begin
      // ... i jeżeli istnieje wskazany element, usuń go
      if (next_ptr^.Col = c) then
      begin
          cell_ptr^.NextCell := next_ptr^.NextCell;
          Dispose(next_ptr);
      end;
  end
  else
  begin
    // jeśli nie istnieje wskazany element, utwórz go
    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;

    // Wpisz wartość
      next_ptr^.Value := new_value;
  end;
end;

// Zwróć wartosć wskazanego elementu
function TSparseArray.GetValue(r, c : Longint) : String10;
var
    cell_ptr : PSparseCell;
begin
    if ((r < 0) or (c < 0)) then
        raise EInvalidOperation.Create(
            'Numer wiersza/kolumny nie może być ujemny.');

    // Sprawdź, czy istnieje wartownik tego wiersza
    if (r > Max_Row)
    then
        GetValue := DEFAULT_VALUE
    else
    begin
        // Znajdź komórkę z wartością kolumny >= c.
        cell_ptr := RowSentinel[r].NextCell;
        while (cell_ptr^.Col < c) do
            cell_ptr := cell_ptr^.NextCell;

        // Jeżeli nie znaleziono, zwróć wartość domyślną
        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.
