YAPB

In the previous post I have mostly talked about Enex (Enumerable Extensions) I have enabled for all DeHL’s collection classes. Now I will list the other changes that got into this release that may be of interest to you:

• Enex (Enumerable Extensions) in DeHL.Collections.Enex. Support for chained queries, predicates and selectors.
• THashTree (A tree that uses hashes to access the child nodes). in DeHL.Collections.HashTree.
• TConverter can be created with given IType‘s as opposed from the default ones.
• TSuppressedWrapperType which can be used to wrap another IType. It’s main function is to forward all calls to the enclosed IType except the Cleanup() and Management() ones. This way you can use temporary collections inside your collection without the “cleanup” problem.
• Fixed 2 bugs in Resize() method of THashSet and TDictionary which resulted in corrupted heap in some cases.
• TLinkedList properties called First and Last were renamed to FirstNode and LastNode to avoid naming conflicts with Enex’s First() and Last() methods.
• Fixed a bug in TQueue‘s enumerator object. It enumerated the queue’s elements quite wrong.
• Renamed TScopedPtr to a better name: Scoped.
• Added a new type: Nullable. It can be used to represent a NULL value for non-object types such as Integer.
• New life-time extensions for TRefCountedObject. Each ref-counted object can now “keep-alive” other ref-counted objects. This was an useful addition in order to support query-chains in Enex.

How to use the new Nullable<> type:

function GetTheSum(const AList: TList<Integer>):
    Nullable<Integer>;
begin
  { Check if the list is non-null and has elements }
  if (AList = nil) or (AList.Count = 0) then
    Result.MakeNull();
  else
    Result := AList.Sum();
end;

var
  LSum: Nullable<Integer>;
begin
  { ... }
  LSum := GetTheSum(...);
  if not LSum.IsNull then
    WriteLn(LSum.Value);
end;

I agree, this is not the best example, but it is OK to get you started. Nullable values are useful when you function may return or even accept a normal (let’s say Integer) value or a NULL.

Since I have started working on DeHL, one of the main purposes was to get to the point where I could use Linq-like extensions on collection classes. Of course I could not call the new functionality Linq since it’s not language-integrated, so I decided to give it another name: Enex (aka Enumerable Extensions). All collection classes in DeHL now support a wide set of methods that allow querying and selecting elements from the starting collection. A lot of work has been put into this release, ranging from extensions to type system, object life-time management, optimizations and bug-fixes and of course a lot of testing.

Now, back to Enex, let’s visit some cool examples of what the new functionality can do:

Let’s check a very simple example. Assuming you have a list of integers and you want to find the sum of all elements that are greater than the list average. In the “times before” you wold write something like this:

  { Calculate the average of the list }
  Sum := 0;

  for I := 0 to List.Count - 1 do
    Sum := Sum + List[I];

  Avg := Sum div List.Count;

  { Calculate the sum of the elements above average }
  Sum := 0;

  for I := 0 to List.Count - 1 do
    if List[I] > Avg then
      Sum := Sum + List[I];

… Now it is as simple as this:

  { ... }
  Sum := List.WhereGreater(List.Average()).Sum();
  { ... }

Now, let’s see another more complex example. Considering that you have two collections of integers. You have to determine the maximum value common to both collections. Check it out:

  { ... }
  Max := AColl1.Intersect(AColl2).Max();
  { ... }

