1 /** 2 * ae.utils.range 3 * 4 * License: 5 * This Source Code Form is subject to the terms of 6 * the Mozilla Public License, v. 2.0. If a copy of 7 * the MPL was not distributed with this file, You 8 * can obtain one at http://mozilla.org/MPL/2.0/. 9 * 10 * Authors: 11 * Vladimir Panteleev <ae@cy.md> 12 */ 13 14 module ae.utils.range; 15 16 import std.range.primitives; 17 import std.typecons; 18 19 import ae.utils.meta : isDebug; 20 import ae.utils.text.ascii : toDec; 21 22 /// An equivalent of an array range, but which maintains 23 /// a start and end pointer instead of a start pointer 24 /// and length. This allows .popFront to be faster. 25 /// Optionally, omits bounds checking for even more speed. 26 // TODO: Can we make CHECKED implicit, controlled by 27 // -release, like regular arrays? 28 // TODO: Does this actually make a difference in practice? 29 // Run some benchmarks... 30 struct FastArrayRange(T, bool CHECKED=isDebug) 31 { 32 /// Current head and end. 33 T* ptr, end; 34 35 this(T[] arr) 36 { 37 ptr = arr.ptr; 38 end = ptr + arr.length; 39 } /// 40 41 @property T front() 42 { 43 static if (CHECKED) 44 assert(!empty); 45 return *ptr; 46 } /// 47 48 void popFront() 49 { 50 static if (CHECKED) 51 assert(!empty); 52 ptr++; 53 } /// 54 55 @property bool empty() { return ptr==end; } /// 56 57 @property ref typeof(this) save() { return this; } /// 58 59 T opIndex(size_t index) 60 { 61 static if (CHECKED) 62 assert(index < end-ptr); 63 return ptr[index]; 64 } /// 65 66 T[] opSlice() 67 { 68 return ptrSlice(ptr, end); 69 } /// 70 71 T[] opSlice(size_t from, size_t to) 72 { 73 static if (CHECKED) 74 assert(from <= to && to <= end-ptr); 75 return ptr[from..to]; 76 } /// 77 } 78 79 auto fastArrayRange(T)(T[] arr) { return FastArrayRange!T(arr); } /// ditto 80 81 // TODO move to ae.utils.array 82 /// Returns a slice for the memory from `a` to `b`. 83 T[] ptrSlice(T)(T* a, T* b) 84 { 85 return a[0..b-a]; 86 } 87 88 unittest 89 { 90 FastArrayRange!ubyte r; 91 auto x = r.save; 92 } 93 94 // ************************************************************************ 95 96 /// Presents a null-terminated pointer (C-like string) as a range. 97 struct NullTerminated(E) 98 { 99 E* ptr; /// Current head. 100 bool empty() { return !*ptr; } /// 101 ref E front() { return *ptr; } /// 102 void popFront() { ptr++; } /// 103 auto save() { return this; } /// 104 } 105 auto nullTerminated(E)(E* ptr) 106 { 107 return NullTerminated!E(ptr); 108 } /// ditto 109 110 /// 111 unittest 112 { 113 void test(S)(S s) 114 { 115 import std.utf, std.algorithm.comparison; 116 assert(equal(s.byCodeUnit, s.ptr.nullTerminated)); 117 } 118 // String literals are null-terminated 119 test("foo"); 120 test("foo"w); 121 test("foo"d); 122 } 123 124 // ************************************************************************ 125 126 /// Apply a predicate over each consecutive pair. 127 template pairwise(alias pred) 128 { 129 import std.range : zip, dropOne; 130 import std.algorithm.iteration : map; 131 import std.functional : binaryFun; 132 133 auto pairwise(R)(R r) 134 { 135 return zip(r, r.dropOne).map!(pair => binaryFun!pred(pair[0], pair[1])); 136 } 137 } 138 139 /// 140 unittest 141 { 142 import std.algorithm.comparison : equal; 143 assert(equal(pairwise!"a+b"([1, 2, 3]), [3, 5])); 144 assert(equal(pairwise!"b-a"([1, 2, 3]), [1, 1])); 145 } 146 147 // ************************************************************************ 148 149 /// An infinite variant of `iota`. 150 struct InfiniteIota(T) 151 { 152 T front; /// 153 enum empty = false; /// 154 void popFront() { front++; } /// 155 T opIndex(T offset) { return front + offset; } /// 156 InfiniteIota save() { return this; } /// 157 } 158 InfiniteIota!T infiniteIota(T)() { return InfiniteIota!T.init; } /// ditto 159 160 // ************************************************************************ 161 162 /// Empty range of type E. 163 struct EmptyRange(E) 164 { 165 @property E front() { assert(false); } /// 166 void popFront() { assert(false); } /// 167 @property E back() { assert(false); } /// 168 void popBack() { assert(false); } /// 169 E opIndex(size_t) { assert(false); } /// 170 enum empty = true; /// 171 enum save = typeof(this).init; /// 172 enum size_t length = 0; /// 173 } 174 175 EmptyRange!E emptyRange(E)() { return EmptyRange!E.init; } /// ditto 176 177 static assert(isInputRange!(EmptyRange!uint)); 178 static assert(isForwardRange!(EmptyRange!uint)); 179 static assert(isBidirectionalRange!(EmptyRange!uint)); 180 static assert(isRandomAccessRange!(EmptyRange!uint)); 181 182 // ************************************************************************ 183 184 /// Like `only`, but evaluates the argument lazily, i.e. when the 185 /// range's "front" is evaluated. 186 /// DO NOT USE before this bug is fixed: 187 /// https://issues.dlang.org/show_bug.cgi?id=11044 188 auto onlyLazy(E)(lazy E value) 189 { 190 struct Lazy 191 { 192 bool empty = false; 193 @property E front() { assert(!empty); return value; } 194 void popFront() { assert(!empty); empty = true; } 195 alias back = front; 196 alias popBack = popFront; 197 @property size_t length() { return empty ? 0 : 1; } 198 E opIndex(size_t i) { assert(!empty); assert(i == 0); return value; } 199 @property typeof(this) save() { return this; } 200 } 201 return Lazy(); 202 } 203 204 static assert(isInputRange!(typeof(onlyLazy(1)))); 205 static assert(isForwardRange!(typeof(onlyLazy(1)))); 206 static assert(isBidirectionalRange!(typeof(onlyLazy(1)))); 207 static assert(isRandomAccessRange!(typeof(onlyLazy(1)))); 208 209 unittest 210 { 211 import std.algorithm.comparison; 212 import std.range; 213 214 int i; 215 auto r = onlyLazy(i); 216 i = 1; assert(equal(r, 1.only)); 217 i = 2; assert(equal(r, 2.only)); 218 } 219 220 // ************************************************************************ 221 222 /// Defer range construction until first empty/front call. 223 auto lazyInitRange(R)(R delegate() constructor) 224 { 225 bool initialized; 226 R r = void; 227 228 ref R getRange() 229 { 230 if (!initialized) 231 { 232 r = constructor(); 233 initialized = true; 234 } 235 return r; 236 } 237 238 struct LazyRange 239 { 240 bool empty() { return getRange().empty; } 241 auto ref front() { return getRange().front; } 242 void popFront() { return getRange().popFront; } 243 } 244 return LazyRange(); 245 } 246 247 /// 248 unittest 249 { 250 import std.algorithm.iteration; 251 import std.range; 252 253 int[] todo, done; 254 chain( 255 only({ todo = [1, 2, 3]; }), 256 // eager will fail: todo.map!(n => (){ done ~= n; }), 257 lazyInitRange(() => todo.map!(n => (){ done ~= n; })), 258 ).each!(dg => dg()); 259 assert(done == [1, 2, 3]); 260 } 261 262 // ************************************************************************ 263 264 /// A faster, random-access version of `cartesianProduct`. 265 auto fastCartesianProduct(R...)(R ranges) 266 { 267 struct Product 268 { 269 size_t start, end; 270 R ranges; 271 auto front() { return this[0]; } 272 void popFront() { start++; } 273 auto back() { return this[$-1]; } 274 void popBack() { end--; } 275 bool empty() const { return start == end; } 276 size_t length() { return end - start; } 277 alias opDollar = length; 278 279 auto opIndex(size_t index) 280 { 281 auto p = start + index; 282 size_t[R.length] positions; 283 foreach (i, r; ranges) 284 { 285 auto l = r.length; 286 positions[i] = p % l; 287 p /= l; 288 } 289 assert(p == 0, "Out of bounds"); 290 mixin({ 291 string s; 292 foreach (i; 0 .. R.length) 293 s ~= `ranges[` ~ toDec(i) ~ `][positions[` ~ toDec(i) ~ `]], `; 294 return `return tuple(` ~ s ~ `);`; 295 }()); 296 } 297 } 298 size_t end = 1; 299 foreach (r; ranges) 300 end *= r.length; 301 return Product(0, end, ranges); 302 } 303 304 unittest 305 { 306 import std.algorithm.comparison : equal; 307 assert(fastCartesianProduct().length == 1); 308 assert(fastCartesianProduct([1, 2, 3]).equal([tuple(1), tuple(2), tuple(3)])); 309 assert(fastCartesianProduct([1, 2], [3, 4, 5]).equal([ 310 tuple(1, 3), tuple(2, 3), 311 tuple(1, 4), tuple(2, 4), 312 tuple(1, 5), tuple(2, 5), 313 ])); 314 } 315 316 // ************************************************************************ 317 318 /// Calculate the mean value of the range's elements (sum divided by length). 319 /// The range must obviously be non-empty. 320 auto average(R)(R range) if (hasLength!R) 321 { 322 import std.algorithm.iteration : sum; 323 return sum(range) / range.length; 324 } 325 326 unittest 327 { 328 assert([1, 2, 3].average == 2); 329 } 330 331 // ************************************************************************ 332 333 /// `map` variant which takes the predicate as a functor. 334 /// https://forum.dlang.org/post/qnigarkuxxnqwdernhzv@forum.dlang.org 335 struct PMap(R, Pred) 336 { 337 R r; /// Source range. 338 Pred pred; /// The predicate. 339 340 auto ref front() { return pred(r.front); } /// 341 static if (__traits(hasMember, R, "back")) 342 auto ref back() { return pred(r.back); } /// 343 344 alias r this; 345 } 346 auto pmap(R, Pred)(R r, Pred pred) { return PMap!(R, Pred)(r, pred); } /// ditto 347 348 unittest 349 { 350 import std.algorithm.comparison : equal; 351 import std.range : iota; 352 assert(5.iota.pmap((int n) => n + 1).equal([1, 2, 3, 4, 5])); 353 }