94 changes: 51 additions & 43 deletions std/algorithm/searching.d
View file
Original file line number Diff line number Diff line change
Expand Up @@ -321,6 +321,7 @@ is ignored.
}

public:
///
this(Range needle)
{
if (!needle.length) return;
Expand All @@ -347,6 +348,7 @@ public:
}
}

///
Range beFound(Range haystack)
{
import std.algorithm.comparison : max;
Expand All @@ -368,11 +370,13 @@ public:
return haystack[$ .. $];
}

///
@property size_t length()
{
return needle.length;
}

///
alias opDollar = length;
}

Expand Down Expand Up @@ -1765,8 +1769,7 @@ if (isForwardRange!R1 && isForwardRange!R2
assert(equal(r, SList!int(2, 5, 7, 3)[]));
}

// Specialization for searching a random-access range for a
// bidirectional range
/// ditto
R1 find(alias pred = "a == b", R1, R2)(R1 haystack, R2 needle)
if (isRandomAccessRange!R1 && isBidirectionalRange!R2
&& is(typeof(binaryFun!pred(haystack.front, needle.front)) : bool))
Expand All @@ -1775,9 +1778,7 @@ if (isRandomAccessRange!R1 && isBidirectionalRange!R2
const needleLength = walkLength(needle.save);
if (needleLength > haystack.length)
{
// @@@BUG@@@
//return haystack[$ .. $];
return haystack[haystack.length .. haystack.length];
return haystack[$ .. $];
}
// @@@BUG@@@
// auto needleBack = moveBack(needle);
Expand Down Expand Up @@ -1837,8 +1838,7 @@ if (isRandomAccessRange!R1 && isBidirectionalRange!R2
//assert(find!"a == b"("abc", "bc").length == 2);
}

// Leftover specialization: searching a random-access range for a
// non-bidirectional forward range
/// ditto
R1 find(alias pred = "a == b", R1, R2)(R1 haystack, R2 needle)
if (isRandomAccessRange!R1 && isForwardRange!R2 && !isBidirectionalRange!R2 &&
is(typeof(binaryFun!pred(haystack.front, needle.front)) : bool))
Expand Down Expand Up @@ -3850,6 +3850,43 @@ enum OpenRight
yes /// Interval is open to the right (last element is not included)
}

/**
Lazily iterates $(D range) _until the element $(D e) for which
$(D pred(e, sentinel)) is true.
Params:
pred = Predicate to determine when to stop.
range = The $(XREF_PACK_NAMED _range,primitives,isInputRange,input _range)
to iterate over.
sentinel = The element to stop at.
openRight = Determines whether the element for which the given predicate is
true should be included in the resulting range ($(D OpenRight.no)), or
not ($(D OpenRight.yes)).
Returns:
An $(XREF_PACK_NAMED _range,primitives,isInputRange,input _range) that
iterates over the original range's elements, but ends when the specified
predicate becomes true. If the original range is a
$(XREF_PACK_NAMED _range,primitives,isForwardRange,forward _range) or
higher, this range will be a forward range.
*/
Until!(pred, Range, Sentinel)
until(alias pred = "a == b", Range, Sentinel)
(Range range, Sentinel sentinel, OpenRight openRight = OpenRight.yes)
if (!is(Sentinel == OpenRight))
{
return typeof(return)(range, sentinel, openRight);
}

/// Ditto
Until!(pred, Range, void)
until(alias pred, Range)
(Range range, OpenRight openRight = OpenRight.yes)
{
return typeof(return)(range, openRight);
}

