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.

Introduction to ds

“Introduction to ds” is a slide presentation/manual about ds which I started last year. I never had enough time to finish it quickly so I wrote it now and then and just recently finished it.

The presentation explains the concepts and design decisions behind ds, provides short code examples to demonstrate basic usage and covers each data structure in a few words. I tried to squeeze in as much information as possible but due to the complexity of the topic it’s impossible to go into detail – each data structure alone could easily fill a presentation…

Code examples are all in haXe language, but converting to AS3 is simply a matter of removing type parameters <T> and renaming Int to int, Float to Number and so on.

“Introduction to ds” (pdf)

Or watch it on slideshare.net:

I hope you find it useful! (if you are an experienced game programmer you will be probably bored ;))