1 module nxt.unique_range; 2 3 version(unittest) 4 { 5 import nxt.dbgio : dbg; 6 import std.algorithm.comparison : equal; 7 } 8 9 import std.range.primitives : hasLength; 10 11 /** Unique range (slice) owning its source of `Source`. 12 13 Copy construction is disabled, explicit copying is instead done through 14 member `.dup`. 15 */ 16 struct UniqueRange(Source) 17 if (hasLength!Source) // TODO use traits `isArrayContainer` checking fo 18 { 19 import std.range.primitives : ElementType, isBidirectionalRange; 20 import std.traits : isArray; 21 alias SourceRange = typeof(Source.init[]); 22 alias E = ElementType!SourceRange; 23 24 @disable this(this); // not intended to be copied 25 26 pragma(inline, true) @safe pure nothrow @nogc: 27 28 /// Construct from `source`. 29 this(Source source) 30 { 31 import std.algorithm.mutation : move; 32 move(source, _source); // TODO remove `move` when compiler does it for us 33 _sourceRange = _source[]; 34 } 35 36 /// Construct from reference to `source`, used by `intoUniqueRange`. 37 private this(ref Source source) 38 { 39 import std.algorithm.mutation : move; 40 move(source, _source); // TODO remove `move` when compiler does it for us 41 _sourceRange = _source[]; 42 } 43 44 /// Is `true` if range is empty. 45 @property bool empty() const @trusted 46 { 47 static if (!__traits(hasMember, SourceRange, "empty")) 48 { 49 import std.range.primitives : empty; 50 } 51 return (cast(Unqual!SourceRange)_sourceRange).empty; // TODO remove cast and @trusted when SortedRange.empty is const 52 } 53 54 /// Returns: length of `this`. 55 static if (hasLength!(typeof(Source.init[]))) 56 { 57 @property size_t length() const @trusted 58 { 59 return (cast(Unqual!SourceRange)_sourceRange).length; // TODO remove cast and @trusted when SortedRange.empty is const 60 } 61 } 62 63 /// Front element. 64 @property scope auto ref inout(E) front() inout return @trusted 65 { 66 assert(!empty); 67 static if (!__traits(hasMember, SourceRange, "front")) 68 { 69 import std.range.primitives : front; 70 } 71 return cast(inout(E))(cast(SourceRange)_sourceRange).front; 72 } 73 74 /// Pop front element. 75 void popFront() 76 { 77 static if (!__traits(hasMember, SourceRange, "popFront")) 78 { 79 import std.range.primitives : popFront; 80 } 81 _sourceRange.popFront(); // should include check for emptyness 82 } 83 84 /// Pop front element and return it. 85 E frontPop()() 86 { 87 assert(!empty); 88 89 import core.internal.traits : hasElaborateDestructor; 90 static if (__traits(isCopyable, E) && 91 !hasElaborateDestructor!E) 92 { 93 typeof(return) value = front; 94 popFront(); 95 return value; 96 } 97 else 98 { 99 static assert(0, "TODO if front is an l-value move it out and return it"); 100 // import std.algorithm.mutation : move; 101 // import core.internal.traits : Unqual; 102 // TODO reinterpret as typeof(*(cast(Unqual!E*)(&_source[_frontIx]))) iff `E` doesn't contain any immutable indirections 103 // typeof(return) value = move(_sourceRange.front); 104 // popFront(); 105 // return value; 106 } 107 } 108 alias stealFront = frontPop; 109 110 static if (isBidirectionalRange!(typeof(Source.init[]))) 111 { 112 /// Back element. 113 @property scope auto ref inout(E) back() inout return @trusted 114 { 115 assert(!empty); 116 static if (!__traits(hasMember, SourceRange, "back")) 117 { 118 import std.range.primitives : back; 119 } 120 return cast(inout(E))(cast(SourceRange)_sourceRange).back; 121 } 122 123 /// Pop back element. 124 void popBack() 125 { 126 static if (!__traits(hasMember, SourceRange, "popBack")) 127 { 128 import std.range.primitives : popBack; 129 } 130 _sourceRange.popBack(); // should include check for emptyness 131 } 132 133 /// Pop back element and return it. 134 E backPop()() 135 { 136 assert(!empty); 137 138 import core.internal.traits : hasElaborateDestructor; 139 static if (__traits(isCopyable, E) && 140 !hasElaborateDestructor!E) 141 { 142 typeof(return) value = back; 143 popBack(); 144 return value; 145 } 146 else 147 { 148 static assert(0, "TODO if back is an l-value move it out and return it"); 149 // import std.algorithm.mutation : move; 150 // import core.internal.traits : Unqual; 151 // TODO reinterpret as typeof(*(cast(Unqual!E*)(&_source[_backIx]))) iff `E` doesn't contain any immutable indirections 152 // typeof(return) value = move(_sourceRange.back); 153 // popBack(); 154 // return value; 155 } 156 } 157 alias stealBack = backPop; 158 } 159 160 /// Returns: shallow duplicate of `this`. 161 static if (__traits(hasMember, Source, "dup")) 162 { 163 @property typeof(this) dup()() const // template-lazy 164 { 165 return typeof(return)(_source.dup); 166 } 167 } 168 169 private: 170 Source _source; // typically a non-reference counted container type with disable copy construction 171 SourceRange _sourceRange; 172 } 173 174 /** Returns: A range of `Source` that owns its `source` (data container). 175 Similar to Rust's `into_iter`. 176 */ 177 UniqueRange!Source intoUniqueRange(Source)(Source source) 178 { 179 return typeof(return)(source); // construct from reference 180 } 181 182 /// A generator is a range which owns its state (typically a non-reference counted container). 183 alias intoGenerator = intoUniqueRange; 184 185 /// basics 186 @safe pure nothrow @nogc unittest 187 { 188 import nxt.dynamic_array : SA = DynamicArray; 189 import std.traits : isIterable; 190 import std.range.primitives : isInputRange; 191 alias C = SA!int; 192 193 auto cs = C([11, 13, 15, 17].s).intoUniqueRange; 194 auto cs2 = cs.dup; 195 196 assert(cs !is cs2); 197 198 assert(cs == cs2); 199 cs2.popFront(); 200 assert(cs2.length == 3); 201 assert(cs != cs2); 202 203 static assert(isInputRange!(typeof(cs))); 204 static assert(isIterable!(typeof(cs))); 205 206 assert(!cs.empty); 207 assert(cs.length == 4); 208 assert(cs.front == 11); 209 assert(cs.back == 17); 210 211 cs.popFront(); 212 assert(cs.length == 3); 213 assert(cs.front == 13); 214 assert(cs.back == 17); 215 216 cs.popBack(); 217 assert(cs.length == 2); 218 assert(cs.front == 13); 219 assert(cs.back == 15); 220 221 assert(cs.frontPop() == 13); 222 assert(cs.length == 1); 223 assert(cs.front == 15); 224 assert(cs.back == 15); 225 226 assert(cs.backPop() == 15); 227 assert(cs.length == 0); 228 assert(cs.empty); 229 } 230 231 /// combined with Phobos ranges 232 @safe pure nothrow unittest 233 { 234 import nxt.dynamic_array : SA = DynamicArray; 235 alias C = SA!int; 236 assert(C([11, 13, 15, 17].s) 237 .intoUniqueRange() 238 .filterUnique!(_ => _ != 11) 239 .mapUnique!(_ => 2*_) 240 .equal([2*13, 2*15, 2*17])); 241 } 242 243 import std.functional : unaryFun; 244 245 template mapUnique(fun...) if (fun.length >= 1) 246 { 247 import std.algorithm.mutation : move; 248 import std.range.primitives : isInputRange, ElementType; 249 import core.internal.traits : Unqual; 250 251 auto mapUnique(Range)(Range r) if (isInputRange!(Unqual!Range)) 252 { 253 import std.meta : AliasSeq, staticMap; 254 255 alias RE = ElementType!(Range); 256 static if (fun.length > 1) 257 { 258 import std.functional : adjoin; 259 import std.meta : staticIndexOf; 260 261 alias _funs = staticMap!(unaryFun, fun); 262 alias _fun = adjoin!_funs; 263 264 // Once DMD issue #5710 is fixed, this validation loop can be moved into a template. 265 foreach (f; _funs) 266 { 267 static assert(!is(typeof(f(RE.init)) == void), 268 "Mapping function(s) must not return void: " ~ _funs.stringof); 269 } 270 } 271 else 272 { 273 alias _fun = unaryFun!fun; 274 alias _funs = AliasSeq!(_fun); 275 276 // Do the validation separately for single parameters due to DMD issue #15777. 277 static assert(!is(typeof(_fun(RE.init)) == void), 278 "Mapping function(s) must not return void: " ~ _funs.stringof); 279 } 280 281 return MapUniqueResult!(_fun, Range)(move(r)); 282 } 283 } 284 285 private struct MapUniqueResult(alias fun, Range) 286 { 287 import core.internal.traits : Unqual; 288 import std.range.primitives : isInputRange, isForwardRange, isBidirectionalRange, isRandomAccessRange, isInfinite, hasSlicing; 289 import std.algorithm.mutation : move; 290 291 alias R = Unqual!Range; 292 R _input; 293 294 static if (isBidirectionalRange!R) 295 { 296 @property auto ref back()() 297 { 298 assert(!empty, "Attempting to fetch the back of an empty mapUnique."); 299 return fun(_input.back); 300 } 301 302 void popBack()() 303 { 304 assert(!empty, "Attempting to popBack an empty mapUnique."); 305 _input.popBack(); 306 } 307 } 308 309 this(R input) 310 { 311 _input = move(input); // TODO remove `move` when compiler does it for us 312 } 313 314 static if (isInfinite!R) 315 { 316 // Propagate infinite-ness. 317 enum bool empty = false; 318 } 319 else 320 { 321 @property bool empty() 322 { 323 return _input.empty; 324 } 325 } 326 327 void popFront() 328 { 329 assert(!empty, "Attempting to popFront an empty mapUnique."); 330 _input.popFront(); 331 } 332 333 @property auto ref front() 334 { 335 assert(!empty, "Attempting to fetch the front of an empty mapUnique."); 336 return fun(_input.front); 337 } 338 339 static if (isRandomAccessRange!R) 340 { 341 static if (is(typeof(_input[ulong.max]))) 342 private alias opIndex_t = ulong; 343 else 344 private alias opIndex_t = uint; 345 346 auto ref opIndex(opIndex_t index) 347 { 348 return fun(_input[index]); 349 } 350 } 351 352 static if (hasLength!R) 353 { 354 @property auto length() 355 { 356 return _input.length; 357 } 358 359 alias opDollar = length; 360 } 361 362 static if (hasSlicing!R && 363 __traits(isCopyable, R)) 364 { 365 static if (is(typeof(_input[ulong.max .. ulong.max]))) 366 private alias opSlice_t = ulong; 367 else 368 private alias opSlice_t = uint; 369 370 static if (hasLength!R) 371 { 372 auto opSlice(opSlice_t low, opSlice_t high) 373 { 374 return typeof(this)(_input[low .. high]); 375 } 376 } 377 else static if (is(typeof(_input[opSlice_t.max .. $]))) 378 { 379 struct DollarToken{} 380 enum opDollar = DollarToken.init; 381 auto opSlice(opSlice_t low, DollarToken) 382 { 383 return typeof(this)(_input[low .. $]); 384 } 385 386 auto opSlice(opSlice_t low, opSlice_t high) 387 { 388 import std.range : takeExactly; 389 return this[low .. $].takeExactly(high - low); 390 } 391 } 392 } 393 394 static if (isForwardRange!R && 395 __traits(isCopyable, R)) // TODO should save be allowed for non-copyable? 396 { 397 @property auto save() 398 { 399 return typeof(this)(_input.save); 400 } 401 } 402 } 403 404 // TODO Add duck-typed interface that shows that result is still sorted according to `predicate` 405 template filterUnique(alias predicate) if (is(typeof(unaryFun!predicate))) 406 { 407 import std.algorithm.mutation : move; 408 import std.range.primitives : isInputRange; 409 import core.internal.traits : Unqual; 410 411 auto filterUnique(Range)(Range range) 412 if (isInputRange!(Unqual!Range)) 413 { 414 return FilterUniqueResult!(unaryFun!predicate, Range)(move(range)); 415 } 416 } 417 418 // TODO Add duck-typed interface that shows that result is still sorted according to `predicate` 419 private struct FilterUniqueResult(alias pred, Range) 420 { 421 import std.algorithm.mutation : move; 422 import std.range.primitives : isForwardRange, isInfinite; 423 import core.internal.traits : Unqual; 424 alias R = Unqual!Range; 425 R _input; 426 427 this(R r) 428 { 429 _input = move(r); // TODO remove `move` when compiler does it for us 430 while (!_input.empty && !pred(_input.front)) 431 { 432 _input.popFront(); 433 } 434 } 435 436 static if (__traits(isCopyable, Range)) 437 { 438 auto opSlice() { return this; } 439 } 440 441 static if (isInfinite!Range) 442 { 443 enum bool empty = false; 444 } 445 else 446 { 447 @property bool empty() { return _input.empty; } 448 } 449 450 void popFront() 451 { 452 do 453 { 454 _input.popFront(); 455 } while (!_input.empty && !pred(_input.front)); 456 } 457 458 @property auto ref front() 459 { 460 assert(!empty, "Attempting to fetch the front of an empty filterUnique."); 461 return _input.front; 462 } 463 464 static if (isForwardRange!R && 465 __traits(isCopyable, R)) // TODO should save be allowed for non-copyable? 466 { 467 @property auto save() 468 { 469 return typeof(this)(_input.save); 470 } 471 } 472 } 473 474 // TODO move these hidden behind template defs of takeUnique 475 import core.internal.traits : Unqual; 476 import std.range.primitives : isInputRange, isInfinite, hasSlicing; 477 478 /// Unique take. 479 UniqueTake!R takeUnique(R)(R input, size_t n) 480 if (is(R T == UniqueTake!T)) 481 { 482 import std.algorithm.mutation : move; 483 import std.algorithm.comparison : min; 484 return R(move(input.source), // TODO remove `move` when compiler does it for us 485 min(n, input._maxAvailable)); 486 } 487 488 /// ditto 489 UniqueTake!(R) takeUnique(R)(R input, size_t n) 490 if (isInputRange!(Unqual!R) && 491 (isInfinite!(Unqual!R) || 492 !hasSlicing!(Unqual!R) && 493 !is(R T == UniqueTake!T))) 494 { 495 import std.algorithm.mutation : move; 496 return UniqueTake!R(move(input), n); // TODO remove `move` when compiler does it for us 497 } 498 499 struct UniqueTake(Range) 500 if (isInputRange!(Unqual!Range) && 501 //take _cannot_ test hasSlicing on infinite ranges, because hasSlicing uses 502 //take for slicing infinite ranges. 503 !((!isInfinite!(Unqual!Range) && hasSlicing!(Unqual!Range)) || is(Range T == UniqueTake!T))) 504 { 505 import std.range.primitives : isForwardRange, hasAssignableElements, ElementType, hasMobileElements, isRandomAccessRange, moveFront; 506 507 private alias R = Unqual!Range; 508 509 /// User accessible in read and write 510 public R source; 511 512 private size_t _maxAvailable; 513 514 alias Source = R; 515 516 this(R source, size_t _maxAvailable) 517 { 518 import std.algorithm.mutation : move; 519 this.source = move(source); 520 this._maxAvailable = _maxAvailable; 521 } 522 523 /// Range primitives 524 @property bool empty() 525 { 526 return _maxAvailable == 0 || source.empty; 527 } 528 529 /// ditto 530 @property auto ref front() 531 { 532 assert(!empty, 533 "Attempting to fetch the front of an empty " 534 ~ UniqueTake.stringof); 535 return source.front; 536 } 537 538 /// ditto 539 void popFront() 540 { 541 assert(!empty, 542 "Attempting to popFront() past the end of a " 543 ~ UniqueTake.stringof); 544 source.popFront(); 545 --_maxAvailable; 546 } 547 548 static if (isForwardRange!R) 549 /// ditto 550 @property UniqueTake save() 551 { 552 return UniqueTake(source.save, _maxAvailable); 553 } 554 555 static if (hasAssignableElements!R) 556 /// ditto 557 @property auto front(ElementType!R v) 558 { 559 assert(!empty, 560 "Attempting to assign to the front of an empty " 561 ~ UniqueTake.stringof); 562 // This has to return auto instead of void because of Bug 4706. 563 source.front = v; 564 } 565 566 // static if (hasMobileElements!R) 567 // { 568 // /// ditto 569 // auto moveFront() 570 // { 571 // assert(!empty, 572 // "Attempting to move the front of an empty " 573 // ~ UniqueTake.stringof); 574 // return source.moveFront(); 575 // } 576 // } 577 578 static if (isInfinite!R) 579 { 580 /// ditto 581 @property size_t length() const 582 { 583 return _maxAvailable; 584 } 585 586 /// ditto 587 alias opDollar = length; 588 589 //Note: Due to UniqueTake/hasSlicing circular dependency, 590 //This needs to be a restrained template. 591 /// ditto 592 auto opSlice()(size_t i, size_t j) 593 if (hasSlicing!R) 594 { 595 assert(i <= j, "Invalid slice bounds"); 596 assert(j <= length, "Attempting to slice past the end of a " 597 ~ UniqueTake.stringof); 598 return source[i .. j]; 599 } 600 } 601 else static if (hasLength!R) 602 { 603 /// ditto 604 @property size_t length() 605 { 606 import std.algorithm.comparison : min; 607 return min(_maxAvailable, source.length); 608 } 609 610 alias opDollar = length; 611 } 612 613 static if (isRandomAccessRange!R) 614 { 615 /// ditto 616 void popBack() 617 { 618 assert(!empty, 619 "Attempting to popBack() past the beginning of a " 620 ~ UniqueTake.stringof); 621 --_maxAvailable; 622 } 623 624 /// ditto 625 @property auto ref back() 626 { 627 assert(!empty, 628 "Attempting to fetch the back of an empty " 629 ~ UniqueTake.stringof); 630 return source[this.length - 1]; 631 } 632 633 /// ditto 634 auto ref opIndex(size_t index) 635 { 636 assert(index < length, 637 "Attempting to index out of the bounds of a " 638 ~ UniqueTake.stringof); 639 return source[index]; 640 } 641 642 static if (hasAssignableElements!R) 643 { 644 /// ditto 645 @property auto back(ElementType!R v) 646 { 647 // This has to return auto instead of void because of Bug 4706. 648 assert(!empty, 649 "Attempting to assign to the back of an empty " 650 ~ UniqueTake.stringof); 651 source[this.length - 1] = v; 652 } 653 654 /// ditto 655 void opIndexAssign(ElementType!R v, size_t index) 656 { 657 assert(index < length, 658 "Attempting to index out of the bounds of a " 659 ~ UniqueTake.stringof); 660 source[index] = v; 661 } 662 } 663 664 static if (hasMobileElements!R) 665 { 666 /// ditto 667 auto moveBack() 668 { 669 assert(!empty, 670 "Attempting to move the back of an empty " 671 ~ UniqueTake.stringof); 672 return source.moveAt(this.length - 1); 673 } 674 675 /// ditto 676 auto moveAt(size_t index) 677 { 678 assert(index < length, 679 "Attempting to index out of the bounds of a " 680 ~ UniqueTake.stringof); 681 return source.moveAt(index); 682 } 683 } 684 } 685 686 /** 687 Access to maximal length of the range. 688 Note: the actual length of the range depends on the underlying range. 689 If it has fewer elements, it will stop before maxLength is reached. 690 */ 691 @property size_t maxLength() const 692 { 693 return _maxAvailable; 694 } 695 } 696 697 /// array range 698 @safe pure nothrow @nogc unittest 699 { 700 import nxt.dynamic_array : SA = DynamicArray; 701 import std.traits : isIterable; 702 import std.range.primitives : isInputRange; 703 alias C = SA!int; 704 705 auto cs = C([11, 13].s).intoUniqueRange; 706 707 alias CS = typeof(cs); 708 static assert(isInputRange!(typeof(cs))); 709 static assert(isIterable!(typeof(cs))); 710 711 assert(cs.front == 11); 712 cs.popFront(); 713 714 assert(cs.front == 13); 715 cs.popFront(); 716 717 assert(cs.empty); 718 } 719 720 import std.functional : binaryFun; 721 722 InputRange findUnique(alias pred = "a == b", InputRange, Element)(InputRange haystack, scope Element needle) 723 if (isInputRange!InputRange && 724 is (typeof(binaryFun!pred(haystack.front, needle)) : bool)) 725 { 726 for (; !haystack.empty; haystack.popFront()) 727 { 728 if (binaryFun!pred(haystack.front, needle)) 729 break; 730 } 731 import std.algorithm.mutation : move; 732 return move(haystack); 733 } 734 735 version(unittest) 736 { 737 import nxt.array_help : s; 738 }