1 
// Written in the D programming language. 

2 


3 
/** 

4 
Implements algorithms oriented mainly towards processing of 

5 
sequences. Some functions are semantic equivalents or supersets of 

6 
those found in the $(D $(LESS)_algorithm$(GREATER)) header in $(WEB 

7 
sgi.com/tech/stl/, Alexander Stepanov's Standard Template Library) for 

8 
C++. 

9 


10 
Note: 

11 


12 
Many functions in this module are parameterized with a function or a 

13 
$(GLOSSARY predicate). The predicate may be passed either as a 

14 
function name, a delegate name, a $(GLOSSARY functor) name, or a 

15 
compiletime string. The string may consist of $(B any) legal D 

16 
expression that uses the symbol $(D a) (for unary functions) or the 

17 
symbols $(D a) and $(D b) (for binary functions). These names will NOT 

18 
interfere with other homonym symbols in user code because they are 

19 
evaluated in a different context. The default for all binary 

20 
comparison predicates is $(D "a == b") for unordered operations and 

21 
$(D "a < b") for ordered operations. 

22 


23 
Example: 

24 


25 
 

26 
int[] a = ...; 

27 
static bool greater(int a, int b) 

28 
{ 

29 
return a > b; 

30 
} 

31 
sort!(greater)(a); // predicate as alias 

32 
sort!("a > b")(a); // predicate as string 

33 
// (no ambiguity with array name) 

34 
sort(a); // no predicate, "a < b" is implicit 

35 
 

36 


37 
Macros: 

38 
WIKI = Phobos/StdAlgorithm 

39 


40 
Copyright: Andrei Alexandrescu 2008. 

41 


42 
License: $(WEB boost.org/LICENSE_1_0.txt, Boost License 1.0). 

43 


44 
Authors: $(WEB erdani.com, Andrei Alexandrescu) 

45 
*/ 

46 
module std.algorithm; 

47 
//debug = std_algorithm; 

48 


49 
import std.c.string; 

50 
import std.array, std.container, std.conv, std.exception, 

51 
std.functional, std.math, std.metastrings, std.range, std.string, 

52 
std.traits, std.typecons, std.typetuple, std.stdio; 

53 


54 
version(unittest) 

55 
{ 

56 
import std.random, std.stdio, std.string; 

57 
mixin(dummyRanges); 

58 
} 

59 


60 
/** 

61 
Implements the homonym function (also known as $(D transform)) present 

62 
in many languages of functional flavor. The call $(D map!(fun)(range)) 

63 
returns a range of which elements are obtained by applying $(D fun(x)) 

64 
left to right for all $(D x) in $(D range). The original ranges are 

65 
not changed. Evaluation is done lazily. The range returned by $(D map) 

66 
caches the last value such that evaluating $(D front) multiple times 

67 
does not result in multiple calls to $(D fun). 

68 


69 
Example: 

70 
 

71 
int[] arr1 = [ 1, 2, 3, 4 ]; 

72 
int[] arr2 = [ 5, 6 ]; 

73 
auto squares = map!("a * a")(chain(arr1, arr2)); 

74 
assert(equal(squares, [ 1, 4, 9, 16, 25, 36 ])); 

75 
 

76 


77 
Multiple functions can be passed to $(D map). In that case, the 

78 
element type of $(D map) is a tuple containing one element for each 

79 
function. 

80 


81 
Example: 

82 


83 
 

84 
auto arr1 = [ 1, 2, 3, 4 ]; 

85 
foreach (e; map!("a + a", "a * a")(arr1)) 

86 
{ 

87 
writeln(e[0], " ", e[1]); 

88 
} 

89 
 

90 


91 
You may alias $(D map) with some function(s) to a symbol and use it 

92 
separately: 

93 


94 
 

95 
alias map!(to!string) stringize; 

96 
assert(equal(stringize([ 1, 2, 3, 4 ]), [ "1", "2", "3", "4" ])); 

97 
 

98 
*/ 

99 
template map(fun...) 

100 
{ 

101 
auto map(Range)(Range r) 

102 
{ 

103 
static if (fun.length > 1) 

104 
{ 

105 
return Map!(adjoin!(staticMap!(unaryFun, fun)), Range)(r); 

106 
} 

107 
else 

108 
{ 

109 
return Map!(unaryFun!fun, Range)(r); 

110 
} 

111 
} 

112 
} 

113 


114 
struct Map(alias fun, Range) if (isInputRange!(Unqual!Range)) 

115 
{ 

116 
alias Unqual!Range R; 

117 
alias fun _fun; 

118 
// Uncomment this to reveal a @@@BUG@@@ in the compiler 

119 
//alias typeof(fun(.ElementType!R.init)) ElementType; 

120 
alias typeof({ return fun(.ElementType!R.init); }()) ElementType; 

121 
R _input; 

122 


123 
static if (isBidirectionalRange!(R)) 

124 
{ 

125 
@property ElementType back() 

126 
{ 

127 
return _fun(_input.back); 

128 
} 

129 


130 
void popBack() 

131 
{ 

132 
_input.popBack(); 

133 
} 

134 
} 

135 


136 
this(R input) 

137 
{ 

138 
_input = input; 

139 
} 

140 


141 
static if (isInfinite!R) 

142 
{ 

143 
// Propagate infiniteness. 

144 
enum bool empty = false; 

145 
} 

146 
else 

147 
{ 

148 
@property bool empty() 

149 
{ 

150 
return _input.empty; 

151 
} 

152 
} 

153 


154 
void popFront() 

155 
{ 

156 
_input.popFront(); 

157 
} 

158 


159 
@property ElementType front() 

160 
{ 

161 
return _fun(_input.front); 

162 
} 

163 


164 
static if (isRandomAccessRange!R) 

165 
{ 

166 
ElementType opIndex(size_t index) 

167 
{ 

168 
return _fun(_input[index]); 

169 
} 

170 
} 

171 


172 
// hasLength is busted, Bug 2873 

173 
static if (is(typeof(_input.length) : size_t) 

174 
 is(typeof(_input.length()) : size_t)) 

175 
{ 

176 
@property size_t length() 

177 
{ 

178 
return _input.length; 

179 
} 

180 
} 

181 


182 
static if (hasSlicing!(R)) 

183 
{ 

184 
typeof(this) opSlice(size_t lowerBound, size_t upperBound) 

185 
{ 

186 
return typeof(this)(_input[lowerBound..upperBound]); 

187 
} 

188 
} 

189 


190 
static if (isForwardRange!R) 

191 
@property Map save() 

192 
{ 

193 
auto result = this; 

194 
result._input = result._input.save; 

195 
return result; 

196 
} 

197 
} 

198 


199 
unittest 

200 
{ 

201 
debug(std_algorithm) scope(success) 

202 
writeln("unittest @", __FILE__, ":", __LINE__, " done."); 

203 
alias map!(to!string) stringize; 

204 
assert(equal(stringize([ 1, 2, 3, 4 ]), [ "1", "2", "3", "4" ])); 

205 
uint counter; 

206 
alias map!((a) { return counter++; }) count; 

207 
assert(equal(count([ 10, 2, 30, 4 ]), [ 0, 1, 2, 3 ])); 

208 
counter = 0; 

209 
adjoin!((a) { return counter++; }, (a) { return counter++; })(1); 

210 
alias map!((a) { return counter++; }, (a) { return counter++; }) countAndSquare; 

211 
//assert(equal(countAndSquare([ 10, 2 ]), [ tuple(0u, 100), tuple(1u, 4) ])); 

212 
} 

213 


214 
unittest 

215 
{ 

216 
debug(std_algorithm) scope(success) 

217 
writeln("unittest @", __FILE__, ":", __LINE__, " done."); 

218 
int[] arr1 = [ 1, 2, 3, 4 ]; 

219 
const int[] arr1Const = arr1; 

220 
int[] arr2 = [ 5, 6 ]; 

221 
auto squares = map!("a * a")(arr1Const); 

222 
assert(equal(squares, [ 1, 4, 9, 16 ][])); 

223 
assert(equal(map!("a * a")(chain(arr1, arr2)), [ 1, 4, 9, 16, 25, 36 ][])); 

224 


225 
// Test the caching stuff. 

226 
assert(squares.back == 16); 

227 
auto squares2 = squares.save; 

228 
assert(squares2.back == 16); 

229 


230 
assert(squares2.front == 1); 

231 
squares2.popFront; 

232 
assert(squares2.front == 4); 

233 
squares2.popBack; 

234 
assert(squares2.front == 4); 

235 
assert(squares2.back == 9); 

236 


237 
assert(equal(map!("a * a")(chain(arr1, arr2)), [ 1, 4, 9, 16, 25, 36 ][])); 

238 


239 
uint i; 

240 
foreach (e; map!("a", "a * a")(arr1)) 

241 
{ 

242 
assert(e[0] == ++i); 

243 
assert(e[1] == i * i); 

244 
} 

245 


246 
// Test length. 

247 
assert(squares.length == 4); 

248 
assert(map!"a * a"(chain(arr1, arr2)).length == 6); 

249 


250 
// Test indexing. 

251 
assert(squares[0] == 1); 

252 
assert(squares[1] == 4); 

253 
assert(squares[2] == 9); 

254 
assert(squares[3] == 16); 

255 


256 
// Test slicing. 

257 
auto squareSlice = squares[1..squares.length  1]; 

258 
assert(equal(squareSlice, [4, 9][])); 

259 
assert(squareSlice.back == 9); 

260 
assert(squareSlice[1] == 9); 

261 


262 
// Test on a forward range to make sure it compiles when all the fancy 

263 
// stuff is disabled. 

264 
auto fibsSquares = map!"a * a"(recurrence!("a[n1] + a[n2]")(1, 1)); 

265 
assert(fibsSquares.front == 1); 

266 
fibsSquares.popFront; 

267 
fibsSquares.popFront; 

268 
assert(fibsSquares.front == 4); 

269 
fibsSquares.popFront; 

270 
assert(fibsSquares.front == 9); 

271 


272 
auto repeatMap = map!"a"(repeat(1)); 

273 
static assert(isInfinite!(typeof(repeatMap))); 

274 


275 
auto intRange = map!"a"([1,2,3]); 

276 
static assert(isRandomAccessRange!(typeof(intRange))); 

277 


278 
foreach(DummyType; AllDummyRanges) 

279 
{ 

280 
DummyType d; 

281 
auto m = map!"a * a"(d); 

282 


283 
static assert(propagatesRangeType!(typeof(m), DummyType)); 

284 
assert(equal(m, [1,4,9,16,25,36,49,64,81,100])); 

285 
} 

286 
} 

287 


288 
// reduce 

289 
/** 

290 
Implements the homonym function (also known as $(D accumulate), $(D 

291 
compress), $(D inject), or $(D foldl)) present in various programming 

292 
languages of functional flavor. The call $(D reduce!(fun)(seed, 

293 
range)) first assigns $(D seed) to an internal variable $(D result), 

294 
also called the accumulator. Then, for each element $(D x) in $(D 

295 
range), $(D result = fun(result, x)) gets evaluated. Finally, $(D 

296 
result) is returned. The oneargument version $(D reduce!(fun)(range)) 

297 
works similarly, but it uses the first element of the range as the 

298 
seed (the range must be nonempty). 

299 


300 
Many aggregate range operations turn out to be solved with $(D reduce) 

301 
quickly and easily. The example below illustrates $(D reduce)'s 

302 
remarkable power and flexibility. 

303 


304 
Example: 

305 
 

306 
int[] arr = [ 1, 2, 3, 4, 5 ]; 

307 
// Sum all elements 

308 
auto sum = reduce!("a + b")(0, arr); 

309 
assert(sum == 15); 

310 


311 
// Compute the maximum of all elements 

312 
auto largest = reduce!(max)(arr); 

313 
assert(largest == 5); 

314 


315 
// Compute the number of odd elements 

316 
auto odds = reduce!("a + (b & 1)")(0, arr); 

317 
assert(odds == 3); 

318 


319 
// Compute the sum of squares 

320 
auto ssquares = reduce!("a + b * b")(0, arr); 

321 
assert(ssquares == 55); 

322 


323 
// Chain multiple ranges into seed 

324 
int[] a = [ 3, 4 ]; 

325 
int[] b = [ 100 ]; 

326 
auto r = reduce!("a + b")(chain(a, b)); 

327 
assert(r == 107); 

328 


329 
// Mixing convertible types is fair game, too 

330 
double[] c = [ 2.5, 3.0 ]; 

331 
auto r1 = reduce!("a + b")(chain(a, b, c)); 

332 
assert(r1 == 112.5); 

333 
 

334 


335 
$(DDOC_SECTION_H Multiple functions:) Sometimes it is very useful to 

336 
compute multiple aggregates in one pass. One advantage is that the 

337 
computation is faster because the looping overhead is shared. That's 

338 
why $(D reduce) accepts multiple functions. If two or more functions 

339 
are passed, $(D reduce) returns a $(XREF typecons, Tuple) object with 

340 
one member per passedin function. The number of seeds must be 

341 
correspondingly increased. 

342 


343 
Example: 

344 
 

345 
double[] a = [ 3.0, 4, 7, 11, 3, 2, 5 ]; 

346 
// Compute minimum and maximum in one pass 

347 
auto r = reduce!(min, max)(a); 

348 
// The type of r is Tuple!(double, double) 

349 
assert(r[0] == 2); // minimum 

350 
assert(r[1] == 11); // maximum 

351 


352 
// Compute sum and sum of squares in one pass 

353 
r = reduce!("a + b", "a + b * b")(tuple(0.0, 0.0), a); 

354 
assert(r[0] == 35); // sum 

355 
assert(r[1] == 233); // sum of squares 

356 
// Compute average and standard deviation from the above 

357 
auto avg = r[0] / a.length; 

358 
auto stdev = sqrt(r[1] / a.length  avg * avg); 

359 
 

360 
*/ 

361 


362 
template reduce(fun...) 

363 
{ 

364 
auto reduce(Args...)(Args args) 

365 
if (Args.length > 0 && Args.length <= 2 && isIterable!(Args[$  1])) 

366 
{ 

367 
static if(isInputRange!(Args[$  1])) 

368 
{ 

369 
static if (Args.length == 2) 

370 
{ 

371 
alias args[0] seed; 

372 
alias args[1] r; 

373 
Unqual!(Args[0]) result = seed; 

374 
for (; !r.empty; r.popFront) 

375 
{ 

376 
static if (fun.length == 1) 

377 
{ 

378 
result = binaryFun!(fun[0])(result, r.front); 

379 
} 

380 
else 

381 
{ 

382 
foreach (i, Unused; Args[0].Types) 

383 
{ 

384 
result[i] = binaryFun!(fun[i])(result[i], r.front); 

385 
} 

386 
} 

387 
} 

388 
return result; 

389 
} 

390 
else 

391 
{ 

392 
enforce(!args[$  1].empty, 

393 
"Cannot reduce an empty range w/o an explicit seed value."); 

394 
alias args[0] r; 

395 
static if (fun.length == 1) 

396 
{ 

397 
return reduce(r.front, (r.popFront(), r)); 

398 
} 

399 
else 

400 
{ 

401 
static assert(fun.length > 1); 

402 
typeof(adjoin!(staticMap!(binaryFun, fun))(r.front, r.front)) 

403 
result = void; 

404 
foreach (i, T; result.Types) 

405 
{ 

406 
auto p = (cast(void*) &result[i])[0 .. result[i].sizeof]; 

407 
emplace!T(p, r.front); 

408 
} 

409 
r.popFront(); 

410 
return reduce(result, r); 

411 
} 

412 
} 

413 
} 

414 
else 

415 
{ // opApply case. Coded as a separate case because efficiently 

416 
// handling all of the small details like avoiding unnecessary 

417 
// copying, iterating by dchar over strings, and dealing with the 

418 
// no explicit start value case would become an unreadable mess 

419 
// if these were merged. 

420 
alias args[$  1] r; 

421 
alias Args[$  1] R; 

422 
alias ForeachType!R E; 

423 


424 
static if(args.length == 2) 

425 
{ 

426 
static if(fun.length == 1) 

427 
{ 

428 
auto result = Tuple!(Unqual!(Args[0]))(args[0]); 

429 
} 

430 
else 

431 
{ 

432 
Unqual!(Args[0]) result = args[0]; 

433 
} 

434 


435 
enum bool initialized = true; 

436 
} 

437 
else static if(fun.length == 1) 

438 
{ 

439 
Tuple!(typeof(binaryFun!fun(E.init, E.init))) result = void; 

440 
bool initialized = false; 

441 
} 

442 
else 

443 
{ 

444 
typeof(adjoin!(staticMap!(binaryFun, fun))(E.init, E.init)) 

445 
result = void; 

446 
bool initialized = false; 

447 
} 

448 


449 
// For now, just iterate using ref to avoid unnecessary copying. 

450 
// When Bug 2443 is fixed, this may need to change. 

451 
foreach(ref elem; r) 

452 
{ 

453 
if(initialized) 

454 
{ 

455 
foreach(i, T; result.Types) 

456 
{ 

457 
result[i] = binaryFun!(fun[i])(result[i], elem); 

458 
} 

459 
} 

460 
else 

461 
{ 

462 
static if(is(typeof(&initialized))) 

463 
{ 

464 
initialized = true; 

465 
} 

466 


467 
foreach (i, T; result.Types) 

468 
{ 

469 
auto p = (cast(void*) &result[i]) 

470 
[0 .. result[i].sizeof]; 

471 
emplace!T(p, elem); 

472 
} 

473 
} 

474 
} 

475 


476 
enforce(initialized, 

477 
"Cannot reduce an empty iterable w/o an explicit seed value."); 

478 


479 
static if(fun.length == 1) 

480 
{ 

481 
return result[0]; 

482 
} 

483 
else 

484 
{ 

485 
return result; 

486 
} 

487 
} 

488 
} 

489 
} 

490 


491 
unittest 

492 
{ 

493 
debug(std_algorithm) scope(success) 

494 
writeln("unittest @", __FILE__, ":", __LINE__, " done."); 

495 
double[] a = [ 3, 4 ]; 

496 
auto r = reduce!("a + b")(0.0, a); 

497 
assert(r == 7); 

498 
r = reduce!("a + b")(a); 

499 
assert(r == 7); 

500 
r = reduce!(min)(a); 

501 
assert(r == 3); 

502 
double[] b = [ 100 ]; 

503 
auto r1 = reduce!("a + b")(chain(a, b)); 

504 
assert(r1 == 107); 

505 


506 
// two funs 

507 
auto r2 = reduce!("a + b", "a  b")(tuple(0., 0.), a); 

508 
assert(r2[0] == 7 && r2[1] == 7); 

509 
auto r3 = reduce!("a + b", "a  b")(a); 

510 
assert(r3[0] == 7 && r3[1] == 1); 

511 


512 
a = [ 1, 2, 3, 4, 5 ]; 

513 
// Stringize with commas 

514 
string rep = reduce!("a ~ `, ` ~ to!(string)(b)")("", a); 

515 
assert(rep[2 .. $] == "1, 2, 3, 4, 5", "["~rep[2 .. $]~"]"); 

516 


517 
// Test the opApply case. 

518 
struct OpApply 

519 
{ 

520 
bool actEmpty; 

521 


522 
int opApply(int delegate(ref int) dg) 

523 
{ 

524 
int res; 

525 
if(actEmpty) return res; 

526 


527 
foreach(i; 0..100) 

528 
{ 

529 
res = dg(i); 

530 
if(res) break; 

531 
} 

532 
return res; 

533 
} 

534 
} 

535 


536 
OpApply oa; 

537 
auto hundredSum = reduce!"a + b"(iota(100)); 

538 
assert(reduce!"a + b"(5, oa) == hundredSum + 5); 

539 
assert(reduce!"a + b"(oa) == hundredSum); 

540 
assert(reduce!("a + b", max)(oa) == tuple(hundredSum, 99)); 

541 
assert(reduce!("a + b", max)(tuple(5, 0), oa) == tuple(hundredSum + 5, 99)); 

542 


543 
// Test for throwing on empty range plus no seed. 

544 
try { 

545 
reduce!"a + b"([1, 2][0..0]); 

546 
assert(0); 

547 
} catch(Exception) {} 

548 


549 
oa.actEmpty = true; 

550 
try { 

551 
reduce!"a + b"(oa); 

552 
assert(0); 

553 
} catch(Exception) {} 

554 
} 

555 


556 
unittest 

557 
{ 

558 
debug(std_algorithm) scope(success) 

559 
writeln("unittest @", __FILE__, ":", __LINE__, " done."); 

560 
const float a = 0.0; 

561 
const float[] b = [ 1.2, 3, 3.3 ]; 

562 
float[] c = [ 1.2, 3, 3.3 ]; 

563 
auto r = reduce!"a + b"(a, b); 

564 
r = reduce!"a + b"(a, c); 

565 
} 

566 


567 
/** 

568 
Fills a range with a value. 

569 


570 
Example: 

571 
 

572 
int[] a = [ 1, 2, 3, 4 ]; 

573 
fill(a, 5); 

574 
assert(a == [ 5, 5, 5, 5 ]); 

575 
 

576 
*/ 

577 
void fill(Range, Value)(Range range, Value filler) 

578 
if (isForwardRange!Range && is(typeof(range.front = filler))) 

579 
{ 

580 
alias ElementType!Range T; 

581 
static if (hasElaborateCopyConstructor!T  !isDynamicArray!Range) 

582 
{ 

583 
for (; !range.empty; range.popFront) 

584 
{ 

585 
range.front = filler; 

586 
} 

587 
} 

588 
else 

589 
{ 

590 
if (range.empty) return; 

591 
// Range is a dynamic array of bald values, just fill memory 

592 
// Can't use memcpy or memmove coz ranges overlap 

593 
range.front = filler; 

594 
auto bytesToFill = T.sizeof * (range.length  1); 

595 
auto bytesFilled = T.sizeof; 

596 
while (bytesToFill) 

597 
{ 

598 
auto fillNow = min(bytesToFill, bytesFilled); 

599 
memcpy(cast(void*) range.ptr + bytesFilled, 

600 
cast(void*) range.ptr, 

601 
fillNow); 

602 
bytesToFill = fillNow; 

603 
bytesFilled += fillNow; 

604 
} 

605 
} 

606 
} 

607 


608 
unittest 

609 
{ 

610 
debug(std_algorithm) scope(success) 

611 
writeln("unittest @", __FILE__, ":", __LINE__, " done."); 

612 
int[] a = [ 1, 2, 3 ]; 

613 
fill(a, 6); 

614 
assert(a == [ 6, 6, 6 ], text(a)); 

615 
void fun0() 

616 
{ 

617 
foreach (i; 0 .. 1000) 

618 
{ 

619 
foreach (ref e; a) e = 6; 

620 
} 

621 
} 

622 
void fun1() { foreach (i; 0 .. 1000) fill(a, 6); } 

623 
//void fun2() { foreach (i; 0 .. 1000) fill2(a, 6); } 

624 
//writeln(benchmark!(fun0, fun1, fun2)(10000)); 

625 
} 

626 


627 
/** 

628 
Fills $(D range) with a pattern copied from $(D filler). The length of 

629 
$(D range) does not have to be a multiple of the length of $(D 

630 
filler). If $(D filler) is empty, an exception is thrown. 

631 


632 
Example: 

633 
 

634 
int[] a = [ 1, 2, 3, 4, 5 ]; 

635 
int[] b = [ 8, 9 ]; 

636 
fill(a, b); 

637 
assert(a == [ 8, 9, 8, 9, 8 ]); 

638 
 

639 
*/ 

640 


641 
void fill(Range1, Range2)(Range1 range, Range2 filler) 

642 
if (isForwardRange!Range1 && isForwardRange!Range2 

643 
&& is(typeof(Range1.init.front = Range2.init.front))) 

644 
{ 

645 
enforce(!filler.empty); 

646 
auto t = filler.save; 

647 
for (; !range.empty; range.popFront, t.popFront) 

648 
{ 

649 
if (t.empty) t = filler; 

650 
range.front = t.front; 

651 
} 

652 
} 

653 


654 
unittest 

655 
{ 

656 
debug(std_algorithm) scope(success) 

657 
writeln("unittest @", __FILE__, ":", __LINE__, " done."); 

658 
int[] a = [ 1, 2, 3, 4, 5 ]; 

659 
int[] b = [1, 2]; 

660 
fill(a, b); 

661 
assert(a == [ 1, 2, 1, 2, 1 ]); 

662 
} 

663 


664 
/** 

665 
Fills a range with a value. Assumes that the range does not currently 

666 
contain meaningful content. This is of interest for structs that 

667 
define copy constructors (for all other types, fill and 

668 
uninitializedFill are equivalent). 

669 


670 
Example: 

671 
 

672 
struct S { ... } 

673 
S[] s = (cast(S*) malloc(5 * S.sizeof))[0 .. 5]; 

674 
uninitializedFill(s, 42); 

675 
assert(s == [ 42, 42, 42, 42, 42 ]); 

676 
 

677 
*/ 

678 
void uninitializedFill(Range, Value)(Range range, Value filler) 

679 
if (isForwardRange!Range && is(typeof(range.front = filler))) 