Next: what is the sum of all odd numbers in interval [0..100]?

  Sum := TEnexEnumerable<Integer>
    .Interval(0, 100)
    .Where(function(Arg1: Integer): Boolean
      begin
        Exit(Odd(Arg1);
      end)
    .Sum();

The last one: You want to take all integers from a list with their absolute value and only once; and you want to write them on the screen directly:

  for I in ARandomList
    .Select(function(Arg1: Integer): Integer
      begin
        Exit(Abs(Arg1));
      end)
    .Distinct()
  do
    WriteLn(I);

What’s working and what’s not:

• Some problems in the compiler prevent the use of generic function Select<TOut> and Cast<TOut> for now. These two could have been used to transform each element of the collection to some other type.
• Everything is based in interfaces to make use of automatical garbage collection. the only restriction is that the first enumerable (from which the chain starts) should be either an interface or must be destroyed explicitly.
• All collections have overriden versions of some functions. For example in a list, the First() method is implemeted directly so that you benefit from full speed whenever possible.
• No lambdas … that makes writing selectors or predicates rather unpleasant.
• Sum() and Average() are only supported for types registered as integers or reals (including BigCardinal and BigInteger).
• All selector and predicate-based selection is done on-the fly so there is no additional memory used!

There are of course much more possible use cases for Enex-enabled collections, I simply do not have the time to list all of them.

You can download the latest version of DeHL here.

In the last post I have described how enumeration works in Delphi. Now I will try to expand the subject a bit and make a more general description of what enumerability actually means and how it can solve some basic problems and patterns.

“An enumrebale is not necessarily a collection“. You should keep in mind that enumerability doesn’t apply only to collections. It is a more abstract concept. Enumeration can apply to any kind of sequence — abstract, mathematical or a collection. As an example let’s talk about streams — streams are also enumerables, in some cases these behave exactly like enumerable collections: For streams that do not have a defined size (like for example downloading a file over a HTTP stream that doesn’t say the file size). All you can do in these cases is to read bytes from the stream until you read the bottom and receive an EOF notification.

“Abstract vs concrete sequences“. An abstract sequence in my definition is one that doesn’t occupy space and each new element is generated on the fly by the enumerable. A concrete sequence is more akin to a collection which already has its elements stored somewhere and all it does is to fetch them when enumerating.

In the next example I took a known mathematical sequence which I am sure all of you are acquainted with: the Fibonacci sequence; and created an abstract enumerable which at each iteration calculates the next number:

type
  TFibonacciEnumerator = record
  private
    FCurrent, FPrev,
      FCount, FMaxCount: Cardinal;

    function GetCurrent: Cardinal;
  public
    { Move to the next calculation }
    function MoveNext(): Boolean;

    { Reads the current number }
    property Current: Cardinal read GetCurrent;
  end;

  Fibonacci = record
  private
    FLimit: Cardinal;

  public
    { Returns the enumerator object }
    function GetEnumerator(): TFibonacciEnumerator;

    { Static function that }
    class function OfLength(const ALength: Cardinal): Fibonacci; static;
  end;

{ TFibonacciEnumerator }

function TFibonacciEnumerator.GetCurrent: Cardinal;
begin
  Result := FCurrent;
end;

function TFibonacciEnumerator.MoveNext: Boolean;
var
  LTemp: Cardinal;
begin
  { Check if the end of the chain }
  if FCount >= FMaxCount then
    Exit(false);

  Result := true;

  { Make the next calculation }
  if FCount <= 1 then
    FCurrent := FCount
  else
  begin
    LTemp := FCurrent;
    FCurrent := FCurrent + FPrev;
    FPrev := LTemp;
  end;

  Inc(FCount);
end;

{ Fibonacci }

function Fibonacci.GetEnumerator: TFibonacciEnumerator;
begin
  Result.FCurrent := 0;
  Result.FPrev := 0;
  Result.FCount := 0;
  Result.FMaxCount := FLimit;
end;

class function Fibonacci.OfLength(const ALength: Cardinal): Fibonacci;
begin
  if ALength = 0 then
    raise EArgumentOutOfRangeException.Create('ALength should be > 0');

  Result.FLimit := ALength;
end;

var
  Number: Cardinal;
begin
  { Show the first 100 Fibonacci numbers }
  for Number in Fibonacci.OfLength(100) do
    WriteLn(Number);

  ReadLn;
end.

What is cool about this example is the fact that you do not occupy any memory with the calculated numbers, those are made on-the-fly.

This example did not demonstrate another important aspect of enumerables and exactly: “materializing” abstract sequences. If my Fibonacci record was actually a class derived from TEnumerable<Cardinal>, I could have written this:

var
  List: TList<Cardinal>;
begin
  List := TList<Cardinal>.Create(Fibonnaci.OfLength(100));
end.

This would have “materialized” the abstract sequence generated by the Fibonacci object and stored each value in a concrete sequence (the List collection).

Unfortunately Delphi’s generics support is at it’s infancy so not many features are yet available in the standard classes to exploit the power of Enumerables. I predict this will change over time and more cool stuff will appear either directly in the RTL or in form of 3rd-party libraries.

It is not a surprise that most programming languages in our time have the built-in support for enumerators/iterators. This is a mandatory feature since enumerators and enumerable collections simplify the development of applications and make the code cleaner. Languages such as C#, Java or Delphi have built-in syntax constructs that allow simplified and clean ways of enumerating over a collection by the means of  “foreach” or special “for” loops.

In Delphi, enumerators have been added to the language for some time now in form of a special “for” loop (you can read in the Help about it more). It allows enumerating elements of an array, string and in most collection classes. While in the case of intrinsic types, the compiler simply transforms the loop into an ordinary “for” loop, in the case of collection classes things become more interesting. But let’s take each case separately:

Enumerating over a String:

var
  LString: String;
  LChar: Char;
begin
  LString := 'Hello World';

  for LChar in LString do
    Write(c);
end;

It’s simple as that! It does not have such a negative impact on the speed and make your code look much cleaner, it also helps avoid using an index variable. The same method can be applied for AnsiString, WideString and ShortString.

Enumerating over an Array:

var
  LArr: TBytes;
  LByte: Byte;
begin
  LArr := TBytes.Create(1, 2, 3, 4, 5);

  for LByte in LArr do
    Write(LByte);
end.

Looks simple. And indeed it is! There are more use cases for different types of arrays, but you can find that in the Help.

Enumerating over a collection:

var
  List: TList<Integer>;
  I: Integer;
begin
  List := TList<Integer>.Create();
  List.AddRange([1, 2, 3, 4, 5]);

  for I in List do
    WriteLn(I);
end.

In this case the overhead for the “for” loop is higher since a call to List.GetEnumerator() is made to obtain an enumerator object. Then at each iteration the MoveNext() and Current() methods are called on the enumerator to move to the next element in the list and retrieve its value.

There are in fact only a few rules that you must abide in order to support enumeration in your collections:

1. You must have either a class, interface or record type.
2. Your class, interface or record must expose a GetEnumerator() function that returns an enumerator.
3. The enumerator can be either a class, interface or a record type.
4. The enumerator must expose a MoveNext() function that returns a Boolean and a Current property that returns the current element.
5. When the enumerator is created there is no current element selected. Only after the first call to MoveNext() your enumerator must select the first element in the collection.
6. MoveNext() must return true if the next element was selected or false if the collection is finished.

Extreme case — enumerating over a record using a record enumerator:

type
  { The enumerator record }
  TRecordEnumerator = record
  private
    FArray: TBytes;
    FIndex: Integer;

    function GetCurrent: Byte;
  public
    function MoveNext(): Boolean;
    property Current: Byte read GetCurrent;
  end;

  { The record/collection that will be enumerated }
  TRecordCollection = record
  private
    FArray: TBytes;
  public
    function GetEnumerator(): TRecordEnumerator;
  end;

{ TRecordCollection }

function TRecordCollection.GetEnumerator: TRecordEnumerator;
begin
  Result.FArray := FArray;
  Result.FIndex := -1;
end;

{ TRecordEnumerator }

function TRecordEnumerator.GetCurrent: Byte;
begin
  Result := FArray[FIndex];
end;

function TRecordEnumerator.MoveNext: Boolean;
begin
  Inc(FIndex);

  if FIndex >= Length(FArray) then
    Exit(false);

  Exit(true);
end;

var
  LColl: TRecordCollection;
  B: Byte;

begin
  LColl.FArray := TBytes.Create(1, 2, 3, 4, 5, 6);

  for B in LColl do
    WriteLn(B);

  ReadLn;
end.

The compiler doesn’t really care what it is enumerating and what it uses to do that. It simply must find the required methods exposed in the enumerated collection and in the enumerator.