nxt.container.common source code

1 /** Helpers used by containers.
2  */
3 module nxt.container.common;
4 
5 /** Flag for use of dynamic version of Rust-style ownership-and borrowing.
6  */
7 enum BorrowCheckFlag : ubyte { no, yes }
8 
9 /** Growth strategy.
10  */
11 enum GrowthStrategy {
12 	grow_2,						// 2.0
13 	grow_3over2,				// 1.5
14 }
15 
16 /** Reserve room for `extra` more elements in `x`.
17  */
18 size_t reserveWithGrowth(GrowthStrategy gs, T)(ref T x, size_t extra)
19 if (is(typeof(T.init.capacity) : size_t) &&
20 	is(typeof(x.reserve(size_t.init)) == size_t))
21 {
22 	const newCapacity = x.capacity + extra;
23 	static      if (gs == GrowthStrategy.grow_2)
24 		return x.reserve(newCapacity);
25 	else static if (gs == GrowthStrategy.grow_3over2)
26 		return x.reserve(newCapacity);
27 	else
28 		static assert(0, "Unknown growth strategy " ~ gs.stringof);
29 }
30 
31 @safe pure nothrow unittest {
32 	int[] x;
33 	x.reserve(2);
34 	x.reserveWithGrowth!(GrowthStrategy.grow_2)(1);
35 	assert(x.capacity >= 3);
36 }
37 
38 /** Try to pop first occurrence of `needle` in `haystack` (if any).
39     Returns: `true` iff pop was made, `false` otherwise.
40  */
41 bool popFirstMaybe(alias pred = "a == b", C, E)(ref C haystack, in E needle)
42 if (__traits(hasMember, C, "length") &&
43     __traits(hasMember, C, "popAt"))
44     // TODO: activate this restriction
45     // if (hasSlicing!C &&
46     //     is(ElementType!C == E.init))
47 {
48     import std.functional : binaryFun;
49     // doesn't work for uncopyable element types: import std.algorithm.searching : countUntil;
50     size_t offset = 0;
51     foreach (const ref e; haystack[])
52     {
53         if (binaryFun!pred(e, needle))
54             break;
55         offset += 1;
56     }
57     if (offset != haystack.length)
58     {
59         haystack.popAt(offset);
60         return true;
61     }
62     return false;
63 }
64 
65 /** Remove element at index `index` in `r`.
66  *
67  * TODO: reuse in array*.d
68  * TODO: better name removeAt
69  */
70 void shiftToFrontAt(T)(T[] r, size_t index) @trusted
71 {
72     assert(index + 1 <= r.length);
73 
74     // TODO: use this instead:
75     // immutable si = index + 1;   // source index
76     // immutable ti = index;       // target index
77     // immutable restLength = this.length - (index + 1);
78     // moveEmplaceAll(_store.ptr[si .. si + restLength],
79     //                _store.ptr[ti .. ti + restLength]);
80 
81     // for each element index that needs to be moved
82     foreach (immutable i; 0 .. r.length - (index + 1))
83     {
84         immutable si = index + i + 1; // source index
85         immutable ti = index + i;     // target index
86         import core.lifetime : moveEmplace;
87         moveEmplace(r.ptr[si], // TODO: remove `move` when compiler does it for us
88                     r.ptr[ti]);
89     }
90 }
91 
92 @safe pure nothrow @nogc unittest
93 {
94     int[4] x = [11, 12, 13, 14];
95     x[].shiftToFrontAt(1);
96     assert(x == [11, 13, 14, 14]);
97 }