Welcome to dcollections

dcollections is an implementation of collection classes inspired by Tango, Java, and C++. The goal of dcollections is to provide an efficient collections implementation that uses as many D ideas as possible.

Dcollections 1.0 has been released! This version is exactly the same as 0.03, except the README has been updated. It is available in tarball and zip formats. See below on how to access source via svn.

Dcollections 2.0 has gone into beta. Version 2.0 is built for D2, and will not work with D1. The version numbers will be 2.0a, 2.0b, etc. until it comes out of beta, and then it will be just called 2.0. The current beta release 2.0c is available in tarball and zip formats.

Jordi Sayol has also been kind enough to create .deb packages for dcollections. A .deb package is available for [116] for the library and docs. Note the version for these is 1.99 so it can upgrade to 2.0 once it comes out (apparently debian doesn't agree with my wacky versioning scheme!) These packages come from his google code site http://code.google.com/p/d-packages. Note that these contain compiled libs for both x86 and x86_64.

License

dcollections 1.0 is Open Source software distributed under the BSD License. See the full license here.

dcollections 2.0 is Open Source software distributed under the Boost License. See the full license here.

Features

  • Hash, RBTree, Link, Array, and Deque (D2 only) 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 and ranges are struct-based.
  • version 1.0 compatible with Tango and Phobos, version 2.0 compatible with D2 phobos.
  • Safe slicing for D2.
  • Removal while traversing.
  • Removal of elements does not invalidate cursors or ranges when possible.
  • Cursors and ranges 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.
  • Filter, transform, and chain iterators.
  • Custom allocators.

Changes from 1.0 to 2.0

Some noteworthy changes:

  • 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.
  • const/inout decorations (not everything works yet).

See the full ChangeLog

Documentation

DDoc is used to generate all the API documentation, which can be found here. Note this is 1.0 documentation, the 2.0 documentation cannot be automatically generated, and so is in a state of limbo at the moment. Eventually, an online version of the documentation will be available. The releases will have the generated documentation available (currently in basic ddoc format). Note, there is a nicely built debian package for the D2 documentation thanks to Epileg.

I will build some sort of tutorial eventually.

TODO

Note, version 1.0 is frozen, and will not gain any new features. This TODO list reflects items that will be done for the 2.0 version only.

In no specific order:

  • Add debug-mode code to allow ranges and cursors to check validity for testing.
  • Remove workarounds when compiler is fixed.
  • Figure out how to make const cursors/ranges work (need tail-const for this).
  • Look into how to have shared containers.
  • tutorial

Get it

trunk (D1 version):

svn co http://svn.dsource.org/projects/dcollections/trunk

d2 branch: (this will eventually become trunk)

svn co http://svn.dsource.org/projects/dcollections/branches/d2

Version X.XX:

svn co http://svn.dsource.org/projects/dcollections/tags/version-X.XX

You can find download zip, tarball, and deb packages here.