17.11 TSortedCollection

TSortedCollection is an abstract class, implementing a sorted collection. You should never use an instance of TSortedCollection directly, instead you should declare a descendent type, and override the Compare (614) method.

Because the collection is ordered, TSortedCollection overrides some TCollection methods, to provide faster routines for lookup.

The Compare (614) method decides how elements in the collection should be ordered. Since TCollection has no way of knowing how to order pointers, you must override the compare method.

Additionally, TCollection provides a means to filter out duplicates. if you set Duplicates to False (the default) then duplicates will not be allowed.

Here is the complete declaration of TSortedCollection

 TYPE
    TSortedCollection = OBJECT (TCollection)
          Duplicates: Boolean; { Duplicates flag }
       Constructor Init (ALimit, ADelta: Sw_Integer);
       Constructor Load (Var S: TStream);
       Function KeyOf (Item: Pointer): Pointer; Virtual;
       Function IndexOf (Item: Pointer): Sw_Integer; Virtual;
       Function Compare (Key1, Key2: Pointer): Sw_Integer; Virtual;
       Function Search (Key: Pointer; Var Index: Sw_Integer): Boolean;Virtual;
       Procedure Insert (Item: Pointer); Virtual;
       Procedure Store (Var S: TStream);
    END;
    PSortedCollection = ^TSortedCollection;

In the subsequent examples, the following descendent of TSortedCollection is used:

Listing: objectex/mysortc.pp

Unit MySortC;

Interface

Uses Objects;

Type
  PMySortedCollection = ^TMySortedCollection;
  TMySortedCollection = Object(TSortedCollection)
       Function Compare (Key1,Key2 : Pointer): Sw_integer; virtual;
       end;

Implementation

Uses MyObject;

Function TMySortedCollection.Compare (Key1,Key2 : Pointer) :sw_integer;

begin
  Compare:=PMyobject(Key1)^.GetField - PMyObject(Key2)^.GetField;
end;

end.

TSortedCollection.Init

Declaration:: Constructor TSortedCollection.Init (ALimit, ADelta: Sw_Integer);
Description:: Init calls the inherited constuctor (see TCollection.Init (593)) and sets the Duplicates flag to false.
You should not call this method directly, since TSortedCollection is a abstract class. Instead, the descendent classes should call it via the inherited keyword.
Errors:: None.
See also:: Load (613), Done (595)

For an example, see

TSortedCollection.Load

Declaration:: Constructor Load (Var S: TStream);
Description:: Load calls the inherited constuctor (see TCollection.Load (594)) and reads the Duplicates flag from the stream..
You should not call this method directly, since TSortedCollection is a abstract class. Instead, the descendent classes should call it via the inherited keyword.
Errors:: None.
See also:: Init (612), Done (595)

For an example, see TCollection.Load (594).

TSortedCollection.KeyOf

Declaration:: Function TSortedCollection.KeyOf (Item: Pointer): Pointer; Virtual;
Description:: KeyOf returns the key associated with Item. TSortedCollection returns the item itself as the key, descendent objects can override this method to calculate a (unique) key based on the item passed (such as hash values).
Keys are used to sort the objects, they are used to search and sort the items in the collection. If descendent types override this method then it allows possibly for faster search/sort methods based on keys rather than on the objects themselves.
Errors:: None.
See also:: IndexOf (613), Compare (614).

TSortedCollection.IndexOf

Declaration:: Function TSortedCollection.IndexOf (Item: Pointer): Sw_Integer; Virtual;
Description:: IndexOf returns the index of Item in the collection. It searches for the object based on it’s key. If duplicates are allowed, then it returns the index of last object that matches Item.
In case Item is not found in the collection, -1 is returned.
Errors:: None.
See also:: Search (615), Compare (614).

For an example, see TCollection.IndexOf (596)

TSortedCollection.Compare

Declaration:

Function TSortedCollection.Compare (Key1, Key2: Pointer): Sw_Integer; Virtual;

Description:

Compare is an abstract method that should be overridden by descendent objects in order to compare two items in the collection. This method is used in the Search (615) method and in the Insert (616) method to determine the ordering of the objects.

