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