Numerics 0.57 released (Hashtables, Bugfix)

2

1. The main purpose of the release is to implement hash tables (aka associative arrays) with keys of BigCardinal or BigInteger type; such hash tables are important for cryptographic applications. The hash tables in Delphi are implemented by a generic TDictionary<TKey,TValue> class. The release includes a new unit GNumerics.pas with two helper generic classes TBigIntegerDictionary<TValue> and TBigCardinalDictionary<TValue> specializing the base generic dictionary class. For example to work with a hash table having BigInteger keys and string values you need something like this:

uses GNumerics;

[..]
var
  HashTable: TBigIntegerDictionary<string>;
  A: BigInteger;

[..]
begin
// create hash table instance
  HashTable:= TBigIntegerDictionary<string>.Create;
  A:= BigInteger('1234567890987654321');
  try
// fill hash table with data
    HashTable.Add(A * A, 'some string value');
    [..]
  finally
// destroy hash table
    HashTable.Free;
  end;
end;

2. Some bugs fixed; in particular a nasty access violation bug in BigInteger.ModPow function was fixed.

3. Minor changes in BigCardinal/BigInteger methods.

Link to the download page

Update

Version 0.58 fixes the conversion bug from (U)Int64 to BigInteger/BigCardinal.

Advertisements

Implementing generic interfaces in Delphi

9

Delphi supports generic interfaces; for example we can declare a generic interface

type
  IChecker<T> = interface
    function Check(const Instance: T): Boolean;
  end;

and use this generic interface as follows:

unit UseDemo;

interface

uses GenChecks;

type
  TDemo<T> = class
  private
    FChecker: IChecker<T>;
  public
    constructor Create(AChecker: IChecker<T>);
    procedure Check(AValue: T);
  end;

implementation

{ TDemo<T> }

procedure TDemo<T>.Check(AValue: T);
begin
  if FChecker.Check(AValue)
    then Writeln('Passed')
    else Writeln('Stopped')
end;

constructor TDemo<T>.Create(AChecker: IChecker<T>);
begin
  FChecker:= AChecker;
end;

end.

To implement the above generic interface IChecker we need a generic class; the straightforward solution is

type
  TChecker<T> = class(TInterfacedObject, IChecker<T>)
    function Check(const Instance: T): Boolean;
  end;

If the IChecker interface can be implemented like that, we need nothing else. The problem with the above implementation is that we are limited to the generic constraints on the type T and can’t use properties of specific types like Integer or string that will finally be substituted for the type T.

A more elastic solution is to introduce an abstract base type and derive the specific implementations from it. Here is a full code example:

program GenericEx1;

{$APPTYPE CONSOLE}

uses
  SysUtils,
  GenChecks in 'GenChecks.pas',
  UseDemo in 'UseDemo.pas';

procedure TestInt;
var
  Demo: TDemo<Integer>;

begin
  Demo:= TDemo<Integer>.Create(TIntChecker.Create(42));
  Demo.Check(0);
  Demo.Check(42);
end;

procedure TestStr;
var
  Demo: TDemo<string>;

begin
  Demo:= TDemo<string>.Create(TStrChecker.Create('trololo'));
  Demo.Check('ololo');
  Demo.Check('olololo');
end;

begin
  TestInt;
  TestStr;
  ReadLn;
end.
unit GenChecks;

interface

type
  IChecker<T> = interface
    function Check(const Instance: T): Boolean;
  end;

type
  TCustomChecker<T> = class(TInterfacedObject, IChecker<T>)
  protected
    FCheckValue: T;
    function Check(const Instance: T): Boolean; virtual; abstract;
  public
    constructor Create(ACheckValue: T);
  end;

  TIntChecker = class(TCustomChecker<Integer>)
  protected
    function Check(const Instance: Integer): Boolean; override;
  end;

  TStrChecker = class(TCustomChecker<string>)
  protected
    function Check(const Instance: string): Boolean; override;
  end;

implementation

{ TCustomChecker<T> }