The function should compare the two keys of items and return the following function results:

Result ¡ 0: If Key1 is logically before Key2 (Key1<Key2)
Result = 0: If Key1 and Key2 are equal. (Key1=Key2)
Result ¿ 0: If Key1 is logically after Key2 (Key1>Key2)

Errors:

An ’abstract run-time error’ will be generated if you call TSortedCollection.Compare directly.

See also:

IndexOf (613), Search (615)

Listing: objectex/mysortc.pp

TSortedCollection.Search

Declaration:

Function TSortedCollection.Search (Key: Pointer; Var Index: Sw_Integer): Boolean;Virtual;

Description:

Search looks for the item with key Key and returns the position of the item (if present) in the collection in Index.

Instead of a linear search as TCollection does, TSortedCollection uses a binary search based on the keys of the objects. It uses the Compare (614) function to implement this search.

If the item is found, Search returns True, otherwise False is returned.

Errors:

None.

See also:

IndexOf (596).

Listing: objectex/ex36.pp

Program ex36;

{ Program to demonstrate the TSortedCollection.Insert method }

Uses Objects,MyObject,MySortC;
{ For TMyObject,TMySortedCollection definition and registration }

Var C : PSortedCollection;
    M : PMyObject;
    I : Longint;

Procedure PrintField (Dummy: Pointer;P : PMyObject);

begin
  Writeln ('Field : ',P^.GetField);
end;

begin
  Randomize;
  C:=New(PMySortedCollection,Init(120,10));
  C^.Duplicates:=True;
  Writeln ('Inserting 100 records at random places.');
  For I:=1 to 100 do
    begin
    M:=New(PMyObject,Init);
    M^.SetField(Random(100));
    C^.Insert(M)
    end;
  M:=New(PMyObject,Init);
  Repeat;
    Write ('Value to search for (-1 stops) :');
    read (I);
    If I<>-1 then
      begin
      M^.SetField(i);
      If Not C^.Search (M,I) then
        Writeln ('No such value found')
      else
        begin
        Write ('Value ',PMyObject(C^.At(I))^.GetField);
        Writeln (' present at position ',I);
        end;
      end;
  Until I=-1;
  Dispose(M,Done);
  Dispose(C,Done);
end.

TSortedCollection.Insert

Declaration:: Procedure TSortedCollection.Insert (Item: Pointer); Virtual;
Description:: Insert inserts an item in the collection at the correct position, such that the collection is ordered at all times. You should never use Atinsert (608), since then the collection ordering is not guaranteed.
If Item is already present in the collection, and Duplicates is False, the item will not be inserted.
Errors:: None.
See also:: AtInsert (608)

Listing: objectex/ex35.pp

Program ex35;

{ Program to demonstrate the TSortedCollection.Insert method }

Uses Objects,MyObject,MySortC;
{ For TMyObject,TMySortedCollection definition and registration }

Var C : PSortedCollection;
    M : PMyObject;
    I : Longint;

Procedure PrintField (Dummy: Pointer;P : PMyObject);

begin
  Writeln ('Field : ',P^.GetField);
end;

begin
  Randomize;
  C:=New(PMySortedCollection,Init(120,10));
  Writeln ('Inserting 100 records at random places.');
  For I:=1 to 100 do
    begin
    M:=New(PMyObject,Init);
    M^.SetField(Random(100));
    C^.Insert(M)
    end;
  Writeln ('Values : ');
  C^.Foreach(@PrintField);
  Dispose(C,Done);
end.

TSortedCollection.Store

Declaration:: Procedure TSortedCollection.Store (Var S: TStream);
Description:: Store writes the collection to the stream S. It does this by calling the inherited TCollection.Store (609), and then writing the Duplicates flag to the stream.
After a Store, the collection can be loaded from the stream with the constructor Load (613)
Errors:: Errors can be those of TStream.Put (571).
See also:: Load (613)

For an example, see TCollection.Load (594).

[next] [prev] [prev-tail] [front] [up]