unit Collect;
{ Collection classes for Delphi 2.0
  Alin Flaider, 1996
  aflaidar@datalog.ro }
  
interface
uses Windows, Classes, Sysutils;

const
  coIndexError = -1;              { Index out of range }
  coOverflow   = -2;              { Overflow }
  coUnderflow  = -3;              { Underflow }

type
 CollException = class(Exception);

 TCollection = class( TObject)
    private                       { return item at index position }
       function    At( Index : integer) : Pointer;
                                  { replace item at index position}
       procedure   AtPut( Index : integer; Item : Pointer);
    protected
       It     : PPointerList;     { array of pointers }
       Limit  : integer;          { Current Allocated size of array}
       Delta  : integer;          {Number of items by which the collection grows when full}
                                  { deletes item at index position }
       procedure   AtDelete      (Index : integer);
                                  { generates CollException }
       procedure   Error         (Code,Info : Integer); virtual;
                                  { destroys specified Item; override this method if Item is not
                                    a descendant of TObject }
       procedure   FreeItem      (Item : Pointer); virtual;
    public
       Count  : integer;          {Current Number of Items}
       constructor create(aLimit, aDelta : integer);
                                  {before deallocating object it disposes all items and the storage array}
       destructor  destroy; override;
                                  {inserts Item at specified position }
       procedure   AtInsert( Index : integer; Item : Pointer);
                                  {deletes and disposes Item at specified position}
       procedure   AtFree(Index: Integer);
                                  {deletes Item}
       procedure   Delete( Item : Pointer);
                                  {deletes all Items without disposing them }
       procedure   DeleteAll;
                                  {formerly Free, renamed to Clear to avoid bypassing inherited TObject.Free;
                                   deletes and disposes Item }
       procedure Clear(Item: Pointer);
                                  {finds first item that satisfies condition specified in
                                   function Test( Item: pointer): boolean}
       function    FirstThat( Test : Pointer) : Pointer;
                                  {finds last item that satisfies condition specified in
                                   function Test( Item: pointer): boolean}
       function    LastThat( Test : Pointer) : Pointer;
                                  {calls procedure Action( Item: pointer) for each item in collection}
       procedure   ForEach( Action : Pointer);
                                  {disposes all items; set counter to zero}
       procedure   FreeAll;
                                  {finds position of Item using a linear search}
       function    IndexOf( Item : Pointer) : integer; virtual;
                                  {inserts Item at the end of collection}
       procedure   Insert( Item : Pointer); virtual;
                                  {packs collection by removing nil Items}
       procedure   Pack;
                                  {expands array of pointers }
       procedure   SetLimit( aLimit : integer);virtual;
                                  {direct access to items through position}
       property Items[Index: integer]: pointer read At write AtPut; default;
    end;

    TSortedCollection = class(TCollection)
       Duplicates: boolean;       {if true, rejects item whose key already exists}
                                  {override this method to specify relation bewtween two keys
                                  1 if Key1 comes after Key2, -1 if Key1 comes before Key2,
                                  0 if Key1 is equivalent to Key2}
       function Compare (Key1,Key2 : Pointer): Integer; virtual; abstract;
                                  {returns key of Item}
       function KeyOf   (Item : Pointer): Pointer; virtual;
                                  {finds index of item by calling Search}
       function IndexOf (Item : Pointer): integer; virtual;
                                  {finds item required position and performs insertion }
       procedure Insert  (Item : Pointer); virtual;
                                  {finds index of item by performing an optimised search}
       function Search  (key : Pointer; Var Index : integer) : Boolean; virtual;
    end;

implementation

constructor TCollection.Create(ALimit, ADelta: Integer);
begin
   inherited Create;
   Limit:= 0;
   Delta:=aDelta;
   Count:=0;
   It := nil;
   SetLimit( ALimit);
end;

destructor TCollection.Destroy;
begin
   FreeAll;
   SetLimit(0);
   inherited Destroy;
end;

function TCollection.At(Index: Integer): Pointer;
begin
   If Index > pred(Count) then
   begin
     Error(coIndexError,0);
     Result :=nil;
   end
   else Result := It^[Index];
end;

procedure TCollection.AtPut(Index: Integer; Item: Pointer);
begin
   if (Index < 0) or (Index >= Count) then
     Error(coIndexError,0)
   else It^[Index] := Item;
end;

procedure TCollection.AtDelete(Index: Integer);
var p: pointer;
begin
   if (Index < 0) or (Index >= Count) then
   begin
      Error(coIndexError,0);
      exit;
   end;
   if Index < pred(Count) then
     move( It^[succ(Index)], It^[Index], (count-index)*sizeof(pointer));
   Dec(Count);
