Hi Free Pascal community!

I'm pleased to announce the generic library, compatible with Delphi Generics.Collections (almost ;) ).

Homepage

https://code.google.com/p/fpc-generics-collections/

SVN

http://fpc-generics-collections.googlecode.com/svn/trunk/

=== modules ===

Generics.Defaults
Generics.Collections
Generics.Helpers
Generics.Hashes

=== compatible classes ===

TEnumerator<T>
TEnumerable<T>
TList<T>
TQueue<T>
TStack<T>
TDictionary<TKey, TValue>
TObjectList<T: TObject>
TObjectStack<T: TObject>
TObjectDictionary<TKey, TValue>

=== renamed (because compiler limations/bug) ===

TArrayHelper<T> instead of TArray<T>

=== additional classes ===
************
TDictionary<TKey, TValue, TProbeSequence, THash, THashFactory> TObjectDictionary<TKey, TValue, TProbeSequence, THash, THashFactory>

TKey - key, TValue - value, THashFactory - hash factory :) TProbeSequence - TProbeSequence is special record for open addresing. To choose from a predefined:
TLinearProbing, TQuadraticProbing, TDoubleHashing, TFastLinearProbing, TFastQuadraticProbing, TFastDoubleHashing (fast version is without "mod")
more info at http://en.wikipedia.org/wiki/Open_addressing THash - type for hash (to reduce size of dictionary - can be UInt8, UInt16, UInt32 etc.)

For example, Delphi TDictionary version in this library is defined as: TDictionary<TKey, TValue> = class(TDictionary<TKey, TValue, TFastLinearProbing, UInt32, TDelphiHashFactory>);
************
TDictionaryList<TKey, TValue, TIndex, THash, THashFactory> class, that combines a TList and TDictionary

TKey - key, TValue - value, THashFactory - hash factory :) TIndex - type for index (to reduce size of dictionary - can be UInt8, UInt16, UInt32 etc.)
THash - type for hash (to reduce size of dictionary - can be UInt8, UInt16, UInt32 etc.)
************
Similar to TList, TDictionary and TDictionaryList, but uses normal operators instead of IEqualityComparer.

TFastList
TFastDictionary
TFastDictionaryList
************
TFastArrayHelper<T> - similar rules as above

=== not implemented ===

TThreadedQueue<T>

=== FAQ ===

1. How to use record as Key or Value in dictionary?

You need to wait for some compiler magic ( system functions GetReferenceToValue and GetValueSize described bolow) or add two methods to record:

    TRecord = record
      (* ... *)
      function GetValueSize: Integer; inline;
      function GetReferenceToValue: Pointer; inline;
    end;

2. How to use Pointer or some custom type as Key or Value in dictionary?

You need to wait for some compiler magic ( system functions GetReferenceToValue and GetValueSize described bolow) or use TValueHelper:

    uses
      Generics.Collections, Generics.Helpers;
    (* ... *)
      type
        TValueHelperPointer = TValueHelper<Pointer>;
      var
        d: TDictionary<TValueHelperPointer, string>;
      begin
        (* ... *)
        d.Add(nil, 'foo');

=== TODO ===

Comparer from Generics.Defaults can be optimized.

I have no knowledge of FPC compiler design, so i need a little help...

First thing : To finish my work I need critical compiler magic functions/feature. At first look mayby there is no sense for this functions but during work on Generic library it's necessary:

  function GetReferenceToValue(Value: T): Pointer; // for string types

return @s[1] or nil for empty string for Int32 return @i etc. returns a reference to the value, as

measured by human/programmer

  function GetValueSize(Value: T): Integer; // for string types return

Length(s), for Int32 returs 4 etc.

This functions should be implemented as operators (like Inc, Dec operators).

There is half-workaround/cripled solution as record/type helpers (module Generics.Helpers). Don't work for custom strings, and for custom "basic" types like:

  type MyStr = type string;
  type MyInt = type Int32;

Second thing: Bugs. Look at Critical - fix is needed to perform compatibility with Delphi and proper work.

