1 module vest.range.expand_nested; 2 3 import std.range : empty, popFront, front, isInputRange, ElementType; 4 import std.functional : forward; 5 import std.traits : isNarrowString, Unqual; 6 7 // Recursive expands nested iterators 8 auto expandNested(size_t depth = 1, Range)(auto ref Range range) 9 if (isInputRange!Range) 10 { 11 static if(depth > 1) { 12 return expandNested!(depth - 1)( Expander!Range(forward!range) ); 13 } else { 14 return Expander!Range(forward!range); 15 } 16 } 17 18 auto expandRecursively(Range)(auto ref Range range) 19 if (isInputRange!Range) 20 { 21 alias nested_t = ElementType!Range; 22 23 static if(isInputRange!nested_t && !isNarrowString!nested_t) 24 { 25 return expandRecursively( Expander!Range(forward!range) ); 26 } else { 27 return range; 28 } 29 } 30 31 private struct Expander(Range) 32 { 33 private: 34 alias nested_t = Unqual!(typeof(Range.init.front)); 35 Range range; 36 nested_t nested; 37 public: 38 39 this(Range range) 40 { 41 this.range = range; 42 if(!range.empty) { 43 nested = range.front; 44 } else { 45 // if range is empty initialize nested by default 46 nested = typeof(range.front).init; 47 } 48 } 49 50 @property 51 bool empty() 52 { 53 if(range.empty()) { 54 return true; 55 } 56 57 // Until as the nested iterator is empty, 58 // go to the next non-empty nested iterator 59 while(nested.empty) { 60 range.popFront(); 61 if(range.empty()) { 62 return true; 63 } 64 nested = range.front; 65 } 66 67 return false; 68 } 69 70 @property 71 auto front() 72 { 73 assert(!range.empty); 74 assert(!nested.empty); 75 return nested.front; 76 } 77 78 void popFront() 79 { 80 nested.popFront(); 81 if(nested.empty) { 82 range.popFront(); 83 if(!range.empty) { 84 nested = range.front; 85 } 86 } 87 } 88 } 89 90 91 //////////////////////////////////////////////// 92 93 // cd source 94 // rdmd -unittest -main vest/range/expand_nested 95 96 nothrow unittest { 97 import std.range : iota; 98 import std.algorithm : map; 99 import std.array : array; 100 101 assert(iota(20, 25, 1) 102 .map!(x => iota(21, x, 1)) 103 .expandNested 104 .array == [21, 21, 22, 21, 22, 23]); 105 106 assert(iota(20, 25, 1) 107 .map!(x => iota(19, x, 1)) 108 .expandNested 109 .array == [19, 19, 20, 19, 20, 21, 19, 20, 21, 22, 19, 20, 21, 22, 23]); 110 111 assert(iota(20, 25, 1) 112 .map!(x => iota(20, x, 1)) 113 .expandNested 114 .array == [20, 20, 21, 20, 21, 22, 20, 21, 22, 23]); 115 116 assert(iota(1, 6, 1) 117 .map!(x => [1,2]) 118 .expandNested 119 .array == [1, 2, 1, 2, 1, 2, 1, 2, 1, 2]); 120 121 assert([ 122 [1,2], 123 [3,4], 124 [5,6,7] 125 ].expandNested 126 .array == [1, 2, 3, 4, 5, 6, 7]); 127 128 assert([ 129 [1,2], 130 [], 131 [], 132 [3,4], 133 [], 134 [5,6,7] 135 ].expandNested 136 .array == [1, 2, 3, 4, 5, 6, 7]); 137 138 assert([ 139 [1,2], 140 [], 141 [3,4], 142 [5,6,7] 143 ].expandNested 144 .array == [1, 2, 3, 4, 5, 6, 7]); 145 146 assert([ 147 [], 148 [], 149 [1,2], 150 [], 151 [], 152 [3,4], 153 [], 154 [5,6,7], 155 [] 156 ].expandNested 157 .array == [1, 2, 3, 4, 5, 6, 7]); 158 159 assert([ 160 [ 161 [1,2], 162 [3,4], 163 ],[ 164 [5,6,7], 165 [8,9], 166 ],[ 167 [], 168 [], 169 [], 170 [10,11,12], 171 ] 172 ].expandNested 173 .array == [[1, 2], [3, 4], [5, 6, 7], [8, 9], [], [], [], [10, 11, 12]]); 174 175 assert([ 176 [ 177 [1,2], 178 [3,4], 179 ],[ 180 [5,6,7], 181 [8,9], 182 ],[ 183 (int[]).init, 184 [], 185 ],[ 186 ],[ 187 [], 188 ],[ 189 [], 190 [], 191 [], 192 [10,11,12], 193 ] 194 ].expandNested 195 .array == [[1, 2], [3, 4], [5, 6, 7], [8, 9], [], [], [], [], [], [], [10, 11, 12]]); 196 197 assert([ 198 [ 199 [1,2], 200 [3,4], 201 ],[ 202 [5,6,7], 203 [8,9], 204 ],[ 205 [], 206 [], 207 [], 208 [10,11,12], 209 ] 210 ].expandNested.expandNested 211 .array == [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]); 212 213 assert([ 214 [], 215 [ 216 [1,2], 217 [3,4], 218 ],[ 219 [5,6,7], 220 [8,9], 221 ],[ 222 (int[]).init, 223 [], 224 ],[ 225 ],[ 226 [], 227 ],[ 228 [], 229 [], 230 [], 231 [10,11,12], 232 [], 233 ], 234 [], 235 ].expandNested.expandNested 236 .array == [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]); 237 238 239 // Deep nesting 240 assert([ 241 [ 242 [1,2], 243 [3,4], 244 ],[ 245 [5,6,7], 246 [8,9], 247 ],[ 248 [], 249 [], 250 [], 251 [10,11], 252 ] 253 ].expandNested!2 254 .array == [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]); 255 256 assert([ 257 [ 258 [ 259 [1,2], 260 [3,4], 261 ],[ 262 [5,6,7], 263 [8,9], 264 ] 265 ],[ 266 [ 267 [1,2], 268 [3,4], 269 ],[ 270 [5,6,7], 271 [8,9], 272 ] 273 ] 274 ].expandNested!3 275 .array == [1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 2, 3, 4, 5, 6, 7, 8, 9]); 276 277 278 // Expand nesting recursively 279 assert([ 280 [ 281 [1,2], 282 [3,4], 283 ],[ 284 [5,6,7], 285 [8,9], 286 ],[ 287 [], 288 [], 289 [10,11], 290 ] 291 ].expandRecursively 292 .array == [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11] ); 293 294 295 296 assert([ 297 [ 298 [ 299 [1,2], 300 [3,4], 301 ],[ 302 [5,6,7], 303 [8,9], 304 ] 305 ],[ 306 [ 307 [10,11], 308 [], 309 [12], 310 ] 311 ] 312 ].expandRecursively 313 .array == [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12] ); 314 315 assert([[[[[[[[ 316 ["hellow"], 317 [], 318 ["world"], 319 ]]]]]]]].expandRecursively 320 .array == ["hellow", "world"] ); 321 322 { 323 const(int)[][] arr = [[], [21], [21, 22], [21, 22, 23]]; 324 assert(arr.expandNested.array == [21, 21, 22, 21, 22, 23]); 325 }{ 326 const(int[])[] arr = [[], [21], [21, 22], [21, 22, 23]]; 327 assert(arr.expandNested.array == [21, 21, 22, 21, 22, 23]); 328 } 329 }