[fpc-devel] Generic Programming Units

[Dean Zobec]

John Briggs wrote:

>This is a repost of an earlier response to another thread. I did not recieve
>any response so I am posting this in its own thread.
>
>I have several old books (circa 1991), including source code, covering TP6 in 
>my library.
>  
>
I still remember the Algorithms + Data Structures = Programming book
from Niklaus Wirth back in 1976, it was a masterpiece. I'll try to find
it in a library to reread it :-)

>Perhaps the most interesting one covers generic programming. It covers 
>modelling generic data stuctures including:
>	Generic Stacks
>	Generic Queques
>	Generic Arrays
>	Generic Virtual Arrays
>	Generic Matrices
>	Generic Jagged Matrices
>	Generic Internal Hash Tables
>	Generic Singly Linked Lists
>	Generic Doubly Linked Lists
>	Generic AVL Trees
>	Generic Graphs
>
>If any of these are of interest, please respond because I will have to rework 
>the code for it to compile cleanly using FPC.
>
>Regards
>
>John
>  
>
As you've probably heard from Florian, FPC needs a good containers
library. I've started looking at Decal this week, the code has been
ported to fpc by Marco Van de Voort and now compiles with FPC. It's
based on the TVarRec and open array construction (array of const) to be
able to add to the containers even the base types as integers, floats,
chars, etc.
The generic functions are very powerful and model closely the C++ STL
library (as fpc does not have generics yet a sort of typecast is still
required when fetching the items from the container). The library was
not designed for speed though, from the first test the DArray class is
twice as slow then the TFPList for example).  Anyway, I think it's a
good start, since as I've seen from the wiki, we'll not have generics in
fpc available soon (I would be glad to contribute to the generics
implementation, but this but is still beyond my current poor fpc
knowledge :( ) . When our compiler will support generics, if Decal will
be fully covered by unit tests I think it will be easier to convert to it.

The code is available in the old fpc cvs under the directory
projects/contrib/decal. I've began to clean the unit to make it more
readable, moving the comments in a fpdoc xml file and restoring a proper
indentation.
Then I'm planning to pin down the code with unit tests with FPCUnit to
begin a refactoring in case there are potential speed improvements and
to remove possible bugs (I've seen a lot of strange comments in the code
that does not smell very good). The unit is quite big, more or less
9.000 lines of code, and quite complicated, so I'll surely need help.
In any case I'm very interested on the subject of container classes so
I'm glad to discuss it with other people interested in it.

As the project looks like a long term one and I think that fpc urgently
needs a optimized hash table  I'll also work on a streamlined hash table
with a chaining technique as a collision resolution scheme and a paging
for the allocation of the nodes in the chains, to have an associative
container that would easily beat the TStringList in search speed when
the number of items added is more than 100.000 (the IndexOf() function
in an unordered TStringList does a linear search).

I would be glad to receive  opinions on the container classes
implementation in FPC and of course we'll surely need help (I'm not
working as a professional programmer, I even do not work in the IT
field, so my programming work as an hobby is limited to the evenings),
so feel free to get in contact with me even in private if you prefer.

Ciao,
Dean