I remember seeing discussion about fcl-stl saying that it would still need improvement but nobody is actively working on it. I just couldn't find the thread about it now. So, what is the current state? Sorry I have not studied the lib myself yet (long ToDo list).

For example, if someone is developing a competing generics library, could he be advised to improve fcl-stl instead? Would patches be accepted?

This is based on a forum discussion:
http://www.lazarus.freepascal.org/index.php/topic,19496.msg111098/topicseen.html

Regards,
Juha

Juha Manninen wrote

I remember seeing discussion about fcl-stl saying that it would still need improvement but nobody is actively working on it. I just couldn't find the thread about it now. So, what is the current state? Sorry I have not studied the lib myself yet (long ToDo list).

It should work. Somewhen after the discussion you mentioned I tested whether managed types (e.g. AnsiStrings) work correctly and so far I didn't find any problems, so the problems I mentioned in that thread aren't existing (anymore). At least as far as I've tested.

For example, if someone is developing a competing generics library, could he be advised to improve fcl-stl instead? Would patches be accepted?

Patches are definitely welcome for that library. :)

Regards,
Sven

Juha Manninen wrote

For example, if someone is developing a competing generics library, could he be advised to improve fcl-stl instead? Would patches be accepted?

Hi there.

I have been working on a few generic types here:

https://github.com/tangentstorm/xpl/blob/master/code/ll.pas { linked list / ring with generic cursor type + for/in support }

https://github.com/tangentstorm/xpl/blob/master/code/stacks.pas { simple stack<t> with some forth-like methods }

https://github.com/tangentstorm/xpl/blob/master/code/di.pas { very simple dictionary type (string keys only at the moment) }

You probably wouldn't want my code as-is because I don't use the Delphi conventions, but I might be able to run it through a filter to adapt it.

I had been thinking about considered refactoring the fundamentals library to use generics too at some point:

http://fundementals.sourceforge.net/index.htm

I actually didn't know about fcl-stl . I'm willing to work on it, and to contribute my code, but the license is a problem for me. If the original authors were willing to dual-license under MIT and LGPL+SLE I'd be happy to do the same, and to generate
a version that followed the Borland coding conventions.

( Not sure what that would mean for the fundamentals idea, but perhaps it wouldn't be necessary anymore. )

( tangentstorm on #fpc )

Juha Manninen wrote

I remember seeing discussion about fcl-stl saying that it would still need improvement but nobody is actively working on it. I just couldn't find the thread about it now. So, what is the current state? Sorry I have not studied the lib myself yet (long ToDo list).

Current state is working, but we have no usage numbers (in fact, we don't have this for anything)

For example, if someone is developing a competing generics library, could he be advised to improve fcl-stl instead? Would patches be accepted?

Definitely.

The more and better patches it gets, the better it is.

Michael.

Juha Manninen wrote

For example, if someone is developing a competing generics library, could he be advised to improve fcl-stl instead?

Definitively.

Would patches be accepted?

Yes.

2013/1/11 Juha Manninen

Oh, generics again!

Shameless plug: http://code.google.com/p/fprb/wiki/heContnrs ;-)

Jan
(gmp package author)

No one seems to see: http://bugs.freepascal.org/view.php?id=23654 :(

leledumbo wrote

No one seems to see: http://bugs.freepascal.org/view.php?id=23654 :(

Well, it's a new feature: just slapping another piece of code into fpc-stl not improving existing stuff.

leledumbo wrote

No one seems to see: http://bugs.freepascal.org/view.php?id=23654 :(

As I have explained several times on the mailing lists, the core team does not really use generics. That means that issues/bugs with generics are given less attention than other bugs. Not because we do not care, but simply because no-one feels confident enough
(or so I suspect, I know I don't).

I have added the tree implementation:
I have just checked compilation, and added a copyright header.

Many thanks for this contribution !

If someone feels like maintaining the fcl-stl and caring about bugs in it, feel free to volunteer. I will give you appropriate rights to deal with it.

Michael.

No, but adding things from time to time shows it is not dead code :-)

Michael.

Indeed, but the additions should follow a common goal and as far as I understood, fcl-stl shall provide opaque containers which is not the case for a tree implementation.

? Why not ? I see no difference with a list or collection ?

Michael.

In our previous episode, Michael Van Canneyt said:

I didn't get the problem either.

I do see another redudancy. gset already has a red-black implementation. (even if it is called a set)

I do see another redudancy. gset already has a red-black implementation.

(even if it is called a set)

Problem: The tree is invisible, it can't be used as a generic red-black tree

A tree is something implementation specific while the fpc-stl is only about opaque data structures. E.g. the fpc-stl supports TSet: but the whole implementation is hidden. The user does not/need not to know how the set works internally. It could be a linked list, a tree, whatever.

Indeed, but the additions should follow a common goal and as far as I

understood, fcl-stl shall provide opaque containers which is not the case for a tree implementation.

I thought a better goal would be to have arbitrary data structures that's commonly used with generic content, and tree is often a missing pearl from other stl-like packages (original C++ STL, Java CF, etc.). File system hierarchy, state space searching, ast, etc. all of them uses tree. In fact, IMHO AVLTree should also be included in fcl-stl, since the current content data type is pointer, which is NOT typesafe, and it's better to replace it with a generic data type placeholder.

Furthermore, stl shouldn't be limited to containers. C++ STL has <algorithm> doesn't it?

For me, a tree is a data structure, just like a set, list, collection, queue, whatever.

Generics for me are just a way to say 'we don't know the actual data type yet' for a particular data structure, and then later create the data structure with a specific type.

So, in my head, it's perfectly OK to have a tree in fcl-stl.

But like I said in earlier posts: I have no affinity whatsoever with generics, so I'm not very well placed to make judgments.

Well, all the more reason for someone to actually take control of fcl-stl :-)

Michael.

A tree is an implementation detail. For example a set could be implemented using a tree.

Thanks, Michael. I haven't put the documentation though and I guess since there are a lot of algorithms running on k-ary tree I'll add more...

Where does the C++ STL expose a tree? It might be used internally by a map or set but I'am not aware of any tree class in the C++ STL.

Java CF, etc.). File system hierarchy, state space searching, ast, etc. all of them uses tree.

Internally, yes.

Yes. But since we miss subroutine templates/generics this will be hard to achieve.

Yes, STL is about usage patterns (like any good container library) but not about implementation.

Where does the C++ STL expose a tree? It might be used internally by a

map or set but I'am not aware of any tree class in the C++ STL.

No, no, I was saying this data structure is even missing from C++ stl. In the end, we often need to write again and again that depth first, breadth first, iterative deepening, and many other algorithms working on tree that works exactly the same in any context. Even the tree itself as a container without any traversal algorithm is quite helpful.

leledumbo wrote

> Where does the C++ STL expose a tree? It might be used internally by a map or set but I'am not aware of any tree class in the C++ STL. No, no, I was saying this data structure is even missing from C++ stl.

For good reasons. As said before a tree is an implementation detail. When having a fully implemented C++ STL one really seldomly needs an explicit tree implementation. Of course, there are special cases which are speed/memory sensitive which require to implement explicitly a tree but in this case a generic tree is probably also the wrong choice because it does not allow the hand crafted optimizations needed in such cases.

I understand you the first time :-)

