1 /** 2 This module is a submodule of $(MREF std, range). 3 4 The main $(MREF std, range) module provides template-based tools for working with 5 ranges, but sometimes an object-based interface for ranges is needed, such as 6 when runtime polymorphism is required. For this purpose, this submodule 7 provides a number of object and `interface` definitions that can be used to 8 wrap around range objects created by the $(MREF std, range) templates. 9 10 $(SCRIPT inhibitQuickIndex = 1;) 11 $(DIVC quickindex, 12 $(BOOKTABLE , 13 $(TR $(TD $(LREF InputRange)) 14 $(TD Wrapper for input ranges. 15 )) 16 $(TR $(TD $(LREF InputAssignable)) 17 $(TD Wrapper for input ranges with assignable elements. 18 )) 19 $(TR $(TD $(LREF ForwardRange)) 20 $(TD Wrapper for forward ranges. 21 )) 22 $(TR $(TD $(LREF ForwardAssignable)) 23 $(TD Wrapper for forward ranges with assignable elements. 24 )) 25 $(TR $(TD $(LREF BidirectionalRange)) 26 $(TD Wrapper for bidirectional ranges. 27 )) 28 $(TR $(TD $(LREF BidirectionalAssignable)) 29 $(TD Wrapper for bidirectional ranges with assignable elements. 30 )) 31 $(TR $(TD $(LREF RandomAccessFinite)) 32 $(TD Wrapper for finite random-access ranges. 33 )) 34 $(TR $(TD $(LREF RandomAccessAssignable)) 35 $(TD Wrapper for finite random-access ranges with assignable elements. 36 )) 37 $(TR $(TD $(LREF RandomAccessInfinite)) 38 $(TD Wrapper for infinite random-access ranges. 39 )) 40 $(TR $(TD $(LREF OutputRange)) 41 $(TD Wrapper for output ranges. 42 )) 43 $(TR $(TD $(LREF OutputRangeObject)) 44 $(TD Class that implements the `OutputRange` interface and wraps the 45 `put` methods in virtual functions. 46 )) 47 $(TR $(TD $(LREF outputRangeObject)) 48 $(TD Convenience function for creating an `OutputRangeObject` with a base 49 range of type R that accepts types E. 50 )) 51 $(TR $(TD $(LREF InputRangeObject)) 52 $(TD Class that implements the `InputRange` interface and wraps the 53 input range methods in virtual functions. 54 )) 55 $(TR $(TD $(LREF inputRangeObject)) 56 $(TD Convenience function for creating an `InputRangeObject` 57 of the proper type. 58 )) 59 $(TR $(TD $(LREF MostDerivedInputRange)) 60 $(TD Returns the interface type that best matches the range. 61 )) 62 )) 63 64 65 Source: $(PHOBOSSRC std/range/interfaces.d) 66 67 License: $(HTTP boost.org/LICENSE_1_0.txt, Boost License 1.0). 68 69 Authors: $(HTTP erdani.com, Andrei Alexandrescu), David Simcha, and 70 $(HTTP jmdavisprog.com, Jonathan M Davis). Credit for some of the ideas 71 in building this module goes to 72 $(HTTP fantascienza.net/leonardo/so/, Leonardo Maffi). 73 */ 74 module std.range.interfaces; 75 76 import std.meta; 77 import std.range.primitives; 78 import std.traits; 79 80 /**These interfaces are intended to provide virtual function-based wrappers 81 * around input ranges with element type E. This is useful where a well-defined 82 * binary interface is required, such as when a DLL function or virtual function 83 * needs to accept a generic range as a parameter. Note that 84 * $(REF_ALTTEXT isInputRange, isInputRange, std, range, primitives) 85 * and friends check for conformance to structural interfaces 86 * not for implementation of these `interface` types. 87 * 88 * Limitations: 89 * 90 * These interfaces are not capable of forwarding `ref` access to elements. 91 * 92 * Infiniteness of the wrapped range is not propagated. 93 * 94 * Length is not propagated in the case of non-random access ranges. 95 * 96 * See_Also: 97 * $(LREF inputRangeObject) 98 */ 99 interface InputRange(E) { 100 /// 101 @property E front(); 102 103 /// 104 E moveFront(); 105 106 /// 107 void popFront(); 108 109 /// 110 @property bool empty(); 111 112 /* Measurements of the benefits of using opApply instead of range primitives 113 * for foreach, using timings for iterating over an iota(100_000_000) range 114 * with an empty loop body, using the same hardware in each case: 115 * 116 * Bare Iota struct, range primitives: 278 milliseconds 117 * InputRangeObject, opApply: 436 milliseconds (1.57x penalty) 118 * InputRangeObject, range primitives: 877 milliseconds (3.15x penalty) 119 */ 120 121 /**`foreach` iteration uses opApply, since one delegate call per loop 122 * iteration is faster than three virtual function calls. 123 */ 124 int opApply(scope int delegate(E)); 125 126 /// Ditto 127 int opApply(scope int delegate(size_t, E)); 128 129 } 130 131 /// 132 @safe unittest 133 { 134 import std.algorithm.iteration : map; 135 import std.range : iota; 136 137 void useRange(InputRange!int range) { 138 // Function body. 139 } 140 141 // Create a range type. 142 auto squares = map!"a * a"(iota(10)); 143 144 // Wrap it in an interface. 145 auto squaresWrapped = inputRangeObject(squares); 146 147 // Use it. 148 useRange(squaresWrapped); 149 } 150 151 /**Interface for a forward range of type `E`.*/ 152 interface ForwardRange(E) : InputRange!E { 153 /// 154 @property ForwardRange!E save(); 155 } 156 157 /**Interface for a bidirectional range of type `E`.*/ 158 interface BidirectionalRange(E) : ForwardRange!(E) { 159 /// 160 @property BidirectionalRange!E save(); 161 162 /// 163 @property E back(); 164 165 /// 166 E moveBack(); 167 168 /// 169 void popBack(); 170 } 171 172 /**Interface for a finite random access range of type `E`.*/ 173 interface RandomAccessFinite(E) : BidirectionalRange!(E) { 174 /// 175 @property RandomAccessFinite!E save(); 176 177 /// 178 E opIndex(size_t); 179 180 /// 181 E moveAt(size_t); 182 183 /// 184 @property size_t length(); 185 186 /// 187 alias opDollar = length; 188 189 // Can't support slicing until issues with requiring slicing for all 190 // finite random access ranges are fully resolved. 191 version (none) 192 { 193 /// 194 RandomAccessFinite!E opSlice(size_t, size_t); 195 } 196 } 197 198 /**Interface for an infinite random access range of type `E`.*/ 199 interface RandomAccessInfinite(E) : ForwardRange!E { 200 /// 201 E moveAt(size_t); 202 203 /// 204 @property RandomAccessInfinite!E save(); 205 206 /// 207 E opIndex(size_t); 208 } 209 210 /**Adds assignable elements to InputRange.*/ 211 interface InputAssignable(E) : InputRange!E { 212 /// 213 @property void front(E newVal); 214 215 alias front = InputRange!E.front; // overload base interface method 216 } 217 218 @safe unittest 219 { 220 static assert(isInputRange!(InputAssignable!int)); 221 } 222 223 /**Adds assignable elements to ForwardRange.*/ 224 interface ForwardAssignable(E) : InputAssignable!E, ForwardRange!E { 225 /// 226 @property ForwardAssignable!E save(); 227 } 228 229 /**Adds assignable elements to BidirectionalRange.*/ 230 interface BidirectionalAssignable(E) : ForwardAssignable!E, BidirectionalRange!E { 231 /// 232 @property BidirectionalAssignable!E save(); 233 234 /// 235 @property void back(E newVal); 236 } 237 238 /**Adds assignable elements to RandomAccessFinite.*/ 239 interface RandomFiniteAssignable(E) : RandomAccessFinite!E, BidirectionalAssignable!E { 240 /// 241 @property RandomFiniteAssignable!E save(); 242 243 /// 244 void opIndexAssign(E val, size_t index); 245 } 246 247 /**Interface for an output range of type `E`. Usage is similar to the 248 * `InputRange` interface and descendants.*/ 249 interface OutputRange(E) { 250 /// 251 void put(E); 252 } 253 254 // https://issues.dlang.org/show_bug.cgi?id=6973 255 @safe unittest 256 { 257 static assert(isOutputRange!(OutputRange!int, int)); 258 } 259 260 261 // CTFE function that generates mixin code for one put() method for each 262 // type E. 263 private string putMethods(E...)() 264 { 265 import std.conv : to; 266 267 string ret; 268 269 foreach (ti, Unused; E) 270 { 271 ret ~= "void put(E[" ~ to!string(ti) ~ "] e) { .put(_range, e); }"; 272 } 273 274 return ret; 275 } 276 277 /**Implements the `OutputRange` interface for all types E and wraps the 278 * `put` method for each type `E` in a virtual function. 279 */ 280 class OutputRangeObject(R, E...) : staticMap!(OutputRange, E) { 281 // @BUG 4689: There should be constraints on this template class, but 282 // DMD won't let me put them in. 283 private R _range; 284 285 /// 286 this(R range) { 287 this._range = range; 288 } 289 290 mixin(putMethods!E()); 291 } 292 293 294 /**Returns the interface type that best matches `R`.*/ 295 template MostDerivedInputRange(R) 296 if (isInputRange!(Unqual!R)) 297 { 298 private alias E = ElementType!R; 299 300 static if (isRandomAccessRange!R) 301 { 302 static if (isInfinite!R) 303 { 304 alias MostDerivedInputRange = RandomAccessInfinite!E; 305 } 306 else static if (hasAssignableElements!R) 307 { 308 alias MostDerivedInputRange = RandomFiniteAssignable!E; 309 } 310 else 311 { 312 alias MostDerivedInputRange = RandomAccessFinite!E; 313 } 314 } 315 else static if (isBidirectionalRange!R) 316 { 317 static if (hasAssignableElements!R) 318 { 319 alias MostDerivedInputRange = BidirectionalAssignable!E; 320 } 321 else 322 { 323 alias MostDerivedInputRange = BidirectionalRange!E; 324 } 325 } 326 else static if (isForwardRange!R) 327 { 328 static if (hasAssignableElements!R) 329 { 330 alias MostDerivedInputRange = ForwardAssignable!E; 331 } 332 else 333 { 334 alias MostDerivedInputRange = ForwardRange!E; 335 } 336 } 337 else 338 { 339 static if (hasAssignableElements!R) 340 { 341 alias MostDerivedInputRange = InputAssignable!E; 342 } 343 else 344 { 345 alias MostDerivedInputRange = InputRange!E; 346 } 347 } 348 } 349 350 /**Implements the most derived interface that `R` works with and wraps 351 * all relevant range primitives in virtual functions. If `R` is already 352 * derived from the `InputRange` interface, aliases itself away. 353 */ 354 template InputRangeObject(R) 355 if (isInputRange!(Unqual!R)) 356 { 357 static if (is(R : InputRange!(ElementType!R))) 358 { 359 alias InputRangeObject = R; 360 } 361 else static if (!is(Unqual!R == R)) 362 { 363 alias InputRangeObject = InputRangeObject!(Unqual!R); 364 } 365 else 366 { 367 368 /// 369 class InputRangeObject : MostDerivedInputRange!(R) { 370 private R _range; 371 private alias E = ElementType!R; 372 373 this(R range) { 374 this._range = range; 375 } 376 377 @property E front() { return _range.front; } 378 379 E moveFront() { 380 return _range.moveFront(); 381 } 382 383 void popFront() { _range.popFront(); } 384 @property bool empty() { return _range.empty; } 385 386 static if (isForwardRange!R) 387 { 388 @property typeof(this) save() { 389 return new typeof(this)(_range.save); 390 } 391 } 392 393 static if (hasAssignableElements!R) 394 { 395 @property void front(E newVal) { 396 _range.front = newVal; 397 } 398 } 399 400 static if (isBidirectionalRange!R) 401 { 402 @property E back() { return _range.back; } 403 404 E moveBack() { 405 return _range.moveBack(); 406 } 407 408 void popBack() { return _range.popBack(); } 409 410 static if (hasAssignableElements!R) 411 { 412 @property void back(E newVal) { 413 _range.back = newVal; 414 } 415 } 416 } 417 418 static if (isRandomAccessRange!R) 419 { 420 E opIndex(size_t index) { 421 return _range[index]; 422 } 423 424 E moveAt(size_t index) { 425 return _range.moveAt(index); 426 } 427 428 static if (hasAssignableElements!R) 429 { 430 void opIndexAssign(E val, size_t index) { 431 _range[index] = val; 432 } 433 } 434 435 static if (!isInfinite!R) 436 { 437 @property size_t length() { 438 return _range.length; 439 } 440 441 alias opDollar = length; 442 443 // Can't support slicing until all the issues with 444 // requiring slicing support for finite random access 445 // ranges are resolved. 446 version (none) 447 { 448 typeof(this) opSlice(size_t lower, size_t upper) { 449 return new typeof(this)(_range[lower .. upper]); 450 } 451 } 452 } 453 } 454 455 // Optimization: One delegate call is faster than three virtual 456 // function calls. Use opApply for foreach syntax. 457 int opApply(scope int delegate(E) dg) { 458 int res; 459 460 for (auto r = _range; !r.empty; r.popFront()) 461 { 462 res = dg(r.front); 463 if (res) break; 464 } 465 466 return res; 467 } 468 469 int opApply(scope int delegate(size_t, E) dg) { 470 int res; 471 472 size_t i = 0; 473 for (auto r = _range; !r.empty; r.popFront()) 474 { 475 res = dg(i, r.front); 476 if (res) break; 477 i++; 478 } 479 480 return res; 481 } 482 } 483 } 484 } 485 486 /**Convenience function for creating an `InputRangeObject` of the proper type. 487 * See $(LREF InputRange) for an example. 488 */ 489 InputRangeObject!R inputRangeObject(R)(R range) 490 if (isInputRange!R) 491 { 492 static if (is(R : InputRange!(ElementType!R))) 493 { 494 return range; 495 } 496 else 497 { 498 return new InputRangeObject!R(range); 499 } 500 } 501 502 /**Convenience function for creating an `OutputRangeObject` with a base range 503 * of type `R` that accepts types `E`. 504 */ 505 template outputRangeObject(E...) { 506 507 /// 508 OutputRangeObject!(R, E) outputRangeObject(R)(R range) { 509 return new OutputRangeObject!(R, E)(range); 510 } 511 } 512 513 /// 514 @safe unittest 515 { 516 import std.array; 517 auto app = appender!(uint[])(); 518 auto appWrapped = outputRangeObject!(uint, uint[])(app); 519 static assert(is(typeof(appWrapped) : OutputRange!(uint[]))); 520 static assert(is(typeof(appWrapped) : OutputRange!(uint))); 521 } 522 523 @system unittest 524 { 525 import std.algorithm.comparison : equal; 526 import std.array; 527 import std.internal.test.dummyrange; 528 529 static void testEquality(R)(iInputRange r1, R r2) { 530 assert(equal(r1, r2)); 531 } 532 533 auto arr = [1,2,3,4]; 534 RandomFiniteAssignable!int arrWrapped = inputRangeObject(arr); 535 static assert(isRandomAccessRange!(typeof(arrWrapped))); 536 // static assert(hasSlicing!(typeof(arrWrapped))); 537 static assert(hasLength!(typeof(arrWrapped))); 538 arrWrapped[0] = 0; 539 assert(arr[0] == 0); 540 assert(arr.moveFront() == 0); 541 assert(arr.moveBack() == 4); 542 assert(arr.moveAt(1) == 2); 543 544 foreach (elem; arrWrapped) {} 545 foreach (i, elem; arrWrapped) {} 546 547 assert(inputRangeObject(arrWrapped) is arrWrapped); 548 549 foreach (DummyType; AllDummyRanges) 550 { 551 auto d = DummyType.init; 552 static assert(propagatesRangeType!(DummyType, 553 typeof(inputRangeObject(d)))); 554 static assert(propagatesRangeType!(DummyType, 555 MostDerivedInputRange!DummyType)); 556 InputRange!uint wrapped = inputRangeObject(d); 557 assert(equal(wrapped, d)); 558 } 559 560 // Test output range stuff. 561 auto app = appender!(uint[])(); 562 auto appWrapped = outputRangeObject!(uint, uint[])(app); 563 static assert(is(typeof(appWrapped) : OutputRange!(uint[]))); 564 static assert(is(typeof(appWrapped) : OutputRange!(uint))); 565 566 appWrapped.put(1); 567 appWrapped.put([2, 3]); 568 assert(app.data.length == 3); 569 assert(equal(app.data, [1,2,3])); 570 }