tutorial.txt

                         PascalAdt tutorial.

This document provides an introduction to the PascalAdt library and
briefly explains its basic functions using an example of a simple
program dealing with a database of customers and their orders.

An API reference documentation for PascalAdt is available at
https://pascaladt.github.io/pascaladt-docs.

I. What is PascalAdt?
II. How to use it?
        1. The customer.pas program.
        2. The basics.
           2.1 Simple type defines.
           2.2 Terminology.
           2.3 Files.
           2.4 Containers.
           2.5 Basic methods.
           2.6 Functors.
        3. Sets and maps.
           3.1 Basic information.
           3.2 Searching for items.
           3.3 Inserting items.
           3.4 Removing items.
        4. Lists.
           4.1 Basic information.
           4.2 Inserting items.
        5. Iterators.
           5.1 Basic information.
           5.2 Ranges.
           5.3 Simplified class hierarchy.
               5.3.1 TIterator.
               5.3.2 TForwardIterator.
               5.3.3 TBidirectionalIterator.
               5.3.4 TRandomAccessIterator.
               5.3.5 TSetIterator.
           5.4 Invalidation of iterators.
           5.5 Ownership issues.
           5.6 Example.
        6. Algorithms.
        7. Compositions of functors.
III. Where to find more information?
IV. Author.

I. What is PascalAdt?

PascalAdt is a library of data structures and algorithms. ADT is an
acronym for Abstract Data Types. Aho, Hopcroft and Ullman use it quite
often in their "Data Structures and Algorithms" textbook. Hence the
name.

