1 
// Written in the D programming language. 

2 


3 
/** 

4 
Defines generic _containers. 

5 


6 
Macros: 

7 
WIKI = Phobos/StdContainer 

8 
TEXTWITHCOMMAS = $0 

9 
LEADINGROW = <tr style=leadingrow bgcolor=#E4E9EF><td colspan=3><b><em>$0</em></b></td></tr> 

10 


11 
Copyright: Redblack tree code copyright (C) 2008 by Steven Schveighoffer. Other code 

12 
copyright 2010 Andrei Alexandrescu. All rights reserved by the respective holders. 

13 


14 
License: Distributed under the Boost Software License, Version 1.0. 

15 
(See accompanying file LICENSE_1_0.txt or copy at $(WEB 

16 
boost.org/LICENSE_1_0.txt)). 

17 


18 
Authors: Steven Schveighoffer, $(WEB erdani.com, Andrei Alexandrescu) 

19 


20 
$(BOOKTABLE $(TEXTWITHCOMMAS Container primitives. Below, $(D C) means 

21 
a _container type, $(D c) is a value of _container type, $(D n$(SUB 

22 
x)) represents the effective length of value $(D x), which could be a 

23 
single element (in which case $(D n$(SUB x)) is $(D 1)), a _container, 

24 
or a range.), 

25 


26 
$(TR $(TH Syntax) $(TH $(BIGOH ·)) $(TH Description)) 

27 


28 
$(TR $(TDNW $(D C(x))) $(TDNW $(D n$(SUB x))) $(TD Creates a 

29 
_container of type $(D C) from either another _container or a range.)) 

30 


31 
$(TR $(TDNW $(D c.dup)) $(TDNW $(D n$(SUB c))) $(TD Returns a 

32 
duplicate of the _container.)) 

33 


34 
$(TR $(TDNW $(D c ~ x)) $(TDNW $(D n$(SUB c) + n$(SUB x))) $(TD 

35 
Returns the concatenation of $(D c) and $(D r). $(D x) may be a single 

36 
element or an input range.)) 

37 


38 
$(TR $(TDNW $(D x ~ c)) $(TDNW $(D n$(SUB c) + n$(SUB x))) $(TD 

39 
Returns the concatenation of $(D x) and $(D c). $(D x) may be a 

40 
single element or an input range type.)) 

41 


42 
$(LEADINGROW Iteration) 

43 


44 
$(TR $(TD $(D c.Range)) $(TD) $(TD The primary range 

45 
type associated with the _container.)) 

46 


47 
$(TR $(TD $(D c[])) $(TDNW $(D log n$(SUB c))) $(TD Returns a range 

48 
iterating over the entire _container, in a _containerdefined order.)) 

49 


50 
$(TR $(TDNW $(D c[a, b])) $(TDNW $(D log n$(SUB c))) $(TD Fetches a 

51 
portion of the _container from key $(D a) to key $(D b).)) 

52 


53 
$(LEADINGROW Capacity) 

54 


55 
$(TR $(TD $(D c.empty)) $(TD $(D 1)) $(TD Returns $(D true) if the 

56 
_container has no elements, $(D false) otherwise.)) 

57 


58 
$(TR $(TD $(D c.length)) $(TDNW $(D log n$(SUB c))) $(TD Returns the 

59 
number of elements in the _container.)) 

60 


61 
$(TR $(TDNW $(D c.length = n)) $(TDNW $(D n$(SUB c) + n)) $(TD Forces 

62 
the number of elements in the _container to $(D n). If the _container 

63 
ends up growing, the added elements are initialized in a 

64 
_containerdependent manner (usually with $(D T.init)).)) 

65 


66 
$(TR $(TD $(D c.capacity)) $(TDNW $(D log n$(SUB c))) $(TD Returns the 

67 
maximum number of elements that can be stored in the _container 

68 
without triggering a reallocation.)) 

69 


70 
$(TR $(TD $(D c.reserve(x))) $(TD $(D n$(SUB c))) $(TD Forces $(D 

71 
capacity) to at least $(D x) without reducing it.)) 

72 


73 
$(LEADINGROW Access) 

74 


75 
$(TR $(TDNW $(D c.front)) $(TDNW $(D log n$(SUB c))) $(TD Returns the 

76 
first element of the _container, in a _containerdefined order.)) 

77 


78 
$(TR $(TDNW $(D c.moveFront)) $(TDNW $(D log n$(SUB c))) $(TD 

79 
Destructively reads and returns the first element of the 

80 
_container. The slot is not removed from the _container; it is left 

81 
initalized with $(D T.init). This routine need not be defined if $(D 

82 
front) returns a $(D ref).)) 

83 


84 
$(TR $(TDNW $(D c.front = v)) $(TDNW $(D log n$(SUB c))) $(TD Assigns 

85 
$(D v) to the first element of the _container.)) 

86 


87 
$(TR $(TDNW $(D c.back)) $(TDNW $(D log n$(SUB c))) $(TD Returns the 

88 
last element of the _container, in a _containerdefined order.)) 

89 


90 
$(TR $(TDNW $(D c.moveBack)) $(TDNW $(D log n$(SUB c))) $(TD 

91 
Destructively reads and returns the first element of the 

92 
container. The slot is not removed from the _container; it is left 

93 
initalized with $(D T.init). This routine need not be defined if $(D 

94 
front) returns a $(D ref).)) 

95 


96 
$(TR $(TDNW $(D c.back = v)) $(TDNW $(D log n$(SUB c))) $(TD Assigns 

97 
$(D v) to the last element of the _container.)) 

98 


99 
$(TR $(TDNW $(D c[x])) $(TDNW $(D log n$(SUB c))) $(TD Provides 

100 
indexed access into the _container. The index type is 

101 
_containerdefined. A container may define several index types (and 

102 
consequently overloaded indexing).)) 

103 


104 
$(TR $(TDNW $(D c.moveAt(x))) $(TDNW $(D log n$(SUB c))) $(TD 

105 
Destructively reads and returns the value at position $(D x). The slot 

106 
is not removed from the _container; it is left initialized with $(D 

107 
T.init).)) 

108 


109 
$(TR $(TDNW $(D c[x] = v)) $(TDNW $(D log n$(SUB c))) $(TD Sets 

110 
element at specified index into the _container.)) 

111 


112 
$(TR $(TDNW $(D c[x] $(I op)= v)) $(TDNW $(D log n$(SUB c))) 

113 
$(TD Performs readmodifywrite operation at specified index into the 

114 
_container.)) 

115 


116 
$(LEADINGROW Operations) 

117 


118 
$(TR $(TDNW $(D e in c)) $(TDNW $(D log n$(SUB c))) $(TD 

119 
Returns nonzero if e is found in $(D c).)) 

120 


121 
$(TR $(TDNW $(D c.lowerBound(v))) $(TDNW $(D log n$(SUB c))) $(TD 

122 
Returns a range of all elements strictly less than $(D v).)) 

123 


124 
$(TR $(TDNW $(D c.upperBound(v))) $(TDNW $(D log n$(SUB c))) $(TD 

125 
Returns a range of all elements strictly greater than $(D v).)) 

126 


127 
$(TR $(TDNW $(D c.equalRange(v))) $(TDNW $(D log n$(SUB c))) $(TD 

128 
Returns a range of all elements in $(D c) that are equal to $(D v).)) 

129 


130 
$(LEADINGROW Modifiers) 

131 


132 
$(TR $(TDNW $(D c ~= x)) $(TDNW $(D n$(SUB c) + n$(SUB x))) 

133 
$(TD Appends $(D x) to $(D c). $(D x) may be a single element or an 

134 
input range type.)) 

135 


136 
$(TR $(TDNW $(D c.clear())) $(TDNW $(D n$(SUB c))) $(TD Removes all 

137 
elements in $(D c).)) 

138 


139 
$(TR $(TDNW $(D c.insert(x))) $(TDNW $(D n$(SUB x) * log n$(SUB c))) 

140 
$(TD Inserts $(D x) in $(D c) at a position (or positions) chosen by $(D c).)) 

141 


142 
$(TR $(TDNW $(D c.stableInsert(x))) 

143 
$(TDNW $(D n$(SUB x) * log n$(SUB c))) $(TD Same as $(D c.insert(x)), 

144 
but is guaranteed to not invalidate any ranges.)) 

145 


146 
$(TR $(TDNW $(D c.linearInsert(v))) $(TDNW $(D n$(SUB c))) $(TD Same 

147 
as $(D c.insert(v)) but relaxes complexity to linear.)) 

148 


149 
$(TR $(TDNW $(D c.stableLinearInsert(v))) $(TDNW $(D n$(SUB c))) 

150 
$(TD Same as $(D c.stableInsert(v)) but relaxes complexity to linear.)) 

151 


152 
$(TR $(TDNW $(D c.removeAny())) $(TDNW $(D log n$(SUB c))) 

153 
$(TD Removes some element from $(D c) and returns it.)) 

154 


155 
$(TR $(TDNW $(D c.stableRemoveAny(v))) $(TDNW $(D log n$(SUB c))) 

156 
$(TD Same as $(D c.removeAny(v)), but is guaranteed to not invalidate any 

157 
iterators.)) 

158 


159 
$(TR $(TDNW $(D c.insertFront(v))) $(TDNW $(D log n$(SUB c))) 

160 
$(TD Inserts $(D v) at the front of $(D c).)) 

161 


162 
$(TR $(TDNW $(D c.stableInsertFront(v))) $(TDNW $(D log n$(SUB c))) 

163 
$(TD Same as $(D c.insertFront(v)), but guarantees no ranges will be 

164 
invalidated.)) 

165 


166 
$(TR $(TDNW $(D c.insertBack(v))) $(TDNW $(D log n$(SUB c))) 

167 
$(TD Inserts $(D v) at the back of $(D c).)) 

168 


169 
$(TR $(TDNW $(D c.stableInsertBack(v))) $(TDNW $(D log n$(SUB c))) 

170 
$(TD Same as $(D c.insertBack(v)), but guarantees no ranges will be 

171 
invalidated.)) 

172 


173 
$(TR $(TDNW $(D c.removeFront())) $(TDNW $(D log n$(SUB c))) 

174 
$(TD Removes the element at the front of $(D c).)) 

175 


176 
$(TR $(TDNW $(D c.stableRemoveFront())) $(TDNW $(D log n$(SUB c))) 

177 
$(TD Same as $(D c.removeFront()), but guarantees no ranges will be 

178 
invalidated.)) 

179 


180 
$(TR $(TDNW $(D c.removeBack())) $(TDNW $(D log n$(SUB c))) 

181 
$(TD Removes the value at the back of $(D c).)) 

182 


183 
$(TR $(TDNW $(D c.stableRemoveBack())) $(TDNW $(D log n$(SUB c))) 

184 
$(TD Same as $(D c.removeBack()), but guarantees no ranges will be 

185 
invalidated.)) 

186 


187 
$(TR $(TDNW $(D c.remove(r))) $(TDNW $(D n$(SUB r) * log n$(SUB c))) 

188 
$(TD Removes range $(D r) from $(D c).)) 

189 


190 
$(TR $(TDNW $(D c.stableRemove(r))) 

191 
$(TDNW $(D n$(SUB r) * log n$(SUB c))) 

192 
$(TD Same as $(D c.remove(r)), but guarantees iterators are not 

193 
invalidated.)) 

194 


195 
$(TR $(TDNW $(D c.linearRemove(r))) $(TDNW $(D n$(SUB c))) 

196 
$(TD Removes range $(D r) from $(D c).)) 

197 


198 
$(TR $(TDNW $(D c.stableLinearRemove(r))) $(TDNW $(D n$(SUB c))) 

199 
$(TD Same as $(D c.linearRemove(r)), but guarantees iterators are not 

200 
invalidated.)) 

201 


202 
$(TR $(TDNW $(D c.removeKey(k))) $(TDNW $(D log n$(SUB c))) 

203 
$(TD Removes an element from $(D c) by using its key $(D k). 

204 
The key's type is defined by the _container.)) 

205 


206 
$(TR $(TDNW $(D )) $(TDNW $(D )) $(TD )) 

207 


208 
) 

209 
*/ 

210 
module std.container; 

211 


212 
import core.memory, core.stdc.stdlib, core.stdc.string, std.algorithm, 

213 
std.conv, std.exception, std.functional, std.range, std.traits, 

214 
std.typecons, std.typetuple; 

215 
version(unittest) import std.stdio; 

216 


217 
version(unittest) version = RBDoChecks; 

218 


219 
//version = RBDoChecks; 

220 


221 
version(RBDoChecks) 

222 
{ 

223 
import std.stdio; 

224 
} 

225 


226 


227 


228 
/* The following documentation and type $(D TotalContainer) are 

229 
intended for developers only. 

230 


231 
$(D TotalContainer) is an unimplemented container that illustrates a 

232 
host of primitives that a container may define. It is to some extent 

233 
the bottom of the conceptual container hierarchy. A given container 

234 
most often will choose to only implement a subset of these primitives, 

235 
and define its own additional ones. Adhering to the standard primitive 

236 
names below allows generic code to work independently of containers. 

237 


238 
Things to remember: any container must be a reference type, whether 

239 
implemented as a $(D class) or $(D struct). No primitive below 

240 
requires the container to escape addresses of elements, which means 

241 
that compliant containers can be defined to use reference counting or 

242 
other deterministic memory management techniques. 

243 


244 
A container may choose to define additional specific operations. The 

245 
only requirement is that those operations bear different names than 

246 
the ones below, lest user code gets confused. 

247 


248 
Complexity of operations should be interpreted as "at least as good 

249 
as". If an operation is required to have $(BIGOH n) complexity, it 

250 
could have anything lower than that, e.g. $(BIGOH log(n)). Unless 

251 
specified otherwise, $(D n) inside a $(BIGOH) expression stands for 

252 
the number of elements in the container. 

253 
*/ 

254 
struct TotalContainer(T) 

