After much work and toil, I have created dcollections for D2.  I think I can say that this is the first collection package available for D2.  I still hold hope that it will be used as the standard collection package for phobos for D2.

Please visit http://www.dsource.org/projects/dcollections for details.

Some VERY IMPORTANT notes for this release:

1. it is very beta software.  Although the implementation has changed very little from the 1.0 version, not everything will properly compile.  I have filed several compiler bugs to fix some problems I had while porting, and inserted workarounds for things I could work around.  Please use the LATEST compiler (currently 2.046) because some very important features have been added that dcollections relies on.  Although it is beta, the algorithms and implementation is largely unchanged so functionality should be pretty solid.

2. the docs are not online for d2.  Unfortunately, dsource's auto-doc-generator that I was using for the 1.0 version is based on a 1.0 compiler, so it will not automatically generate the d2 docs.  However, I have included some basic ddoc generated docs in the download package, don't expect them to be very fun to use :)

3. The docs are not fully updated, so they might be just flat out wrong!  I plan to update the docs completely for the next beta release.

So, for the good stuff... here are some notes for differences between 1.0 and 2.0:

    * Ranges!
    * Filled out slicing for all containers
    * Cursors are now non-movable.  Use ranges for safe iteration.
    * The interfaces have been cut down significantly. The question I asked myself when deciding whether I wanted to keep an interface is "would anyone use this interface?"
    * Functions that should be fast but can be slow (O(n)) have been removed from all interfaces, and in most cases, from the containers. Notably missing is searching a non-quick lookup container for a value. Use std.algorithm.find for that.
    * ArrayMultiset has been removed -- it's complexity functions did not fit with the multiset requirements (specifically, quick lookup of an element's presence).
    * ArrayList slicing now simply returns a range instead of a "live" slice.  Note that an ArrayList range is aliased to a D array.
    * Full unit tests added for all container types.

I have also changed the license from BSD to Boost.


--------

I have also formally released version 0.03 as version 1.0, nothing has changed there, including the license.  However, no new features will be added to dcollections version 1.0, only bug fixes will be done.

Please, file tickets on dsource for any problems you have.  And let me know if there are any ideas you think would be useful.

-Steve

Thanks Steven. I was waiting for this for a long time.


On Wed, 19 May 2010 11:09:11 -0500, Steven Schveighoffer <schveiguy@yahoo.com> wrote:

> After much work and toil, I have created dcollections for D2.  I think I can say that this is the first collection package available for D2.  I still hold hope that it will be used as the standard collection package for phobos for D2.
>
> Please visit http://www.dsource.org/projects/dcollections for details.
>
> Some VERY IMPORTANT notes for this release:
>
> 1. it is very beta software.  Although the implementation has changed very little from the 1.0 version, not everything will properly compile.  I have filed several compiler bugs to fix some problems I had while porting, and inserted workarounds for things I could work around.  Please use the LATEST compiler (currently 2.046) because some very important features have been added that dcollections relies on.  Although it is beta, the algorithms and implementation is largely unchanged so functionality should be pretty solid.
>
> 2. the docs are not online for d2.  Unfortunately, dsource's auto-doc-generator that I was using for the 1.0 version is based on a 1.0 compiler, so it will not automatically generate the d2 docs.  However, I have included some basic ddoc generated docs in the download package, don't expect them to be very fun to use :)
>
> 3. The docs are not fully updated, so they might be just flat out wrong!  I plan to update the docs completely for the next beta release.
>
> So, for the good stuff... here are some notes for differences between 1.0 and 2.0:
>
>      * Ranges!
>      * Filled out slicing for all containers
>      * Cursors are now non-movable.  Use ranges for safe iteration.
>      * The interfaces have been cut down significantly. The question I asked myself when deciding whether I wanted to keep an interface is "would anyone use this interface?"
>      * Functions that should be fast but can be slow (O(n)) have been removed from all interfaces, and in most cases, from the containers. Notably missing is searching a non-quick lookup container for a value. Use std.algorithm.find for that.
>      * ArrayMultiset has been removed -- it's complexity functions did not fit with the multiset requirements (specifically, quick lookup of an element's presence).
>      * ArrayList slicing now simply returns a range instead of a "live" slice.  Note that an ArrayList range is aliased to a D array.
>      * Full unit tests added for all container types.
>
> I have also changed the license from BSD to Boost.
>
>
> --------
>
> I have also formally released version 0.03 as version 1.0, nothing has changed there, including the license.  However, no new features will be added to dcollections version 1.0, only bug fixes will be done.
>
> Please, file tickets on dsource for any problems you have.  And let me know if there are any ideas you think would be useful.
>
> -Steve


-- 
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/

Are the collections supposed to not have isEmpty members?

Looking forward to using dcollections, and here's to hoping they make it into phobos.

OTish: What are your thoughts on a bimap implementation and a child/sibling or general tree implementation as part of dcollections?

