D library projects

[Andrei Alexandrescu]

dsimcha wrote:
> == Quote from Bill Baxter (wbaxter at gmail.com)'s article
>> On Sat, Nov 14, 2009 at 10:58 AM, div0 <div0 at users.sourceforge.net> wrote:
>>> What phobos is really lacking is a bunch of container classes, ala stl.
>>> I've been pondering swiping/porting the container classes from stlport.
>>> License looks like the port could be re-licensed as boost.
>>>
>>> good idea/bad idea?
>> STL implementation code is horrifically unreadable.  But potentially
>> worse is that the design is, I suspect, thoroughly entrenched in
>> assumptions based on the limitations of C++ templates (contributing to
>> that unreadablility).  And they're designed around iterators rather
>> than ranges, which will surely make for some significant differences.
>> I sure wouldn't try to port STLport or any other flavor of STL to D.
>> I kinda think the best way to write a container lib for D would just
>> be to go back to square one: pseudocode in CLR and other algorithms
>> books.  Certainly not the quickest way, though.
>> Anyway I thought Steve S. or Dimscha or someone said they were writing
>> a D2 container lib already. No?
>> --bb
> 
> Someone (I think it's Steve) has his dcollections lib.

I think http://www.gobosoft.com/eiffel/gobo/structure/ with some ideas 
from dcollections would be great. I don't think Java's collections form 
a good design for D.

> Tango has a bunch of
> collections.

Are those following Java's collection design?

> I think what we really need is to define what paradigm we're using for
> collections.  Here are some questions that really need to be answered before we
> can start implementing a std.collections:
> 
> 1.  How do we prioritize the following when tradeoffs have to be made:
> 
>     a.  Safety
>     b.  Flexibility
>     c.  Performance
>     d.  Simplicity/Ease of use
> 
> STL, for example, primarily focuses on performance and flexibility at the expense
> of simplicity and safety.  We might not want that tradeoff.

I think policies should decide here. Let the user make the choice and 
offer a good set of defaults.

> 2.  Should we use an OO flavor w/ classes and explicit Interface interfaces or a
> more template-y flavor with structs and compile-time interfaces?

I'd be leaning more towards classes, but I'm still waiting for a killer 
argument one way or another.

> 3.  Reference or value semantics?

I'm again leaning towards reference semantics.

> 4.  What primitives must a collection have by definition?

This is a long discussion. I've exposed briefly a couple of opinions in 
the past, for example I think Container!T should expose:

bool empty();
bool add(T);
T popAny();
OnePassIterator!T opSlice();

Perhaps OnePassIterator could be ForwardIterator, but I'm not positive.

Better container reflect more detailed primitives.

Please advise.

> 5.  To what extent should collections be designed with the limitations of the
> current GC in mind?

I don't know. Probably some tradeoffs may be necessary, but I hope not.

> 6.  Should we allow custom allocators?  I would actually say no, because based on
> my experience with my TempAlloc collections, if you're using a custom allocator,
> you probably want to design the implementation with the details of that allocator
> in mind.  Furthermore, it may be hard to make things safe without knowing
> something about how the memory allocator works.

Good question. Would love to, but I don't know how to design a good 
solution.


Andrei