Scan

// `Fold` collapses a slice into one answer: the total of a month's sales. A scan keeps every
// step of the way instead: the total so far after each day. That running answer is a slice of
// its own, as long as the input, and it answers questions a single total cannot — when did the
// sales pass 100, what was the best day up to Friday, where does record 4 start in a file.
//
// `PartialSum` writes the running sums; `InclusiveScan` does the same with any combining function;
// `ExclusiveScan` writes, at each place, the combination of everything *before* it. All three
// write into a writable slice that you supply, which may be the input itself, and refuse one that
// is too short by returning false. `Iota` fills a slice with a counting sequence.
//
// `Midpoint` finds the number halfway between two others. That sounds like `(a + b) / 2`, but
// the sum can be too large for the type even when the answer is not, and then it wraps round to
// a nonsense value. `Midpoint` never forms the sum, so it is right for any two values.
import Algorithms::{ ExclusiveScan, InclusiveScan, Iota, Midpoint, PartialSum };
import Io::{ Print, PrintLine };

func Larger(left: int32, right: int32) -> int32 {
    return left > right ? left : right;
}

func Add(left: int32, right: int32) -> int32 {
    return left + right;
}

func Show(label: char8[..], values: int32[..]) {
    Print("{:<10}", label);
    for value in values {
        Print("{:>5}", value);
    }
    PrintLine();
}

func Main() -> int {
    // A week's sales, and the day numbers 1 to 7 to label them: start at 1, step by 1.
    let sales: int32[7] = [12, 30, 7, 25, 18, 40, 9];
    var days: int32[7] = [0; 7];
    Iota<int32>(days[..], 1, 1);
    Show("day", days[..]);
    Show("sales", sales[..]);

    // The total so far after each day.
    var total: int32[7] = [0; 7];
    PartialSum<int32>(sales[..], total[..]);
    Show("total", total[..]);

    // The best day so far: the same scan, combining with `Larger` instead of `+`.
    var best: int32[7] = [0; 7];
    InclusiveScan<int32>(sales[..], best[..], Larger);
    Show("best", best[..]);

    // Records of these lengths sit one after another in a file. Where does each start? At the
    // sum of the lengths before it — an exclusive scan from 0.
    let lengths: int32[4] = [14, 6, 22, 10];
    var offsets: int32[4] = [0; 4];
    ExclusiveScan<int32>(lengths[..], offsets[..], 0, Add);
    Show("length", lengths[..]);
    Show("offset", offsets[..]);

    // A destination too short is refused, and left as it was.
    var short: int32[3] = [0; 3];
    PrintLine("fits in 3? {}", PartialSum<int32>(sales[..], short[..]));

    // Halfway between two large positions. Their sum, 4100000000, does not fit in an `int32`, so
    // `(low + high) / 2` wraps round to a negative number. `Midpoint` takes the distance between
    // them instead — always representable as a `uint32` — and adds half of it to `low`.
    let low: int32 = 2000000000;
    let high: int32 = 2100000000;
    PrintLine("(low + high) / 2  {}", (low + high) / 2);
    PrintLine("Midpoint          {}", Midpoint(low, high));

    // With an odd distance there is no exact middle; integers round towards the first argument.
    // There is one `Midpoint` per type, so a bare literal, which several of them accept, needs
    // its type written:
    //
    //     Midpoint(3, 8)
    //         error: call to 'Midpoint' is ambiguous: 4 overloads accept argument types (int, int)
    PrintLine("Midpoint(3, 8) {}", Midpoint(3i32, 8i32));
    PrintLine("Midpoint(8, 3) {}", Midpoint(8i32, 3i32));
    return 0;
}