/// ditto
struct Until(alias pred, Range, Sentinel) if (isInputRange!Range)
{
private Range _input;
Expand All @@ -3865,6 +3902,7 @@ struct Until(alias pred, Range, Sentinel) if (isInputRange!Range)
bool _done;

static if (!is(Sentinel == void))
///
this(Range input, Sentinel sentinel,
OpenRight openRight = OpenRight.yes)
{
Expand All @@ -3874,18 +3912,21 @@ struct Until(alias pred, Range, Sentinel) if (isInputRange!Range)
_done = _input.empty || openRight && predSatisfied();
}
else
///
this(Range input, OpenRight openRight = OpenRight.yes)
{
_input = input;
_openRight = openRight;
_done = _input.empty || openRight && predSatisfied();
}

///
@property bool empty()
{
return _done;
}

///
@property auto ref front()
{
assert(!empty);
Expand All @@ -3900,6 +3941,7 @@ struct Until(alias pred, Range, Sentinel) if (isInputRange!Range)
return cast(bool) startsWith!pred(_input, _sentinel);
}

///
void popFront()
{
assert(!empty);
Expand All @@ -3919,6 +3961,7 @@ struct Until(alias pred, Range, Sentinel) if (isInputRange!Range)
static if (isForwardRange!Range)
{
static if (!is(Sentinel == void))
///
@property Until save()
{
Until result = this;
Expand All @@ -3929,6 +3972,7 @@ struct Until(alias pred, Range, Sentinel) if (isInputRange!Range)
return result;
}
else
///
@property Until save()
{
Until result = this;
Expand All @@ -3940,42 +3984,6 @@ struct Until(alias pred, Range, Sentinel) if (isInputRange!Range)
}
}

/**
Lazily iterates $(D range) _until the element $(D e) for which
$(D pred(e, sentinel)) is true.
Params:
pred = Predicate to determine when to stop.
range = The $(XREF_PACK_NAMED _range,primitives,isInputRange,input _range)
to iterate over.
sentinel = The element to stop at.
openRight = Determines whether the element for which the given predicate is
true should be included in the resulting range ($(D OpenRight.no)), or
not ($(D OpenRight.yes)).
Returns:
An $(XREF_PACK_NAMED _range,primitives,isInputRange,input _range) that
iterates over the original range's elements, but ends when the specified
predicate becomes true. If the original range is a
$(XREF_PACK_NAMED _range,primitives,isForwardRange,forward _range) or
higher, this range will be a forward range.
*/
Until!(pred, Range, Sentinel)
until(alias pred = "a == b", Range, Sentinel)
(Range range, Sentinel sentinel, OpenRight openRight = OpenRight.yes)
if (!is(Sentinel == OpenRight))
{
return typeof(return)(range, sentinel, openRight);
}

/// Ditto
Until!(pred, Range, void)
until(alias pred, Range)
(Range range, OpenRight openRight = OpenRight.yes)
{
return typeof(return)(range, openRight);
}

///
@safe unittest
{
Expand Down
28 changes: 28 additions & 0 deletions std/algorithm/setops.d
View file
Original file line number Diff line number Diff line change
Expand Up @@ -788,6 +788,8 @@ struct NWayUnion(alias less, RangeOfRanges)
private alias ElementType = .ElementType!(.ElementType!RangeOfRanges);
private alias comp = binaryFun!less;
private RangeOfRanges _ror;

///
static bool compFront(.ElementType!RangeOfRanges a,
.ElementType!RangeOfRanges b)
{
Expand All @@ -796,6 +798,7 @@ struct NWayUnion(alias less, RangeOfRanges)
}
BinaryHeap!(RangeOfRanges, compFront) _heap;

///
this(RangeOfRanges ror)
{
import std.algorithm.mutation : remove, SwapStrategy;
Expand All @@ -807,13 +810,16 @@ struct NWayUnion(alias less, RangeOfRanges)
_heap.acquire(_ror);
}

///
@property bool empty() { return _ror.empty; }

///
@property auto ref front()
{
return _heap.front.front;
}

///
void popFront()
{
_heap.removeFront();
Expand Down Expand Up @@ -900,6 +906,7 @@ private:
}

public:
///
this(R1 r1, R2 r2)
{
this.r1 = r1;
Expand All @@ -908,12 +915,14 @@ public:
adjustPosition();
}

///
void popFront()
{
r1.popFront();
adjustPosition();
}

///
@property auto ref front()
{
assert(!empty);
Expand All @@ -922,6 +931,7 @@ public:

static if (isForwardRange!R1 && isForwardRange!R2)
{
///
@property typeof(this) save()
{
auto ret = this;
Expand All @@ -931,6 +941,7 @@ public:
}
}

///
@property bool empty() { return r1.empty; }
}

Expand Down Expand Up @@ -1010,13 +1021,15 @@ private:
}

public:
///
this(Rs input)
{
this._input = input;
// position to the first element
adjustPosition();
}

///
@property bool empty()
{
foreach (ref r; _input)
Expand All @@ -1026,6 +1039,7 @@ public:
return false;
}

///
void popFront()
{
assert(!empty);
Expand All @@ -1042,6 +1056,7 @@ public:
adjustPosition();
}

///
@property ElementType front()
{
assert(!empty);
Expand All @@ -1050,6 +1065,7 @@ public:

static if (allSatisfy!(isForwardRange, Rs))
{
///
@property SetIntersection save()
{
auto ret = this;
Expand Down Expand Up @@ -1158,6 +1174,7 @@ private:
}

public:
///
this(R1 r1, R2 r2)
{
this.r1 = r1;
Expand All @@ -1166,6 +1183,7 @@ public:
adjustPosition();
}

///
void popFront()
{
assert(!empty);
Expand All @@ -1187,6 +1205,7 @@ public:
adjustPosition();
}

///
@property auto ref front()
{
assert(!empty);
Expand All @@ -1197,6 +1216,7 @@ public:

static if (isForwardRange!R1 && isForwardRange!R2)
{
///
@property typeof(this) save()
{
auto ret = this;
Expand All @@ -1206,8 +1226,10 @@ public:
}
}

///
ref auto opSlice() { return this; }

///
@property bool empty() { return r1.empty && r2.empty; }
}

Expand Down Expand Up @@ -1300,17 +1322,20 @@ public:
static assert(!is(CommonType!(staticMap!(.ElementType, Rs)) == void),
typeof(this).stringof ~ ": incompatible element types.");

///
this(Rs rs)
{
this._r = rs;
adjustPosition();
}

///
@property bool empty()
{
return _crt == _crt.max;
}

///
void popFront()
{
// Assumes _crt is correct
Expand All @@ -1327,6 +1352,7 @@ public:
assert(false);
}

///
@property auto ref ElementType front()
{
assert(!empty);
Expand All @@ -1342,6 +1368,7 @@ public:

static if (allSatisfy!(isForwardRange, Rs))
{
///
@property auto save()
{
auto ret = this;
Expand All @@ -1355,6 +1382,7 @@ public:

static if (allSatisfy!(hasLength, Rs))
{
///
@property size_t length()
{
size_t result;
Expand Down