680 
{ 

681 
alias ElementType!Range T; 

682 
static if (hasElaborateCopyConstructor!T) 

683 
{ 

684 
// Must construct stuff by the book 

685 
for (; !range.empty; range.popFront) 

686 
{ 

687 
emplace!T((cast(void*) &range.front)[0 .. T.sizeof], filler); 

688 
} 

689 
} 

690 
else 

691 
{ 

692 
// Doesn't matter whether fill is initialized or not 

693 
return fill(range, filler); 

694 
} 

695 
} 

696 


697 
unittest 

698 
{ 

699 
debug(std_algorithm) scope(success) 

700 
writeln("unittest @", __FILE__, ":", __LINE__, " done."); 

701 
int[] a = [ 1, 2, 3 ]; 

702 
uninitializedFill(a, 6); 

703 
assert(a == [ 6, 6, 6 ]); 

704 
void fun0() 

705 
{ 

706 
foreach (i; 0 .. 1000) 

707 
{ 

708 
foreach (ref e; a) e = 6; 

709 
} 

710 
} 

711 
void fun1() { foreach (i; 0 .. 1000) fill(a, 6); } 

712 
//void fun2() { foreach (i; 0 .. 1000) fill2(a, 6); } 

713 
//writeln(benchmark!(fun0, fun1, fun2)(10000)); 

714 
} 

715 


716 
/** 

717 
Initializes all elements of a range with their $(D .init) 

718 
value. Assumes that the range does not currently contain meaningful 

719 
content. 

720 


721 
Example: 

722 
 

723 
struct S { ... } 

724 
S[] s = (cast(S*) malloc(5 * S.sizeof))[0 .. 5]; 

725 
initialize(s); 

726 
assert(s == [ 0, 0, 0, 0, 0 ]); 

727 
 

728 
*/ 

729 
void initializeAll(Range)(Range range) 

730 
if (isForwardRange!Range && is(typeof(range.front = range.front))) 

731 
{ 

732 
alias ElementType!Range T; 

733 
static assert(is(typeof(&(range.front())))  !hasElaborateAssign!T, 

734 
"Cannot initialize a range that does not expose" 

735 
" references to its elements"); 

736 
static if (!isDynamicArray!Range) 

737 
{ 

738 
static if (is(typeof(&(range.front())))) 

739 
{ 

740 
// Range exposes references 

741 
for (; !range.empty; range.popFront) 

742 
{ 

743 
memcpy(&(range.front()), &T.init, T.sizeof); 

744 
} 

745 
} 

746 
else 

747 
{ 

748 
// Go the slow route 

749 
for (; !range.empty; range.popFront) 

750 
{ 

751 
range.front = filler; 

752 
} 

753 
} 

754 
} 

755 
else 

756 
{ 

757 
fill(range, T.init); 

758 
} 

759 
} 

760 


761 
unittest 

762 
{ 

763 
debug(std_algorithm) scope(success) 

764 
writeln("unittest @", __FILE__, ":", __LINE__, " done."); 

765 
int[] a = [ 1, 2, 3 ]; 

766 
uninitializedFill(a, 6); 

767 
assert(a == [ 6, 6, 6 ]); 

768 
initializeAll(a); 

769 
assert(a == [ 0, 0, 0 ]); 

770 
void fun0() 

771 
{ 

772 
foreach (i; 0 .. 1000) 

773 
{ 

774 
foreach (ref e; a) e = 6; 

775 
} 

776 
} 

777 
void fun1() { foreach (i; 0 .. 1000) fill(a, 6); } 

778 
//void fun2() { foreach (i; 0 .. 1000) fill2(a, 6); } 

779 
//writeln(benchmark!(fun0, fun1, fun2)(10000)); 

780 
} 

781 


782 
// filter 

783 
/** 

784 
Implements the homonym function present in various programming 

785 
languages of functional flavor. The call $(D filter!(fun)(range)) 

786 
returns a new range only containing elements $(D x) in $(D r) for 

787 
which $(D predicate(x)) is $(D true). 

788 


789 
Example: 

790 
 

791 
int[] arr = [ 1, 2, 3, 4, 5 ]; 

792 
// Sum all elements 

793 
auto small = filter!("a < 3")(arr); 

794 
assert(small == [ 1, 2 ]); 

795 
// In combination with chain() to span multiple ranges 

796 
int[] a = [ 3, 2, 400 ]; 

797 
int[] b = [ 100, 101, 102 ]; 

798 
auto r = filter!("a > 0")(chain(a, b)); 

799 
assert(equal(r, [ 3, 400, 100, 102 ])); 

800 
// Mixing convertible types is fair game, too 

801 
double[] c = [ 2.5, 3.0 ]; 

802 
auto r1 = filter!("cast(int) a != a")(chain(c, a, b)); 

803 
assert(r1 == [ 2.5 ]); 

804 
 

805 
*/ 

806 
template filter(alias pred) 

807 
{ 

808 
auto filter(Range)(Range rs) 

809 
{ 

810 
return Filter!(unaryFun!(pred), Range)(rs); 

811 
} 

812 
} 

813 


814 
struct Filter(alias pred, Range) if (isInputRange!(Unqual!Range)) 

815 
{ 

816 
alias Unqual!Range R; 

817 
R _input; 

818 


819 
this(R r) 

820 
{ 

821 
_input = r; 

822 
while (!_input.empty && !pred(_input.front)) _input.popFront; 

823 
} 

824 


825 
ref Filter opSlice() 

826 
{ 

827 
return this; 

828 
} 

829 


830 
static if (isInfinite!Range) 

831 
{ 

832 
enum bool empty = false; 

833 
} 

834 
else 

835 
{ 

836 
@property bool empty() { return _input.empty; } 

837 
} 

838 


839 
void popFront() 

840 
{ 

841 
do 

842 
{ 

843 
_input.popFront; 

844 
} while (!_input.empty && !pred(_input.front)); 

845 
} 

846 


847 
@property auto ref front() 

848 
{ 

849 
return _input.front; 

850 
} 

851 


852 
static if(isForwardRange!R) 

853 
{ 

854 
@property typeof(this) save() 

855 
{ 

856 
return typeof(this)(_input); 

857 
} 

858 
} 

859 
} 

860 


861 
unittest 

862 
{ 

863 
debug(std_algorithm) scope(success) 

864 
writeln("unittest @", __FILE__, ":", __LINE__, " done."); 

865 
int[] a = [ 3, 4, 2 ]; 

866 
auto r = filter!("a > 3")(a); 

867 
static assert(isForwardRange!(typeof(r))); 

868 
assert(equal(r, [ 4 ][])); 

869 


870 
a = [ 1, 22, 3, 42, 5 ]; 

871 
auto under10 = filter!("a < 10")(a); 

872 
assert(equal(under10, [1, 3, 5][])); 

873 
static assert(isForwardRange!(typeof(under10))); 

874 
under10.front() = 4; 

875 
assert(equal(under10, [4, 3, 5][])); 

876 
under10.front() = 40; 

877 
assert(equal(under10, [40, 3, 5][])); 

878 
under10.front() = 1; 

879 


880 
auto infinite = filter!"a > 2"(repeat(3)); 

881 
static assert(isInfinite!(typeof(infinite))); 

882 
static assert(isForwardRange!(typeof(infinite))); 

883 


884 
foreach(DummyType; AllDummyRanges) { 

885 
DummyType d; 

886 
auto f = filter!"a & 1"(d); 

887 
assert(equal(f, [1,3,5,7,9])); 

888 


889 
static if (isForwardRange!DummyType) { 

890 
static assert(isForwardRange!(typeof(f))); 

891 
} 

892 
} 

893 


894 
// With delegates 

895 
int x = 10; 

896 
int overX(int a) { return a > x; } 

897 
typeof(filter!overX(a)) getFilter() 

898 
{ 

899 
return filter!overX(a); 

900 
} 

901 
auto r1 = getFilter(); 

902 
assert(equal(r1, [22, 42])); 

903 


904 
// With chain 

905 
auto nums = [0,1,2,3,4]; 

906 
assert(equal(filter!overX(chain(a, nums)), [22, 42])); 

907 


908 
// With copying of inner struct Filter to Map 

909 
auto arr = [1,2,3,4,5]; 

910 
auto m = map!"a + 1"(filter!"a < 4"(arr)); 

911 
} 

912 


913 
unittest 

914 
{ 

915 
int[] a = [ 3, 4 ]; 

916 
const aConst = a; 

917 
auto r = filter!("a > 3")(aConst); 

918 
assert(equal(r, [ 4 ][])); 

919 


920 
a = [ 1, 22, 3, 42, 5 ]; 

921 
auto under10 = filter!("a < 10")(a); 

922 
assert(equal(under10, [1, 3, 5][])); 

923 
assert(under10.save == under10); 

924 


925 
// With copying of inner struct Filter to Map 

926 
auto arr = [1,2,3,4,5]; 

927 
auto m = map!"a + 1"(filter!"a < 4"(arr)); 

928 
} 

929 


930 
unittest 

931 
{ 

932 
assert(equal(compose!(map!"2 * a", filter!"a & 1")([1,2,3,4,5]), 

933 
[2,6,10])); 

934 
assert(equal(pipe!(filter!"a & 1", map!"2 * a")([1,2,3,4,5]), 

935 
[2,6,10])); 

936 
} 

937 


938 
unittest 

939 
{ 

940 
int x = 10; 

941 
int underX(int a) { return a < x; } 

942 
const(int)[] list = [ 1, 2, 10, 11, 3, 4 ]; 

943 
assert(equal(filter!underX(list), [ 1, 2, 3, 4 ])); 

944 
} 

945 


946 
// filterBidirectional 

947 
/** 

948 
* Similar to $(D filter), except it defines a bidirectional 

949 
* range. There is a speed disadvantage  the constructor spends time 

950 
* finding the last element in the range that satisfies the filtering 

951 
* condition (in addition to finding the first one). The advantage is 

952 
* that the filtered range can be spanned from both directions. Also, 

953 
* $(XREF range, retro) can be applied against the filtered range. 

954 
* 

955 
Example: 

956 
 

957 
int[] arr = [ 1, 2, 3, 4, 5 ]; 

958 
auto small = filterBidirectional!("a < 3")(arr); 

959 
assert(small.back == 2); 

960 
assert(equal(small, [ 1, 2 ])); 

961 
assert(equal(retro(small), [ 2, 1 ])); 

962 
// In combination with chain() to span multiple ranges 

963 
int[] a = [ 3, 2, 400 ]; 

964 
int[] b = [ 100, 101, 102 ]; 

965 
auto r = filterBidirectional!("a > 0")(chain(a, b)); 

966 
assert(r.back == 102); 

967 
 

968 
*/ 

969 
template filterBidirectional(alias pred) 

970 
{ 

971 
FilterBidirectional!(unaryFun!(pred), Range) 

972 
filterBidirectional(Range)(Range rs) 

973 
{ 

974 
return typeof(return)(rs); 

975 
} 

976 
} 

977 


978 
struct FilterBidirectional(alias pred, Range) if (isBidirectionalRange!(Unqual!Range)) 

979 
{ 

980 
alias Unqual!Range R; 

981 
R _input; 

982 


983 
this(R r) 

984 
{ 

985 
_input = r; 

986 
while (!_input.empty && !pred(_input.front)) _input.popFront(); 

987 
while (!_input.empty && !pred(_input.back)) _input.popBack(); 

988 
} 

989 


990 
@property bool empty() { return _input.empty; } 

991 


992 
void popFront() 

993 
{ 

994 
do 

995 
{ 

996 
_input.popFront; 

997 
} while (!_input.empty && !pred(_input.front)); 

998 
} 

999 


1000 
@property auto ref front() 

1001 
{ 

1002 
return _input.front; 

1003 
} 

1004 


1005 
void popBack() 

1006 
{ 

1007 
do 

1008 
{ 

1009 
_input.popBack; 

1010 
} while (!_input.empty && !pred(_input.back)); 

1011 
} 

1012 


1013 
@property auto ref back() 

1014 
{ 

1015 
return _input.back; 

1016 
} 

1017 


1018 
@property typeof(this) save() 

1019 
{ 

1020 
return typeof(this)(_input); 

1021 
} 

1022 
} 

1023 


1024 
unittest 

1025 
{ 

1026 
int[] arr = [ 1, 2, 3, 4, 5 ]; 

1027 
auto small = filterBidirectional!("a < 3")(arr); 

1028 
static assert(isBidirectionalRange!(typeof(small))); 

1029 
assert(small.back == 2); 

1030 
assert(equal(small, [ 1, 2 ])); 

1031 
assert(equal(retro(small), [ 2, 1 ])); 

1032 
// In combination with chain() to span multiple ranges 

1033 
int[] a = [ 3, 2, 400 ]; 

1034 
int[] b = [ 100, 101, 102 ]; 

1035 
auto r = filterBidirectional!("a > 0")(chain(a, b)); 

1036 
assert(r.back == 102); 

1037 
} 

1038 


1039 
// move 

1040 
/** 

1041 
Moves $(D source) into $(D target) via a destructive 

1042 
copy. Specifically: $(UL $(LI If $(D hasAliasing!T) is true (see 

1043 
$(XREF traits, hasAliasing)), then the representation of $(D source) 

1044 
is bitwise copied into $(D target) and then $(D source = T.init) is 

1045 
evaluated.) $(LI Otherwise, $(D target = source) is evaluated.)) See 

1046 
also $(XREF contracts, pointsTo). 

1047 


1048 
Preconditions: 

1049 
$(D &source == &target  !pointsTo(source, source)) 

1050 
*/ 

1051 
void move(T)(ref T source, ref T target) 

1052 
{ 

1053 
if (&source == &target) return; 

1054 
assert(!pointsTo(source, source)); 

1055 
static if (is(T == struct)) 

1056 
{ 

1057 
// Most complicated case. Destroy whatever target had in it 

1058 
// and bitblast source over it 

1059 
static if (is(typeof(target.__dtor()))) target.__dtor(); 

1060 
memcpy(&target, &source, T.sizeof); 

1061 
// If the source defines a destructor or a postblit hook, we must obliterate the 

1062 
// object in order to avoid double freeing and undue aliasing 

1063 
static if (is(typeof(source.__dtor()))  is(typeof(source.__postblit()))) 

1064 
{ 

1065 
static T empty; 

1066 
memcpy(&source, &empty, T.sizeof); 

1067 
} 

1068 
} 

1069 
else 

1070 
{ 

1071 
// Primitive data (including pointers and arrays) or class  

1072 
// assignment works great 

1073 
target = source; 

1074 
// static if (is(typeof(source = null))) 

1075 
// { 

1076 
// // Nullify the source to help the garbage collector 

1077 
// source = null; 

1078 
// } 

1079 
} 

1080 
} 

1081 


1082 
unittest 

1083 
{ 

1084 
debug(std_algorithm) scope(success) 

1085 
writeln("unittest @", __FILE__, ":", __LINE__, " done."); 

1086 
Object obj1 = new Object; 

1087 
Object obj2 = obj1; 

1088 
Object obj3; 

1089 
move(obj2, obj3); 

1090 
assert(obj3 is obj1); 

1091 


1092 
struct S1 { int a = 1, b = 2; } 

1093 
S1 s11 = { 10, 11 }; 

1094 
S1 s12; 

1095 
move(s11, s12); 

1096 
assert(s11.a == 10 && s11.b == 11 && s12.a == 10 && s12.b == 11); 

1097 


1098 
struct S2 { int a = 1; int * b; } 

1099 
S2 s21 = { 10, new int }; 

1100 
S2 s22; 

1101 
move(s21, s22); 

1102 
assert(s21 == s22); 

1103 
} 

1104 


1105 
/// Ditto 

1106 
T move(T)(ref T src) 

1107 
{ 

1108 
T result; 

1109 
move(src, result); 

1110 
return result; 

1111 
} 

1112 


1113 
// moveAll 

1114 
/** 

1115 
For each element $(D a) in $(D src) and each element $(D b) in $(D 

1116 
tgt) in lockstep in increasing order, calls $(D move(a, b)). Returns 

1117 
the leftover portion of $(D tgt). Throws an exeption if there is not 

1118 
enough room in $(D tgt) to acommodate all of $(D src). 

1119 


1120 
Preconditions: 

1121 
$(D walkLength(src) >= walkLength(tgt)) 

1122 
*/ 

1123 
Range2 moveAll(Range1, Range2)(Range1 src, Range2 tgt) 

1124 
{ 

1125 
for (; !src.empty; src.popFront, tgt.popFront) 

1126 
{ 

1127 
enforce(!tgt.empty); 

1128 
move(src.front, tgt.front); 

1129 
} 

1130 
return tgt; 

1131 
} 

1132 


1133 
unittest 

1134 
{ 

1135 
debug(std_algorithm) scope(success) 

1136 
writeln("unittest @", __FILE__, ":", __LINE__, " done."); 

1137 
int[] a = [ 1, 2, 3 ]; 

1138 
int[] b = new int[5]; 

1139 
assert(moveAll(a, b) is b[3 .. $]); 

1140 
assert(a == b[0 .. 3]); 

1141 
assert(a == [ 1, 2, 3 ]); 

1142 
} 

1143 


1144 
// moveSome 

1145 
/** 

1146 
For each element $(D a) in $(D src) and each element $(D b) in $(D 

1147 
tgt) in lockstep in increasing order, calls $(D move(a, b)). Stops 

1148 
when either $(D src) or $(D tgt) have been exhausted. Returns the 

1149 
leftover portions of the two ranges. 

1150 
*/ 

1151 
Tuple!(Range1, Range2) moveSome(Range1, Range2)(Range1 src, Range2 tgt) 

1152 
{ 

1153 
for (; !src.empty && !tgt.empty; src.popFront, tgt.popFront) 

1154 
{ 

1155 
enforce(!tgt.empty); 

1156 
move(src.front, tgt.front); 

1157 
} 

1158 
return tuple(src, tgt); 

1159 
} 

1160 


1161 
unittest 

1162 
{ 

1163 
debug(std_algorithm) scope(success) 

1164 
writeln("unittest @", __FILE__, ":", __LINE__, " done."); 

1165 
int[] a = [ 1, 2, 3, 4, 5 ]; 

1166 
int[] b = new int[3]; 

1167 
assert(moveSome(a, b)[0] is a[3 .. $]); 

1168 
assert(a[0 .. 3] == b); 

1169 
assert(a == [ 1, 2, 3, 4, 5 ]); 

1170 
} 

1171 


1172 
// swap 

1173 
/** 

1174 
Swaps $(D lhs) and $(D rhs). See also $(XREF exception, pointsTo). 

1175 


1176 
Preconditions: 

1177 


1178 
$(D !pointsTo(lhs, lhs) && !pointsTo(lhs, rhs) && !pointsTo(rhs, lhs) 

1179 
&& !pointsTo(rhs, rhs)) 

1180 
*/ 

1181 
void swap(T)(ref T lhs, ref T rhs) @trusted pure nothrow 

1182 
if (isMutable!T && !is(typeof(T.init.proxySwap(T.init)))) 

1183 
{ 

1184 
static if (hasElaborateAssign!T) 

1185 
{ 

1186 
// For structs with nontrivial assignment, move memory directly 

1187 
// First check for undue aliasing 

1188 
assert(!pointsTo(lhs, rhs) && !pointsTo(rhs, lhs) 

1189 
&& !pointsTo(lhs, lhs) && !pointsTo(rhs, rhs)); 

1190 
// Swap bits 

1191 
ubyte[T.sizeof] t = void; 

1192 
auto a = (cast(ubyte*) &lhs)[0 .. T.sizeof]; 

1193 
auto b = (cast(ubyte*) &rhs)[0 .. T.sizeof]; 

1194 
t[] = a[]; 

1195 
a[] = b[]; 

1196 
b[] = t[]; 

1197 
} 

1198 
else 

1199 
{ 

1200 
// Temporary fix Bug 4789. Wor around the fact that assigning a static 

1201 
// array to itself doesn't work properly. 

1202 
static if(isStaticArray!T) { 

1203 
if(lhs.ptr is rhs.ptr) { 

1204 
return; 

1205 
} 

1206 
} 

1207 


1208 
// For nonstruct types, suffice to do the classic swap 

1209 
auto tmp = lhs; 

1210 
lhs = rhs; 

1211 
rhs = tmp; 

1212 
} 

1213 
} 

1214 


1215 
// Not yet documented 

1216 
void swap(T)(T lhs, T rhs) if (is(typeof(T.init.proxySwap(T.init)))) 

1217 
{ 

1218 
lhs.proxySwap(rhs); 

1219 
} 

1220 


1221 
unittest 

1222 
{ 

1223 
debug(std_algorithm) scope(success) 

1224 
writeln("unittest @", __FILE__, ":", __LINE__, " done."); 

1225 
int a = 42, b = 34; 

1226 
swap(a, b); 

1227 
assert(a == 34 && b == 42); 

1228 


1229 
struct S { int x; char c; int[] y; } 

1230 
S s1 = { 0, 'z', [ 1, 2 ] }; 

1231 
S s2 = { 42, 'a', [ 4, 6 ] }; 

1232 
//writeln(s2.tupleof.stringof); 

1233 
swap(s1, s2); 

1234 
assert(s1.x == 42); 

1235 
assert(s1.c == 'a'); 

1236 
assert(s1.y == [ 4, 6 ]); 

1237 


1238 
assert(s2.x == 0); 

1239 
assert(s2.c == 'z'); 

1240 
assert(s2.y == [ 1, 2 ]); 

1241 


1242 
immutable int imm1, imm2; 

1243 
static assert(!__traits(compiles, swap(imm1, imm2))); 

1244 
} 

1245 


1246 
unittest 

1247 
{ 

1248 
struct NoCopy 

1249 
{ 

1250 
this(this) { assert(0); } 

1251 
int n; 

1252 
string s; 

1253 
} 

1254 
NoCopy nc1, nc2; 

1255 
nc1.n = 127; nc1.s = "abc"; 

1256 
nc2.n = 513; nc2.s = "uvwxyz"; 

1257 
swap(nc1, nc2); 

1258 
assert(nc1.n == 513 && nc1.s == "uvwxyz"); 

1259 
assert(nc2.n == 127 && nc2.s == "abc"); 

1260 


1261 
struct NoCopyHolder 

1262 
{ 

1263 
NoCopy noCopy; 

1264 
} 

1265 
NoCopyHolder h1, h2; 

1266 
h1.noCopy.n = 31; h1.noCopy.s = "abc"; 

1267 
h2.noCopy.n = 65; h2.noCopy.s = null; 

1268 
swap(h1, h2); 

1269 
assert(h1.noCopy.n == 65 && h1.noCopy.s == null); 

1270 
assert(h2.noCopy.n == 31 && h2.noCopy.s == "abc"); 

1271 


1272 
const NoCopy const1, const2; 

1273 
static assert(!__traits(compiles, swap(const1, const2))); 

1274 
} 

1275 


1276 
void swapFront(R1, R2)(R1 r1, R2 r2) 

1277 
if (isInputRange!R1 && isInputRange!R2) 

1278 
{ 

1279 
static if (is(typeof(swap(r1.front, r2.front)))) 

1280 
{ 

1281 
swap(r1.front, r2.front); 

1282 
} 

1283 
else 

1284 
{ 

1285 
auto t1 = moveFront(r1), t2 = moveFront(r2); 

1286 
r1.front = move(t2); 

1287 
r2.front = move(t1); 

1288 
} 

1289 
} 

1290 


1291 
// splitter 

1292 
/** 

1293 
Splits a range using an element as a separator. This can be used with 

1294 
any range type, but is most popular with string types. 

1295 


1296 
Two adjacent separators are considered to surround an empty element in 

1297 
the split range. 

1298 


1299 
If the empty range is given, the result is a range with one empty 

1300 
element. If a range with one separator is given, the result is a range 

1301 
with two empty elements. 

1302 


1303 
Example: 

1304 
 

1305 
assert(equal(splitter("hello world", ' '), [ "hello", "", "world" ])); 

1306 
int[] a = [ 1, 2, 0, 0, 3, 0, 4, 5, 0 ]; 

1307 
int[][] w = [ [1, 2], [], [3], [4, 5] ]; 

1308 
assert(equal(splitter(a, 0), w)); 

1309 
a = null; 

1310 
assert(equal(splitter(a, 0), [ (int[]).init ])); 

1311 
a = [ 0 ]; 

1312 
assert(equal(splitter(a, 0), [ (int[]).init, (int[]).init ])); 

1313 
a = [ 0, 1 ]; 

1314 
assert(equal(splitter(a, 0), [ [], [1] ])); 

1315 
 

1316 
*/ 

1317 
struct Splitter(Range, Separator) 

1318 
if (is(typeof(ElementType!Range.init == Separator.init)) && hasSlicing!Range) 

