Segmented Ranges?

[bearophile]

Often enough you have to perform operations on some non-flat 
sequence, like on a 2D matrix:

import std.stdio;
void main() {
     auto m1 = [[], [2, 5], [], [10, 20], [], [], [30, 40, 50]];
     foreach (row; m1)
         foreach (x; row)
             writeln(x);
}


Such multi-level ranges are common. But a Range (below an Input 
Range) that works on a generic multi level Range is slower than 
the two nested for loops because it needs to keep attention to 
the exhaustion of the sub-ranges at every iteration (see 
popFront):


import std.stdio, std.traits, std.array, std.range, std.algorithm;

struct BilevelScan(Range) {
     private Range range;
     typeof(range.front) currentSegment;

     this(Range range_) {
         this.range = range_;
         _nextItem();
     }

     @property bool empty() {
         return range.empty && currentSegment.empty;
     }

     @property auto front() {
         return currentSegment.front;
     }

     void popFront() {
         currentSegment.popFront();
         _nextItem();
     }

     private void _nextItem() {
         while (!range.empty && currentSegment.empty) {
             currentSegment = range.front;
             range.popFront();
         }
     }
}

void main() { // some test code
     auto m1 = [[], [2, 5], [], [10, 20], [], [], [30, 40, 50]];

     foreach (x; BilevelScan!(typeof(m1))(m1))
         writeln(x);
     writeln(m1, "\n");

     auto m2 = [[10.5]];
     foreach (x; BilevelScan!(typeof(m2))(m2))
         writeln(x);
     writeln(m2, "\n");

     auto m3 = 6.iota().map!(i => iota(10 ^^ i + i, 10 ^^ i + i + 
3))();
     foreach (x; BilevelScan!(typeof(m3))(m3))
         writeln(x);
     writeln(m3, "\n");
}



In the paper "Segmented Iterators and Hierarchical Algorithms" 
Matthew H. Austern offers a solution to regain the lost 
efficiency:
http://


Some quotations from the paper:

>segmented data structures are common. Within the STL, for 
>example, the deque container is typically implemented as a 
>segmented array, and hash tables [6] are typically implemented 
>as arrays of buckets. Other examples of segmentation include 
>two-dimensional matrices, graphs, files in record-based file 
>systems, and, on modern NUMA (non-uniform memory architecture) 
>multiprocessor machines, even ordinary memory.<

>A segmented iterator has the same associated types as any other 
>iterator (a value type, for example), and, additionally, it has 
>an associated segment iterator type and local iterator type. 
>Writing a generic algorithm that uses segmented iterators 
>requires the ability to name those types. Additionally, a fully 
>generic algorithm ought to be usable with both segmented and 
>nonsegmented iterators.<

>The distinction between segmented and nonsegmented iterators is 
>orthogonal to the distinction between Forward Iterators, 
>Bidirectional Iterators, and Random Access Iterators.<

>Multiple levels of segmentation can be used with no extra 
>effort. Nothing in this discussion, or this implementation of 
>fill, assumes that the local iterator is nonsegmented.<

>Segmented iterators, an extension of ordinary STL iterators, 
>make it possible for generic algorithms to treat a segmented 
>data structure as something other than a uniform range of 
>elements. This allows existing algorithms to operate more 
>efficiently on segmented data structures, and provides a natural 
>decomposition for parallel computation. Segmented iterators 
>enable new kinds of generic algorithms that explicitly depend on 
>segmentation.<


In D the concept of Input Range is defined as a type that 
statically supports (there is also some necessary semantics that 
can't be expressed in the D code of such concepts):

R r;              // can define a range object
if (r.empty) {}   // can test for empty
r.popFront();     // can invoke popFront()
auto h = r.front; // can get the front of the range of non-void 
type



So an idea is to introduce in D the multi-level Ranges:
SegmentedInputRange
SegmentedOutputRange
SegmentedForwardRange
SegmentedBidirectionalRange
SegmentedRandomAccessRange

I think a Segmented Input Range is more complex than an Input 
Range. Inventing such ranges is like finding the miminal set of 
axioms that allow to write down a theorem, that is to efficiently 
implement the normal algorithms. This is not an easy for me, I 
don't know much about this topic.

Bye,
bearophile