std/indexable

pub trait Indexable
  type Elem
  # Returns the element at the given index. Negative indices count from the
  # end, so `a[-1]` returns the last element. Raises when index is out of
  # bounds, naming the index as it was written and the size there was:
  # `index out of range` on its own told a caller with a computed index
  # nothing it did not already know. The wording is `Array`'s
  # (src/iyi/array.iyi), because one mistake gets one sentence.
  def [](index : Int32) : Elem
  # Returns the element at the given index, or nil when index is out of bounds.
  # Negative indices count from the end.
  def []?(index : Int32) : Elem | ::Nil
  # Binary search on a sorted collection. Returns the first element for which
  # the block returns true, or nil if no element matches.
  def bsearch(& : (Elem -> Bool)) : Elem | ::Nil
  # Binary search returning the index of the first element for which the block
  # returns true, or nil.
  def bsearch_index(& : (Elem -> Bool)) : Int32 | ::Nil
  # Single-index navigation.
  def dig(index : Int32) : Elem
  # Single-index nilable navigation.
  def dig?(index : Int32) : Elem | ::Nil
  # Default iteration yielding elements sequentially from 0 up to size - 1.
  # It answers `Enumerable`'s requirement for a type that also says `impl
  # Enumerable`, which is one more line than the ergonomics claim implies
  # (SPEC.md II.6) — the claim that this trait supplied it was false, and
  # `Array` went without `zip`, `take` and the rest until the line existed.
  def each(& : (Elem -> Nil)) : Nil
  # Yields consecutive overlapping windows of n elements each.
  def each_cons(n : Int32, & : (Array(Elem) -> Nil)) : Nil
  # Returns an Array of consecutive overlapping windows of n elements each.
  def each_cons(n : Int32) : Array(Array(Elem))
  # Yields each valid index from 0 up to size - 1.
  def each_index(& : (Int32 -> Nil)) : Nil
  # Yields slices of n elements each to the given block.
  def each_slice(n : Int32, & : (Array(Elem) -> Nil)) : Nil
  # Returns an Array of slices of n elements each.
  def each_slice(n : Int32) : Array(Array(Elem))
  # Returns true when the collection contains no elements.
  def empty? : Bool
  # Structural equality comparing collection size and element values.
  def equals?(other : self) : Bool
  # Structural equality comparing elements with a custom predicate block.
  def equals?(other : self, & : (Elem, Elem -> Bool)) : Bool
  # Returns the element at index. If out of bounds, returns the default value.
  def fetch(index : Int32, default : Elem) : Elem
  # Returns the element at index. If out of bounds, yields the original index
  # to the given block and returns its result.
  def fetch(index : Int32, & : (Int32 -> Elem)) : Elem
  # Returns the first element. Raises when the collection is empty.
  def first : Elem
  # Returns the first element, or nil when the collection is empty.
  def first? : Elem | ::Nil
  # Combines the elements' hashes. Wrapping arithmetic, because a hash is a
  # number modulo the word and nothing else: written with the checked `*` and
  # `+`, this panicked with "arithmetic overflow" the moment a collection was
  # long enough for `31 * h` to leave `Int32` - six elements of two digits
  # each was enough, while the five-element cases in the gates passed.
  #
  # Mixed as the prelude's `Array#hash` is, which is also what keeps an
  # array's and another indexable's hashes one function: `31 * h + e` gave
  # a grid of pairs a few hashes between many, and a table probing a slot
  # at a time merged their runs.
  def hash : Int32
  # Returns the first index where element equals value, or nil if not found.
  def index(value : Elem) : Int32 | ::Nil
  # Returns the first index for which the block returns true, or nil.
  def index(& : (Elem -> Bool)) : Int32 | ::Nil
  # Joins element string representations with the specified separator.
  #
  # Into one builder, as `Array#join` writes: adding each element to the
  # text so far copied that text once per element, and 20,000 elements
  # took 1.8 s where the same array's `join` took 1 ms.
  def join(separator : String = "") : String
  # Returns the last element. Raises when the collection is empty.
  def last : Elem
  # Returns the last element, or nil when the collection is empty.
  def last? : Elem | ::Nil
  # Yields elements in reverse order, from size - 1 down to 0.
  def reverse_each(& : (Elem -> Nil)) : Nil
  # Returns the last index where element equals value, or nil if not found.
  def rindex(value : Elem) : Int32 | ::Nil
  # Returns the last index for which the block returns true, or nil.
  def rindex(& : (Elem -> Bool)) : Int32 | ::Nil
  # One element, or *n* distinct ones, chosen by `random`, a fresh generator
  # when none is given, the way std/random's `Array#sample` chooses them:
  # so a `Deque` makes the other library's choices in its order, as an
  # array does. `sample(Int32)` was a seed here and a count there, so
  # `[10, 20, 30, 40, 50].sample(3)` answered 20 without std/random and
  # three elements with it, a `Deque`'s answered 20 either way, and
  # `sample` answered the middle element on every run.
  def sample(random : Random | ::Nil = nil) : Elem
  def sample(n : Int32, random : Random | ::Nil = nil) : Array(Elem)
  # Returns a sample element using the index returned by the caller's block.
  def sample(& : (Int32 -> Int32)) : Elem
  abstract def size : Int32
  # Copies elements into a newly allocated Array with pre-allocated capacity.
  def to_a : Array(Elem)
  abstract def unsafe_fetch(index : Int32) : Elem
  # Returns an Array containing elements at the given indices array.
  def values_at(indexes : Array(Int32)) : Array(Elem)
  # Returns an Array containing elements at the given indices.
  def values_at(*indexes : Int32) : Array(Elem)