1319 
{ 

1320 
private: 

1321 
Range _input; 

1322 
Separator _separator; 

1323 
enum size_t _unComputed = size_t.max  1, _atEnd = size_t.max; 

1324 
size_t _frontLength = _unComputed; 

1325 
size_t _backLength = _unComputed; 

1326 


1327 
static if(isBidirectionalRange!Range) 

1328 
{ 

1329 
static sizediff_t lastIndexOf(Range haystack, Separator needle) 

1330 
{ 

1331 
immutable index = countUntil(retro(haystack), needle); 

1332 
return (index == 1) ? 1 : haystack.length  1  index; 

1333 
} 

1334 
} 

1335 


1336 
public: 

1337 
this(Range input, Separator separator) 

1338 
{ 

1339 
_input = input; 

1340 
_separator = separator; 

1341 
// computeFront(); 

1342 
// computeBack(); 

1343 
} 

1344 


1345 
static if (isInfinite!Range) 

1346 
{ 

1347 
enum bool empty = false; 

1348 
} 

1349 
else 

1350 
{ 

1351 
@property bool empty() 

1352 
{ 

1353 
return _frontLength == _atEnd; 

1354 
} 

1355 
} 

1356 


1357 
@property Range front() 

1358 
{ 

1359 
assert(!empty); 

1360 
if (_frontLength == _unComputed) 

1361 
{ 

1362 
_frontLength = countUntil(_input, _separator); 

1363 
if (_frontLength == 1) _frontLength = _input.length; 

1364 
} 

1365 
return _input[0 .. _frontLength]; 

1366 
} 

1367 


1368 
void popFront() 

1369 
{ 

1370 
assert(!empty); 

1371 
if (_frontLength == _unComputed) 

1372 
{ 

1373 
front; 

1374 
} 

1375 
assert(_frontLength <= _input.length); 

1376 
if (_frontLength == _input.length) 

1377 
{ 

1378 
// no more input and need to fetch => done 

1379 
_frontLength = _atEnd; 

1380 


1381 
// Probably don't need this, but just for consistency: 

1382 
_backLength = _atEnd; 

1383 
} 

1384 
else 

1385 
{ 

1386 
_input = _input[_frontLength .. _input.length]; 

1387 
skipOver(_input, _separator)  assert(false); 

1388 
_frontLength = _unComputed; 

1389 
} 

1390 
} 

1391 


1392 
static if(isForwardRange!Range) 

1393 
{ 

1394 
@property typeof(this) save() 

1395 
{ 

1396 
auto ret = this; 

1397 
ret._input = _input.save; 

1398 
return ret; 

1399 
} 

1400 
} 

1401 


1402 
static if(isBidirectionalRange!Range) 

1403 
{ 

1404 
@property Range back() 

1405 
{ 

1406 
assert(!empty); 

1407 
if (_backLength == _unComputed) 

1408 
{ 

1409 
immutable lastIndex = lastIndexOf(_input, _separator); 

1410 
if(lastIndex == 1) 

1411 
{ 

1412 
_backLength = _input.length; 

1413 
} 

1414 
else 

1415 
{ 

1416 
_backLength = _input.length  lastIndex  1; 

1417 
} 

1418 
} 

1419 
return _input[_input.length  _backLength .. _input.length]; 

1420 
} 

1421 


1422 
void popBack() 

1423 
{ 

1424 
assert(!empty); 

1425 
if (_backLength == _unComputed) 

1426 
{ 

1427 
back; 

1428 
} 

1429 
assert(_backLength <= _input.length); 

1430 
if (_backLength == _input.length) 

1431 
{ 

1432 
// no more input and need to fetch => done 

1433 
_frontLength = _atEnd; 

1434 
_backLength = _atEnd; 

1435 
} 

1436 
else 

1437 
{ 

1438 
_input = _input[0 .. _input.length  _backLength]; 

1439 
if(!_input.empty && _input.back == _separator) 

1440 
{ 

1441 
_input.popBack(); 

1442 
} 

1443 
else 

1444 
{ 

1445 
assert(false); 

1446 
} 

1447 
_backLength = _unComputed; 

1448 
} 

1449 
} 

1450 
} 

1451 
} 

1452 


1453 
/// Ditto 

1454 
Splitter!(Range, Separator) 

1455 
splitter(Range, Separator)(Range r, Separator s) 

1456 
if (is(typeof(ElementType!Range.init == ElementType!Separator.init)) 

1457 
 

1458 
is(typeof(ElementType!Range.init == Separator.init)) 

1459 
) 

1460 
{ 

1461 
return typeof(return)(r, s); 

1462 
} 

1463 


1464 
unittest 

1465 
{ 

1466 
debug(std_algorithm) scope(success) 

1467 
writeln("unittest @", __FILE__, ":", __LINE__, " done."); 

1468 
assert(equal(splitter("hello world", ' '), [ "hello", "", "world" ])); 

1469 
int[] a = [ 1, 2, 0, 0, 3, 0, 4, 5, 0 ]; 

1470 
int[][] w = [ [1, 2], [], [3], [4, 5], [] ]; 

1471 
static assert(isForwardRange!(typeof(splitter(a, 0)))); 

1472 


1473 
// foreach (x; splitter(a, 0)) { 

1474 
// writeln("[", x, "]"); 

1475 
// } 

1476 
assert(equal(splitter(a, 0), w)); 

1477 
a = null; 

1478 
assert(equal(splitter(a, 0), [ (int[]).init ][])); 

1479 
a = [ 0 ]; 

1480 
assert(equal(splitter(a, 0), [ (int[]).init, (int[]).init ][])); 

1481 
a = [ 0, 1 ]; 

1482 
assert(equal(splitter(a, 0), [ [], [1] ][])); 

1483 


1484 
// Thoroughly exercise the bidirectional stuff. 

1485 
auto str = "abc abcd abcde ab abcdefg abcdefghij ab ac ar an at ada"; 

1486 
assert(equal( 

1487 
retro(splitter(str, 'a')), 

1488 
retro(array(splitter(str, 'a'))) 

1489 
)); 

1490 


1491 
// Test interleaving front and back. 

1492 
auto split = splitter(str, 'a'); 

1493 
assert(split.front == ""); 

1494 
assert(split.back == ""); 

1495 
split.popBack(); 

1496 
assert(split.back == "d"); 

1497 
split.popFront(); 

1498 
assert(split.front == "bc "); 

1499 
assert(split.back == "d"); 

1500 
split.popFront(); 

1501 
split.popBack(); 

1502 
assert(split.back == "t "); 

1503 
split.popBack(); 

1504 
split.popBack(); 

1505 
split.popFront(); 

1506 
split.popFront(); 

1507 
assert(split.front == "b "); 

1508 
assert(split.back == "r "); 

1509 


1510 
foreach(DummyType; AllDummyRanges) { // Bug 4408 

1511 
static if(isRandomAccessRange!DummyType) { 

1512 
static assert(isBidirectionalRange!DummyType); 

1513 
DummyType d; 

1514 
auto s = splitter(d, 5); 

1515 
assert(equal(s.front, [1,2,3,4])); 

1516 
assert(equal(s.back, [6,7,8,9,10])); 

1517 


1518 


1519 
auto s2 = splitter(d, [4, 5]); 

1520 
assert(equal(s2.front, [1,2,3])); 

1521 
assert(equal(s2.back, [6,7,8,9,10])); 

1522 
} 

1523 
} 

1524 
} 

1525 


1526 
/** 

1527 
Splits a range using another range as a separator. This can be used 

1528 
with any range type, but is most popular with string types. 

1529 
*/ 

1530 
struct Splitter(Range, Separator) 

1531 
if (is(typeof(Range.init.front == Separator.init.front) : bool)) 

1532 
{ 

1533 
private: 

1534 
Range _input; 

1535 
Separator _separator; 

1536 
// _frontLength == size_t.max means empty 

1537 
size_t _frontLength = size_t.max; 

1538 
static if (isBidirectionalRange!Range) 

1539 
size_t _backLength = size_t.max; 

1540 


1541 
size_t separatorLength() { return _separator.length; } 

1542 


1543 
void ensureFrontLength() 

1544 
{ 

1545 
if (_frontLength != _frontLength.max) return; 

1546 
assert(!_input.empty); 

1547 
// compute front length 

1548 
_frontLength = _input.length  find(_input, _separator).length; 

1549 
static if (isBidirectionalRange!Range) 

1550 
if (_frontLength == _input.length) _backLength = _frontLength; 

1551 
} 

1552 


1553 
void ensureBackLength() 

1554 
{ 

1555 
static if (isBidirectionalRange!Range) 

1556 
if (_backLength != _backLength.max) return; 

1557 
assert(!_input.empty); 

1558 
// compute back length 

1559 
static if (isBidirectionalRange!Range) 

1560 
{ 

1561 
_backLength = _input.length  

1562 
find(retro(_input), retro(_separator)).length; 

1563 
} 

1564 
} 

1565 


1566 
public: 

1567 
this(Range input, Separator separator) 

1568 
{ 

1569 
_input = input; 

1570 
_separator = separator; 

1571 
} 

1572 


1573 
@property Range front() 

1574 
{ 

1575 
assert(!empty); 

1576 
ensureFrontLength(); 

1577 
return _input[0 .. _frontLength]; 

1578 
} 

1579 


1580 
static if (isInfinite!Range) 

1581 
{ 

1582 
enum bool empty = false; // Propagate infiniteness 

1583 
} 

1584 
else 

1585 
{ 

1586 
@property bool empty() 

1587 
{ 

1588 
return _frontLength == size_t.max && _input.empty; 

1589 
} 

1590 
} 

1591 


1592 
void popFront() 

1593 
{ 

1594 
assert(!empty); 

1595 
ensureFrontLength; 

1596 
if (_frontLength == _input.length) 

1597 
{ 

1598 
// done, there's no separator in sight 

1599 
_input = _input[_frontLength .. _frontLength]; 

1600 
_frontLength = _frontLength.max; 

1601 
static if (isBidirectionalRange!Range) 

1602 
_backLength = _backLength.max; 

1603 
return; 

1604 
} 

1605 
if (_frontLength + separatorLength == _input.length) 

1606 
{ 

1607 
// Special case: popping the firsttolast item; there is 

1608 
// an empty item right after this. 

1609 
_input = _input[_input.length .. _input.length]; 

1610 
_frontLength = 0; 

1611 
static if (isBidirectionalRange!Range) 

1612 
_backLength = 0; 

1613 
return; 

1614 
} 

1615 
// Normal case, pop one item and the separator, get ready for 

1616 
// reading the next item 

1617 
_input = _input[_frontLength + separatorLength .. _input.length]; 

1618 
// mark _frontLength as uninitialized 

1619 
_frontLength = _frontLength.max; 

1620 
} 

1621 


1622 
static if(isForwardRange!Range) 

1623 
{ 

1624 
@property typeof(this) save() 

1625 
{ 

1626 
auto ret = this; 

1627 
ret._input = _input.save; 

1628 
return ret; 

1629 
} 

1630 
} 

1631 


1632 
// Bidirectional functionality as suggested by Brad Roberts. 

1633 
static if (isBidirectionalRange!Range) 

1634 
{ 

1635 
@property Range back() 

1636 
{ 

1637 
ensureBackLength; 

1638 
return _input[_input.length  _backLength .. _input.length]; 

1639 
} 

1640 


1641 
void popBack() 

1642 
{ 

1643 
ensureBackLength; 

1644 
if (_backLength == _input.length) 

1645 
{ 

1646 
// done 

1647 
_input = _input[0 .. 0]; 

1648 
_frontLength = _frontLength.max; 

1649 
_backLength = _backLength.max; 

1650 
return; 

1651 
} 

1652 
if (_backLength + separatorLength == _input.length) 

1653 
{ 

1654 
// Special case: popping the firsttofirst item; there is 

1655 
// an empty item right before this. Leave the separator in. 

1656 
_input = _input[0 .. 0]; 

1657 
_frontLength = 0; 

1658 
_backLength = 0; 

1659 
return; 

1660 
} 

1661 
// Normal case 

1662 
_input = _input[0 .. _input.length  _backLength  separatorLength]; 

1663 
_backLength = _backLength.max; 

1664 
} 

1665 
} 

1666 
} 

1667 


1668 
unittest 

1669 
{ 

1670 
debug(std_algorithm) scope(success) 

1671 
writeln("unittest @", __FILE__, ":", __LINE__, " done."); 

1672 
auto s = ",abc, de, fg,hi,"; 

1673 
auto sp0 = splitter(s, ','); 

1674 
// //foreach (e; sp0) writeln("[", e, "]"); 

1675 
assert(equal(sp0, ["", "abc", " de", " fg", "hi", ""][])); 

1676 


1677 
auto s1 = ", abc, de, fg, hi, "; 

1678 
auto sp1 = splitter(s1, ", "); 

1679 
//foreach (e; sp1) writeln("[", e, "]"); 

1680 
assert(equal(sp1, ["", "abc", "de", " fg", "hi", ""][])); 

1681 
static assert(isForwardRange!(typeof(sp1))); 

1682 


1683 
int[] a = [ 1, 2, 0, 3, 0, 4, 5, 0 ]; 

1684 
int[][] w = [ [1, 2], [3], [4, 5], [] ]; 

1685 
uint i; 

1686 
foreach (e; splitter(a, 0)) 

1687 
{ 

1688 
assert(i < w.length); 

1689 
assert(e == w[i++]); 

1690 
} 

1691 
assert(i == w.length); 

1692 
// // Now go back 

1693 
// auto s2 = splitter(a, 0); 

1694 


1695 
// foreach (e; retro(s2)) 

1696 
// { 

1697 
// assert(i > 0); 

1698 
// assert(equal(e, w[i]), text(e)); 

1699 
// } 

1700 
// assert(i == 0); 

1701 


1702 
wstring names = ",peter,paul,jerry,"; 

1703 
auto words = split(names, ","); 

1704 
assert(walkLength(words) == 5, text(walkLength(words))); 

1705 
} 

1706 


1707 
unittest 

1708 
{ 

1709 
debug(std_algorithm) scope(success) 

1710 
writeln("unittest @", __FILE__, ":", __LINE__, " done."); 

1711 
auto s6 = ","; 

1712 
auto sp6 = splitter(s6, ','); 

1713 
foreach (e; sp6) 

1714 
{ 

1715 
//writeln("{", e, "}"); 

1716 
} 

1717 
assert(equal(sp6, ["", ""][])); 

1718 
} 

1719 


1720 
struct Splitter(alias isTerminator, Range, 

1721 
Slice = Select!(is(typeof(Range.init[0 .. 1])), 

1722 
Range, 

1723 
ElementType!(Range)[])) 

1724 
if(!is(isTerminator)) 

1725 
{ 

1726 
private Range _input; 

1727 
private size_t _end; 

1728 
private alias unaryFun!isTerminator _isTerminator; 

1729 


1730 
this(Range input) 

1731 
{ 

1732 
_input = input; 

1733 
if (_input.empty) 

1734 
{ 

1735 
_end = _end.max; 

1736 
} 

1737 
else 

1738 
{ 

1739 
// Chase first terminator 

1740 
while (_end < _input.length && !_isTerminator(_input[_end])) 

1741 
{ 

1742 
++_end; 

1743 
} 

1744 
} 

1745 
} 

1746 


1747 
static if (isInfinite!Range) 

1748 
{ 

1749 
enum bool empty = false; // Propagate infiniteness. 

1750 
} 

1751 
else 

1752 
{ 

1753 
@property bool empty() 

1754 
{ 

1755 
return _end == _end.max; 

1756 
} 

1757 
} 

1758 


1759 
@property Range front() 

1760 
{ 

1761 
assert(!empty); 

1762 
return _input[0 .. _end]; 

1763 
} 

1764 


1765 
void popFront() 

1766 
{ 

1767 
assert(!empty); 

1768 
if (_input.empty) 

1769 
{ 

1770 
_end = _end.max; 

1771 
return; 

1772 
} 

1773 
// Skip over existing word 

1774 
_input = _input[_end .. _input.length]; 

1775 
// Skip terminator 

1776 
for (;;) 

1777 
{ 

1778 
if (_input.empty) 

1779 
{ 

1780 
// Nothing following the terminator  done 

1781 
_end = _end.max; 

1782 
return; 

1783 
} 

1784 
if (!_isTerminator(_input.front)) 

1785 
{ 

1786 
// Found a legit next field 

1787 
break; 

1788 
} 

1789 
_input.popFront(); 

1790 
} 

1791 
assert(!_input.empty && !_isTerminator(_input.front)); 

1792 
// Prepare _end 

1793 
_end = 1; 

1794 
while (_end < _input.length && !_isTerminator(_input[_end])) 

1795 
{ 

1796 
++_end; 

1797 
} 

1798 
} 

1799 


1800 
static if(isForwardRange!Range) 

1801 
{ 

1802 
@property typeof(this) save() 

1803 
{ 

1804 
auto ret = this; 

1805 
ret._input = _input.save; 

1806 
return ret; 

1807 
} 

1808 
} 

1809 
} 

1810 


1811 
Splitter!(isTerminator, Range) 

1812 
splitter(alias isTerminator, Range)(Range input) 

1813 
if (is(typeof(unaryFun!(isTerminator)(ElementType!(Range).init)))) 

1814 
{ 

1815 
return typeof(return)(input); 

1816 
} 

1817 


1818 
unittest 

1819 
{ 

1820 
debug(std_algorithm) scope(success) 

1821 
writeln("unittest @", __FILE__, ":", __LINE__, " done."); 

1822 
void compare(string sentence, string[] witness) 

1823 
{ 

1824 
foreach (word; splitter!"a == ' '"(sentence)) 

1825 
{ 

1826 
assert(word == witness.front, word); 

1827 
witness.popFront(); 

1828 
} 

1829 
assert(witness.empty, witness[0]); 

1830 
} 

1831 


1832 
compare(" Mary has a little lamb. ", 

1833 
["", "Mary", "has", "a", "little", "lamb."]); 

1834 
compare("Mary has a little lamb. ", 

1835 
["Mary", "has", "a", "little", "lamb."]); 

1836 
compare("Mary has a little lamb.", 

1837 
["Mary", "has", "a", "little", "lamb."]); 

1838 
compare("", []); 

1839 
compare(" ", [""]); 

1840 


1841 
static assert(isForwardRange!(typeof(splitter!"a == ' '"("ABC")))); 

1842 


1843 
foreach(DummyType; AllDummyRanges) 

1844 
{ 

1845 
static if(isRandomAccessRange!DummyType) 

1846 
{ 

1847 
auto rangeSplit = splitter!"a == 5"(DummyType.init); 

1848 
assert(equal(rangeSplit.front, [1,2,3,4])); 

1849 
rangeSplit.popFront(); 

1850 
assert(equal(rangeSplit.front, [6,7,8,9,10])); 

1851 
} 

1852 
} 

1853 
} 

1854 


1855 
// joiner 

1856 
/** 

1857 
Lazily joins a range of ranges with a separator. The separator itself 

1858 
is a range. 

1859 


1860 
Example: 

1861 
 

1862 
assert(equal(joiner([""], "xyz"), "")); 

1863 
assert(equal(joiner(["", ""], "xyz"), "xyz")); 

1864 
assert(equal(joiner(["", "abc"], "xyz"), "xyzabc")); 

1865 
assert(equal(joiner(["abc", ""], "xyz"), "abcxyz")); 

1866 
assert(equal(joiner(["abc", "def"], "xyz"), "abcxyzdef")); 

1867 
assert(equal(joiner(["Mary", "has", "a", "little", "lamb"], "..."), 

1868 
"Mary...has...a...little...lamb")); 

1869 
 

1870 
*/ 

1871 
auto joiner(RoR, Separator)(RoR r, Separator sep) 

1872 
if (isForwardRange!RoR && isInputRange!(ElementType!RoR) 

1873 
&& isForwardRange!Separator 

1874 
&& is(ElementType!Separator : ElementType!(ElementType!RoR))) 

1875 
{ 

1876 
static struct Result 

1877 
{ 

1878 
private RoR _items; 

1879 
private ElementType!RoR _current; 

1880 
private Separator _sep, _currentSep; 

1881 


1882 
private void useSeparator() 

1883 
{ 

1884 
assert(_currentSep.empty && _current.empty, 

1885 
"joiner: internal error"); 

1886 
if (_sep.empty) 

1887 
{ 

1888 
// Advance to the next range in the 

1889 
// input 

1890 
//_items.popFront(); 

1891 
for (;; _items.popFront()) 

1892 
{ 

1893 
if (_items.empty) return; 

1894 
if (!_items.front.empty) break; 

1895 
} 

1896 
_current = _items.front; 

1897 
_items.popFront(); 

1898 
} 

1899 
else 

1900 
{ 

1901 
// Must make sure something is coming after the 

1902 
// separator  it's a separator, not a terminator! 

1903 
if (_items.empty) return; 

1904 
_currentSep = _sep.save; 

1905 
assert(!_currentSep.empty); 

1906 
} 

1907 
} 

1908 


1909 
private void useItem() 

1910 
{ 

1911 
assert(_currentSep.empty && _current.empty, 

1912 
"joiner: internal error"); 

1913 
// Use the input 

1914 
if (_items.empty) return; 

1915 
_current = _items.front; 

1916 
_items.popFront(); 

1917 
if (!_current.empty) 

1918 
{ 

1919 
return; 

1920 
} 

1921 
// No data in the current item  toggle to use the 

1922 
// separator 

1923 
useSeparator(); 

1924 
} 

1925 


1926 
this(RoR items, Separator sep) 

1927 
{ 

1928 
_items = items; 

1929 
_sep = sep; 

1930 
useItem(); 

1931 
// We need the separator if the input has at least two 

1932 
// elements 

1933 
if (_current.empty && _items.empty) 

1934 
{ 

1935 
// Vacate the whole thing 

1936 
_currentSep = _currentSep.init; 

1937 
} 

1938 
} 

1939 


1940 
@property auto empty() 

1941 
{ 

1942 
return _current.empty && _currentSep.empty; 

1943 
} 

1944 


1945 
@property ElementType!(ElementType!RoR) front() 

1946 
{ 

1947 
if (!_currentSep.empty) return _currentSep.front; 

1948 
assert(!_current.empty); 

1949 
return _current.front; 

1950 
} 

1951 


1952 
void popFront() 

1953 
{ 

1954 
assert(!empty); 

1955 
// Using separator? 

1956 
if (!_currentSep.empty) 

1957 
{ 

1958 
_currentSep.popFront(); 

1959 
if (!_currentSep.empty) return; 

1960 
useItem(); 

1961 
} 

1962 
else 

1963 
{ 

1964 
// we're using the range 

1965 
_current.popFront(); 

1966 
if (!_current.empty) return; 

1967 
useSeparator(); 

1968 
} 

1969 
} 

1970 


1971 
static if (isForwardRange!RoR && isForwardRange!(ElementType!RoR)) 

1972 
{ 

1973 
@property auto save() 

1974 
{ 

1975 
Result copy; 

1976 
copy._items = _items.save; 

1977 
copy._current = _current.save; 

1978 
copy._sep = _sep.save; 

1979 
copy._currentSep = _currentSep.save; 

1980 
return copy; 

1981 
} 

1982 
} 

1983 
} 

1984 
return Result(r, sep); 

1985 
} 

1986 


1987 
unittest 

1988 
{ 

1989 
debug(std_algorithm) scope(success) 

1990 
writeln("unittest @", __FILE__, ":", __LINE__, " done."); 

1991 
static assert(isInputRange!(typeof(joiner([""], "")))); 

1992 
static assert(isForwardRange!(typeof(joiner([""], "")))); 

1993 
assert(equal(joiner([""], "xyz"), ""), text(joiner([""], "xyz"))); 

1994 
assert(equal(joiner(["", ""], "xyz"), "xyz"), text(joiner(["", ""], "xyz"))); 

1995 
assert(equal(joiner(["", "abc"], "xyz"), "xyzabc")); 

1996 
assert(equal(joiner(["abc", ""], "xyz"), "abcxyz")); 

1997 
assert(equal(joiner(["abc", "def"], "xyz"), "abcxyzdef")); 

1998 
assert(equal(joiner(["Mary", "has", "a", "little", "lamb"], "..."), 

1999 
"Mary...has...a...little...lamb")); 

2000 
} 

2001 


2002 
auto joiner(RoR)(RoR r) 

2003 
if (isInputRange!RoR && isInputRange!(ElementType!RoR)) 

2004 
{ 

2005 
static struct Result 

2006 
{ 

2007 
private: 

2008 
RoR _items; 

2009 
ElementType!RoR _current; 

2010 
void prepare() 

2011 
{ 

2012 
for (;; _items.popFront()) 

2013 
{ 

2014 
if (_items.empty) return; 

2015 
if (!_items.front.empty) break; 

2016 
} 

2017 
_current = _items.front; 

2018 
_items.popFront(); 

2019 
} 

2020 
public: 

2021 
this(RoR r) 

2022 
{ 

2023 
_items = r; 

2024 
prepare(); 

2025 
} 

2026 
static if (isInfinite!(ElementType!RoR)) 

2027 
{ 

2028 
enum bool empty = false; 

2029 
} 

2030 
else 

2031 
{ 

2032 
@property auto empty() 

2033 
{ 

2034 
return _current.empty; 

2035 
} 

2036 
} 

2037 
@property auto ref front() 

2038 
{ 

2039 
assert(!empty); 

2040 
return _current.front; 

2041 
} 

2042 
void popFront() 

2043 
{ 

2044 
assert(!_current.empty); 

2045 
_current.popFront(); 

2046 
if (_current.empty) prepare(); 

2047 
} 

2048 
static if (isForwardRange!RoR && isForwardRange!(ElementType!RoR)) 

2049 
{ 

2050 
@property auto save() 

2051 
{ 

2052 
Result copy; 

2053 
copy._items = _items.save; 

2054 
copy._current = _current.save; 

2055 
return copy; 

2056 
} 

2057 
} 

2058 
} 

2059 
return Result(r); 

2060 
} 