end;

procedure TCollection.AtInsert( Index: integer; Item: pointer);
var i : integer;
begin
   if (Index < 0) or ( Index > Count) then
   begin
      Error(coIndexError,0);
      exit;
   end;
   if Limit = Count then
   begin
     if Delta = 0 then
     begin
        Error(coOverFlow,0);
        exit;
     end;
     SetLimit( Limit+Delta);
   end;
   If Index <> Count then  {move compensates for overlaps}
      move( It^[Index], It^[Index+1], (count - index)*sizeof(pointer));
   It^[Index] := Item;
   Inc(Count);
end;

procedure TCollection.Delete( Item: pointer);
begin
   AtDelete(Indexof(Item));
end;

procedure TCollection.DeleteAll;
begin
   Count:=0
end;

procedure TCollection.Error(Code, Info: Integer);
begin
   case Code of
        coIndexError: raise CollException.Create('Collection error; wrong index: '+IntToStr(Info));
        coOverflow:  raise CollException.Create('Collection overflow - cannot grow!');
        coUnderflow: raise CollException.Create('Collection underflow - cannot shrink!');
   end
end;

function TCollection.FirstThat(Test: Pointer): Pointer;
type
   tTestFunc = function( p : pointer) : Boolean;
var i : integer;
begin
  Result := nil;
  for i := 0 to pred(count) do
    if tTestFunc(test)(It^[i]) then begin
       Result := It[i];
       break
    end
end;

procedure TCollection.ForEach(Action: Pointer);
type
   tActionProc = procedure(p : pointer);
var i : integer;
begin
  for i := 0 to pred(Count) do
    tActionProc(Action)(It^[i]);
end;

procedure TCollection.Clear(Item: Pointer);
begin
   Delete(Item);
   FreeItem(Item);
end;

procedure TCollection.FreeAll;
var i : integer;
begin
  for I := 0 to Count - 1 do FreeItem(At(I));
  Count := 0;
end;

procedure TCollection.FreeItem(Item: Pointer);
begin
  if Item <> nil then TObject(Item).Free;
end;

function TCollection.IndexOf(Item: Pointer): integer;
var i : integer;
begin
  Result := -1;
  for i := 0 to pred(count) do
    if Item = It^[i] then begin
       Result := i;
       break
    end
end;

procedure TCollection.Insert(Item: Pointer);
begin
   AtInsert(Count,Item);
end;

function TCollection.LastThat(Test: Pointer): pointer;
type
   tTestFunc = function( p : pointer) : Boolean;
var i : integer;
begin
  Result := nil;
  for i := pred(count) downto 1 do
    if tTestFunc(test)(It^[i]) then begin
       Result := It^[i];
       break
    end
end;

procedure TCollection.Pack;
var i: integer;
begin
  for i := pred(count) downto 0 do if It^[i] = nil then AtDelete(i);
end;

procedure TCollection.SetLimit(ALimit: Integer);
begin
  if (ALimit < Count) then Error( coUnderFlow , 0);
  if ALimit <> Limit then
  begin
    ReallocMem( It, ALimit* SizeOf(Pointer));
    Limit := ALimit;
  end;
end;

function TSortedCollection.IndexOf(Item: Pointer): Integer;
var
  i: Integer;
begin
  IndexOf := -1;
  if Search(KeyOf(Item), i) then
  begin
    if Duplicates then
      while (i < Count) and (Item <> It^[I]) do Inc(i);
    if i < Count then IndexOf := i;
  end;
end;

procedure TSortedCollection.Insert(Item: Pointer);
var i : integer;
begin
  if not Search(KeyOf(Item), I) or Duplicates then AtInsert(I, Item);
end;

function TSortedCollection.KeyOf(Item: Pointer): Pointer;
begin
  Result := Item;
end;

function TSortedCollection.Search;
var
  L, H, I, C: Integer;
begin
  Search := False;
  L := 0;
  H := Count - 1;
  while L <= H do
  begin
    I := (L + H) shr 1;
    C := Compare(KeyOf(It^[I]), Key);
    if C < 0 then L := I + 1 else
    begin
      H := I - 1;
      if C = 0 then
      begin
        Search := True;
        if not Duplicates then L := I;
      end;
    end;
  end;
  Index := L;
end;

procedure TCollection.AtFree(Index: Integer);
var
  Item: Pointer;
begin
  Item := At(Index);
  AtDelete(Index);
  FreeItem(Item);
end;

end.