For me, a tree is at the same level as a set. Whatever models your data best.

That you can implement a data structure internally using a tree (or vice versa) is for me not a criterium. You could probably implement a tree using vector. or stacks, queues or whatnot (maybe not very efficient, but that is not the point). Or you could implement a set using a vector or vice versa.

From that perspective, the vector is an implementation detail of the tree.

Yet vector is part of fcl-stl... So I see no difference whatsoever.

Anyway, I didn't mean to argue. I'm just saying:
If someone wants to take control of fcl-stl: please do so.

Michael.

For good reasons. As said before a tree is an implementation detail.

When having a fully implemented C++ STL one really seldomly needs an explicit tree implementation. Of course, there are special cases which are speed/memory sensitive which require to implement explicitly a tree but in this case a generic tree is probably also the wrong choice because it does not allow the hand crafted optimizations needed in such cases.

This is what I see from the POV of C++ STL designer, while I take Boost POV. I agree with Michael, and I implement this to leverage tree as more than just backend of some container (e.g. set and map) to stand as a container on its own. Isn't it a good idea to have a tree that can act as both backend and be used standalone? From tree, graph can also be built (but I'd rather separate the implementation to have tree optimized version of the traversal algorithm, no need to check for "mark as visited").

A set is defined by some properties and possible operations like that it can contain each element only once, that it is possible to build intersections, unions etc.

Then it should go in a separate package like fcl-trees. At least I don't consider a tree as something fitting in fcl-stl being a generic library in the strict sense, see also
http://en.wikipedia.org/wiki/Generic_programming#Stepanov-Musser_and_other_generic_programming_paradigms

Aha... That's a mathematical definition.

So: A graph is also mathematically defined. And a tree is just a specialized graph.

Stalemate :-)

Michael.

Hmm... I guess fcl-stl has to be renamed to fcl-gcl (generic container library) and we could have another fcl-gdsl (generic data structure library) for different purposes because the name standard template library used as container only library sounds inefficient.

It is a definition, yes.

So: A graph is also mathematically defined. And a tree is just a specialized graph.

So a number is also at the same level? It is also mathematically defined :) So even ansi pascal has generics, it has numbers: integers and reals :)

Stalemate :-)

Exactly :-)

Like I said, I didn't mean to argue.

For me there is no difference, but then I have no affinity with Generics.

Just to say that I am not suitable to maintain fcl-stl. But someone should definitely take care of it.

Michael.

Like I said, I didn't mean to argue. For me there is no difference, but then I have no affinity with Generics.

See the link in my other mail ;)

Just to say that I am not suitable to maintain fcl-stl. But someone should definitely take care of it.

Yes, but keeping in mind how to create a good generics library.

So: A graph is also mathematically defined. And a tree is just a

specialized graph.

Indeed :)

I just realized that if you add an already existing node to other part of my tree such that it create a circular path, you have a graph, and both traversal algorithm will end up in infinite loop! (well, depending on the path, it might end up in out of memory first :p)

So let's settle it up, there are tons of ready data structures and algorithm out there, including some in my code repository, both generics and data type specific, that will be useful to have in FPC. We already have scattered data structures and algorithm for the sake of Delphi compatibility (Classes.TList, Contnrs.TObjectList, etc.) so we shouldn't scratter more. I thought fcl-stl was a good place for this, but seeing that it's a container only package, things seem need to be reorganized. I'd be happy to donate when things get clearer.

In our previous episode, Florian Kl?mpfl said:

I learned my containers with Java, rather than STL. But your argumentation sounds more like the fixation of interfaces rather than real classes (which always have an implementation, and thus have properties like O(log n) ness, in order walking etc, something that e.g. the principal pattern SET doesn't convey).