http://bugs.freepascal.org/view.php?id=24283 (CRITICAL! Very Important!)
http://bugs.freepascal.org/view.php?id=24282 (CRITICAL! Very Important!)
http://bugs.freepascal.org/view.php?id=24254 (CRITICAL! for TArray.Sort<T>)
http://bugs.freepascal.org/view.php?id=24287 (Very Important!) http://bugs.freepascal.org/view.php?id=24072 (Very Important!) http://bugs.freepascal.org/view.php?id=24097 (Important!) http://bugs.freepascal.org/view.php?id=24064 (Important!) http://bugs.freepascal.org/view.php?id=24071 (Important!) http://bugs.freepascal.org/view.php?id=24285 (Important!) http://bugs.freepascal.org/view.php?id=24286 similar to 24285 http://bugs.freepascal.org/view.php?id=24458
http://bugs.freepascal.org/view.php?id=24098 (Frustrating) http://bugs.freepascal.org/view.php?id=24073
http://bugs.freepascal.org/view.php?id=24463

Sorry for ugly e mail. I do not have much experience with mailing lists. Waiting for testing and suggestions. I've added a zip to download:

https://code.google.com/p/fpc-generics-collections/downloads/list

2013/5/22 Maciej Izak

Nice. Now I know where all those bug reports come from :P

Are those available in Delphi as well? If not I see no use in them.

function GetReferenceToValue(Value: T): Pointer; // for string types return @s[1] or nil for empty string for Int32 return @i etc. returns a reference to the value, as

Consider this code:

=== code begin ===

procedure SomeProc(aValue: Int32);
var
   p: Pointer;
begin
    p := GetReferenceToValue(aValue);
end;

=== code end ===

The value stored in "p" will be of no significant use for you to be stored in the longterm, because aValue will be located on the stack and thus the pointer will no longer be valid once the function exits. This will also be the case for strings, arrays, records, etc. No compiler magic will change this.

measured by human/programmer function GetValueSize(Value: T): Integer; // for string types return Length(s), for Int32 returs 4 etc.

You should not store the string's content, but only the reference to the string. If you use assignment operators the RTL will take care of the rest.

Second thing: Bugs. Look at Critical - fix is needed to perform compatibility with Delphi and proper work. http://bugs.freepascal.org/view.php?id=24283 (CRITICAL! Very Important!)

I don't consider nested specializations as critical. It's likely that I will fix this after I've fixed other generic problems...

http://bugs.freepascal.org/view.php?id=24282 (CRITICAL! Very Important!)

The underlying problem is also the source of some other bugs... I'm happy when I've fixed this, but it's not highest priority... (keyword: partial specialization)

http://bugs.freepascal.org/view.php?id=24254 (CRITICAL! for TArray.Sort<T>)

I don't consider this critical. It's a missing feature that needs to be implemented and will be implemented when time permits (though I'm looking forward to having this feature available :) )

http://bugs.freepascal.org/view.php?id=24287 (Very Important!) http://bugs.freepascal.org/view.php?id=24072 (Very Important!)

Also part of "partial specialization"

http://bugs.freepascal.org/view.php?id=24097 (Important!)

Forward declarations are encountered seldomly enough so that I don't consider this as important.

http://bugs.freepascal.org/view.php?id=24064 (Important!)

Considering that your example does not compile in Delphi either and the way generics and units work I consider it as unlikely that I'll fix that.

That comes when Borland decides to use "<...>" for generic parameters... I could still kill them for that decision -.-
This won't be fixed for quite some time.

http://bugs.freepascal.org/view.php?id=24073 http://bugs.freepascal.org/view.php?id=24463

Regards,
Sven

Nice. Now I know where all those bug reports come from :P

:D It's my pleasure. Aren't you happy?

Are those available in Delphi as well? If not I see no use in them.

Consider this code:

Yes, I know that. I need this only for shortterm. In that case for safety maybe we should remove System.Addr? ;) In Delphi they do that by special interfaces created for each type (lost of time and memory). First, I can't implement this by Delphi way because we have still a lot of generics bugs. Secondly, I think that we can do much more better implementation of Generics. This is not C#, in Pascal we have better access to pointers. Now I'm using (I hope temporarily):

=== code begin ===

  TValueAnsiStringHelper = record helper for AnsiString
    function GetValueSize: Integer; inline;
    function GetReferenceToValue: Pointer; inline;
  end;
