D library projects

[dsimcha]

== 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.  Tango has a bunch of
collections.  I've written a few collections that are specifically designed for,
and somewhat coupled to my TempAlloc allocator.  (hash sets, hash tables are
there, AVL trees are almost ready)  These will be Boost licensed and could easily
be adapted to "normal" GC memory management once we figure out what the API should
be.  I've also written an associative array implementation that's specifically
designed with the current GC implementation in mind (RandAA).

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.

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?

3.  Reference or value semantics?

4.  What primitives must a collection have by definition?

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

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.

For example, my TempAlloc data structures place deleted nodes on free lists local
to the collection, because you can only delete stuff from TempAlloc in LIFO order,
so this is the only way the memory could get recycled.  They are also not designed
with even the slightest consideration for sharing across threads because
TempAlloc-allocated memory isn't supposed to be shared across threads.  Finally,
since TempAlloc itself is inherently a performance hack, they place a premium on
performance at the expense of safety and flexibility.