255 
{ 

256 
/** 

257 
If the container has a notion of keyvalue mapping, $(D KeyType) 

258 
defines the type of the key of the container. 

259 
*/ 

260 
alias T KeyType; 

261 


262 
/** 

263 
If the container has a notion of multikeyvalue mapping, $(D 

264 
KeyTypes[k]), where $(D k) is a zerobased unsigned number, defines 

265 
the type of the $(D k)th key of the container. 

266 


267 
A container may define both $(D KeyType) and $(D KeyTypes), e.g. in 

268 
the case it has the notion of primary/preferred key. 

269 
*/ 

270 
alias TypeTuple!(T) KeyTypes; 

271 


272 
/** 

273 
If the container has a notion of keyvalue mapping, $(D ValueType) 

274 
defines the type of the value of the container. Typically, a mapstyle 

275 
container mapping values of type $(D K) to values of type $(D V) 

276 
defines $(D KeyType) to be $(D K) and $(D ValueType) to be $(D V). 

277 
*/ 

278 
alias T ValueType; 

279 


280 
/** 

281 
Defines the container's primary range, which embodies one of the 

282 
ranges defined in $(XREFMODULE range). 

283 


284 
Generally a container may define several types of ranges. 

285 
*/ 

286 
struct Range 

287 
{ 

288 
/// Range primitives. 

289 
@property bool empty() 

290 
{ 

291 
assert(0); 

292 
} 

293 
/// Ditto 

294 
@property T front() 

295 
{ 

296 
assert(0); 

297 
} 

298 
/// Ditto 

299 
T moveFront() 

300 
{ 

301 
assert(0); 

302 
} 

303 
/// Ditto 

304 
void popFront() 

305 
{ 

306 
assert(0); 

307 
} 

308 
/// Ditto 

309 
@property T back() 

310 
{ 

311 
assert(0); 

312 
} 

313 
/// Ditto 

314 
T moveBack() 

315 
{ 

316 
assert(0); 

317 
} 

318 
/// Ditto 

319 
void popBack() 

320 
{ 

321 
assert(0); 

322 
} 

323 
/// Ditto 

324 
T opIndex(size_t i) 

325 
{ 

326 
assert(0); 

327 
} 

328 
/// Ditto 

329 
void opIndexAssign(T value, size_t i) 

330 
{ 

331 
assert(0); 

332 
} 

333 
/// Ditto 

334 
void opIndexOpAssign(string op)(T value, uint i) 

335 
{ 

336 
assert(0); 

337 
} 

338 
/// Ditto 

339 
T moveAt(size_t i) 

340 
{ 

341 
assert(0); 

342 
} 

343 
/// Ditto 

344 
@property size_t length() 

345 
{ 

346 
assert(0); 

347 
} 

348 
} 

349 


350 
/** 

351 
Property returning $(D true) if and only if the container has no 

352 
elements. 

353 


354 
Complexity: $(BIGOH 1) 

355 
*/ 

356 
@property bool empty() 

357 
{ 

358 
assert(0); 

359 
} 

360 


361 
/** 

362 
Returns a duplicate of the container. The elements themselves are not 

363 
transitively duplicated. 

364 


365 
Complexity: $(BIGOH n). 

366 
*/ 

367 
@property TotalContainer dup() 

368 
{ 

369 
assert(0); 

370 
} 

371 


372 
/** 

373 
Returns the number of elements in the container. 

374 


375 
Complexity: $(BIGOH log(n)). 

376 
*/ 

377 
@property size_t length() 

378 
{ 

379 
assert(0); 

380 
} 

381 


382 
/** 

383 
Returns the maximum number of elements the container can store without 

384 
(a) allocating memory, (b) invalidating iterators upon insertion. 

385 


386 
Complexity: $(BIGOH log(n)). 

387 
*/ 

388 
@property size_t capacity() 

389 
{ 

390 
assert(0); 

391 
} 

392 


393 
/** 

394 
Ensures sufficient capacity to accommodate $(D n) elements. 

395 


396 
Postcondition: $(D capacity >= n) 

397 


398 
Complexity: $(BIGOH log(e  capacity)) if $(D e > capacity), otherwise 

399 
$(BIGOH 1). 

400 
*/ 

401 
void reserve(size_t e) 

402 
{ 

403 
assert(0); 

404 
} 

405 


406 
/** 

407 
Returns a range that iterates over all elements of the container, in a 

408 
containerdefined order. The container should choose the most 

409 
convenient and fast method of iteration for $(D opSlice()). 

410 


411 
Complexity: $(BIGOH log(n)) 

412 
*/ 

413 
Range opSlice() 

414 
{ 

415 
assert(0); 

416 
} 

417 


418 
/** 

419 
Returns a range that iterates the container between two 

420 
specified positions. 

421 


422 
Complexity: $(BIGOH log(n)) 

423 
*/ 

424 
Range opSlice(size_t a, size_t b) 

425 
{ 

426 
assert(0); 

427 
} 

428 


429 
/** 

430 
Forward to $(D opSlice().front) and $(D opSlice().back), respectively. 

431 


432 
Complexity: $(BIGOH log(n)) 

433 
*/ 

434 
@property T front() 

435 
{ 

436 
assert(0); 

437 
} 

438 
/// Ditto 

439 
T moveFront() 

440 
{ 

441 
assert(0); 

442 
} 

443 
/// Ditto 

444 
@property T back() 

445 
{ 

446 
assert(0); 

447 
} 

448 
/// Ditto 

449 
T moveBack() 

450 
{ 

451 
assert(0); 

452 
} 

453 


454 
/** 

455 
Indexing operators yield or modify the value at a specified index. 

456 
*/ 

457 
/** 

458 
Indexing operators yield or modify the value at a specified index. 

459 
*/ 

460 
ValueType opIndex(KeyType) 

461 
{ 

462 
assert(0); 

463 
} 

464 
/// ditto 

465 
void opIndexAssign(KeyType) 

466 
{ 

467 
assert(0); 

468 
} 

469 
/// ditto 

470 
void opIndexOpAssign(string op)(KeyType) 

471 
{ 

472 
assert(0); 

473 
} 

474 
T moveAt(size_t i) 

475 
{ 

476 
assert(0); 

477 
} 

478 


479 
/** 

480 
$(D k in container) returns true if the given key is in the container. 

481 
*/ 

482 
bool opBinary(string op)(KeyType k) if (op == "in") 

483 
{ 

484 
assert(0); 

485 
} 

486 


487 
/** 

488 
Returns a range of all elements containing $(D k) (could be empty or a 

489 
singleton range). 

490 
*/ 

491 
Range equalRange(KeyType k) 

492 
{ 

493 
assert(0); 

494 
} 

495 


496 
/** 

497 
Returns a range of all elements with keys less than $(D k) (could be 

498 
empty or a singleton range). Only defined by containers that store 

499 
data sorted at all times. 

500 
*/ 

501 
Range lowerBound(KeyType k) 

502 
{ 

503 
assert(0); 

504 
} 

505 


506 
/** 

507 
Returns a range of all elements with keys larger than $(D k) (could be 

508 
empty or a singleton range). Only defined by containers that store 

509 
data sorted at all times. 

510 
*/ 

511 
Range upperBound(KeyType k) 

512 
{ 

513 
assert(0); 

514 
} 

515 


516 
/** 

517 
Returns a new container that's the concatenation of $(D this) and its 

518 
argument. $(D opBinaryRight) is only defined if $(D Stuff) does not 

519 
define $(D opBinary). 

520 


521 
Complexity: $(BIGOH n + m), where m is the number of elements in $(D 

522 
stuff) 

523 
*/ 

524 
TotalContainer opBinary(string op)(Stuff rhs) if (op == "~") 

525 
{ 

526 
assert(0); 

527 
} 

528 


529 
/// ditto 

530 
TotalContainer opBinaryRight(string op)(Stuff lhs) if (op == "~") 

531 
{ 

532 
assert(0); 

533 
} 

534 


535 
/** 

536 
Forwards to $(D insertAfter(this[], stuff)). 

537 
*/ 

538 
void opOpAssign(string op)(Stuff stuff) if (op == "~") 

539 
{ 

540 
assert(0); 

541 
} 

542 


543 
/** 

544 
Removes all contents from the container. The container decides how $(D 

545 
capacity) is affected. 

546 


547 
Postcondition: $(D empty) 

548 


549 
Complexity: $(BIGOH n) 

550 
*/ 

551 
void clear() 

552 
{ 

553 
assert(0); 

554 
} 

555 


556 
/** 

557 
Sets the number of elements in the container to $(D newSize). If $(D 

558 
newSize) is greater than $(D length), the added elements are added to 

559 
unspecified positions in the container and initialized with $(D 

560 
.init). 

561 


562 
Complexity: $(BIGOH abs(n  newLength)) 

563 


564 
Postcondition: $(D _length == newLength) 

565 
*/ 

566 
@property void length(size_t newLength) 

567 
{ 

568 
assert(0); 

569 
} 

570 


571 
/** 

572 
Inserts $(D stuff) in an unspecified position in the 

573 
container. Implementations should choose whichever insertion means is 

574 
the most advantageous for the container, but document the exact 

575 
behavior. $(D stuff) can be a value convertible to the element type of 

576 
the container, or a range of values convertible to it. 

577 


578 
The $(D stable) version guarantees that ranges iterating over the 

579 
container are never invalidated. Client code that counts on 

580 
noninvalidating insertion should use $(D stableInsert). Such code would 

581 
not compile against containers that don't support it. 

582 


583 
Returns: The number of elements added. 

584 


585 
Complexity: $(BIGOH m * log(n)), where $(D m) is the number of 

586 
elements in $(D stuff) 

587 
*/ 

588 
size_t insert(Stuff)(Stuff stuff) 

589 
{ 

590 
assert(0); 

591 
} 

592 
///ditto 

593 
size_t stableInsert(Stuff)(Stuff stuff) 

594 
{ 

595 
assert(0); 

596 
} 

597 


598 
/** 

599 
Same as $(D insert(stuff)) and $(D stableInsert(stuff)) respectively, 

600 
but relax the complexity constraint to linear. 

601 
*/ 

602 
size_t linearInsert(Stuff)(Stuff stuff) 

603 
{ 

604 
assert(0); 

605 
} 

606 
///ditto 

607 
size_t stableLinearInsert(Stuff)(Stuff stuff) 

608 
{ 

609 
assert(0); 

610 
} 

611 


612 
/** 

613 
Picks one value in an unspecified position in the container, removes 

614 
it from the container, and returns it. Implementations should pick the 

615 
value that's the most advantageous for the container, but document the 

616 
exact behavior. The stable version behaves the same, but guarantees that 

617 
ranges iterating over the container are never invalidated. 

618 


619 
Precondition: $(D !empty) 

620 


621 
Returns: The element removed. 

622 


623 
Complexity: $(BIGOH log(n)). 

624 
*/ 

625 
T removeAny() 

626 
{ 

627 
assert(0); 

628 
} 

629 
/// ditto 

630 
T stableRemoveAny() 

631 
{ 

632 
assert(0); 

633 
} 

634 


635 
/** 

636 
Inserts $(D value) to the front or back of the container. $(D stuff) 

637 
can be a value convertible to the container's element type or a range 

638 
of values convertible to it. The stable version behaves the same, but 

639 
guarantees that ranges iterating over the container are never 

640 
invalidated. 

641 


642 
Returns: The number of elements inserted 

643 


644 
Complexity: $(BIGOH log(n)). 

645 
*/ 

646 
size_t insertFront(Stuff)(Stuff stuff) 

647 
{ 

648 
assert(0); 

649 
} 

650 
/// ditto 

651 
size_t stableInsertFront(Stuff)(Stuff stuff) 

652 
{ 

653 
assert(0); 

654 
} 

655 
/// ditto 

656 
size_t insertBack(Stuff)(Stuff stuff) 

657 
{ 

658 
assert(0); 

659 
} 

660 
/// ditto 

661 
size_t stableInsertBack(T value) 

662 
{ 

663 
assert(0); 

664 
} 

665 


666 
/** 

667 
Removes the value at the front or back of the container. The stable 

668 
version behaves the same, but guarantees that ranges iterating over 

669 
the container are never invalidated. The optional parameter $(D 

670 
howMany) instructs removal of that many elements. If $(D howMany > n), 

671 
all elements are removed and no exception is thrown. 

672 


673 
Precondition: $(D !empty) 

674 


675 
Complexity: $(BIGOH log(n)). 

676 
*/ 

677 
void removeFront() 

678 
{ 

679 
assert(0); 

680 
} 

681 
/// ditto 

682 
void stableRemoveFront() 

683 
{ 

684 
assert(0); 

685 
} 

686 
/// ditto 

687 
void removeBack() 

688 
{ 

689 
assert(0); 

690 
} 

691 
/// ditto 

692 
void stableRemoveBack() 

693 
{ 

694 
assert(0); 

695 
} 

696 


697 
/** 

698 
Removes $(D howMany) values at the front or back of the 

699 
container. Unlike the unparameterized versions above, these functions 

700 
do not throw if they could not remove $(D howMany) elements. Instead, 

701 
if $(D howMany > n), all elements are removed. The returned value is 

702 
the effective number of elements removed. The stable version behaves 

703 
the same, but guarantees that ranges iterating over the container are 

704 
never invalidated. 

705 


706 
Returns: The number of elements removed 

707 


708 
Complexity: $(BIGOH howMany * log(n)). 

709 
*/ 

710 
size_t removeFront(size_t howMany) 

711 
{ 

712 
assert(0); 

713 
} 

714 
/// ditto 

715 
size_t stableRemoveFront(size_t howMany) 

716 
{ 

717 
assert(0); 

718 
} 

719 
/// ditto 

720 
size_t removeBack(size_t howMany) 

721 
{ 

722 
assert(0); 

723 
} 

724 
/// ditto 

725 
size_t stableRemoveBack(size_t howMany) 

726 
{ 

727 
assert(0); 

728 
} 

729 


730 
/** 

731 
Removes all values corresponding to key $(D k). 

732 


733 
Complexity: $(BIGOH m * log(n)), where $(D m) is the number of 

734 
elements with the same key. 

735 


736 
Returns: The number of elements removed. 

737 
*/ 

738 
size_t removeKey(KeyType k) 

739 
{ 

740 
assert(0); 

741 
} 

742 


743 
/** 

744 
Inserts $(D stuff) before, after, or instead range $(D r), which must 

745 
be a valid range previously extracted from this container. $(D stuff) 

746 
can be a value convertible to the container's element type or a range 

747 
of objects convertible to it. The stable version behaves the same, but 

748 
guarantees that ranges iterating over the container are never 

749 
invalidated. 

750 


751 
Returns: The number of values inserted. 

752 


753 
Complexity: $(BIGOH n + m), where $(D m) is the length of $(D stuff) 

754 
*/ 

755 
size_t insertBefore(Stuff)(Range r, Stuff stuff) 

756 
{ 

757 
assert(0); 

758 
} 

759 
/// ditto 

760 
size_t stableInsertBefore(Stuff)(Range r, Stuff stuff) 

761 
{ 

762 
assert(0); 

763 
} 

764 
/// ditto 

765 
size_t insertAfter(Stuff)(Range r, Stuff stuff) 

766 
{ 

767 
assert(0); 

768 
} 

769 
/// ditto 

770 
size_t stableInsertAfter(Stuff)(Range r, Stuff stuff) 

771 
{ 

772 
assert(0); 

773 
} 

774 
/// ditto 

775 
size_t replace(Stuff)(Range r, Stuff stuff) 

776 
{ 

777 
assert(0); 

778 
} 

779 
/// ditto 

780 
size_t stableReplace(Stuff)(Range r, Stuff stuff) 

781 
{ 

782 
assert(0); 

783 
} 

784 


785 
/** 

786 
Removes all elements belonging to $(D r), which must be a range 

787 
obtained originally from this container. The stable version behaves the 

788 
same, but guarantees that ranges iterating over the container are 

789 
never invalidated. 

790 


791 
Returns: A range spanning the remaining elements in the container that 

792 
initially were right after $(D r). 

793 


794 
Complexity: $(BIGOH m * log(n)), where $(D m) is the number of 

795 
elements in $(D r) 

796 
*/ 

797 
Range remove(Range r) 

798 
{ 

799 
assert(0); 

800 
} 

801 
/// ditto 

802 
Range stableRemove(Range r) 

803 
{ 

804 
assert(0); 

805 
} 

806 


807 
/** 

808 
Same as $(D remove) above, but has complexity relaxed to linear. 

809 


810 
Returns: A range spanning the remaining elements in the container that 

811 
initially were right after $(D r). 

812 


813 
Complexity: $(BIGOH n) 

814 
*/ 

815 
Range linearRemove(Range r) 

816 
{ 

817 
assert(0); 

818 
} 

819 
/// ditto 

820 
Range stableLinearRemove(Range r) 

821 
{ 

822 
assert(0); 

823 
} 

824 
} 

825 


826 
unittest { 

827 
TotalContainer!int test; 

828 
} 

829 


830 
/** 

831 
Returns an initialized container. This function is mainly for 

832 
eliminating construction differences between $(D class) containers and 

833 
$(D struct) containers. 

834 
*/ 

835 
Container make(Container, T...)(T arguments) if (is(Container == struct)) 

836 
{ 

837 
static if (T.length == 0) 

838 
static assert(false, "You must pass at least one argument"); 

839 
else 

840 
return Container(arguments); 

841 
} 

842 


843 
/// ditto 

844 
Container make(Container, T...)(T arguments) if (is(Container == class)) 

845 
{ 

846 
return new Container(arguments); 

847 
} 

848 


849 
/** 

850 
Implements a simple and fast singlylinked list. 

851 
*/ 

852 
struct SList(T) 

853 
{ 

854 
private struct Node 

855 
{ 

856 
T _payload; 

857 
Node * _next; 

858 
this(T a, Node* b) { _payload = a; _next = b; } 

859 
} 

860 
private Node * _root; 

861 


862 
private static Node * findLastNode(Node * n) 

863 
{ 

864 
assert(n); 

865 
auto ahead = n._next; 

866 
while (ahead) 

867 
{ 

868 
n = ahead; 

869 
ahead = n._next; 

870 
} 

871 
return n; 

872 
} 

873 


874 
private static Node * findLastNode(Node * n, size_t limit) 

875 
{ 

876 
assert(n && limit); 

877 
auto ahead = n._next; 

878 
while (ahead) 

879 
{ 

880 
if (!limit) break; 

881 
n = ahead; 

882 
ahead = n._next; 

883 
} 

884 
return n; 

885 
} 

886 


887 
private static Node * findNode(Node * n, Node * findMe) 

888 
{ 

889 
assert(n); 

890 
auto ahead = n._next; 

891 
while (ahead != findMe) 

892 
{ 

893 
n = ahead; 

894 
enforce(n); 

895 
ahead = n._next; 

896 
} 

897 
return n; 

898 
} 

899 


900 
/** 

901 
Constructor taking a number of nodes 

902 
*/ 

903 
this(U)(U[] values...) if (isImplicitlyConvertible!(U, T)) 

904 
{ 

905 
insertFront(values); 

906 
} 

907 


908 
/** 

909 
Constructor taking an input range 

910 
*/ 

911 
this(Stuff)(Stuff stuff) 

912 
if (isInputRange!Stuff 

913 
&& isImplicitlyConvertible!(ElementType!Stuff, T) 

914 
&& !is(Stuff == T[])) 

915 
{ 

916 
insertFront(stuff); 

917 
} 

918 


919 
/** 

920 
Comparison for equality. 

921 


922 
Complexity: $(BIGOH min(n, n1)) where $(D n1) is the number of 

923 
elements in $(D rhs). 

924 
*/ 

925 
bool opEquals(ref const SList rhs) const 

926 
{ 

927 
const(Node) * n1 = _root, n2 = rhs._root; 

928 


929 
for (;; n1 = n1._next, n2 = n2._next) 

930 
{ 

931 
if (!n1) return !n2; 

932 
if (!n2  n1._payload != n2._payload) return false; 

933 
} 

934 
} 

935 


936 
/** 

937 
Defines the container's primary range, which embodies a forward range. 

938 
*/ 

939 
struct Range 

940 
{ 

941 
private Node * _head; 

942 
private this(Node * p) { _head = p; } 

943 
/// Forward range primitives. 

944 
bool empty() const { return !_head; } 

945 
/// ditto 

946 
@property Range save() { return this; } 

947 
/// ditto 

948 
@property T front() { return _head._payload; } 

949 
/// ditto 

950 
@property void front(T value) 

951 
{ 

952 
enforce(_head); 

953 
_head._payload = value; 

954 
} 

955 
/// ditto 

956 
void popFront() 

957 
{ 

958 
enforce(_head); 

959 
_head = _head._next; 

960 
} 

961 


962 
T moveFront() 

963 
{ 

964 
enforce(_head); 

965 
return move(_head._payload); 

966 
} 

967 


968 
bool sameHead(Range rhs) 

969 
{ 

970 
return _head && _head == rhs._head; 

971 
} 

972 
} 

973 


974 
unittest 

975 
{ 

976 
static assert(isForwardRange!Range); 

977 
} 

978 


979 
/** 

980 
Property returning $(D true) if and only if the container has no 

981 
elements. 

982 


983 
Complexity: $(BIGOH 1) 

984 
*/ 

985 
@property bool empty() const 

986 
{ 

987 
return _root is null; 

988 
} 

989 


990 
/** 

991 
Duplicates the container. The elements themselves are not transitively 

992 
duplicated. 

993 


994 
Complexity: $(BIGOH n). 

995 
*/ 

996 
@property SList dup() 

997 
{ 

998 
return SList(this[]); 

999 
} 

1000 


1001 
/** 

1002 
Returns a range that iterates over all elements of the container, in 

1003 
forward order. 

1004 


1005 
Complexity: $(BIGOH 1) 

1006 
*/ 

1007 
Range opSlice() 

1008 
{ 

1009 
return Range(_root); 

1010 
} 

1011 


1012 
/** 

1013 
Forward to $(D opSlice().front). 

1014 


1015 
Complexity: $(BIGOH 1) 

1016 
*/ 

1017 
@property T front() 

1018 
{ 

1019 
enforce(_root); 

1020 
return _root._payload; 

1021 
} 

1022 


1023 
/** 

1024 
Forward to $(D opSlice().front(value)). 

1025 


1026 
Complexity: $(BIGOH 1) 

1027 
*/ 

1028 
@property void front(T value) 

1029 
{ 

1030 
enforce(_root); 

1031 
_root._payload = value; 

1032 
} 

1033 


1034 
unittest 

1035 
{ 

1036 
auto s = SList!int(1, 2, 3); 

1037 
s.front = 42; 

1038 
assert(s == SList!int(42, 2, 3)); 

1039 
} 

1040 


1041 
/** 

1042 
Returns a new $(D SList) that's the concatenation of $(D this) and its 

1043 
argument. $(D opBinaryRight) is only defined if $(D Stuff) does not 

1044 
define $(D opBinary). 

1045 
*/ 

1046 
SList opBinary(string op, Stuff)(Stuff rhs) 

1047 
if (op == "~" && is(typeof(SList(rhs)))) 

1048 
{ 

1049 
auto toAdd = SList(rhs); 

1050 
static if (is(Stuff == SList)) 

1051 
{ 

1052 
toAdd = toAdd.dup; 

1053 
} 

1054 
if (empty) return toAdd; 

1055 
// TODO: optimize 

1056 
auto result = dup; 

1057 
auto n = findLastNode(result._root); 

1058 
n._next = toAdd._root; 

1059 
return result; 

1060 
} 

1061 


1062 
/** 

1063 
Removes all contents from the $(D SList). 

1064 


1065 
Postcondition: $(D empty) 

1066 


1067 
Complexity: $(BIGOH 1) 

1068 
*/ 

1069 
void clear() 

1070 
{ 

1071 
_root = null; 

1072 
} 

1073 


1074 
/** 

1075 
Inserts $(D stuff) to the front of the container. $(D stuff) can be a 

1076 
value convertible to $(D T) or a range of objects convertible to $(D 

1077 
T). The stable version behaves the same, but guarantees that ranges 

1078 
iterating over the container are never invalidated. 

1079 


1080 
Returns: The number of elements inserted 

1081 


1082 
Complexity: $(BIGOH log(n)) 

1083 
*/ 

1084 
size_t insertFront(Stuff)(Stuff stuff) 

1085 
if (isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, T)) 

1086 
{ 

1087 
size_t result; 

1088 
Node * n, newRoot; 

1089 
foreach (item; stuff) 

1090 
{ 

1091 
auto newNode = new Node(item, null); 

1092 
(newRoot ? n._next : newRoot) = newNode; 

1093 
n = newNode; 

1094 
++result; 

1095 
} 

1096 
if (!n) return 0; 

1097 
// Last node points to the old root 

1098 
n._next = _root; 

1099 
_root = newRoot; 

1100 
return result; 

1101 
} 

1102 


1103 
/// ditto 

1104 
size_t insertFront(Stuff)(Stuff stuff) 

1105 
if (isImplicitlyConvertible!(Stuff, T)) 

1106 
{ 

1107 
auto newRoot = new Node(stuff, _root); 

1108 
_root = newRoot; 

1109 
return 1; 

1110 
} 

1111 


1112 
/// ditto 

1113 
alias insertFront insert; 

1114 


1115 
/// ditto 

1116 
alias insert stableInsert; 

1117 


1118 
/// ditto 

1119 
alias insertFront stableInsertFront; 

1120 


1121 
/** 

1122 
Picks one value from the front of the container, removes it from the 

1123 
container, and returns it. 

1124 


1125 
Precondition: $(D !empty) 

1126 


1127 
Returns: The element removed. 

1128 


1129 
Complexity: $(BIGOH 1). 

1130 
*/ 

1131 
T removeAny() 

1132 
{ 

1133 
enforce(!empty); 

1134 
auto result = move(_root._payload); 

1135 
_root = _root._next; 

1136 
return result; 

1137 
} 

1138 
/// ditto 

1139 
alias removeAny stableRemoveAny; 

1140 


1141 
/** 

1142 
Removes the value at the front of the container. The stable version 

1143 
behaves the same, but guarantees that ranges iterating over the 

1144 
container are never invalidated. 

1145 


1146 
Precondition: $(D !empty) 

1147 


1148 
Complexity: $(BIGOH 1). 

1149 
*/ 

1150 
void removeFront() 

1151 
{ 

1152 
enforce(_root); 

1153 
_root = _root._next; 

1154 
} 

1155 


1156 
/// ditto 

1157 
alias removeFront stableRemoveFront; 

1158 