function TValueAnsiStringHelper.GetValueSize: Integer;
begin
  Result := Length(Self) * SizeOf(AnsiChar);
end;
function TValueAnsiStringHelper.GetReferenceToValue: Pointer;
begin
  if Length(Self)  0 then
    Result := @Self[1]
  else
    Result := nil;
end;

=== code end ===
Etc. for other basic types.

I, really need this for custom comparers and equality comparers, for example:

=== code begin ===
while AComparer.Compare(AValues[I].GetReferenceToValue, P.GetReferenceToValue, AValues[I].GetValueSize, P.GetValueSize) < 0 do // ...
if FEqualityComparer.Equals(AKey.GetReferenceToValue, LItem.Pair.Key.GetReferenceToValue, AKey.GetValueSize, LItem.Pair.Key.GetValueSize) then
=== code end ===

measured by human/programmer

But with generics code for some types i don't have predefined operators (for example: records), and here is the problem with Generics Dictionary. GetValueSize and GetReferenceToValue is in the same level as System.SizeOf and System.Addr.

I think it's a natural evolution System.SizeOf and System.Addr for Generics (to operate on values). There is no other language as FreePascal and it would be wrong to introduce something stupid to such an important system functions. If my thinking is wrong, please, any hint of an alternative. Without it, I'm completely stuck.

As critical error I mean - hardcore incompatibility with Delphi version of Generics.Collections. With critical error you can't compile Delphi code "as is" with this library.

Depends. On the one hand I'm happy that someone stresses the generics implementation to its limits (like JC Chu does as well), but on the other hand it means work in - in case of generics - a bunch of headaches... ;)

I still see no need for this. I would simply do

=== code begin ===

if FEqualityComparer.Equals(AKey, LItem.Pair.Key) then
   ...

=== code end ===

Why fall back to pointers for something like this if we can use static types?! And if that means that the comparer needs to be implemented for each type, then so be it (you could implement a default generic comparer, which uses the normal "=" operator, maybe some others for basic types like strings and a TObject.Equals based one and the other comparators should be supplied by the user). You can't do things as equality tests in a general way anyway (best example: case sensitive vs. case insensitive comparison of strings). If your concern is performance then you could declare the two parameters as "constref" so that they are passed by reference and not by value.

If your implementation of Generics.Dictionary needs certain operators than the type with which the dictionary is specialized needs to implement these operators. If the type does not: bad luck.

I see no need for a context sensitive SizeOf and your GetReferenceToValue is simply flawed, because you can't capture the correct location of a parameter passed by value as this is just a copy, no "@Self" will result in the correct value here. E.g.:

=== code begin ===

{$mode objfpc}
type
   TLongIntHelper = type helper for LongInt
     function GetSelfAddress: Pointer;
   end;
function TLongIntHelper.GetSelfAddress: Pointer;
begin
   Result := @Self;
end;
var
   l: LongInt;
procedure TestProc(aValue: LongInt);
begin
   Writeln(hexstr(aValue.GetSelfAddress));
   Writeln(hexstr(l.GetSelfAddress));
end;
begin
   l := 42;
   Writeln(hexstr(l.GetSelfAddress));
   TestProc(l);
end.

=== code end ===

=== output begin ===

0040B000
0140FE4C
0040B000

=== output end ===

There is no other language as FreePascal and it would be wrong to introduce something stupid to such an important system functions. If my thinking is wrong, please, any hint of an alternative. Without it, I'm completely stuck.

Regards,
Sven

In our previous episode, Sven Barth said:

While playing a bit with this code using some minor stuff I have on top of delphi containers, I noticed something small:

TList<T> obscures TList if generics.collections is imported after classes. It doesn't in Delphi. I used tthreadlist in generics.collections using code, and needed to declare a local (normal) tlist for it.

The code itself didn't compile because of a lot of not really clear "gendef" errors.

Yes, cross unit "type overloading" is still a problem in FPC. I've done some preparations to solve this (the compiler now keeps track whether a symtable contains a generic), but I've yet to implement the final lookup system for this.

The code itself didn't compile because of a lot of not really clear "gendef" errors.

I already have fixed the gendef problems you reported locally, but I need to find the time to write a nice commit message, because I've changed the complete implementation of constraints.

Regards,
Sven