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