constructor TCustomChecker<T>.Create(ACheckValue: T);
begin
  FCheckValue:= ACheckValue;
end;

{ TIntChecker }

function TIntChecker.Check(const Instance: Integer): Boolean;
begin
  Result:= Instance = FCheckValue;
end;

{ TStrChecker }

function TStrChecker.Check(const Instance: string): Boolean;
begin
  Result:= Length(Instance) = Length(FCheckValue);
end;

end.

In the above example each interface reference ICheck references its own class instance; this is necessary because every instance contains a parameter (FCheckValue) set in the constructor. If an implementation does not require such a parameter creating new instances for every interface reference will be an overhead. A better solution is to use a singleton instance.

Here is a full code example for the integer type:

program GenericEx2;

{$APPTYPE CONSOLE}

uses
  SysUtils,
  GenChecks in 'GenChecks.pas',
  UseDemo in 'UseDemo.pas';

procedure TestInt;
var
  Demo: TDemo<Integer>;

begin
  Demo:= TDemo<Integer>.Create(TIntChecker.Ordinal);
  Demo.Check(0);
  Demo.Check(42);
end;

begin
  TestInt;
  ReadLn;
end.
unit GenChecks;

interface

uses Generics.Defaults;

type
  IChecker<T> = interface
    function Check(const Instance: T): Boolean;
  end;

  TCustomChecker<T> = class(TSingletonImplementation, IChecker<T>)
  protected
    function Check(const Instance: T): Boolean; virtual; abstract;
  end;

  TIntChecker = class(TCustomChecker<Integer>)
  private
    class var
      FOrdinal: TCustomChecker<Integer>;
  public
    class function Ordinal: TIntChecker;
  end;

implementation

type
  TOrdinalIntChecker = class(TIntChecker)
  public
    function Check(const Instance: Integer): Boolean; override;
  end;

{ TOrdinalIntChecker }

function TOrdinalIntChecker.Check(const Instance: Integer): Boolean;
begin
  Result:= Instance = 42;
end;

{ TIntChecker }

class function TIntChecker.Ordinal: TIntChecker;
begin
  if FOrdinal = nil then
    FOrdinal := TOrdinalIntChecker.Create;
  Result := TIntChecker(FOrdinal);
end;

end.

Generic musings 2

9

It was pointed out in the comments to my previous post that my simple generic sorting routine contains additional overhead compared to TArray Rtl code (Generic.Collections & Generic.Defaults units) because RTTI is used inside the loop. Yes, that is true. Let us improve the code by taking RTTI check away from the loop, while keeping the code simple (without using over-weighted and tricky IComparer interface).

Simple tasks should have simple solutions. Now when I look at it the solution seems quite obvious, still I spent some hours trying to find it – generics are weird for beginner. The last step that led to working code was to declare generic procedural type TCompare inside generic class TArray, without it the code would not compile:

unit GenericSort;

interface

type
  TArray<T> = class
  public type
    TCompare = function(const L, R: T): Integer;
  private
    class procedure InternalSort(var A: array of T;
      Compare: TCompare); static;
  public
    class procedure InsertionSort(var A: array of T); static;
  end;

function CompareInt(const L, R: Integer): Integer;

implementation

uses SysUtils, TypInfo;

class procedure TArray.InternalSort(var A: array of T; Compare: TCompare);
var
  I, J: Integer;
  Item: T;
  P: PTypeInfo;

begin
  for I:= 1 + Low(A) to High(A) do begin
    Item:= A[I];
    J:= I - 1;
    while (J >= Low(A)) and (Compare(A[J], Item) > 0) do begin
      A[J + 1]:= A[J];
      Dec(J);
    end;
    A[J + 1]:= Item;
  end;
end;

function CompareInt(const L, R: Integer): Integer;
begin
 if L < R then Result:= -1
  else if L > R then Result:= 1
  else Result:= 0;
end;

class procedure TArray.InsertionSort(var A: array of T);
var
  P: PTypeInfo;

