nxt.container.common source code

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