ds 2.0-beta released

I’ve just uploaded a new version of my data structures library for Haxe to haxelib. Please note that the new version requires Haxe 3.3.0-rc.1 and might not even compile using an older version like 3.2.x. Many thanks go to Simon Krajewski and Hugh Sanderson for fixing countless Haxe bugs related to my library :)

The update includes many small breaking changes so I’ve decided to release a new major version instead of a minor release. It’s a beta since there still are some problems with the java/cs target but all other targets are just working fine.


  • All arrayed structures have been refactored and now use fixed sized, native arrays (aka “Vectors”) for storing elements. This should be a bit faster when using static targets and gives more control over memory usage (prevent over-allocation).
  • In addition to the flash target, the cpp target now fully supports the @:generic meta, greatly improving performance.
  • Da (“dense array”) has been replaced with a new ArrayList implementation (similar to the one found in the Java collection framework).
  • I’m now using dox for generating documentation instead of chxdoc as the latter one doesn’t seem to be maintained any longer.
  • Some frequently used methods are now defined as properties, e.g. Collection.size() is now simply Collection.size.
  • A bunch of classes and methods were renamed to better match the Haxe code style and to improve readability; and there are no more abbreviations, for example BinaryTreeNode.getL() is now called getLeft().
  • Moved some helper classes to a new tools package
  • Python is now fully supported and tested
  • Many bug fixes …

Arrays v Vectors

When talking about the differences between arrays and vectors things can get a bit confusing if you are new to Haxe. In the world of Haxe, the built-in Array type is of dynamic nature (resizable) whereas Vectors have a constant size – in other languages like Java or C++ the exact opposite is true, where the length of an array is established when the array is created and Vector is a resizable container.
To prevent this kind of confusion I’m not using the term Vector, but instead added a NativeArray typedef similar to VectorData<T> (mapping to flash.Vector<T>, neko.NativeArray<T> and so on).

This approach was also required during development to get around some issues with the compiler; as mentioned above targeting java still doesn’t work so I’m falling back to the regular Array type.

Size v capacity

In addition to the size field, which counts the actual number of elements stored, some collections now also define a capacity field, denoting the number of elements that can be added without allocating more space.
Whenever a collection runs out of space capacity is adjusted according to the current growth rate (see constants defined in GrowthRate class). Here is an example:

//create an empty list with a capacity of 2 (default)
var list = new ArrayList();

//fill list with items
for (i in 0...100) list.pushback(i);

trace(list.size); //prints 100
trace(list.capacity); //prints 139

Notice that capacity is slightly larger than size. This is because the default growth rate is 1.5×. Filling the list requires multiple resize operations to fit 100 elements, so the growth pattern is 2,4,7,11,17,26,40,61,92,139 (see GrowthRate.compute() for implementation details).
Re-allocations are expensive so it’s best practice to create a collection with an initial capacity close to the expected size if possible:

//create an empty list with a capacity of 100
var list = new ArrayList(100);

The growth rate itself can also be adjusted (though the default should be fine in most cases). Possible values are GrowthRate.MILD (1.125× plus a constant) or GrowthRate.DOUBLE (2×). Assigning GrowthRate.FIXED means that the container isn’t resizable and a runtime error will occur if the user is trying to add more elements to it. Assigning any number >0, capacity grows by a constant value like so:

var list = new ArrayList(10);
trace(list.growthRate); //equals GrowthRate.NORMAL
list.growthRate = 10;
for (i in 0...100) list.add(i);

The growth pattern now becomes 20,30,40,50,60,70,80,100.