Red black trees are one of those basic collection types that should be available. Anyone want to write one for D for placement into Phobos?

Walter Bright wrote:
> Red black trees are one of those basic collection types that should be available. Anyone want to write one for D for placement into Phobos?

Did anyone else read this and go "WTH"? Wouldn't it be better to actually bless a community based standard library effort, than take submissions piecemeal whenever you feel like it? Sure red black trees are a basic collection that most people will need at some point, but why  isn't it being made part of a larger templated collections portion of the library?

I know for a fact that there is a group of people who would gladly take up the standard library torch and run with it, people who would be accountable to you and the community, with open source, documentation, and a roadmap for development.

Its this kind of lack of vision which I think will retard D's evolution into a production language, so that it forever remains at the level of hobbyist hackery.

Kyle Furlong wrote:
> Walter Bright wrote:
>> Red black trees are one of those basic collection types that should be available. Anyone want to write one for D for placement into Phobos?
> 
> Did anyone else read this and go "WTH"? Wouldn't it be better to actually bless a community based standard library effort, than take submissions piecemeal whenever you feel like it? Sure red black trees are a basic collection that most people will need at some point, but why  isn't it being made part of a larger templated collections portion of the library?
> 
> I know for a fact that there is a group of people who would gladly take up the standard library torch and run with it, people who would be accountable to you and the community, with open source, documentation, and a roadmap for development.
> 
> Its this kind of lack of vision which I think will retard D's evolution into a production language, so that it forever remains at the level of hobbyist hackery.

I would welcome it if you (or anyone else) makes a proposal for a set of to-be-implemented collection classes.

> Did anyone else read this and go "WTH"?

No, I though: "yes, excellent." Motivating some ppl to contribute, is surely not a wrong thing.

Frank Benoit (keinfarbton) wrote:
>> Did anyone else read this and go "WTH"? 
> 
> No, I though: "yes, excellent." Motivating some ppl to contribute, is
> surely not a wrong thing.

Maybe I did come across as a little harsh, I do believe that in absence of a community driven, roadmap based development effort, this is better than a closed, Walter-written std lib.

Walter Bright wrote:
> Kyle Furlong wrote:
>> Walter Bright wrote:
>>> Red black trees are one of those basic collection types that should be available. Anyone want to write one for D for placement into Phobos?
>>
>> Did anyone else read this and go "WTH"? Wouldn't it be better to actually bless a community based standard library effort, than take submissions piecemeal whenever you feel like it? Sure red black trees are a basic collection that most people will need at some point, but why  isn't it being made part of a larger templated collections portion of the library?
>>
>> I know for a fact that there is a group of people who would gladly take up the standard library torch and run with it, people who would be accountable to you and the community, with open source, documentation, and a roadmap for development.
>>
>> Its this kind of lack of vision which I think will retard D's evolution into a production language, so that it forever remains at the level of hobbyist hackery.
> 
> I would welcome it if you (or anyone else) makes a proposal for a set of to-be-implemented collection classes.

I don't have the expertise to design them but Doug Lea does:

http://g.oswego.edu/dl/classes/collections/

Perhaps his collection design could form the basis for a D collections library, templated of course.

Walter Bright wrote:

> Kyle Furlong wrote:
>> Walter Bright wrote:
>>> Red black trees are one of those basic collection types that should be available. Anyone want to write one for D for placement into Phobos?
>> 
>> Did anyone else read this and go "WTH"? Wouldn't it be better to
>> actually bless a community based standard library effort, than take
>> submissions piecemeal whenever you feel like it? Sure red black trees
>> are a basic collection that most people will need at some point, but why
>>  isn't it being made part of a larger templated collections portion of
>> the library?
>> 
>> I know for a fact that there is a group of people who would gladly take up the standard library torch and run with it, people who would be accountable to you and the community, with open source, documentation, and a roadmap for development.
>> 
>> Its this kind of lack of vision which I think will retard D's evolution into a production language, so that it forever remains at the level of hobbyist hackery.
> 
> I would welcome it if you (or anyone else) makes a proposal for a set of to-be-implemented collection classes.

Walter, please take a look at mango.containers in Mango's SVN: http://dsource.org/projects/mango/browser/trunk/mango/containers

It's meant to be a standard containers library similar to the Java collections, but in more of a D style.  It uses mango.locks to implement some thread-safe containers, so it's integrated into mango, but I feel it will be appropriate as a generic library.  It's not done yet, however. There are still signifigant efforts yet to go in documentation, container implementations, and algorithms (I've only got array quicksort and reverse).

There's some demo code I use for unittesting at: http://dsource.org/projects/mango/browser/trunk/mango/test/containers.d

I'd also like to mention (as long as I have your ear...err.. eyes) that most of Mango would do well in the standard library, and I think you should consider releasing Mango along with the compiler, as it is a very well put-together and cohesive library.  It's got very efficient class-based IO support with integrated encoding conversion, a SAX parser (beta- my work), soon to have a decent DOM parser (my work- built on top of  SAX parser), a logging framework, semaphore classes, http client, and other things.  I would love to see large portions of Mango replace large parts of Phobos, and the rest of it to become the javax of Phobos (and optional, extended part of the standard library) since not everyone needs an http server or servlet support.  I think we need to include a standard library such as Mango in order to attract modern users used to the likes of Java and C# libraries.  <End Mango plug>

Thoughts?

-- 
~John Demme
me@teqdruid.com
http://www.teqdruid.com/

John Demme wrote:
> Thoughts?

Mango is obviously a well thought out and excellent library. If you and Kris are game, I am.

Walter Bright wrote:
> John Demme wrote:
>> Thoughts?
> 
> Mango is obviously a well thought out and excellent library. If you and Kris are game, I am.

The plot thickens.

Walter Bright wrote:
> Red black trees are one of those basic collection types that should be available. Anyone want to write one for D for placement into Phobos?

I've been trying to write one based off of a C++ version over the the code project (actual link is in the code file).

http://www.dsource.org/projects/arcgames/browser/trunk/physics/d/binarytree.d

However, after I add the third node, I get an access violation. I haven't had much time to really sit down and debug it, all I know is that somehow I am trying to access a null object which causes an access violation. Eventually I'll get it to work, just a matter of time.

---

I also have a doubly linked list with a mergesort (I wrote the list but I did not write the merge sort implemtation, again the link where I got it from is in there). It seems to work well
http://dsource.org/projects/freeuniverse/browser/trunk/freeuniverse/arc/templates/dlinkedlist.d

Then again, I'm sure the it would need some fixing up and heavy testing, plus making sure that the places I got some of the code from would allow it to be licensed under public domain before even thinking about putting it in a std lib. Just thought I'd mention them in case anyone finds it useful.

~ Clay S.