2061 


2062 
unittest 

2063 
{ 

2064 
debug(std_algorithm) scope(success) 

2065 
writeln("unittest @", __FILE__, ":", __LINE__, " done."); 

2066 
static assert(isInputRange!(typeof(joiner([""])))); 

2067 
static assert(isForwardRange!(typeof(joiner([""])))); 

2068 
assert(equal(joiner([""]), "")); 

2069 
assert(equal(joiner(["", ""]), "")); 

2070 
assert(equal(joiner(["", "abc"]), "abc")); 

2071 
assert(equal(joiner(["abc", ""]), "abc")); 

2072 
assert(equal(joiner(["abc", "def"]), "abcdef")); 

2073 
assert(equal(joiner(["Mary", "has", "a", "little", "lamb"]), 

2074 
"Maryhasalittlelamb")); 

2075 
assert(equal(joiner(std.range.repeat("abc", 3)), "abcabcabc")); 

2076 


2077 
// joiner allows inplace mutation! 

2078 
auto a = [ [1, 2, 3], [42, 43] ]; 

2079 
auto j = joiner(a); 

2080 
j.front() = 44; 

2081 
assert(a == [ [44, 2, 3], [42, 43] ]); 

2082 
} 

2083 


2084 
// uniq 

2085 
/** 

2086 
Iterates unique consecutive elements of the given range (functionality 

2087 
akin to the $(WEB wikipedia.org/wiki/_Uniq, _uniq) system 

2088 
utility). Equivalence of elements is assessed by using the predicate 

2089 
$(D pred), by default $(D "a == b"). If the given range is 

2090 
bidirectional, $(D uniq) also yields a bidirectional range. 

2091 


2092 
Example: 

2093 
 

2094 
int[] arr = [ 1, 2, 2, 2, 2, 3, 4, 4, 4, 5 ]; 

2095 
assert(equal(uniq(arr), [ 1, 2, 3, 4, 5 ][])); 

2096 
 

2097 
*/ 

2098 
struct Uniq(alias pred, R) 

2099 
{ 

2100 
R _input; 

2101 


2102 
this(R input) 

2103 
{ 

2104 
_input = input; 

2105 
} 

2106 


2107 
ref Uniq opSlice() 

2108 
{ 

2109 
return this; 

2110 
} 

2111 


2112 
void popFront() 

2113 
{ 

2114 
auto last = _input.front; 

2115 
do 

2116 
{ 

2117 
_input.popFront; 

2118 
} 

2119 
while (!_input.empty && binaryFun!(pred)(last, _input.front)); 

2120 
} 

2121 


2122 
@property ElementType!(R) front() { return _input.front; } 

2123 


2124 
static if (isBidirectionalRange!R) 

2125 
{ 

2126 
void popBack() 

2127 
{ 

2128 
auto last = _input.back; 

2129 
do 

2130 
{ 

2131 
_input.popBack; 

2132 
} 

2133 
while (!_input.empty && binaryFun!(pred)(last, _input.back)); 

2134 
} 

2135 


2136 
@property ElementType!(R) back() { return _input.back; } 

2137 
} 

2138 


2139 
static if (isInfinite!R) 

2140 
{ 

2141 
enum bool empty = false; // Propagate infiniteness. 

2142 
} 

2143 
else 

2144 
{ 

2145 
@property bool empty() { return _input.empty; } 

2146 
} 

2147 


2148 


2149 
static if (isForwardRange!R) { 

2150 
@property typeof(this) save() { 

2151 
return typeof(this)(_input.save); 

2152 
} 

2153 
} 

2154 
} 

2155 


2156 
/// Ditto 

2157 
Uniq!(pred, Range) uniq(alias pred = "a == b", Range)(Range r) 

2158 
{ 

2159 
return typeof(return)(r); 

2160 
} 

2161 


2162 
unittest 

2163 
{ 

2164 
debug(std_algorithm) scope(success) 

2165 
writeln("unittest @", __FILE__, ":", __LINE__, " done."); 

2166 
int[] arr = [ 1, 2, 2, 2, 2, 3, 4, 4, 4, 5 ]; 

2167 
auto r = uniq(arr); 

2168 
static assert(isForwardRange!(typeof(r))); 

2169 


2170 
assert(equal(r, [ 1, 2, 3, 4, 5 ][])); 

2171 
assert(equal(retro(r), retro([ 1, 2, 3, 4, 5 ][]))); 

2172 


2173 
foreach(DummyType; AllDummyRanges) { 

2174 
DummyType d; 

2175 
auto u = uniq(d); 

2176 
assert(equal(u, [1,2,3,4,5,6,7,8,9,10])); 

2177 


2178 
static assert(d.rt == RangeType.Input  isForwardRange!(typeof(u))); 

2179 


2180 
static if (d.rt >= RangeType.Bidirectional) { 

2181 
assert(equal(retro(u), [10,9,8,7,6,5,4,3,2,1])); 

2182 
} 

2183 
} 

2184 
} 

2185 


2186 
// group 

2187 
/** 

2188 
Similarly to $(D uniq), $(D group) iterates unique consecutive 

2189 
elements of the given range. The element type is $(D 

2190 
Tuple!(ElementType!R, uint)) because it includes the count of 

2191 
equivalent elements seen. Equivalence of elements is assessed by using 

2192 
the predicate $(D pred), by default $(D "a == b"). 

2193 


2194 
$(D Group) is an input range if $(D R) is an input range, and a 

2195 
forward range in all other cases. 

2196 


2197 
Example: 

2198 
 

2199 
int[] arr = [ 1, 2, 2, 2, 2, 3, 4, 4, 4, 5 ]; 

2200 
assert(equal(group(arr), [ tuple(1, 1u), tuple(2, 4u), tuple(3, 1u), 

2201 
tuple(4, 3u), tuple(5, 1u) ][])); 

2202 
 

2203 
*/ 

2204 
struct Group(alias pred, R) if (isInputRange!R) 

2205 
{ 

2206 
private R _input; 

2207 
private Tuple!(ElementType!R, uint) _current; 

2208 
private alias binaryFun!pred comp; 

2209 


2210 
this(R input) 

2211 
{ 

2212 
_input = input; 

2213 
if (!_input.empty) popFront; 

2214 
} 

2215 


2216 
void popFront() 

2217 
{ 

2218 
if (_input.empty) 

2219 
{ 

2220 
_current[1] = 0; 

2221 
} 

2222 
else 

2223 
{ 

2224 
_current = tuple(_input.front, 1u); 

2225 
_input.popFront; 

2226 
while (!_input.empty && comp(_current[0], _input.front)) 

2227 
{ 

2228 
++_current[1]; 

2229 
_input.popFront; 

2230 
} 

2231 
} 

2232 
} 

2233 


2234 
static if (isInfinite!R) 

2235 
{ 

2236 
enum bool empty = false; // Propagate infiniteness. 

2237 
} 

2238 
else 

2239 
{ 

2240 
@property bool empty() 

2241 
{ 

2242 
return _current[1] == 0; 

2243 
} 

2244 
} 

2245 


2246 
@property ref Tuple!(ElementType!R, uint) front() 

2247 
{ 

2248 
assert(!empty); 

2249 
return _current; 

2250 
} 

2251 


2252 
static if (isForwardRange!R) { 

2253 
@property typeof(this) save() { 

2254 
typeof(this) ret; 

2255 
ret._input = this._input.save; 

2256 
ret._current = this._current; 

2257 


2258 
return ret; 

2259 
} 

2260 
} 

2261 
} 

2262 


2263 
/// Ditto 

2264 
Group!(pred, Range) group(alias pred = "a == b", Range)(Range r) 

2265 
{ 

2266 
return typeof(return)(r); 

2267 
} 

2268 


2269 
unittest 

2270 
{ 

2271 
debug(std_algorithm) scope(success) 

2272 
writeln("unittest @", __FILE__, ":", __LINE__, " done."); 

2273 
int[] arr = [ 1, 2, 2, 2, 2, 3, 4, 4, 4, 5 ]; 

2274 
assert(equal(group(arr), [ tuple(1, 1u), tuple(2, 4u), tuple(3, 1u), 

2275 
tuple(4, 3u), tuple(5, 1u) ][])); 

2276 
static assert(isForwardRange!(typeof(group(arr)))); 

2277 


2278 
foreach(DummyType; AllDummyRanges) { 

2279 
DummyType d; 

2280 
auto g = group(d); 

2281 


2282 
static assert(d.rt == RangeType.Input  isForwardRange!(typeof(g))); 

2283 


2284 
assert(equal(g, [tuple(1, 1u), tuple(2, 1u), tuple(3, 1u), tuple(4, 1u), 

2285 
tuple(5, 1u), tuple(6, 1u), tuple(7, 1u), tuple(8, 1u), 

2286 
tuple(9, 1u), tuple(10, 1u)])); 

2287 
} 

2288 
} 

2289 


2290 
// overwriteAdjacent 

2291 
/* 

2292 
Reduces $(D r) by shifting it to the left until no adjacent elements 

2293 
$(D a), $(D b) remain in $(D r) such that $(D pred(a, b)). Shifting is 

2294 
performed by evaluating $(D move(source, target)) as a primitive. The 

2295 
algorithm is stable and runs in $(BIGOH r.length) time. Returns the 

2296 
reduced range. 

2297 


2298 
The default $(XREF _algorithm, move) performs a potentially 

2299 
destructive assignment of $(D source) to $(D target), so the objects 

2300 
beyond the returned range should be considered "empty". By default $(D 

2301 
pred) compares for equality, in which case $(D overwriteAdjacent) 

2302 
collapses adjacent duplicate elements to one (functionality akin to 

2303 
the $(WEB wikipedia.org/wiki/Uniq, uniq) system utility). 

2304 


2305 
Example: 

2306 
 

2307 
int[] arr = [ 1, 2, 2, 2, 2, 3, 4, 4, 4, 5 ]; 

2308 
auto r = overwriteAdjacent(arr); 

2309 
assert(r == [ 1, 2, 3, 4, 5 ]); 

2310 
 

2311 
*/ 

2312 
// Range overwriteAdjacent(alias pred, alias move, Range)(Range r) 

2313 
// { 

2314 
// if (r.empty) return r; 

2315 
// //auto target = begin(r), e = end(r); 

2316 
// auto target = r; 

2317 
// auto source = r; 

2318 
// source.popFront; 

2319 
// while (!source.empty) 

2320 
// { 

2321 
// if (!pred(target.front, source.front)) 

2322 
// { 

2323 
// target.popFront; 

2324 
// continue; 

2325 
// } 

2326 
// // found an equal *source and *target 

2327 
// for (;;) 

2328 
// { 

2329 
// //@@@ 

2330 
// //move(source.front, target.front); 

2331 
// target[0] = source[0]; 

2332 
// source.popFront; 

2333 
// if (source.empty) break; 

2334 
// if (!pred(target.front, source.front)) target.popFront; 

2335 
// } 

2336 
// break; 

2337 
// } 

2338 
// return range(begin(r), target + 1); 

2339 
// } 

2340 


2341 
// /// Ditto 

2342 
// Range overwriteAdjacent( 

2343 
// string fun = "a == b", 

2344 
// alias move = .move, 

2345 
// Range)(Range r) 

2346 
// { 

2347 
// return .overwriteAdjacent!(binaryFun!(fun), move, Range)(r); 

2348 
// } 

2349 


2350 
// unittest 

2351 
// { 

2352 
// int[] arr = [ 1, 2, 2, 2, 2, 3, 4, 4, 4, 5 ]; 

2353 
// auto r = overwriteAdjacent(arr); 

2354 
// assert(r == [ 1, 2, 3, 4, 5 ]); 

2355 
// assert(arr == [ 1, 2, 3, 4, 5, 3, 4, 4, 4, 5 ]); 

2356 


2357 
// } 

2358 


2359 
// find 

2360 
/** 

2361 
Finds an individual element in an input range. Elements of $(D 

2362 
haystack) are compared with $(D needle) by using predicate $(D 

2363 
pred). Performs $(BIGOH walkLength(haystack)) evaluations of $(D 

2364 
pred). See also $(WEB sgi.com/tech/stl/_find.html, STL's _find). 

2365 


2366 
To _find the last occurence of $(D needle) in $(D haystack), call $(D 

2367 
find(retro(haystack), needle)). See also $(XREF range, retro). 

2368 


2369 
Params: 

2370 


2371 
haystack = The range searched in. 

2372 


2373 
needle = The element searched for. 

2374 


2375 
Constraints: 

2376 


2377 
$(D isInputRange!R && is(typeof(binaryFun!pred(haystack.front, needle) 

2378 
: bool))) 

2379 


2380 
Returns: 

2381 


2382 
$(D haystack) advanced such that $(D binaryFun!pred(haystack.front, 

2383 
needle)) is $(D true) (if no such position exists, returns $(D 

2384 
haystack) after exhaustion). 

2385 


2386 
Example: 

2387 


2388 
 

2389 
assert(find("hello, world", ',') == ", world"); 

2390 
assert(find([1, 2, 3, 5], 4) == []); 

2391 
assert(find(SList!int(1, 2, 3, 4, 5)[], 4) == SList!int(4, 5)[]); 

2392 
assert(find!"a > b"([1, 2, 3, 5], 2) == [3, 5]); 

2393 


2394 
auto a = [ 1, 2, 3 ]; 

2395 
assert(find(a, 5).empty); // not found 

2396 
assert(!find(a, 2).empty); // found 

2397 


2398 
// Caseinsensitive find of a string 

2399 
string[] s = [ "Hello", "world", "!" ]; 

2400 
assert(!find!("tolower(a) == b")(s, "hello").empty); 

2401 
 

2402 
*/ 

2403 
R find(alias pred = "a == b", R, E)(R haystack, E needle) 

2404 
if (isInputRange!R && 

2405 
is(typeof(binaryFun!pred(haystack.front, needle)) : bool)) 

2406 
{ 

2407 
for (; !haystack.empty; haystack.popFront()) 

2408 
{ 

2409 
if (binaryFun!pred(haystack.front, needle)) break; 

2410 
} 

2411 
return haystack; 

2412 
} 

2413 


2414 
unittest 

2415 
{ 

2416 
debug(std_algorithm) scope(success) 

2417 
writeln("unittest @", __FILE__, ":", __LINE__, " done."); 

2418 
auto lst = SList!int(1, 2, 5, 7, 3); 

2419 
assert(lst.front == 1); 

2420 
auto r = find(lst[], 5); 

2421 
assert(equal(r, SList!int(5, 7, 3)[])); 

2422 
assert(find([1, 2, 3, 5], 4).empty); 

2423 
} 

2424 


2425 
/** 

2426 
Finds a forward range in another. Elements are compared for 

2427 
equality. Performs $(BIGOH walkLength(haystack) * walkLength(needle)) 

2428 
comparisons in the worst case. Specializations taking advantage of 

2429 
bidirectional or random access (where present) may accelerate search 

2430 
depending on the statistics of the two ranges' content. 

2431 


2432 
Params: 

2433 


2434 
haystack = The range searched in. 

2435 


2436 
needle = The range searched for. 

2437 


2438 
Constraints: 

2439 


2440 
$(D isForwardRange!R1 && isForwardRange!R2 && 

2441 
is(typeof(binaryFun!pred(haystack.front, needle.front) : bool))) 

2442 


2443 
Returns: 

2444 


2445 
$(D haystack) advanced such that $(D needle) is a prefix of it (if no 

2446 
such position exists, returns $(D haystack) advanced to termination). 

2447 


2448 
 

2449 
assert(find("hello, world", "World").empty); 

2450 
assert(find("hello, world", "wo") == "world"); 

2451 
assert(find([1, 2, 3, 4], SList!(2, 3)[]) == [2, 3, 4]); 

2452 
 

2453 
*/ 

2454 
R1 find(alias pred = "a == b", R1, R2)(R1 haystack, R2 needle) 

2455 
if (isForwardRange!R1 && isForwardRange!R2 

2456 
&& is(typeof(binaryFun!pred(haystack.front, needle.front)) : bool) 

2457 
&& !isRandomAccessRange!R1) 

2458 
{ 

2459 
static if (is(typeof(pred == "a == b")) && pred == "a == b" && isSomeString!R1 && isSomeString!R2 

2460 
&& haystack[0].sizeof == needle[0].sizeof) 

2461 
{ 

2462 
//return cast(R1) find(representation(haystack), representation(needle)); 

2463 
// Specialization for simple string search 

2464 
alias Select!(haystack[0].sizeof == 1, ubyte[], 

2465 
Select!(haystack[0].sizeof == 2, ushort[], uint[])) 

2466 
Representation; 

2467 
// Will use the array specialization 

2468 
return cast(R1) .find!(pred, Representation, Representation) 

2469 
(cast(Representation) haystack, cast(Representation) needle); 

2470 
} 

2471 
else 

2472 
{ 

2473 
return simpleMindedFind!pred(haystack, needle); 

2474 
} 

2475 
} 

2476 


2477 
unittest 

2478 
{ 

2479 
debug(std_algorithm) scope(success) 

2480 
writeln("unittest @", __FILE__, ":", __LINE__, " done."); 

2481 
auto lst = SList!int(1, 2, 5, 7, 3); 

2482 
static assert(isForwardRange!(int[])); 

2483 
static assert(isForwardRange!(typeof(lst[]))); 

2484 
auto r = find(lst[], [2, 5]); 

2485 
assert(equal(r, SList!int(2, 5, 7, 3)[])); 

2486 
} 

2487 


2488 
// Specialization for searching a randomaccess range for a 

2489 
// bidirectional range 

2490 
R1 find(alias pred = "a == b", R1, R2)(R1 haystack, R2 needle) 

2491 
if (isRandomAccessRange!R1 && isBidirectionalRange!R2 

2492 
&& is(typeof(binaryFun!pred(haystack.front, needle.front)) : bool)) 

2493 
{ 

2494 
if (needle.empty) return haystack; 

2495 
const needleLength = walkLength(needle); 

2496 
if (needleLength > haystack.length) 

2497 
{ 

2498 
// @@@BUG@@@ 

2499 
//return haystack[$ .. $]; 

2500 
return haystack[haystack.length .. haystack.length]; 

2501 
} 

2502 
// @@@BUG@@@ 

2503 
// auto needleBack = moveBack(needle); 

2504 
// Stage 1: find the step 

2505 
size_t step = 1; 

2506 
auto needleBack = needle.back; 

2507 
needle.popBack(); 

2508 
for (auto i = needle.save; !i.empty && !binaryFun!pred(i.back, needleBack); 

2509 
i.popBack(), ++step) 

2510 
{ 

2511 
} 

2512 
// Stage 2: linear find 

2513 
size_t scout = needleLength  1; 

2514 
for (;;) 

2515 
{ 

2516 
if (scout >= haystack.length) 

2517 
{ 

2518 
return haystack[haystack.length .. haystack.length]; 

2519 
} 

2520 
if (!binaryFun!pred(haystack[scout], needleBack)) 

2521 
{ 

2522 
++scout; 

2523 
continue; 

2524 
} 

2525 
// Found a match with the last element in the needle 

2526 
auto cand = haystack[scout + 1  needleLength .. haystack.length]; 

2527 
if (startsWith!pred(cand, needle)) 

2528 
{ 

2529 
// found 

2530 
return cand; 

2531 
} 

2532 
// Continue with the stride 

2533 
scout += step; 

2534 
} 

2535 
} 

2536 


2537 
unittest 

2538 
{ 

2539 
//scope(success) writeln("unittest @", __FILE__, ":", __LINE__, " done."); 

2540 
// @@@BUG@@@ removing static below makes unittest fail 

2541 
static struct BiRange 

2542 
{ 

2543 
int[] payload; 

2544 
@property bool empty() { return payload.empty; } 

2545 
@property BiRange save() { return this; } 

2546 
@property ref int front() { return payload[0]; } 

2547 
@property ref int back() { return payload[$  1]; } 

2548 
void popFront() { return payload.popFront(); } 

2549 
void popBack() { return payload.popBack(); } 

2550 
} 

2551 
//static assert(isBidirectionalRange!BiRange); 

2552 
auto r = BiRange([1, 2, 3, 10, 11, 4]); 

2553 
//assert(equal(find(r, [3, 10]), BiRange([3, 10, 11, 4]))); 

2554 
//assert(find("abc", "bc").length == 2); 

2555 
debug(std_algorithm) scope(success) 

2556 
writeln("unittest @", __FILE__, ":", __LINE__, " done."); 

2557 
//assert(find!"a == b"("abc", "bc").length == 2); 

2558 
} 

2559 


2560 
// Leftover specialization: searching a randomaccess range for a 

2561 
// nonbidirectional forward range 

2562 
R1 find(alias pred = "a == b", R1, R2)(R1 haystack, R2 needle) 

2563 
if (isRandomAccessRange!R1 && isForwardRange!R2 && !isBidirectionalRange!R2 

2564 
&& is(typeof(binaryFun!pred(haystack.front, needle.front)) : bool)) 

2565 
{ 

2566 
static if (!is(ElementType!R1 == ElementType!R2)) 

2567 
{ 

2568 
return simpleMindedFind!pred(haystack, needle); 

2569 
} 

2570 
else 

2571 
{ 

2572 
// Prepare the search with needle's first element 

2573 
if (needle.empty) return haystack; 

2574 
haystack = .find!pred(haystack, needle.front); 

2575 
if (haystack.empty) return haystack; 

2576 
needle.popFront(); 

2577 
size_t matchLen = 1; 

2578 
// Loop invariant: haystack[0 .. matchLen] matches everything in 

2579 
// the initial needle that was popped out of needle. 

2580 
for (;;) 

2581 
{ 

2582 
// Extend matchLength as much as possible 

2583 
for (;;) 

2584 
{ 

2585 
if (needle.empty  haystack.empty) return haystack; 

2586 
if (!binaryFun!pred(haystack[matchLen], needle.front)) break; 

2587 
++matchLen; 

2588 
needle.popFront(); 

2589 
} 

2590 
auto bestMatch = haystack[0 .. matchLen]; 

2591 
haystack.popFront(); 

2592 
haystack = .find!pred(haystack, bestMatch); 

2593 
} 

2594 
} 

2595 
} 

2596 


2597 
unittest 

2598 
{ 

2599 
assert(find([ 1, 2, 3 ], SList!int(2, 3)[]) == [ 2, 3 ]); 

2600 
assert(find([ 1, 2, 1, 2, 3, 3 ], SList!int(2, 3)[]) == [ 2, 3, 3 ]); 

2601 
} 

2602 


2603 
// Internally used by some find() overloads above. Can't make it 

2604 
// private due to bugs in the compiler. 

2605 
/*private*/ R1 simpleMindedFind(alias pred, R1, R2)(R1 haystack, R2 needle) 

2606 
{ 

2607 
enum estimateNeedleLength = hasLength!R1 && !hasLength!R2; 

2608 


2609 
static if (hasLength!R1) 

2610 
{ 

2611 
static if (hasLength!R2) 

2612 
size_t estimatedNeedleLength = 0; 

2613 
else 

2614 
immutable size_t estimatedNeedleLength = needle.length; 

2615 
} 

2616 


2617 
bool haystackTooShort() 

2618 
{ 

2619 
static if (hasLength!R1) 

2620 
{ 

2621 
return haystack.length < estimatedNeedleLength; 

2622 
} 

2623 
else 

2624 
{ 

2625 
return haystack.empty; 

2626 
} 

2627 
} 

2628 


2629 
searching: 

2630 
for (;; haystack.popFront()) 

2631 
{ 

2632 
if (haystackTooShort()) 

2633 
{ 

2634 
// Failed search 

2635 
static if (hasLength!R1) 

2636 
{ 

2637 
static if (is(typeof(haystack[haystack.length .. 

2638 
haystack.length]) : R1)) 

2639 
return haystack[haystack.length .. haystack.length]; 

2640 
else 

2641 
return R1.init; 

2642 
} 

2643 
else 

2644 
{ 

2645 
assert(haystack.empty); 

2646 
return haystack; 

2647 
} 

2648 
} 

2649 
static if (estimateNeedleLength) 

2650 
size_t matchLength = 0; 

2651 
for (auto h = haystack.save, n = needle.save; 

2652 
!n.empty; 

2653 
h.popFront(), n.popFront()) 

2654 
{ 

2655 
if (h.empty  !binaryFun!pred(h.front, n.front)) 

2656 
{ 

2657 
// Failed searching n in h 

2658 
static if (estimateNeedleLength) 

2659 
{ 

2660 
if (estimatedNeedleLength < matchLength) 

2661 
estimatedNeedleLength = matchLength; 

2662 
} 

2663 
continue searching; 

2664 
} 

2665 
static if (estimateNeedleLength) 

2666 
++matchLength; 

2667 
} 

2668 
break; 

2669 
} 

2670 
return haystack; 

2671 
} 

2672 


