nxt.filterarray source code

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