language: D (dmd) (dmd-2.042)
date: 595 days 21 hours ago
link:
visibility: private 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

import std.stdio, std.algorithm, std.random, std.array, std.range, std.traits;
 
// To add: less and SwapStrategy template arguments.
struct LazySort(Range) if (isRandomAccessRange!Range) {
    Range data;
    private size_t idx, idxSorted;
 
    bool empty() { return idx >= data.length; }
 
    ForeachType!Range front() {
        if (idx >= idxSorted) {
            immutable oldIdxSorted = idxSorted;
            idxSorted = min(data.length, idxSorted ? (idxSorted * 2) : 1);
            partialSort(data[oldIdxSorted .. $], idxSorted - oldIdxSorted);
        }
        return data[idx];
    }
 
    void popFront() { idx++; }
}
 
void main() {
    auto A = array(iota(25));
    randomShuffle(A);
    writeln(A);
 
    foreach (x; LazySort!(int[])(A))
        write(x, " ");
}