Arrays and slices

Array<T> is Pepper’s growable list. Beyond append, indexing and sort, it has the everyday algorithms, and slice gives a function “some of the elements” without copying them:

total(values: ArraySlice<int>): int {
    var sum = 0;
    for (var x in values) {
        sum = sum + x;
    }
    return sum;
}

main(): int {
    # Searching a sorted array.
    var sorted = [1, 3, 3, 5, 8];
    assert(sorted.is_sorted(), "sorted");
    assert(sorted.binary_search(5).value() == 3, "found at 3");
    assert(sorted.binary_search(4).is_empty(), "no 4");
    assert(sorted.upper_bound(3) - sorted.lower_bound(3) == 2, "two 3s");

    # Changing elements in place.
    var a = [4, 4, 1, 2, 2, 7];
    a.dedup();
    assert(a == [4, 1, 2, 7], "adjacent repeats removed");
    a.retain((x) => x % 2 == 0);
    assert(a == [4, 2], "odd elements removed");
    a.resize(4, 0);
    assert(a == [4, 2, 0, 0], "padded with 0");
    var tail = a.split_off(2);
    assert(a == [4, 2] && tail == [0, 0], "split in two");
    tail.fill(9);
    assert(tail == [9, 9], "filled");

    # A slice views part of an array without copying it.
    var numbers = [1, 2, 3, 4, 5];
    var middle = numbers.slice(1, 4);
    assert(middle.count == 3 && middle[0] == 2, "views [2, 3, 4]");
    assert(total(middle) == 9, "passed to a function");
    assert(middle.to_array() == [2, 3, 4], "copied out");
    return 0;
}

Searching a sorted array

• binary_search(item) returns the index of the first element equal to item as a ulong?, in O(log count). The element type must be Comparable (every number, char and String is), and the array sorted in its compare order.
• binary_search_by(order) searches with a function that says whether an element sorts before (negative), at (0) or after (positive) the target.
• lower_bound(item) and upper_bound(item) are the first and last places item could be inserted to keep the array sorted; the elements between them equal item.
• is_sorted() reports whether the array is in that order.

Changing elements in place

• fill(value) sets every element to value.
• retain(keep) removes each element keep returns false for, keeping the order of the rest. keep must not change the array; if it does, retain panics with Array modified during retain.
• dedup() removes each element equal (==) to the one before it; on a sorted array that removes every duplicate.
• resize(count, value) shortens the array, or appends copies of value.
• split_off(index) moves the elements from index on into a new array.

Each counts as modifying the array, so a for loop over it panics on its next step.

Slices

a.slice(start, end) is an ArraySlice<T>: a read-only view of the elements from start up to but not including end. It has count, is_empty, indexing, for loops, slice, to_array, find, contains and the searches above.

A slice is safe by construction:

• It holds a reference to its array, so the array lives as long as the slice does.
• It is fail-fast, like an iterator. Once the array changes (any store, append, remove_at, sort, …), every later use of the slice panics with Array modified while a slice of it is in use, so it can never read an element that moved or a buffer that was freed. Make a new slice after changing the array.

Not yet

• Slices are read-only; there is no slice that writes through to its array, and no a[1..4] syntax: write a.slice(1, 4).
• sort takes a comparer (a.sort((x, y) => x.compare(y))); a sort() with none, sort_unstable, rotate, drain, chunks and windows are not there yet.
• String has no slice type; substr copies.