2673 
/** 

2674 
Finds two or more $(D needles) into a $(D haystack). The predicate $(D 

2675 
pred) is used throughout to compare elements. By default, elements are 

2676 
compared for equality. 

2677 


2678 
Params: 

2679 


2680 
haystack = The target of the search. Must be an $(GLOSSARY input 

2681 
range). If any of $(D needles) is a range with elements comparable to 

2682 
elements in $(D haystack), then $(D haystack) must be a $(GLOSSARY 

2683 
forward range) such that the search can backtrack. 

2684 


2685 
needles = One or more items to search for. Each of $(D needles) must 

2686 
be either comparable to one element in $(D haystack), or be itself a 

2687 
$(GLOSSARY forward range) with elements comparable with elements in 

2688 
$(D haystack). 

2689 


2690 
Returns: 

2691 


2692 
A tuple containing $(D haystack) positioned to match one of the 

2693 
needles and also the 1based index of the matching element in $(D 

2694 
needles) (0 if none of $(D needles) matched, 1 if $(D needles[0]) 

2695 
matched, 2 if $(D needles[1]) matched...). 

2696 


2697 
The relationship between $(D haystack) and $(D needles) simply means 

2698 
that one can e.g. search for individual $(D int)s or arrays of $(D 

2699 
int)s in an array of $(D int)s. In addition, if elements are 

2700 
individually comparable, searches of heterogeneous types are allowed 

2701 
as well: a $(D double[]) can be searched for an $(D int) or a $(D 

2702 
short[]), and conversely a $(D long) can be searched for a $(D float) 

2703 
or a $(D double[]). This makes for efficient searches without the need 

2704 
to coerce one side of the comparison into the other's side type. 

2705 


2706 
Example: 

2707 
 

2708 
int[] a = [ 1, 4, 2, 3 ]; 

2709 
assert(find(a, 4) == [ 4, 2, 3 ]); 

2710 
assert(find(a, [ 1, 4 ]) == [ 1, 4, 2, 3 ]); 

2711 
assert(find(a, [ 1, 3 ], 4) == tuple([ 4, 2, 3 ], 2)); 

2712 
// Mixed types allowed if comparable 

2713 
assert(find(a, 5, [ 1.2, 3.5 ], 2.0, [ 1 ]) == tuple([ 2, 3 ], 3)); 

2714 
 

2715 


2716 
The complexity of the search is $(BIGOH haystack.length * 

2717 
max(needles.length)). (For needles that are individual items, length 

2718 
is considered to be 1.) The strategy used in searching several 

2719 
subranges at once maximizes cache usage by moving in $(D haystack) as 

2720 
few times as possible. 

2721 
*/ 

2722 
Tuple!(Range, size_t) find(alias pred = "a == b", Range, Ranges...) 

2723 
(Range haystack, Ranges needles) 

2724 
if (Ranges.length > 1 && allSatisfy!(isForwardRange, Ranges)) 

2725 
{ 

2726 
for (;; haystack.popFront) 

2727 
{ 

2728 
size_t r = startsWith!pred(haystack, needles); 

2729 
if (r  haystack.empty) 

2730 
{ 

2731 
return tuple(haystack, r); 

2732 
} 

2733 
} 

2734 
} 

2735 


2736 
unittest 

2737 
{ 

2738 
debug(std_algorithm) scope(success) 

2739 
writeln("unittest @", __FILE__, ":", __LINE__, " done."); 

2740 
auto s1 = "Mary has a little lamb"; 

2741 
//writeln(find(s1, "has a", "has an")); 

2742 
assert(find(s1, "has a", "has an") == tuple("has a little lamb", 1)); 

2743 
assert(find("abc", "bc").length == 2); 

2744 
} 

2745 


2746 
unittest 

2747 
{ 

2748 
debug(std_algorithm) scope(success) 

2749 
writeln("unittest @", __FILE__, ":", __LINE__, " done."); 

2750 
int[] a = [ 1, 2, 3 ]; 

2751 
assert(find(a, 5).empty); 

2752 
assert(find(a, 2) == [2, 3]); 

2753 


2754 
foreach (T; TypeTuple!(int, double)) 

2755 
{ 

2756 
auto b = rndstuff!(T)(); 

2757 
if (!b.length) continue; 

2758 
b[$ / 2] = 200; 

2759 
b[$ / 4] = 200; 

2760 
assert(find(b, 200).length == b.length  b.length / 4); 

2761 
} 

2762 


2763 
// Caseinsensitive find of a string 

2764 
string[] s = [ "Hello", "world", "!" ]; 

2765 
//writeln(find!("toupper(a) == toupper(b)")(s, "hello")); 

2766 
assert(find!("toupper(a) == toupper(b)")(s, "hello").length == 3); 

2767 


2768 
static bool f(string a, string b) { return toupper(a) == toupper(b); } 

2769 
assert(find!(f)(s, "hello").length == 3); 

2770 
} 

2771 


2772 
unittest 

2773 
{ 

2774 
debug(std_algorithm) scope(success) 

2775 
writeln("unittest @", __FILE__, ":", __LINE__, " done."); 

2776 
int[] a = [ 1, 2, 3, 2, 6 ]; 

2777 
assert(find(std.range.retro(a), 5).empty); 

2778 
assert(equal(find(std.range.retro(a), 2), [ 2, 3, 2, 1 ][])); 

2779 


2780 
foreach (T; TypeTuple!(int, double)) 

2781 
{ 

2782 
auto b = rndstuff!(T)(); 

2783 
if (!b.length) continue; 

2784 
b[$ / 2] = 200; 

2785 
b[$ / 4] = 200; 

2786 
assert(find(std.range.retro(b), 200).length == 

2787 
b.length  (b.length  1) / 2); 

2788 
} 

2789 
} 

2790 


2791 
unittest 

2792 
{ 

2793 
debug(std_algorithm) scope(success) 

2794 
writeln("unittest @", __FILE__, ":", __LINE__, " done."); 

2795 
int[] a = [ 1, 0, 1, 2, 3, 4, 5 ]; 

2796 
int[] b = [ 1, 2, 3 ]; 

2797 
assert(find(a, b) == [ 1, 2, 3, 4, 5 ]); 

2798 
assert(find(b, a).empty); 

2799 


2800 
foreach(DummyType; AllDummyRanges) { 

2801 
DummyType d; 

2802 
auto findRes = find(d, 5); 

2803 
assert(equal(findRes, [5,6,7,8,9,10])); 

2804 
} 

2805 
} 

2806 


2807 
/// Ditto 

2808 
struct BoyerMooreFinder(alias pred, Range) 

2809 
{ 

2810 
private: 

2811 
size_t skip[]; 

2812 
sizediff_t[ElementType!(Range)] occ; 

2813 
Range needle; 

2814 


2815 
sizediff_t occurrence(ElementType!(Range) c) 

2816 
{ 

2817 
auto p = c in occ; 

2818 
return p ? *p : 1; 

2819 
} 

2820 


2821 
/* 

2822 
This helper function checks whether the last "portion" bytes of 

2823 
"needle" (which is "nlen" bytes long) exist within the "needle" at 

2824 
offset "offset" (counted from the end of the string), and whether the 

2825 
character preceding "offset" is not a match. Notice that the range 

2826 
being checked may reach beyond the beginning of the string. Such range 

2827 
is ignored. 

2828 
*/ 

2829 
static bool needlematch(R)(R needle, 

2830 
size_t portion, size_t offset) 

2831 
{ 

2832 
sizediff_t virtual_begin = needle.length  offset  portion; 

2833 
sizediff_t ignore = 0; 

2834 
if (virtual_begin < 0) { 

2835 
ignore = virtual_begin; 

2836 
virtual_begin = 0; 

2837 
} 

2838 
if (virtual_begin > 0 

2839 
&& needle[virtual_begin  1] == needle[$  portion  1]) 

2840 
return 0; 

2841 


2842 
immutable delta = portion  ignore; 

2843 
return equal(needle[needle.length  delta .. needle.length], 

2844 
needle[virtual_begin .. virtual_begin + delta]); 

2845 
} 

2846 


2847 
public: 

2848 
this(Range needle) 

2849 
{ 

2850 
if (!needle.length) return; 

2851 
this.needle = needle; 

2852 
/* Populate table with the analysis of the needle */ 

2853 
/* But ignoring the last letter */ 

2854 
foreach (i, n ; needle[0 .. $  1]) 

2855 
{ 

2856 
this.occ[n] = i; 

2857 
} 

2858 
/* Preprocess #2: init skip[] */ 

2859 
/* Note: This step could be made a lot faster. 

2860 
* A simple implementation is shown here. */ 

2861 
this.skip = new size_t[needle.length]; 

2862 
foreach (a; 0 .. needle.length) 

2863 
{ 

2864 
size_t value = 0; 

2865 
while (value < needle.length 

2866 
&& !needlematch(needle, a, value)) 

2867 
{ 

2868 
++value; 

2869 
} 

2870 
this.skip[needle.length  a  1] = value; 

2871 
} 

2872 
} 

2873 


2874 
Range beFound(Range haystack) 

2875 
{ 

2876 
if (!needle.length) return haystack; 

2877 
if (needle.length > haystack.length) return haystack[$ .. $]; 

2878 
/* Search: */ 

2879 
auto limit = haystack.length  needle.length; 

2880 
for (size_t hpos = 0; hpos <= limit; ) 

2881 
{ 

2882 
size_t npos = needle.length  1; 

2883 
while (pred(needle[npos], haystack[npos+hpos])) 

2884 
{ 

2885 
if (npos == 0) return haystack[hpos .. $]; 

2886 
npos; 

2887 
} 

2888 
hpos += max(skip[npos], npos  occurrence(haystack[npos+hpos])); 

2889 
} 

2890 
return haystack[$ .. $]; 

2891 
} 

2892 


2893 
@property size_t length() 

2894 
{ 

2895 
return needle.length; 

2896 
} 

2897 
} 

2898 


2899 
/// Ditto 

2900 
BoyerMooreFinder!(binaryFun!(pred), Range) boyerMooreFinder 

2901 
(alias pred = "a == b", Range) 

2902 
(Range needle) if (isRandomAccessRange!(Range)  isSomeString!Range) 

2903 
{ 

2904 
return typeof(return)(needle); 

2905 
} 

2906 


2907 
// Oddly this is not disabled by bug 4759 

2908 
Range1 find(Range1, alias pred, Range2)( 

2909 
Range1 haystack, BoyerMooreFinder!(pred, Range2) needle) 

2910 
{ 

2911 
return needle.beFound(haystack); 

2912 
} 

2913 


2914 
unittest 

2915 
{ 

2916 
debug(std_algorithm) scope(success) 

2917 
writeln("unittest @", __FILE__, ":", __LINE__, " done."); 

2918 
string h = "/homes/aalexand/d/dmd/bin/../lib/libphobos.a(dmain2.o)" 

2919 
"(.gnu.linkonce.tmain+0x74): In function `main' undefined reference" 

2920 
" to `_Dmain':"; 

2921 
string[] ns = ["libphobos", "function", " undefined", "`", ":"]; 

2922 
foreach (n ; ns) { 

2923 
auto p = find(h, boyerMooreFinder(n)); 

2924 
assert(!p.empty); 

2925 
} 

2926 


2927 
int[] a = [ 1, 0, 1, 2, 3, 4, 5 ]; 

2928 
int[] b = [ 1, 2, 3 ]; 

2929 
//writeln(find(a, boyerMooreFinder(b))); 

2930 
assert(find(a, boyerMooreFinder(b)) == [ 1, 2, 3, 4, 5 ]); 

2931 
assert(find(b, boyerMooreFinder(a)).empty); 

2932 
} 

2933 


2934 
/** 

2935 
Advances the input range $(D haystack) by calling $(D haystack.popFront) 

2936 
until either $(D pred(haystack.front)), or $(D 

2937 
haystack.empty). Performs $(BIGOH haystack.length) evaluations of $(D 

2938 
pred). See also $(WEB sgi.com/tech/stl/find_if.html, STL's find_if). 

2939 


2940 
To find the last element of a bidirectional $(D haystack) satisfying 

2941 
$(D pred), call $(D find!(pred)(retro(haystack))). See also $(XREF 

2942 
range, retro). 

2943 


2944 
Example: 

2945 
 

2946 
auto arr = [ 1, 2, 3, 4, 1 ]; 

2947 
assert(find!("a > 2")(arr) == [ 3, 4, 1 ]); 

2948 


2949 
// with predicate alias 

2950 
bool pred(int x) { return x + 1 > 1.5; } 

2951 
assert(find!(pred)(arr) == arr); 

2952 
 

2953 
*/ 

2954 
Range find(alias pred, Range)(Range haystack) if (isInputRange!(Range)) 

2955 
{ 

2956 
alias unaryFun!(pred) predFun; 

2957 
for (; !haystack.empty && !predFun(haystack.front); haystack.popFront) 

2958 
{ 

2959 
} 

2960 
return haystack; 

2961 
} 

2962 


2963 
unittest 

2964 
{ 

2965 
//scope(success) writeln("unittest @", __FILE__, ":", __LINE__, " done."); 

2966 
int[] a = [ 1, 2, 3 ]; 

2967 
assert(find!("a > 2")(a) == [3]); 

2968 
bool pred(int x) { return x + 1 > 1.5; } 

2969 
assert(find!(pred)(a) == a); 

2970 
} 

2971 


2972 
// findSkip 

2973 
/** 

2974 
* If $(D needle) occurs in $(D haystack), positions $(D haystack) 

2975 
* right after the first occurrence of $(D needle) and returns $(D 

2976 
* true). Otherwise, leaves $(D haystack) as is and returns $(D 

2977 
* false). 

2978 
* 

2979 
* Example: 

2980 
 

2981 
string s = "abcdef"; 

2982 
assert(findSkip("abcdef", "cd") && s == "ef"); 

2983 
s = "abcdef"; 

2984 
assert(!findSkip("abcdef", "cxd") && s == "abcdef"); 

2985 
assert(findSkip("abcdef", "def") && s.empty); 

2986 
 

2987 
*/ 

2988 
bool findSkip(alias pred = "a == b", R1, R2)(ref R1 haystack, R2 needle) 

2989 
if (isForwardRange!R1 && isForwardRange!R2 

2990 
&& is(typeof(binaryFun!pred(haystack.front, needle.front)))) 

2991 
{ 

2992 
auto parts = findSplit!pred(haystack, needle); 

2993 
if (parts[1].empty) return false; 

2994 
// found 

2995 
haystack = parts[2]; 

2996 
return true; 

2997 
} 

2998 


2999 
unittest 

3000 
{ 

3001 
string s = "abcdef"; 

3002 
assert(findSkip(s, "cd") && s == "ef"); 

3003 
s = "abcdef"; 

3004 
assert(!findSkip(s, "cxd") && s == "abcdef"); 

3005 
s = "abcdef"; 

3006 
assert(findSkip(s, "def") && s.empty); 

3007 
} 

3008 


3009 
/** 

3010 
These functions find the first occurrence of $(D needle) in $(D 

3011 
haystack) and then split $(D haystack) as follows. 

3012 


3013 
$(D findSplit) returns a tuple $(D result) containing $(I three) 

3014 
ranges. $(D result[0]) is the portion of $(D haystack) before $(D 

3015 
needle), $(D result[1]) is the portion of $(D haystack) that matches 

3016 
$(D needle), and $(D result[2]) is the portion of $(D haystack) after 

3017 
the match. 

3018 


3019 
$(D findSplitBefore) returns a tuple $(D result) containing two 

3020 
ranges. $(D result[0]) is the portion of $(D haystack) before $(D 

3021 
needle), and $(D result[1]) is the balance of $(D haystack) starting 

3022 
with the match. If $(D needle) was not found, $(D result[0]) 

3023 
comprehends $(D haystack) entirely and $(D result[1]) is empty. 

3024 


3025 
$(D findSplitAfter) returns a tuple $(D result) containing two ranges. 

3026 
$(D result[0]) is the portion of $(D haystack) up to and including the 

3027 
match, and $(D result[1]) is the balance of $(D haystack) starting 

3028 
after the match. If $(D needle) was not found, $(D result[0]) is empty 

3029 
and $(D result[1]) is $(D haystack). 

3030 


3031 
In all cases, the concatenation of the returned ranges spans the 

3032 
entire $(D haystack). 

3033 


3034 
If $(D haystack) is a randomaccess range, all three components of the 

3035 
tuple have the same type as $(D haystack). Otherwise, $(D haystack) 

3036 
must be a forward range and the type of $(D result[0]) and $(D 

3037 
result[1]) is the same as $(XREF range,takeExactly). 

3038 


3039 
Example: 

3040 
 

3041 
auto a = [ 1, 2, 3, 4, 5, 6, 7, 8 ]; 

3042 
auto r = findSplit(a, [9, 1]); 

3043 
assert(r[0] == a); 

3044 
assert(r[1].empty); 

3045 
assert(r[2].empty); 

3046 
r = findSplit(a, [ 3, 4 ]); 

3047 
assert(r[0] == a[0 .. 2]); 

3048 
assert(r[1] == a[2 .. 4]); 

3049 
assert(r[2] == a[4 .. $]); 

3050 
auto r1 = findSplitBefore(a, [ 7, 8 ]); 

3051 
assert(r1[0] == a[0 .. 6]); 

3052 
assert(r1[1] == a[6 .. $]); 

3053 
auto r1 = findSplitAfter(a, [ 7, 8 ]); 

3054 
assert(r1[0] == a); 

3055 
assert(r1[1].empty); 

3056 
 

3057 
*/ 

3058 
auto findSplit(alias pred = "a == b", R1, R2)(R1 haystack, R2 needle) 

3059 
if (isForwardRange!R1 && isForwardRange!R2) 

3060 
{ 

3061 
static if (isSomeString!R1 && isSomeString!R2 

3062 
 isRandomAccessRange!R1 && hasLength!R2) 

3063 
{ 

3064 
auto balance = find!pred(haystack, needle); 

3065 
immutable pos1 = haystack.length  balance.length; 

3066 
immutable pos2 = balance.empty ? pos1 : pos1 + needle.length; 

3067 
return tuple(haystack[0 .. pos1], 

3068 
haystack[pos1 .. pos2], 

3069 
haystack[pos2 .. haystack.length]); 

3070 
} 

3071 
else 

3072 
{ 

3073 
auto original = haystack.save; 

3074 
auto h = haystack.save; 

3075 
auto n = needle.save; 

3076 
size_t pos1, pos2; 

3077 
while (!n.empty && !h.empty) 

3078 
{ 

3079 
if (binaryFun!pred(h.front, n.front)) 

3080 
{ 

3081 
h.popFront(); 

3082 
n.popFront(); 

3083 
++pos2; 

3084 
} 

3085 
else 

3086 
{ 

3087 
haystack.popFront(); 

3088 
n = needle.save; 

3089 
h = haystack.save; 

3090 
pos2 = ++pos1; 

3091 
} 

3092 
} 

3093 
return tuple(takeExactly(original, pos1), 

3094 
takeExactly(haystack, pos2  pos1), 

3095 
h); 

3096 
} 

3097 
} 

3098 


3099 
/// Ditto 

3100 
auto findSplitBefore(alias pred = "a == b", R1, R2)(R1 haystack, R2 needle) 

3101 
if (isForwardRange!R1 && isForwardRange!R2) 

3102 
{ 

3103 
static if (isSomeString!R1 && isSomeString!R2 

3104 
 isRandomAccessRange!R1 && hasLength!R2) 

3105 
{ 

3106 
auto balance = find!pred(haystack, needle); 

3107 
immutable pos = haystack.length  balance.length; 

3108 
return tuple(haystack[0 .. pos], haystack[pos .. haystack.length]); 

3109 
} 

3110 
else 

3111 
{ 

3112 
auto original = haystack.save; 

3113 
auto h = haystack.save; 

3114 
auto n = needle.save; 

3115 
size_t pos; 

3116 
while (!n.empty && !h.empty) 

3117 
{ 

3118 
if (binaryFun!pred(h.front, n.front)) 

3119 
{ 

3120 
h.popFront(); 

3121 
n.popFront(); 

3122 
} 

3123 
else 

3124 
{ 

3125 
haystack.popFront(); 

3126 
n = needle.save; 

3127 
h = haystack.save; 

3128 
++pos; 

3129 
} 

3130 
} 

3131 
return tuple(takeExactly(original, pos), haystack); 

3132 
} 

3133 
} 

3134 


3135 
/// Ditto 

3136 
auto findSplitAfter(alias pred = "a == b", R1, R2)(R1 haystack, R2 needle) 

3137 
if (isForwardRange!R1 && isForwardRange!R2) 

3138 
{ 

3139 
static if (isSomeString!R1 && isSomeString!R2 

3140 
 isRandomAccessRange!R1 && hasLength!R2) 

3141 
{ 

3142 
auto balance = find!pred(haystack, needle); 

3143 
immutable pos = balance.empty ? 0 : haystack.length  balance.length + needle.length; 

3144 
return tuple(haystack[0 .. pos], haystack[pos .. haystack.length]); 

3145 
} 

3146 
else 

3147 
{ 

3148 
auto original = haystack.save; 

3149 
auto h = haystack.save; 

3150 
auto n = needle.save; 

3151 
size_t pos1, pos2; 

3152 
while (!n.empty) 

3153 
{ 

3154 
if (h.empty) 

3155 
{ 

3156 
// Failed search 

3157 
return tuple(takeExactly(original, 0), original); 

3158 
} 

3159 
if (binaryFun!pred(h.front, n.front)) 

3160 
{ 

3161 
h.popFront(); 

3162 
n.popFront(); 

3163 
++pos2; 

3164 
} 

3165 
else 

3166 
{ 

3167 
haystack.popFront(); 

3168 
n = needle.save; 

3169 
h = haystack.save; 

3170 
pos2 = ++pos1; 

3171 
} 

3172 
} 

3173 
return tuple(takeExactly(original, pos2), h); 

3174 
} 

3175 
} 

3176 


3177 
unittest 

3178 
{ 

3179 
auto a = [ 1, 2, 3, 4, 5, 6, 7, 8 ]; 

3180 
auto r = findSplit(a, [9, 1]); 

3181 
assert(r[0] == a); 

3182 
assert(r[1].empty); 

3183 
assert(r[2].empty); 

3184 
r = findSplit(a, [3]); 

3185 
assert(r[0] == a[0 .. 2]); 

3186 
assert(r[1] == a[2 .. 3]); 

3187 
assert(r[2] == a[3 .. $]); 

3188 


3189 
auto r1 = findSplitBefore(a, [9, 1]); 

3190 
assert(r1[0] == a); 

3191 
assert(r1[1].empty); 

3192 
r1 = findSplitBefore(a, [3, 4]); 

3193 
assert(r1[0] == a[0 .. 2]); 

3194 
assert(r1[1] == a[2 .. $]); 

3195 


3196 
r1 = findSplitAfter(a, [9, 1]); 

3197 
assert(r1[0].empty); 

3198 
assert(r1[1] == a); 

3199 
r1 = findSplitAfter(a, [3, 4]); 

3200 
assert(r1[0] == a[0 .. 4]); 

3201 
assert(r1[1] == a[4 .. $]); 

3202 
} 

3203 


3204 
unittest 

3205 
{ 

3206 
auto a = [ 1, 2, 3, 4, 5, 6, 7, 8 ]; 

3207 
auto fwd = filter!"a > 0"(a); 

3208 
auto r = findSplit(fwd, [9, 1]); 

3209 
assert(equal(r[0], a)); 

3210 
assert(r[1].empty); 

3211 
assert(r[2].empty); 

3212 
r = findSplit(fwd, [3]); 

3213 
assert(equal(r[0], a[0 .. 2])); 

3214 
assert(equal(r[1], a[2 .. 3])); 

3215 
assert(equal(r[2], a[3 .. $])); 

3216 


3217 
auto r1 = findSplitBefore(fwd, [9, 1]); 

3218 
assert(equal(r1[0], a)); 

3219 
assert(r1[1].empty); 

3220 
r1 = findSplitBefore(fwd, [3, 4]); 

3221 
assert(equal(r1[0], a[0 .. 2])); 

3222 
assert(equal(r1[1], a[2 .. $])); 

3223 


3224 
r1 = findSplitAfter(fwd, [9, 1]); 

3225 
assert(r1[0].empty); 

3226 
assert(equal(r1[1], a)); 

3227 
r1 = findSplitAfter(fwd, [3, 4]); 

3228 
assert(equal(r1[0], a[0 .. 4])); 

3229 
assert(equal(r1[1], a[4 .. $])); 

3230 
} 

3231 


3232 
/** 

3233 
If $(D haystack) supports slicing, returns the smallest number $(D n) 

3234 
such that $(D haystack[n .. $].startsWith!pred(needle)). Oherwise, 

3235 
returns the smallest $(D n) such that after $(D n) calls to $(D 

3236 
haystack.popFront), $(D haystack.startsWith!pred(needle)). If no such 

3237 
number could be found, return $(D 1). 

3238 
*/ 

3239 
sizediff_t countUntil(alias pred = "a == b", R1, R2)(R1 haystack, R2 needle) 

3240 
if (is(typeof(startsWith!pred(haystack, needle)))) 

