www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - group sortedness invariance

reply "bearophile" <bearophileHUGS lycos.com> writes:
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?

Feb 28 2013
parent "bearophile" <bearophileHUGS lycos.com> writes:
Is this ER going to somehow help?


Feb 28 2013