1 /** Extend std.algorithm.setopts to also operate on set- and map-like
2 	containers/ranges.
3 
4 	See_Also: http://forum.dlang.org/post/nvd09v$24e9$1@digitalmars.com
5 */
6 module nxt.setops_ex;
7 
8 // version = show;
9 
10 /** Specialization for `std.algorithm.setopts.setUnion` for AA. */
11 auto setUnionUpdate(T1, T2)(T1 a, T2 b) @trusted
12 if (isAA!T1 &&
13 	isAA!T2)
14 {
15 	if (a.length < b.length)
16 		return setUnionHelper(a, b);
17 	else
18 		return setUnionHelper(b, a);
19 }
20 
21 /** Helper function for `setUnionUpdate` that assumes `small` has shorter length than
22 	`large` .
23 */
24 private static auto setUnionHelper(Small, Large)(const Small small, Large large)
25 {
26 	Large united = large.dup;   /+ TODO: this shallow copy prevents large from being `const` +/
27 	foreach (const ref e; small.byKeyValue)
28 	{
29 		if (auto hitPtr = e.key in large)
30 			(*hitPtr) = e.value; /+ TODO: this potentially changes the value of +/
31 		else
32 			united[e.key] = e.value;
33 	}
34 	return united;
35 }
36 
37 /** Is `true` iff `T` is map-like container, that is provides membership
38  * checking via the `in` operator or `contains`.
39  *
40  * TODO: Move to Phobos std.traits
41  */
42 enum isAA(T) = __traits(isAssociativeArray, T); /+ TODO: check if in operator returns reference to value +/
43 
44 /// union of associative array (via keys)
45 pure @safe unittest {
46 	alias Map = string[int];
47 
48 	Map x = [0 : "a", 1 : "b"];
49 	Map y = [2 : "c"];
50 
51 	Map c = [0 : "a", 1 : "b", 2 : "c"];
52 
53 	// test associativity
54 	assert(setUnionUpdate(x, y) == c);
55 	assert(setUnionUpdate(y, x) == c);
56 }
57 
58 import std.traits : CommonType, isAssociativeArray;
59 import std.range.primitives;
60 import std.meta : anySatisfy, allSatisfy, staticMap;
61 import std.functional : binaryFun;
62 import std.range : SearchPolicy;
63 import nxt.range_ex : haveCommonElementType;
64 
65 private alias typeOfAAKeyValue(T) = typeof(T.init.byKeyValue);
66 private alias typeOfAAKey(T) = typeof(T.init.keys[0]);
67 private alias typeOfAAValue(T) = typeof(T.init.values[0]);
68 
69 /** Intersection of two or more associative arrays of type `Ts`.
70  *
71  * See_Also: https://forum.dlang.org/post/puwffthbqaktlqnourrs@forum.dlang.org
72  * TODO: Use switch + static foreach at https://forum.dlang.org/post/tdajgh$262i$1@digitalmars.com
73  */
74 auto setIntersectionAA(Ts...)(Ts inputs)
75 if (Ts.length >= 2 &&
76 	allSatisfy!(isAssociativeArray, Ts) &&
77 	!is(CommonType!(staticMap!(typeOfAAKey, Ts)) == void) &&
78 	!is(CommonType!(staticMap!(typeOfAAValue, Ts)) == void))
79 {
80 	alias Ranges = staticMap!(typeOfAAKeyValue, Ts);
81 	alias KeyType = CommonType!(staticMap!(typeOfAAKey, Ts));
82 	alias ValueType = CommonType!(staticMap!(typeOfAAValue, Ts));
83 	struct Pair { KeyType key; ValueType value; }
84 	struct Result
85 	{
86 		alias E0 = typeof(Ranges[0].front);
87 		this(Ts inputs)
88 		{
89 			this._inputs = inputs;
90 			size_t lengthMin = inputs[0].length;
91 			static foreach (const i, input; inputs)
92 			{
93 				this._ranges[i] = input.byKeyValue;
94 				if (i != 0 &&
95 					input.length < lengthMin)
96 				{
97 					lengthMin = input.length;
98 					_shortestInputIndex = i;
99 				}
100 			}
101 			tryFindNextFront();
102 		}
103 		@property bool empty() /*TODO: const*/
104 		{
105 			final switch (_shortestInputIndex)
106 			{
107 				static foreach (i; 0 .. _ranges.length)
108 				{
109 				case i:
110 					return _ranges[i].empty;
111 				}
112 			}
113 		}
114 		@property /*TODO: inout*/ Pair front() /*TODO: inout*/
115 		{
116 			final switch (_shortestInputIndex)
117 			{
118 				static foreach (i; 0 .. _ranges.length)
119 				{
120 				case i:
121 					return typeof(return)(_ranges[i].front.key,
122 										  _ranges[i].front.value);
123 				}
124 			}
125 		}
126 		void popFront()
127 		{
128 			foreach (ref range; _ranges)
129 				range.popFront();
130 			tryFindNextFront();
131 		}
132 		private void tryFindNextFront()
133 		{
134 			while (!empty)
135 			{
136 				if (matchPopOtherFronts(front))
137 					break;
138 			sw:
139 				final switch (_shortestInputIndex)
140 				{
141 					static foreach (i; 0 .. _ranges.length)
142 					{
143 					case i:
144 						_ranges[i].popFront();
145 						break sw;
146 					}
147 				}
148 			}
149 		}
150 		private bool matchPopOtherFronts(scope const Pair baseFront)
151 		{
152 			typeof(return) result = true;
153 			static foreach (const i; 0 .. Ranges.length) /+ TODO: replace with `static foreach (range; ranges)` when possible +/
154 			{
155 				if (i != _shortestInputIndex)
156 				{
157 					if (_ranges[i].empty)
158 						return false;
159 					if (auto valuePtr = baseFront.key in inputs[i])
160 					{
161 						if (baseFront.value != *valuePtr)
162 						{
163 							_ranges[i].popFront();
164 							result = false;
165 						}
166 					}
167 					else
168 						result = false;
169 				}
170 			}
171 			return result;
172 		}
173 	private:
174 		Ts _inputs;
175 		Ranges _ranges;
176 		size_t _shortestInputIndex;
177 		invariant { assert(_shortestInputIndex < inputs.length); }
178 	}
179 	return Result(inputs);
180 }
181 
182 ///
183 @safe unittest {
184 	alias T = int[string];
185 	T x2   = [	   "1":1, "2":2,		"4":4];
186 	T x3   = ["0":0, "1":1, "2":2, "3":3, "4":4];
187 	T x4   = [	   "1":1, "2":2, "3":3, "4":4, "5":5];
188 	T xh;
189 	auto y = setIntersectionAA(x2, x3, x4);
190 	assert(y._shortestInputIndex == 0);
191 	xh[y.front.key] = y.front.value;
192 	assert(!y.empty);
193 
194 	y.popFront();
195 	xh[y.front.key] = y.front.value;
196 	assert(!y.empty);
197 
198 	y.popFront();
199 	xh[y.front.key] = y.front.value;
200 	assert(!y.empty);
201 
202 	y.popFront();
203 	assert(y.empty);
204 
205 	assert(xh == x2);
206 }
207 
208 /** Intersection of two or more ranges of type `Rs`.
209  *
210  * See_Also: https://forum.dlang.org/post/puwffthbqaktlqnourrs@forum.dlang.org
211  */
212 private struct SetIntersectionFast(alias less = "a < b",
213 								   SearchPolicy preferredSearchPolicy = SearchPolicy.gallop,
214 								   Rs...)
215 if (Rs.length >= 2 &&
216 	allSatisfy!(isInputRange, Rs) &&
217 	!anySatisfy!(isAssociativeArray, Rs) &&
218 	haveCommonElementType!Rs)
219 {
220 private:
221 	Rs _inputs;
222 	alias comp = binaryFun!less;
223 	alias ElementType = CommonType!(staticMap!(.ElementType, Rs));
224 
225 	// Positions to the first elements that are all equal
226 	void adjustPosition()
227 	{
228 		if (empty) return;
229 
230 		auto compsLeft = Rs.length; // number of compares left
231 		static if (Rs.length > 1) while (true)
232 		{
233 			foreach (i, ref r; _inputs)
234 			{
235 				alias next = _inputs[(i + 1) % Rs.length]; // requires copying of range
236 
237 				/+ TODO: Use upperBound only when next.length / r.length > 12 +/
238 
239 				import std.range.primitives : isRandomAccessRange;
240 				static if (allSatisfy!(isRandomAccessRange, typeof(next)))
241 				{
242 					import std.range : assumeSorted;
243 
244 					/+ TODO: remove need for this hack +/
245 					static if (less == "a < b")
246 						enum lessEq = "a <= b";
247 					else static if (less == "a > b")
248 						enum lessEq = "a >= b";
249 
250 					/+ TODO: can we merge thsse two lines two one single assignment from nextUpperBound to next +/
251 					auto nextUpperBound = next.assumeSorted!lessEq.upperBound!preferredSearchPolicy(r.front);
252 					next = next[$ - nextUpperBound.length .. $];
253 
254 					if (next.empty)
255 						return; // next became empty, so everything becomes empty
256 					else if (next.front != r.front)
257 						compsLeft = Rs.length; // we need to start counting comparing again starting with next.front
258 				}
259 				else
260 				{
261 					if (comp(next.front, r.front))
262 					{
263 						do
264 						{
265 							next.popFront();
266 							if (next.empty) return;
267 						}
268 						while (comp(next.front, r.front));
269 						compsLeft = Rs.length;
270 					}
271 				}
272 				if (--compsLeft == 0) return; // count down, and if we have made Rs.length iterations we are compsLeft finding a common front element
273 			}
274 		}
275 	}
276 
277 public:
278 	///
279 	this(Rs inputs)
280 	{
281 		import std.functional : forward;
282 		this._inputs = inputs; /+ TODO: remove `forward` when compiler does it for us +/
283 		// position to the first element
284 		adjustPosition();
285 	}
286 
287 	///
288 	@property bool empty()
289 	{
290 		foreach (ref r; _inputs)
291 			if (r.empty)
292 				return true;
293 		return false;
294 	}
295 
296 	///
297 	void popFront() in(!empty)
298 	{
299 		static if (Rs.length > 1)
300 			foreach (i, ref r; _inputs)
301 			{
302 				alias next = _inputs[(i + 1) % Rs.length];
303 				assert(!comp(r.front, next.front));
304 			}
305 
306 		foreach (ref r; _inputs)
307 			r.popFront();
308 		adjustPosition();
309 	}
310 
311 	///
312 	ElementType front() @property in(!empty) => _inputs[0].front;
313 
314 	static if (allSatisfy!(isForwardRange, Rs))
315 	{
316 		///
317 		@property SetIntersectionFast save()
318 		{
319 			auto ret = this;
320 			foreach (i, ref r; _inputs)
321 				ret._inputs[i] = r.save;
322 			return ret;
323 		}
324 	}
325 }
326 
327 import core.internal.traits : Unqual;
328 
329 auto assumeMoveableSorted(alias pred = "a < b", R)(R r)
330 if (isInputRange!(Unqual!R))
331 {
332 	import core.lifetime : move;
333 	return MoveableSortedRange!(Unqual!R, pred)(move(r)); /+ TODO: remove `move` when compiler does it for us +/
334 }
335 
336 /** Get intersection of `ranges`.
337  *
338  * See_Also: https://forum.dlang.org/post/puwffthbqaktlqnourrs@forum.dlang.org
339  */
340 MoveableSortedRange!(SetIntersectionFast!(less, preferredSearchPolicy, Rs))
341 setIntersectionFast(alias less = "a < b",
342 					SearchPolicy preferredSearchPolicy = SearchPolicy.gallop,
343 					Rs...)(Rs ranges)
344 if (Rs.length >= 2 &&
345 	allSatisfy!(isInputRange, Rs) &&
346 	haveCommonElementType!Rs)
347 {
348 	/+ TODO: Remove need for these switch cases if this can be fixed: +/
349 	// http://forum.dlang.org/post/pknonazfniihvpicxbld@forum.dlang.org
350 	import std.range : assumeSorted;
351 	static if (Rs.length == 2)
352 	{
353 		import core.lifetime : move;
354 		return assumeMoveableSorted(SetIntersectionFast!(less,
355 														 preferredSearchPolicy,
356 														 Rs)(move(ranges[0]), /+ TODO: remove `move` when compiler does it for us +/
357 															 move(ranges[1]))); /+ TODO: remove `move` when compiler does it for us +/
358 	}
359 	else
360 	{
361 		import std.functional : forward;
362 		return assumeMoveableSorted(SetIntersectionFast!(less,
363 														 preferredSearchPolicy,
364 														 Rs)(forward!ranges)); /+ TODO: remove `forward` when compiler does it for us +/
365 	}
366 }
367 
368 @safe unittest {
369 	import std.algorithm.comparison : equal;
370 	import std.algorithm.sorting : sort;
371 	import std.algorithm.setops : setIntersection;
372 	import nxt.random_ex : randInPlaceWithElementRange;
373 	import nxt.container.dynamic_array : DynamicArray;
374 	import nxt.algorithm_ex : collect;
375 
376 	alias E = ulong;
377 	alias A = DynamicArray!E;
378 
379 	auto a0 = A();
380 	auto a1 = A(1);
381 
382 	enum less = "a < b";
383 
384 	auto s0 = setIntersectionFast!(less)(a0[], a0[]);
385 	assert(s0.equal(a0[]));
386 
387 	auto s1 = setIntersectionFast!(less)(a1[], a1[]);
388 	assert(s1.equal(a1[]));
389 
390 	immutable smallTestLength = 1000;
391 	immutable factor = 12; // this is the magical limit on my laptop when performance of `upperBound` beats standard implementation
392 	immutable largeTestLength = factor*smallTestLength;
393 	E elementLow = 0;
394 	E elementHigh = 10_000_000;
395 	A x;
396 	x.length = smallTestLength;
397 	A y;
398 	y.length = largeTestLength;
399 
400 	x[].randInPlaceWithElementRange(elementLow, elementHigh);
401 	y[].randInPlaceWithElementRange(elementLow, elementHigh);
402 
403 	sort(x[]);
404 	sort(y[]);
405 
406 	// associative
407 	assert(equal(setIntersectionFast!(less)(x[], y[]),
408 				 setIntersectionFast!(less)(y[], x[])));
409 
410 	// same as current
411 	assert(equal(setIntersection!(less)(x[], y[]),
412 				 setIntersectionFast!(less)(x[], y[])));
413 
414 	void testSetIntersection()
415 	{
416 		auto z = setIntersection!(less)(x[], y[]).collect!A;
417 	}
418 
419 	void testSetIntersectionNew()
420 	{
421 		auto z = setIntersectionFast!(less)(x[], y[]).collect!A;
422 	}
423 
424 	import std.datetime.stopwatch : benchmark;
425 	import core.time : Duration;
426 	immutable testCount = 10;
427 	auto r = benchmark!(testSetIntersection,
428 						testSetIntersectionNew)(testCount);
429 	version (show)
430 	{
431 		import std.stdio : writeln;
432 		import std.conv : to;
433 		writeln("old testSetIntersection: ", to!Duration(r[0]));
434 		writeln("new testSetIntersection: ", to!Duration(r[1]));
435 	}
436 }
437 
438 pure nothrow @safe unittest {
439 	import std.algorithm.comparison : equal;
440 	enum less = "a < b";
441 	auto si = setIntersectionFast!(less)([1, 2, 3],
442 										 [1, 2, 3]);
443 	const sic = si.save();
444 	assert(si.equal([1, 2, 3]));
445 }
446 
447 /+ TODO: remove this `MoveableSortedRange` and replace with Phobos' `SortedRange` in this buffer +/
448 struct MoveableSortedRange(Range, alias pred = "a < b")
449 if (isInputRange!Range)
450 {
451 	import std.functional : binaryFun;
452 
453 	private alias predFun = binaryFun!pred;
454 	private bool geq(L, R)(L lhs, R rhs)
455 	{
456 		return !predFun(lhs, rhs);
457 	}
458 	private bool gt(L, R)(L lhs, R rhs)
459 	{
460 		return predFun(rhs, lhs);
461 	}
462 	private Range _input;
463 
464 	// Undocummented because a clearer way to invoke is by calling
465 	// assumeSorted.
466 	this(Range input)
467 	out
468 	{
469 		// moved out of the body as a workaround for Issue 12661
470 		dbgVerifySorted();
471 	}
472 	do
473 	{
474 		import core.lifetime : move;
475 		this._input = move(input); // TODO
476 	}
477 
478 	// Assertion only.
479 	private void dbgVerifySorted()
480 	{
481 		if (!__ctfe)
482 		debug
483 		{
484 			static if (isRandomAccessRange!Range && hasLength!Range)
485 			{
486 				import core.bitop : bsr;
487 				import std.algorithm.sorting : isSorted;
488 
489 				// Check the sortedness of the input
490 				if (this._input.length < 2) return;
491 
492 				immutable size_t msb = bsr(this._input.length) + 1;
493 				assert(msb > 0 && msb <= this._input.length);
494 				immutable step = this._input.length / msb;
495 				auto st = stride(this._input, step);
496 
497 				assert(isSorted!pred(st), "Range is not sorted");
498 			}
499 		}
500 	}
501 
502 	/// Range primitives.
503 	@property bool empty()			 //const
504 	{
505 		return this._input.empty;
506 	}
507 
508 	/// Ditto
509 	static if (isForwardRange!Range)
510 	@property auto save()
511 	{
512 		// Avoid the constructor
513 		typeof(this) result = this;
514 		result._input = _input.save;
515 		return result;
516 	}
517 
518 	/// Ditto
519 	@property auto ref front()
520 	{
521 		return _input.front;
522 	}
523 
524 	/// Ditto
525 	void popFront()
526 	{
527 		_input.popFront();
528 	}
529 
530 	/// Ditto
531 	static if (isBidirectionalRange!Range)
532 	{
533 		@property auto ref back()
534 		{
535 			return _input.back;
536 		}
537 
538 		/// Ditto
539 		void popBack()
540 		{
541 			_input.popBack();
542 		}
543 	}
544 
545 	/// Ditto
546 	static if (isRandomAccessRange!Range)
547 		auto ref opIndex(size_t i)
548 		{
549 			return _input[i];
550 		}
551 
552 	/// Ditto
553 	static if (hasSlicing!Range)
554 		auto opSlice(size_t a, size_t b)
555 		{
556 			assert(
557 				a <= b,
558 				"Attempting to slice a SortedRange with a larger first argument than the second."
559 			);
560 			typeof(this) result = this;
561 			result._input = _input[a .. b];// skip checking
562 			return result;
563 		}
564 
565 	/// Ditto
566 	static if (hasLength!Range)
567 	{
568 		@property size_t length()		  //const
569 		{
570 			return _input.length;
571 		}
572 		alias opDollar = length;
573 	}
574 
575 /**
576    Releases the controlled range and returns it.
577 */
578 	auto release()
579 	{
580 		import core.lifetime : move;
581 		return move(_input);
582 	}
583 
584 	// Assuming a predicate "test" that returns 0 for a left portion
585 	// of the range and then 1 for the rest, returns the index at
586 	// which the first 1 appears. Used internally by the search routines.
587 	private size_t getTransitionIndex(SearchPolicy sp, alias test, V)(V v)
588 	if (sp == SearchPolicy.binarySearch && isRandomAccessRange!Range && hasLength!Range)
589 	{
590 		size_t first = 0, count = _input.length;
591 		while (count > 0)
592 		{
593 			immutable step = count / 2, it = first + step;
594 			if (!test(_input[it], v))
595 			{
596 				first = it + 1;
597 				count -= step + 1;
598 			}
599 			else
600 				count = step;
601 		}
602 		return first;
603 	}
604 
605 	// Specialization for trot and gallop
606 	private size_t getTransitionIndex(SearchPolicy sp, alias test, V)(V v)
607 	if ((sp == SearchPolicy.trot || sp == SearchPolicy.gallop)
608 		&& isRandomAccessRange!Range)
609 	{
610 		if (empty || test(front, v)) return 0;
611 		immutable count = length;
612 		if (count == 1) return 1;
613 		size_t below = 0, above = 1, step = 2;
614 		while (!test(_input[above], v))
615 		{
616 			// Still too small, update below and increase gait
617 			below = above;
618 			immutable next = above + step;
619 			if (next >= count)
620 			{
621 				// Overshot - the next step took us beyond the end. So
622 				// now adjust next and simply exit the loop to do the
623 				// binary search thingie.
624 				above = count;
625 				break;
626 			}
627 			// Still in business, increase step and continue
628 			above = next;
629 			static if (sp == SearchPolicy.trot)
630 				++step;
631 			else
632 				step <<= 1;
633 		}
634 		return below + this[below .. above].getTransitionIndex!(
635 			SearchPolicy.binarySearch, test, V)(v);
636 	}
637 
638 	// Specialization for trotBackwards and gallopBackwards
639 	private size_t getTransitionIndex(SearchPolicy sp, alias test, V)(V v)
640 	if ((sp == SearchPolicy.trotBackwards || sp == SearchPolicy.gallopBackwards)
641 		&& isRandomAccessRange!Range)
642 	{
643 		immutable count = length;
644 		if (empty || !test(back, v)) return count;
645 		if (count == 1) return 0;
646 		size_t below = count - 2, above = count - 1, step = 2;
647 		while (test(_input[below], v))
648 		{
649 			// Still too large, update above and increase gait
650 			above = below;
651 			if (below < step)
652 			{
653 				// Overshot - the next step took us beyond the end. So
654 				// now adjust next and simply fall through to do the
655 				// binary search thingie.
656 				below = 0;
657 				break;
658 			}
659 			// Still in business, increase step and continue
660 			below -= step;
661 			static if (sp == SearchPolicy.trot)
662 				++step;
663 			else
664 				step <<= 1;
665 		}
666 		return below + this[below .. above].getTransitionIndex!(
667 			SearchPolicy.binarySearch, test, V)(v);
668 	}
669 
670 // lowerBound
671 /**
672    This function uses a search with policy $(D sp) to find the
673    largest left subrange on which $(D pred(x, value)) is `true` for
674    all $(D x) (e.g., if $(D pred) is "less than", returns the portion of
675    the range with elements strictly smaller than `value`). The search
676    schedule and its complexity are documented in
677    $(LREF SearchPolicy).  See_Also: STL's
678    $(HTTP sgi.com/tech/stl/lower_bound.html, lower_bound).
679 */
680 	auto lowerBound(SearchPolicy sp = SearchPolicy.binarySearch, V)(V value)
681 	if (isTwoWayCompatible!(predFun, ElementType!Range, V)
682 		 && hasSlicing!Range)
683 	{
684 		return this[0 .. getTransitionIndex!(sp, geq)(value)];
685 	}
686 
687 // upperBound
688 /**
689 This function searches with policy $(D sp) to find the largest right
690 subrange on which $(D pred(value, x)) is `true` for all $(D x)
691 (e.g., if $(D pred) is "less than", returns the portion of the range
692 with elements strictly greater than `value`). The search schedule
693 and its complexity are documented in $(LREF SearchPolicy).
694 
695 For ranges that do not offer random access, $(D SearchPolicy.linear)
696 is the only policy allowed (and it must be specified explicitly lest it exposes
697 user code to unexpected inefficiencies). For random-access searches, all
698 policies are allowed, and $(D SearchPolicy.binarySearch) is the default.
699 
700 See_Also: STL's $(HTTP sgi.com/tech/stl/lower_bound.html,upper_bound).
701 */
702 	auto upperBound(SearchPolicy sp = SearchPolicy.binarySearch, V)(V value)
703 	if (isTwoWayCompatible!(predFun, ElementType!Range, V))
704 	{
705 		static assert(hasSlicing!Range || sp == SearchPolicy.linear,
706 			"Specify SearchPolicy.linear explicitly for "
707 			~ typeof(this).stringof);
708 		static if (sp == SearchPolicy.linear)
709 		{
710 			for (; !_input.empty && !predFun(value, _input.front);
711 				 _input.popFront())
712 			{
713 			}
714 			return this;
715 		}
716 		else
717 		{
718 			return this[getTransitionIndex!(sp, gt)(value) .. length];
719 		}
720 	}
721 
722 
723 // equalRange
724 /**
725    Returns the subrange containing all elements $(D e) for which both $(D
726    pred(e, value)) and $(D pred(value, e)) evaluate to $(D false) (e.g.,
727    if $(D pred) is "less than", returns the portion of the range with
728    elements equal to `value`). Uses a classic binary search with
729    interval halving until it finds a value that satisfies the condition,
730    then uses $(D SearchPolicy.gallopBackwards) to find the left boundary
731    and $(D SearchPolicy.gallop) to find the right boundary. These
732    policies are justified by the fact that the two boundaries are likely
733    to be near the first found value (i.e., equal ranges are relatively
734    small). Completes the entire search in $(BIGOH log(n)) time. See also
735    STL's $(HTTP sgi.com/tech/stl/equal_range.html, equal_range).
736 */
737 	auto equalRange(V)(V value)
738 	if (isTwoWayCompatible!(predFun, ElementType!Range, V)
739 		&& isRandomAccessRange!Range)
740 	{
741 		size_t first = 0, count = _input.length;
742 		while (count > 0)
743 		{
744 			immutable step = count / 2;
745 			auto it = first + step;
746 			if (predFun(_input[it], value))
747 			{
748 				// Less than value, bump left bound up
749 				first = it + 1;
750 				count -= step + 1;
751 			}
752 			else if (predFun(value, _input[it]))
753 			{
754 				// Greater than value, chop count
755 				count = step;
756 			}
757 			else
758 			{
759 				// Equal to value, do binary searches in the
760 				// leftover portions
761 				// Gallop towards the left end as it's likely nearby
762 				immutable left = first
763 					+ this[first .. it]
764 					.lowerBound!(SearchPolicy.gallopBackwards)(value).length;
765 				first += count;
766 				// Gallop towards the right end as it's likely nearby
767 				immutable right = first
768 					- this[it + 1 .. first]
769 					.upperBound!(SearchPolicy.gallop)(value).length;
770 				return this[left .. right];
771 			}
772 		}
773 		return this.init;
774 	}
775 
776 // trisect
777 /**
778 Returns a tuple $(D r) such that $(D r[0]) is the same as the result
779 of $(D lowerBound(value)), $(D r[1]) is the same as the result of $(D
780 equalRange(value)), and $(D r[2]) is the same as the result of $(D
781 upperBound(value)). The call is faster than computing all three
782 separately. Uses a search schedule similar to $(D
783 equalRange). Completes the entire search in $(BIGOH log(n)) time.
784 */
785 	auto trisect(V)(V value)
786 	if (isTwoWayCompatible!(predFun, ElementType!Range, V)
787 		&& isRandomAccessRange!Range && hasLength!Range)
788 	{
789 		import std.typecons : tuple;
790 		size_t first = 0, count = _input.length;
791 		while (count > 0)
792 		{
793 			immutable step = count / 2;
794 			auto it = first + step;
795 			if (predFun(_input[it], value))
796 			{
797 				// Less than value, bump left bound up
798 				first = it + 1;
799 				count -= step + 1;
800 			}
801 			else if (predFun(value, _input[it]))
802 			{
803 				// Greater than value, chop count
804 				count = step;
805 			}
806 			else
807 			{
808 				// Equal to value, do binary searches in the
809 				// leftover portions
810 				// Gallop towards the left end as it's likely nearby
811 				immutable left = first
812 					+ this[first .. it]
813 					.lowerBound!(SearchPolicy.gallopBackwards)(value).length;
814 				first += count;
815 				// Gallop towards the right end as it's likely nearby
816 				immutable right = first
817 					- this[it + 1 .. first]
818 					.upperBound!(SearchPolicy.gallop)(value).length;
819 				return tuple(this[0 .. left], this[left .. right],
820 						this[right .. length]);
821 			}
822 		}
823 		// No equal element was found
824 		return tuple(this[0 .. first], this.init, this[first .. length]);
825 	}
826 
827 // contains
828 /**
829 Returns `true` if and only if `value` can be found in $(D
830 range), which is assumed to be sorted. Performs $(BIGOH log(r.length))
831 evaluations of $(D pred). See_Also: STL's $(HTTP
832 sgi.com/tech/stl/binary_search.html, binary_search).
833  */
834 
835 	bool contains(V)(V value)
836 	if (isRandomAccessRange!Range)
837 	{
838 		if (empty) return false;
839 		immutable i = getTransitionIndex!(SearchPolicy.binarySearch, geq)(value);
840 		if (i >= length) return false;
841 		return !predFun(value, _input[i]);
842 	}
843 
844 // groupBy
845 /**
846 Returns a range of subranges of elements that are equivalent according to the
847 sorting relation.
848  */
849 	auto groupBy()()
850 	{
851 		import std.algorithm.iteration : chunkBy;
852 		return _input.chunkBy!((a, b) => !predFun(a, b) && !predFun(b, a));
853 	}
854 }