3241 
{ 

3242 
static if (isNarrowString!R1) 

3243 
{ 

3244 
// Narrow strings are handled a bit differently 

3245 
auto length = haystack.length; 

3246 
for (; !haystack.empty; haystack.popFront) 

3247 
{ 

3248 
if (startsWith!pred(haystack, needle)) 

3249 
{ 

3250 
return length  haystack.length; 

3251 
} 

3252 
} 

3253 
} 

3254 
else 

3255 
{ 

3256 
typeof(return) result; 

3257 
for (; !haystack.empty; ++result, haystack.popFront()) 

3258 
{ 

3259 
if (startsWith!pred(haystack, needle)) return result; 

3260 
} 

3261 
} 

3262 
return 1; 

3263 
} 

3264 


3265 
/** 

3266 
* Same as $(D countUntil). This symbol has been scheduled for 

3267 
* deprecation because it is easily confused with the homonym function 

3268 
* in $(D std.string). 

3269 
*/ 

3270 
sizediff_t indexOf(alias pred = "a == b", R1, R2)(R1 haystack, R2 needle) 

3271 
if (is(typeof(startsWith!pred(haystack, needle)))) 

3272 
{ 

3273 
pragma(msg, "std.algorithm.indexOf has been scheduled for deprecation." 

3274 
" You may want to use std.algorithm.countUntil instead."); 

3275 
return countUntil!pred(haystack, needle); 

3276 
} 

3277 


3278 
/** 

3279 
Interval option specifier for $(D until) (below) and others. 

3280 
*/ 

3281 
enum OpenRight 

3282 
{ 

3283 
no, /// Interval is closed to the right (last element included) 

3284 
yes /// Interval is open to the right (last element is not included) 

3285 
} 

3286 


3287 
/** 

3288 
Lazily iterates $(D range) until value $(D sentinel) is found, at 

3289 
which point it stops. 

3290 


3291 
Example: 

3292 
 

3293 
int[] a = [ 1, 2, 4, 7, 7, 2, 4, 7, 3, 5]; 

3294 
assert(equal(a.until(7), [1, 2, 4][])); 

3295 
assert(equal(a.until(7, OpenRight.no), [1, 2, 4, 7][])); 

3296 
 

3297 
*/ 

3298 
struct Until(alias pred, Range, Sentinel) if (isInputRange!Range) 

3299 
{ 

3300 
private Range _input; 

3301 
static if (!is(Sentinel == void)) 

3302 
private Sentinel _sentinel; 

3303 
// mixin(bitfields!( 

3304 
// OpenRight, "_openRight", 1, 

3305 
// bool, "_done", 1, 

3306 
// uint, "", 6)); 

3307 
// OpenRight, "_openRight", 1, 

3308 
// bool, "_done", 1, 

3309 
OpenRight _openRight; 

3310 
bool _done; 

3311 


3312 
static if (!is(Sentinel == void)) 

3313 
this(Range input, Sentinel sentinel, 

3314 
OpenRight openRight = OpenRight.yes) 

3315 
{ 

3316 
_input = input; 

3317 
_sentinel = sentinel; 

3318 
_openRight = openRight; 

3319 
_done = _input.empty  openRight && predSatisfied(); 

3320 
} 

3321 
else 

3322 
this(Range input, OpenRight openRight = OpenRight.yes) 

3323 
{ 

3324 
_input = input; 

3325 
_openRight = openRight; 

3326 
_done = _input.empty  openRight && predSatisfied(); 

3327 
} 

3328 


3329 
@property bool empty() 

3330 
{ 

3331 
return _done; 

3332 
} 

3333 


3334 
@property ElementType!Range front() 

3335 
{ 

3336 
assert(!empty); 

3337 
return _input.front; 

3338 
} 

3339 


3340 
bool predSatisfied() 

3341 
{ 

3342 
static if (is(Sentinel == void)) 

3343 
return unaryFun!pred(_input.front); 

3344 
else 

3345 
return startsWith!pred(_input, _sentinel); 

3346 
} 

3347 


3348 
void popFront() 

3349 
{ 

3350 
assert(!empty); 

3351 
if (!_openRight) 

3352 
{ 

3353 
if (predSatisfied()) 

3354 
{ 

3355 
_done = true; 

3356 
return; 

3357 
} 

3358 
_input.popFront; 

3359 
_done = _input.empty; 

3360 
} 

3361 
else 

3362 
{ 

3363 
_input.popFront; 

3364 
_done = _input.empty  predSatisfied; 

3365 
} 

3366 
} 

3367 


3368 
static if (!is(Sentinel == void)) 

3369 
@property Until save() 

3370 
{ 

3371 
Until result; 

3372 


3373 
result._input = _input.save; 

3374 
result._sentinel = _sentinel; 

3375 
result._openRight = _openRight; 

3376 
result._done = _done; 

3377 


3378 
return result; 

3379 
} 

3380 
else 

3381 
@property Until save() 

3382 
{ 

3383 
Until result; 

3384 


3385 
result._input = _input.save; 

3386 
result._openRight = _openRight; 

3387 
result._done = _done; 

3388 


3389 
return result; 

3390 
} 

3391 
} 

3392 


3393 
/// Ditto 

3394 
Until!(pred, Range, Sentinel) 

3395 
until(alias pred = "a == b", Range, Sentinel) 

3396 
(Range range, Sentinel sentinel, OpenRight openRight = OpenRight.yes) 

3397 
if (!is(Sentinel == OpenRight)) 

3398 
{ 

3399 
return typeof(return)(range, sentinel, openRight); 

3400 
} 

3401 


3402 
/// Ditto 

3403 
Until!(pred, Range, void) 

3404 
until(alias pred, Range) 

3405 
(Range range, OpenRight openRight = OpenRight.yes) 

3406 
{ 

3407 
return typeof(return)(range, openRight); 

3408 
} 

3409 


3410 
unittest 

3411 
{ 

3412 
//scope(success) writeln("unittest @", __FILE__, ":", __LINE__, " done."); 

3413 
int[] a = [ 1, 2, 4, 7, 7, 2, 4, 7, 3, 5]; 

3414 


3415 
static assert(isForwardRange!(typeof(a.until(7)))); 

3416 
static assert(isForwardRange!(typeof(until!"a == 2"(a, OpenRight.no)))); 

3417 


3418 
assert(equal(a.until(7), [1, 2, 4][])); 

3419 
assert(equal(a.until([7, 2]), [1, 2, 4, 7][])); 

3420 
assert(equal(a.until(7, OpenRight.no), [1, 2, 4, 7][])); 

3421 
assert(equal(until!"a == 2"(a, OpenRight.no), [1, 2][])); 

3422 
} 

3423 


3424 
/** 

3425 
If the range $(D doesThisStart) starts with $(I any) of the $(D 

3426 
withOneOfThese) ranges or elements, returns 1 if it starts with $(D 

3427 
withOneOfThese[0]), 2 if it starts with $(D withOneOfThese[1]), and so 

3428 
on. If no match, returns 0. 

3429 


3430 
Example: 

3431 
 

3432 
assert(startsWith("abc", "")); 

3433 
assert(startsWith("abc", "a")); 

3434 
assert(!startsWith("abc", "b")); 

3435 
assert(startsWith("abc", 'a', "b") == 1); 

3436 
assert(startsWith("abc", "b", "a") == 2); 

3437 
assert(startsWith("abc", "a", "a") == 1); 

3438 
assert(startsWith("abc", "x", "a", "b") == 2); 

3439 
assert(startsWith("abc", "x", "aa", "ab") == 3); 

3440 
assert(startsWith("abc", "x", "aaa", "sab") == 0); 

3441 
assert(startsWith("abc", "x", "aaa", "a", "sab") == 3); 

3442 
 

3443 
*/ 

3444 
uint startsWith(alias pred = "a == b", Range, Ranges...) 

3445 
(Range doesThisStart, Ranges withOneOfThese) 

3446 
if (Ranges.length > 1 && isInputRange!Range 

3447 
&& is(typeof(.startsWith!pred(doesThisStart, withOneOfThese[0])) 

3448 
: bool) 

3449 
&& is(typeof(.startsWith!pred(doesThisStart, withOneOfThese[1 .. $])) 

3450 
: uint)) 

3451 
{ 

3452 
alias doesThisStart lhs; 

3453 
alias withOneOfThese rhs; 

3454 


3455 
// Make one pass looking for empty ranges 

3456 
foreach (i, Unused; Ranges) 

3457 
{ 

3458 
// Empty range matches everything 

3459 
static if (!is(typeof(binaryFun!pred(lhs.front, rhs[i])) : bool)) 

3460 
{ 

3461 
if (rhs[i].empty) return i + 1; 

3462 
} 

3463 
} 

3464 


3465 
for (; !lhs.empty; lhs.popFront()) 

3466 
{ 

3467 
foreach (i, Unused; Ranges) 

3468 
{ 

3469 
static if (is(typeof(binaryFun!pred(lhs.front, rhs[i])) : bool)) 

3470 
{ 

3471 
// Singleelement 

3472 
if (binaryFun!pred(lhs.front, rhs[i])) 

3473 
{ 

3474 
// found, but continue to account for oneelement 

3475 
// range matches (consider startsWith("ab", "a", 

3476 
// 'a') should return 1, not 2). 

3477 
continue; 

3478 
} 

3479 
} 

3480 
else 

3481 
{ 

3482 
if (binaryFun!pred(lhs.front, rhs[i].front)) 

3483 
{ 

3484 
continue; 

3485 
} 

3486 
} 

3487 
// This code executed on failure to match 

3488 
// Out with this guy, check for the others 

3489 
uint result = startsWith!pred(lhs, rhs[0 .. i], rhs[i + 1 .. $]); 

3490 
if (result > i) ++result; 

3491 
return result; 

3492 
} 

3493 


3494 
// If execution reaches this point, then the front matches for all 

3495 
// rhs ranges. What we need to do now is to lop off the front of 

3496 
// all ranges involved and recurse. 

3497 
foreach (i, Unused; Ranges) 

3498 
{ 

3499 
static if (is(typeof(binaryFun!pred(lhs.front, rhs[i])) : bool)) 

3500 
{ 

3501 
// Test has passed in the previous loop 

3502 
return i + 1; 

3503 
} 

3504 
else 

3505 
{ 

3506 
rhs[i].popFront(); 

3507 
if (rhs[i].empty) return i + 1; 

3508 
} 

3509 
} 

3510 
} 

3511 
return 0; 

3512 
} 

3513 


3514 


3515 
/// Ditto 

3516 
bool startsWith(alias pred = "a == b", R1, R2) 

3517 
(R1 doesThisStart, R2 withThis) 

3518 
if (isInputRange!R1 && isInputRange!R2 

3519 
&& is(typeof(binaryFun!pred(doesThisStart.front, withThis.front)) 

3520 
: bool)) 

3521 
{ 

3522 
// Special case for two arrays 

3523 
static if (isArray!R1 && isArray!R2) 

3524 
{ 

3525 
alias doesThisStart haystack; 

3526 
alias withThis needle; 

3527 
//writeln("Matching: ", haystack, " with ", needle); 

3528 
if (haystack.length < needle.length) return 0; 

3529 
foreach (j; 0 .. needle.length) 

3530 
{ 

3531 
if (!binaryFun!pred(needle[j], haystack[j])) 

3532 
// not found 

3533 
return false; 

3534 
} 

3535 
// found! 

3536 
return true; 

3537 
} 

3538 
else 

3539 
{ 

3540 
static if (hasLength!R1 && hasLength!R2) 

3541 
{ 

3542 
if (doesThisStart.length < withThis.length) return false; 

3543 
} 

3544 
if (withThis.empty) return true; 

3545 
for (; !doesThisStart.empty; doesThisStart.popFront()) 

3546 
{ 

3547 
if (!binaryFun!pred(doesThisStart.front, withThis.front)) 

3548 
break; 

3549 
withThis.popFront(); 

3550 
if (withThis.empty) return true; 

3551 
} 

3552 
return false; 

3553 
} 

3554 
} 

3555 


3556 
/// Ditto 

3557 
bool startsWith(alias pred = "a == b", R, E) 

3558 
(R doesThisStart, E withThis) 

3559 
if (isInputRange!R && is(typeof(binaryFun!pred(doesThisStart.front, withThis)) 

3560 
: bool)) 

3561 
{ 

3562 
return doesThisStart.empty 

3563 
? false 

3564 
: binaryFun!pred(doesThisStart.front, withThis); 

3565 
} 

3566 


3567 
unittest 

3568 
{ 

3569 
debug(std_algorithm) scope(success) 

3570 
writeln("unittest @", __FILE__, ":", __LINE__, " done."); 

3571 
bool x = startsWith("ab", "a"); 

3572 
assert(startsWith("abc", "")); 

3573 
assert(startsWith("abc", "a")); 

3574 
assert(!startsWith("abc", "b")); 

3575 
assert(!startsWith("abc", "b", "bc", "abcd", "xyz")); 

3576 
assert(startsWith("abc", "a", "b") == 1); 

3577 
assert(startsWith("abc", "b", "a") == 2); 

3578 
assert(startsWith("abc", "a", 'a') == 1); 

3579 
assert(startsWith("abc", 'a', "a") == 1); 

3580 
assert(startsWith("abc", "x", "a", "b") == 2); 

3581 
assert(startsWith("abc", "x", "aa", "ab") == 3); 

3582 
assert(startsWith("abc", "x", "aaa", "sab") == 0); 

3583 
assert(startsWith("abc", 'a')); 

3584 
assert(!startsWith("abc", "sab")); 

3585 
assert(startsWith("abc", 'x', "aaa", 'a', "sab") == 3); 

3586 
} 

3587 


3588 
unittest 

3589 
{ 

3590 
debug(std_algorithm) scope(success) 

3591 
writeln("unittest @", __FILE__, ":", __LINE__, " done."); 

3592 
assert(!startsWith("abc", 'x', 'n', 'b')); 

3593 
assert(startsWith("abc", 'x', 'n', 'a') == 3); 

3594 
} 

3595 


3596 
/** 

3597 
If $(D startsWith(r1, r2)), consume the corresponding elements off $(D 

3598 
r1) and return $(D true). Otherwise, leave $(D r1) unchanged and 

3599 
return $(D false). 

3600 
*/ 

3601 
bool skipOver(alias pred = "a == b", R1, R2)(ref R1 r1, R2 r2) 

3602 
if (is(typeof(binaryFun!pred(r1.front, r2.front)))) 

3603 
{ 

3604 
auto r = r1.save; 

3605 
while (!r2.empty && !r.empty && binaryFun!pred(r.front, r2.front)) 

3606 
{ 

3607 
r.popFront(); 

3608 
r2.popFront(); 

3609 
} 

3610 
return r2.empty ? (r1 = r, true) : false; 

3611 
} 

3612 


3613 
unittest 

3614 
{ 

3615 
//scope(success) writeln("unittest @", __FILE__, ":", __LINE__, " done."); 

3616 
auto s1 = "Hello world"; 

3617 
assert(!skipOver(s1, "Ha")); 

3618 
assert(s1 == "Hello world"); 

3619 
assert(skipOver(s1, "Hell") && s1 == "o world"); 

3620 
} 

3621 


3622 
/** 

3623 
Checks whether a range starts with an element, and if so, consume that 

3624 
element off $(D r) and return $(D true). Otherwise, leave $(D r) 

3625 
unchanged and return $(D false). 

3626 
*/ 

3627 
bool skipOver(alias pred = "a == b", R, E)(ref R r, E e) 

3628 
if (is(typeof(binaryFun!pred(r.front, e)))) 

3629 
{ 

3630 
return binaryFun!pred(r.front, e) 

3631 
? (r.popFront(), true) 

3632 
: false; 

3633 
} 

3634 


3635 
unittest { 

3636 
auto s1 = "Hello world"; 

3637 
assert(!skipOver(s1, "Ha")); 

3638 
assert(s1 == "Hello world"); 

3639 
assert(skipOver(s1, "Hell") && s1 == "o world"); 

3640 
} 

3641 


3642 
/* (Not yet documented.) 

3643 
Consume all elements from $(D r) that are equal to one of the elements 

3644 
$(D es). 

3645 
*/ 

3646 
void skipAll(alias pred = "a == b", R, Es...)(ref R r, Es es) 

3647 
//if (is(typeof(binaryFun!pred(r1.front, es[0])))) 

3648 
{ 

3649 
loop: 

3650 
for (; !r.empty; r.popFront()) 

3651 
{ 

3652 
foreach (i, E; Es) 

3653 
{ 

3654 
if (binaryFun!pred(r.front, es[i])) 

3655 
{ 

3656 
continue loop; 

3657 
} 

3658 
} 

3659 
break; 

3660 
} 

3661 
} 

3662 


3663 
unittest 

3664 
{ 

3665 
//scope(success) writeln("unittest @", __FILE__, ":", __LINE__, " done."); 

3666 
auto s1 = "Hello world"; 

3667 
skipAll(s1, 'H', 'e'); 

3668 
assert(s1 == "llo world"); 

3669 
} 

3670 


3671 
/** 

3672 
The reciprocal of $(D startsWith). 

3673 


3674 
Example: 

3675 
 

3676 
assert(endsWith("abc", "")); 

3677 
assert(!endsWith("abc", "b")); 

3678 
assert(endsWith("abc", "a", 'c') == 2); 

3679 
assert(endsWith("abc", "c", "a") == 1); 

3680 
assert(endsWith("abc", "c", "c") == 1); 

3681 
assert(endsWith("abc", "x", "c", "b") == 2); 

3682 
assert(endsWith("abc", "x", "aa", "bc") == 3); 

3683 
assert(endsWith("abc", "x", "aaa", "sab") == 0); 

3684 
assert(endsWith("abc", "x", "aaa", 'c', "sab") == 3); 

3685 
 

3686 
*/ 

3687 
uint 

3688 
endsWith(alias pred = "a == b", Range, Ranges...) 

3689 
(Range doesThisEnd, Ranges withOneOfThese) 

3690 
if (isInputRange!(Range) && Ranges.length > 0 

3691 
&& is(typeof(binaryFun!pred(doesThisEnd.back, withOneOfThese[0].back)))) 

3692 
{ 

3693 
alias doesThisEnd lhs; 

3694 
alias withOneOfThese rhs; 

3695 
// Special case for two arrays 

3696 
static if (Ranges.length == 1 && isArray!Range && isArray!(Ranges[0]) 

3697 
&& is(typeof(binaryFun!(pred)(lhs[0], rhs[0][0])))) 

3698 
{ 

3699 
if (lhs.length < rhs[0].length) return 0; 

3700 
auto k = lhs.length  rhs[0].length; 

3701 
foreach (j; 0 .. rhs[0].length) 

3702 
{ 

3703 
if (!binaryFun!(pred)(rhs[0][j], lhs[j + k])) 

3704 
// not found 

3705 
return 0u; 

3706 
} 

3707 
// found! 

3708 
return 1u; 

3709 
} 

3710 
else 

3711 
{ 

3712 
// Make one pass looking for empty ranges 

3713 
foreach (i, Unused; Ranges) 

3714 
{ 

3715 
// Empty range matches everything 

3716 
if (rhs[i].empty) return i + 1; 

3717 
} 

3718 
bool mismatch[Ranges.length]; 

3719 
for (; !lhs.empty; lhs.popBack) 

3720 
{ 

3721 
foreach (i, Unused; Ranges) 

3722 
{ 

3723 
if (mismatch[i]) continue; 

3724 
if (binaryFun!pred(lhs.back, rhs[i].back)) 

3725 
{ 

3726 
// Stay in the game 

3727 
rhs[i].popBack(); 

3728 
// Done with success if exhausted 

3729 
if (rhs[i].empty) return i + 1; 

3730 
} 

3731 
else 

3732 
{ 

3733 
// Out 

3734 
mismatch[i] = true; 

3735 
} 

3736 
} 

3737 
} 

3738 
return 0; 

3739 
} 

3740 
} 

3741 


3742 
unittest 

3743 
{ 

3744 
debug(std_algorithm) scope(success) 

3745 
writeln("unittest @", __FILE__, ":", __LINE__, " done."); 

3746 
assert(endsWith("abc", "")); 

3747 
assert(!endsWith("abc", "a")); 

3748 
assert(!endsWith("abc", 'a')); 

3749 
assert(!endsWith("abc", "b")); 

3750 
assert(endsWith("abc", "a", "c") == 2); 

3751 
assert(endsWith("abc", 'a', 'c') == 2); 

3752 
assert(endsWith("abc", "c", "a") == 1); 

3753 
assert(endsWith("abc", "c", "c") == 1); 

3754 
assert(endsWith("abc", "x", "c", "b") == 2); 

3755 
assert(endsWith("abc", "x", "aa", "bc") == 3); 

3756 
assert(endsWith("abc", "x", "aaa", "sab") == 0); 

3757 
assert(endsWith("abc", "x", "aaa", "c", "sab") == 3); 

3758 
// string a = "abc"; 

3759 
// immutable(char[1]) b = "c"; 

3760 
// assert(wyda(a, b)); 

3761 
} 

3762 


3763 
/** 

3764 
Checks whether $(D doesThisEnd) starts with one of the individual 

3765 
elements $(D withOneOfThese) according to $(D pred). 

3766 


3767 
Example: 

3768 
 

3769 
assert(endsWith("abc", 'x', 'c', 'a') == 2); 

3770 
 

3771 
*/ 

3772 
uint endsWith(alias pred = "a == b", Range, Elements...) 

3773 
(Range doesThisEnd, Elements withOneOfThese) 

3774 
if (isInputRange!Range && Elements.length > 0 

3775 
&& is(typeof(binaryFun!pred(doesThisEnd.front, withOneOfThese[0])))) 

3776 
{ 

3777 
if (doesThisEnd.empty) return 0; 

3778 
auto back = doesThisEnd.back; 

3779 
foreach (i, Unused; Elements) 

3780 
{ 

3781 
if (binaryFun!pred(back, withOneOfThese[i])) return i + 1; 

3782 
} 

3783 
return 0; 

3784 
} 

3785 


3786 
unittest 

3787 
{ 

3788 
debug(std_algorithm) scope(success) 

3789 
writeln("unittest @", __FILE__, ":", __LINE__, " done."); 

3790 
assert(!startsWith("abc", 'x', 'n', 'b')); 

3791 
assert(startsWith("abc", 'x', 'n', 'a') == 3); 

3792 
} 

3793 


3794 
// findAdjacent 

3795 
/** 

3796 
Advances $(D r) until it finds the first two adjacent elements $(D a), 

3797 
$(D b) that satisfy $(D pred(a, b)). Performs $(BIGOH r.length) 

3798 
evaluations of $(D pred). See also $(WEB 

3799 
sgi.com/tech/stl/adjacent_find.html, STL's adjacent_find). 

3800 


3801 
Example: 

3802 
 

3803 
int[] a = [ 11, 10, 10, 9, 8, 8, 7, 8, 9 ]; 

3804 
auto r = findAdjacent(a); 

3805 
assert(r == [ 10, 10, 9, 8, 8, 7, 8, 9 ]); 

3806 
p = findAdjacent!("a < b")(a); 

3807 
assert(p == [ 7, 8, 9 ]); 

3808 
 

3809 
*/ 

3810 
Range findAdjacent(alias pred = "a == b", Range)(Range r) 

3811 
if (isForwardRange!(Range)) 

3812 
{ 

3813 
auto ahead = r; 

3814 
if (!ahead.empty) 

3815 
{ 

3816 
for (ahead.popFront; !ahead.empty; r.popFront, ahead.popFront) 

3817 
{ 

3818 
if (binaryFun!(pred)(r.front, ahead.front)) return r; 

3819 
} 

3820 
} 

3821 
return ahead; 

3822 
} 

3823 


3824 
unittest 

3825 
{ 

3826 
//scope(success) writeln("unittest @", __FILE__, ":", __LINE__, " done."); 

3827 
int[] a = [ 11, 10, 10, 9, 8, 8, 7, 8, 9 ]; 

3828 
auto p = findAdjacent(a); 

3829 
assert(p == [10, 10, 9, 8, 8, 7, 8, 9 ]); 

3830 
p = findAdjacent!("a < b")(a); 

3831 
assert(p == [7, 8, 9]); 

3832 
// empty 

3833 
a = []; 

3834 
p = findAdjacent(a); 

3835 
assert(p.empty); 

3836 
// not found 

3837 
a = [ 1, 2, 3, 4, 5 ]; 

3838 
p = findAdjacent(a); 

3839 
assert(p.empty); 

3840 
p = findAdjacent!"a > b"(a); 

3841 
assert(p.empty); 

3842 
} 

3843 


3844 
// findAmong 

3845 
/** 

3846 
Advances $(D seq) by calling $(D seq.popFront) until either $(D 

3847 
find!(pred)(choices, seq.front)) is $(D true), or $(D seq) becomes 

3848 
empty. Performs $(BIGOH seq.length * choices.length) evaluations of 

3849 
$(D pred). See also $(WEB sgi.com/tech/stl/find_first_of.html, STL's 

3850 
find_first_of). 

3851 


3852 
Example: 

3853 
 

3854 
int[] a = [ 1, 0, 1, 2, 3, 4, 5 ]; 

3855 
int[] b = [ 3, 1, 2 ]; 

3856 
assert(findAmong(a, b) == a[2 .. $]); 

3857 
 

3858 
*/ 

3859 
Range1 findAmong(alias pred = "a == b", Range1, Range2)( 

3860 
Range1 seq, Range2 choices) 

