I've been tinkering with a collection package that is a hybrid between C++, Java, and Tango, utilizing the best D features (such as slicing, foreach, etc.).

The result is dcollections.  Here is a list of the features:

    * Hash, RBTree, Link, and Array implementations for appropriate
containers.
    * List, Set, Map, and Multiset containers provided.
    * Able to swap out underlying implementation of a container, or
customize implementation.
    * Minimized heap activity. All cursors are struct-based.
    * Should be compatible with both Tango and Phobos (tested with Tango).
    * Slicing where appropriate (currently only ArrayList, but will add to
other containers).
    * Removal while traversing.
    * Removal of elements does not invalidate cursors where possible.
    * Cursors can be kept for later use (such as O(1) removal if supported
by the container).
    * Interfaces for implementation-independent code.
    * Concatenation and appending for lists.
    * dup functions.
    * Set/Map intersection.
    * Handy filter, transform, and chain iterators.

There's a lot left to be done, especially on the documentation and testing side, so don't expect everything to be properly documented or actually work :)  But I think it's at a point where it can be useful.

Enjoy!

http://www.dsource.org/projects/dcollections

-Steve

Steven Schveighoffer Wrote:

> I've been tinkering with a collection package that is a hybrid between C++, Java, and Tango, utilizing the best D features (such as slicing, foreach, etc.).
> 
> The result is dcollections.  Here is a list of the features:
> 
>     * Hash, RBTree, Link, and Array implementations for appropriate
> containers.
>     * List, Set, Map, and Multiset containers provided.
>     * Able to swap out underlying implementation of a container, or
> customize implementation.
>     * Minimized heap activity. All cursors are struct-based.
>     * Should be compatible with both Tango and Phobos (tested with Tango).
>     * Slicing where appropriate (currently only ArrayList, but will add to
> other containers).
>     * Removal while traversing.
>     * Removal of elements does not invalidate cursors where possible.
>     * Cursors can be kept for later use (such as O(1) removal if supported
> by the container).
>     * Interfaces for implementation-independent code.
>     * Concatenation and appending for lists.
>     * dup functions.
>     * Set/Map intersection.
>     * Handy filter, transform, and chain iterators.
> 
> There's a lot left to be done, especially on the documentation and testing side, so don't expect everything to be properly documented or actually work :)  But I think it's at a point where it can be useful.
> 
> Enjoy!
> 
> http://www.dsource.org/projects/dcollections
> 
> -Steve
> 
> 