1159 
/** 

1160 
Removes $(D howMany) values at the front or back of the 

1161 
container. Unlike the unparameterized versions above, these functions 

1162 
do not throw if they could not remove $(D howMany) elements. Instead, 

1163 
if $(D howMany > n), all elements are removed. The returned value is 

1164 
the effective number of elements removed. The stable version behaves 

1165 
the same, but guarantees that ranges iterating over the container are 

1166 
never invalidated. 

1167 


1168 
Returns: The number of elements removed 

1169 


1170 
Complexity: $(BIGOH howMany * log(n)). 

1171 
*/ 

1172 
size_t removeFront(size_t howMany) 

1173 
{ 

1174 
size_t result; 

1175 
while (_root && result < howMany) 

1176 
{ 

1177 
_root = _root._next; 

1178 
++result; 

1179 
} 

1180 
return result; 

1181 
} 

1182 


1183 
/// ditto 

1184 
alias removeFront stableRemoveFront; 

1185 


1186 
/** 

1187 
Inserts $(D stuff) after range $(D r), which must be a range 

1188 
previously extracted from this container. Given that all ranges for a 

1189 
list end at the end of the list, this function essentially appends to 

1190 
the list and uses $(D r) as a potentially fast way to reach the last 

1191 
node in the list. (Ideally $(D r) is positioned near or at the last 

1192 
element of the list.) 

1193 


1194 
$(D stuff) can be a value convertible to $(D T) or a range of objects 

1195 
convertible to $(D T). The stable version behaves the same, but 

1196 
guarantees that ranges iterating over the container are never 

1197 
invalidated. 

1198 


1199 
Returns: The number of values inserted. 

1200 


1201 
Complexity: $(BIGOH k + m), where $(D k) is the number of elements in 

1202 
$(D r) and $(D m) is the length of $(D stuff). 

1203 
*/ 

1204 


1205 
size_t insertAfter(Stuff)(Range r, Stuff stuff) 

1206 
{ 

1207 
if (!_root) 

1208 
{ 

1209 
enforce(!r._head); 

1210 
return insertFront(stuff); 

1211 
} 

1212 
enforce(r._head); 

1213 
auto n = findLastNode(r._head); 

1214 
SList tmp; 

1215 
auto result = tmp.insertFront(stuff); 

1216 
n._next = tmp._root; 

1217 
return result; 

1218 
} 

1219 


1220 
/** 

1221 
Similar to $(D insertAfter) above, but accepts a range bounded in 

1222 
count. This is important for ensuring fast insertions in the middle of 

1223 
the list. For fast insertions after a specified position $(D r), use 

1224 
$(D insertAfter(take(r, 1), stuff)). The complexity of that operation 

1225 
only depends on the number of elements in $(D stuff). 

1226 


1227 
Precondition: $(D r.original.empty  r.maxLength > 0) 

1228 


1229 
Returns: The number of values inserted. 

1230 


1231 
Complexity: $(BIGOH k + m), where $(D k) is the number of elements in 

1232 
$(D r) and $(D m) is the length of $(D stuff). 

1233 
*/ 

1234 
size_t insertAfter(Stuff)(Take!Range r, Stuff stuff) 

1235 
{ 

1236 
auto orig = r.original; 

1237 
if (!orig._head) 

1238 
{ 

1239 
// Inserting after a null range counts as insertion to the 

1240 
// front 

1241 
return insertFront(stuff); 

1242 
} 

1243 
enforce(!r.empty); 

1244 
// Find the last valid element in the range 

1245 
foreach (i; 1 .. r.maxLength) 

1246 
{ 

1247 
if (!orig._head._next) break; 

1248 
orig.popFront(); 

1249 
} 

1250 
// insert here 

1251 
SList tmp; 

1252 
tmp._root = orig._head._next; 

1253 
auto result = tmp.insertFront(stuff); 

1254 
orig._head._next = tmp._root; 

1255 
return result; 

1256 
} 

1257 


1258 
/// ditto 

1259 
alias insertAfter stableInsertAfter; 

1260 


1261 
/** 

1262 
Removes a range from the list in linear time. 

1263 


1264 
Returns: An empty range. 

1265 


1266 
Complexity: $(BIGOH n) 

1267 
*/ 

1268 
Range linearRemove(Range r) 

1269 
{ 

1270 
if (!_root) 

1271 
{ 

1272 
enforce(!r._head); 

1273 
return this[]; 

1274 
} 

1275 
auto n = findNode(_root, r._head); 

1276 
n._next = null; 

1277 
return Range(null); 

1278 
} 

1279 


1280 
/** 

1281 
Removes a $(D Take!Range) from the list in linear time. 

1282 


1283 
Returns: A range comprehending the elements after the removed range. 

1284 


1285 
Complexity: $(BIGOH n) 

1286 
*/ 

1287 
Range linearRemove(Take!Range r) 

1288 
{ 

1289 
auto orig = r.original; 

1290 
// We have something to remove here 

1291 
if (orig._head == _root) 

1292 
{ 

1293 
// remove straight from the head of the list 

1294 
for (; !orig.empty; orig.popFront()) 

1295 
{ 

1296 
removeFront(); 

1297 
} 

1298 
return this[]; 

1299 
} 

1300 
if (!r.maxLength) 

1301 
{ 

1302 
// Nothing to remove, return the range itself 

1303 
return orig; 

1304 
} 

1305 
// Remove from somewhere in the middle of the list 

1306 
enforce(_root); 

1307 
auto n1 = findNode(_root, orig._head); 

1308 
auto n2 = findLastNode(orig._head, r.maxLength); 

1309 
n1._next = n2._next; 

1310 
return Range(n1._next); 

1311 
} 

1312 


1313 
/// ditto 

1314 
alias linearRemove stableLinearRemove; 

1315 
} 

1316 


1317 
unittest 

1318 
{ 

1319 
auto s = make!(SList!int)(1, 2, 3); 

1320 
auto n = s.findLastNode(s._root); 

1321 
assert(n && n._payload == 3); 

1322 
} 

1323 


1324 
unittest 

1325 
{ 

1326 
auto s = SList!int(1, 2, 5, 10); 

1327 
assert(walkLength(s[]) == 4); 

1328 
} 

1329 


1330 
unittest 

1331 
{ 

1332 
auto src = take([0, 1, 2, 3], 3); 

1333 
auto s = SList!int(src); 

1334 
assert(s == SList!int(0, 1, 2)); 

1335 
} 

1336 


1337 
unittest 

1338 
{ 

1339 
auto a = SList!int(1, 2, 3); 

1340 
auto b = SList!int(4, 5, 6); 

1341 
// @@@BUG@@@ in compiler 

1342 
//auto c = a ~ b; 

1343 
auto d = [ 4, 5, 6 ]; 

1344 
auto e = a ~ d; 

1345 
assert(e == SList!int(1, 2, 3, 4, 5, 6)); 

1346 
} 

1347 


1348 
unittest 

1349 
{ 

1350 
auto a = SList!int(1, 2, 3); 

1351 
auto c = a ~ 4; 

1352 
assert(c == SList!int(1, 2, 3, 4)); 

1353 
} 

1354 


1355 
unittest 

1356 
{ 

1357 
auto s = SList!int(1, 2, 3, 4); 

1358 
s.insertFront([ 42, 43 ]); 

1359 
assert(s == SList!int(42, 43, 1, 2, 3, 4)); 

1360 
} 

1361 


1362 
unittest 

1363 
{ 

1364 
auto s = SList!int(1, 2, 3); 

1365 
assert(s.removeAny() == 1); 

1366 
assert(s == SList!int(2, 3)); 

1367 
assert(s.stableRemoveAny() == 2); 

1368 
assert(s == SList!int(3)); 

1369 
} 

1370 


1371 
unittest 

1372 
{ 

1373 
auto s = SList!int(1, 2, 3); 

1374 
s.removeFront(); 

1375 
assert(equal(s[], [2, 3])); 

1376 
s.stableRemoveFront(); 

1377 
assert(equal(s[], [3])); 

1378 
} 

1379 


1380 
unittest 

1381 
{ 

1382 
auto s = SList!int(1, 2, 3, 4, 5, 6, 7); 

1383 
assert(s.removeFront(3) == 3); 

1384 
assert(s == SList!int(4, 5, 6, 7)); 

1385 
} 

1386 


1387 
unittest 

1388 
{ 

1389 
auto a = SList!int(1, 2, 3); 

1390 
auto b = SList!int(1, 2, 3); 

1391 
assert(a.insertAfter(a[], b[]) == 3); 

1392 
} 

1393 


1394 
unittest 

1395 
{ 

1396 
auto s = SList!int(1, 2, 3, 4); 

1397 
auto r = take(s[], 2); 

1398 
assert(s.insertAfter(r, 5) == 1); 

1399 
assert(s == SList!int(1, 2, 5, 3, 4)); 

1400 
} 

1401 


1402 
unittest 

1403 
{ 

1404 
auto s = SList!int(1, 2, 3, 4, 5); 

1405 
auto r = s[]; 

1406 
popFrontN(r, 3); 

1407 
auto r1 = s.linearRemove(r); 

1408 
assert(s == SList!int(1, 2, 3)); 

1409 
assert(r1.empty); 

1410 
} 

1411 


1412 
unittest 

1413 
{ 

1414 
auto s = SList!int(1, 2, 3, 4, 5, 6, 7, 8, 9, 10); 

1415 
auto r = s[]; 

1416 
popFrontN(r, 3); 

1417 
auto r1 = take(r, 4); 

1418 
assert(equal(r1, [4, 5, 6, 7])); 

1419 
auto r2 = s.linearRemove(r1); 

1420 
assert(s == SList!int(1, 2, 3, 8, 9, 10)); 

1421 
assert(equal(r2, [8, 9, 10])); 

1422 
} 

1423 


1424 


1425 
unittest 

1426 
{ 

1427 
auto lst = SList!int(1, 5, 42, 9); 

1428 
assert(!lst.empty); 

1429 
assert(lst.front == 1); 

1430 
assert(walkLength(lst[]) == 4); 

1431 


1432 
auto lst2 = lst ~ [ 1, 2, 3 ]; 

1433 
assert(walkLength(lst2[]) == 7); 

1434 


1435 
auto lst3 = lst ~ [ 7 ]; 

1436 
assert(walkLength(lst3[]) == 5); 

1437 
} 

1438 


1439 
unittest 

1440 
{ 

1441 
auto s = make!(SList!int)(1, 2, 3); 

1442 
} 

1443 


1444 
/** 

1445 
Array type with deterministic control of memory. The memory allocated 

1446 
for the array is reclaimed as soon as possible; there is no reliance 

1447 
on the garbage collector. $(D Array) uses $(D malloc) and $(D free) 

1448 
for managing its own memory. 

1449 
*/ 

1450 
struct Array(T) if (!is(T : const(bool))) 

1451 
{ 

1452 
// This structure is not copyable. 

1453 
private struct Payload 

1454 
{ 

1455 
size_t _capacity; 

1456 
T[] _payload; 

1457 


1458 
// Convenience constructor 

1459 
this(T[] p) { _capacity = p.length; _payload = p; } 

1460 


1461 
// Destructor releases array memory 

1462 
~this() 

1463 
{ 

1464 
foreach (ref e; _payload) .clear(e); 

1465 
static if (hasIndirections!T) 

1466 
GC.removeRange(_payload.ptr); 

1467 
free(_payload.ptr); 

1468 
} 

1469 


1470 
this(this) 

1471 
{ 

1472 
assert(0); 

1473 
} 

1474 


1475 
void opAssign(Array!(T).Payload rhs) 

1476 
{ 

1477 
assert(false); 

1478 
} 

1479 


1480 
// Duplicate data 

1481 
// @property Payload dup() 

1482 
// { 

1483 
// Payload result; 

1484 
// result._payload = _payload.dup; 

1485 
// // Conservatively assume initial capacity == length 

1486 
// result._capacity = result._payload.length; 

1487 
// return result; 

1488 
// } 

1489 


1490 
// length 

1491 
@property size_t length() const 

1492 
{ 

1493 
return _payload.length; 

1494 
} 

1495 


1496 
// length 

1497 
@property void length(size_t newLength) 

1498 
{ 

1499 
if (length >= newLength) 

1500 
{ 

1501 
// shorten 

1502 
static if (is(T == struct) && hasElaborateDestructor!T) 

1503 
{ 

1504 
foreach (ref e; _payload.ptr[newLength .. _payload.length]) 

1505 
{ 

1506 
clear(e); 

1507 
} 

1508 
} 

1509 
_payload = _payload.ptr[0 .. newLength]; 

1510 
return; 

1511 
} 

1512 
// enlarge 

1513 
auto startEmplace = length; 

1514 
_payload = (cast(T*) realloc(_payload.ptr, 

1515 
T.sizeof * newLength))[0 .. newLength]; 

1516 
initializeAll(_payload.ptr[startEmplace .. length]); 

1517 
} 

1518 


1519 
// capacity 

1520 
@property size_t capacity() const 

1521 
{ 

1522 
return _capacity; 

1523 
} 

1524 


1525 
// reserve 

1526 
void reserve(size_t elements) 

1527 
{ 

1528 
if (elements <= capacity) return; 

1529 
immutable sz = elements * T.sizeof; 

1530 
static if (hasIndirections!T) // should use hasPointers instead 

1531 
{ 

1532 
/* Because of the transactional nature of this 

1533 
* relative to the garbage collector, ensure no 

1534 
* threading bugs by using malloc/copy/free rather 

1535 
* than realloc. 

1536 
*/ 

1537 
immutable oldLength = length; 

1538 
auto newPayload = 

1539 
enforce((cast(T*) malloc(sz))[0 .. oldLength]); 

1540 
// copy old data over to new array 

1541 
newPayload[] = _payload[]; 

1542 
// Zero out unused capacity to prevent gc from seeing 

1543 
// false pointers 

1544 
memset(newPayload.ptr + oldLength, 

1545 
0, 

1546 
(elements  oldLength) * T.sizeof); 

1547 
GC.addRange(newPayload.ptr, sz); 

1548 
GC.removeRange(_data._payload.ptr); 

1549 
free(_data._payload.ptr); 

1550 
_data._payload = newPayload; 

1551 
} 

1552 
else 

1553 
{ 

1554 
/* These can't have pointers, so no need to zero 

1555 
* unused region 

1556 
*/ 

1557 
auto newPayload = 

1558 
enforce(cast(T*) realloc(_payload.ptr, sz))[0 .. length]; 

1559 
_payload = newPayload; 

1560 
} 

1561 
_capacity = elements; 

1562 
} 

1563 


1564 
// Insert one item 

1565 
size_t insertBack(Stuff)(Stuff stuff) 

1566 
if (isImplicitlyConvertible!(Stuff, T)) 

1567 
{ 

1568 
if (_capacity == length) 

1569 
{ 

1570 
reserve(1 + capacity * 3 / 2); 

1571 
} 

1572 
assert(capacity > length && _payload.ptr); 

1573 
emplace!T((cast(void*) (_payload.ptr + _payload.length)) 

1574 
[0 .. T.sizeof], 

1575 
stuff); 

1576 
_payload = _payload.ptr[0 .. _payload.length + 1]; 

1577 
return 1; 

1578 
} 

1579 


1580 
/// Insert a range of items 

1581 
size_t insertBack(Stuff)(Stuff stuff) 

1582 
if (isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, T)) 

1583 
{ 

1584 
static if (hasLength!Stuff) 

1585 
{ 

1586 
immutable oldLength = length; 

1587 
reserve(oldLength + stuff.length); 

1588 
} 

1589 
size_t result; 

1590 
foreach (item; stuff) 

1591 
{ 

1592 
insertBack(item); 

1593 
++result; 

1594 
} 

1595 
static if (hasLength!Stuff) 

1596 
{ 

1597 
assert(length == oldLength + stuff.length); 

1598 
} 

1599 
return result; 

1600 
} 

1601 
} 

1602 
private alias RefCounted!(Payload, RefCountedAutoInitialize.no) Data; 

1603 
private Data _data; 

1604 


1605 
this(U)(U[] values...) if (isImplicitlyConvertible!(U, T)) 

1606 
{ 

1607 
auto p = malloc(T.sizeof * values.length); 

1608 
if (hasIndirections!T && p) 

1609 
{ 

1610 
GC.addRange(p, T.sizeof * values.length); 

1611 
} 

1612 
foreach (i, e; values) 

1613 
{ 

1614 
emplace!T(p[i * T.sizeof .. (i + 1) * T.sizeof], e); 

1615 
assert((cast(T*) p)[i] == e); 

1616 
} 

1617 
_data.RefCounted.initialize((cast(T*) p)[0 .. values.length]); 

1618 
} 

1619 


1620 
/** 

1621 
Comparison for equality. 

1622 
*/ 

1623 
bool opEquals(ref const Array rhs) const 

1624 
{ 

1625 
if (empty) return rhs.empty; 

1626 
if (rhs.empty) return false; 

1627 
return _data._payload == rhs._data._payload; 

1628 
} 

1629 


1630 
/** 

1631 
Defines the container's primary range, which is a randomaccess range. 

1632 
*/ 

1633 
struct Range 

1634 
{ 

1635 
private Array _outer; 

1636 
private size_t _a, _b; 

1637 


1638 
this(Array data, size_t a, size_t b) 

1639 
{ 

1640 
_outer = data; 

1641 
_a = a; 

1642 
_b = b; 

1643 
} 

1644 


1645 
@property bool empty() const 

1646 
{ 

1647 
assert(_outer.length >= _b); 

1648 
return _a >= _b; 

1649 
} 

1650 


1651 
@property Range save() 

1652 
{ 

1653 
return this; 

1654 
} 

1655 


1656 
@property T front() 

1657 
{ 

1658 
enforce(!empty); 

1659 
return _outer[_a]; 

1660 
} 

1661 


1662 
@property void front(T value) 

1663 
{ 

1664 
enforce(!empty); 

1665 
_outer[_a] = move(value); 

1666 
} 

1667 


1668 
void popFront() 

1669 
{ 

1670 
enforce(!empty); 

1671 
++_a; 

1672 
} 

1673 


1674 
T moveFront() 

1675 
{ 

1676 
enforce(!empty); 

1677 
return move(_outer._data._payload[_a]); 

1678 
} 

1679 


1680 
T moveBack() 

1681 
{ 

1682 
enforce(!empty); 

1683 
return move(_outer._data._payload[_b  1]); 

1684 
} 

1685 


1686 
T moveAt(size_t i) 

1687 
{ 

1688 
i += _a; 

1689 
enforce(i < _b && !empty); 

1690 
return move(_outer._data._payload[_a + i]); 

1691 
} 

1692 


1693 
T opIndex(size_t i) 

1694 
{ 

1695 
i += _a; 

1696 
enforce(i < _b && _b <= _outer.length); 

1697 
return _outer[i]; 

1698 
} 

1699 


1700 
void opIndexAssign(T value, size_t i) 

1701 
{ 

1702 
i += _a; 

1703 
enforce(i < _b && _b <= _outer.length); 

1704 
_outer[i] = value; 

1705 
} 

1706 


1707 
void opIndexOpAssign(string op)(T value, size_t i) 

1708 
{ 

1709 
enforce(_outer && _a + i < _b && _b <= _outer._payload.length); 

1710 
mixin("_outer._payload.ptr[_a + i] "~op~"= value;"); 

1711 
} 

1712 
} 

1713 


1714 
/** 

1715 
Property returning $(D true) if and only if the container has no 

1716 
elements. 

1717 


1718 
Complexity: $(BIGOH 1) 

1719 
*/ 

1720 
@property bool empty() const 

1721 
{ 

1722 
return !_data.RefCounted.isInitialized  _data._payload.empty; 

1723 
} 

1724 


1725 
/** 

1726 
Duplicates the container. The elements themselves are not transitively 

1727 
duplicated. 

1728 


1729 
Complexity: $(BIGOH n). 

1730 
*/ 

1731 
@property Array dup() 

1732 
{ 

1733 
if (!_data.RefCounted.isInitialized) return this; 

1734 
return Array(_data._payload); 

1735 
} 

1736 


1737 
/** 

1738 
Returns the number of elements in the container. 

1739 


1740 
Complexity: $(BIGOH 1). 

1741 
*/ 

1742 
@property size_t length() const 

1743 
{ 

1744 
return _data.RefCounted.isInitialized ? _data._payload.length : 0; 

1745 
} 

