nxt.filterarray source code

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 }