Just wondering why people (especially from the U.S.) always build red-black trees instead of AVL trees ( http://en.wikipedia.org/wiki/Avl_tree ) which are faster, simpler to understand, simpler to implement and support the same set of operations?

Some guy wrote:
> Steven Schveighoffer Wrote:
> 
>> I've been tinkering with a collection package that is a hybrid between C++, Java, and Tango, utilizing the best D features (such as slicing, foreach, etc.).
>>
>> The result is dcollections.  Here is a list of the features:
>>
>>     * Hash, RBTree, Link, and Array implementations for appropriate containers.
>>     * List, Set, Map, and Multiset containers provided.
>>     * Able to swap out underlying implementation of a container, or customize implementation.
>>     * Minimized heap activity. All cursors are struct-based.
>>     * Should be compatible with both Tango and Phobos (tested with Tango).
>>     * Slicing where appropriate (currently only ArrayList, but will add to other containers).
>>     * Removal while traversing.
>>     * Removal of elements does not invalidate cursors where possible.
>>     * Cursors can be kept for later use (such as O(1) removal if supported by the container).
>>     * Interfaces for implementation-independent code.
>>     * Concatenation and appending for lists.
>>     * dup functions.
>>     * Set/Map intersection.
>>     * Handy filter, transform, and chain iterators.
>>
>> There's a lot left to be done, especially on the documentation and testing side, so don't expect everything to be properly documented or actually work :)  But I think it's at a point where it can be useful.
>>
>> Enjoy!
>>
>> http://www.dsource.org/projects/dcollections
>>
>> -Steve 
>>
>>
> 
> Just wondering why people (especially from the U.S.) always build red-black trees instead of AVL trees ( http://en.wikipedia.org/wiki/Avl_tree ) which are faster, simpler to understand, simpler to implement and support the same set of operations?
It mentions in that very wiki article that AVL trees may be slower at insertion than red-black trees.

"Some guy" wrote

> Just wondering why people (especially from the U.S.) always build red-black trees instead of AVL trees ( http://en.wikipedia.org/wiki/Avl_tree ) which are faster, simpler to understand, simpler to implement and support the same set of operations?

Maybe because I've never heard of them :)  Although, I probably did in my algorithms class, I just don't remember paying a lot of attention there...

No matter though, the TreeMap collection's implementation can be easily swapped out for an AVL version.  Thanks for the link!

-Steve

Steven Schveighoffer wrote:
> I've been tinkering with a collection package that is a hybrid between C++, Java, and Tango, utilizing the best D features (such as slicing, foreach, etc.).

Interesting stuff.  Any plans for adding sorting?

"torhu" wrote
> Steven Schveighoffer wrote:
>> I've been tinkering with a collection package that is a hybrid between C++, Java, and Tango, utilizing the best D features (such as slicing, foreach, etc.).
>
> Interesting stuff.  Any plans for adding sorting?

I wasn't planning on it...

I think sorting really only makes sense in cases where quick lookup is possible.  The implementations I support are:

RBTree -> already sorted
Hash -> can't be sorted
Link -> don't have quick lookup.
Array -> possible to sort using the built-in array sort:

ArrayList!(int) x([5,4,3,2,1]);

x.asArray.sort;

Basically, for ArrayList, any possible sort routines that are written for builtin arrays can be applied.

For unsortable implementations, they can be 'sorted' by adding them to a Tree implementation, which will sort on insertion.  Or if you like, turned into an array, and sorted there.

Is there another requirement I'm missing?

-Steve

Reply to Steven,

> "torhu" wrote
> 
>> Steven Schveighoffer wrote:
>> 
>>> I've been tinkering with a collection package that is a hybrid
>>> between C++, Java, and Tango, utilizing the best D features (such as
>>> slicing, foreach, etc.).
>>> 
>> Interesting stuff.  Any plans for adding sorting?
>> 
> I wasn't planning on it...
> 
> I think sorting really only makes sense in cases where quick lookup is
> possible.  The implementations I support are:
> 
> RBTree -> already sorted
> Hash -> can't be sorted
> Link -> don't have quick lookup.
> Array -> possible to sort using the built-in array sort:
> ArrayList!(int) x([5,4,3,2,1]);
> 
> x.asArray.sort;
> 
> Basically, for ArrayList, any possible sort routines that are written
> for builtin arrays can be applied.
> 
> For unsortable implementations, they can be 'sorted' by adding them to
> a Tree implementation, which will sort on insertion.  Or if you like,
> turned into an array, and sorted there.
> 
> Is there another requirement I'm missing?
> 
> -Steve
> 

One thing that might make this easier would be a collection of collections type:

Many!(T, RBTree, Array) foo

foo would have the API for both RBTree and Array but adding/removing to/from one would also do the same to the other. This might be more useful with something like several RBTrees where each is sorted differently.

Steven Schveighoffer wrote:
> "torhu" wrote
>> Steven Schveighoffer wrote:
>>> I've been tinkering with a collection package that is a hybrid between C++, Java, and Tango, utilizing the best D features (such as slicing, foreach, etc.).
>>
>> Interesting stuff.  Any plans for adding sorting?
> 
> I wasn't planning on it...
> 
> I think sorting really only makes sense in cases where quick lookup is possible.  The implementations I support are:
> 
> RBTree -> already sorted
> Hash -> can't be sorted
> Link -> don't have quick lookup.
> Array -> possible to sort using the built-in array sort:
> 

I was mostly thinking about a sortable linked list.  I guess it can be done by copying the contents into another container, like you suggest. How fast that would be would probably depend on how your linked list is implemented, how much needs to be copied before sorting can be done.

Steven Schveighoffer wrote:
> I've been tinkering with a collection package that is a hybrid between C++, Java, and Tango, utilizing the best D features (such as slicing, foreach, etc.).
> 
> The result is dcollections.  Here is a list of the features:
> 
>     * Hash, RBTree, Link, and Array implementations for appropriate containers.
>     * List, Set, Map, and Multiset containers provided.
>     * Able to swap out underlying implementation of a container, or customize implementation.
>     * Minimized heap activity. All cursors are struct-based.
>     * Should be compatible with both Tango and Phobos (tested with Tango).
>     * Slicing where appropriate (currently only ArrayList, but will add to other containers).
>     * Removal while traversing.
>     * Removal of elements does not invalidate cursors where possible.
>     * Cursors can be kept for later use (such as O(1) removal if supported by the container).
>     * Interfaces for implementation-independent code.
>     * Concatenation and appending for lists.
>     * dup functions.
>     * Set/Map intersection.
>     * Handy filter, transform, and chain iterators.
> 
> There's a lot left to be done, especially on the documentation and testing side, so don't expect everything to be properly documented or actually work :)  But I think it's at a point where it can be useful.
> 
> Enjoy!
> 
> http://www.dsource.org/projects/dcollections
> 
> -Steve 
> 
> 
Nice!  Have you considered adding a B+Tree (or a B*Tree). That would require a backing file store...but it could be quite useful.

Some guy wrote:
> Steven Schveighoffer Wrote:
> 
>> I've been tinkering with a collection package that is a hybrid between C++, Java, and Tango, utilizing the best D features (such as slicing, foreach, etc.).
>>
>> The result is dcollections.  Here is a list of the features:
>>
>>     * Hash, RBTree, Link, and Array implementations for appropriate containers.
>>     * List, Set, Map, and Multiset containers provided.
>>     * Able to swap out underlying implementation of a container, or customize implementation.
>>     * Minimized heap activity. All cursors are struct-based.
>>     * Should be compatible with both Tango and Phobos (tested with Tango).
>>     * Slicing where appropriate (currently only ArrayList, but will add to other containers).
>>     * Removal while traversing.
>>     * Removal of elements does not invalidate cursors where possible.
>>     * Cursors can be kept for later use (such as O(1) removal if supported by the container).
>>     * Interfaces for implementation-independent code.
>>     * Concatenation and appending for lists.
>>     * dup functions.
>>     * Set/Map intersection.
>>     * Handy filter, transform, and chain iterators.
>>
>> There's a lot left to be done, especially on the documentation and testing side, so don't expect everything to be properly documented or actually work :)  But I think it's at a point where it can be useful.
>>
>> Enjoy!
>>
>> http://www.dsource.org/projects/dcollections
>>
>> -Steve 
>>
>>
> 
> Just wondering why people (especially from the U.S.) always build red-black trees instead of AVL trees ( http://en.wikipedia.org/wiki/Avl_tree ) which are faster, simpler to understand, simpler to implement and support the same set of operations?

Well, according to my data structures prof...

- For data inserted perfectly randomly, plain BSTs work best
- For data inserted mostly randomly but with occasional ordering, red-black trees work best. This is why Java's collection framework uses them, since for unknown user data they're probably the best choice
- For data inserted in a mostly-ordered fashion, AVL trees work best
- For data retrieved in an ordered or clumped fashion, Splay trees are best
- For data that won't fit entirely in memory, B+trees are best (but that's sort of a special niche)