1746 


1747 
/** 

1748 
Returns the maximum number of elements the container can store without 

1749 
(a) allocating memory, (b) invalidating iterators upon insertion. 

1750 


1751 
Complexity: $(BIGOH 1) 

1752 
*/ 

1753 
@property size_t capacity() 

1754 
{ 

1755 
return _data.RefCounted.isInitialized ? _data._capacity : 0; 

1756 
} 

1757 


1758 
/** 

1759 
Ensures sufficient capacity to accommodate $(D e) elements. 

1760 


1761 
Postcondition: $(D capacity >= e) 

1762 


1763 
Complexity: $(BIGOH 1) 

1764 
*/ 

1765 
void reserve(size_t elements) 

1766 
{ 

1767 
if (!_data.RefCounted.isInitialized) 

1768 
{ 

1769 
if (!elements) return; 

1770 
immutable sz = elements * T.sizeof; 

1771 
auto p = enforce(malloc(sz)); 

1772 
static if (hasIndirections!T) 

1773 
{ 

1774 
GC.addRange(p, sz); 

1775 
} 

1776 
_data.RefCounted.initialize(cast(T[]) p[0 .. 0]); 

1777 
_data._capacity = elements; 

1778 
} 

1779 
else 

1780 
{ 

1781 
_data.reserve(elements); 

1782 
} 

1783 
} 

1784 


1785 
/** 

1786 
Returns a range that iterates over elements of the container, in 

1787 
forward order. 

1788 


1789 
Complexity: $(BIGOH 1) 

1790 
*/ 

1791 
Range opSlice() 

1792 
{ 

1793 
// Workaround for bug 4356 

1794 
Array copy; 

1795 
copy._data = this._data; 

1796 
return Range(copy, 0, length); 

1797 
} 

1798 


1799 
/** 

1800 
Returns a range that iterates over elements of the container from 

1801 
index $(D a) up to (excluding) index $(D b). 

1802 


1803 
Precondition: $(D a <= b && b <= length) 

1804 


1805 
Complexity: $(BIGOH 1) 

1806 
*/ 

1807 
Range opSlice(size_t a, size_t b) 

1808 
{ 

1809 
enforce(a <= b && b <= length); 

1810 
// Workaround for bug 4356 

1811 
Array copy; 

1812 
copy._data = this._data; 

1813 
return Range(copy, a, b); 

1814 
} 

1815 


1816 
/** 

1817 
@@@BUG@@@ This doesn't work yet 

1818 
*/ 

1819 
size_t opDollar() const 

1820 
{ 

1821 
return length; 

1822 
} 

1823 


1824 
/** 

1825 
Forward to $(D opSlice().front) and $(D opSlice().back), respectively. 

1826 


1827 
Precondition: $(D !empty) 

1828 


1829 
Complexity: $(BIGOH 1) 

1830 
*/ 

1831 
@property T front() 

1832 
{ 

1833 
enforce(!empty); 

1834 
return *_data._payload.ptr; 

1835 
} 

1836 


1837 
/// ditto 

1838 
@property void front(T value) 

1839 
{ 

1840 
enforce(!empty); 

1841 
*_data._payload.ptr = value; 

1842 
} 

1843 


1844 
/// ditto 

1845 
@property T back() 

1846 
{ 

1847 
enforce(!empty); 

1848 
return _data._payload[$  1]; 

1849 
} 

1850 


1851 
/// ditto 

1852 
@property void back(T value) 

1853 
{ 

1854 
enforce(!empty); 

1855 
_data._payload[$  1] = value; 

1856 
} 

1857 


1858 
/** 

1859 
Indexing operators yield or modify the value at a specified index. 

1860 


1861 
Precondition: $(D i < length) 

1862 


1863 
Complexity: $(BIGOH 1) 

1864 
*/ 

1865 
T opIndex(size_t i) 

1866 
{ 

1867 
enforce(_data.RefCounted.isInitialized); 

1868 
return _data._payload[i]; 

1869 
} 

1870 


1871 
/// ditto 

1872 
void opIndexAssign(T value, size_t i) 

1873 
{ 

1874 
enforce(_data.RefCounted.isInitialized); 

1875 
_data._payload[i] = value; 

1876 
} 

1877 


1878 
/// ditto 

1879 
void opIndexOpAssign(string op)(T value, size_t i) 

1880 
{ 

1881 
mixin("_data._payload[i] "~op~"= value;"); 

1882 
} 

1883 


1884 
/** 

1885 
Returns a new container that's the concatenation of $(D this) and its 

1886 
argument. $(D opBinaryRight) is only defined if $(D Stuff) does not 

1887 
define $(D opBinary). 

1888 


1889 
Complexity: $(BIGOH n + m), where m is the number of elements in $(D 

1890 
stuff) 

1891 
*/ 

1892 
Array opBinary(string op, Stuff)(Stuff stuff) if (op == "~") 

1893 
{ 

1894 
// TODO: optimize 

1895 
Array result; 

1896 
// @@@BUG@@ result ~= this[] doesn't work 

1897 
auto r = this[]; 

1898 
result ~= r; 

1899 
assert(result.length == length); 

1900 
result ~= stuff[]; 

1901 
return result; 

1902 
} 

1903 


1904 
/** 

1905 
Forwards to $(D insertBack(stuff)). 

1906 
*/ 

1907 
void opOpAssign(string op, Stuff)(Stuff stuff) if (op == "~") 

1908 
{ 

1909 
static if (is(typeof(stuff[]))) 

1910 
{ 

1911 
insertBack(stuff[]); 

1912 
} 

1913 
else 

1914 
{ 

1915 
insertBack(stuff); 

1916 
} 

1917 
} 

1918 


1919 
/** 

1920 
Removes all contents from the container. The container decides how $(D 

1921 
capacity) is affected. 

1922 


1923 
Postcondition: $(D empty) 

1924 


1925 
Complexity: $(BIGOH n) 

1926 
*/ 

1927 
void clear() 

1928 
{ 

1929 
.clear(_data); 

1930 
} 

1931 


1932 
/** 

1933 
Sets the number of elements in the container to $(D newSize). If $(D 

1934 
newSize) is greater than $(D length), the added elements are added to 

1935 
unspecified positions in the container and initialized with $(D 

1936 
T.init). 

1937 


1938 
Complexity: $(BIGOH abs(n  newLength)) 

1939 


1940 
Postcondition: $(D length == newLength) 

1941 
*/ 

1942 
@property void length(size_t newLength) 

1943 
{ 

1944 
_data.RefCounted.ensureInitialized(); 

1945 
_data.length = newLength; 

1946 
} 

1947 


1948 
/** 

1949 
Picks one value in an unspecified position in the container, removes 

1950 
it from the container, and returns it. Implementations should pick the 

1951 
value that's the most advantageous for the container, but document the 

1952 
exact behavior. The stable version behaves the same, but guarantees 

1953 
that ranges iterating over the container are never invalidated. 

1954 


1955 
Precondition: $(D !empty) 

1956 


1957 
Returns: The element removed. 

1958 


1959 
Complexity: $(BIGOH log(n)). 

1960 
*/ 

1961 
T removeAny() 

1962 
{ 

1963 
auto result = back; 

1964 
removeBack(); 

1965 
return result; 

1966 
} 

1967 
/// ditto 

1968 
alias removeAny stableRemoveAny; 

1969 


1970 
/** 

1971 
Inserts $(D value) to the front or back of the container. $(D stuff) 

1972 
can be a value convertible to $(D T) or a range of objects convertible 

1973 
to $(D T). The stable version behaves the same, but guarantees that 

1974 
ranges iterating over the container are never invalidated. 

1975 


1976 
Returns: The number of elements inserted 

1977 


1978 
Complexity: $(BIGOH m * log(n)), where $(D m) is the number of 

1979 
elements in $(D stuff) 

1980 
*/ 

1981 
size_t insertBack(Stuff)(Stuff stuff) 

1982 
if (isImplicitlyConvertible!(Stuff, T)  

1983 
isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, T)) 

1984 
{ 

1985 
_data.RefCounted.ensureInitialized(); 

1986 
return _data.insertBack(stuff); 

1987 
} 

1988 
/// ditto 

1989 
alias insertBack insert; 

1990 


1991 
/** 

1992 
Removes the value at the back of the container. The stable version 

1993 
behaves the same, but guarantees that ranges iterating over the 

1994 
container are never invalidated. 

1995 


1996 
Precondition: $(D !empty) 

1997 


1998 
Complexity: $(BIGOH log(n)). 

1999 
*/ 

2000 
void removeBack() 

2001 
{ 

2002 
enforce(!empty); 

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

2004 
{ 

2005 
// Destroy this guy 

2006 
.clear(_data._payload[$  1]); 

2007 
} 

2008 
_data._payload = _data._payload[0 .. $  1]; 

2009 
} 

2010 
/// ditto 

2011 
alias removeBack stableRemoveBack; 

2012 


2013 
/** 

2014 
Removes $(D howMany) values at the front or back of the 

2015 
container. Unlike the unparameterized versions above, these functions 

2016 
do not throw if they could not remove $(D howMany) elements. Instead, 

2017 
if $(D howMany > n), all elements are removed. The returned value is 

2018 
the effective number of elements removed. The stable version behaves 

2019 
the same, but guarantees that ranges iterating over the container are 

2020 
never invalidated. 

2021 


2022 
Returns: The number of elements removed 

2023 


2024 
Complexity: $(BIGOH howMany). 

2025 
*/ 

2026 
size_t removeBack(size_t howMany) 

2027 
{ 

2028 
if (howMany > length) howMany = length; 

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

2030 
{ 

2031 
// Destroy this guy 

2032 
foreach (ref e; _data._payload[$  howMany .. $]) 

2033 
{ 

2034 
.clear(e); 

2035 
} 

2036 
} 

2037 
_data._payload = _data._payload[0 .. $  howMany]; 

2038 
return howMany; 

2039 
} 

2040 
/// ditto 

2041 
alias removeBack stableRemoveBack; 

2042 


2043 
/** 

2044 
Inserts $(D stuff) before, after, or instead range $(D r), which must 

2045 
be a valid range previously extracted from this container. $(D stuff) 

2046 
can be a value convertible to $(D T) or a range of objects convertible 

2047 
to $(D T). The stable version behaves the same, but guarantees that 

2048 
ranges iterating over the container are never invalidated. 

2049 


2050 
Returns: The number of values inserted. 

2051 


2052 
Complexity: $(BIGOH n + m), where $(D m) is the length of $(D stuff) 

2053 
*/ 

2054 
size_t insertBefore(Stuff)(Range r, Stuff stuff) 

2055 
if (isImplicitlyConvertible!(Stuff, T)) 

2056 
{ 

2057 
enforce(r._outer._data == _data && r._a < length); 

2058 
reserve(length + 1); 

2059 
assert(_data.RefCounted.isInitialized); 

2060 
// Move elements over by one slot 

2061 
memmove(_data._payload.ptr + r._a + 1, 

2062 
_data._payload.ptr + r._a, 

2063 
T.sizeof * (length  r._a)); 

2064 
emplace!T((cast(void*) (_data._payload.ptr + r._a))[0 .. T.sizeof], 

2065 
stuff); 

2066 
_data._payload = _data._payload.ptr[0 .. _data._payload.length + 1]; 

2067 
return 1; 

2068 
} 

2069 


2070 
/// ditto 

2071 
size_t insertBefore(Stuff)(Range r, Stuff stuff) 

2072 
if (isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, T)) 

2073 
{ 

2074 
enforce(r._outer._data == _data && r._a <= length); 

2075 
static if (isForwardRange!Stuff) 

2076 
{ 

2077 
// Can find the length in advance 

2078 
auto extra = walkLength(stuff); 

2079 
if (!extra) return 0; 

2080 
reserve(length + extra); 

2081 
assert(_data.RefCounted.isInitialized); 

2082 
// Move elements over by extra slots 

2083 
memmove(_data._payload.ptr + r._a + extra, 

2084 
_data._payload.ptr + r._a, 

2085 
T.sizeof * (length  r._a)); 

2086 
foreach (p; _data._payload.ptr + r._a .. 

2087 
_data._payload.ptr + r._a + extra) 

2088 
{ 

2089 
emplace!T((cast(void*) p)[0 .. T.sizeof], stuff.front); 

2090 
stuff.popFront(); 

2091 
} 

2092 
_data._payload = 

2093 
_data._payload.ptr[0 .. _data._payload.length + extra]; 

2094 
return extra; 

2095 
} 

2096 
else 

2097 
{ 

2098 
enforce(_data); 

2099 
immutable offset = r._a; 

2100 
enforce(offset <= length); 

2101 
auto result = insertBack(stuff); 

2102 
bringToFront(this[offset .. length  result], 

2103 
this[length  result .. length]); 

2104 
return result; 

2105 
} 

2106 
} 

2107 


2108 
/// ditto 

2109 
size_t insertAfter(Stuff)(Range r, Stuff stuff) 

2110 
{ 

2111 
// TODO: optimize 

2112 
enforce(_data); 

2113 
immutable offset = r.ptr + r.length  _data._payload.ptr; 

2114 
enforce(offset <= length); 

2115 
auto result = insertBack(stuff); 

2116 
bringToFront(this[offset .. length  result], 

2117 
this[length  result .. length]); 

2118 
return result; 

2119 
} 

2120 


2121 
/// ditto 

2122 
size_t replace(Stuff)(Range r, Stuff stuff) 

2123 
if (isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, T)) 

2124 
{ 

2125 
enforce(_data); 

2126 
immutable offset = r.ptr  _data._payload.ptr; 

2127 
enforce(offset <= length); 

2128 
size_t result; 

2129 
for (; !stuff.empty; stuff.popFront()) 

2130 
{ 

2131 
if (r.empty) 

2132 
{ 

2133 
// append the rest 

2134 
return result + insertBack(stuff); 

2135 
} 

2136 
r.front = stuff.front; 

2137 
r.popFront(); 

2138 
++result; 

2139 
} 

2140 
// Remove remaining stuff in r 

2141 
remove(r); 

2142 
return result; 

2143 
} 

2144 


2145 
/// ditto 

2146 
size_t replace(Stuff)(Range r, Stuff stuff) 

2147 
if (isImplicitlyConvertible!(Stuff, T)) 

2148 
{ 

2149 
if (r.empty) 

2150 
{ 

2151 
insertBefore(r, stuff); 

2152 
} 

2153 
else 

2154 
{ 

2155 
r.front = stuff; 

2156 
r.popFront(); 

2157 
remove(r); 

2158 
} 

2159 
return 1; 

2160 
} 

2161 


2162 
/** 

2163 
Removes all elements belonging to $(D r), which must be a range 

2164 
obtained originally from this container. The stable version behaves 

2165 
the same, but guarantees that ranges iterating over the container are 

2166 
never invalidated. 

2167 


2168 
Returns: A range spanning the remaining elements in the container that 

2169 
initially were right after $(D r). 

2170 


2171 
Complexity: $(BIGOH n  m), where $(D m) is the number of elements in 

2172 
$(D r) 

2173 
*/ 

2174 
Range linearRemove(Range r) 

2175 
{ 

2176 
enforce(_data.RefCounted.isInitialized); 

2177 
enforce(r._a <= r._b && r._b <= length); 

2178 
immutable offset1 = r._a; 

2179 
immutable offset2 = r._b; 

2180 
immutable tailLength = length  offset2; 

2181 
// Use copy here, not a[] = b[] because the ranges may overlap 

2182 
copy(this[offset2 .. length], this[offset1 .. offset1 + tailLength]); 

2183 
length = offset1 + tailLength; 

2184 
return this[length  tailLength .. length]; 

2185 
} 

2186 


2187 
/// ditto 

2188 
alias remove stableLinearRemove; 

2189 


2190 
} 

2191 


2192 
// unittest 

2193 
// { 

2194 
// Array!int a; 

2195 
// assert(a.empty); 

2196 
// } 

2197 


2198 
unittest 

2199 
{ 

2200 
Array!int a = Array!int(1, 2, 3); 

2201 
//a._data._refCountedDebug = true; 

2202 
auto b = a.dup; 

2203 
assert(b == Array!int(1, 2, 3)); 

2204 
b.front = 42; 

2205 
assert(b == Array!int(42, 2, 3)); 

2206 
assert(a == Array!int(1, 2, 3)); 

2207 
} 

2208 


2209 
unittest 

2210 
{ 

2211 
auto a = Array!int(1, 2, 3); 

2212 
assert(a.length == 3); 

2213 
} 

2214 


2215 
unittest 

2216 
{ 

2217 
Array!int a; 

2218 
a.reserve(1000); 

2219 
assert(a.length == 0); 

2220 
assert(a.empty); 

2221 
assert(a.capacity >= 1000); 

2222 
auto p = a._data._payload.ptr; 

2223 
foreach (i; 0 .. 1000) 

2224 
{ 

2225 
a.insertBack(i); 

2226 
} 

2227 
assert(p == a._data._payload.ptr); 

2228 
} 

2229 


2230 
unittest 

2231 
{ 

2232 
auto a = Array!int(1, 2, 3); 

2233 
a[1] *= 42; 

2234 
assert(a[1] == 84); 

2235 
} 

2236 


2237 
unittest 

2238 
{ 

2239 
auto a = Array!int(1, 2, 3); 

2240 
auto b = Array!int(11, 12, 13); 

2241 
auto c = a ~ b; 

2242 
//foreach (e; c) writeln(e); 

2243 
assert(c == Array!int(1, 2, 3, 11, 12, 13)); 

2244 
//assert(a ~ b[] == Array!int(1, 2, 3, 11, 12, 13)); 

2245 
} 

2246 


2247 
unittest 

2248 
{ 

2249 
auto a = Array!int(1, 2, 3); 

2250 
auto b = Array!int(11, 12, 13); 

2251 
a ~= b; 

2252 
assert(a == Array!int(1, 2, 3, 11, 12, 13)); 

2253 
} 

2254 


2255 
unittest 

2256 
{ 

2257 
auto a = Array!int(1, 2, 3, 4); 

2258 
assert(a.removeAny() == 4); 

2259 
assert(a == Array!int(1, 2, 3)); 

2260 
} 

2261 


2262 
unittest 

2263 
{ 

2264 
auto a = Array!int(1, 2, 3, 4, 5); 

2265 
auto r = a[2 .. a.length]; 

2266 
assert(a.insertBefore(r, 42) == 1); 

2267 
assert(a == Array!int(1, 2, 42, 3, 4, 5)); 

2268 
r = a[2 .. 2]; 

2269 
assert(a.insertBefore(r, [8, 9]) == 2); 

2270 
assert(a == Array!int(1, 2, 8, 9, 42, 3, 4, 5)); 

2271 
} 

2272 


2273 
unittest 

2274 
{ 

2275 
auto a = Array!int(0, 1, 2, 3, 4, 5, 6, 7, 8); 

2276 
a.linearRemove(a[4 .. 6]); 

2277 
auto b = Array!int(0, 1, 2, 3, 6, 7, 8); 

2278 
//writeln(a.length); 

2279 
//foreach (e; a) writeln(e); 

2280 
assert(a == Array!int(0, 1, 2, 3, 6, 7, 8)); 

2281 
} 

2282 


2283 
// BinaryHeap 

2284 
/** 

2285 
Implements a $(WEB en.wikipedia.org/wiki/Binary_heap, binary heap) 

2286 
container on top of a given randomaccess range type (usually $(D 

2287 
T[])) or a randomaccess container type (usually $(D Array!T)). The 

2288 
documentation of $(D BinaryHeap) will refer to the underlying range or 

2289 
container as the $(I store) of the heap. 

2290 


2291 
The binary heap induces structure over the underlying store such that 

2292 
accessing the largest element (by using the $(D front) property) is a 

2293 
$(BIGOH 1) operation and extracting it (by using the $(D 

2294 
removeFront()) method) is done fast in $(BIGOH log n) time. 

2295 


2296 
If $(D less) is the lessthan operator, which is the default option, 

2297 
then $(D BinaryHeap) defines a socalled maxheap that optimizes 

2298 
extraction of the $(I largest) elements. To define a minheap, 

2299 
instantiate BinaryHeap with $(D "a > b") as its predicate. 

2300 


2301 
Simply extracting elements from a $(D BinaryHeap) container is 

2302 
tantamount to lazily fetching elements of $(D Store) in descending 

2303 
order. Extracting elements from the $(D BinaryHeap) to completion 

2304 
leaves the underlying store sorted in ascending order but, again, 

2305 
yields elements in descending order. 

2306 


2307 
If $(D Store) is a range, the $(D BinaryHeap) cannot grow beyond the 

2308 
size of that range. If $(D Store) is a container that supports $(D 

2309 
insertBack), the $(D BinaryHeap) may grow by adding elements to the 

2310 
container. 

2311 


2312 
Example: 

2313 
 

2314 
// Example from "Introduction to Algorithms" Cormen et al, p 146 

2315 
int[] a = [ 4, 1, 3, 2, 16, 9, 10, 14, 8, 7 ]; 

2316 
auto h = heapify(a); 

2317 
// largest element 

2318 
assert(h.front == 16); 

2319 
// a has the heap property 

2320 
assert(equal(a, [ 16, 14, 10, 9, 8, 7, 4, 3, 2, 1 ])); 

2321 
 

2322 
*/ 