3861 
if (isInputRange!Range1 && isForwardRange!Range2) 

3862 
{ 

3863 
for (; !seq.empty && find!pred(choices, seq.front).empty; seq.popFront) 

3864 
{ 

3865 
} 

3866 
return seq; 

3867 
} 

3868 


3869 
unittest 

3870 
{ 

3871 
//scope(success) writeln("unittest @", __FILE__, ":", __LINE__, " done."); 

3872 
int[] a = [ 1, 0, 2, 1, 2, 3, 4, 5 ]; 

3873 
int[] b = [ 1, 2, 3 ]; 

3874 
assert(findAmong(a, b) == [2, 1, 2, 3, 4, 5 ]); 

3875 
assert(findAmong(b, [ 4, 6, 7 ][]).empty); 

3876 
assert(findAmong!("a==b")(a, b).length == a.length  2); 

3877 
assert(findAmong!("a==b")(b, [ 4, 6, 7 ][]).empty); 

3878 
} 

3879 


3880 
// count 

3881 
/** 

3882 
The first version counts the number of elements $(D x) in $(D r) for 

3883 
which $(D pred(x, value)) is $(D true). $(D pred) defaults to 

3884 
equality. Performs $(BIGOH r.length) evaluations of $(D pred). 

3885 


3886 
The second version returns the number of times $(D needle) occurs in 

3887 
$(D haystack). Throws an exception if $(D needle.empty), as the _count 

3888 
of the empty range in any range would be infinite. Overlapped counts 

3889 
are not considered, for example $(D count("aaa", "aa")) is $(D 1), not 

3890 
$(D 2). 

3891 


3892 
The third version counts the elements for which $(D pred(x)) is $(D 

3893 
true). Performs $(BIGOH r.length) evaluations of $(D pred). 

3894 


3895 
Example: 

3896 
 

3897 
// count elements in range 

3898 
int[] a = [ 1, 2, 4, 3, 2, 5, 3, 2, 4 ]; 

3899 
assert(count(a, 2) == 3); 

3900 
assert(count!("a > b")(a, 2) == 5); 

3901 
// count range in range 

3902 
assert(count("abcadfabf", "ab") == 2); 

3903 
assert(count("ababab", "abab") == 1); 

3904 
assert(count("ababab", "abx") == 0); 

3905 
// count predicate in range 

3906 
assert(count!("a > 1")(a) == 8); 

3907 
 

3908 
*/ 

3909 
size_t count(alias pred = "a == b", Range, E)(Range r, E value) 

3910 
if (isInputRange!Range && is(typeof(binaryFun!pred(r.front, value)) == bool)) 

3911 
{ 

3912 
bool pred2(ElementType!(Range) a) { return binaryFun!pred(a, value); } 

3913 
return count!(pred2)(r); 

3914 
} 

3915 


3916 
unittest 

3917 
{ 

3918 
debug(std_algorithm) scope(success) 

3919 
writeln("unittest @", __FILE__, ":", __LINE__, " done."); 

3920 
int[] a = [ 1, 2, 4, 3, 2, 5, 3, 2, 4 ]; 

3921 
assert(count(a, 2) == 3, text(count(a, 2))); 

3922 
assert(count!("a > b")(a, 2) == 5, text(count!("a > b")(a, 2))); 

3923 


3924 
// check strings 

3925 
assert(count("Ã¦Â—Â¥Ã¦ÂœÂ¬Ã¨ÂªÂž") == 3); 

3926 
assert(count("Ã¦Â—Â¥Ã¦ÂœÂ¬Ã¨ÂªÂž"w) == 3); 

3927 
assert(count("Ã¦Â—Â¥Ã¦ÂœÂ¬Ã¨ÂªÂž"d) == 3); 

3928 


3929 
assert(count!("a == 'Ã¦Â—Â¥'")("Ã¦Â—Â¥Ã¦ÂœÂ¬Ã¨ÂªÂž") == 1); 

3930 
assert(count!("a == 'Ã¦ÂœÂ¬'")("Ã¦Â—Â¥Ã¦ÂœÂ¬Ã¨ÂªÂž"w) == 1); 

3931 
assert(count!("a == 'Ã¨ÂªÂž'")("Ã¦Â—Â¥Ã¦ÂœÂ¬Ã¨ÂªÂž"d) == 1); 

3932 
} 

3933 


3934 
unittest 

3935 
{ 

3936 
debug(std_algorithm) printf("algorithm.count.unittest\n"); 

3937 
string s = "This is a fofofof list"; 

3938 
string sub = "fof"; 

3939 
assert(count(s, sub) == 2); 

3940 
} 

3941 


3942 
/// Ditto 

3943 
size_t count(alias pred = "a == b", R1, R2)(R1 haystack, R2 needle) 

3944 
if (isInputRange!R1 && isForwardRange!R2 && is(typeof(binaryFun!pred(haystack, needle)) == bool)) 

3945 
{ 

3946 
enforce(!needle.empty, "Cannot count occurrences of an empty range"); 

3947 
size_t result; 

3948 
for (; findSkip!pred(haystack, needle); ++result) 

3949 
{ 

3950 
} 

3951 
return result; 

3952 
} 

3953 


3954 
unittest 

3955 
{ 

3956 
assert(count("abcadfabf", "ab") == 2); 

3957 
assert(count("ababab", "abab") == 1); 

3958 
assert(count("ababab", "abx") == 0); 

3959 
} 

3960 


3961 
/// Ditto 

3962 
size_t count(alias pred = "true", Range)(Range r) if (isInputRange!(Range)) 

3963 
{ 

3964 
size_t result; 

3965 
for (; !r.empty; r.popFront()) 

3966 
{ 

3967 
if (unaryFun!pred(r.front)) ++result; 

3968 
} 

3969 
return result; 

3970 
} 

3971 


3972 
unittest 

3973 
{ 

3974 
debug(std_algorithm) scope(success) 

3975 
writeln("unittest @", __FILE__, ":", __LINE__, " done."); 

3976 
int[] a = [ 1, 2, 4, 3, 2, 5, 3, 2, 4 ]; 

3977 
assert(count!("a == 3")(a) == 2); 

3978 
} 

3979 


3980 
// balancedParens 

3981 
/** 

3982 
Checks whether $(D r) has "balanced parentheses", i.e. all instances 

3983 
of $(D lPar) are closed by corresponding instances of $(D rPar). The 

3984 
parameter $(D maxNestingLevel) controls the nesting level allowed. The 

3985 
most common uses are the default or $(D 0). In the latter case, no 

3986 
nesting is allowed. 

3987 


3988 
Example: 

3989 
 

3990 
auto s = "1 + (2 * (3 + 1 / 2)"; 

3991 
assert(!balancedParens(s, '(', ')')); 

3992 
s = "1 + (2 * (3 + 1) / 2)"; 

3993 
assert(balancedParens(s, '(', ')')); 

3994 
s = "1 + (2 * (3 + 1) / 2)"; 

3995 
assert(!balancedParens(s, '(', ')', 1)); 

3996 
s = "1 + (2 * 3 + 1) / (2  5)"; 

3997 
assert(balancedParens(s, '(', ')', 1)); 

3998 
 

3999 
*/ 

4000 


4001 
bool balancedParens(Range, E)(Range r, E lPar, E rPar, 

4002 
size_t maxNestingLevel = size_t.max) 

4003 
if (isInputRange!(Range) && is(typeof(r.front == lPar))) 

4004 
{ 

4005 
size_t count; 

4006 
for (; !r.empty; r.popFront()) 

4007 
{ 

4008 
if (r.front == lPar) 

4009 
{ 

4010 
if (count > maxNestingLevel) return false; 

4011 
++count; 

4012 
} 

4013 
else if (r.front == rPar) 

4014 
{ 

4015 
if (!count) return false; 

4016 
count; 

4017 
} 

4018 
} 

4019 
return count == 0; 

4020 
} 

4021 


4022 
unittest 

4023 
{ 

4024 
auto s = "1 + (2 * (3 + 1 / 2)"; 

4025 
assert(!balancedParens(s, '(', ')')); 

4026 
s = "1 + (2 * (3 + 1) / 2)"; 

4027 
assert(balancedParens(s, '(', ')')); 

4028 
s = "1 + (2 * (3 + 1) / 2)"; 

4029 
assert(!balancedParens(s, '(', ')', 0)); 

4030 
s = "1 + (2 * 3 + 1) / (2  5)"; 

4031 
assert(balancedParens(s, '(', ')', 0)); 

4032 
} 

4033 


4034 
// equal 

4035 
/** 

4036 
Returns $(D true) if and only if the two ranges compare equal element 

4037 
for element, according to binary predicate $(D pred). The ranges may 

4038 
have different element types, as long as $(D pred(a, b)) evaluates to 

4039 
$(D bool) for $(D a) in $(D r1) and $(D b) in $(D r2). Performs 

4040 
$(BIGOH min(r1.length, r2.length)) evaluations of $(D pred). See also 

4041 
$(WEB sgi.com/tech/stl/_equal.html, STL's equal). 

4042 


4043 
Example: 

4044 
 

4045 
int[] a = [ 1, 2, 4, 3 ]; 

4046 
assert(!equal(a, a[1..$])); 

4047 
assert(equal(a, a)); 

4048 


4049 
// different types 

4050 
double[] b = [ 1., 2, 4, 3]; 

4051 
assert(!equal(a, b[1..$])); 

4052 
assert(equal(a, b)); 

4053 


4054 
// predicated: ensure that two vectors are approximately equal 

4055 
double[] c = [ 1.005, 2, 4, 3]; 

4056 
assert(equal!(approxEqual)(b, c)); 

4057 
 

4058 
*/ 

4059 
bool equal(alias pred = "a == b", Range1, Range2)(Range1 r1, Range2 r2) 

4060 
if (isInputRange!(Range1) && isInputRange!(Range2) 

4061 
&& is(typeof(binaryFun!pred(r1.front, r2.front)))) 

4062 
{ 

4063 
foreach (e1; r1) 

4064 
{ 

4065 
if (r2.empty) return false; 

4066 
if (!binaryFun!(pred)(e1, r2.front)) return false; 

4067 
r2.popFront; 

4068 
} 

4069 
return r2.empty; 

4070 
} 

4071 


4072 
unittest 

4073 
{ 

4074 
debug(std_algorithm) scope(success) 

4075 
writeln("unittest @", __FILE__, ":", __LINE__, " done."); 

4076 
int[] a = [ 1, 2, 4, 3]; 

4077 
assert(!equal(a, a[1..$])); 

4078 
assert(equal(a, a)); 

4079 
// test with different types 

4080 
double[] b = [ 1., 2, 4, 3]; 

4081 
assert(!equal(a, b[1..$])); 

4082 
assert(equal(a, b)); 

4083 


4084 
// predicated 

4085 
double[] c = [ 1.005, 2, 4, 3]; 

4086 
assert(equal!(approxEqual)(b, c)); 

4087 
} 

4088 


4089 
// cmp 

4090 
/********************************** 

4091 
Performs threeway lexicographical comparison on two input ranges 

4092 
according to predicate $(D pred). Iterating $(D r1) and $(D r2) in 

4093 
lockstep, $(D cmp) compares each element $(D e1) of $(D r1) with the 

4094 
corresponding element $(D e2) in $(D r2). If $(D binaryFun!pred(e1, 

4095 
e2)), $(D cmp) returns a negative value. If $(D binaryFun!pred(e2, 

4096 
e1)), $(D cmp) returns a positive value. If one of the ranges has been 

4097 
finished, $(D cmp) returns a negative value if $(D r1) has fewer 

4098 
elements than $(D r2), a positive value if $(D r1) has more elements 

4099 
than $(D r2), and $(D 0) if the ranges have the same number of 

4100 
elements. 

4101 


4102 
If the ranges are strings, $(D cmp) performs UTF decoding 

4103 
appropriately and compares the ranges one code point at a time. 

4104 
*/ 

4105 


4106 
int cmp(alias pred = "a < b", R1, R2)(R1 r1, R2 r2) 

4107 
if (isInputRange!R1 && isInputRange!R2 && !(isSomeString!R1 && isSomeString!R2)) 

4108 
{ 

4109 
for (;; r1.popFront(), r2.popFront()) 

4110 
{ 

4111 
if (r1.empty) return r2.empty; 

4112 
if (r2.empty) return r1.empty; 

4113 
auto a = r1.front, b = r2.front; 

4114 
if (binaryFun!pred(a, b)) return 1; 

4115 
if (binaryFun!pred(b, a)) return 1; 

4116 
} 

4117 
} 

4118 


4119 
// Specialization for strings (for speed purposes) 

4120 
int cmp(alias pred = "a < b", R1, R2)(R1 r1, R2 r2) if (isSomeString!R1 && isSomeString!R2) 

4121 
{ 

4122 
enum isLessThan = is(pred : string) && pred == "a < b"; 

4123 
// For speed only 

4124 
static int threeWay(size_t a, size_t b) 

4125 
{ 

4126 
static if (size_t.sizeof == int.sizeof && isLessThan) 

4127 
return a  b; 

4128 
else 

4129 
return binaryFun!pred(b, a) ? 1 : binaryFun!pred(a, b) ? 1 : 0; 

4130 
} 

4131 
// For speed only 

4132 
// @@@BUG@@@ overloading should be allowed for nested functions 

4133 
static int threeWayInt(int a, int b) 

4134 
{ 

4135 
static if (isLessThan) 

4136 
return a  b; 

4137 
else 

4138 
return binaryFun!pred(b, a) ? 1 : binaryFun!pred(a, b) ? 1 : 0; 

4139 
} 

4140 


4141 
static if (typeof(r1[0]).sizeof == typeof(r2[0]).sizeof && isLessThan) 

4142 
{ 

4143 
static if (typeof(r1[0]).sizeof == 1) 

4144 
{ 

4145 
immutable len = min(r1.length, r2.length); 

4146 
immutable result = std.c.string.memcmp(r1.ptr, r2.ptr, len); 

4147 
if (result) return result; 

4148 
} 

4149 
else 

4150 
{ 

4151 
auto p1 = r1.ptr, p2 = r2.ptr, 

4152 
pEnd = p1 + min(r1.length, r2.length); 

4153 
for (; p1 != pEnd; ++p1, ++p2) 

4154 
{ 

4155 
if (*p1 != *p2) return threeWayInt(cast(int) *p1, cast(int) *p2); 

4156 
} 

4157 
} 

4158 
return threeWay(r1.length, r2.length); 

4159 
} 

4160 
else 

4161 
{ 

4162 
for (size_t i1, i2;;) 

4163 
{ 

4164 
if (i1 == r1.length) return threeWay(i2, r2.length); 

4165 
if (i2 == r2.length) return threeWay(r1.length, i1); 

4166 
immutable c1 = std.utf.decode(r1, i1), 

4167 
c2 = std.utf.decode(r2, i2); 

4168 
if (c1 != c2) return threeWayInt(cast(int) c1, cast(int) c2); 

4169 
} 

4170 
} 

4171 
} 

4172 


4173 
unittest 

4174 
{ 

4175 
int result; 

4176 


4177 
debug(string) printf("string.cmp.unittest\n"); 

4178 
result = cmp("abc", "abc"); 

4179 
assert(result == 0); 

4180 
// result = cmp(null, null); 

4181 
// assert(result == 0); 

4182 
result = cmp("", ""); 

4183 
assert(result == 0); 

4184 
result = cmp("abc", "abcd"); 

4185 
assert(result < 0); 

4186 
result = cmp("abcd", "abc"); 

4187 
assert(result > 0); 

4188 
result = cmp("abc"d, "abd"); 

4189 
assert(result < 0); 

4190 
result = cmp("bbc", "abc"w); 

4191 
assert(result > 0); 

4192 
result = cmp("aaa", "aaaa"d); 

4193 
assert(result < 0); 

4194 
result = cmp("aaaa", "aaa"d); 

4195 
assert(result > 0); 

4196 
result = cmp("aaa", "aaa"d); 

4197 
assert(result == 0); 

4198 
} 

4199 


4200 
// MinType 

4201 
template MinType(T...) 

4202 
{ 

4203 
static assert(T.length >= 2); 

4204 
static if (T.length == 2) 

4205 
{ 

4206 
static if (!is(typeof(T[0].min))) 

4207 
alias CommonType!(T[0 .. 2]) MinType; 

4208 
else static if (mostNegative!(T[1]) < mostNegative!(T[0])) 

4209 
alias T[1] MinType; 

4210 
else static if (mostNegative!(T[1]) > mostNegative!(T[0])) 

4211 
alias T[0] MinType; 

4212 
else static if (T[1].max < T[0].max) 

4213 
alias T[1] MinType; 

4214 
else 

4215 
alias T[0] MinType; 

4216 
} 

4217 
else 

4218 
{ 

4219 
alias MinType!(MinType!(T[0 .. 2]), T[2 .. $]) MinType; 

4220 
} 

4221 
} 

4222 


4223 
// min 

4224 
/** 

4225 
Returns the minimum of the passedin values. The type of the result is 

4226 
computed by using $(XREF traits, CommonType). 

4227 
*/ 

4228 
MinType!(T1, T2, T) min(T1, T2, T...)(T1 a, T2 b, T xs) 

4229 
{ 

4230 
static if (T.length == 0) 

4231 
{ 

4232 
static if (isIntegral!(T1) && isIntegral!(T2) 

4233 
&& (mostNegative!(T1) < 0) != (mostNegative!(T2) < 0)) 

4234 
static if (mostNegative!(T1) < 0) 

4235 
immutable chooseB = b < a && a > 0; 

4236 
else 

4237 
immutable chooseB = b < a  b < 0; 

4238 
else 

4239 
immutable chooseB = b < a; 

4240 
return cast(typeof(return)) (chooseB ? b : a); 

4241 
} 

4242 
else 

4243 
{ 

4244 
return min(min(a, b), xs); 

4245 
} 

4246 
} 

4247 


4248 
unittest 

4249 
{ 

4250 
debug(std_algorithm) scope(success) 

4251 
writeln("unittest @", __FILE__, ":", __LINE__, " done."); 

4252 
int a = 5; 

4253 
short b = 6; 

4254 
double c = 2; 

4255 
auto d = min(a, b); 

4256 
assert(is(typeof(d) == int)); 

4257 
assert(d == 5); 

4258 
auto e = min(a, b, c); 

4259 
assert(is(typeof(e) == double)); 

4260 
assert(e == 2); 

4261 
// mixed signedness test 

4262 
a = 10; 

4263 
uint f = 10; 

4264 
static assert(is(typeof(min(a, f)) == int)); 

4265 
assert(min(a, f) == 10); 

4266 
} 

4267 


4268 
// MaxType 

4269 
template MaxType(T...) 

4270 
{ 

4271 
static assert(T.length >= 2); 

4272 
static if (T.length == 2) 

4273 
{ 

4274 
static if (!is(typeof(T[0].min))) 

4275 
alias CommonType!(T[0 .. 2]) MaxType; 

4276 
else static if (T[1].max > T[0].max) 

4277 
alias T[1] MaxType; 

4278 
else 

4279 
alias T[0] MaxType; 

4280 
} 

4281 
else 

4282 
{ 

4283 
alias MaxType!(MaxType!(T[0], T[1]), T[2 .. $]) MaxType; 

4284 
} 

4285 
} 

4286 


4287 
// max 

4288 
/** 

4289 
Returns the maximum of the passedin values. The type of the result is 

4290 
computed by using $(XREF traits, CommonType). 

4291 


4292 
Example: 

4293 
 

4294 
int a = 5; 

4295 
short b = 6; 

4296 
double c = 2; 

4297 
auto d = max(a, b); 

4298 
assert(is(typeof(d) == int)); 

4299 
assert(d == 6); 

4300 
auto e = min(a, b, c); 

4301 
assert(is(typeof(e) == double)); 

4302 
assert(e == 2); 

4303 
 

4304 
*/ 

4305 
MaxType!(T1, T2, T) max(T1, T2, T...)(T1 a, T2 b, T xs) 

4306 
{ 

4307 
static if (T.length == 0) 

4308 
{ 

4309 
static if (isIntegral!(T1) && isIntegral!(T2) 

4310 
&& (mostNegative!(T1) < 0) != (mostNegative!(T2) < 0)) 

4311 
static if (mostNegative!(T1) < 0) 

4312 
immutable chooseB = b > a  a < 0; 

4313 
else 

4314 
immutable chooseB = b > a && b > 0; 

4315 
else 

4316 
immutable chooseB = b > a; 

4317 
return cast(typeof(return)) (chooseB ? b : a); 

4318 
} 

4319 
else 

4320 
{ 

4321 
return max(max(a, b), xs); 

4322 
} 

4323 
} 

4324 


4325 
unittest 

4326 
{ 

4327 
debug(std_algorithm) scope(success) 

4328 
writeln("unittest @", __FILE__, ":", __LINE__, " done."); 

4329 
int a = 5; 

4330 
short b = 6; 

4331 
double c = 2; 

4332 
auto d = max(a, b); 

4333 
assert(is(typeof(d) == int)); 

4334 
assert(d == 6); 

4335 
auto e = max(a, b, c); 

4336 
assert(is(typeof(e) == double)); 

4337 
assert(e == 6); 

4338 
// mixed sign 

4339 
a = 5; 

4340 
uint f = 5; 

4341 
static assert(is(typeof(max(a, f)) == uint)); 

4342 
assert(max(a, f) == 5); 

4343 
} 

4344 


4345 
/** 

4346 
Returns the minimum element of a range together with the number of 

4347 
occurrences. The function can actually be used for counting the 

4348 
maximum or any other ordering predicate (that's why $(D maxCount) is 

4349 
not provided). 

4350 


4351 
Example: 

4352 
 

4353 
int[] a = [ 2, 3, 4, 1, 2, 4, 1, 1, 2 ]; 

4354 
// Minimum is 1 and occurs 3 times 

4355 
assert(minCount(a) == tuple(1, 3)); 

4356 
// Maximum is 4 and occurs 2 times 

4357 
assert(minCount!("a > b")(a) == tuple(4, 2)); 

4358 
 

4359 
*/ 

4360 
Tuple!(ElementType!(Range), size_t) 

4361 
minCount(alias pred = "a < b", Range)(Range range) 

4362 
{ 

4363 
if (range.empty) return typeof(return)(); 

4364 
auto p = &(range.front()); 

4365 
size_t occurrences = 1; 

4366 
for (range.popFront; !range.empty; range.popFront) 

4367 
{ 

4368 
if (binaryFun!(pred)(*p, range.front)) continue; 

4369 
if (binaryFun!(pred)(range.front, *p)) 

4370 
{ 

4371 
// change the min 

4372 
p = &(range.front()); 

4373 
occurrences = 1; 

4374 
} 

4375 
else 

4376 
{ 

4377 
++occurrences; 

4378 
} 

4379 
} 

4380 
return tuple(*p, occurrences); 

4381 
} 

4382 


4383 
unittest 

4384 
{ 

4385 
debug(std_algorithm) scope(success) 

4386 
writeln("unittest @", __FILE__, ":", __LINE__, " done."); 

4387 
int[] a = [ 2, 3, 4, 1, 2, 4, 1, 1, 2 ]; 

4388 
assert(minCount(a) == tuple(1, 3)); 

4389 
assert(minCount!("a > b")(a) == tuple(4, 2)); 

4390 
int[][] b = [ [4], [2, 4], [4], [4] ]; 

4391 
auto c = minCount!("a[0] < b[0]")(b); 

4392 
assert(c == tuple([2, 4], 1), text(c[0])); 

4393 
} 

4394 


4395 
// minPos 

4396 
/** 

4397 
Returns the position of the minimum element of forward range $(D 

4398 
range), i.e. a subrange of $(D range) starting at the position of its 

4399 
smallest element and with the same ending as $(D range). The function 

4400 
can actually be used for counting the maximum or any other ordering 

4401 
predicate (that's why $(D maxPos) is not provided). 

4402 


4403 
Example: 

4404 
 

4405 
int[] a = [ 2, 3, 4, 1, 2, 4, 1, 1, 2 ]; 

4406 
// Minimum is 1 and first occurs in position 3 

4407 
assert(minPos(a) == [ 1, 2, 4, 1, 1, 2 ]); 

4408 
// Maximum is 4 and first occurs in position 2 

4409 
assert(minPos!("a > b")(a) == [ 4, 1, 2, 4, 1, 1, 2 ]); 

4410 
 

4411 
*/ 

4412 
Range minPos(alias pred = "a < b", Range)(Range range) 

4413 
{ 

4414 
if (range.empty) return range; 

4415 
auto result = range; 

4416 
for (range.popFront; !range.empty; range.popFront) 

4417 
{ 

4418 
if (binaryFun!(pred)(result.front, range.front) 

4419 
 !binaryFun!(pred)(range.front, result.front)) continue; 

4420 
// change the min 

4421 
result = range; 

4422 
} 

4423 
return result; 

4424 
} 

4425 


4426 
unittest 

