D library projects

[dsimcha]

== Quote from Steven Schveighoffer (schveiguy at yahoo.com)'s article
> On Sat, 14 Nov 2009 22:08:23 -0500, Andrei Alexandrescu
> <SeeWebsiteForEmail at erdani.org> wrote:
> > dsimcha wrote:
> >> Tango has a bunch of
> >> collections.
> >
> > Are those following Java's collection design?
> The original collections in Tango were ported from Doug Lea's original
> code, not the Java design (which was also based on Doug Lea's design).
> The newer ones are rewritten from scratch, but in the same feel.
> dcollections have some Java feel in that they are classes and interfaces,
> but also add C++ style iterators (cursors).
> >> 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.
> I agree -- it should be possible with the metaprogramming power of D to
> allow for the user to choose his weapon -- power and speed vs. safe.  I
> think simplicity is a given.
> For example, it could be a version statement that decides whether ranges
> of a container do runtime checks for safety.
> >> 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.
> I think shoehorning containers that are graph based into value types might
> be a little strenuous.  All the builtin D container types are essentially
> reference types (arrays are not exactly reference types but behave mostly
> like reference types), I don't see why we should change that.
> Making them classes allows for interfaces which helps allow runtime
> decisions for things like copying data between containers that are of
> different types.  See dcollections and how easy it is to copy data from
> one type to another.
> > 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.
> In dcollections, the custom allocator is a template argument for the
> collection class.
> Using a custom allocator has brought tremendous speedups, because you go
> through fewer collection cycles, and waste much less space.
> I think it's possible to design a custom allocator framework that is
> hidden completely from the API.  dcollections has 2 different allocators
> -- the default is a custom allocator I wrote to cut down on the GC
> collection cycles (which I also contributed to Tango and is now their
> default allocator), and the alternative is an allocator which simply uses
> the GC to allocate all nodes with 'new'.  The code to use such containers
> does not change if you change the allocator.
> Tango does have an allocator that ONLY works for pure value types (types
> that have no pointers in them), and it is even faster than my custom
> allocator, but it requires you "know what you are doing."  I think with
> the power of D2 we should be able to come up with some template magic that
> disallows such an allocator from being used with the wrong types.
> -Steve

After looking at dcollections some more, it looks very well thought out and IMHO
is a good starting point for a std.collections, provided a few issues are taken
care of:

1.  License needs to be Boost, not BSD.  You'd need to relicense it under Boost.

2.  Needs to be D2-ified, which you mentioned a few posts back that you were going
to do anyhow.

3.  I don't know how your cursor concept would interact with ranges.  You've
mentioned that cursors have some capabilities that ranges don't, but they are also
more awkward to use.  For a std.collections, I think being range-based is a must.

Also, have you considered contributing the Hash class to the AA project on dsource
and nominating it to replace the current AA implementation?