2323 
struct BinaryHeap(Store, alias less = "a < b") 

2324 
if (isRandomAccessRange!(Store)  isRandomAccessRange!(typeof(Store.init[]))) 

2325 
{ 

2326 
// Really weird @@BUG@@: if you comment out the "private:" label below, 

2327 
// std.algorithm can't unittest anymore 

2328 
//private: 

2329 


2330 
// The payload includes the support store and the effective length 

2331 
private RefCounted!(Tuple!(Store, "_store", size_t, "_length"), 

2332 
RefCountedAutoInitialize.no) _payload; 

2333 
// Comparison predicate 

2334 
private alias binaryFun!(less) comp; 

2335 
// Convenience accessors 

2336 
private @property ref Store _store() 

2337 
{ 

2338 
assert(_payload.RefCounted.isInitialized); 

2339 
return _payload._store; 

2340 
} 

2341 
private @property ref size_t _length() 

2342 
{ 

2343 
assert(_payload.RefCounted.isInitialized); 

2344 
return _payload._length; 

2345 
} 

2346 


2347 
// Asserts that the heap property is respected. 

2348 
private void assertValid() 

2349 
{ 

2350 
debug 

2351 
{ 

2352 
if (!_payload.RefCounted.isInitialized) return; 

2353 
if (_length < 2) return; 

2354 
for (size_t n = _length  1; n >= 1; n) 

2355 
{ 

2356 
auto parentIdx = (n  1) / 2; 

2357 
assert(!comp(_store[parentIdx], _store[n]), text(n)); 

2358 
} 

2359 
} 

2360 
} 

2361 


2362 
// Assuming the element at index i perturbs the heap property in 

2363 
// store r, percolates it down the heap such that the heap 

2364 
// property is restored. 

2365 
private void percolateDown(Store r, size_t i, size_t length) 

2366 
{ 

2367 
for (;;) 

2368 
{ 

2369 
auto left = i * 2 + 1, right = left + 1; 

2370 
if (right == length) 

2371 
{ 

2372 
if (comp(r[i], r[left])) swap(r, i, left); 

2373 
return; 

2374 
} 

2375 
if (right > length) return; 

2376 
assert(left < length && right < length); 

2377 
auto largest = comp(r[i], r[left]) 

2378 
? (comp(r[left], r[right]) ? right : left) 

2379 
: (comp(r[i], r[right]) ? right : i); 

2380 
if (largest == i) return; 

2381 
swap(r, i, largest); 

2382 
i = largest; 

2383 
} 

2384 
} 

2385 


2386 
// @@@BUG@@@: add private here, std.algorithm doesn't unittest anymore 

2387 
/*private*/ void pop(Store store) 

2388 
{ 

2389 
assert(!store.empty); 

2390 
if (store.length == 1) return; 

2391 
auto t1 = moveFront(store[]); 

2392 
auto t2 = moveBack(store[]); 

2393 
store.front = move(t2); 

2394 
store.back = move(t1); 

2395 
percolateDown(store, 0, store.length  1); 

2396 
} 

2397 


2398 
/*private*/ static void swap(Store _store, size_t i, size_t j) 

2399 
{ 

2400 
static if (is(typeof(swap(_store[i], _store[j])))) 

2401 
{ 

2402 
swap(_store[i], _store[j]); 

2403 
} 

2404 
else static if (is(typeof(_store.moveAt(i)))) 

2405 
{ 

2406 
auto t1 = _store.moveAt(i); 

2407 
auto t2 = _store.moveAt(j); 

2408 
_store[i] = move(t2); 

2409 
_store[j] = move(t1); 

2410 
} 

2411 
else // assume it's a container and access its range with [] 

2412 
{ 

2413 
auto t1 = _store[].moveAt(i); 

2414 
auto t2 = _store[].moveAt(j); 

2415 
_store[i] = move(t2); 

2416 
_store[j] = move(t1); 

2417 
} 

2418 
} 

2419 


2420 
public: 

2421 


2422 
/** 

2423 
Converts the store $(D s) into a heap. If $(D initialSize) is 

2424 
specified, only the first $(D initialSize) elements in $(D s) 

2425 
are transformed into a heap, after which the heap can grow up 

2426 
to $(D r.length) (if $(D Store) is a range) or indefinitely (if 

2427 
$(D Store) is a container with $(D insertBack)). Performs 

2428 
$(BIGOH min(r.length, initialSize)) evaluations of $(D less). 

2429 
*/ 

2430 
this(Store s, size_t initialSize = size_t.max) 

2431 
{ 

2432 
acquire(s, initialSize); 

2433 
} 

2434 


2435 
/** 

2436 
Takes ownership of a store. After this, manipulating $(D s) may make 

2437 
the heap work incorrectly. 

2438 
*/ 

2439 
void acquire(Store s, size_t initialSize = size_t.max) 

2440 
{ 

2441 
_payload.RefCounted.ensureInitialized(); 

2442 
_store() = move(s); 

2443 
_length() = min(_store.length, initialSize); 

2444 
if (_length < 2) return; 

2445 
for (auto i = (_length  2) / 2; ; ) 

2446 
{ 

2447 
this.percolateDown(_store, i, _length); 

2448 
if (i == 0) break; 

2449 
} 

2450 
assertValid; 

2451 
} 

2452 


2453 
/** 

2454 
Takes ownership of a store assuming it already was organized as a 

2455 
heap. 

2456 
*/ 

2457 
void assume(Store s, size_t initialSize = size_t.max) 

2458 
{ 

2459 
_payload.RefCounted.ensureInitialized(); 

2460 
_store() = s; 

2461 
_length() = min(_store.length, initialSize); 

2462 
assertValid; 

2463 
} 

2464 


2465 
/** 

2466 
Clears the heap. Returns the portion of the store from $(D 0) up to 

2467 
$(D length), which satisfies the $(LUCKY heap property). 

2468 
*/ 

2469 
auto release() 

2470 
{ 

2471 
if (!_payload.RefCounted.isInitialized) 

2472 
{ 

2473 
return typeof(_store[0 .. _length]).init; 

2474 
} 

2475 
assertValid(); 

2476 
auto result = _store[0 .. _length]; 

2477 
_payload = _payload.init; 

2478 
return result; 

2479 
} 

2480 


2481 
/** 

2482 
Returns $(D true) if the heap is _empty, $(D false) otherwise. 

2483 
*/ 

2484 
@property bool empty() 

2485 
{ 

2486 
return !length; 

2487 
} 

2488 


2489 
/** 

2490 
Returns a duplicate of the heap. The underlying store must also 

2491 
support a $(D dup) method. 

2492 
*/ 

2493 
@property BinaryHeap dup() 

2494 
{ 

2495 
BinaryHeap result; 

2496 
if (!_payload.RefCounted.isInitialized) return result; 

2497 
result.assume(_store.dup, length); 

2498 
return result; 

2499 
} 

2500 


2501 
/** 

2502 
Returns the _length of the heap. 

2503 
*/ 

2504 
@property size_t length() 

2505 
{ 

2506 
return _payload.RefCounted.isInitialized ? _length : 0; 

2507 
} 

2508 


2509 
/** 

2510 
Returns the _capacity of the heap, which is the length of the 

2511 
underlying store (if the store is a range) or the _capacity of the 

2512 
underlying store (if the store is a container). 

2513 
*/ 

2514 
@property size_t capacity() 

2515 
{ 

2516 
if (!_payload.RefCounted.isInitialized) return 0; 

2517 
static if (is(typeof(_store.capacity) : size_t)) 

2518 
{ 

2519 
return _store.capacity; 

2520 
} 

2521 
else 

2522 
{ 

2523 
return _store.length; 

2524 
} 

2525 
} 

2526 


2527 
/** 

2528 
Returns a copy of the _front of the heap, which is the largest element 

2529 
according to $(D less). 

2530 
*/ 

2531 
@property ElementType!Store front() 

2532 
{ 

2533 
enforce(!empty); 

2534 
return _store.front; 

2535 
} 

2536 


2537 
/** 

2538 
Clears the heap by detaching it from the underlying store. 

2539 
*/ 

2540 
void clear() 

2541 
{ 

2542 
_payload = _payload.init; 

2543 
} 

2544 


2545 
/** 

2546 
Inserts $(D value) into the store. If the underlying store is a range 

2547 
and $(D length == capacity), throws an exception. 

2548 
*/ 

2549 
size_t insert(ElementType!Store value) 

2550 
{ 

2551 
static if (is(typeof(_store.insertBack(value)))) 

2552 
{ 

2553 
_payload.RefCounted.ensureInitialized(); 

2554 
if (length == _store.length) 

2555 
{ 

2556 
// reallocate 

2557 
_store.insertBack(value); 

2558 
} 

2559 
else 

2560 
{ 

2561 
// no reallocation 

2562 
_store[_length] = value; 

2563 
} 

2564 
} 

2565 
else 

2566 
{ 

2567 
// can't grow 

2568 
enforce(length < _store.length, 

2569 
"Cannot grow a heap created over a range"); 

2570 
_store[_length] = value; 

2571 
} 

2572 


2573 
// sink down the element 

2574 
for (size_t n = _length; n; ) 

2575 
{ 

2576 
auto parentIdx = (n  1) / 2; 

2577 
if (!comp(_store[parentIdx], _store[n])) break; // done! 

2578 
// must swap and continue 

2579 
swap(_store, parentIdx, n); 

2580 
n = parentIdx; 

2581 
} 

2582 
++_length; 

2583 
assertValid(); 

2584 
return 1; 

2585 
} 

2586 


2587 
/** 

2588 
Removes the largest element from the heap. 

2589 
*/ 

2590 
void removeFront() 

2591 
{ 

2592 
enforce(!empty); 

2593 
if (_length > 1) 

2594 
{ 

2595 
auto t1 = moveFront(_store[]); 

2596 
auto t2 = moveAt(_store[], _length  1); 

2597 
_store.front = move(t2); 

2598 
_store[_length  1] = move(t1); 

2599 
} 

2600 
_length; 

2601 
percolateDown(_store, 0, _length); 

2602 
} 

2603 


2604 
/** 

2605 
Removes the largest element from the heap and returns a copy of 

2606 
it. The element still resides in the heap's store. For performance 

2607 
reasons you may want to use $(D removeFront) with heaps of objects 

2608 
that are expensive to copy. 

2609 
*/ 

2610 
ElementType!Store removeAny() 

2611 
{ 

2612 
removeFront(); 

2613 
return _store[_length]; 

2614 
} 

2615 


2616 
/** 

2617 
Replaces the largest element in the store with $(D value). 

2618 
*/ 

2619 
void replaceFront(ElementType!Store value) 

2620 
{ 

2621 
// must replace the top 

2622 
assert(!empty); 

2623 
_store.front = value; 

2624 
percolateDown(_store, 0, _length); 

2625 
assertValid; 

2626 
} 

2627 


2628 
/** 

2629 
If the heap has room to grow, inserts $(D value) into the store and 

2630 
returns $(D true). Otherwise, if $(D less(value, front)), calls $(D 

2631 
replaceFront(value)) and returns again $(D true). Otherwise, leaves 

2632 
the heap unaffected and returns $(D false). This method is useful in 

2633 
scenarios where the smallest $(D k) elements of a set of candidates 

2634 
must be collected. 

2635 
*/ 

2636 
bool conditionalInsert(ElementType!Store value) 

2637 
{ 

2638 
_payload.RefCounted.ensureInitialized(); 

2639 
if (_length < _store.length) 

2640 
{ 

2641 
insert(value); 

2642 
return true; 

2643 
} 

2644 
// must replace the top 

2645 
assert(!_store.empty); 

2646 
if (!comp(value, _store.front)) return false; // value >= largest 

2647 
_store.front = value; 

2648 
percolateDown(_store, 0, _length); 

2649 
assertValid; 

2650 
return true; 

2651 
} 

2652 
} 

2653 


2654 
/** 

2655 
Convenience function that returns a $(D BinaryHeap!Store) object 

2656 
initialized with $(D s) and $(D initialSize). 

2657 
*/ 

2658 
BinaryHeap!Store heapify(Store)(Store s, size_t initialSize = size_t.max) 

2659 
{ 

2660 
return BinaryHeap!Store(s, initialSize); 

2661 
} 

2662 


2663 
unittest 

2664 
{ 

2665 
{ 

2666 
// example from "Introduction to Algorithms" Cormen et al., p 146 

2667 
int[] a = [ 4, 1, 3, 2, 16, 9, 10, 14, 8, 7 ]; 

2668 
auto h = heapify(a); 

2669 
assert(h.front == 16); 

2670 
assert(a == [ 16, 14, 10, 8, 7, 9, 3, 2, 4, 1 ]); 

2671 
auto witness = [ 16, 14, 10, 9, 8, 7, 4, 3, 2, 1 ]; 

2672 
for (; !h.empty; h.removeFront(), witness.popFront()) 

2673 
{ 

2674 
assert(!witness.empty); 

2675 
assert(witness.front == h.front); 

2676 
} 

2677 
assert(witness.empty); 

2678 
} 

2679 
{ 

2680 
int[] a = [ 4, 1, 3, 2, 16, 9, 10, 14, 8, 7 ]; 

2681 
int[] b = new int[a.length]; 

2682 
BinaryHeap!(int[]) h = BinaryHeap!(int[])(b, 0); 

2683 
foreach (e; a) 

2684 
{ 

2685 
h.insert(e); 

2686 
} 

2687 
assert(b == [ 16, 14, 10, 8, 7, 3, 9, 1, 4, 2 ], text(b)); 

2688 
} 

2689 
} 

2690 


2691 
//////////////////////////////////////////////////////////////////////////////// 

2692 
// Array!bool 

2693 
//////////////////////////////////////////////////////////////////////////////// 

2694 


2695 
/** 

2696 
_Array specialized for $(D bool). Packs together values efficiently by 

2697 
allocating one bit per element. 

2698 
*/ 

2699 
struct Array(T) if (is(T == bool)) 

