Hello,

Say I want to implement a kind of linked list which node data may be anything. Thus I cannot store data on place (in nodes), indeed; so it should be referenced. But pointers themselves are supposed to be typed. So, how can I do that?

type list = ^node;
    node = record
        data : ???;
        next : list;
    end;

I tried to use Pointer, but then I get an error saying the compiler found <some type> while it expected "untyped". What is the use of Pointer (without type for pointed data)? I also had a look at Variant; this looks like an ugly hack ;-) And avyway is not really generic. I need data to ba able to be anything, including first a linked list itself... Finaly, when trying to write the the algo for a given type, I get an issue since the def above is recursive, recursively pointing in fact. So, I need to stop the run somewhere by allocating the memory for non-yet-existing data pointed by a pointer -- I guess.

    p^ := <I'll tell you soon, just book the place>

(The compiler warns about not initialised pointers.)

Pointers (sic!) to implementations of similar things (including trees) welcome... More generally, I cannot find in the library units for common data structures (sequence, associative table, set (the collection)...).

Denis
________________________________

vit esse estrany ☣

spir.wikidot.com

Try the following:

type list = ^node;
   node = record
       data : Variant;
       next : list;
   end;

Variant can store a lot pf data types, however please note that it's very slow type.
You also must remember that Pascal is Strong typed, unlike C or duck type languages.

The Pointer type store only memory address and not the data itself, so it's not recommended to use it unless you control the memory allocation itself for each 'data'.

Ido

http://ik.homelinux.org/

2010/4/23 spir ☣

1° Using the root class TObject might be a good alternative? Storing any object within the structure is easy.
Getting the object back will need a type overwrite.

2° Concerning standard structures, you might want to look at TList, TObjectList, TInterfacedList, TComponentList, TStringList which provide a lot. TStringList is very easy to use as a hash list in fact.

3° There are additional structured types in the FCL

4° You might want to read "Tomes of Delphi: Algorithms and data structures". See this link:
http://www.amazon.com/Tomes-Delphi-Algorithms-Data-Structures/dp/1556227361 The source code attached is interesting.

5° You might want to investigate the generics in FPC, since thyey're very useful to build typed containers.

5° Stay away from untyped types, they're (mostly) dangerous. Basically, it means your requirements or design has not been sufficiently investigated. Using precise types in Pascal is, in fact, a huge advantage. You will have been warned.

Hope this helps,
Thierry
Selon ik :

spir ☣ wrote

Say I want to implement a kind of linked list which node data may be anything. Thus I cannot store data on place (in nodes), indeed; so it should be referenced. But pointers themselves are supposed to be typed. So, how can I do that?

The key to solving this problem is to answer the question "How will I know what type of data that pointer points to?" Once you determine what is being pointed to you can cast Pointer^ to that type and all should work.

I would use Pointer as an untyped pointer to anything and ignore the warning. Perhaps you can turn off that warning for this code segment since you are doing this intentionally.

Thank you for both answers.
Are there kinds of untyped data structures in the library (such as sequence/list, table/mapping/hash/dictionary). I'd like to see how they're implemented. As a detail, my need is not necessarily the collection to be untyped, but the type to be known and/or , it is closer to what is sometimes called "generics". I want to implement the container algorithms once only, since they don't depend on the type of the content. Then I may specialise eg a Sequence type into one for strings to add a join method.

Denis
________________________________

vit esse estrany ☣

spir.wikidot.com

using a cast on a pointer^ means using the pointer^ as an untyped pointer to anything but turning off the warning, with the laser-like precision of just turning it off for that assignment (or comparison or whatever it is you're doing).

But this does depend on the user of the linked list knowing what the data type is.

Denis - Would it be at all possible for the objects that you are storing all to be derived from a single object type, such as tObject? That would let you use the "is" operator, and also to use collections http://freepascal.org/docs-html/rtl/objects/tcollection.html

I think what you are looking for may be possible only with classes, unless you roll your own by storing the type of what the pointer points to, as an enumerated type value in the record beside the pointer.

If you use classes, maybe something like the class reference type on p67 of ftp://ftp.freepascal.org/pub/fpc/docs-pdf/ref.pdf
might be useful.

FP