begin
  P:= TypeInfo(T);
  case P^.Kind of
    tkInteger: InternalSort(A, @CompareInt);
    tkUString: InternalSort(A, @CompareStr);
  end;
end;

end.

Note that the function ‘CompareInt’ is declared in interface section. If you comment out interface declaration you get compile error

[DCC Error] GenericSort.pas(54): E2506 Method of parameterized type declared in interface section must not use local symbol ‘CompareInt’.

Generic musings

7

Delphi (as Pascal descendant) has always had powerful type system. Consider the following sample code implementing simple insertion sort algorithm (I use Delphi 2009):

unit InsSort;

interface

type
  TItem = Integer;
  TArray = array of TItem;

procedure InsertionSort(var A: TArray);

implementation

procedure InsertionSort(var A: TArray);
var
  I, J: Integer;
  Item: TItem;

begin
  for I:= 1 + Low(A) to High(A) do begin
    Item:= A[I];
    J:= I - 1;
    while (J >= Low(A)) and (A[J] > Item) do begin
      A[J + 1]:= A[J];
      Dec(J);
    end;
    A[J + 1]:= Item;
  end;
end;

The above code sorts integer array; if we need to sort array of strings, all we have to do is to switch TItem type declaration from Integer to string:

type
  TItem = string;

If our task is to sort both integer and string arrays we should have two separate source code units (though they differ just by one word). Clearly that is code duplication that can’t be solved in plain Pascal. But Delphi has generics, let us try generics. Naive

  procedure InsertionSort<TItem>(var A: array of TItem);

does not compile, we need class to use generics; we also need some means to compare generic types, so I have written the following simple generic class:

type
  TArray<TItem> = class
    class function Compare(const L, R: TItem): Integer; static;
    class procedure InsertionSort(var A: array of TItem); static;
  end;

implementation

uses SysUtils, TypInfo;

class function TArray<TItem>.Compare(const L, R: TItem): Integer;
var
  P: PTypeInfo;

begin
  P:= TypeInfo(TItem);
  case P^.Kind of
    tkInteger: begin
      if PInteger(@L)^ < PInteger(@R)^ then Result:= -1
      else if PInteger(@L)^ > PInteger(@R)^ then Result:= 1
      else Result:= 0;
    end;
    tkUString: Result:= CompareStr(PString(@L)^, PString(@R)^);
  end;
end;

class procedure TArray<TItem>.InsertionSort(var A: array of TItem);
var
  I, J: Integer;
  Item: TItem;

begin
  for I:= 1 + Low(A) to High(A) do begin
    Item:= A[I];
    J:= I - 1;
//    while (J >= Low(A)) and (A[J] > Item) do begin
    while (J >= Low(A)) and (Compare(A[J], Item) > 0) do begin
      A[J + 1]:= A[J];
      Dec(J);
    end;
    A[J + 1]:= Item;
  end;
end;

It works but it looks ugly. Think also of crazy overhead of generic comparison, especially for plain types like Integers that are normally compared by just a single assembler instruction. Delphi 2009 Rtl (Generics.Defaults.pas unit) provides more elegant (and more lengthy) solution based on IComparer generic interface, but it boils down to the same inefficient runtime type information usage.

But why we need the ‘Compare’ function at all? By the time the compiler generates code for generic TItem type the compiler should already know actual type to substitute for TItem, and using the actual type it can compile the elegant line

    while .. (A[J] > Item) ..

much more efficiently than the ugly

    while .. (Compare(A[J], Item) > 0) ..

The idea of direct efficient Generic comparison also invokes Haskell’s ‘type class’ concept. The ‘Type class’ is something very different from OOP class. In Haskell every type is an instance of many type classes. For example integer type is an instance of ‘Eq’ type class because integers can be compared for equality, of ‘Ord’ type class because all comparison operation (<, <=, >, >=) are applicable to integers, of ‘Show’ type class because integers can be converted to string, etc. In our case the generic TItem type should be an instance of ‘Ord’ type class.