Data Structures For Games
The library contains parametrized classes that allow programmers to easily implement standard data structures like linked lists, queues, stacks or multi-dimensional arrays. The result is somewhere in between the C++ STL (Standard Template Library) and the Java Collection framework.
Documentation
Cross-Platform Support
ds supports the following Haxe compilation targets: -swf, -js, -neko, -python, -php, -cpp
-hl, -java, -cs, jvm are experimental.
Installation
Install Haxe and run $ haxelib install polygonal-ds from the console, then compile with $ haxe ... -lib polygonal-ds.
Conditional Compilation Flags
-D generic
Enables generic classes (adds @:generic meta).
Nice performance boost for static typed platforms (-swf,-cpp only).
-D alchemy
Enables fast virtual memory for FP10+ ("alchemy memory"). Extra performance for Flash.
Changelog
2.2.0 (wip)
- all: removed polygonal package structure
- fixed: Graph.removeSingleArcs(), removeMutualArcs()
- modified: More conservative inlining (use selective inlining when actually needed)
- modified: Use implicit casting for Comparables
- added: Bitfield abstract
- modified: ArrayTools.pairwise length parameter
- modified: Added GraphNode.visible (quickly hide node from graph without disconnecting it)
- modified: Added Array2.flipHorizontal, Array2.flipVertical
- modified: Added ArrayTools.random()
- modified: Added Array2.shiftRowLeft, Array2.shiftRowRight
- modified: Added GraphNode.forEeachNeighbor()
- all: Small fixes and optimizations
2.1.1 (released 2019-11-10)
Supports Haxe Compiler 4.0.1, hxcpp 4.0.64
- modified: require Haxe 4.0.0 (Haxe 3.x no longer maintained)
- added: RadixSort helper class
- added: ArrayList.bruteforce()
- added: ArrayTools.bruteforce()
- fixed: Graph.dlbfs(): incorrect GraphNode.parent pointer
- added: Bits.swap()
- modified: Graph.removeArc(): add optional mutual parameter
- added: ArrayTools.forEach()
- added: ArrayList.addNativeArray()
- added: FreeList helper class (tools package)
- added: ArrayList.pairwise()
- modified: removed var shadowing warnings (-D warn-var-shadowing)
- modified: moved mem package to tools package
- modified: Array2.countNeighbors(): add manhatten parameter
- added: TreeTools.ofIndentedList()
- added: TreeTools.randomTree()
- added: TreeTools.map()
- modified: trim package to polygonal.ds
- added: ArrayList.resize()
- fixed: ArrayList.reverse()
- added: compile with
-D no-assert to remove assert statements even when compiling with -debug
- added: compile with
-D runtime_assert to use non-macro asserts (faster)
- modified: ArrayTools.equals(): now passing equals function as argument
2.0.1 (released 2017-10-10)
Supports Haxe Compiler 3.4.4, hxcpp 3.4.188
- modified: HashKey: allow static initializers for non-static targets
- added: Array2.Array2Cell.of()
- modified: renamed M to MathTools
- modified: removed unused imports/vars
- added ArrayTools.pairwise()
- added Array2.countNeighbors()
- added wrap=true parameter to Array2.shift* methods
2.0.0 (released 2017-01-31)
Supports Haxe Compiler 3.4.0, hxcpp 3.4.49
- added: Array2.copy()
- modified: optimized Array2.resize(): use fast blit when only changing #rows
- modified: optimized ArrayList.remove(): remove multiple values at once, use fast blit
- modified: added ArrayTools.swap()
- modified: added ArrayTools.getFront()
- modified: added ArrayTools.iter()
- added: ArrayList.addArray()
- added: Array2.getIndexAtCell()
- fixed: Array2.clear(), Array3.clear()
- added: ArrayList.addArray()
- added: ArrayList.insertionSort()
- modified: allow more method chaining
- modified: Sll/Dll: popDown() => tailToHead(), shiftUp() => headToTail()
- added: tools.Shuffle for customizing Math.random() rng
- fixed: integer hash tables print all key,value pairs for duplicate keys
2.0.0-rc1 (released 2016-11-05)
Supports Haxe Compiler 3.4.0-rc1, hxcpp 3.4.2
- modified: replaced GraphArc.cost with a more versatile GraphArc.userData field
- added: Graph.serialize() and Graph.unserialize()
- added: implemented iter(), fast alternative to iterator()
- modified: inline and optimize forEach()
2.0.0-beta (released 2016-05-24)
- modified: replaced pooling package with lightweight de.polygonal.ds.tools.ObjectPool class
- modified: removed some Bits methods (better suited for abstract), move Bits class to tools package
- modified: BitVector: use getters for size/capacity
- modified: better method naming: don't use abbreviations
- modified: renamed Graph methods (DFS, BFS, DLBFS => dfs, bfs, dlbfs)
- modified: added Set.unset() method
- modified: remove .swc files- no longer maintained (use tools/swc/run.bat to create swc libs on your own)
- added: List<T> interface (implemented by ArrayList, Sll, Dll)
- modified: replaced de.polygonal.ds.Vector typedef with NativeArray<T> type.
- added: NativeArrayTools: helper class for working with fast platform specific native arrays.
- modified: arrayed structures now use fast platform specific "native arrays" (vectors) for internal storage
- added: replaced Da structure with new ArrayList implementation (resizable native array)
- modified: renamed swp() => swap(), cpy() => copy()
- modified: Map.clr() renamed to Map.unset() to distinguish from Collection.clear()
- modified: optimized toString()
- added: various growth rates for vector-based structures (see GrowthRate)
- modified: Array2/3: getW(), getH(), getD() is now a property: width, height, depth
- modified: removed ArrayConvert due to issues with -D generic, instead added ?source:Array<T> to constructor
- modified: removed toVector() method
- modified: renamed ArrayUtil to ArrayTools: match Haxe naming style
- modified: iter() renamed to forEach() and implement for all structures
- modified: removed redundant assign() and fill() methods: use forEach() instead
- modified: size() is now a property: Collection.size
- fixed: haxelib package
- modified: greatly improved performance for static platforms when compiled with -D generic (-swf and -cpp only)
- modified: cpp target: increase performance by skipping bounds checking when accessing arrays internally
- fixed: always increment iterator state inside next()
- added: support python and php target
- fixed: Graph.remove()
- modified: require flash10; drop support for fp 9.x
- added: IntIntHashTable.hasPair() for checking if a {key, value} pair exists
- added: IntIntHashTable.clrPair() for removing a {key, value} pair
- added: IntIntHashTable.toKeyVector()
- added: Array.getRect() for extracting a rectangular region
- modified: use access control instead of friend sytax with typedef
- modified: less aggressive inlining
1.4.1 (released 2013-07-08)
- modified: removed "polygonal-core" haxelib dependency
1.4.0 (released 2013-06-28; Haxe 3.0.0)
Supports Haxe Compiler 3.0.0
- modified: support Haxe 3 only (Haxe 2.x and Neko 1.x are no longer supported)
- modified: sacrifice Collection.toDA() for proper @:generic support
- modified: explicitly allocate elements in ArrayUtil.alloc() when targeting neko
- fixed: several fixes when compiling with -D generic
- modified: change BitVector to use the haxe.ds.Vector as data
- modified: ArrayUtil.shrink(): trim when targeting cpp
- modified: ArrayUtil.alloc(): explicitly allocate elements when targeting cpp
- modified: more conservative inlining
- modified: don't allocate stack arrays when doing iterative pre/post-order traversals
- modified: optimized TreeNode.contains()
- modified: optimize TreeNode.levelOrder by using an implicit queue
- modified: all: fill() method returns this for chaining
1.39 (released 2013-02-12)
Supports Haxe Compiler 2.10 & Haxe 3.00 r6189
- fixed: swc files: get rid of warnings for Flash Builder 4.7 + falcon compiler
- fixed: cpp + blackberry target
- fixed: some Haxe 3 fixes
1.38 (released 2013-01-27)
- modified: swc: moved Haxe classes to hx package
- added: serialization of TreeNode structures (de.polygonal.ds.Serialization)
- fixed: minor fixes for -D haxe3
- added: ArrayUtil.equals()
- added: IntIntHashTable, IntHashTable, HashTable.getAll()
- fixed: IntIntHashTable.remove()
- added: BitVector.getBucketAt(), getBuckets()
- modified: replaced DA.swapWithBack() with DA.swapPop()
- added: ArrayUtil.split()
- fixed: TreeNode.removeChildren()
- added: unit tests
- added: support Neko 2.0 RC (compile with -D neko_v2)
1.37 (released 2012-11-15)
- modified: Graph: added Graph.borrowArc() and Graph.returnArc() to allow optional arc pooling
- fixed: TreeNode.isAncestor(), TreeNode.isDescendant()
- fixed: LinkedObjectPool: object instantiation for non-flash targets
- added: ArrayUtil.quickPerm(): counting quickperm algorithm
1.36 (released 2012-07-25)
- added: TreeNode.isAncestor()
- added: TreeNode.isDescendant()
- added: TreeNode.getChildIndex()
- modified: TreeNode.preorder, postorder: allow node removal during traversal
- fixed: PriorityQueue.toString(): now prints elements in sorted order
- modified: faster debugging with --no-inline through macro-based asserts
- fixed: DA.inRange()
- added: DLL.createNode(), DLL.appendNode(), DLL.prependNode()
- fixed: typo Bitflags.setiff() => setfif()
- added: TreeNode.insertChildAt()
- added: TreeNode.removeChildAt()
- added: TreeNode.setChildIndex()
- added: TreeNode.swapChildren()
- added: TreeNode.swapChildrenAt()
- fixed: TreeNode.insertAfterChild(), insertBeforeChild()
- modified: TreeNode.numChildren() is now O(1)
- added: TreeNode.removeChildren()
- added: TreeNode.setStack()
- modified: TreeNode.getChildAtIndex() => TreeNode.getChildAt()
- modified: cpp/nme target: now supporting MemoryManager
- added: XmlConvert.toTreeNode(): xml => TreeNode conversion
- added: Array2.copyCol(), Array2.swapCol()
- added: Array2.copyRow(), Array2.swapRow()
- fixed: support Haxe 2.10
- modified: also dump state with toString() in release mode
- fixed: DA.sort() out of bound access
- fixed: BitVector.ofBytes for neko
1.35 (released 2011-12-22)
- modified: Collection.clone(): make assign parameter optional so clone() does a shallow copy per default
- added: Array2.setNestedArray()
- added: TreeNode.getChildAtIndex()
- added: include Lambda class in swc files (http://haxe.org/api/lambda)
- added: TreeNode.childIterator()
- fixed: Heap.remove(), PriorityQueue.remove()
- fixed: Collection.toVector()
- modified: Heap.remove(), PriorityQueue.remove() is now O(1)
1.34 (released 2011-10-26)
- added: all: Collection.toVector() for FP10+
- modified: too many issues with -D swf-protected so revert back to prefixing private members with underscore
1.33 (released 2011-10-21)
- modified: disabled haxe.rtti.Generic optimization by default, enable with -D 'generic' (replaces 'no_rtti' flag)
- fixed: DynamicObjectPool: 'object x was returned twice to the pool' assert
- added: DynamicObjectPool.used()
- added: Compare.lexiographic()
- added: Bits.unpackUI16Lo(), unpackUI16Hi()
- fixed: DLL.lastNodeOf()
- fixed: TreeNode.levelOrder
- modified: ObjectPool: allow lazy allocation by using ObjectPool.allocate(true, ...)
- added: ArrayedDeque.indexOfFront(), indexOfBack()
- added: LinkedDeque.indexOfFront(), indexOfBack()
- fixed: HashMap.toArray()
- added: BitVector.clrRange(), setRange()
- added: Array2.inRange(), Array3.inRange()
- added: Array2.getAt(), Array3.getAt()
- fi