{
Unit: IntList
Author: Jochen Kunkel
Purpose: Handling of Interger lists
Date: 2010-04-04

Array index extern is from 1 to max, intern 0 to max-1, because of use of dynamic array
number: value
index: array index


PRIVATE
List: dynamic array of Integer
Quicksort: sorting the list
Split: used for quicksort

PUBLIC
AddItem: adds Item at end of list
DeleteItem: delets the specific item
IsInList: checks if given numer is already in list
ItemCount: returns count of items in list
GetItem: returns item on given position
Sort: sorts the list ascending
}

unit IntList;

{$mode objfpc}{$H+}

interface

uses
  Classes, SysUtils;

type
  TIntList = class
    constructor Create;

  private
    List: array of integer;
    procedure Quicksort(l, r: integer);
    function Split(l, r: integer): integer;

  public
    procedure AddItem(number: integer);
    procedure AddItemAtPos(number, index: integer);
    procedure DeleteItem(index: integer);
    function IsInList(number: integer): boolean;
    function Item(index: integer): integer;
    function ItemCount: integer;
    procedure SetItemCount(size: integer);
    procedure Shift(oldindex, newindex: integer);
    procedure Sort;
    procedure WriteToScreen;

  end;

implementation

{private}
procedure TIntList.Quicksort(l, r: integer);
var
  p: integer;

begin
  if l < r then
  begin
    p := Split(l, r);
    Quicksort(l, p - 1);
    Quicksort(p + 1, r);
  end;
end;

function TIntList.Split(l, r: integer): integer;
var
  i, j, p, d: integer;

begin
  i := l;
  j := r - 1;
  p := list[r];

  while i < j do
  begin
    while (list[i] < p) and (i < r) do
      Inc(i);

    while (list[j] > p) and (j > l) do
      Dec(j);

    if i < j then
    begin
      d := list[i];
      list[i] := list[j];
      list[j] := d;
    end;
  end;

  if list[i] > p then
  begin
    d := list[i];
    list[i] := list[r];
    list[r] := d;
  end;
  Result := i;
end;



{public}
constructor TIntList.Create;
begin
  inherited;
  SetLength(list, 0);
end;

procedure TIntList.AddItem(number: integer);
begin
  SetLength(list, Length(list) + 1);  //extend list
  list[High(list)] := number;         //write new value at end
end;

procedure TIntList.AddItemAtPos(number, index: integer);
var
  i: integer;
begin
  if (index - 1 <= High(list)) and (index - 1 >= Low(list)) then//0<index<max
  begin
    SetLength(list, Length(list) + 1);      //extend list
    for i := High(list) downto index - 1 do //-1
      list[i] := list[i - 1]; //shift elements

    list[index - 1] := number; // new element

  end;
end;

procedure TIntList.DeleteItem(index: integer);
var
  i: integer;
begin
  for i := index to Length(list) - 1 do
    list[i - 1] := list[i]; // shift

  SetLength(list, Length(list) - 1); // delete last entry
end;

function TIntList.IsInList(number: integer): boolean;
var
  i: integer;
begin
  Result := False;
  for i := 0 to High(list) do
  begin
    if number = list[i] then
      Result := True;
      exit; // leave function on 1st apperance
  end;
end;

function TIntList.Item(index: integer): integer;
begin
  Result := list[index - 1];
end;

function TIntList.ItemCount: integer;
begin
  Result := Length(list);
end;

procedure TIntList.SetItemCount(size: integer);
begin
  SetLength(list, size);
end;

procedure TIntList.Shift(oldindex, newindex: integer);
var
  dum: integer;
begin
  dum := list[oldindex - 1];   //save value
  DeleteItem(oldindex);        //delete value
  AddItemAtPos(dum, newindex); //write value
end;

procedure TIntList.Sort;
begin
  //quicksort
  Quicksort(0, High(list));
end;

procedure TIntList.WriteToScreen;
var
  i: integer;
begin
  for i := 0 to High(list) do
    Write(list[i]);
end;

end.