2700 
{ 

2701 
static immutable uint bitsPerWord = size_t.sizeof * 8; 

2702 
private alias Tuple!(Array!(size_t).Payload, "_backend", ulong, "_length") 

2703 
Data; 

2704 
private RefCounted!(Data, RefCountedAutoInitialize.no) _store; 

2705 


2706 
private ref size_t[] data() 

2707 
{ 

2708 
assert(_store.RefCounted.isInitialized); 

2709 
return _store._backend._payload; 

2710 
} 

2711 


2712 
private ref size_t dataCapacity() 

2713 
{ 

2714 
return _store._backend._capacity; 

2715 
} 

2716 


2717 
/** 

2718 
Defines the container's primary range. 

2719 
*/ 

2720 
struct Range 

2721 
{ 

2722 
private Array!bool _outer; 

2723 
private ulong _a, _b; 

2724 
/// Range primitives 

2725 
@property Range save() 

2726 
{ 

2727 
version (bug4437) 

2728 
{ 

2729 
return this; 

2730 
} 

2731 
else 

2732 
{ 

2733 
auto copy = this; 

2734 
return copy; 

2735 
} 

2736 
} 

2737 
/// Ditto 

2738 
@property bool empty() 

2739 
{ 

2740 
return _a >= _b  _outer.length < _b; 

2741 
} 

2742 
/// Ditto 

2743 
@property T front() 

2744 
{ 

2745 
enforce(!empty); 

2746 
return _outer[_a]; 

2747 
} 

2748 
/// Ditto 

2749 
@property void front(bool value) 

2750 
{ 

2751 
enforce(!empty); 

2752 
_outer[_a] = value; 

2753 
} 

2754 
/// Ditto 

2755 
T moveFront() 

2756 
{ 

2757 
enforce(!empty); 

2758 
return _outer.moveAt(_a); 

2759 
} 

2760 
/// Ditto 

2761 
void popFront() 

2762 
{ 

2763 
enforce(!empty); 

2764 
++_a; 

2765 
} 

2766 
/// Ditto 

2767 
@property T back() 

2768 
{ 

2769 
enforce(!empty); 

2770 
return _outer[_b  1]; 

2771 
} 

2772 
/// Ditto 

2773 
T moveBack() 

2774 
{ 

2775 
enforce(!empty); 

2776 
return _outer.moveAt(_b  1); 

2777 
} 

2778 
/// Ditto 

2779 
void popBack() 

2780 
{ 

2781 
enforce(!empty); 

2782 
_b; 

2783 
} 

2784 
/// Ditto 

2785 
T opIndex(size_t i) 

2786 
{ 

2787 
return _outer[_a + i]; 

2788 
} 

2789 
/// Ditto 

2790 
void opIndexAssign(T value, size_t i) 

2791 
{ 

2792 
_outer[_a + i] = value; 

2793 
} 

2794 
/// Ditto 

2795 
T moveAt(size_t i) 

2796 
{ 

2797 
return _outer.moveAt(_a + i); 

2798 
} 

2799 
/// Ditto 

2800 
@property ulong length() const 

2801 
{ 

2802 
assert(_a <= _b); 

2803 
return _b  _a; 

2804 
} 

2805 
} 

2806 


2807 
/** 

2808 
Property returning $(D true) if and only if the container has 

2809 
no elements. 

2810 


2811 
Complexity: $(BIGOH 1) 

2812 
*/ 

2813 
@property bool empty() 

2814 
{ 

2815 
return !length; 

2816 
} 

2817 


2818 
unittest 

2819 
{ 

2820 
Array!bool a; 

2821 
//a._store._refCountedDebug = true; 

2822 
assert(a.empty); 

2823 
a.insertBack(false); 

2824 
assert(!a.empty); 

2825 
} 

2826 


2827 
/** 

2828 
Returns a duplicate of the container. The elements themselves 

2829 
are not transitively duplicated. 

2830 


2831 
Complexity: $(BIGOH n). 

2832 
*/ 

2833 
@property Array!bool dup() 

2834 
{ 

2835 
Array!bool result; 

2836 
result.insertBack(this[]); 

2837 
return result; 

2838 
} 

2839 


2840 
unittest 

2841 
{ 

2842 
Array!bool a; 

2843 
assert(a.empty); 

2844 
auto b = a.dup; 

2845 
assert(b.empty); 

2846 
a.insertBack(true); 

2847 
assert(b.empty); 

2848 
} 

2849 


2850 
/** 

2851 
Returns the number of elements in the container. 

2852 


2853 
Complexity: $(BIGOH log(n)). 

2854 
*/ 

2855 
@property ulong length() 

2856 
{ 

2857 
return _store.RefCounted.isInitialized ? _store._length : 0; 

2858 
} 

2859 


2860 
unittest 

2861 
{ 

2862 
Array!bool a; 

2863 
assert(a.length == 0); 

2864 
a.insert(true); 

2865 
assert(a.length == 1, text(a.length)); 

2866 
} 

2867 


2868 
/** 

2869 
Returns the maximum number of elements the container can store 

2870 
without (a) allocating memory, (b) invalidating iterators upon 

2871 
insertion. 

2872 


2873 
Complexity: $(BIGOH log(n)). 

2874 
*/ 

2875 
@property ulong capacity() 

2876 
{ 

2877 
return _store.RefCounted.isInitialized 

2878 
? cast(ulong) bitsPerWord * _store._backend.capacity 

2879 
: 0; 

2880 
} 

2881 


2882 
unittest 

2883 
{ 

2884 
Array!bool a; 

2885 
assert(a.capacity == 0); 

2886 
foreach (i; 0 .. 100) 

2887 
{ 

2888 
a.insert(true); 

2889 
assert(a.capacity >= a.length, text(a.capacity)); 

2890 
} 

2891 
} 

2892 


2893 
/** 

2894 
Ensures sufficient capacity to accommodate $(D n) elements. 

2895 


2896 
Postcondition: $(D capacity >= n) 

2897 


2898 
Complexity: $(BIGOH log(e  capacity)) if $(D e > capacity), 

2899 
otherwise $(BIGOH 1). 

2900 
*/ 

2901 
void reserve(ulong e) 

2902 
{ 

2903 
_store.RefCounted.ensureInitialized(); 

2904 
_store._backend.reserve(to!size_t((e + bitsPerWord  1) / bitsPerWord)); 

2905 
} 

2906 


2907 
unittest 

2908 
{ 

2909 
Array!bool a; 

2910 
assert(a.capacity == 0); 

2911 
a.reserve(15657); 

2912 
assert(a.capacity >= 15657); 

2913 
} 

2914 


2915 
/** 

2916 
Returns a range that iterates over all elements of the 

2917 
container, in a containerdefined order. The container should 

2918 
choose the most convenient and fast method of iteration for $(D 

2919 
opSlice()). 

2920 


2921 
Complexity: $(BIGOH log(n)) 

2922 
*/ 

2923 
Range opSlice() 

2924 
{ 

2925 
return Range(this, 0, length); 

2926 
} 

2927 


2928 
unittest 

2929 
{ 

2930 
Array!bool a; 

2931 
a.insertBack([true, false, true, true]); 

2932 
assert(a[].length == 4); 

2933 
} 

2934 


2935 
/** 

2936 
Returns a range that iterates the container between two 

2937 
specified positions. 

2938 


2939 
Complexity: $(BIGOH log(n)) 

2940 
*/ 

2941 
Range opSlice(ulong a, ulong b) 

2942 
{ 

2943 
enforce(a <= b && b <= length); 

2944 
return Range(this, a, b); 

2945 
} 

2946 


2947 
unittest 

2948 
{ 

2949 
Array!bool a; 

2950 
a.insertBack([true, false, true, true]); 

2951 
assert(a[0 .. 2].length == 2); 

2952 
} 

2953 


2954 
/** 

2955 
Equivalent to $(D opSlice().front) and $(D opSlice().back), 

2956 
respectively. 

2957 


2958 
Complexity: $(BIGOH log(n)) 

2959 
*/ 

2960 
@property bool front() 

2961 
{ 

2962 
enforce(!empty); 

2963 
return data.ptr[0] & 1; 

2964 
} 

2965 


2966 
/// Ditto 

2967 
@property void front(bool value) 

2968 
{ 

2969 
enforce(!empty); 

2970 
if (value) data.ptr[0] = 1; 

2971 
else data.ptr[0] &= ~cast(size_t) 1; 

2972 
} 

2973 


2974 
unittest 

2975 
{ 

2976 
Array!bool a; 

2977 
a.insertBack([true, false, true, true]); 

2978 
assert(a.front); 

2979 
a.front = false; 

2980 
assert(!a.front); 

2981 
} 

2982 


2983 
/// Ditto 

2984 
@property bool back() 

2985 
{ 

2986 
enforce(!empty); 

2987 
return data.back & (1u << ((_store._length  1) % bitsPerWord)); 

2988 
} 

2989 


2990 
/// Ditto 

2991 
@property void back(bool value) 

2992 
{ 

2993 
enforce(!empty); 

2994 
if (value) 

2995 
{ 

2996 
data.back = (1u << ((_store._length  1) % bitsPerWord)); 

2997 
} 

2998 
else 

2999 
{ 

3000 
data.back &= 

3001 
~(cast(size_t)1 << ((_store._length  1) % bitsPerWord)); 

3002 
} 

3003 
} 

3004 


3005 
unittest 

3006 
{ 

3007 
Array!bool a; 

3008 
a.insertBack([true, false, true, true]); 

3009 
assert(a.back); 

3010 
a.back = false; 

3011 
assert(!a.back); 

3012 
} 

3013 


3014 
/** 

3015 
Indexing operators yield or modify the value at a specified index. 

3016 
*/ 

3017 
bool opIndex(ulong i) 

3018 
{ 

3019 
auto div = cast(size_t) (i / bitsPerWord); 

3020 
auto rem = i % bitsPerWord; 

3021 
enforce(div < data.length); 

3022 
return data.ptr[div] & (1u << rem); 

3023 
} 

3024 
/// ditto 

3025 
void opIndexAssign(bool value, ulong i) 

3026 
{ 

3027 
auto div = cast(size_t) (i / bitsPerWord); 

3028 
auto rem = i % bitsPerWord; 

3029 
enforce(div < data.length); 

3030 
if (value) data.ptr[div] = (1u << rem); 

3031 
else data.ptr[div] &= ~(cast(size_t)1 << rem); 

3032 
} 

3033 
/// ditto 

3034 
void opIndexOpAssign(string op)(bool value, ulong i) 

3035 
{ 

3036 
auto div = cast(size_t) (i / bitsPerWord); 

3037 
auto rem = i % bitsPerWord; 

3038 
enforce(div < data.length); 

3039 
auto oldValue = cast(bool) (data.ptr[div] & (1u << rem)); 

3040 
// Do the deed 

3041 
auto newValue = mixin("oldValue "~op~" value"); 

3042 
// Write back the value 

3043 
if (newValue != oldValue) 

3044 
{ 

3045 
if (newValue) data.ptr[div] = (1u << rem); 

3046 
else data.ptr[div] &= ~(cast(size_t)1 << rem); 

3047 
} 

3048 
} 

3049 
/// Ditto 

3050 
T moveAt(ulong i) 

3051 
{ 

3052 
return this[i]; 

3053 
} 

3054 


3055 
unittest 

3056 
{ 

3057 
Array!bool a; 

3058 
a.insertBack([true, false, true, true]); 

3059 
assert(a[0] && !a[1]); 

3060 
a[0] &= a[1]; 

3061 
assert(!a[0]); 

3062 
} 

3063 


3064 
/** 

3065 
Returns a new container that's the concatenation of $(D this) 

3066 
and its argument. 

3067 


3068 
Complexity: $(BIGOH n + m), where m is the number of elements 

3069 
in $(D stuff) 

3070 
*/ 

3071 
Array!bool opBinary(string op, Stuff)(Stuff rhs) if (op == "~") 

3072 
{ 

3073 
auto result = this; 

3074 
return result ~= rhs; 

3075 
} 

3076 


3077 
unittest 

3078 
{ 

3079 
Array!bool a; 

3080 
a.insertBack([true, false, true, true]); 

3081 
Array!bool b; 

3082 
b.insertBack([true, true, false, true]); 

3083 
assert(equal((a ~ b)[], 

3084 
[true, false, true, true, true, true, false, true])); 

3085 
} 

3086 


3087 
// /// ditto 

3088 
// TotalContainer opBinaryRight(Stuff, string op)(Stuff lhs) if (op == "~") 

3089 
// { 

3090 
// assert(0); 

3091 
// } 

3092 


3093 
/** 

3094 
Forwards to $(D insertAfter(this[], stuff)). 

3095 
*/ 

3096 
// @@@BUG@@@ 

3097 
//ref Array!bool opOpAssign(string op, Stuff)(Stuff stuff) if (op == "~") 

3098 
Array!bool opOpAssign(string op, Stuff)(Stuff stuff) if (op == "~") 

3099 
{ 

3100 
static if (is(typeof(stuff[]))) insertBack(stuff[]); 

3101 
else insertBack(stuff); 

3102 
return this; 

3103 
} 

3104 


3105 
unittest 

3106 
{ 

3107 
Array!bool a; 

3108 
a.insertBack([true, false, true, true]); 

3109 
Array!bool b; 

3110 
a.insertBack([false, true, false, true, true]); 

3111 
a ~= b; 

3112 
assert(equal( 

3113 
a[], 

3114 
[true, false, true, true, false, true, false, true, true])); 

3115 
} 

3116 


3117 
/** 

3118 
Removes all contents from the container. The container decides 

3119 
how $(D capacity) is affected. 

3120 


3121 
Postcondition: $(D empty) 

3122 


3123 
Complexity: $(BIGOH n) 

3124 
*/ 

3125 
void clear() 

3126 
{ 

3127 
this = Array!bool(); 

3128 
} 

3129 


3130 
unittest 

3131 
{ 

3132 
Array!bool a; 

3133 
a.insertBack([true, false, true, true]); 

3134 
a.clear(); 

3135 
assert(a.capacity == 0); 

3136 
} 

3137 


3138 
/** 

3139 
Sets the number of elements in the container to $(D 

3140 
newSize). If $(D newSize) is greater than $(D length), the 

3141 
added elements are added to the container and initialized with 

3142 
$(D ElementType.init). 

3143 


3144 
Complexity: $(BIGOH abs(n  newLength)) 

3145 


3146 
Postcondition: $(D _length == newLength) 

3147 
*/ 

3148 
@property void length(ulong newLength) 

3149 
{ 

3150 
_store.RefCounted.ensureInitialized(); 

3151 
auto newDataLength = 

3152 
to!size_t((newLength + bitsPerWord  1) / bitsPerWord); 

3153 
_store._backend.length = newDataLength; 

3154 
_store._length = newLength; 

3155 
} 

3156 


3157 
unittest 

3158 
{ 

3159 
Array!bool a; 

3160 
a.length = 1057; 

3161 
assert(a.length == 1057); 

3162 
foreach (e; a) 

3163 
{ 

3164 
assert(!e); 

3165 
} 

3166 
} 

3167 


3168 
/** 

3169 
Inserts $(D stuff) in the container. $(D stuff) can be a value 

3170 
convertible to $(D ElementType) or a range of objects 

3171 
convertible to $(D ElementType). 

3172 


3173 
The $(D stable) version guarantees that ranges iterating over 

3174 
the container are never invalidated. Client code that counts on 

3175 
noninvalidating insertion should use $(D stableInsert). 

3176 


3177 
Returns: The number of elements added. 

3178 


3179 
Complexity: $(BIGOH m * log(n)), where $(D m) is the number of 

3180 
elements in $(D stuff) 

3181 
*/ 

3182 
alias insertBack insert; 

3183 
///ditto 

3184 
alias insertBack stableInsert; 

3185 


3186 
/** 

3187 
Same as $(D insert(stuff)) and $(D stableInsert(stuff)) 

3188 
respectively, but relax the complexity constraint to linear. 

3189 
*/ 

3190 
alias insertBack linearInsert; 

3191 
///ditto 

3192 
alias insertBack stableLinearInsert; 

3193 


3194 
/** 

3195 
Picks one value in the container, removes it from the 

3196 
container, and returns it. The stable version behaves the same, 

3197 
but guarantees that ranges iterating over the container are 

3198 
never invalidated. 

3199 


3200 
Precondition: $(D !empty) 

3201 


3202 
Returns: The element removed. 

3203 


3204 
Complexity: $(BIGOH log(n)) 

3205 
*/ 

3206 
T removeAny() 

3207 
{ 

3208 
auto result = back(); 

3209 
removeBack(); 

3210 
return result; 

3211 
} 

3212 
/// ditto 

3213 
alias removeAny stableRemoveAny; 

3214 


3215 
unittest 

3216 
{ 

3217 
Array!bool a; 

3218 
a.length = 1057; 

3219 
assert(!a.removeAny()); 

3220 
assert(a.length == 1056); 

3221 
foreach (e; a) 

3222 
{ 

3223 
assert(!e); 

3224 
} 

3225 
} 

3226 


3227 
/** 

3228 
Inserts $(D value) to the back of the container. $(D stuff) can 

3229 
be a value convertible to $(D ElementType) or a range of 

3230 
objects convertible to $(D ElementType). The stable version 

3231 
behaves the same, but guarantees that ranges iterating over the 

3232 
container are never invalidated. 

3233 


3234 
Returns: The number of elements inserted 

3235 


3236 
Complexity: $(BIGOH log(n)) 

3237 
*/ 

3238 
ulong insertBack(Stuff)(Stuff stuff) if (is(Stuff : bool)) 

3239 
{ 

3240 
_store.RefCounted.ensureInitialized(); 

3241 
auto rem = _store._length % bitsPerWord; 

3242 
if (rem) 

3243 
{ 

3244 
// Fits within the current array 

3245 
if (stuff) 

3246 
{ 

3247 
data[$  1] = (1u << rem); 

3248 
} 

3249 
else 

3250 
{ 

3251 
data[$  1] &= ~(1u << rem); 

3252 
} 

3253 
} 

3254 
else 

3255 
{ 

3256 
// Need to add more data 

3257 
_store._backend.insertBack(stuff); 

3258 
} 

3259 
++_store._length; 

3260 
return 1; 

3261 
} 

3262 
/// Ditto 

3263 
ulong insertBack(Stuff)(Stuff stuff) 

3264 
if (isInputRange!Stuff && is(ElementType!Stuff : bool)) 

3265 
{ 

3266 
static if (!hasLength!Stuff) ulong result; 

3267 
for (; !stuff.empty; stuff.popFront()) 

3268 
{ 

3269 
insertBack(stuff.front); 

3270 
static if (!hasLength!Stuff) ++result; 

3271 
} 

3272 
static if (!hasLength!Stuff) return result; 

3273 
else return stuff.length; 

3274 
} 

3275 
/// ditto 

3276 
alias insertBack stableInsertBack; 

3277 


3278 
/** 

3279 
Removes the value at the front or back of the container. The 

3280 
stable version behaves the same, but guarantees that ranges 

3281 
iterating over the container are never invalidated. The 

3282 
optional parameter $(D howMany) instructs removal of that many 

3283 
elements. If $(D howMany > n), all elements are removed and no 

3284 
exception is thrown. 

3285 


3286 
Precondition: $(D !empty) 

3287 


3288 
Complexity: $(BIGOH log(n)). 

3289 
*/ 

3290 
void removeBack() 

3291 
{ 

3292 
enforce(_store._length); 

3293 
if (_store._length % bitsPerWord) 

3294 
{ 

3295 
// Cool, just decrease the length 

3296 
_store._length; 

3297 
} 

3298 
else 

3299 
{ 

3300 
// Reduce the allocated space 

3301 
_store._length; 

3302 
_store._backend.length = _store._backend.length  1; 

3303 
} 

3304 
} 

3305 
/// ditto 

3306 
alias removeBack stableRemoveBack; 

3307 


3308 
/** 

3309 
Removes $(D howMany) values at the front or back of the 

3310 
container. Unlike the unparameterized versions above, these 

3311 
functions do not throw if they could not remove $(D howMany) 

3312 
elements. Instead, if $(D howMany > n), all elements are 

3313 
removed. The returned value is the effective number of elements 

3314 
removed. The stable version behaves the same, but guarantees 

3315 
that ranges iterating over the container are never invalidated. 

3316 


3317 
Returns: The number of elements removed 

3318 


3319 
Complexity: $(BIGOH howMany * log(n)). 

3320 
*/ 

3321 
/// ditto 

3322 
ulong removeBack(ulong howMany) 

3323 
{ 

3324 
if (howMany >= length) 

3325 
{ 

3326 
howMany = length; 

3327 
clear(); 

3328 
} 

3329 
else 

3330 
{ 

3331 
length = length  howMany; 

3332 
} 

3333 
return howMany; 

3334 
} 

3335 


3336 
unittest 

3337 
{ 

3338 
Array!bool a; 

3339 
a.length = 1057; 

3340 
assert(a.removeBack(1000) == 1000); 

3341 
assert(a.length == 57); 

3342 
foreach (e; a) 

3343 
{ 

3344 
assert(!e); 

3345 
} 

3346 
} 

3347 


3348 
/** 

3349 
Inserts $(D stuff) before, after, or instead range $(D r), 

3350 
which must be a valid range previously extracted from this 

3351 
container. $(D stuff) can be a value convertible to $(D 

3352 
ElementType) or a range of objects convertible to $(D 

3353 
ElementType). The stable version behaves the same, but 

3354 
guarantees that ranges iterating over the container are never 

3355 
invalidated. 

3356 


3357 
Returns: The number of values inserted. 

3358 


3359 
Complexity: $(BIGOH n + m), where $(D m) is the length of $(D stuff) 

3360 
*/ 

3361 
ulong insertBefore(Stuff)(Range r, Stuff stuff) 

3362 
{ 

3363 
// TODO: make this faster, it moves one bit at a time 

3364 
immutable inserted = stableInsertBack(stuff); 

3365 
immutable tailLength = length  inserted; 

3366 
bringToFront( 

3367 
this[r._a .. tailLength], 

3368 
this[tailLength .. length]); 

3369 
return inserted; 

3370 
} 

3371 
/// ditto 

3372 
alias insertBefore stableInsertBefore; 

3373 


3374 
unittest 

3375 
{ 

3376 
Array!bool a; 

3377 
version (bugxxxx) 

3378 
{ 

3379 
a._store.refCountedDebug = true; 

3380 
} 

3381 
a.insertBefore(a[], true); 

3382 
assert(a.length == 1, text(a.length)); 

3383 
a.insertBefore(a[], false); 

3384 
assert(a.length == 2, text(a.length)); 

3385 
} 

3386 


3387 
/// ditto 

3388 
ulong insertAfter(Stuff)(Range r, Stuff stuff) 

3389 
{ 

3390 
// TODO: make this faster, it moves one bit at a time 

3391 
immutable inserted = stableInsertBack(stuff); 

3392 
immutable tailLength = length  inserted; 

3393 
bringToFront( 

3394 
this[r._b .. tailLength], 

3395 
this[tailLength .. length]); 

3396 
return inserted; 

3397 
} 

3398 
/// ditto 

3399 
alias insertAfter stableInsertAfter; 

3400 


3401 
unittest 

3402 
{ 

3403 
Array!bool a; 

3404 
a.length = 10; 

3405 
a.insertAfter(a[0 .. 5], true); 

3406 
assert(a.length == 11, text(a.length)); 

3407 
assert(a[5]); 

3408 
} 

3409 
/// ditto 

3410 
size_t replace(Stuff)(Range r, Stuff stuff) if (is(Stuff : bool)) 

3411 
{ 

3412 
if (!r.empty) 

3413 
{ 

3414 
// There is room 

3415 
r.front = stuff; 

3416 
r.popFront(); 

3417 
linearRemove(r); 

3418 
} 

3419 
else 

3420 
{ 

3421 
// No room, must insert 

3422 
insertBefore(r, stuff); 

3423 
} 

3424 
return 1; 

3425 
} 

3426 
/// ditto 

3427 
alias replace stableReplace; 

3428 


3429 
unittest 

3430 
{ 

3431 
Array!bool a; 

3432 
a.length = 10; 

3433 
a.replace(a[3 .. 5], true); 

3434 
assert(a.length == 9, text(a.length)); 

3435 
assert(a[3]); 

3436 
} 

3437 


3438 
/** 

3439 
Removes all elements belonging to $(D r), which must be a range 

3440 
obtained originally from this container. The stable version 

3441 
behaves the same, but guarantees that ranges iterating over the 

3442 
container are never invalidated. 

3443 


3444 
Returns: A range spanning the remaining elements in the container that 

3445 
initially were right after $(D r). 

3446 


3447 
Complexity: $(BIGOH n) 

3448 
*/ 

3449 
Range linearRemove(Range r) 

3450 
{ 

3451 
copy(this[r._b .. length], this[r._a .. length]); 

3452 
length = length  r.length; 

3453 
return this[r._a .. length]; 

3454 
} 

3455 
/// ditto 

3456 
alias linearRemove stableLinearRemove; 

3457 
} 

3458 


3459 
unittest 

3460 
{ 

3461 
Array!bool a; 

3462 
assert(a.empty); 

3463 
} 

3464 


3465 
/* 

3466 
* Implementation for a Red Black node for use in a Red Black Tree (see below) 

3467 
* 

3468 
* this implementation assumes we have a marker Node that is the parent of the 

3469 
* root Node. This marker Node is not a valid Node, but marks the end of the 

3470 
* collection. The root is the left child of the marker Node, so it is always 

3471 
* last in the collection. The marker Node is passed in to the setColor 

3472 
* function, and the Node which has this Node as its parent is assumed to be 

3473 
* the root Node. 

3474 
* 

3475 
* A Red Black tree should have O(lg(n)) insertion, removal, and search time. 

3476 
*/ 