end

pub trait IndexableMutable : ::Std::Indexable::Indexable
  type Elem
  # The count elements from offset become value. A negative count is a
  # mistake; a window that runs past the end is refused by naming the
  # index that would have been written.
  def fill(value : Elem, offset : Int32, count : Int32) : self
  # Every element becomes value.
  def fill(value : Elem) : self
  # Every element becomes what the block answers for its index.
  def fill(& : (Int32 -> Elem)) : self
  # Reverses elements in place.
  def reverse_in_place : self
  # Rotates elements in place so that the element at position n comes
  # first; a negative n rotates the other way. Three reversals, no
  # scratch space.
  def rotate_in_place(n : Int32 = 1) : self
  # Swaps two elements in place.
  def swap(index0 : Int32, index1 : Int32) : self
  abstract def unsafe_put(index : Int32, value : Elem) : Elem
  # Replaces the element at index with what the block answers for it,
  # and answers the new value.
  def update(index : Int32, & : (Elem -> Elem)) : Elem
end

impl Indexable for Array(T) forall T
  def unsafe_fetch(index : Int32) : T
end

impl IndexableMutable for Array(T) forall T
  def unsafe_put(index : Int32, value : T) : T
end

class ::Array(T)
  # Every pair with an element of the other array, this array's order
  # first. Not `product`: on an `Enumerable`, `product` is the
  # multiplicative fold, and one name means one thing.
  def cartesian(other : Array(U)) : Array(Tuple(T, U)) forall U
  # Forgets every element.
  def clear : Array(T)
  # Removes the nils in place.
  def compact_in_place : Array(T)
  # Removes and answers the element at index, shifting what follows left.
  def delete_at(index : Int32) : T
  # Removes every element the block answers true for, in place, keeping
  # the order of the rest; one pass, no per-element shifting.
  def delete_if(& : (T -> Bool)) : Array(T)
  # The same pairs, handed to a block in the same order, with no array of
  # them made - the other library's `each_cartesian`.
  def each_cartesian(other : Array(U), & : (T, U -> _)) : Nil forall U
  # Inserts value at index, shifting what follows right. An index of
  # `size` appends; `-1` also appends, as the position after the last.
  def insert(index : Int32, value : T) : Array(T)
  # Keeps only the elements the block answers true for, in place.
  def keep_if(& : (T -> Bool)) : Array(T)
  # A copy rotated so that the element at position n comes first; the
  # past participle names the copy, as `sorted` and `reversed` do, and
  # `rotate_in_place` is the one that moves this array.
  def rotated(n : Int32 = 1) : Array(T)
end