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