group sortedness invariance

bearophile bearophileHUGS at lycos.com
Thu Feb 28 07:46:03 PST 2013


In a program I'd like to perform binary searches on a random 
access range similar to r4, the result of a sort.group.array:


import std.algorithm: sort, group;
import std.array: array;
void main() {
     auto data = [10, 3, 1, 2, 11, 1, 3, 10];
     auto r1 = sort(data);
     pragma(msg, typeof(r1)); // SortedRange!(int[], "a < b")
     auto r2 = array(r1);
     pragma(msg, typeof(r2)); // int[]
     auto r3 = group(r1);
     pragma(msg, typeof(r3)); // Group!("a == b", 
SortedRange!(int[], "a < b"))
     auto r4 = array(r3);
     pragma(msg, typeof(r4)); // Tuple!(int, uint)[]
}


In this program r4 is a Tuple!(int,uint)[]. But I'd like r4 to be 
something like a SortedRange!(int[],"a < b").

To convert r4 to a SortedRange there is the assumeSorted, that 
performs a bit of tests. But assumeSorted should not be needed 
because group doesn't break the property of being sorted.

So what I'd like is a function similar to array(), that fed with 
a lazy Group!SortedRange returns a proper eager SortedRange. Or 
maybe just an agroup() function that returns an eager 
SortedRange. Do you have ideas?

Bye,
bearophile


More information about the Digitalmars-d mailing list