3477 
struct RBNode(V) 

3478 
{ 

3479 
/* 

3480 
* Convenience alias 

3481 
*/ 

3482 
alias RBNode* Node; 

3483 


3484 
private Node _left; 

3485 
private Node _right; 

3486 
private Node _parent; 

3487 


3488 
/** 

3489 
* The value held by this node 

3490 
*/ 

3491 
V value; 

3492 


3493 
/** 

3494 
* Enumeration determining what color the node is. Null nodes are assumed 

3495 
* to be black. 

3496 
*/ 

3497 
enum Color : byte 

3498 
{ 

3499 
Red, 

3500 
Black 

3501 
} 

3502 


3503 
/** 

3504 
* The color of the node. 

3505 
*/ 

3506 
Color color; 

3507 


3508 
/** 

3509 
* Get the left child 

3510 
*/ 

3511 
@property Node left() 

3512 
{ 

3513 
return _left; 

3514 
} 

3515 


3516 
/** 

3517 
* Get the right child 

3518 
*/ 

3519 
@property Node right() 

3520 
{ 

3521 
return _right; 

3522 
} 

3523 


3524 
/** 

3525 
* Get the parent 

3526 
*/ 

3527 
@property Node parent() 

3528 
{ 

3529 
return _parent; 

3530 
} 

3531 


3532 
/** 

3533 
* Set the left child. Also updates the new child's parent node. This 

3534 
* does not update the previous child. 

3535 
* 

3536 
* Returns newNode 

3537 
*/ 

3538 
@property Node left(Node newNode) 

3539 
{ 

3540 
_left = newNode; 

3541 
if(newNode !is null) 

3542 
newNode._parent = &this; 

3543 
return newNode; 

3544 
} 

3545 


3546 
/** 

3547 
* Set the right child. Also updates the new child's parent node. This 

3548 
* does not update the previous child. 

3549 
* 

3550 
* Returns newNode 

3551 
*/ 

3552 
@property Node right(Node newNode) 

3553 
{ 

3554 
_right = newNode; 

3555 
if(newNode !is null) 

3556 
newNode._parent = &this; 

3557 
return newNode; 

3558 
} 

3559 


3560 
// assume _left is not null 

3561 
// 

3562 
// performs rotateright operation, where this is T, _right is R, _left is 

3563 
// L, _parent is P: 

3564 
// 

3565 
// P P 

3566 
//  >  

3567 
// T L 

3568 
// / \ / \ 

3569 
// L R a T 

3570 
// / \ / \ 

3571 
// a b b R 

3572 
// 

3573 
/** 

3574 
* Rotate right. This performs the following operations: 

3575 
*  The left child becomes the parent of this node. 

3576 
*  This node becomes the new parent's right child. 

3577 
*  The old right child of the new parent becomes the left child of this 

3578 
* node. 

3579 
*/ 

3580 
Node rotateR() 

3581 
in 

3582 
{ 

3583 
assert(_left !is null); 

3584 
} 

3585 
body 

3586 
{ 

3587 
// sets _left._parent also 

3588 
if(isLeftNode) 

3589 
parent.left = _left; 

3590 
else 

3591 
parent.right = _left; 

3592 
Node tmp = _left._right; 

3593 


3594 
// sets _parent also 

3595 
_left.right = &this; 

3596 


3597 
// sets tmp._parent also 

3598 
left = tmp; 

3599 


3600 
return &this; 

3601 
} 

3602 


3603 
// assumes _right is non null 

3604 
// 

3605 
// performs rotateleft operation, where this is T, _right is R, _left is 

3606 
// L, _parent is P: 

3607 
// 

3608 
// P P 

3609 
//  >  

3610 
// T R 

3611 
// / \ / \ 

3612 
// L R T b 

3613 
// / \ / \ 

3614 
// a b L a 

3615 
// 

3616 
/** 

3617 
* Rotate left. This performs the following operations: 

3618 
*  The right child becomes the parent of this node. 

3619 
*  This node becomes the new parent's left child. 

3620 
*  The old left child of the new parent becomes the right child of this 

3621 
* node. 

3622 
*/ 

3623 
Node rotateL() 

3624 
in 

3625 
{ 

3626 
assert(_right !is null); 

3627 
} 

3628 
body 

3629 
{ 

3630 
// sets _right._parent also 

3631 
if(isLeftNode) 

3632 
parent.left = _right; 

3633 
else 

3634 
parent.right = _right; 

3635 
Node tmp = _right._left; 

3636 


3637 
// sets _parent also 

3638 
_right.left = &this; 

3639 


3640 
// sets tmp._parent also 

3641 
right = tmp; 

3642 
return &this; 

3643 
} 

3644 


3645 


3646 
/** 

3647 
* Returns true if this node is a left child. 

3648 
* 

3649 
* Note that this should always return a value because the root has a 

3650 
* parent which is the marker node. 

3651 
*/ 

3652 
@property bool isLeftNode() const 

3653 
in 

3654 
{ 

3655 
assert(_parent !is null); 

3656 
} 

3657 
body 

3658 
{ 

3659 
return _parent._left is &this; 

3660 
} 

3661 


3662 
/** 

3663 
* Set the color of the node after it is inserted. This performs an 

3664 
* update to the whole tree, possibly rotating nodes to keep the RedBlack 

3665 
* properties correct. This is an O(lg(n)) operation, where n is the 

3666 
* number of nodes in the tree. 

3667 
* 

3668 
* end is the marker node, which is the parent of the topmost valid node. 

3669 
*/ 

3670 
void setColor(Node end) 

3671 
{ 

3672 
// test against the marker node 

3673 
if(_parent !is end) 

3674 
{ 

3675 
if(_parent.color == Color.Red) 

3676 
{ 

3677 
Node cur = &this; 

3678 
while(true) 

3679 
{ 

3680 
// because root is always black, _parent._parent always exists 

3681 
if(cur._parent.isLeftNode) 

3682 
{ 

3683 
// parent is left node, y is 'uncle', could be null 

3684 
Node y = cur._parent._parent._right; 

3685 
if(y !is null && y.color == Color.Red) 

3686 
{ 

3687 
cur._parent.color = Color.Black; 

3688 
y.color = Color.Black; 

3689 
cur = cur._parent._parent; 

3690 
if(cur._parent is end) 

3691 
{ 

3692 
// root node 

3693 
cur.color = Color.Black; 

3694 
break; 

3695 
} 

3696 
else 

3697 
{ 

3698 
// not root node 

3699 
cur.color = Color.Red; 

3700 
if(cur._parent.color == Color.Black) 

3701 
// satisfied, exit the loop 

3702 
break; 

3703 
} 

3704 
} 

3705 
else 

3706 
{ 

3707 
if(!cur.isLeftNode) 

3708 
cur = cur._parent.rotateL(); 

3709 
cur._parent.color = Color.Black; 

3710 
cur = cur._parent._parent.rotateR(); 

3711 
cur.color = Color.Red; 

3712 
// tree should be satisfied now 

3713 
break; 

3714 
} 

3715 
} 

3716 
else 

3717 
{ 

3718 
// parent is right node, y is 'uncle' 

3719 
Node y = cur._parent._parent._left; 

3720 
if(y !is null && y.color == Color.Red) 

3721 
{ 

3722 
cur._parent.color = Color.Black; 

3723 
y.color = Color.Black; 

3724 
cur = cur._parent._parent; 

3725 
if(cur._parent is end) 

3726 
{ 

3727 
// root node 

3728 
cur.color = Color.Black; 

3729 
break; 

3730 
} 

3731 
else 

3732 
{ 

3733 
// not root node 

3734 
cur.color = Color.Red; 

3735 
if(cur._parent.color == Color.Black) 

3736 
// satisfied, exit the loop 

3737 
break; 

3738 
} 

3739 
} 

3740 
else 

3741 
{ 

3742 
if(cur.isLeftNode) 

3743 
cur = cur._parent.rotateR(); 

3744 
cur._parent.color = Color.Black; 

3745 
cur = cur._parent._parent.rotateL(); 

3746 
cur.color = Color.Red; 

3747 
// tree should be satisfied now 

3748 
break; 

3749 
} 

3750 
} 

3751 
} 

3752 


3753 
} 

3754 
} 

3755 
else 

3756 
{ 

3757 
// 

3758 
// this is the root node, color it black 

3759 
// 

3760 
color = Color.Black; 

3761 
} 

3762 
} 

3763 


3764 
/** 

3765 
* Remove this node from the tree. The 'end' node is used as the marker 

3766 
* which is root's parent. Note that this cannot be null! 

3767 
* 

3768 
* Returns the next highest valued node in the tree after this one, or end 

3769 
* if this was the highestvalued node. 

3770 
*/ 

3771 
Node remove(Node end) 

3772 
{ 

3773 
// 

3774 
// remove this node from the tree, fixing the color if necessary. 

3775 
// 

3776 
Node x; 

3777 
Node ret; 

3778 
if(_left is null  _right is null) 

3779 
{ 

3780 
ret = next; 

3781 
} 

3782 
else 

3783 
{ 

3784 
// 

3785 
// normally, we can just swap this node's and y's value, but 

3786 
// because an iterator could be pointing to y and we don't want to 

3787 
// disturb it, we swap this node and y's structure instead. This 

3788 
// can also be a benefit if the value of the tree is a large 

3789 
// struct, which takes a long time to copy. 

3790 
// 

3791 
Node yp, yl, yr; 

3792 
Node y = next; 

3793 
yp = y._parent; 

3794 
yl = y._left; 

3795 
yr = y._right; 

3796 
auto yc = y.color; 

3797 
auto isyleft = y.isLeftNode; 

3798 


3799 
// 

3800 
// replace y's structure with structure of this node. 

3801 
// 

3802 
if(isLeftNode) 

3803 
_parent.left = y; 

3804 
else 

3805 
_parent.right = y; 

3806 
// 

3807 
// need special case so y doesn't point back to itself 

3808 
// 

3809 
y.left = _left; 

3810 
if(_right is y) 

3811 
y.right = &this; 

3812 
else 

3813 
y.right = _right; 

3814 
y.color = color; 

3815 


3816 
// 

3817 
// replace this node's structure with structure of y. 

3818 
// 

3819 
left = yl; 

3820 
right = yr; 

3821 
if(_parent !is y) 

3822 
{ 

3823 
if(isyleft) 

3824 
yp.left = &this; 

3825 
else 

3826 
yp.right = &this; 

3827 
} 

3828 
color = yc; 

3829 


3830 
// 

3831 
// set return value 

3832 
// 

3833 
ret = y; 

3834 
} 

3835 


3836 
// if this has less than 2 children, remove it 

3837 
if(_left !is null) 

3838 
x = _left; 

3839 
else 

3840 
x = _right; 

3841 


3842 
// remove this from the tree at the end of the procedure 

3843 
bool removeThis = false; 

3844 
if(x is null) 

3845 
{ 

3846 
// pretend this is a null node, remove this on finishing 

3847 
x = &this; 

3848 
removeThis = true; 

3849 
} 

3850 
else if(isLeftNode) 

3851 
_parent.left = x; 

3852 
else 

3853 
_parent.right = x; 

3854 


3855 
// if the color of this is black, then it needs to be fixed 

3856 
if(color == color.Black) 

3857 
{ 

3858 
// need to recolor the tree. 

3859 
while(x._parent !is end && x.color == Node.Color.Black) 

3860 
{ 

3861 
if(x.isLeftNode) 

3862 
{ 

3863 
// left node 

3864 
Node w = x._parent._right; 

3865 
if(w.color == Node.Color.Red) 

3866 
{ 

3867 
w.color = Node.Color.Black; 

3868 
x._parent.color = Node.Color.Red; 

3869 
x._parent.rotateL(); 

3870 
w = x._parent._right; 

3871 
} 

3872 
Node wl = w.left; 

3873 
Node wr = w.right; 

3874 
if((wl is null  wl.color == Node.Color.Black) && 

3875 
(wr is null  wr.color == Node.Color.Black)) 

3876 
{ 

3877 
w.color = Node.Color.Red; 

3878 
x = x._parent; 

3879 
} 

3880 
else 

3881 
{ 

3882 
if(wr is null  wr.color == Node.Color.Black) 

3883 
{ 

3884 
// wl cannot be null here 

3885 
wl.color = Node.Color.Black; 

3886 
w.color = Node.Color.Red; 

3887 
w.rotateR(); 

3888 
w = x._parent._right; 

3889 
} 

3890 


3891 
w.color = x._parent.color; 

3892 
x._parent.color = Node.Color.Black; 

3893 
w._right.color = Node.Color.Black; 

3894 
x._parent.rotateL(); 

3895 
x = end.left; // x = root 

3896 
} 

3897 
} 

3898 
else 

3899 
{ 

3900 
// right node 

3901 
Node w = x._parent._left; 

3902 
if(w.color == Node.Color.Red) 

3903 
{ 

3904 
w.color = Node.Color.Black; 

3905 
x._parent.color = Node.Color.Red; 

3906 
x._parent.rotateR(); 

3907 
w = x._parent._left; 

3908 
} 

3909 
Node wl = w.left; 

3910 
Node wr = w.right; 

3911 
if((wl is null  wl.color == Node.Color.Black) && 

3912 
(wr is null  wr.color == Node.Color.Black)) 

3913 
{ 

3914 
w.color = Node.Color.Red; 

3915 
x = x._parent; 

3916 
} 

3917 
else 

3918 
{ 

3919 
if(wl is null  wl.color == Node.Color.Black) 

3920 
{ 

3921 
// wr cannot be null here 

3922 
wr.color = Node.Color.Black; 

3923 
w.color = Node.Color.Red; 

3924 
w.rotateL(); 

3925 
w = x._parent._left; 

3926 
} 

3927 


3928 
w.color = x._parent.color; 

3929 
x._parent.color = Node.Color.Black; 

3930 
w._left.color = Node.Color.Black; 

3931 
x._parent.rotateR(); 

3932 
x = end.left; // x = root 

3933 
} 

3934 
} 

3935 
} 

3936 
x.color = Node.Color.Black; 

3937 
} 

3938 


3939 
if(removeThis) 

3940 
{ 

3941 
// 

3942 
// clear this node out of the tree 

3943 
// 

3944 
if(isLeftNode) 

3945 
_parent.left = null; 

3946 
else 

3947 
_parent.right = null; 

3948 
} 

3949 


3950 
return ret; 

3951 
} 

3952 


3953 
/** 

3954 
* Return the leftmost descendant of this node. 

3955 
*/ 

3956 
@property Node leftmost() 

3957 
{ 

3958 
Node result = &this; 

3959 
while(result._left !is null) 

3960 
result = result._left; 

3961 
return result; 

3962 
} 

3963 


3964 
/** 

3965 
* Return the rightmost descendant of this node 

3966 
*/ 

3967 
@property Node rightmost() 

3968 
{ 

3969 
Node result = &this; 

3970 
while(result._right !is null) 

3971 
result = result._right; 

3972 
return result; 

3973 
} 

3974 


3975 
/** 

3976 
* Returns the next valued node in the tree. 

3977 
* 

3978 
* You should never call this on the marker node, as it is assumed that 

3979 
* there is a valid next node. 

3980 
*/ 

3981 
@property Node next() 

3982 
{ 

3983 
Node n = &this; 

3984 
if(n.right is null) 

3985 
{ 

3986 
while(!n.isLeftNode) 

3987 
n = n._parent; 

3988 
return n._parent; 

3989 
} 

3990 
else 

3991 
return n.right.leftmost; 

3992 
} 

3993 


3994 
/** 

3995 
* Returns the previous valued node in the tree. 

3996 
* 

3997 
* You should never call this on the leftmost node of the tree as it is 

3998 
* assumed that there is a valid previous node. 

3999 
*/ 

4000 
@property Node prev() 

4001 
{ 

4002 
Node n = &this; 

4003 
if(n.left is null) 

4004 
{ 

4005 
while(n.isLeftNode) 

4006 
n = n._parent; 

4007 
return n._parent; 

4008 
} 

4009 
else 

4010 
return n.left.rightmost; 

4011 
} 

4012 


4013 
Node dup(scope Node delegate(V v) alloc) 

4014 
{ 

4015 
// 

4016 
// duplicate this and all child nodes 

4017 
// 

4018 
// The recursion should be lg(n), so we shouldn't have to worry about 

4019 
// stack size. 

4020 
// 

4021 
Node copy = alloc(value); 

4022 
copy.color = color; 

4023 
if(_left !is null) 

4024 
copy.left = _left.dup(alloc); 

4025 
if(_right !is null) 

4026 
copy.right = _right.dup(alloc); 

4027 
return copy; 

4028 
} 

4029 


4030 
Node dup() 

4031 
{ 

4032 
Node copy = new RBNode!V; 

4033 
copy.value = value; 

4034 
copy.color = color; 

4035 
if(_left !is null) 

4036 
copy.left = _left.dup(); 

4037 
if(_right !is null) 

4038 
copy.right = _right.dup(); 

4039 
return copy; 

4040 
} 

4041 
} 

4042 


4043 
/** 

4044 
* Implementation of a $(LUCKY redblack tree) container. 

4045 
* 

4046 
* All inserts, removes, searches, and any function in general has complexity 

4047 
* of $(BIGOH lg(n)). 

4048 
* 

4049 
* To use a different comparison than $(D "a < b"), pass a different operator string 

4050 
* that can be used by $(XREF functional, binaryFun), or pass in a 

4051 
* function, delegate, functor, or any type where $(D less(a, b)) results in a $(D bool) 

4052 
* value. 

4053 
* 

4054 
* Note that less should produce a strict ordering. That is, for two unequal 

4055 
* elements $(D a) and $(D b), $(D less(a, b) == !less(b, a)). $(D less(a, a)) should 

4056 
* always equal $(D false). 

4057 
* 

4058 
* If $(D allowDuplicates) is set to $(D true), then inserting the same element more than 

4059 
* once continues to add more elements. If it is $(D false), duplicate elements are 

4060 
* ignored on insertion. If duplicates are allowed, then new elements are 

4061 
* inserted after all existing duplicate elements. 

4062 
*/ 

4063 
struct RedBlackTree(T, alias less = "a < b", bool allowDuplicates = false) 

4064 
if (is(typeof(less(T.init, T.init)) == bool)  is(typeof(less) == string)) 