Sheer awesomeness!  I've been waiting for along time for a decent collections lib for D2.  I haven't tested it extensively, but it definitely builds w/o a hitch (using a custom build script I wrote that builds dcollections and other libs I use in one go) and works for the toy examples I tested.

One small comment, though:  Looking at your ArrayList code, wouldn't it make more sense to use a capacity field here than to use the builtin array appending mechanism, given that this is a class, not a struct?

Ellery Newcomer Wrote:

> Are the collections supposed to not have isEmpty members?

No.  Use length == 0.  O(1) length is always supported for all collections.

> OTish: What are your thoughts on a bimap implementation and a child/sibling or general tree implementation as part of dcollections?

I haven't the slightest what a bimap is :)  I am not an expert in collections or data structures, I just reimplement things I have understood.  My implementations are basically copied from my algorithm book, and refined as much as I can do.

That being said, if you have any implementation of a tree or hash, it should be easy to insert into dcollections.  If you have ideas for other collection types (i.e. other than Map, Set, Multiset or List), then I can look into that if you point me at an implementation or have one of your own.  I purposefully left out multi-map because I've never had a huge use for it, and it seemed like a awkward thing to create an interface for...

-Steve

dsimcha Wrote:

> One small comment, though:  Looking at your ArrayList code, wouldn't it make more sense to use a capacity field here than to use the builtin array appending mechanism, given that this is a class, not a struct?

Yes, that is part of my semi-documented long term plan.  I actually am planning on adding an "extendLength" runtime function to support extending the length of an array as much as possible without reallocating.  That way I can make ArrayList independent of the allocation sizes that the GC supports.

-Steve

Hi Steven,

On Wed, 19 May 2010 12:09:11 -0400, Steven Schveighoffer wrote:

> After much work and toil, I have created dcollections for D2.  I think I can say that this is the first collection package available for D2.  I still hold hope that it will be used as the standard collection package for phobos for D2.

Cool!

In case anyone's interested, I tried out dcollections using my very alpha 'd-build' script, and it works just fine:

http://github.com/gmfawcett/d-build/tree/dcollections-test

tarball of the dcollections test branch: http://github.com/gmfawcett/d-build/tarball/dcollections-test

Checking out the 'dcollections-test' branch of that git project, you should be able to just run './d-build test.d' and it will first download dcollections and then compile it along with the test program. There are several limitations; see the README for details.

There's a long way to go before d-build is more than a toy. But I'd like to keep it on people's radars, and am interested in your thoughts and feedback. See the "envy for go packages" threads on this list for context.

Regards,
Graham


