]>
Commit | Line | Data |
---|---|---|
b4c522fa IB |
1 | /** |
2 | This module implements a red-black tree container. | |
3 | ||
4 | This module is a submodule of $(MREF std, container). | |
5 | ||
6 | Source: $(PHOBOSSRC std/container/_rbtree.d) | |
7 | ||
8 | Copyright: Red-black tree code copyright (C) 2008- by Steven Schveighoffer. Other code | |
9 | copyright 2010- Andrei Alexandrescu. All rights reserved by the respective holders. | |
10 | ||
11 | License: Distributed under the Boost Software License, Version 1.0. | |
12 | (See accompanying file LICENSE_1_0.txt or copy at $(HTTP | |
13 | boost.org/LICENSE_1_0.txt)). | |
14 | ||
15 | Authors: Steven Schveighoffer, $(HTTP erdani.com, Andrei Alexandrescu) | |
16 | */ | |
17 | module std.container.rbtree; | |
18 | ||
19 | /// | |
20 | @safe pure unittest | |
21 | { | |
22 | import std.algorithm.comparison : equal; | |
23 | import std.container.rbtree; | |
24 | ||
25 | auto rbt = redBlackTree(3, 1, 4, 2, 5); | |
26 | assert(rbt.front == 1); | |
27 | assert(equal(rbt[], [1, 2, 3, 4, 5])); | |
28 | ||
29 | rbt.removeKey(1, 4); | |
30 | assert(equal(rbt[], [2, 3, 5])); | |
31 | ||
32 | rbt.removeFront(); | |
33 | assert(equal(rbt[], [3, 5])); | |
34 | ||
35 | rbt.insert([1, 2, 4]); | |
36 | assert(equal(rbt[], [1, 2, 3, 4, 5])); | |
37 | ||
38 | // Query bounds in O(log(n)) | |
39 | assert(rbt.lowerBound(3).equal([1, 2])); | |
40 | assert(rbt.equalRange(3).equal([3])); | |
41 | assert(rbt.upperBound(3).equal([4, 5])); | |
42 | ||
43 | // A Red Black tree with the highest element at front: | |
44 | import std.range : iota; | |
45 | auto maxTree = redBlackTree!"a > b"(iota(5)); | |
46 | assert(equal(maxTree[], [4, 3, 2, 1, 0])); | |
47 | ||
48 | // adding duplicates will not add them, but return 0 | |
49 | auto rbt2 = redBlackTree(1, 3); | |
50 | assert(rbt2.insert(1) == 0); | |
51 | assert(equal(rbt2[], [1, 3])); | |
52 | assert(rbt2.insert(2) == 1); | |
53 | ||
54 | // however you can allow duplicates | |
55 | auto ubt = redBlackTree!true([0, 1, 0, 1]); | |
56 | assert(equal(ubt[], [0, 0, 1, 1])); | |
57 | } | |
58 | ||
59 | import std.format; | |
60 | import std.functional : binaryFun; | |
61 | ||
62 | public import std.container.util; | |
63 | ||
64 | version (unittest) debug = RBDoChecks; | |
65 | ||
66 | //debug = RBDoChecks; | |
67 | ||
68 | /* | |
69 | * Implementation for a Red Black node for use in a Red Black Tree (see below) | |
70 | * | |
71 | * this implementation assumes we have a marker Node that is the parent of the | |
72 | * root Node. This marker Node is not a valid Node, but marks the end of the | |
73 | * collection. The root is the left child of the marker Node, so it is always | |
74 | * last in the collection. The marker Node is passed in to the setColor | |
75 | * function, and the Node which has this Node as its parent is assumed to be | |
76 | * the root Node. | |
77 | * | |
78 | * A Red Black tree should have O(lg(n)) insertion, removal, and search time. | |
79 | */ | |
80 | struct RBNode(V) | |
81 | { | |
82 | /* | |
83 | * Convenience alias | |
84 | */ | |
85 | alias Node = RBNode*; | |
86 | ||
87 | private Node _left; | |
88 | private Node _right; | |
89 | private Node _parent; | |
90 | ||
91 | /** | |
92 | * The value held by this node | |
93 | */ | |
94 | V value; | |
95 | ||
96 | /** | |
97 | * Enumeration determining what color the node is. Null nodes are assumed | |
98 | * to be black. | |
99 | */ | |
100 | enum Color : byte | |
101 | { | |
102 | Red, | |
103 | Black | |
104 | } | |
105 | ||
106 | /** | |
107 | * The color of the node. | |
108 | */ | |
109 | Color color; | |
110 | ||
111 | /** | |
112 | * Get the left child | |
113 | */ | |
114 | @property inout(RBNode)* left() inout | |
115 | { | |
116 | return _left; | |
117 | } | |
118 | ||
119 | /** | |
120 | * Get the right child | |
121 | */ | |
122 | @property inout(RBNode)* right() inout | |
123 | { | |
124 | return _right; | |
125 | } | |
126 | ||
127 | /** | |
128 | * Get the parent | |
129 | */ | |
130 | @property inout(RBNode)* parent() inout | |
131 | { | |
132 | return _parent; | |
133 | } | |
134 | ||
135 | /** | |
136 | * Set the left child. Also updates the new child's parent node. This | |
137 | * does not update the previous child. | |
138 | * | |
139 | * Returns newNode | |
140 | */ | |
141 | @property Node left(Node newNode) | |
142 | { | |
143 | _left = newNode; | |
144 | if (newNode !is null) | |
145 | newNode._parent = &this; | |
146 | return newNode; | |
147 | } | |
148 | ||
149 | /** | |
150 | * Set the right child. Also updates the new child's parent node. This | |
151 | * does not update the previous child. | |
152 | * | |
153 | * Returns newNode | |
154 | */ | |
155 | @property Node right(Node newNode) | |
156 | { | |
157 | _right = newNode; | |
158 | if (newNode !is null) | |
159 | newNode._parent = &this; | |
160 | return newNode; | |
161 | } | |
162 | ||
163 | // assume _left is not null | |
164 | // | |
165 | // performs rotate-right operation, where this is T, _right is R, _left is | |
166 | // L, _parent is P: | |
167 | // | |
168 | // P P | |
169 | // | -> | | |
170 | // T L | |
171 | // / \ / \ | |
172 | // L R a T | |
173 | // / \ / \ | |
174 | // a b b R | |
175 | // | |
176 | /** | |
177 | * Rotate right. This performs the following operations: | |
178 | * - The left child becomes the parent of this node. | |
179 | * - This node becomes the new parent's right child. | |
180 | * - The old right child of the new parent becomes the left child of this | |
181 | * node. | |
182 | */ | |
183 | Node rotateR() | |
184 | in | |
185 | { | |
186 | assert(_left !is null); | |
187 | } | |
188 | body | |
189 | { | |
190 | // sets _left._parent also | |
191 | if (isLeftNode) | |
192 | parent.left = _left; | |
193 | else | |
194 | parent.right = _left; | |
195 | Node tmp = _left._right; | |
196 | ||
197 | // sets _parent also | |
198 | _left.right = &this; | |
199 | ||
200 | // sets tmp._parent also | |
201 | left = tmp; | |
202 | ||
203 | return &this; | |
204 | } | |
205 | ||
206 | // assumes _right is non null | |
207 | // | |
208 | // performs rotate-left operation, where this is T, _right is R, _left is | |
209 | // L, _parent is P: | |
210 | // | |
211 | // P P | |
212 | // | -> | | |
213 | // T R | |
214 | // / \ / \ | |
215 | // L R T b | |
216 | // / \ / \ | |
217 | // a b L a | |
218 | // | |
219 | /** | |
220 | * Rotate left. This performs the following operations: | |
221 | * - The right child becomes the parent of this node. | |
222 | * - This node becomes the new parent's left child. | |
223 | * - The old left child of the new parent becomes the right child of this | |
224 | * node. | |
225 | */ | |
226 | Node rotateL() | |
227 | in | |
228 | { | |
229 | assert(_right !is null); | |
230 | } | |
231 | body | |
232 | { | |
233 | // sets _right._parent also | |
234 | if (isLeftNode) | |
235 | parent.left = _right; | |
236 | else | |
237 | parent.right = _right; | |
238 | Node tmp = _right._left; | |
239 | ||
240 | // sets _parent also | |
241 | _right.left = &this; | |
242 | ||
243 | // sets tmp._parent also | |
244 | right = tmp; | |
245 | return &this; | |
246 | } | |
247 | ||
248 | ||
249 | /** | |
250 | * Returns true if this node is a left child. | |
251 | * | |
252 | * Note that this should always return a value because the root has a | |
253 | * parent which is the marker node. | |
254 | */ | |
255 | @property bool isLeftNode() const | |
256 | in | |
257 | { | |
258 | assert(_parent !is null); | |
259 | } | |
260 | body | |
261 | { | |
262 | return _parent._left is &this; | |
263 | } | |
264 | ||
265 | /** | |
266 | * Set the color of the node after it is inserted. This performs an | |
267 | * update to the whole tree, possibly rotating nodes to keep the Red-Black | |
268 | * properties correct. This is an O(lg(n)) operation, where n is the | |
269 | * number of nodes in the tree. | |
270 | * | |
271 | * end is the marker node, which is the parent of the topmost valid node. | |
272 | */ | |
273 | void setColor(Node end) | |
274 | { | |
275 | // test against the marker node | |
276 | if (_parent !is end) | |
277 | { | |
278 | if (_parent.color == Color.Red) | |
279 | { | |
280 | Node cur = &this; | |
281 | while (true) | |
282 | { | |
283 | // because root is always black, _parent._parent always exists | |
284 | if (cur._parent.isLeftNode) | |
285 | { | |
286 | // parent is left node, y is 'uncle', could be null | |
287 | Node y = cur._parent._parent._right; | |
288 | if (y !is null && y.color == Color.Red) | |
289 | { | |
290 | cur._parent.color = Color.Black; | |
291 | y.color = Color.Black; | |
292 | cur = cur._parent._parent; | |
293 | if (cur._parent is end) | |
294 | { | |
295 | // root node | |
296 | cur.color = Color.Black; | |
297 | break; | |
298 | } | |
299 | else | |
300 | { | |
301 | // not root node | |
302 | cur.color = Color.Red; | |
303 | if (cur._parent.color == Color.Black) | |
304 | // satisfied, exit the loop | |
305 | break; | |
306 | } | |
307 | } | |
308 | else | |
309 | { | |
310 | if (!cur.isLeftNode) | |
311 | cur = cur._parent.rotateL(); | |
312 | cur._parent.color = Color.Black; | |
313 | cur = cur._parent._parent.rotateR(); | |
314 | cur.color = Color.Red; | |
315 | // tree should be satisfied now | |
316 | break; | |
317 | } | |
318 | } | |
319 | else | |
320 | { | |
321 | // parent is right node, y is 'uncle' | |
322 | Node y = cur._parent._parent._left; | |
323 | if (y !is null && y.color == Color.Red) | |
324 | { | |
325 | cur._parent.color = Color.Black; | |
326 | y.color = Color.Black; | |
327 | cur = cur._parent._parent; | |
328 | if (cur._parent is end) | |
329 | { | |
330 | // root node | |
331 | cur.color = Color.Black; | |
332 | break; | |
333 | } | |
334 | else | |
335 | { | |
336 | // not root node | |
337 | cur.color = Color.Red; | |
338 | if (cur._parent.color == Color.Black) | |
339 | // satisfied, exit the loop | |
340 | break; | |
341 | } | |
342 | } | |
343 | else | |
344 | { | |
345 | if (cur.isLeftNode) | |
346 | cur = cur._parent.rotateR(); | |
347 | cur._parent.color = Color.Black; | |
348 | cur = cur._parent._parent.rotateL(); | |
349 | cur.color = Color.Red; | |
350 | // tree should be satisfied now | |
351 | break; | |
352 | } | |
353 | } | |
354 | } | |
355 | ||
356 | } | |
357 | } | |
358 | else | |
359 | { | |
360 | // | |
361 | // this is the root node, color it black | |
362 | // | |
363 | color = Color.Black; | |
364 | } | |
365 | } | |
366 | ||
367 | /** | |
368 | * Remove this node from the tree. The 'end' node is used as the marker | |
369 | * which is root's parent. Note that this cannot be null! | |
370 | * | |
371 | * Returns the next highest valued node in the tree after this one, or end | |
372 | * if this was the highest-valued node. | |
373 | */ | |
374 | Node remove(Node end) | |
375 | { | |
376 | // | |
377 | // remove this node from the tree, fixing the color if necessary. | |
378 | // | |
379 | Node x; | |
380 | Node ret = next; | |
381 | ||
382 | // if this node has 2 children | |
383 | if (_left !is null && _right !is null) | |
384 | { | |
385 | // | |
386 | // normally, we can just swap this node's and y's value, but | |
387 | // because an iterator could be pointing to y and we don't want to | |
388 | // disturb it, we swap this node and y's structure instead. This | |
389 | // can also be a benefit if the value of the tree is a large | |
390 | // struct, which takes a long time to copy. | |
391 | // | |
392 | Node yp, yl, yr; | |
393 | Node y = ret; // y = next | |
394 | yp = y._parent; | |
395 | yl = y._left; | |
396 | yr = y._right; | |
397 | auto yc = y.color; | |
398 | auto isyleft = y.isLeftNode; | |
399 | ||
400 | // | |
401 | // replace y's structure with structure of this node. | |
402 | // | |
403 | if (isLeftNode) | |
404 | _parent.left = y; | |
405 | else | |
406 | _parent.right = y; | |
407 | // | |
408 | // need special case so y doesn't point back to itself | |
409 | // | |
410 | y.left = _left; | |
411 | if (_right is y) | |
412 | y.right = &this; | |
413 | else | |
414 | y.right = _right; | |
415 | y.color = color; | |
416 | ||
417 | // | |
418 | // replace this node's structure with structure of y. | |
419 | // | |
420 | left = yl; | |
421 | right = yr; | |
422 | if (_parent !is y) | |
423 | { | |
424 | if (isyleft) | |
425 | yp.left = &this; | |
426 | else | |
427 | yp.right = &this; | |
428 | } | |
429 | color = yc; | |
430 | } | |
431 | ||
432 | // if this has less than 2 children, remove it | |
433 | if (_left !is null) | |
434 | x = _left; | |
435 | else | |
436 | x = _right; | |
437 | ||
438 | bool deferedUnlink = false; | |
439 | if (x is null) | |
440 | { | |
441 | // pretend this is a null node, defer unlinking the node | |
442 | x = &this; | |
443 | deferedUnlink = true; | |
444 | } | |
445 | else if (isLeftNode) | |
446 | _parent.left = x; | |
447 | else | |
448 | _parent.right = x; | |
449 | ||
450 | // if the color of this is black, then it needs to be fixed | |
451 | if (color == color.Black) | |
452 | { | |
453 | // need to recolor the tree. | |
454 | while (x._parent !is end && x.color == Node.Color.Black) | |
455 | { | |
456 | if (x.isLeftNode) | |
457 | { | |
458 | // left node | |
459 | Node w = x._parent._right; | |
460 | if (w.color == Node.Color.Red) | |
461 | { | |
462 | w.color = Node.Color.Black; | |
463 | x._parent.color = Node.Color.Red; | |
464 | x._parent.rotateL(); | |
465 | w = x._parent._right; | |
466 | } | |
467 | Node wl = w.left; | |
468 | Node wr = w.right; | |
469 | if ((wl is null || wl.color == Node.Color.Black) && | |
470 | (wr is null || wr.color == Node.Color.Black)) | |
471 | { | |
472 | w.color = Node.Color.Red; | |
473 | x = x._parent; | |
474 | } | |
475 | else | |
476 | { | |
477 | if (wr is null || wr.color == Node.Color.Black) | |
478 | { | |
479 | // wl cannot be null here | |
480 | wl.color = Node.Color.Black; | |
481 | w.color = Node.Color.Red; | |
482 | w.rotateR(); | |
483 | w = x._parent._right; | |
484 | } | |
485 | ||
486 | w.color = x._parent.color; | |
487 | x._parent.color = Node.Color.Black; | |
488 | w._right.color = Node.Color.Black; | |
489 | x._parent.rotateL(); | |
490 | x = end.left; // x = root | |
491 | } | |
492 | } | |
493 | else | |
494 | { | |
495 | // right node | |
496 | Node w = x._parent._left; | |
497 | if (w.color == Node.Color.Red) | |
498 | { | |
499 | w.color = Node.Color.Black; | |
500 | x._parent.color = Node.Color.Red; | |
501 | x._parent.rotateR(); | |
502 | w = x._parent._left; | |
503 | } | |
504 | Node wl = w.left; | |
505 | Node wr = w.right; | |
506 | if ((wl is null || wl.color == Node.Color.Black) && | |
507 | (wr is null || wr.color == Node.Color.Black)) | |
508 | { | |
509 | w.color = Node.Color.Red; | |
510 | x = x._parent; | |
511 | } | |
512 | else | |
513 | { | |
514 | if (wl is null || wl.color == Node.Color.Black) | |
515 | { | |
516 | // wr cannot be null here | |
517 | wr.color = Node.Color.Black; | |
518 | w.color = Node.Color.Red; | |
519 | w.rotateL(); | |
520 | w = x._parent._left; | |
521 | } | |
522 | ||
523 | w.color = x._parent.color; | |
524 | x._parent.color = Node.Color.Black; | |
525 | w._left.color = Node.Color.Black; | |
526 | x._parent.rotateR(); | |
527 | x = end.left; // x = root | |
528 | } | |
529 | } | |
530 | } | |
531 | x.color = Node.Color.Black; | |
532 | } | |
533 | ||
534 | if (deferedUnlink) | |
535 | { | |
536 | // | |
537 | // unlink this node from the tree | |
538 | // | |
539 | if (isLeftNode) | |
540 | _parent.left = null; | |
541 | else | |
542 | _parent.right = null; | |
543 | } | |
544 | ||
545 | // clean references to help GC - Bugzilla 12915 | |
546 | _left = _right = _parent = null; | |
547 | ||
548 | return ret; | |
549 | } | |
550 | ||
551 | /** | |
552 | * Return the leftmost descendant of this node. | |
553 | */ | |
554 | @property inout(RBNode)* leftmost() inout | |
555 | { | |
556 | inout(RBNode)* result = &this; | |
557 | while (result._left !is null) | |
558 | result = result._left; | |
559 | return result; | |
560 | } | |
561 | ||
562 | /** | |
563 | * Return the rightmost descendant of this node | |
564 | */ | |
565 | @property inout(RBNode)* rightmost() inout | |
566 | { | |
567 | inout(RBNode)* result = &this; | |
568 | while (result._right !is null) | |
569 | result = result._right; | |
570 | return result; | |
571 | } | |
572 | ||
573 | /** | |
574 | * Returns the next valued node in the tree. | |
575 | * | |
576 | * You should never call this on the marker node, as it is assumed that | |
577 | * there is a valid next node. | |
578 | */ | |
579 | @property inout(RBNode)* next() inout | |
580 | { | |
581 | inout(RBNode)* n = &this; | |
582 | if (n.right is null) | |
583 | { | |
584 | while (!n.isLeftNode) | |
585 | n = n._parent; | |
586 | return n._parent; | |
587 | } | |
588 | else | |
589 | return n.right.leftmost; | |
590 | } | |
591 | ||
592 | /** | |
593 | * Returns the previous valued node in the tree. | |
594 | * | |
595 | * You should never call this on the leftmost node of the tree as it is | |
596 | * assumed that there is a valid previous node. | |
597 | */ | |
598 | @property inout(RBNode)* prev() inout | |
599 | { | |
600 | inout(RBNode)* n = &this; | |
601 | if (n.left is null) | |
602 | { | |
603 | while (n.isLeftNode) | |
604 | n = n._parent; | |
605 | return n._parent; | |
606 | } | |
607 | else | |
608 | return n.left.rightmost; | |
609 | } | |
610 | ||
611 | Node dup(scope Node delegate(V v) alloc) | |
612 | { | |
613 | // | |
614 | // duplicate this and all child nodes | |
615 | // | |
616 | // The recursion should be lg(n), so we shouldn't have to worry about | |
617 | // stack size. | |
618 | // | |
619 | Node copy = alloc(value); | |
620 | copy.color = color; | |
621 | if (_left !is null) | |
622 | copy.left = _left.dup(alloc); | |
623 | if (_right !is null) | |
624 | copy.right = _right.dup(alloc); | |
625 | return copy; | |
626 | } | |
627 | ||
628 | Node dup() | |
629 | { | |
630 | Node copy = new RBNode!V(null, null, null, value); | |
631 | copy.color = color; | |
632 | if (_left !is null) | |
633 | copy.left = _left.dup(); | |
634 | if (_right !is null) | |
635 | copy.right = _right.dup(); | |
636 | return copy; | |
637 | } | |
638 | } | |
639 | ||
640 | //constness checks | |
641 | @safe pure unittest | |
642 | { | |
643 | const RBNode!int n; | |
644 | static assert(is(typeof(n.leftmost))); | |
645 | static assert(is(typeof(n.rightmost))); | |
646 | static assert(is(typeof(n.next))); | |
647 | static assert(is(typeof(n.prev))); | |
648 | } | |
649 | ||
650 | private struct RBRange(N) | |
651 | { | |
652 | alias Node = N; | |
653 | alias Elem = typeof(Node.value); | |
654 | ||
655 | private Node _begin; | |
656 | private Node _end; | |
657 | ||
658 | private this(Node b, Node e) | |
659 | { | |
660 | _begin = b; | |
661 | _end = e; | |
662 | } | |
663 | ||
664 | /** | |
665 | * Returns $(D true) if the range is _empty | |
666 | */ | |
667 | @property bool empty() const | |
668 | { | |
669 | return _begin is _end; | |
670 | } | |
671 | ||
672 | /** | |
673 | * Returns the first element in the range | |
674 | */ | |
675 | @property Elem front() | |
676 | { | |
677 | return _begin.value; | |
678 | } | |
679 | ||
680 | /** | |
681 | * Returns the last element in the range | |
682 | */ | |
683 | @property Elem back() | |
684 | { | |
685 | return _end.prev.value; | |
686 | } | |
687 | ||
688 | /** | |
689 | * pop the front element from the range | |
690 | * | |
691 | * Complexity: amortized $(BIGOH 1) | |
692 | */ | |
693 | void popFront() | |
694 | { | |
695 | _begin = _begin.next; | |
696 | } | |
697 | ||
698 | /** | |
699 | * pop the back element from the range | |
700 | * | |
701 | * Complexity: amortized $(BIGOH 1) | |
702 | */ | |
703 | void popBack() | |
704 | { | |
705 | _end = _end.prev; | |
706 | } | |
707 | ||
708 | /** | |
709 | * Trivial _save implementation, needed for $(D isForwardRange). | |
710 | */ | |
711 | @property RBRange save() | |
712 | { | |
713 | return this; | |
714 | } | |
715 | } | |
716 | ||
717 | /** | |
718 | * Implementation of a $(LINK2 https://en.wikipedia.org/wiki/Red%E2%80%93black_tree, | |
719 | * red-black tree) container. | |
720 | * | |
721 | * All inserts, removes, searches, and any function in general has complexity | |
722 | * of $(BIGOH lg(n)). | |
723 | * | |
724 | * To use a different comparison than $(D "a < b"), pass a different operator string | |
725 | * that can be used by $(REF binaryFun, std,functional), or pass in a | |
726 | * function, delegate, functor, or any type where $(D less(a, b)) results in a $(D bool) | |
727 | * value. | |
728 | * | |
729 | * Note that less should produce a strict ordering. That is, for two unequal | |
730 | * elements $(D a) and $(D b), $(D less(a, b) == !less(b, a)). $(D less(a, a)) should | |
731 | * always equal $(D false). | |
732 | * | |
733 | * If $(D allowDuplicates) is set to $(D true), then inserting the same element more than | |
734 | * once continues to add more elements. If it is $(D false), duplicate elements are | |
735 | * ignored on insertion. If duplicates are allowed, then new elements are | |
736 | * inserted after all existing duplicate elements. | |
737 | */ | |
738 | final class RedBlackTree(T, alias less = "a < b", bool allowDuplicates = false) | |
739 | if (is(typeof(binaryFun!less(T.init, T.init)))) | |
740 | { | |
741 | import std.meta : allSatisfy; | |
742 | import std.range : Take; | |
743 | import std.range.primitives : isInputRange, walkLength; | |
744 | import std.traits : isIntegral, isDynamicArray, isImplicitlyConvertible; | |
745 | ||
746 | alias _less = binaryFun!less; | |
747 | ||
748 | version (unittest) | |
749 | { | |
750 | static if (is(typeof(less) == string)) | |
751 | { | |
752 | private enum doUnittest = isIntegral!T && (less == "a < b" || less == "a > b"); | |
753 | } | |
754 | else | |
755 | enum doUnittest = false; | |
756 | ||
757 | // note, this must be final so it does not affect the vtable layout | |
758 | bool arrayEqual(T[] arr) | |
759 | { | |
760 | if (walkLength(this[]) == arr.length) | |
761 | { | |
762 | foreach (v; arr) | |
763 | { | |
764 | if (!(v in this)) | |
765 | return false; | |
766 | } | |
767 | return true; | |
768 | } | |
769 | return false; | |
770 | } | |
771 | } | |
772 | else | |
773 | { | |
774 | private enum doUnittest = false; | |
775 | } | |
776 | ||
777 | /** | |
778 | * Element type for the tree | |
779 | */ | |
780 | alias Elem = T; | |
781 | ||
782 | // used for convenience | |
783 | private alias RBNode = .RBNode!Elem; | |
784 | private alias Node = RBNode.Node; | |
785 | ||
786 | private Node _end; | |
787 | private Node _begin; | |
788 | private size_t _length; | |
789 | ||
790 | private void _setup() | |
791 | { | |
792 | assert(!_end); //Make sure that _setup isn't run more than once. | |
793 | _begin = _end = allocate(); | |
794 | } | |
795 | ||
796 | static private Node allocate() | |
797 | { | |
798 | return new RBNode; | |
799 | } | |
800 | ||
801 | static private Node allocate(Elem v) | |
802 | { | |
803 | return new RBNode(null, null, null, v); | |
804 | } | |
805 | ||
806 | /** | |
807 | * The range types for $(D RedBlackTree) | |
808 | */ | |
809 | alias Range = RBRange!(RBNode*); | |
810 | alias ConstRange = RBRange!(const(RBNode)*); /// Ditto | |
811 | alias ImmutableRange = RBRange!(immutable(RBNode)*); /// Ditto | |
812 | ||
813 | static if (doUnittest) @safe pure unittest | |
814 | { | |
815 | import std.algorithm.comparison : equal; | |
816 | import std.range.primitives; | |
817 | auto ts = new RedBlackTree(1, 2, 3, 4, 5); | |
818 | assert(ts.length == 5); | |
819 | auto r = ts[]; | |
820 | ||
821 | static if (less == "a < b") | |
822 | auto vals = [1, 2, 3, 4, 5]; | |
823 | else | |
824 | auto vals = [5, 4, 3, 2, 1]; | |
825 | assert(equal(r, vals)); | |
826 | ||
827 | assert(r.front == vals.front); | |
828 | assert(r.back != r.front); | |
829 | auto oldfront = r.front; | |
830 | auto oldback = r.back; | |
831 | r.popFront(); | |
832 | r.popBack(); | |
833 | assert(r.front != r.back); | |
834 | assert(r.front != oldfront); | |
835 | assert(r.back != oldback); | |
836 | assert(ts.length == 5); | |
837 | } | |
838 | ||
839 | // find a node based on an element value | |
840 | private inout(RBNode)* _find(Elem e) inout | |
841 | { | |
842 | static if (allowDuplicates) | |
843 | { | |
844 | inout(RBNode)* cur = _end.left; | |
845 | inout(RBNode)* result = null; | |
846 | while (cur) | |
847 | { | |
848 | if (_less(cur.value, e)) | |
849 | cur = cur.right; | |
850 | else if (_less(e, cur.value)) | |
851 | cur = cur.left; | |
852 | else | |
853 | { | |
854 | // want to find the left-most element | |
855 | result = cur; | |
856 | cur = cur.left; | |
857 | } | |
858 | } | |
859 | return result; | |
860 | } | |
861 | else | |
862 | { | |
863 | inout(RBNode)* cur = _end.left; | |
864 | while (cur) | |
865 | { | |
866 | if (_less(cur.value, e)) | |
867 | cur = cur.right; | |
868 | else if (_less(e, cur.value)) | |
869 | cur = cur.left; | |
870 | else | |
871 | return cur; | |
872 | } | |
873 | return null; | |
874 | } | |
875 | } | |
876 | ||
877 | // add an element to the tree, returns the node added, or the existing node | |
878 | // if it has already been added and allowDuplicates is false | |
879 | private auto _add(Elem n) | |
880 | { | |
881 | Node result; | |
882 | static if (!allowDuplicates) | |
883 | bool added = true; | |
884 | ||
885 | if (!_end.left) | |
886 | { | |
887 | _end.left = _begin = result = allocate(n); | |
888 | } | |
889 | else | |
890 | { | |
891 | Node newParent = _end.left; | |
892 | Node nxt; | |
893 | while (true) | |
894 | { | |
895 | if (_less(n, newParent.value)) | |
896 | { | |
897 | nxt = newParent.left; | |
898 | if (nxt is null) | |
899 | { | |
900 | // | |
901 | // add to right of new parent | |
902 | // | |
903 | newParent.left = result = allocate(n); | |
904 | break; | |
905 | } | |
906 | } | |
907 | else | |
908 | { | |
909 | static if (!allowDuplicates) | |
910 | { | |
911 | if (!_less(newParent.value, n)) | |
912 | { | |
913 | result = newParent; | |
914 | added = false; | |
915 | break; | |
916 | } | |
917 | } | |
918 | nxt = newParent.right; | |
919 | if (nxt is null) | |
920 | { | |
921 | // | |
922 | // add to right of new parent | |
923 | // | |
924 | newParent.right = result = allocate(n); | |
925 | break; | |
926 | } | |
927 | } | |
928 | newParent = nxt; | |
929 | } | |
930 | if (_begin.left) | |
931 | _begin = _begin.left; | |
932 | } | |
933 | ||
934 | static if (allowDuplicates) | |
935 | { | |
936 | result.setColor(_end); | |
937 | debug(RBDoChecks) | |
938 | check(); | |
939 | ++_length; | |
940 | return result; | |
941 | } | |
942 | else | |
943 | { | |
944 | import std.typecons : Tuple; | |
945 | ||
946 | if (added) | |
947 | { | |
948 | ++_length; | |
949 | result.setColor(_end); | |
950 | } | |
951 | debug(RBDoChecks) | |
952 | check(); | |
953 | return Tuple!(bool, "added", Node, "n")(added, result); | |
954 | } | |
955 | } | |
956 | ||
957 | ||
958 | /** | |
959 | * Check if any elements exist in the container. Returns $(D false) if at least | |
960 | * one element exists. | |
961 | */ | |
962 | @property bool empty() | |
963 | { | |
964 | return _end.left is null; | |
965 | } | |
966 | ||
967 | /++ | |
968 | Returns the number of elements in the container. | |
969 | ||
970 | Complexity: $(BIGOH 1). | |
971 | +/ | |
972 | @property size_t length() const | |
973 | { | |
974 | return _length; | |
975 | } | |
976 | ||
977 | /** | |
978 | * Duplicate this container. The resulting container contains a shallow | |
979 | * copy of the elements. | |
980 | * | |
981 | * Complexity: $(BIGOH n) | |
982 | */ | |
983 | @property RedBlackTree dup() | |
984 | { | |
985 | return new RedBlackTree(_end.dup(), _length); | |
986 | } | |
987 | ||
988 | static if (doUnittest) @safe pure unittest | |
989 | { | |
990 | import std.algorithm.comparison : equal; | |
991 | auto ts = new RedBlackTree(1, 2, 3, 4, 5); | |
992 | assert(ts.length == 5); | |
993 | auto ts2 = ts.dup; | |
994 | assert(ts2.length == 5); | |
995 | assert(equal(ts[], ts2[])); | |
996 | ts2.insert(cast(Elem) 6); | |
997 | assert(!equal(ts[], ts2[])); | |
998 | assert(ts.length == 5 && ts2.length == 6); | |
999 | } | |
1000 | ||
1001 | /** | |
1002 | * Fetch a range that spans all the elements in the container. | |
1003 | * | |
1004 | * Complexity: $(BIGOH 1) | |
1005 | */ | |
1006 | Range opSlice() | |
1007 | { | |
1008 | return Range(_begin, _end); | |
1009 | } | |
1010 | ||
1011 | /// Ditto | |
1012 | ConstRange opSlice() const | |
1013 | { | |
1014 | return ConstRange(_begin, _end); | |
1015 | } | |
1016 | ||
1017 | /// Ditto | |
1018 | ImmutableRange opSlice() immutable | |
1019 | { | |
1020 | return ImmutableRange(_begin, _end); | |
1021 | } | |
1022 | ||
1023 | /** | |
1024 | * The front element in the container | |
1025 | * | |
1026 | * Complexity: $(BIGOH 1) | |
1027 | */ | |
1028 | Elem front() | |
1029 | { | |
1030 | return _begin.value; | |
1031 | } | |
1032 | ||
1033 | /** | |
1034 | * The last element in the container | |
1035 | * | |
1036 | * Complexity: $(BIGOH log(n)) | |
1037 | */ | |
1038 | Elem back() | |
1039 | { | |
1040 | return _end.prev.value; | |
1041 | } | |
1042 | ||
1043 | /++ | |
1044 | $(D in) operator. Check to see if the given element exists in the | |
1045 | container. | |
1046 | ||
1047 | Complexity: $(BIGOH log(n)) | |
1048 | +/ | |
1049 | bool opBinaryRight(string op)(Elem e) const if (op == "in") | |
1050 | { | |
1051 | return _find(e) !is null; | |
1052 | } | |
1053 | ||
1054 | static if (doUnittest) @safe pure unittest | |
1055 | { | |
1056 | auto ts = new RedBlackTree(1, 2, 3, 4, 5); | |
1057 | assert(cast(Elem) 3 in ts); | |
1058 | assert(cast(Elem) 6 !in ts); | |
1059 | } | |
1060 | ||
1061 | /** | |
1062 | * Compares two trees for equality. | |
1063 | * | |
1064 | * Complexity: $(BIGOH n) | |
1065 | */ | |
1066 | override bool opEquals(Object rhs) | |
1067 | { | |
1068 | import std.algorithm.comparison : equal; | |
1069 | ||
1070 | RedBlackTree that = cast(RedBlackTree) rhs; | |
1071 | if (that is null) return false; | |
1072 | ||
1073 | // If there aren't the same number of nodes, we can't be equal. | |
1074 | if (this._length != that._length) return false; | |
1075 | ||
1076 | auto thisRange = this[]; | |
1077 | auto thatRange = that[]; | |
1078 | return equal!(function(Elem a, Elem b) => !_less(a,b) && !_less(b,a)) | |
1079 | (thisRange, thatRange); | |
1080 | } | |
1081 | ||
1082 | static if (doUnittest) @system unittest | |
1083 | { | |
1084 | auto t1 = new RedBlackTree(1,2,3,4); | |
1085 | auto t2 = new RedBlackTree(1,2,3,4); | |
1086 | auto t3 = new RedBlackTree(1,2,3,5); | |
1087 | auto t4 = new RedBlackTree(1,2,3,4,5); | |
1088 | auto o = new Object(); | |
1089 | ||
1090 | assert(t1 == t1); | |
1091 | assert(t1 == t2); | |
1092 | assert(t1 != t3); | |
1093 | assert(t1 != t4); | |
1094 | assert(t1 != o); // pathological case, must not crash | |
1095 | } | |
1096 | ||
1097 | /** | |
1098 | * Removes all elements from the container. | |
1099 | * | |
1100 | * Complexity: $(BIGOH 1) | |
1101 | */ | |
1102 | void clear() | |
1103 | { | |
1104 | _end.left = null; | |
1105 | _begin = _end; | |
1106 | _length = 0; | |
1107 | } | |
1108 | ||
1109 | static if (doUnittest) @safe pure unittest | |
1110 | { | |
1111 | auto ts = new RedBlackTree(1,2,3,4,5); | |
1112 | assert(ts.length == 5); | |
1113 | ts.clear(); | |
1114 | assert(ts.empty && ts.length == 0); | |
1115 | } | |
1116 | ||
1117 | /** | |
1118 | * Insert a single element in the container. Note that this does not | |
1119 | * invalidate any ranges currently iterating the container. | |
1120 | * | |
1121 | * Returns: The number of elements inserted. | |
1122 | * | |
1123 | * Complexity: $(BIGOH log(n)) | |
1124 | */ | |
1125 | size_t stableInsert(Stuff)(Stuff stuff) if (isImplicitlyConvertible!(Stuff, Elem)) | |
1126 | { | |
1127 | static if (allowDuplicates) | |
1128 | { | |
1129 | _add(stuff); | |
1130 | return 1; | |
1131 | } | |
1132 | else | |
1133 | { | |
1134 | return(_add(stuff).added ? 1 : 0); | |
1135 | } | |
1136 | } | |
1137 | ||
1138 | /** | |
1139 | * Insert a range of elements in the container. Note that this does not | |
1140 | * invalidate any ranges currently iterating the container. | |
1141 | * | |
1142 | * Returns: The number of elements inserted. | |
1143 | * | |
1144 | * Complexity: $(BIGOH m * log(n)) | |
1145 | */ | |
1146 | size_t stableInsert(Stuff)(Stuff stuff) if (isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, Elem)) | |
1147 | { | |
1148 | size_t result = 0; | |
1149 | static if (allowDuplicates) | |
1150 | { | |
1151 | foreach (e; stuff) | |
1152 | { | |
1153 | ++result; | |
1154 | _add(e); | |
1155 | } | |
1156 | } | |
1157 | else | |
1158 | { | |
1159 | foreach (e; stuff) | |
1160 | { | |
1161 | if (_add(e).added) | |
1162 | ++result; | |
1163 | } | |
1164 | } | |
1165 | return result; | |
1166 | } | |
1167 | ||
1168 | /// ditto | |
1169 | alias insert = stableInsert; | |
1170 | ||
1171 | static if (doUnittest) @safe pure unittest | |
1172 | { | |
1173 | auto ts = new RedBlackTree(2,1,3,4,5,2,5); | |
1174 | static if (allowDuplicates) | |
1175 | { | |
1176 | assert(ts.length == 7); | |
1177 | assert(ts.stableInsert(cast(Elem[])[7, 8, 6, 9, 10, 8]) == 6); | |
1178 | assert(ts.length == 13); | |
1179 | assert(ts.stableInsert(cast(Elem) 11) == 1 && ts.length == 14); | |
1180 | assert(ts.stableInsert(cast(Elem) 7) == 1 && ts.length == 15); | |
1181 | ||
1182 | static if (less == "a < b") | |
1183 | assert(ts.arrayEqual([1,2,2,3,4,5,5,6,7,7,8,8,9,10,11])); | |
1184 | else | |
1185 | assert(ts.arrayEqual([11,10,9,8,8,7,7,6,5,5,4,3,2,2,1])); | |
1186 | } | |
1187 | else | |
1188 | { | |
1189 | assert(ts.length == 5); | |
1190 | Elem[] elems = [7, 8, 6, 9, 10, 8]; | |
1191 | assert(ts.stableInsert(elems) == 5); | |
1192 | assert(ts.length == 10); | |
1193 | assert(ts.stableInsert(cast(Elem) 11) == 1 && ts.length == 11); | |
1194 | assert(ts.stableInsert(cast(Elem) 7) == 0 && ts.length == 11); | |
1195 | ||
1196 | static if (less == "a < b") | |
1197 | assert(ts.arrayEqual([1,2,3,4,5,6,7,8,9,10,11])); | |
1198 | else | |
1199 | assert(ts.arrayEqual([11,10,9,8,7,6,5,4,3,2,1])); | |
1200 | } | |
1201 | } | |
1202 | ||
1203 | /** | |
1204 | * Remove an element from the container and return its value. | |
1205 | * | |
1206 | * Complexity: $(BIGOH log(n)) | |
1207 | */ | |
1208 | Elem removeAny() | |
1209 | { | |
1210 | scope(success) | |
1211 | --_length; | |
1212 | auto n = _begin; | |
1213 | auto result = n.value; | |
1214 | _begin = n.remove(_end); | |
1215 | debug(RBDoChecks) | |
1216 | check(); | |
1217 | return result; | |
1218 | } | |
1219 | ||
1220 | static if (doUnittest) @safe pure unittest | |
1221 | { | |
1222 | auto ts = new RedBlackTree(1,2,3,4,5); | |
1223 | assert(ts.length == 5); | |
1224 | auto x = ts.removeAny(); | |
1225 | assert(ts.length == 4); | |
1226 | Elem[] arr; | |
1227 | foreach (Elem i; 1 .. 6) | |
1228 | if (i != x) arr ~= i; | |
1229 | assert(ts.arrayEqual(arr)); | |
1230 | } | |
1231 | ||
1232 | /** | |
1233 | * Remove the front element from the container. | |
1234 | * | |
1235 | * Complexity: $(BIGOH log(n)) | |
1236 | */ | |
1237 | void removeFront() | |
1238 | { | |
1239 | scope(success) | |
1240 | --_length; | |
1241 | _begin = _begin.remove(_end); | |
1242 | debug(RBDoChecks) | |
1243 | check(); | |
1244 | } | |
1245 | ||
1246 | /** | |
1247 | * Remove the back element from the container. | |
1248 | * | |
1249 | * Complexity: $(BIGOH log(n)) | |
1250 | */ | |
1251 | void removeBack() | |
1252 | { | |
1253 | scope(success) | |
1254 | --_length; | |
1255 | auto lastnode = _end.prev; | |
1256 | if (lastnode is _begin) | |
1257 | _begin = _begin.remove(_end); | |
1258 | else | |
1259 | lastnode.remove(_end); | |
1260 | debug(RBDoChecks) | |
1261 | check(); | |
1262 | } | |
1263 | ||
1264 | static if (doUnittest) @safe pure unittest | |
1265 | { | |
1266 | auto ts = new RedBlackTree(1,2,3,4,5); | |
1267 | assert(ts.length == 5); | |
1268 | ts.removeBack(); | |
1269 | assert(ts.length == 4); | |
1270 | ||
1271 | static if (less == "a < b") | |
1272 | assert(ts.arrayEqual([1,2,3,4])); | |
1273 | else | |
1274 | assert(ts.arrayEqual([2,3,4,5])); | |
1275 | ||
1276 | ts.removeFront(); | |
1277 | assert(ts.arrayEqual([2,3,4]) && ts.length == 3); | |
1278 | } | |
1279 | ||
1280 | /++ | |
1281 | Removes the given range from the container. | |
1282 | ||
1283 | Returns: A range containing all of the elements that were after the | |
1284 | given range. | |
1285 | ||
1286 | Complexity: $(BIGOH m * log(n)) (where m is the number of elements in | |
1287 | the range) | |
1288 | +/ | |
1289 | Range remove(Range r) | |
1290 | { | |
1291 | auto b = r._begin; | |
1292 | auto e = r._end; | |
1293 | if (_begin is b) | |
1294 | _begin = e; | |
1295 | while (b !is e) | |
1296 | { | |
1297 | b = b.remove(_end); | |
1298 | --_length; | |
1299 | } | |
1300 | debug(RBDoChecks) | |
1301 | check(); | |
1302 | return Range(e, _end); | |
1303 | } | |
1304 | ||
1305 | static if (doUnittest) @safe pure unittest | |
1306 | { | |
1307 | import std.algorithm.comparison : equal; | |
1308 | auto ts = new RedBlackTree(1,2,3,4,5); | |
1309 | assert(ts.length == 5); | |
1310 | auto r = ts[]; | |
1311 | r.popFront(); | |
1312 | r.popBack(); | |
1313 | assert(ts.length == 5); | |
1314 | auto r2 = ts.remove(r); | |
1315 | assert(ts.length == 2); | |
1316 | assert(ts.arrayEqual([1,5])); | |
1317 | ||
1318 | static if (less == "a < b") | |
1319 | assert(equal(r2, [5])); | |
1320 | else | |
1321 | assert(equal(r2, [1])); | |
1322 | } | |
1323 | ||
1324 | /++ | |
1325 | Removes the given $(D Take!Range) from the container | |
1326 | ||
1327 | Returns: A range containing all of the elements that were after the | |
1328 | given range. | |
1329 | ||
1330 | Complexity: $(BIGOH m * log(n)) (where m is the number of elements in | |
1331 | the range) | |
1332 | +/ | |
1333 | Range remove(Take!Range r) | |
1334 | { | |
1335 | immutable isBegin = (r.source._begin is _begin); | |
1336 | auto b = r.source._begin; | |
1337 | ||
1338 | while (!r.empty) | |
1339 | { | |
1340 | r.popFront(); | |
1341 | b = b.remove(_end); | |
1342 | --_length; | |
1343 | } | |
1344 | ||
1345 | if (isBegin) | |
1346 | _begin = b; | |
1347 | ||
1348 | return Range(b, _end); | |
1349 | } | |
1350 | ||
1351 | static if (doUnittest) @safe pure unittest | |
1352 | { | |
1353 | import std.algorithm.comparison : equal; | |
1354 | import std.range : take; | |
1355 | auto ts = new RedBlackTree(1,2,3,4,5); | |
1356 | auto r = ts[]; | |
1357 | r.popFront(); | |
1358 | assert(ts.length == 5); | |
1359 | auto r2 = ts.remove(take(r, 0)); | |
1360 | ||
1361 | static if (less == "a < b") | |
1362 | { | |
1363 | assert(equal(r2, [2,3,4,5])); | |
1364 | auto r3 = ts.remove(take(r, 2)); | |
1365 | assert(ts.arrayEqual([1,4,5]) && ts.length == 3); | |
1366 | assert(equal(r3, [4,5])); | |
1367 | } | |
1368 | else | |
1369 | { | |
1370 | assert(equal(r2, [4,3,2,1])); | |
1371 | auto r3 = ts.remove(take(r, 2)); | |
1372 | assert(ts.arrayEqual([5,2,1]) && ts.length == 3); | |
1373 | assert(equal(r3, [2,1])); | |
1374 | } | |
1375 | } | |
1376 | ||
1377 | /++ | |
1378 | Removes elements from the container that are equal to the given values | |
1379 | according to the less comparator. One element is removed for each value | |
1380 | given which is in the container. If $(D allowDuplicates) is true, | |
1381 | duplicates are removed only if duplicate values are given. | |
1382 | ||
1383 | Returns: The number of elements removed. | |
1384 | ||
1385 | Complexity: $(BIGOH m log(n)) (where m is the number of elements to remove) | |
1386 | ||
1387 | Example: | |
1388 | -------------------- | |
1389 | auto rbt = redBlackTree!true(0, 1, 1, 1, 4, 5, 7); | |
1390 | rbt.removeKey(1, 4, 7); | |
1391 | assert(equal(rbt[], [0, 1, 1, 5])); | |
1392 | rbt.removeKey(1, 1, 0); | |
1393 | assert(equal(rbt[], [5])); | |
1394 | -------------------- | |
1395 | +/ | |
1396 | size_t removeKey(U...)(U elems) | |
1397 | if (allSatisfy!(isImplicitlyConvertibleToElem, U)) | |
1398 | { | |
1399 | Elem[U.length] toRemove = [elems]; | |
1400 | return removeKey(toRemove[]); | |
1401 | } | |
1402 | ||
1403 | /++ Ditto +/ | |
1404 | size_t removeKey(U)(U[] elems) | |
1405 | if (isImplicitlyConvertible!(U, Elem)) | |
1406 | { | |
1407 | immutable lenBefore = length; | |
1408 | ||
1409 | foreach (e; elems) | |
1410 | { | |
1411 | auto beg = _firstGreaterEqual(e); | |
1412 | if (beg is _end || _less(e, beg.value)) | |
1413 | // no values are equal | |
1414 | continue; | |
1415 | immutable isBegin = (beg is _begin); | |
1416 | beg = beg.remove(_end); | |
1417 | if (isBegin) | |
1418 | _begin = beg; | |
1419 | --_length; | |
1420 | } | |
1421 | ||
1422 | return lenBefore - length; | |
1423 | } | |
1424 | ||
1425 | /++ Ditto +/ | |
1426 | size_t removeKey(Stuff)(Stuff stuff) | |
1427 | if (isInputRange!Stuff && | |
1428 | isImplicitlyConvertible!(ElementType!Stuff, Elem) && | |
1429 | !isDynamicArray!Stuff) | |
1430 | { | |
1431 | import std.array : array; | |
1432 | //We use array in case stuff is a Range from this RedBlackTree - either | |
1433 | //directly or indirectly. | |
1434 | return removeKey(array(stuff)); | |
1435 | } | |
1436 | ||
1437 | //Helper for removeKey. | |
1438 | private template isImplicitlyConvertibleToElem(U) | |
1439 | { | |
1440 | enum isImplicitlyConvertibleToElem = isImplicitlyConvertible!(U, Elem); | |
1441 | } | |
1442 | ||
1443 | static if (doUnittest) @safe pure unittest | |
1444 | { | |
1445 | import std.algorithm.comparison : equal; | |
1446 | import std.range : take; | |
1447 | auto rbt = new RedBlackTree(5, 4, 3, 7, 2, 1, 7, 6, 2, 19, 45); | |
1448 | ||
1449 | //The cast(Elem) is because these tests are instantiated with a variety | |
1450 | //of numeric types, and the literals are all int, which is not always | |
1451 | //implicitly convertible to Elem (e.g. short). | |
1452 | static if (allowDuplicates) | |
1453 | { | |
1454 | assert(rbt.length == 11); | |
1455 | assert(rbt.removeKey(cast(Elem) 4) == 1 && rbt.length == 10); | |
1456 | assert(rbt.arrayEqual([1,2,2,3,5,6,7,7,19,45]) && rbt.length == 10); | |
1457 | ||
1458 | assert(rbt.removeKey(cast(Elem) 6, cast(Elem) 2, cast(Elem) 1) == 3); | |
1459 | assert(rbt.arrayEqual([2,3,5,7,7,19,45]) && rbt.length == 7); | |
1460 | ||
1461 | assert(rbt.removeKey(cast(Elem)(42)) == 0 && rbt.length == 7); | |
1462 | assert(rbt.removeKey(take(rbt[], 3)) == 3 && rbt.length == 4); | |
1463 | ||
1464 | static if (less == "a < b") | |
1465 | assert(equal(rbt[], [7,7,19,45])); | |
1466 | else | |
1467 | assert(equal(rbt[], [7,5,3,2])); | |
1468 | } | |
1469 | else | |
1470 | { | |
1471 | assert(rbt.length == 9); | |
1472 | assert(rbt.removeKey(cast(Elem) 4) == 1 && rbt.length == 8); | |
1473 | assert(rbt.arrayEqual([1,2,3,5,6,7,19,45])); | |
1474 | ||
1475 | assert(rbt.removeKey(cast(Elem) 6, cast(Elem) 2, cast(Elem) 1) == 3); | |
1476 | assert(rbt.arrayEqual([3,5,7,19,45]) && rbt.length == 5); | |
1477 | ||
1478 | assert(rbt.removeKey(cast(Elem)(42)) == 0 && rbt.length == 5); | |
1479 | assert(rbt.removeKey(take(rbt[], 3)) == 3 && rbt.length == 2); | |
1480 | ||
1481 | static if (less == "a < b") | |
1482 | assert(equal(rbt[], [19,45])); | |
1483 | else | |
1484 | assert(equal(rbt[], [5,3])); | |
1485 | } | |
1486 | } | |
1487 | ||
1488 | // find the first node where the value is > e | |
1489 | private inout(RBNode)* _firstGreater(Elem e) inout | |
1490 | { | |
1491 | // can't use _find, because we cannot return null | |
1492 | auto cur = _end.left; | |
1493 | inout(RBNode)* result = _end; | |
1494 | while (cur) | |
1495 | { | |
1496 | if (_less(e, cur.value)) | |
1497 | { | |
1498 | result = cur; | |
1499 | cur = cur.left; | |
1500 | } | |
1501 | else | |
1502 | cur = cur.right; | |
1503 | } | |
1504 | return result; | |
1505 | } | |
1506 | ||
1507 | // find the first node where the value is >= e | |
1508 | private inout(RBNode)* _firstGreaterEqual(Elem e) inout | |
1509 | { | |
1510 | // can't use _find, because we cannot return null. | |
1511 | auto cur = _end.left; | |
1512 | inout(RBNode)* result = _end; | |
1513 | while (cur) | |
1514 | { | |
1515 | if (_less(cur.value, e)) | |
1516 | cur = cur.right; | |
1517 | else | |
1518 | { | |
1519 | result = cur; | |
1520 | cur = cur.left; | |
1521 | } | |
1522 | ||
1523 | } | |
1524 | return result; | |
1525 | } | |
1526 | ||
1527 | /** | |
1528 | * Get a range from the container with all elements that are > e according | |
1529 | * to the less comparator | |
1530 | * | |
1531 | * Complexity: $(BIGOH log(n)) | |
1532 | */ | |
1533 | Range upperBound(Elem e) | |
1534 | { | |
1535 | return Range(_firstGreater(e), _end); | |
1536 | } | |
1537 | ||
1538 | /// Ditto | |
1539 | ConstRange upperBound(Elem e) const | |
1540 | { | |
1541 | return ConstRange(_firstGreater(e), _end); | |
1542 | } | |
1543 | ||
1544 | /// Ditto | |
1545 | ImmutableRange upperBound(Elem e) immutable | |
1546 | { | |
1547 | return ImmutableRange(_firstGreater(e), _end); | |
1548 | } | |
1549 | ||
1550 | /** | |
1551 | * Get a range from the container with all elements that are < e according | |
1552 | * to the less comparator | |
1553 | * | |
1554 | * Complexity: $(BIGOH log(n)) | |
1555 | */ | |
1556 | Range lowerBound(Elem e) | |
1557 | { | |
1558 | return Range(_begin, _firstGreaterEqual(e)); | |
1559 | } | |
1560 | ||
1561 | /// Ditto | |
1562 | ConstRange lowerBound(Elem e) const | |
1563 | { | |
1564 | return ConstRange(_begin, _firstGreaterEqual(e)); | |
1565 | } | |
1566 | ||
1567 | /// Ditto | |
1568 | ImmutableRange lowerBound(Elem e) immutable | |
1569 | { | |
1570 | return ImmutableRange(_begin, _firstGreaterEqual(e)); | |
1571 | } | |
1572 | ||
1573 | /** | |
1574 | * Get a range from the container with all elements that are == e according | |
1575 | * to the less comparator | |
1576 | * | |
1577 | * Complexity: $(BIGOH log(n)) | |
1578 | */ | |
1579 | auto equalRange(this This)(Elem e) | |
1580 | { | |
1581 | auto beg = _firstGreaterEqual(e); | |
1582 | alias RangeType = RBRange!(typeof(beg)); | |
1583 | if (beg is _end || _less(e, beg.value)) | |
1584 | // no values are equal | |
1585 | return RangeType(beg, beg); | |
1586 | static if (allowDuplicates) | |
1587 | { | |
1588 | return RangeType(beg, _firstGreater(e)); | |
1589 | } | |
1590 | else | |
1591 | { | |
1592 | // no sense in doing a full search, no duplicates are allowed, | |
1593 | // so we just get the next node. | |
1594 | return RangeType(beg, beg.next); | |
1595 | } | |
1596 | } | |
1597 | ||
1598 | static if (doUnittest) @safe pure unittest | |
1599 | { | |
1600 | import std.algorithm.comparison : equal; | |
1601 | auto ts = new RedBlackTree(1, 2, 3, 4, 5); | |
1602 | auto rl = ts.lowerBound(3); | |
1603 | auto ru = ts.upperBound(3); | |
1604 | auto re = ts.equalRange(3); | |
1605 | ||
1606 | static if (less == "a < b") | |
1607 | { | |
1608 | assert(equal(rl, [1,2])); | |
1609 | assert(equal(ru, [4,5])); | |
1610 | } | |
1611 | else | |
1612 | { | |
1613 | assert(equal(rl, [5,4])); | |
1614 | assert(equal(ru, [2,1])); | |
1615 | } | |
1616 | ||
1617 | assert(equal(re, [3])); | |
1618 | } | |
1619 | ||
1620 | debug(RBDoChecks) | |
1621 | { | |
1622 | /* | |
1623 | * Print the tree. This prints a sideways view of the tree in ASCII form, | |
1624 | * with the number of indentations representing the level of the nodes. | |
1625 | * It does not print values, only the tree structure and color of nodes. | |
1626 | */ | |
1627 | void printTree(Node n, int indent = 0) | |
1628 | { | |
1629 | import std.stdio : write, writeln; | |
1630 | if (n !is null) | |
1631 | { | |
1632 | printTree(n.right, indent + 2); | |
1633 | for (int i = 0; i < indent; i++) | |
1634 | write("."); | |
1635 | writeln(n.color == n.color.Black ? "B" : "R"); | |
1636 | printTree(n.left, indent + 2); | |
1637 | } | |
1638 | else | |
1639 | { | |
1640 | for (int i = 0; i < indent; i++) | |
1641 | write("."); | |
1642 | writeln("N"); | |
1643 | } | |
1644 | if (indent is 0) | |
1645 | writeln(); | |
1646 | } | |
1647 | ||
1648 | /* | |
1649 | * Check the tree for validity. This is called after every add or remove. | |
1650 | * This should only be enabled to debug the implementation of the RB Tree. | |
1651 | */ | |
1652 | void check() | |
1653 | { | |
1654 | // | |
1655 | // check implementation of the tree | |
1656 | // | |
1657 | int recurse(Node n, string path) | |
1658 | { | |
1659 | import std.stdio : writeln; | |
1660 | if (n is null) | |
1661 | return 1; | |
1662 | if (n.parent.left !is n && n.parent.right !is n) | |
1663 | throw new Exception("Node at path " ~ path ~ " has inconsistent pointers"); | |
1664 | Node next = n.next; | |
1665 | static if (allowDuplicates) | |
1666 | { | |
1667 | if (next !is _end && _less(next.value, n.value)) | |
1668 | throw new Exception("ordering invalid at path " ~ path); | |
1669 | } | |
1670 | else | |
1671 | { | |
1672 | if (next !is _end && !_less(n.value, next.value)) | |
1673 | throw new Exception("ordering invalid at path " ~ path); | |
1674 | } | |
1675 | if (n.color == n.color.Red) | |
1676 | { | |
1677 | if ((n.left !is null && n.left.color == n.color.Red) || | |
1678 | (n.right !is null && n.right.color == n.color.Red)) | |
1679 | throw new Exception("Node at path " ~ path ~ " is red with a red child"); | |
1680 | } | |
1681 | ||
1682 | int l = recurse(n.left, path ~ "L"); | |
1683 | int r = recurse(n.right, path ~ "R"); | |
1684 | if (l != r) | |
1685 | { | |
1686 | writeln("bad tree at:"); | |
1687 | debug printTree(n); | |
1688 | throw new Exception( | |
1689 | "Node at path " ~ path ~ " has different number of black nodes on left and right paths" | |
1690 | ); | |
1691 | } | |
1692 | return l + (n.color == n.color.Black ? 1 : 0); | |
1693 | } | |
1694 | ||
1695 | try | |
1696 | { | |
1697 | recurse(_end.left, ""); | |
1698 | } | |
1699 | catch (Exception e) | |
1700 | { | |
1701 | debug printTree(_end.left, 0); | |
1702 | throw e; | |
1703 | } | |
1704 | } | |
1705 | } | |
1706 | ||
1707 | /** | |
1708 | Formats the RedBlackTree into a sink function. For more info see $(D | |
1709 | std.format.formatValue). Note that this only is available when the | |
1710 | element type can be formatted. Otherwise, the default toString from | |
1711 | Object is used. | |
1712 | */ | |
1713 | static if (is(typeof((){FormatSpec!(char) fmt; formatValue((const(char)[]) {}, ConstRange.init, fmt);}))) | |
1714 | { | |
1715 | void toString(scope void delegate(const(char)[]) sink, FormatSpec!char fmt) const { | |
1716 | sink("RedBlackTree("); | |
1717 | sink.formatValue(this[], fmt); | |
1718 | sink(")"); | |
1719 | } | |
1720 | } | |
1721 | ||
1722 | /** | |
1723 | * Constructor. Pass in an array of elements, or individual elements to | |
1724 | * initialize the tree with. | |
1725 | */ | |
1726 | this(Elem[] elems...) | |
1727 | { | |
1728 | _setup(); | |
1729 | stableInsert(elems); | |
1730 | } | |
1731 | ||
1732 | /** | |
1733 | * Constructor. Pass in a range of elements to initialize the tree with. | |
1734 | */ | |
1735 | this(Stuff)(Stuff stuff) if (isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, Elem)) | |
1736 | { | |
1737 | _setup(); | |
1738 | stableInsert(stuff); | |
1739 | } | |
1740 | ||
1741 | /// | |
1742 | this() | |
1743 | { | |
1744 | _setup(); | |
1745 | } | |
1746 | ||
1747 | private this(Node end, size_t length) | |
1748 | { | |
1749 | _end = end; | |
1750 | _begin = end.leftmost; | |
1751 | _length = length; | |
1752 | } | |
1753 | } | |
1754 | ||
1755 | //Verify Example for removeKey. | |
1756 | @safe pure unittest | |
1757 | { | |
1758 | import std.algorithm.comparison : equal; | |
1759 | auto rbt = redBlackTree!true(0, 1, 1, 1, 4, 5, 7); | |
1760 | rbt.removeKey(1, 4, 7); | |
1761 | assert(equal(rbt[], [0, 1, 1, 5])); | |
1762 | rbt.removeKey(1, 1, 0); | |
1763 | assert(equal(rbt[], [5])); | |
1764 | } | |
1765 | ||
1766 | //Tests for removeKey | |
1767 | @safe pure unittest | |
1768 | { | |
1769 | import std.algorithm.comparison : equal; | |
1770 | { | |
1771 | auto rbt = redBlackTree(["hello", "world", "foo", "bar"]); | |
1772 | assert(equal(rbt[], ["bar", "foo", "hello", "world"])); | |
1773 | assert(rbt.removeKey("hello") == 1); | |
1774 | assert(equal(rbt[], ["bar", "foo", "world"])); | |
1775 | assert(rbt.removeKey("hello") == 0); | |
1776 | assert(equal(rbt[], ["bar", "foo", "world"])); | |
1777 | assert(rbt.removeKey("hello", "foo", "bar") == 2); | |
1778 | assert(equal(rbt[], ["world"])); | |
1779 | assert(rbt.removeKey(["", "world", "hello"]) == 1); | |
1780 | assert(rbt.empty); | |
1781 | } | |
1782 | ||
1783 | { | |
1784 | auto rbt = redBlackTree([1, 2, 12, 27, 4, 500]); | |
1785 | assert(equal(rbt[], [1, 2, 4, 12, 27, 500])); | |
1786 | assert(rbt.removeKey(1u) == 1); | |
1787 | assert(equal(rbt[], [2, 4, 12, 27, 500])); | |
1788 | assert(rbt.removeKey(cast(byte) 1) == 0); | |
1789 | assert(equal(rbt[], [2, 4, 12, 27, 500])); | |
1790 | assert(rbt.removeKey(1, 12u, cast(byte) 27) == 2); | |
1791 | assert(equal(rbt[], [2, 4, 500])); | |
1792 | assert(rbt.removeKey([cast(short) 0, cast(short) 500, cast(short) 1]) == 1); | |
1793 | assert(equal(rbt[], [2, 4])); | |
1794 | } | |
1795 | } | |
1796 | ||
1797 | @safe pure unittest | |
1798 | { | |
1799 | void test(T)() | |
1800 | { | |
1801 | auto rt1 = new RedBlackTree!(T, "a < b", false)(); | |
1802 | auto rt2 = new RedBlackTree!(T, "a < b", true)(); | |
1803 | auto rt3 = new RedBlackTree!(T, "a > b", false)(); | |
1804 | auto rt4 = new RedBlackTree!(T, "a > b", true)(); | |
1805 | } | |
1806 | ||
1807 | test!long(); | |
1808 | test!ulong(); | |
1809 | test!int(); | |
1810 | test!uint(); | |
1811 | test!short(); | |
1812 | test!ushort(); | |
1813 | test!byte(); | |
1814 | test!byte(); | |
1815 | } | |
1816 | ||
1817 | import std.range.primitives : isInputRange, isSomeString, ElementType; | |
1818 | import std.traits : isArray; | |
1819 | ||
1820 | /++ | |
1821 | Convenience function for creating a $(D RedBlackTree!E) from a list of | |
1822 | values. | |
1823 | ||
1824 | Params: | |
1825 | allowDuplicates = Whether duplicates should be allowed (optional, default: false) | |
1826 | less = predicate to sort by (optional) | |
1827 | elems = elements to insert into the rbtree (variadic arguments) | |
1828 | range = range elements to insert into the rbtree (alternative to elems) | |
1829 | +/ | |
1830 | auto redBlackTree(E)(E[] elems...) | |
1831 | { | |
1832 | return new RedBlackTree!E(elems); | |
1833 | } | |
1834 | ||
1835 | /++ Ditto +/ | |
1836 | auto redBlackTree(bool allowDuplicates, E)(E[] elems...) | |
1837 | { | |
1838 | return new RedBlackTree!(E, "a < b", allowDuplicates)(elems); | |
1839 | } | |
1840 | ||
1841 | /++ Ditto +/ | |
1842 | auto redBlackTree(alias less, E)(E[] elems...) | |
1843 | if (is(typeof(binaryFun!less(E.init, E.init)))) | |
1844 | { | |
1845 | return new RedBlackTree!(E, less)(elems); | |
1846 | } | |
1847 | ||
1848 | /++ Ditto +/ | |
1849 | auto redBlackTree(alias less, bool allowDuplicates, E)(E[] elems...) | |
1850 | if (is(typeof(binaryFun!less(E.init, E.init)))) | |
1851 | { | |
1852 | //We shouldn't need to instantiate less here, but for some reason, | |
1853 | //dmd can't handle it if we don't (even though the template which | |
1854 | //takes less but not allowDuplicates works just fine). | |
1855 | return new RedBlackTree!(E, binaryFun!less, allowDuplicates)(elems); | |
1856 | } | |
1857 | ||
1858 | /++ Ditto +/ | |
1859 | auto redBlackTree(Stuff)(Stuff range) | |
1860 | if (isInputRange!Stuff && !isArray!(Stuff)) | |
1861 | { | |
1862 | return new RedBlackTree!(ElementType!Stuff)(range); | |
1863 | } | |
1864 | ||
1865 | /++ Ditto +/ | |
1866 | auto redBlackTree(bool allowDuplicates, Stuff)(Stuff range) | |
1867 | if (isInputRange!Stuff && !isArray!(Stuff)) | |
1868 | { | |
1869 | return new RedBlackTree!(ElementType!Stuff, "a < b", allowDuplicates)(range); | |
1870 | } | |
1871 | ||
1872 | /++ Ditto +/ | |
1873 | auto redBlackTree(alias less, Stuff)(Stuff range) | |
1874 | if ( is(typeof(binaryFun!less((ElementType!Stuff).init, (ElementType!Stuff).init))) | |
1875 | && isInputRange!Stuff && !isArray!(Stuff)) | |
1876 | { | |
1877 | return new RedBlackTree!(ElementType!Stuff, less)(range); | |
1878 | } | |
1879 | ||
1880 | /++ Ditto +/ | |
1881 | auto redBlackTree(alias less, bool allowDuplicates, Stuff)(Stuff range) | |
1882 | if ( is(typeof(binaryFun!less((ElementType!Stuff).init, (ElementType!Stuff).init))) | |
1883 | && isInputRange!Stuff && !isArray!(Stuff)) | |
1884 | { | |
1885 | //We shouldn't need to instantiate less here, but for some reason, | |
1886 | //dmd can't handle it if we don't (even though the template which | |
1887 | //takes less but not allowDuplicates works just fine). | |
1888 | return new RedBlackTree!(ElementType!Stuff, binaryFun!less, allowDuplicates)(range); | |
1889 | } | |
1890 | ||
1891 | /// | |
1892 | @safe pure unittest | |
1893 | { | |
1894 | import std.range : iota; | |
1895 | ||
1896 | auto rbt1 = redBlackTree(0, 1, 5, 7); | |
1897 | auto rbt2 = redBlackTree!string("hello", "world"); | |
1898 | auto rbt3 = redBlackTree!true(0, 1, 5, 7, 5); | |
1899 | auto rbt4 = redBlackTree!"a > b"(0, 1, 5, 7); | |
1900 | auto rbt5 = redBlackTree!("a > b", true)(0.1, 1.3, 5.9, 7.2, 5.9); | |
1901 | ||
1902 | // also works with ranges | |
1903 | auto rbt6 = redBlackTree(iota(3)); | |
1904 | auto rbt7 = redBlackTree!true(iota(3)); | |
1905 | auto rbt8 = redBlackTree!"a > b"(iota(3)); | |
1906 | auto rbt9 = redBlackTree!("a > b", true)(iota(3)); | |
1907 | } | |
1908 | ||
1909 | //Combinations not in examples. | |
1910 | @safe pure unittest | |
1911 | { | |
1912 | auto rbt1 = redBlackTree!(true, string)("hello", "hello"); | |
1913 | auto rbt2 = redBlackTree!((a, b){return a < b;}, double)(5.1, 2.3); | |
1914 | auto rbt3 = redBlackTree!("a > b", true, string)("hello", "world"); | |
1915 | } | |
1916 | ||
1917 | //Range construction. | |
1918 | @safe pure unittest | |
1919 | { | |
1920 | import std.algorithm.comparison : equal; | |
1921 | import std.range : iota; | |
1922 | auto rbt = new RedBlackTree!(int, "a > b")(iota(5)); | |
1923 | assert(equal(rbt[], [4, 3, 2, 1, 0])); | |
1924 | } | |
1925 | ||
1926 | ||
1927 | // construction with arrays | |
1928 | @safe pure unittest | |
1929 | { | |
1930 | import std.algorithm.comparison : equal; | |
1931 | ||
1932 | auto rbt = redBlackTree!"a > b"([0, 1, 2, 3, 4]); | |
1933 | assert(equal(rbt[], [4, 3, 2, 1, 0])); | |
1934 | ||
1935 | auto rbt2 = redBlackTree!"a > b"(["a", "b"]); | |
1936 | assert(equal(rbt2[], ["b", "a"])); | |
1937 | ||
1938 | auto rbt3 = redBlackTree!"a > b"([1, 2]); | |
1939 | assert(equal(rbt3[], [2, 1])); | |
1940 | ||
1941 | auto rbt4 = redBlackTree([0, 1, 7, 5]); | |
1942 | assert(equal(rbt4[], [0, 1, 5, 7])); | |
1943 | ||
1944 | auto rbt5 = redBlackTree(["hello", "world"]); | |
1945 | assert(equal(rbt5[], ["hello", "world"])); | |
1946 | ||
1947 | auto rbt6 = redBlackTree!true([0, 1, 5, 7, 5]); | |
1948 | assert(equal(rbt6[], [0, 1, 5, 5, 7])); | |
1949 | ||
1950 | auto rbt7 = redBlackTree!"a > b"([0, 1, 5, 7]); | |
1951 | assert(equal(rbt7[], [7, 5, 1, 0])); | |
1952 | ||
1953 | auto rbt8 = redBlackTree!("a > b", true)([0.1, 1.3, 5.9, 7.2, 5.9]); | |
1954 | assert(equal(rbt8[], [7.2, 5.9, 5.9, 1.3, 0.1])); | |
1955 | } | |
1956 | ||
1957 | // convenience wrapper range construction | |
1958 | @safe pure unittest | |
1959 | { | |
1960 | import std.algorithm.comparison : equal; | |
1961 | import std.range : chain, iota; | |
1962 | ||
1963 | auto rbt = redBlackTree(iota(3)); | |
1964 | assert(equal(rbt[], [0, 1, 2])); | |
1965 | ||
1966 | auto rbt2 = redBlackTree!"a > b"(iota(2)); | |
1967 | assert(equal(rbt2[], [1, 0])); | |
1968 | ||
1969 | auto rbt3 = redBlackTree(chain([0, 1], [7, 5])); | |
1970 | assert(equal(rbt3[], [0, 1, 5, 7])); | |
1971 | ||
1972 | auto rbt4 = redBlackTree(chain(["hello"], ["world"])); | |
1973 | assert(equal(rbt4[], ["hello", "world"])); | |
1974 | ||
1975 | auto rbt5 = redBlackTree!true(chain([0, 1], [5, 7, 5])); | |
1976 | assert(equal(rbt5[], [0, 1, 5, 5, 7])); | |
1977 | ||
1978 | auto rbt6 = redBlackTree!("a > b", true)(chain([0.1, 1.3], [5.9, 7.2, 5.9])); | |
1979 | assert(equal(rbt6[], [7.2, 5.9, 5.9, 1.3, 0.1])); | |
1980 | } | |
1981 | ||
1982 | @safe pure unittest | |
1983 | { | |
1984 | import std.array : array; | |
1985 | ||
1986 | auto rt1 = redBlackTree(5, 4, 3, 2, 1); | |
1987 | assert(rt1.length == 5); | |
1988 | assert(array(rt1[]) == [1, 2, 3, 4, 5]); | |
1989 | ||
1990 | auto rt2 = redBlackTree!"a > b"(1.1, 2.1); | |
1991 | assert(rt2.length == 2); | |
1992 | assert(array(rt2[]) == [2.1, 1.1]); | |
1993 | ||
1994 | auto rt3 = redBlackTree!true(5, 5, 4); | |
1995 | assert(rt3.length == 3); | |
1996 | assert(array(rt3[]) == [4, 5, 5]); | |
1997 | ||
1998 | auto rt4 = redBlackTree!string("hello", "hello"); | |
1999 | assert(rt4.length == 1); | |
2000 | assert(array(rt4[]) == ["hello"]); | |
2001 | } | |
2002 | ||
2003 | @system unittest | |
2004 | { | |
2005 | import std.conv : to; | |
2006 | ||
2007 | auto rt1 = redBlackTree!string(); | |
2008 | assert(rt1.to!string == "RedBlackTree([])"); | |
2009 | ||
2010 | auto rt2 = redBlackTree!string("hello"); | |
2011 | assert(rt2.to!string == "RedBlackTree([\"hello\"])"); | |
2012 | ||
2013 | auto rt3 = redBlackTree!string("hello", "world", "!"); | |
2014 | assert(rt3.to!string == "RedBlackTree([\"!\", \"hello\", \"world\"])"); | |
2015 | ||
2016 | // type deduction can be done automatically | |
2017 | auto rt4 = redBlackTree(["hello"]); | |
2018 | assert(rt4.to!string == "RedBlackTree([\"hello\"])"); | |
2019 | } | |
2020 | ||
2021 | //constness checks | |
2022 | @safe pure unittest | |
2023 | { | |
2024 | const rt1 = redBlackTree(5,4,3,2,1); | |
2025 | static assert(is(typeof(rt1.length))); | |
2026 | static assert(is(typeof(5 in rt1))); | |
2027 | ||
2028 | static assert(is(typeof(rt1.upperBound(3).front) == const(int))); | |
2029 | import std.algorithm.comparison : equal; | |
2030 | assert(rt1.upperBound(3).equal([4, 5])); | |
2031 | assert(rt1.lowerBound(3).equal([1, 2])); | |
2032 | assert(rt1.equalRange(3).equal([3])); | |
2033 | assert(rt1[].equal([1, 2, 3, 4, 5])); | |
2034 | } | |
2035 | ||
2036 | //immutable checks | |
2037 | @safe pure unittest | |
2038 | { | |
2039 | immutable rt1 = redBlackTree(5,4,3,2,1); | |
2040 | static assert(is(typeof(rt1.length))); | |
2041 | ||
2042 | static assert(is(typeof(rt1.upperBound(3).front) == immutable(int))); | |
2043 | import std.algorithm.comparison : equal; | |
2044 | assert(rt1.upperBound(2).equal([3, 4, 5])); | |
2045 | } | |
2046 | ||
2047 | // issue 15941 | |
2048 | @safe pure unittest | |
2049 | { | |
2050 | class C {} | |
2051 | RedBlackTree!(C, "cast(void*)a < cast(void*) b") tree; | |
2052 | } | |
2053 | ||
2054 | @safe pure unittest // const/immutable elements (issue 17519) | |
2055 | { | |
2056 | RedBlackTree!(immutable int) t1; | |
2057 | RedBlackTree!(const int) t2; | |
2058 | ||
2059 | import std.algorithm.iteration : map; | |
2060 | static struct S { int* p; } | |
2061 | auto t3 = new RedBlackTree!(immutable S, (a, b) => *a.p < *b.p); | |
2062 | t3.insert([1, 2, 3].map!(x => immutable S(new int(x)))); | |
2063 | static assert(!__traits(compiles, *t3.front.p = 4)); | |
2064 | assert(*t3.front.p == 1); | |
2065 | } |