4065 
{ 

4066 
static if(is(typeof(less) == string)) 

4067 
alias binaryFun!(less) _less; 

4068 
else 

4069 
alias less _less; 

4070 


4071 
// BUG: this must come first in the struct due to issue 2810 

4072 


4073 
// add an element to the tree, returns the node added, or the existing node 

4074 
// if it has already been added and allowDuplicates is false 

4075 


4076 
private auto _add(Elem n) 

4077 
{ 

4078 
Node result; 

4079 
static if(!allowDuplicates) 

4080 
bool added = true; 

4081 
if(!_end.left) 

4082 
{ 

4083 
_end.left = result = allocate(n); 

4084 
} 

4085 
else 

4086 
{ 

4087 
Node newParent = _end.left; 

4088 
Node nxt = void; 

4089 
while(true) 

4090 
{ 

4091 
if(_less(n, newParent.value)) 

4092 
{ 

4093 
nxt = newParent.left; 

4094 
if(nxt is null) 

4095 
{ 

4096 
// 

4097 
// add to right of new parent 

4098 
// 

4099 
newParent.left = result = allocate(n); 

4100 
break; 

4101 
} 

4102 
} 

4103 
else 

4104 
{ 

4105 
static if(!allowDuplicates) 

4106 
{ 

4107 
if(!_less(newParent.value, n)) 

4108 
{ 

4109 
result = newParent; 

4110 
added = false; 

4111 
break; 

4112 
} 

4113 
} 

4114 
nxt = newParent.right; 

4115 
if(nxt is null) 

4116 
{ 

4117 
// 

4118 
// add to right of new parent 

4119 
// 

4120 
newParent.right = result = allocate(n); 

4121 
break; 

4122 
} 

4123 
} 

4124 
newParent = nxt; 

4125 
} 

4126 
} 

4127 


4128 
static if(allowDuplicates) 

4129 
{ 

4130 
result.setColor(_end); 

4131 
version(RBDoChecks) 

4132 
check(); 

4133 
return result; 

4134 
} 

4135 
else 

4136 
{ 

4137 
if(added) 

4138 
result.setColor(_end); 

4139 
version(RBDoChecks) 

4140 
check(); 

4141 
return Tuple!(bool, "added", Node, "n")(added, result); 

4142 
} 

4143 
} 

4144 


4145 
version(unittest) 

4146 
{ 

4147 
private enum doUnittest = isIntegral!T; 

4148 


4149 
bool arrayEqual(T[] arr) 

4150 
{ 

4151 
if(walkLength(this[]) == arr.length) 

4152 
{ 

4153 
foreach(v; arr) 

4154 
{ 

4155 
if(!(v in this)) 

4156 
return false; 

4157 
} 

4158 
return true; 

4159 
} 

4160 
return false; 

4161 
} 

4162 


4163 
private static RedBlackTree create(Elem[] elems...) 

4164 
{ 

4165 
return RedBlackTree(elems); 

4166 
} 

4167 
} 

4168 
else 

4169 
{ 

4170 
private enum doUnittest = false; 

4171 
} 

4172 


4173 
/** 

4174 
* Element type for the tree 

4175 
*/ 

4176 
alias T Elem; 

4177 


4178 
// used for convenience 

4179 
private alias RBNode!Elem.Node Node; 

4180 


4181 
private Node _end; 

4182 


4183 
private void _setup() 

4184 
{ 

4185 
_end = allocate(); 

4186 
} 

4187 


4188 
static private Node allocate() 

4189 
{ 

4190 
return new RBNode!Elem; 

4191 
} 

4192 


4193 
static private Node allocate(Elem v) 

4194 
{ 

4195 
auto result = allocate(); 

4196 
result.value = v; 

4197 
return result; 

4198 
} 

4199 


4200 
/** 

4201 
* The range type for $(D RedBlackTree) 

4202 
*/ 

4203 
struct Range 

4204 
{ 

4205 
private Node _begin; 

4206 
private Node _end; 

4207 


4208 
private this(Node b, Node e) 

4209 
{ 

4210 
_begin = b; 

4211 
_end = e; 

4212 
} 

4213 


4214 
/** 

4215 
* Returns $(D true) if the range is _empty 

4216 
*/ 

4217 
@property bool empty() const 

4218 
{ 

4219 
return _begin is _end; 

4220 
} 

4221 


4222 
/** 

4223 
* Returns the first element in the range 

4224 
*/ 

4225 
@property Elem front() 

4226 
{ 

4227 
return _begin.value; 

4228 
} 

4229 


4230 
/** 

4231 
* Returns the last element in the range 

4232 
*/ 

4233 
@property Elem back() 

4234 
{ 

4235 
return _end.prev.value; 

4236 
} 

4237 


4238 
/** 

4239 
* pop the front element from the range 

4240 
* 

4241 
* complexity: amortized $(BIGOH 1) 

4242 
*/ 

4243 
void popFront() 

4244 
{ 

4245 
_begin = _begin.next; 

4246 
} 

4247 


4248 
/** 

4249 
* pop the back element from the range 

4250 
* 

4251 
* complexity: amortized $(BIGOH 1) 

4252 
*/ 

4253 
void popBack() 

4254 
{ 

4255 
_end = _end.prev; 

4256 
} 

4257 


4258 
/** 

4259 
* Trivial _save implementation, needed for $(D isForwardRange). 

4260 
*/ 

4261 
@property Range save() 

4262 
{ 

4263 
return this; 

4264 
} 

4265 
} 

4266 


4267 
static if(doUnittest) unittest 

4268 
{ 

4269 
auto ts = create(1, 2, 3, 4, 5); 

4270 
auto r = ts[]; 

4271 
assert(std.algorithm.equal(r, cast(T[])[1, 2, 3, 4, 5])); 

4272 
assert(r.front == 1); 

4273 
assert(r.back != r.front); 

4274 
auto oldfront = r.front; 

4275 
auto oldback = r.back; 

4276 
r.popFront(); 

4277 
r.popBack(); 

4278 
assert(r.front != r.back); 

4279 
assert(r.front != oldfront); 

4280 
assert(r.back != oldback); 

4281 
} 

4282 


4283 
// find a node based on an element value 

4284 
private Node _find(Elem e) 

4285 
{ 

4286 
static if(allowDuplicates) 

4287 
{ 

4288 
Node cur = _end.left; 

4289 
Node result = null; 

4290 
while(cur) 

4291 
{ 

4292 
if(_less(cur.value, e)) 

4293 
cur = cur.right; 

4294 
else if(_less(e, cur.value)) 

4295 
cur = cur.left; 

4296 
else 

4297 
{ 

4298 
// want to find the leftmost element 

4299 
result = cur; 

4300 
cur = cur.left; 

4301 
} 

4302 
} 

4303 
return result; 

4304 
} 

4305 
else 

4306 
{ 

4307 
Node cur = _end.left; 

4308 
while(cur) 

4309 
{ 

4310 
if(_less(cur.value, e)) 

4311 
cur = cur.right; 

4312 
else if(_less(e, cur.value)) 

4313 
cur = cur.left; 

4314 
else 

4315 
return cur; 

4316 
} 

4317 
return null; 

4318 
} 

4319 
} 

4320 


4321 
/** 

4322 
* Check if any elements exist in the container. Returns $(D true) if at least 

4323 
* one element exists. 

4324 
*/ 

4325 
@property bool empty() 

4326 
{ 

4327 
return _end.left is null; 

4328 
} 

4329 


4330 
/** 

4331 
* Duplicate this container. The resulting container contains a shallow 

4332 
* copy of the elements. 

4333 
* 

4334 
* Complexity: $(BIGOH n) 

4335 
*/ 

4336 
RedBlackTree dup() 

4337 
{ 

4338 
RedBlackTree result; 

4339 
result._setup(); 

4340 
result._end = _end.dup(); 

4341 
return result; 

4342 
} 

4343 


4344 
static if(doUnittest) unittest 

4345 
{ 

4346 
auto ts = create(1, 2, 3, 4, 5); 

4347 
auto ts2 = ts.dup(); 

4348 
assert(std.algorithm.equal(ts[], ts2[])); 

4349 
ts2.insert(cast(Elem)6); 

4350 
assert(!std.algorithm.equal(ts[], ts2[])); 

4351 
} 

4352 


4353 
/** 

4354 
* Fetch a range that spans all the elements in the container. 

4355 
* 

4356 
* Complexity: $(BIGOH log(n)) 

4357 
*/ 

4358 
Range opSlice() 

4359 
{ 

4360 
return Range(_end.leftmost, _end); 

4361 
} 

4362 


4363 
/** 

4364 
* The front element in the container 

4365 
* 

4366 
* Complexity: $(BIGOH log(n)) 

4367 
*/ 

4368 
Elem front() 

4369 
{ 

4370 
return _end.leftmost.value; 

4371 
} 

4372 


4373 
/** 

4374 
* The last element in the container 

4375 
* 

4376 
* Complexity: $(BIGOH log(n)) 

4377 
*/ 

4378 
Elem back() 

4379 
{ 

4380 
return _end.prev.value; 

4381 
} 

4382 


4383 
/** 

4384 
* Check to see if an element exists in the container 

4385 
* 

4386 
* Complexity: $(BIGOH log(n)) 

4387 
*/ 

4388 
bool opBinaryRight(string op)(Elem e) if (op == "in") 

4389 
{ 

4390 
return _find(e) !is null; 

4391 
} 

4392 


4393 
static if(doUnittest) unittest 

4394 
{ 

4395 
auto ts = create(1, 2, 3, 4, 5); 

4396 
assert(cast(Elem)3 in ts); 

4397 
assert(cast(Elem)6 !in ts); 

4398 
} 

4399 


4400 
/** 

4401 
* Clear the container of all elements 

4402 
* 

4403 
* Complexity: $(BIGOH 1) 

4404 
*/ 

4405 
void clear() 

4406 
{ 

4407 
_end.left = null; 

4408 
} 

4409 


4410 
/** 

4411 
* Insert a single element in the container. Note that this does not 

4412 
* invalidate any ranges currently iterating the container. 

4413 
* 

4414 
* Complexity: $(BIGOH log(n)) 

4415 
*/ 

4416 
size_t stableInsert(Stuff)(Stuff stuff) if (isImplicitlyConvertible!(Stuff, Elem)) 

4417 
{ 

4418 
static if(allowDuplicates) 

4419 
{ 

4420 
_add(stuff); 

4421 
return 1; 

4422 
} 

4423 
else 

4424 
{ 

4425 
return(_add(stuff).added ? 1 : 0); 

4426 
} 

4427 
} 

4428 


4429 
/** 

4430 
* Insert a range of elements in the container. Note that this does not 

4431 
* invalidate any ranges currently iterating the container. 

4432 
* 

4433 
* Complexity: $(BIGOH m * log(n)) 

4434 
*/ 

4435 
size_t stableInsert(Stuff)(Stuff stuff) if(isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, Elem)) 

4436 
{ 

4437 
size_t result = 0; 

4438 
static if(allowDuplicates) 

4439 
{ 

4440 
foreach(e; stuff) 

4441 
{ 

4442 
++result; 

4443 
_add(e); 

4444 
} 

4445 
} 

4446 
else 

4447 
{ 

4448 
foreach(e; stuff) 

4449 
{ 

4450 
if(_add(e).added) 

4451 
++result; 

4452 
} 

4453 
} 

4454 
return result; 

4455 
} 

4456 


4457 
/// ditto 

4458 
alias stableInsert insert; 

4459 


4460 
static if(doUnittest) unittest 

4461 
{ 

4462 
auto ts = create(1,2,3,4,5); 

4463 
assert(ts.stableInsert(cast(Elem[])[6, 7, 8, 9, 10]) == 5); 

4464 
assert(ts.stableInsert(cast(Elem)11) == 1); 

4465 
assert(ts.arrayEqual([1,2,3,4,5,6,7,8,9,10,11])); 

4466 
} 

4467 


4468 
/** 

4469 
* Remove an element from the container and return its value. 

4470 
* 

4471 
* Complexity: $(BIGOH log(n)) 

4472 
*/ 

4473 
Elem removeAny() 

4474 
{ 

4475 
auto n = _end.leftmost; 

4476 
auto result = n.value; 

4477 
n.remove(_end); 

4478 
version(RBDoChecks) 

4479 
check(); 

4480 
return result; 

4481 
} 

4482 


4483 
static if(doUnittest) unittest 

4484 
{ 

4485 
auto ts = create(1,2,3,4,5); 

4486 
auto x = ts.removeAny(); 

4487 
Elem[] arr; 

4488 
foreach(Elem i; 1..6) 

4489 
if(i != x) arr ~= i; 

4490 
assert(ts.arrayEqual(arr)); 

4491 
} 

4492 


4493 
/** 

4494 
* Remove the front element from the container. 

4495 
* 

4496 
* Complexity: $(BIGOH log(n)) 

4497 
*/ 

4498 
void removeFront() 

4499 
{ 

4500 
_end.leftmost.remove(_end); 

4501 
version(RBDoChecks) 

4502 
check(); 

4503 
} 

4504 


4505 
/** 

4506 
* Remove the back element from the container. 

4507 
* 

4508 
* Complexity: $(BIGOH log(n)) 

4509 
*/ 

4510 
void removeBack() 

4511 
{ 

4512 
_end.prev.remove(_end); 

4513 
version(RBDoChecks) 

4514 
check(); 

4515 
} 

4516 


4517 
static if(doUnittest) unittest 

4518 
{ 

4519 
auto ts = create(1,2,3,4,5); 

4520 
ts.removeBack(); 

4521 
assert(ts.arrayEqual([1,2,3,4])); 

4522 
ts.removeFront(); 

4523 
assert(ts.arrayEqual([2,3,4])); 

4524 
} 

4525 


4526 
/** 

4527 
* Remove the given range from the container. Returns a range containing 

4528 
* all the elements that were after the given range. 

4529 
* 

4530 
* Complexity: $(BIGOH m * log(n)) 

4531 
*/ 

4532 
Range remove(Range r) 

4533 
{ 

4534 
auto b = r._begin; 

4535 
auto e = r._end; 

4536 
while(b !is e) 

4537 
{ 

4538 
b = b.remove(_end); 

4539 
} 

4540 
version(RBDoChecks) 

4541 
check(); 

4542 
return Range(e, _end); 

4543 
} 

4544 


4545 
static if(doUnittest) unittest 

4546 
{ 

4547 
auto ts = create(1,2,3,4,5); 

4548 
auto r = ts[]; 

4549 
r.popFront(); 

4550 
r.popBack(); 

4551 
auto r2 = ts.remove(r); 

4552 
assert(ts.arrayEqual([1,5])); 

4553 
assert(std.algorithm.equal(r2, [5])); 

4554 
} 

4555 


4556 
// find the first node where the value is > e 

4557 
private Node _firstGreater(Elem e) 

4558 
{ 

4559 
// can't use _find, because we cannot return null 

4560 
auto cur = _end.left; 

4561 
auto result = _end; 

4562 
while(cur) 

4563 
{ 

4564 
if(_less(e, cur.value)) 

4565 
{ 

4566 
result = cur; 

4567 
cur = cur.left; 

4568 
} 

4569 
else 

4570 
cur = cur.right; 

4571 
} 

4572 
return result; 

4573 
} 

4574 


4575 
// find the first node where the value is >= e 

4576 
private Node _firstGreaterEqual(Elem e) 

4577 
{ 

4578 
// can't use _find, because we cannot return null. 

4579 
auto cur = _end.left; 

4580 
auto result = _end; 

4581 
while(cur) 

4582 
{ 

4583 
if(_less(cur.value, e)) 

4584 
cur = cur.right; 

4585 
else 

4586 
{ 

4587 
result = cur; 

4588 
cur = cur.left; 

4589 
} 

4590 


4591 
} 

4592 
return result; 

4593 
} 

4594 


4595 
/** 

4596 
* Get a range from the container with all elements that are > e according 

4597 
* to the less comparator 

4598 
* 

4599 
* Complexity: $(BIGOH log(n)) 

4600 
*/ 

4601 
Range upperBound(Elem e) 

4602 
{ 

4603 
return Range(_firstGreater(e), _end); 

4604 
} 

4605 


4606 
/** 

4607 
* Get a range from the container with all elements that are < e according 

4608 
* to the less comparator 

4609 
* 

4610 
* Complexity: $(BIGOH log(n)) 

4611 
*/ 

4612 
Range lowerBound(Elem e) 

4613 
{ 

4614 
return Range(_end.leftmost, _firstGreaterEqual(e)); 

4615 
} 

4616 


4617 
/** 

4618 
* Get a range from the container with all elements that are == e according 

4619 
* to the less comparator 

4620 
* 

4621 
* Complexity: $(BIGOH log(n)) 

4622 
*/ 

4623 
Range equalRange(Elem e) 

4624 
{ 

4625 
auto beg = _firstGreaterEqual(e); 

4626 
if(beg is _end  _less(e, beg.value)) 

4627 
// no values are equal 

4628 
return Range(beg, beg); 

4629 
static if(allowDuplicates) 

4630 
{ 

4631 
return Range(beg, _firstGreater(e)); 

4632 
} 

4633 
else 

4634 
{ 

4635 
// no sense in doing a full search, no duplicates are allowed, 

4636 
// so we just get the next node. 

4637 
return Range(beg, beg.next); 

4638 
} 

4639 
} 

4640 


4641 
static if(doUnittest) unittest 

4642 
{ 

4643 
auto ts = create(1, 2, 3, 4, 5); 

4644 
auto r1 = ts.lowerBound(3); 

4645 
assert(std.algorithm.equal(r1, [1,2])); 

4646 
auto r2 = ts.upperBound(3); 

4647 
assert(std.algorithm.equal(r2, [4,5])); 

4648 
auto r3 = ts.equalRange(3); 

4649 
assert(std.algorithm.equal(r3, [3])); 

4650 
} 

4651 


4652 
version(RBDoChecks) 

4653 
{ 

4654 
/** 

4655 
* Print the tree. This prints a sideways view of the tree in ASCII form, 

4656 
* with the number of indentations representing the level of the nodes. 

4657 
* It does not print values, only the tree structure and color of nodes. 

4658 
*/ 

4659 
void printTree(Node n, int indent = 0) 

4660 
{ 

4661 
if(n !is null) 

4662 
{ 

4663 
printTree(n.right, indent + 2); 

4664 
for(int i = 0; i < indent; i++) 

4665 
write("."); 

4666 
writeln(n.color == n.color.Black ? "B" : "R"); 

4667 
printTree(n.left, indent + 2); 

4668 
} 

4669 
else 

4670 
{ 

4671 
for(int i = 0; i < indent; i++) 

4672 
write("."); 

4673 
writeln("N"); 

4674 
} 

4675 
if(indent is 0) 

4676 
writeln(); 

4677 
} 

4678 


4679 
/** 

4680 
* Check the tree for validity. This is called after every add or remove. 

4681 
* This should only be enabled to debug the implementation of the RB Tree. 

4682 
*/ 

4683 
void check() 

4684 
{ 

4685 
// 

4686 
// check implementation of the tree 

4687 
// 

4688 
int recurse(Node n, string path) 

4689 
{ 

4690 
if(n is null) 

4691 
return 1; 

4692 
if(n.parent.left !is n && n.parent.right !is n) 

4693 
throw new Exception("Node at path " ~ path ~ " has inconsistent pointers"); 

4694 
Node next = n.next; 

4695 
static if(allowDuplicates) 

4696 
{ 

4697 
if(next !is _end && _less(next.value, n.value)) 

4698 
throw new Exception("ordering invalid at path " ~ path); 

4699 
} 

4700 
else 

4701 
{ 

4702 
if(next !is _end && !_less(n.value, next.value)) 

4703 
throw new Exception("ordering invalid at path " ~ path); 

4704 
} 

4705 
if(n.color == n.color.Red) 

4706 
{ 

4707 
if((n.left !is null && n.left.color == n.color.Red)  

4708 
(n.right !is null && n.right.color == n.color.Red)) 

4709 
throw new Exception("Node at path " ~ path ~ " is red with a red child"); 

4710 
} 

4711 


4712 
int l = recurse(n.left, path ~ "L"); 

4713 
int r = recurse(n.right, path ~ "R"); 

4714 
if(l != r) 

4715 
{ 

4716 
writeln("bad tree at:"); 

4717 
printTree(n); 

4718 
throw new Exception("Node at path " ~ path ~ " has different number of black nodes on left and right paths"); 

4719 
} 

4720 
return l + (n.color == n.color.Black ? 1 : 0); 

4721 
} 

4722 


4723 
try 

4724 
{ 

4725 
recurse(_end.left, ""); 

4726 
} 

4727 
catch(Exception e) 

4728 
{ 

4729 
printTree(_end.left, 0); 

4730 
throw e; 

4731 
} 

4732 
} 

4733 
} 

4734 


4735 
/** 

4736 
* Constructor. Pass in an array of elements, or individual elements to 

4737 
* initialize the tree with. 

4738 
*/ 

4739 
this(U)(U[] elems...) if (isImplicitlyConvertible!(U, Elem)) 

4740 
{ 

4741 
_setup(); 

4742 
stableInsert(elems); 

4743 
} 

4744 


4745 
/** 

4746 
* Constructor. Pass in a range of elements to initialize the tree with. 

4747 
*/ 

4748 
this(Stuff)(Stuff stuff) if (isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, Elem) && !is(Stuff == Elem[])) 

4749 
{ 

4750 
_setup(); 

4751 
stableInsert(stuff); 

4752 
} 

4753 


4754 
} 

4755 


4756 
unittest 

4757 
{ 

4758 
RedBlackTree!uint rt1; 

4759 
RedBlackTree!int rt2; 

4760 
RedBlackTree!ushort rt3; 

4761 
RedBlackTree!short rt4; 

4762 
RedBlackTree!ubyte rt5; 

4763 
RedBlackTree!byte rt6; 

4764 
} 

4765 


4766 
version(unittest) struct UnittestMe { 

4767 
int a; 

4768 
} 

4769 


4770 
unittest 

4771 
{ 

4772 
auto c = Array!UnittestMe(); 

4773 
} 