> 
> Please visit http://www.dsource.org/projects/dcollections for details.
> 
> Some VERY IMPORTANT notes for this release:
> 
> 1. it is very beta software.  Although the implementation has changed very little from the 1.0 version, not everything will properly compile. I have filed several compiler bugs to fix some problems I had while porting, and inserted workarounds for things I could work around. Please use the LATEST compiler (currently 2.046) because some very important features have been added that dcollections relies on. Although it is beta, the algorithms and implementation is largely unchanged so functionality should be pretty solid.
> 
> 2. the docs are not online for d2.  Unfortunately, dsource's auto-doc-generator that I was using for the 1.0 version is based on a 1.0 compiler, so it will not automatically generate the d2 docs. However, I have included some basic ddoc generated docs in the download package, don't expect them to be very fun to use :)
> 
> 3. The docs are not fully updated, so they might be just flat out wrong! I plan to update the docs completely for the next beta release.
> 
> So, for the good stuff... here are some notes for differences between 1.0 and 2.0:
> 
>      * Ranges!
>      * Filled out slicing for all containers * Cursors are now
>      non-movable.  Use ranges for safe iteration. * The interfaces have
>      been cut down significantly. The question I
> asked myself when deciding whether I wanted to keep an interface is
> "would anyone use this interface?"
>      * Functions that should be fast but can be slow (O(n)) have been
> removed from all interfaces, and in most cases, from the containers.
> Notably missing is searching a non-quick lookup container for a value.
> Use std.algorithm.find for that.
>      * ArrayMultiset has been removed -- it's complexity functions did
>      not
> fit with the multiset requirements (specifically, quick lookup of an
> element's presence).
>      * ArrayList slicing now simply returns a range instead of a "live"
> slice.  Note that an ArrayList range is aliased to a D array.
>      * Full unit tests added for all container types.
> 
> I have also changed the license from BSD to Boost.
> 
> 
> --------
> 
> I have also formally released version 0.03 as version 1.0, nothing has changed there, including the license.  However, no new features will be added to dcollections version 1.0, only bug fixes will be done.
> 
> Please, file tickets on dsource for any problems you have.  And let me know if there are any ideas you think would be useful.
> 
> -Steve

On Wed, 19 May 2010 20:27:17 +0000, Graham Fawcett wrote:

> Hi Steven,
> 
> On Wed, 19 May 2010 12:09:11 -0400, Steven Schveighoffer wrote:
> 
>> After much work and toil, I have created dcollections for D2.  I think I can say that this is the first collection package available for D2. I still hold hope that it will be used as the standard collection package for phobos for D2.
> 
> Cool!
> 
> In case anyone's interested, I tried out dcollections using my very alpha 'd-build' script, and it works just fine:
> 
> http://github.com/gmfawcett/d-build/tree/dcollections-test
> 
> tarball of the dcollections test branch: http://github.com/gmfawcett/d-build/tarball/dcollections-test
> 
> Checking out the 'dcollections-test' branch of that git project, you should be able to just run './d-build test.d' and it will first download dcollections and then compile it along with the test program. There are several limitations; see the README for details.
> 
> There's a long way to go before d-build is more than a toy. But I'd like to keep it on people's radars, and am interested in your thoughts and feedback. See the "envy for go packages" threads on this list for context.

Apologies; the "envy for go packages" thread is on the D list, not on D.announce.

Graham

On 05/19/2010 03:07 PM, Steven Schveighoffer wrote:
> Ellery Newcomer Wrote:
>
>> Are the collections supposed to not have isEmpty members?
>
> No.  Use length == 0.  O(1) length is always supported for all collections.
>
>> OTish: What are your thoughts on a bimap implementation and a
>> child/sibling or general tree implementation as part of dcollections?
>
> I haven't the slightest what a bimap is :)  I am not an expert in collections or data structures, I just reimplement things I have understood.  My implementations are basically copied from my algorithm book, and refined as much as I can do.

I think boost.bimap is where I saw it, though I don't don't use c++.

I think it's a map, with values->keys is also a map

>
> That being said, if you have any implementation of a tree or hash, it should be easy to insert into dcollections.  If you have ideas for other collection types (i.e. other than Map, Set, Multiset or List), then I can look into that if you point me at an implementation or have one of your own.  I purposefully left out multi-map because I've never had a huge use for it, and it seemed like a awkward thing to create an interface for...
>
> -Steve

I have a simple child/sibling tree implementation which I could probably dust off and polish up if you want it. The method for visiting the elements is kind of weird, though. And I don't know that it exactly fits the mold of a reference container. Maybe with cursors.

Ugh, I just noticed LinkList doesn't work with interfaces.

Steven Schveighoffer Wrote:

> After much work and toil, I have created dcollections for D2.  I think I can say that this is the first collection package available for D2.  I still hold hope that it will be used as the standard collection package for phobos for D2.
> 
> Please visit http://www.dsource.org/projects/dcollections for details.
> 
> Some VERY IMPORTANT notes for this release:
> 
> 1. it is very beta software.  Although the implementation has changed very little from the 1.0 version, not everything will properly compile.  I have filed several compiler bugs to fix some problems I had while porting, and inserted workarounds for things I could work around.  Please use the LATEST compiler (currently 2.046) because some very important features have been added that dcollections relies on.  Although it is beta, the algorithms and implementation is largely unchanged so functionality should be pretty solid.
> 
> 2. the docs are not online for d2.  Unfortunately, dsource's auto-doc-generator that I was using for the 1.0 version is based on a 1.0 compiler, so it will not automatically generate the d2 docs.  However, I have included some basic ddoc generated docs in the download package, don't expect them to be very fun to use :)
> 
> 3. The docs are not fully updated, so they might be just flat out wrong! I plan to update the docs completely for the next beta release.
> 
> So, for the good stuff... here are some notes for differences between 1.0 and 2.0:
> 
>      * Ranges!
>      * Filled out slicing for all containers
>      * Cursors are now non-movable.  Use ranges for safe iteration.
>      * The interfaces have been cut down significantly. The question I
> asked myself when deciding whether I wanted to keep an interface is "would
> anyone use this interface?"
>      * Functions that should be fast but can be slow (O(n)) have been
> removed from all interfaces, and in most cases, from the containers.
> Notably missing is searching a non-quick lookup container for a value. Use
> std.algorithm.find for that.
>      * ArrayMultiset has been removed -- it's complexity functions did not
> fit with the multiset requirements (specifically, quick lookup of an
> element's presence).
>      * ArrayList slicing now simply returns a range instead of a "live"
> slice.  Note that an ArrayList range is aliased to a D array.
>      * Full unit tests added for all container types.
> 
> I have also changed the license from BSD to Boost.
> 
> 
> --------
> 
> I have also formally released version 0.03 as version 1.0, nothing has changed there, including the license.  However, no new features will be added to dcollections version 1.0, only bug fixes will be done.
> 
> Please, file tickets on dsource for any problems you have.  And let me know if there are any ideas you think would be useful.
> 
> -Steve

Well as long as you're here can I submit an error here? :)

I get an error while building the D2 branch:

Error: ArrayMultiset.obj : No such file or directory

It seems the ArrayMultiset.d is not in the dcollections folder for the D2.x  branch, although it is in trunk (I guess the trunk is the D1.x one?).

Is that module deprecated for d2.x? (although it's listed in the win32 batch file)