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 nxt.my_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 {
20     import nxt.filters : DynamicDenseSetFilter, Growable, Copyable;
21     import nxt.container.dynamic_array : DynamicArray;
22 
23     alias ElementType = E;
24 
25     @disable this(this);
26 
27     pragma(inline, true):
28 
29     /** Insert element `e`.
30         Returns: precense status of element before insertion.
31     */
32     bool insert()(E e)          /* template-lazy */
33     {
34 		// TODO: this doesn’t seem right:
35         const hit = _set.insert(e);
36         if (!hit)
37             _array.insertBack(e);
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 => _set.contains(e); /* template-lazy */
44     /// ditto
45     bool opBinaryRight(string op)(E e) const if (op == "in") => contains(e);
46 
47     /// Check if empty.
48     bool empty() const @property => _array.empty;
49 
50     /// Get length.
51     @property size_t length() const => _array.length;
52 
53     /// Non-mutable slicing.
54     auto opSlice() const => _array.opSlice; /* template-lazy */
55 
56     /// Clear contents.
57     void clear()()              /* template-lazy */
58     {
59         _set.clear();
60         _array.clear();
61     }
62 
63 private:
64     // TODO: merge into store with only one length and capcity
65     DynamicDenseSetFilter!(E, Growable.yes, Copyable.no) _set;
66     DynamicArray!(E, Allocator) _array;
67 }
68 
69 @safe pure nothrow @nogc:
70 
71 unittest
72 {
73     DynamicDenseSetFilterGrowableArray!uint x;
74 
75     assert(!x.insert(42));
76     assert(x.contains(42));
77     assert(x[] == [42].s);
78 
79     assert(x.insert(42));
80     assert(x.contains(42));
81     assert(x[] == [42].s);
82 
83     assert(!x.insert(43));
84     assert(x.contains(43));
85     assert(x[] == [42, 43].s);
86 
87     x.clear();
88     assert(x.empty());
89 
90     assert(!x.insert(44));
91     assert(x.contains(44));
92     assert(x[] == [44].s);
93 }
94 
95 version(unittest)
96 {
97     import nxt.array_help : s;
98 }