1 module nxt.tree; 2 3 /** N-ary tree that cannot shrink but only grow (in breadth and depth). 4 * 5 * Because of this a region allocator can be used for internal memory 6 * allocation. 7 * 8 * See_Also: http://forum.dlang.org/post/prsxfcmkngfwomygmthi@forum.dlang.org 9 */ 10 struct GrowOnlyNaryTree(E) 11 { 12 alias N = Node!E; 13 14 /* @safe pure: */ 15 public: 16 17 /// Create with region size in bytes. 18 this(size_t regionSize) @trusted 19 { 20 _allocator = Allocator(regionSize); 21 } 22 23 this(in E e, size_t regionSize) @trusted 24 { 25 _allocator = Allocator(regionSize); 26 _root = _allocator.make!N(e); 27 } 28 29 /// Returns: top node. 30 inout(Node!E)* root() inout return scope 31 { 32 return _root; 33 } 34 35 private: 36 N* _root; 37 38 // import std.experimental.allocator.mallocator : Mallocator; 39 import std.experimental.allocator : make, makeArray; 40 import std.experimental.allocator.building_blocks.region : Region; 41 import nxt.pure_mallocator : PureMallocator; 42 alias Allocator = Region!PureMallocator; 43 44 Allocator _allocator; 45 } 46 47 /*@safe*/ unittest 48 { 49 struct X { string src; } 50 51 const e = X("alpha"); 52 auto tree = GrowOnlyNaryTree!X(e, 1024 * 1024); 53 assert(tree.root.data == e); 54 55 // TODO this should fail to compile with -dip1000 56 Node!X* dumb() 57 { 58 auto tree = GrowOnlyNaryTree!X(e, 1024 * 1024); 59 return tree.root; 60 } 61 62 dumb(); 63 } 64 65 /// Tree node containing `E`. 66 private struct Node(E) 67 { 68 private: 69 E data; 70 71 // allocate with pointers with std.experimental.allocator.makeArray and each 72 // pointer with std.experimental.allocator.makeArray 73 Node!E*[] subs; 74 }