4427 
{ 

4428 
debug(std_algorithm) scope(success) 

4429 
writeln("unittest @", __FILE__, ":", __LINE__, " done."); 

4430 
int[] a = [ 2, 3, 4, 1, 2, 4, 1, 1, 2 ]; 

4431 
// Minimum is 1 and first occurs in position 3 

4432 
assert(minPos(a) == [ 1, 2, 4, 1, 1, 2 ]); 

4433 
// Maximum is 4 and first occurs in position 5 

4434 
assert(minPos!("a > b")(a) == [ 4, 1, 2, 4, 1, 1, 2 ]); 

4435 
} 

4436 


4437 
// mismatch 

4438 
/** 

4439 
Sequentially compares elements in $(D r1) and $(D r2) in lockstep, and 

4440 
stops at the first mismatch (according to $(D pred), by default 

4441 
equality). Returns a tuple with the reduced ranges that start with the 

4442 
two mismatched values. Performs $(BIGOH min(r1.length, r2.length)) 

4443 
evaluations of $(D pred). See also $(WEB 

4444 
sgi.com/tech/stl/_mismatch.html, STL's mismatch). 

4445 


4446 
Example: 

4447 
 

4448 
int[] x = [ 1, 5, 2, 7, 4, 3 ]; 

4449 
double[] y = [ 1., 5, 2, 7.3, 4, 8 ]; 

4450 
auto m = mismatch(x, y); 

4451 
assert(m[0] == x[3 .. $]); 

4452 
assert(m[1] == y[3 .. $]); 

4453 
 

4454 
*/ 

4455 


4456 
Tuple!(Range1, Range2) 

4457 
mismatch(alias pred = "a == b", Range1, Range2)(Range1 r1, Range2 r2) 

4458 
if (isInputRange!(Range1) && isInputRange!(Range2)) 

4459 
{ 

4460 
for (; !r1.empty && !r2.empty; r1.popFront(), r2.popFront()) 

4461 
{ 

4462 
if (!binaryFun!(pred)(r1.front, r2.front)) break; 

4463 
} 

4464 
return tuple(r1, r2); 

4465 
} 

4466 


4467 
unittest 

4468 
{ 

4469 
debug(std_algorithm) scope(success) 

4470 
writeln("unittest @", __FILE__, ":", __LINE__, " done."); 

4471 
// doc example 

4472 
int[] x = [ 1, 5, 2, 7, 4, 3 ]; 

4473 
double[] y = [ 1., 5, 2, 7.3, 4, 8 ]; 

4474 
auto m = mismatch(x, y); 

4475 
assert(m[0] == [ 7, 4, 3 ]); 

4476 
assert(m[1] == [ 7.3, 4, 8 ]); 

4477 


4478 
int[] a = [ 1, 2, 3 ]; 

4479 
int[] b = [ 1, 2, 4, 5 ]; 

4480 
auto mm = mismatch(a, b); 

4481 
assert(mm[0] == [3]); 

4482 
assert(mm[1] == [4, 5]); 

4483 
} 

4484 


4485 
// levenshteinDistance 

4486 
/** 

4487 
Encodes $(WEB realityinteractive.com/rgrzywinski/archives/000249.html, 

4488 
edit operations) necessary to transform one sequence into 

4489 
another. Given sequences $(D s) (source) and $(D t) (target), a 

4490 
sequence of $(D EditOp) encodes the steps that need to be taken to 

4491 
convert $(D s) into $(D t). For example, if $(D s = "cat") and $(D 

4492 
"cars"), the minimal sequence that transforms $(D s) into $(D t) is: 

4493 
skip two characters, replace 't' with 'r', and insert an 's'. Working 

4494 
with edit operations is useful in applications such as spellcheckers 

4495 
(to find the closest word to a given misspelled word), approximate 

4496 
searches, diffstyle programs that compute the difference between 

4497 
files, efficient encoding of patches, DNA sequence analysis, and 

4498 
plagiarism detection. 

4499 
*/ 

4500 


4501 
enum EditOp : char 

4502 
{ 

4503 
/** Current items are equal; no editing is necessary. */ 

4504 
none = 'n', 

4505 
/** Substitute current item in target with current item in source. */ 

4506 
substitute = 's', 

4507 
/** Insert current item from the source into the target. */ 

4508 
insert = 'i', 

4509 
/** Remove current item from the target. */ 

4510 
remove = 'r' 

4511 
} 

4512 


4513 
struct Levenshtein(Range, alias equals, CostType = size_t) 

4514 
{ 

4515 
void deletionIncrement(CostType n) 

4516 
{ 

4517 
_deletionIncrement = n; 

4518 
InitMatrix(); 

4519 
} 

4520 


4521 
void insertionIncrement(CostType n) 

4522 
{ 

4523 
_insertionIncrement = n; 

4524 
InitMatrix(); 

4525 
} 

4526 


4527 
CostType distance(Range s, Range t) 

4528 
{ 

4529 
auto slen = walkLength(s), tlen = walkLength(t); 

4530 
AllocMatrix(slen + 1, tlen + 1); 

4531 
foreach (i; 1 .. rows) 

4532 
{ 

4533 
auto sfront = s.front; 

4534 
s.popFront(); 

4535 
auto tt = t; 

4536 
foreach (j; 1 .. cols) 

4537 
{ 

4538 
auto cSub = _matrix[i  1][j  1] 

4539 
+ (equals(sfront, tt.front) ? 0 : _substitutionIncrement); 

4540 
tt.popFront(); 

4541 
auto cIns = _matrix[i][j  1] + _insertionIncrement; 

4542 
auto cDel = _matrix[i  1][j] + _deletionIncrement; 

4543 
switch (min_index(cSub, cIns, cDel)) { 

4544 
case 0: 

4545 
_matrix[i][j] = cSub; 

4546 
break; 

4547 
case 1: 

4548 
_matrix[i][j] = cIns; 

4549 
break; 

4550 
default: 

4551 
_matrix[i][j] = cDel; 

4552 
break; 

4553 
} 

4554 
} 

4555 
} 

4556 
return _matrix[slen][tlen]; 

4557 
} 

4558 


4559 
EditOp[] path(Range s, Range t) 

4560 
{ 

4561 
distance(s, t); 

4562 
return path(); 

4563 
} 

4564 


4565 
EditOp[] path() 

4566 
{ 

4567 
EditOp[] result; 

4568 
size_t i = rows  1, j = cols  1; 

4569 
// restore the path 

4570 
while (i  j) { 

4571 
auto cIns = j == 0 ? CostType.max : _matrix[i][j  1]; 

4572 
auto cDel = i == 0 ? CostType.max : _matrix[i  1][j]; 

4573 
auto cSub = i == 0  j == 0 

4574 
? CostType.max 

4575 
: _matrix[i  1][j  1]; 

4576 
switch (min_index(cSub, cIns, cDel)) { 

4577 
case 0: 

4578 
result ~= _matrix[i  1][j  1] == _matrix[i][j] 

4579 
? EditOp.none 

4580 
: EditOp.substitute; 

4581 
i; 

4582 
j; 

4583 
break; 

4584 
case 1: 

4585 
result ~= EditOp.insert; 

4586 
j; 

4587 
break; 

4588 
default: 

4589 
result ~= EditOp.remove; 

4590 
i; 

4591 
break; 

4592 
} 

4593 
} 

4594 
reverse(result); 

4595 
return result; 

4596 
} 

4597 


4598 
private: 

4599 
CostType _deletionIncrement = 1, 

4600 
_insertionIncrement = 1, 

4601 
_substitutionIncrement = 1; 

4602 
CostType[][] _matrix; 

4603 
size_t rows, cols; 

4604 


4605 
void AllocMatrix(size_t r, size_t c) { 

4606 
rows = r; 

4607 
cols = c; 

4608 
if (!_matrix  _matrix.length < r  _matrix[0].length < c) { 

4609 
delete _matrix; 

4610 
_matrix = new CostType[][](r, c); 

4611 
InitMatrix(); 

4612 
} 

4613 
} 

4614 


4615 
void InitMatrix() { 

4616 
foreach (i, row; _matrix) { 

4617 
row[0] = i * _deletionIncrement; 

4618 
} 

4619 
if (!_matrix) return; 

4620 
for (auto i = 0u; i != _matrix[0].length; ++i) { 

4621 
_matrix[0][i] = i * _insertionIncrement; 

4622 
} 

4623 
} 

4624 


4625 
static uint min_index(CostType i0, CostType i1, CostType i2) 

4626 
{ 

4627 
if (i0 <= i1) 

4628 
{ 

4629 
return i0 <= i2 ? 0 : 2; 

4630 
} 

4631 
else 

4632 
{ 

4633 
return i1 <= i2 ? 1 : 2; 

4634 
} 

4635 
} 

4636 
} 

4637 


4638 
/** 

4639 
Returns the $(WEB wikipedia.org/wiki/Levenshtein_distance, Levenshtein 

4640 
distance) between $(D s) and $(D t). The Levenshtein distance computes 

4641 
the minimal amount of edit operations necessary to transform $(D s) 

4642 
into $(D t). Performs $(BIGOH s.length * t.length) evaluations of $(D 

4643 
equals) and occupies $(BIGOH s.length * t.length) storage. 

4644 


4645 
Example: 

4646 
 

4647 
assert(levenshteinDistance("cat", "rat") == 1); 

4648 
assert(levenshteinDistance("parks", "spark") == 2); 

4649 
assert(levenshteinDistance("kitten", "sitting") == 3); 

4650 
// ignore case 

4651 
assert(levenshteinDistance!("toupper(a) == toupper(b)") 

4652 
("parks", "SPARK") == 2); 

4653 
 

4654 
*/ 

4655 
size_t levenshteinDistance(alias equals = "a == b", Range1, Range2) 

4656 
(Range1 s, Range2 t) 

4657 
if (isForwardRange!(Range1) && isForwardRange!(Range2)) 

4658 
{ 

4659 
Levenshtein!(Range1, binaryFun!(equals), size_t) lev; 

4660 
return lev.distance(s, t); 

4661 
} 

4662 


4663 
/** 

4664 
Returns the Levenshtein distance and the edit path between $(D s) and 

4665 
$(D t). 

4666 


4667 
Example: 

4668 
 

4669 
string a = "Saturday", b = "Sunday"; 

4670 
auto p = levenshteinDistanceAndPath(a, b); 

4671 
assert(p[0] == 3); 

4672 
assert(equal(p[1], "nrrnsnnn")); 

4673 
 

4674 
*/ 

4675 
Tuple!(size_t, EditOp[]) 

4676 
levenshteinDistanceAndPath(alias equals = "a == b", Range1, Range2) 

4677 
(Range1 s, Range2 t) 

4678 
if (isForwardRange!(Range1) && isForwardRange!(Range2)) 

4679 
{ 

4680 
Levenshtein!(Range1, binaryFun!(equals)) lev; 

4681 
auto d = lev.distance(s, t); 

4682 
return tuple(d, lev.path); 

4683 
} 

4684 


4685 
unittest 

4686 
{ 

4687 
debug(std_algorithm) scope(success) 

4688 
writeln("unittest @", __FILE__, ":", __LINE__, " done."); 

4689 
assert(levenshteinDistance("a", "a") == 0); 

4690 
assert(levenshteinDistance("a", "b") == 1); 

4691 
assert(levenshteinDistance("aa", "ab") == 1); 

4692 
assert(levenshteinDistance("aa", "abc") == 2); 

4693 
assert(levenshteinDistance("Saturday", "Sunday") == 3); 

4694 
assert(levenshteinDistance("kitten", "sitting") == 3); 

4695 
//lev.deletionIncrement = 2; 

4696 
//lev.insertionIncrement = 100; 

4697 
string a = "Saturday", b = "Sunday"; 

4698 
auto p = levenshteinDistanceAndPath(a, b); 

4699 
assert(cast(string) p[1] == "nrrnsnnn"); 

4700 
} 

4701 


4702 
// copy 

4703 
/** 

4704 
Copies the content of $(D source) into $(D target) and returns the 

4705 
remaining (unfilled) part of $(D target). See also $(WEB 

4706 
sgi.com/tech/stl/_copy.html, STL's copy). If a behavior similar to 

4707 
$(WEB sgi.com/tech/stl/copy_backward.html, STL's copy_backward) is 

4708 
needed, use $(D copy(retro(source), retro(target))). See also $(XREF 

4709 
range, retro). 

4710 


4711 
Example: 

4712 
 

4713 
int[] a = [ 1, 5 ]; 

4714 
int[] b = [ 9, 8 ]; 

4715 
int[] c = new int[a.length + b.length + 10]; 

4716 
auto d = copy(b, copy(a, c)); 

4717 
assert(c[0 .. a.length + b.length] == a ~ b); 

4718 
assert(d.length == 10); 

4719 
 

4720 


4721 
As long as the target range elements support assignment from source 

4722 
range elements, different types of ranges are accepted. 

4723 


4724 
Example: 

4725 
 

4726 
float[] a = [ 1.0f, 5 ]; 

4727 
double[] b = new double[a.length]; 

4728 
auto d = copy(a, b); 

4729 
 

4730 


4731 
To copy at most $(D n) elements from range $(D a) to range $(D b), you 

4732 
may want to use $(D copy(take(a, n), b)). To copy those elements from 

4733 
range $(D a) that satisfy predicate $(D pred) to range $(D b), you may 

4734 
want to use $(D copy(filter!(pred)(a), b)). 

4735 


4736 
Example: 

4737 
 

4738 
int[] a = [ 1, 5, 8, 9, 10, 1, 2, 0 ]; 

4739 
auto b = new int[a.length]; 

4740 
auto c = copy(filter!("(a & 1) == 1")(a), b); 

4741 
assert(b[0 .. $  c.length] == [ 1, 5, 9, 1 ]); 

4742 
 

4743 


4744 
*/ 

4745 
Range2 copy(Range1, Range2)(Range1 source, Range2 target) 

4746 
if (isInputRange!Range1 && isOutputRange!(Range2, ElementType!Range1)) 

4747 
{ 

4748 
for (; !source.empty; source.popFront()) 

4749 
{ 

4750 
put(target, source.front); 

4751 
} 

4752 
return target; 

4753 
} 

4754 


4755 
unittest 

4756 
{ 

4757 
debug(std_algorithm) scope(success) 

4758 
writeln("unittest @", __FILE__, ":", __LINE__, " done."); 

4759 
{ 

4760 
int[] a = [ 1, 5 ]; 

4761 
int[] b = [ 9, 8 ]; 

4762 
int[] c = new int[a.length + b.length + 10]; 

4763 
auto d = copy(b, copy(a, c)); 

4764 
assert(c[0 .. a.length + b.length] == a ~ b); 

4765 
assert(d.length == 10); 

4766 
} 

4767 
{ 

4768 
int[] a = [ 1, 5 ]; 

4769 
int[] b = [ 9, 8 ]; 

4770 
auto e = copy(filter!("a > 1")(a), b); 

4771 
assert(b[0] == 5 && e.length == 1); 

4772 
} 

4773 
} 

4774 


4775 
// swapRanges 

4776 
/** 

4777 
Swaps all elements of $(D r1) with successive elements in $(D r2). 

4778 
Returns a tuple containing the remainder portions of $(D r1) and $(D 

4779 
r2) that were not swapped (one of them will be empty). The ranges may 

4780 
be of different types but must have the same element type and support 

4781 
swapping. 

4782 


4783 
Example: 

4784 
 

4785 
int[] a = [ 100, 101, 102, 103 ]; 

4786 
int[] b = [ 0, 1, 2, 3 ]; 

4787 
auto c = swapRanges(a[1 .. 3], b[2 .. 4]); 

4788 
assert(c[0].empty && c[1].empty); 

4789 
assert(a == [ 100, 2, 3, 103 ]); 

4790 
assert(b == [ 0, 1, 101, 102 ]); 

4791 
 

4792 
*/ 

4793 
Tuple!(Range1, Range2) 

4794 
swapRanges(Range1, Range2)(Range1 r1, Range2 r2) 

4795 
if (isInputRange!(Range1) && isInputRange!(Range2) 

4796 
&& hasSwappableElements!(Range1) && hasSwappableElements!(Range2) 

4797 
&& is(ElementType!(Range1) == ElementType!(Range2))) 

4798 
{ 

4799 
for (; !r1.empty && !r2.empty; r1.popFront, r2.popFront) 

4800 
{ 

4801 
swap(r1.front, r2.front); 

4802 
} 

4803 
return tuple(r1, r2); 

4804 
} 

4805 


4806 
unittest 

4807 
{ 

4808 
debug(std_algorithm) scope(success) 

4809 
writeln("unittest @", __FILE__, ":", __LINE__, " done."); 

4810 
int[] a = [ 100, 101, 102, 103 ]; 

4811 
int[] b = [ 0, 1, 2, 3 ]; 

4812 
auto c = swapRanges(a[1 .. 3], b[2 .. 4]); 

4813 
assert(c[0].empty && c[1].empty); 

4814 
assert(a == [ 100, 2, 3, 103 ]); 

4815 
assert(b == [ 0, 1, 101, 102 ]); 

4816 
} 

4817 


4818 
// reverse 

4819 
/** 

4820 
Reverses $(D r) inplace. Performs $(D r.length) evaluations of $(D 

4821 
swap). See also $(WEB sgi.com/tech/stl/_reverse.html, STL's reverse). 

4822 


4823 
Example: 

4824 
 

4825 
int[] arr = [ 1, 2, 3 ]; 

4826 
reverse(arr); 

4827 
assert(arr == [ 3, 2, 1 ]); 

4828 
 

4829 
*/ 

4830 
void reverse(Range)(Range r) 

4831 
if (isBidirectionalRange!(Range) && hasSwappableElements!(Range)) 

4832 
{ 

4833 
while (!r.empty) 

4834 
{ 

4835 
swap(r.front, r.back); 

4836 
r.popFront; 

4837 
if (r.empty) break; 

4838 
r.popBack; 

4839 
} 

4840 
} 

4841 


4842 
unittest 

4843 
{ 

4844 
debug(std_algorithm) scope(success) 

4845 
writeln("unittest @", __FILE__, ":", __LINE__, " done."); 

4846 
int[] range = null; 

4847 
reverse(range); 

4848 
range = [ 1 ]; 

4849 
reverse(range); 

4850 
assert(range == [1]); 

4851 
range = [1, 2]; 

4852 
reverse(range); 

4853 
assert(range == [2, 1]); 

4854 
range = [1, 2, 3]; 

4855 
reverse(range); 

4856 
assert(range == [3, 2, 1]); 

4857 
} 

4858 


4859 
// bringToFront 

4860 
/** 

4861 
The $(D bringToFront) function has considerable flexibility and 

4862 
usefulness. It can rotate elements in one buffer left or right, swap 

4863 
buffers of equal length, and even move elements across disjoint 

4864 
buffers of different types and different lengths. 

4865 


4866 
$(D bringToFront) takes two ranges $(D front) and $(D back), which may 

4867 
be of different types. Considering the concatenation of $(D front) and 

4868 
$(D back) one unified range, $(D bringToFront) rotates that unified 

4869 
range such that all elements in $(D back) are brought to the beginning 

4870 
of the unified range. The relative ordering of elements in $(D front) 

4871 
and $(D back), respectively, remains unchanged. 

4872 


4873 
The simplest use of $(D bringToFront) is for rotating elements in a 

4874 
buffer. For example: 

4875 


4876 
 

4877 
auto arr = [4, 5, 6, 7, 1, 2, 3]; 

4878 
bringToFront(arr[0 .. 4], arr[4 .. $]); 

4879 
assert(arr == [ 1, 2, 3, 4, 5, 6, 7 ]); 

4880 
 

4881 


4882 
The $(D front) range may actually "step over" the $(D back) 

4883 
range. This is very useful with forward ranges that cannot compute 

4884 
comfortably rightbounded subranges like $(D arr[0 .. 4]) above. In 

4885 
the example below, $(D r2) is a right subrange of $(D r1). 

4886 


4887 
 

4888 
auto list = SList!(int)(4, 5, 6, 7, 1, 2, 3); 

4889 
auto r1 = list[]; 

4890 
auto r2 = list[]; popFrontN(r2, 4); 

4891 
assert(equal(r2, [ 1, 2, 3 ])); 

4892 
bringToFront(r1, r2); 

4893 
assert(equal(list[], [ 1, 2, 3, 4, 5, 6, 7 ])); 

4894 
 

4895 


4896 
Elements can be swapped across ranges of different types: 

4897 


4898 
 

4899 
auto list = SList!(int)(4, 5, 6, 7); 

4900 
auto vec = [ 1, 2, 3 ]; 

4901 
bringToFront(list[], vec); 

4902 
assert(equal(list[], [ 1, 2, 3, 4 ])); 

4903 
assert(equal(vec, [ 5, 6, 7 ])); 

4904 
 

4905 


4906 
Performs $(BIGOH max(front.length, back.length)) evaluations of $(D 

4907 
swap). See also $(WEB sgi.com/tech/stl/_rotate.html, STL's rotate). 

4908 


4909 
Preconditions: 

4910 


4911 
Either $(D front) and $(D back) are disjoint, or $(D back) is 

4912 
reachable from $(D front) and $(D front) is not reachable from $(D 

4913 
back). 

4914 


4915 
Returns: 

4916 


4917 
The number of elements brought to the front, i.e., the length of $(D 

4918 
back). 

4919 
*/ 

4920 
size_t bringToFront(Range1, Range2)(Range1 front, Range2 back) 

4921 
if (isInputRange!Range1 && isForwardRange!Range2) 

4922 
{ 

4923 
enum bool sameHeadExists = is(typeof(front.sameHead(back))); 

4924 
size_t result; 

4925 
for (bool semidone; !front.empty && !back.empty; ) 

4926 
{ 

4927 
static if (sameHeadExists) 

4928 
{ 

4929 
if (front.sameHead(back)) break; // shortcut 

4930 
} 

4931 
// Swap elements until front and/or back ends. 

4932 
auto back0 = back.save; 

4933 
size_t nswaps; 

4934 
do 

4935 
{ 

4936 
static if (sameHeadExists) 

4937 
{ 

4938 
// Detect the steppingover condition. 

4939 
if (front.sameHead(back0)) back0 = back.save; 

4940 
} 

4941 
swapFront(front, back); 

4942 
++nswaps; 

4943 
front.popFront(); 

4944 
back.popFront(); 

4945 
} 

4946 
while (!front.empty && !back.empty); 

4947 


4948 
if (!semidone) result += nswaps; 

4949 


4950 
// Now deal with the remaining elements. 

4951 
if (back.empty) 

4952 
{ 

4953 
if (front.empty) break; 

4954 
// Right side was shorter, which means that we've brought 

4955 
// all the back elements to the front. 

4956 
semidone = true; 

4957 
// Next pass: bringToFront(front, back0) to adjust the rest. 

4958 
back = back0; 

4959 
} 

4960 
else 

4961 
{ 

4962 
assert(front.empty); 

4963 
// Left side was shorter. Let's step into the back. 

4964 
static if (is(Range1 == Take!Range2)) 

4965 
{ 

4966 
front = take(back0, nswaps); 

4967 
} 

4968 
else 

4969 
{ 

4970 
immutable subresult = bringToFront(take(back0, nswaps), 

4971 
back); 

4972 
if (!semidone) result += subresult; 

4973 
break; // done 

4974 
} 

4975 
} 

4976 
} 

4977 
return result; 

4978 
} 

4979 


4980 
unittest 

4981 
{ 

4982 
debug(std_algorithm) scope(success) 

4983 
writeln("unittest @", __FILE__, ":", __LINE__, " done."); 

4984 
// doc example 

4985 
{ 

4986 
int[] arr = [4, 5, 6, 7, 1, 2, 3]; 

4987 
auto p = bringToFront(arr[0 .. 4], arr[4 .. $]); 

4988 
assert(p == arr.length  4); 

4989 
assert(arr == [ 1, 2, 3, 4, 5, 6, 7 ], text(arr)); 

4990 
} 

4991 
{ 

4992 
auto list = SList!(int)(4, 5, 6, 7, 1, 2, 3); 

4993 
auto r1 = list[]; 

4994 
auto r2 = list[]; popFrontN(r2, 4); 

4995 
assert(equal(r2, [ 1, 2, 3 ])); 

4996 
bringToFront(r1, r2); 

4997 
assert(equal(list[], [ 1, 2, 3, 4, 5, 6, 7 ])); 

4998 
} 

4999 
{ 

5000 
auto list = SList!(int)(4, 5, 6, 7); 

5001 
auto vec = [ 1, 2, 3 ]; 

5002 
bringToFront(list[], vec); 

5003 
assert(equal(list[], [ 1, 2, 3, 4 ])); 

5004 
assert(equal(vec, [ 5, 6, 7 ])); 

5005 
} 

5006 
// a more elaborate test 

5007 
{ 

5008 
auto rnd = Random(unpredictableSeed); 

5009 
int[] a = new int[uniform(100, 200, rnd)]; 

5010 
int[] b = new int[uniform(100, 200, rnd)]; 

5011 
foreach (ref e; a) e = uniform(100, 100, rnd); 

5012 
foreach (ref e; b) e = uniform(100, 100, rnd); 

5013 
int[] c = a ~ b; 

5014 
// writeln("a= ", a); 

5015 
// writeln("b= ", b); 

5016 
auto n = bringToFront(c[0 .. a.length], c[a.length .. $]); 

5017 
//writeln("c= ", c); 

5018 
assert(n == 
