nxt.hybrid_array source code

1 /** Hybrid array containers.
2  */
3 module nxt.hybrid_array;
4 
5 import std.traits : isIntegral;
6 import nxt.filters : isDynamicDenseSetFilterable;
7 import std.experimental.allocator.mallocator : Mallocator;
8 
9 /** Hybrid container combining `DynamicDenseSetFilter` growable into `DynamicArray`.
10  *
11  * Has O(1) unordered element access via slicing.
12  *
13  * For use in graph algorithms with limited index ranges.
14  *
15  * TODO: better name?
16  */
17 struct DynamicDenseSetFilterGrowableArray(E, Allocator = Mallocator)
18 if (isDynamicDenseSetFilterable!E) {
19 	import nxt.filters : DynamicDenseSetFilter, Growable, Copyable;
20 	import nxt.container.dynamic_array : DynamicArray;
21 
22 	alias ElementType = E;
23 
24 	this(this) @disable;
25 
26 	pragma(inline, true):
27 
28 	/** Insert element `e`.
29 		Returns: precense status of element before insertion.
30 	*/
31 	bool insert()(E e) /*tlm*/ {
32 		/+ TODO: this doesn’t seem right: +/
33 		const hit = _set.insert(e);
34 		if (!hit)
35 			_array.insertBack(e);
36 		return hit;
37 	}
38 	alias put = insert;		 // OutputRange compatibility
39 
40 	/// Check if element `e` is stored/contained.
41 	bool contains()(E e) const => _set.contains(e); /*tlm*/
42 	/// ditto
43 	bool opBinaryRight(string op)(E e) const if (op == "in") => contains(e);
44 
45 	/// Get length.
46 	@property size_t length() const => _array.length;
47 
48 	/// Non-mutable slicing.
49 	auto opSlice() const => _array.opSlice; /*tlm*/
50 
51 	/// Clear contents.
52 	void clear()() /*tlm*/ {
53 		_set.clear();
54 		_array.clear();
55 	}
56 
57 private:
58 	/+ TODO: merge into store with only one length and capcity +/
59 	DynamicDenseSetFilter!(E, Growable.yes, Copyable.no) _set;
60 	DynamicArray!(E, Allocator) _array;
61 }
62 
63 pure nothrow @safe @nogc:
64 
65 unittest {
66 	DynamicDenseSetFilterGrowableArray!uint x;
67 
68 	assert(!x.insert(42));
69 	assert(x.contains(42));
70 	assert(x[] == [42].s);
71 
72 	assert(x.insert(42));
73 	assert(x.contains(42));
74 	assert(x[] == [42].s);
75 
76 	assert(!x.insert(43));
77 	assert(x.contains(43));
78 	assert(x[] == [42, 43].s);
79 
80 	x.clear();
81 	assert(x.length == 0);
82 
83 	assert(!x.insert(44));
84 	assert(x.contains(44));
85 	assert(x[] == [44].s);
86 }
87 
88 version (unittest) {
89 	import nxt.array_help : s;
90 }