The PascalAdt library provides abstract container interfaces like
general interfaces for lists, maps, sets, etc. Each of these
interfaces has several implementations to choose from. (Note: When we
speak of interfaces we do not mean delphi interfaces, but plainly
something which provides an interface to access sth. Object Pascal
interfaces will be referred to explicitly as 'Object Pascal
interfaces' to distinguish them from the general interfaces).


II. How to use it?

This section provides a tutorial giving an overview of the PascalAdt
library. The library is used in a hypothetical program which maintains
a data base of customers. The program resides in
demo/customer/customer.pas. All code listings in this tutorial are
extracted from this file.

1. The customer.pas program.

Say we want to build a program maintaining a base of customers and
dealing with their orders. We would like to have each customer's name,
address and other such information stored in the database. We would
also like to be able to view each customer's current orders, as well
as view all orders at once or search for orders of a given product.

We declare a simple record-like class to store a customer's data. It
might look something like this:

   TCustomer = class
   private
      FFirstName, FSurname : String;
      FAddress : String;
      FOrders : TListAdt;
   public
      constructor Create(aFirstName, aSurname, aAddress : String);
      destructor Destroy; override;

      property FirstName : String read FFirstName write FFirstName;
      property Surname : String read FSurname write FSurname;
      property Address : String read FAddress write FAddress;
      property Orders : TListAdt read FOrders;
   end;

For the data type of an order we may take the following:

   TOrder = class
   public
      orderId : Cardinal;
      productName, price : String;
      customer : TCustomer;
   end;

A unique ID number, some product, its price and, of course, the
customer placing the order is associated with each order.

2. The basics.

Before delving into details we shall consider some basic general
issues.

2.1 Simple type defines.

The PascalAdt library uses several types defined in adtdefs.inc as
basic numeric types. The most important are: IndexType, SizeType and
UnsignedType. IndexType is a signed type representing an index or the
difference of two indices. SizeType represents a size. UnsignedType is
unsigned, used mostly in conjunction with hashers.

2.2 Terminology.

We call the data structures implemented as classes containers. The
things stored in them are items. A container is said to own its items
if it destroys them automatically when they are removed from the
container or when the container is itself destroyed.

2.3 Files.

If you look at the PascalAdt library sources, you notice that most of
it is not implemented in *.pas files. This is because the sources are
preprocessed with the MCP macro processor to generate several
versions of each container for different item types. Most units are
broken up into three files: adtunit.i, adtunit_impl.i and
adtunit.pas.mcp. The files contain ordinary Pascal code with some MCP
macros. The file adtunit.i contains the interface, adtunit_impl.i the
implementation, and adtunit.pas.mcp puts these two together with
unit uses, initialization and finalization code.

We will be referring to unit names without indicating specific
files. The most convenient reference for the units, classes and
functions in the library is the online PascalAdt API reference
documentation (https://pascaladt.github.io/pascaladt-docs).

2.4 Containers.

The PascalAdt library provides a variety of containers. By default
they store generic objects, i.e., the item type is
TObject. TContainerAdt is the ancestor of all containers, and the root
of the container class hierarchy tree. It is defined in
adtcontbase.i. No concrete container class is derived directly from
TContainerAdt, though, but instead from some abstract class providing
an interface for the implemented functionality. There are in fact many
'chains' of classes. In each of them, declarations are introduced
gradually with each class introducing some new methods. For examle,
one such chain might be TContainerAdt -> TQueueAdt -> TDequeAdt ->
TListAdt -> TDoubleListAdt -> TRandomAccessContainerAdt ->
TArrayAdt. The arrow means that the class on the right is derived from
the one on the left. Here, TQueueAdt is an abstract class providing an
interface of a queue, TDequeAdt an abstract class providing an
interface of a double-ended queue, and so on. The suffix -Adt in the
name of a class means that the class is an abstract container class
providing some interface. Generally speaking, the abstract -Adt
classes provide concepts and concrete classes provide specific
implementations. For instance, there are two classes derived directly
from TDoubleListAdt with almost the same methods, implementing the
same functionality, but in two different ways. These are namely
TDoubleList - a standard doubly-linked list - and TXorList - a
memory-saving implementation of a doubly-linked list, but a somewhat
messy one.

For most containers there are also versions for strings and
integers. These are prefixed with TString (or TInteger), e.g.,
TStringDequeAdt instead of TDequeAdt. They inherit from
TStringContainerAdt (or TIntegerContainerAdt) and their item type is
String (or Integer) instead of TObject.

All abstract -Adt classes, except for TContainerAdt, are defined in
adtcont.i. TContainerAdt is defined in adtcontbase.i.

Going back to our TCustomer class, we see that TListAdt is just a
general interface to a list. It is usually preferable to use abstract
-Adt classes than to use concreate ones, because when you later decide
to change the implementation for some reason it will make your life
much easier.

2.5 Basic methods.

All containers share several basic methods declared in
TContainerAdt. Alone, wihtout other methods, they are rather
useless. The most important of them are:

   procedure Clear; virtual; abstract;

This procedure removes all items from the container.

   function Size : SizeType; virtual; abstract;

Returns the number of items in the container.

   function Empty : Boolean; virtual; abstract;

Returns true if the container doesn't contain any items. This is
equivalent to Size = 0, but may be faster for some implementations. It
is guaranteed to be O(1).

   property OwnsItems : Boolean read FOwnsItems write SetOwnsItems;

Indicates whether the container owns its items. In other words,
whether the items should be destroyed when removed from the container
(this includes destroying them when the container itself is
destroyed). Always true after creation.

2.6 Functors.

Functors are classes which act like routines. In the PascalAdt library
they are implemented as Object Pascal interfaces. Functors are most
commonly used as comparers, hashers or predicates.

All functor interfaces are defined in adtfunct.i. The most important
of them include:

   IUnaryFunctor = interface (IFunctor)
      function Perform(obj : TObject) : TObject;
   end;

Used primarily with sequence algorithms.

   IBinaryComparer = interface (IFunctor)
      function Compare(obj1, obj2 : TObject) : Integer;
   end;

Used to compare two items. Returns 0 if they are equal, a negative
number if ptr1 < ptr2, and a positive number if ptr1 > ptr2.

   IHasher = interface (IFunctor)
      function Hash(obj : TObject) : UnsignedType;
   end;

Hashes a given item.

3. Sets and maps.

3.1 Basic information.

Let's think what we need for our hypothetical customer.pas program. We
would like to store all customers in a database and have possibly fast
access to any customer by their name. We need some sort of a map. The
abstract map interface is TMapAdt. Take a look at its declaration in
adtcont and you will see that there is a small problem with using a
map. Namely, it requires two kinds of objects to be stored - the keys
and the proper items. But we need only one. To get around this, we
shall use a set - TSetAdt. Actually, most maps are implemented by
means of a set. There is even a wrapper class in adtmap providing
the TMapAdt interface for any TSetAdt.

Let's be more specific now and choose a particular implementation for
our set. Let it be a hash table. There are presently two
implementations of hash tables in the PascalAdt library, both of them
in adthash.i. These are THashTable and TScatterTable. The former is
recommended for most uses as it is slightly faster (by a constant
factor). The latter, on the other hand, uses less memory. Notice that
they are both derived from THashSetAdt. Yes, THashSetAdt is an
abstract class derived from TSetAdt 'narrowing' its scope and
introducing several methods for dealing with hash-tables.

For this simple program it suffices to declare one global variable to
store all the customers.

   var
      allCustomers : THashSetAdt;

An object of this type is created in the begining of the main program
block.

   begin
      // ...
      try
         // ...
         allCustomers := THashTable.Create;
         allCustomers.Hasher := TCustomerHasher.Create;
         allCustomers.ItemComparer := TCustomerComparer.Create;

         // ...

         { do the main job }
         Run;

      finally
         allOrders.Free;
         allCustomers.Free;
      end;
   end.

We need a custom hasher and comparer for the TCustomer class. Let's
now look at their declarations.

   TCustomerComparer = class (TFunctor, IBinaryComparer)
   public
      function Compare(obj1, obj2 : TObject) : Integer;
   end;

   TCustomerHasher = class (TFunctor, IHasher)
   public
      function Hash(obj : TObject) : UnsignedType;
   end;

Both the classes inherit from TFunctor, which should be used as a base
class for any class implementing a functor interface.

The definitions of the methods are probably more interesting.

   function CompareCustomers(customer1, customer2 : TCustomer) : IndexType;
   begin
      Result := CompareStr(customer1.Surname, customer2.Surname);
      if Result = 0 then
         Result := CompareStr(customer1.FirstName, customer2.FirstName);
   end;

   // ...

   function TCustomerComparer.Compare(obj1, obj2 : TObject) : Integer;
   begin
      Result := CompareCustomers(TCustomer(obj1), TCustomer(obj2));
   end;

   function TCustomerHasher.Hash(obj : TObject) : UnsignedType;
   var
      nameStr : AnsiString;
   begin
      nameStr := TCustomer(obj).FirstName + TCustomer(obj).Surname;
      Result := FNVHash(PChar(nameStr), Length(nameStr));
   end;

The job of comparing two TCustomer objects is done by a separate
function which will also be needed later in the program. The function
simply compares first the surnames of the customers, and if they are
the same then compares their names. The hasher uses a hashing function
defined in adthashfunct. The function implements a very simple and
efficient FNV algorithm. This is the default for all pre-defined
hashers in adthashfunct, and should be used by your own ones.

Let's now choose a type for the container storing orders. To have an
opportunity to better present the features of the PascalAdt library
let it be something else than a hash table. It might be, for instance,
a sorted set - TSortedSetAdt. This is the same as TSetAdt, but with an
additional requirement that the items in the set are kept in a sorted
order. So when you traverse the set with an iterator, on which later,
the items come in a sorted sequence, in contrast to a hash table, in
which they usually come in a random order. Various search trees fall
into the category of sorted sets. One of them, which guarantees an
O(log(n)) time for all set operations, is the AVL-tree(1) - TAvlTree.

(1) The name comes from the initials of the names of the tree's
    Russian inventors: Adelson-Velskii and Landis.

The declaration and the code constructing the tree might look like the
following.

   var
      allOrders : TSortedSetAdt;
   // ...
   allOrders := TAvlTree.Create;
   allOrders.ItemComparer := TOrderComparer.Create;
   // ...

A comparer must be separately defined for comparing the TOrder
objects.

   TOrderComparer = class (TFunctor, IBinaryComparer)
   public
      function Compare(obj1, obj2 : TObject) : Integer;
   end;

   // ...

   function TOrderComparer.Compare(obj1, obj2 : TObject) : Integer;
   begin
      Result := TOrder(obj1).orderId - TOrder(obj2).orderId;
   end;

In the comparer, the orders are compared according to their unique
IDs.

3.2 Searching for items.

Assume that we have already inserted some orders and now want to check
if an order with a given ID is present in allOrders, and if yes we
want to print its data to the screen. The following function does the
trick.

   procedure FindOrder(orderId : Cardinal);
   var
      order : TOrder;
      orderKey : TOrder;
   begin
      orderKey := TOrder.Create;
      try
         orderKey.orderId := orderId;
         order := TOrder(allOrders.Find(orderKey));
         if order <> nil then
         begin
            PrintOrder(order);
         end else
         begin
            WriteLn('Invalid order ID.');
         end;
      finally
         orderKey.Free;
      end;
   end;

The TSetAdt.Find() method takes one argument which is an item that
should be found. Or more precisely, an item equal to the item searched
according to the comparer passed to the container's constructor. It
returns the first item equal to the argument or nil if there is no
such item. Note that as the argument we use a TOrder object whose only
initialized field is orderId. This is perfectly legal since our
comparer uses this field only and does not access the others. Also,
the container owns only the items which are actually inserted into the
container, not all that are passed to some of its methods. It,
therefore, does not try to destroy the argument, but the only thing it
does with it is to pass it to the comparer's method.

3.3 Inserting items.

Let's now take a closer look at the procedure adding an order to the
database.

   procedure AddOrder;
   var
      order : TOrder;
      surname, firstName : String;
      customerKey : TCustomer;
   begin
      order := TOrder.Create;

      try
         WriteLn('Enter order data.');
         with order do
         begin
            Write('Product name: '); ReadLn(productName);
            Write('Price: '); ReadLn(price);
         end;
         Write('Customer first name: '); ReadLn(firstName);
         Write('Customer surname: '); ReadLn(surname);

         { check if the specified customer is present in the database }
         customerKey := TCustomer.Create(firstName, surname);
         try
            order.customer := TCustomer(allCustomers.Find(customerKey));
         finally
            customerKey.Free;
         end;

         if order.customer <> nil then
         begin
            order.orderId := unusedOrderId;
            Inc(unusedOrderId);
            order.customer.Orders.PushBack(order);
            if not allOrders.Insert(order) then
               WriteLn('Error! Impossible!');
            WriteLn('Order successfully added.');
            WriteLn('Order ID: ', order.orderId);
         end else
         begin
            order.Destroy;
            WriteLn('Invalid customer specified.');
         end;
      except
         { if an exception occurs the order is not automatically destroyed
           (even if it occurs in allOrders.Insert) }
         order.Destroy;
         raise;
      end;
   end;

First, a TOrder object is created and assigned to the variable named
order. Next, the user is prompted for the data necessary for the
order. Then it is checked whether the specified customer exists. This
is roughly the same as when searching in allOrders. Note that
comparerKey is not owned by allCustomers, so it should be destroyed by
the caller. Hence the try ... finally clause.

If the customer is found then the order is assigned a unique ID,
pushed at the back of the list of orders in the customer object
(ignore it for now), and inserted into the allOrders set. The function
used to insert items into a set is named Insert. It returns true if
the item is successfully inserted, false otherwise. When an item may
not be inserted succesfully? To answer this question we need to know
about one property declared in TSetAdt, namely, RepeatedItems. It may
be set by the user and is true if multiple items, i.e. all pairwise
equal according to the used comparer, are allowed. If they are not
allowed, Insert may return false to indicate that its argument is
already present in the container. If RepeatedItems is true it always
returns true. RepeatedItems is false by default, but our order IDs are
supposed to be unique, so it is impossible for Insert to return false
in this case, anyway. Note that if some error occurs while inserting
an item Insert does not return false but raises an
exception. Inserting a duplicated item is not considered to be an
error. So when Insert returns false it means 'You are trying to insert
a duplicated item while RepeatedItems is set to false' and never
anything else.

3.4 Removing items.

Let's take a look at the procedure removing an order.

   procedure RemoveOrder(orderId : Cardinal);
   var
      order : TOrder;
      orderKey : TOrder;
      comparer : IBinaryComparer;
   begin
      orderKey := TOrder.Create;
      try
         orderKey.orderId := orderId;
         order := TOrder(allOrders.Find(orderKey));
         if order <> nil then
         begin
            { remove the order from the list of the customer associated with
              it }
            comparer := TOrderComparer.Create;
            DeleteIf(order.customer.Orders.ForwardStart, MAXINT,
                     EqualTo(comparer, order));

            { remove the order itself }
            if allOrders.Delete(orderKey) = 0 then
               WriteLn('Error! Impossible!');

            WriteLn('Order ', orderId, ' successfully removed.');
         end else
         begin
            WriteLn('Invaid order ID.');
         end;
      finally
         orderKey.Destroy;
      end;
   end;

Ignore the DeleteIf() line for now and concentrate on the ones
below. The TSetAdt.Delete() method is used to remove an item from the
set. As with Find(), we have to provide a TOrder with only necessary
fields filled in. Delete removes all items equal to the argument and
returns the number of items actually removed. If OwnsItems is true
then the items are also destroyed upon removal. If RepeatedItems is
false only two returns are possible: 0 and 1. Since in this particular
function Delete() is invoked only if Find() returns a non-nil pointer,
it is impossible for it to return 0.

4. Lists.

4.1. Basic information.

It would also be nice to have an instant access to the orders made by
a given customer. This can be accomplished by keeping a list of all
orders of the customer with the customer data. In the PascalAdt
library there are three implementations of lists, all of them defined
in adtlist.i. TSingleList is a singly-linked list, derived directly
from TListAdt. TDoubleList and TXorList are doubly-linked lists. Both
of them are immediate descendants of TDoubleListAdt. Of course, many
more containers such as arrays may be used in the same fashion as
lists, provided that they are descendants of TListAdt. However, some
typical list methods may be less efficient in those containers.

For our purposes a singly-linked list is completely sufficient. The
list is created in the constructor of TCustomer.

   constructor TCustomer.Create(aFirstName, aSurname, aAddress : String);
   begin
      // ...
      FOrders := TSingleList.Create;
      FOrders.OwnsItems := False;
   end;

The OwnsItems property of FOrders needs to be set to False because the
orders are already owned by the allOrders container. Otherwise, the
order objects would be freed twice.

4.2 Inserting items.

Let's go back to the AddOrder routine, or rather the part of it
dealing with updating the list of a customer's orders.

   // ...
   order.customer.Orders.PushBack(order);
   // ...

The procedure PushBack pushes an item at the back of a list. There is
also a procedure PushFront, which adds an item at the front. Inserting
in the middle of a list is achieved by means of an iterator and will
be discussed later.

5. Iterators.

We still do not know how to enumerate items of a container. That is
not much of a problem for sets but a grave disadvantage for things
like lists, in which the only way of accessing items is to somehow
traverse the whole container. The way to achieve this is with
iterators.

5.1. Basic information.

If you happen to be familiar with the C++ STL library or just with the
a bit more sophisticated concepts of object-oriented programming you
already know what iterators are. They represent a position within a
container viewed as a sequence of items. Incidentally, most of the
data structures like trees or priority queues, which are not
traditionally seen as sequences, may be considered to be such with
some necessary restrictions.

In other words, iterators are in a way enchanced pointers. They point
to some item, allow to move to the next, but offer some additional
features, and sometimes impose restrictions.

5.2. Ranges.

A pair of iterators denotes a range if both of the iterators belong to
the same container and the first in the pair is closer to the
beginning of the sequence than the second one. Alternatively, they may
both point to the same item. In that case they denote an empty range.

The first iterator in the pair is referred to as the 'start iterator'
of the range. It denotes the first item of the range. The second
iterator is referred to as the 'finish iterator' of the range. It
denotes the first position outside the range. The item pointed to by
the finish iterator is therefore not included in the range.

Almost every container has two methods - Start and Finish - returning
an iterator to the first item in the container and an iterator to the
one-beyond-last position, respectively. The one-beyond-last position
is an invalid position. You cannot access an item at this position. It
only serves to indicate the end of the range comprising the whole
container.

5.3. Simplified class hierarchy.

All abstract iterator classes serving as general interfaces are
defined in adtiters. There are numerous other concrete iterators
implementing the methods defined in those abstract ones. They are
scattered over various units. In this section, we provide a simplified
description of the class hierarchy of abstract iterator classes and a
brief synopsis of each of their methods.

5.3.1. TIterator.

TIterator is the ancestor of all iterators. It declares several basic
methods, the most important of which are:

   property Item : Pointer read GetItem write SetItem;

The Item property provides access to the item to which the iterator
points.

   function Owner : TContainerAdt; virtual; abstract;

Owner() returns the owner of the iterator. The owner is the container
into which the iterator points.

   function Equal(const Pos : TIterator) : Boolean; virtual; abstract;

The Equal() function returns true if Pos is equal to self. In other words, if
they both point to the same position within the same container. Note,
however, that it is assumed that they do point into the same container
and this case is not checked. So it is an error to try to test whether
two iterators belonging to two different containers are equal with
this function. If at some point in your code you are not sure whether
two iterators belong to the same container or not, always check it by
comparing what their Owner functions return.

   procedure ExchangeItem(iter : TIterator); virtual; abstract;

ExchangeItem() exchanges self.Item with iter.Item. Self and iter may
have different owners.

5.3.2. TForwardIterator.

TForwardIterator is probably the most commonly used kind of
iterator. It represents an iterator which allows moving forward, like
in a singly-linked list. Some of its methods include:

   procedure Advance; overload; virtual; abstract;

The Advance procedure moves the iterator one position forward.

   procedure Insert(obj : TObject); overload; virtual; abstract;

In general, Insert is defined to insert obj somewhere in the container
and move to where obj has been inserted. It is not precisely defined
where this 'somewhere' is. All descendants of TListAdt insert just
before the position they point to.

   function Extract : Pointer; virtual; abstract;

The Extract function returns the item pointed to by the iterator,
removes it from the container and advances to the next position. It
does not destroy the item even if OwnsItems is true, only returns it.

   procedure Delete; overload;

Delete is the same as Extract, but destroys the item instead of
returning it.

   function IsFinish : Boolean; virtual; abstract;

Returns true if self is the finish iterator, with regard to the whole
container. That is, if it points to the one-beyond-last position.

5.3.3. TBidirectionalIterator.

TBidirectionalIterator represents an iterator allowing to move in two
directions, one step at a time, like in a doubly-linked list. It
introduces only one procedure, namely Retreat, which moves the
iterator one position backwards.

5.3.4. TRandomAccessIterator.

TRandomAccessIterator represents an iterator which allows to move in
both directions any number of positions at once. It introduces several
new methods. Most important of them follow.

   procedure Advance(i : IndexType);

Advances self by i positions forward. If i is negative goes abs(i)
positions backward.

   property Items[ind : IndexType] : TObject; default;

Provides access to the item at the distance ind from self. So, for
instance, iter[0] is roughly equivatent to iter.Item, iter[5] to
iter.Advance(5); iter.Item; iter.Advance(-5);.

   function Distance(const Pos : TRandomAccessIterator) : IndexType;

Returns the distance from self to pos, i.e. the number of positions
that must be traversed to get to pos. If pos is closer to the
beginning of the container than self, the result is negative.

5.3.5. TSetIterator.

TSetIterator is a bidirectional iterator with some restrictions
imposed on the access to the items. Because the position of an item in
a set is internally defined, i.e. the items cannot be moved around at
will, it is illegal to change the item in such a way that the value of
its 'key' changes. Additionally, items cannot be exchanged.

5.4. Invalidation of iterators.

Iterators may become invalid as a side effect of invoking some
container methods. Invalid iterators should not be accessed at
all.

The methods that invalidate iterators are precisely those that change
something in the internal structure of a container. Any container
methods deleting, extracting or inserting items invalidate all
iterators into this container. Any iterator methods deleting,
extracting or inserting items invalidate all iterators into the owner
container except for the iterator on which the method is invoked.

5.5. Ownership issues.

The good news is that you don't have to worry about destroying
iterators. They are all owned by their containers and automatically
managed by them. Another good thing is that usually nothing terrible
will happen if you nonetheless decide to destroy an iterator by
yourself. It is actually desirable for users to destroy iterators by
themselves as they are freed only periodically and only when it is
impossible that they may be accessed by the user, which usually
happens to be when some method invalidates them. It should be pointed
out that it is legal for the user to destroy iterators only if they
are valid. Invalid iterators should be treated as if they were already
destroyed.

5.6. Example.

To put this all into practice let's consider an example of a usage of
iterators taken from our customer.pas program. Here is the PrintOrders
procedure.

   procedure PrintOrders;
   var
      iter : TForwardIterator;
   begin
      iter := allOrders.Start;
      while not iter.IsFinish do
      begin
         PrintOrder(iter.Item);
         iter.Advance;
      end;
   end;

It simply iterates through all the items in allOrders using a function
PrintOrder defined earlier in the program. The skeleton outlined in
the code above is what you should use to iterate through all items of
a container. One might be tempted to write something like this:

   while not iter.Equal(allOrders.Finish) do
   begin
      PrintOrder(iter.Item);
      iter.Advance;
   end;

What's wrong with this? Think a while. (... a space for thinking ...)
If you still don't get it I'll tell you. There is nothing wrong if
allOrders contains a small number of items. But assume that it
contains, say, 50 000 items. Each time the comparison is made the
Finish function creates one iterator. This iterator is not destroyed,
because there are no methods invalidating iterators called within the
loop. So we finally end up with 50 000 unfreed and unused iterators
eating up memory until some invalidating method destroys them.

To remedy this situation, one might decide to change the above loop
into the following.

   finish := allOrders.Finish;
   while not iter.Equal(finish) do
   begin
      PrintOrder(iter.Item);
      iter.Advance;
   end;

This is slightly less efficient than the version with
IsFinish but completely correct. However, assume that we want to
change the loop so that the items are deleted once they are
printed. The obvious way to do this is:

   finish := allOrders.Finish;
   while not iter.Equal(finish) do
   begin
      PrintOrder(iter.Item);
      iter.Delete;
   end;

But wait - it's a disaster! The Delete() method invalidates all
iterators into allOrders except for iter. Except for iter only. So
finish is invalidated and possibly destroyed. Most probably a
segmentation fault.

The conclusion is that when iterating up to the end of a container
IsFinish should be used. Also, when iterating through a range caution
should be taken not to insert any invalidating method calls inside the
loop.

6. Algorithms.

Similarly to C++ STL, in the PascalAdt library most algorithms are
implemented to deal with ranges and not whole containers. This gives
much greater flexibility and generality, but undoubtedly complicates
things a bit.

All sequence algorithms are defined in adtalgs.

To get started let's look at the PrintCustomer routine, which prints
the data associated with a customer.

   procedure PrintCustomer(obj : TObject);
   var
      customer : TCustomer;
   begin
      Assert(obj is TCustomer);
      customer := TCustomer(obj);
      with customer do
      begin
         WriteLn;
         WriteLn('--------------------------------------------');
         WriteLn('Name: ', FirstName, ' ', Surname);
         WriteLn('Address: ', Address);
         WriteLn('Current number of orders: ', Orders.Size);
         WriteLn('Orders: ');
         ForEach(Orders.ForwardStart, Orders.ForwardFinish,
                 Adapt(@PrintOrderWithoutCustomerInfo));
      end;
   end;

The line that is of particular interest to us is the one with the
invocation of the ForEach routine. Algorithms are simply routines
which take iterators as arguments and perform a certain task on the
range (or ranges) represented by them, sometimes using some additional
functors. The ForEach algorithm simply applies its third argument,
which is an IUnaryFunctor, to every item in the range denoted by its
first two arguments. In this example, the third argument is a functor
returned by the Adapt function. Adapt simply takes a pointer to an
ordinary Pascal function or procedure as an argument and returns a
functor which does exactly the same job as the argument. The returned
functor just calls the routine through a pointer whenever it is
invoked.

Note also that the methods used here to obtain the start and finish
iterators are not, as usual, named Start and Finish, but ForwardStart
and ForwardFinish, respectively. This is because there is nothing like
covariant returns in Object Pascal, i.e. it is not possible to make a
method in a descendant class return a descendant of the return value
type of the same method in an ancestor class. Therefore, if the method
in TListAdt returning the start iterator, which at that stage can be
only guaranteed to be a TForwardIterator, was named Start, then a
method in a descendant class either can't be named Start as well or it
must return a descendant of TForwardIterator. Except for sets and
maps, for which the descendants of TSetIterator or TMapIterator don't
differ much from their ancestors, all methods of any abstract
container class returning iterators have the 'stem' of the name of the
type of the returned iterator prepended to their names.

If the above babble has made you tired, consider the following example
to relax a bit.

   procedure PrintCustomers;
   var
      buff : TPascalArrayType;
      iter : TForwardIterator;
      a : TPascalArray;
      comparer : IBinaryComparer;
      i : Integer;
   begin
      SetLength(buff, allCustomers.Size);

      iter := allCustomers.Start;
      i := 0;
      while not iter.IsFinish do
      begin
         buff[i] := iter.Item;
         Inc(i);
         iter.Advance;
      end;

      a := TPascalArray.Create(buff);
      { It is necessary to indicate that 'a' should not destroy its items.
        By default all containers own their items. }
      a.OwnsItems := False;
      try
         comparer := TCustomerComparer.Create;

         Sort(a.Start, a.Finish, comparer);
         WriteLn('Registered customers:');
         ForEach(a.Start, a.Finish, Adapt(@PrintCustomerName));
      finally
         a.Free;
      end;
   end;

This function prints the names of all customers in allCustomers. The
allCustomers container is a hash table, so if we just iterated through
all the items in it the names would come up in a random fashion
producing a list really hard to read. What we do is to copy the items
into a buffer, sort them, and then print them out. We need the buffer
because, as you remember, items in a hash tables cannot be moved
around - their places are fixed.

PascalArrayType is defined in adtarray as 'array of TObject'.
TPascalArray is a wrapper class which adapts an Object Pascal dynamic
array to the TArrayAdt interface, thus enabling it to be used with the
PascalAdt sequence algorithms. Since the items are already owned by
allCustomers, we need to set a.OwnsItems to False.

Let's take a look at the Sort() routine. It takes a range to be sorted
and a comparer as arguments. The Sort() routine does not do the
sorting itself, but chooses an appropriate algorithm, QuickSort() or
InsertionSort(), depending on the number of items in the range.

Two lines further down, the ForEach() algorithm is used to print the
names of the customers. It uses the PrintCustomerName routine defined
elsewhere.

Brief descriptions of all algorithms can be found in the documentation
for the adtalgs module, together with the algorithms' definitions.

7. Compositions of functors.

Let's go back to the RemoveOrder procedure and take a closer look at
the following lines.

   // ...
   { remove the order from the list of the customer associated with
     it }
   comparer := TOrderComparer.Create;
   DeleteIf(order.customer.Orders.ForwardStart, MAXINT,
            EqualTo(comparer, order));
   // ...

The DeleteIf() algorithm deletes all items for which the predicate
passed as the last argument returns ture. It is unlike other
algorithms in that it does not take a range, but the iterator starting
a range and the number of items. If the end of the container comes
before the specified number of items is visited, then the algorithm
exits. Here, MAXINT is specified, which has the effect of taking into
account all positions starting from the first argument up to the end
of the container.

But what is interesting here is the function EqualTo(). It is one of
the numerous functions in adtfunct used to modify the behaviour of
functors. EqualTo() returns a unary predicate which compares its
argument against the second argument passed to EqualTo(), using the
comparer passed as the first one. It returns true if, and only if, the
comparer returns 0. Other functions which work in an analogous way
include LessThan() and GreaterThan().

There are numerous other functor functions, i.e., functions operating
on functors and modifying their behaviour. Several examples
follow. Negate() takes a predicate pred and returns a predicate
returning true if and only if pred returns false. Bind1st() and
Bind2nd() take a binary functor or predicate f and an object obj, and
return an unary functor or predicate, respectively, which acts as if f
was called with one of the arguments being obj and the second one the
argument passed to the unary functor. The Compose- family of functions
makes it possible to create a functor composed of one or more
functors.

Functor functions are vary handy and sometimes save much
typing. However, they should be used with caution. Basically,
'nesting' too many functor functions should be avoided.

Let's take the following call as an example.

   r := PredOr(PredAnd(Negate(EqualTo(f, obj1)), LessThan(g, obj2)),
               EqualTo(h, obj2));

Assuming f, g and h are IBinaryComparers, r is an IUnaryPredicate
defined to be roughly the following:

   r(x) := ((f(x, obj1) <> 0) and (g(x, obj2) < 0)) or (h(x, obj2) = 0)

Each time a functor function is called a new object is created, so as
a result of this call six objects are created. That's not the main
problem, though. The problem is that there are six additional virtual
routine calls each time the resulting functor is invoked. This is
probably insignificant if the original functors perform some lengthy
jobs anyway, but if they only perform some simple arithmetic
operations and the resulting functor is later applied to a large
number of items, then the overhead might be considerable.

In conclusion, don't use more than two or three functor functions to
create one functor.

III. Where to find more information?

The algorithms and container types discussed in this tutorial are only
a fraction of what is available. We refer to the online PascalAdt API
reference for more information:

https://pascaladt.github.io/pascaladt-docs/

The full source code of the customer.pas program, with many functions
not discussed here, is available in demo/customer/customer.pas.

IV. Author.

The author of this tutorial and the PascalAdt library is Lukasz
Czajka.