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