Array

class Array(T)

  # The elements in both, each once, in this array's order. Taking a value
  # out of the table as it is kept is what keeps it once.
  def &(other : Array(T)) : Array(T)

  # This array *times* times over, one after the other: `[1, 2] * 2` is
  # `[1, 2, 1, 2]`, and zero times is empty.
  def *(times : Int32) : Array(T)

  # The two in order, as a new array; neither operand changes.
  def +(other : Array(T)) : Array(T)

  # The elements not in *other*, duplicates and order kept: `[1, 1, 2, 3] -
  # [2]` is `[1, 1, 3]`. Equality is `==`, asked of a table when *other* is
  # long enough for a search of it per element to cost more than building
  # one, as the other library decides at sixteen.
  def -(other : Array(T)) : Array(T)

  def <<(value : T) : Array(T)

  def ==(other : Array(T)) : Bool

  # `a[1, 2]`: *count* elements from *start*, or as many as there are. A
  # start that wraps below zero or lies past the end is refused, as an index
  # is; a start of exactly `size` is the empty tail, `[]`, as in the other
  # library, because the position after the last is where an append goes.
  def [](start : Int32, count : Int32) : Array(T)

  # A negative index counts from the end, so `a[-1]` is the last element.
  # Still out of range after that wrap (or empty) raises, same message.
  def [](index : Int32) : T

  # `a[1..2]`, `a[1...-1]`, `a[2..]`, `a[..1]`: either end may be negative,
  # and an end past the last element stops at it. The start is held to what
  # `[](start, count)` holds it to, so `[1, 2, 3][3..]` is `[]` and
  # `[1, 2, 3][4..]` is refused: a range that begins outside the array asks
  # about elements that are not there.
  def [](range : Range(B, E)) : Array(T) forall B, E

  def []=(start : Int32, count : Int32, values : Array(T)) : Array(T)

  # `a[1, 2] = x` puts one element where the span was, and `a[1, 2] = [x,
  # y, z]` puts all of them there: the array grows or shrinks by the
  # difference, as the other library's does. A start of `size` appends.
  def []=(start : Int32, count : Int32, value : T) : T

  def []=(index : Int32, value : T) : T

  def []=(range : Range(B, E), values : Array(T)) : Array(T) forall B, E

  def []=(range : Range(B, E), value : T) : T forall B, E

  # The same span, or nil where `[]` would refuse the start. A negative
  # count is a mistake in the call rather than an answer about this array,
  # and is refused by both.
  def []?(start : Int32, count : Int32) : Array(T) | ::Nil

  def []?(index : Int32) : T | ::Nil

  def []?(range : Range(B, E)) : Array(T) | ::Nil forall B, E

  def all?(& : (T -> Bool)) : Bool

  def any?(& : (T -> Bool)) : Bool

  # The elements that are not nil, in an array whose type says so: what a
  # list of `to_i?` answers becomes once the failures are dropped.
  def compact

  # `a.concat(a)` is a doubling, not a loop: `each` walked *other*'s growing
  # size while `<<` grew it, so `[1, 2].concat(itself)` grew the buffer until
  # the capacity arithmetic overflowed. The length is read once.
  def concat(other : Array(T)) : Array(T)

  # The questions a list gets asked with one answer. `find` answers nil
  # when none does, the way Crystal's does and `index` below already did.
  def count(& : (T -> Bool)) : Int32

  # Every element equal to `value` out, answering the last or nil, as the
  # other library's: it took the first alone, `[1, 2, 1]` left `[2, 1]`.
  def delete(value : T) : T | ::Nil

  def dup : Array(T)

  def each(& : (T -> Nil)) : Nil

  def each_with_index(& : (T, Int32 -> Nil)) : Nil

  def empty? : Bool

  def find(& : (T -> Bool)) : T | ::Nil

  # The first `n`, or all of them when there are fewer: a prefix, not a
  # question, so it never panics.
  def first(n : Int32) : Array(T)

  # `first` on an empty array is a mistake rather than a nil: the array knows
  # it is empty and so does whoever wrote the call. `last?` above answers the
  # other question, and is the one the trait defaults use.
  def first : T

  # And the nilable question beside it, as `last?` is beside `last`: without
  # an import a program had `last?` and not `first?`.
  def first? : T | ::Nil

  # Every element that is not an array, from every array nested inside at
  # any depth, in the order they are written: `[[1, [2]], 3]` is `[1, 2,
  # 3]`. The element type is computed the same way, through every level, so
  # `[[1], [[2]]].flatten` is an `Array(Int32)`.
  def flatten

  # Hashing follows `==`, mixed as a tuple's members are (object.iyi): an
  # array writes `==`, so `Reference#hash` answered its type's id and every
  # array key shared one slot - 40,000 of them took 1.2 s to insert.
  def hash : Int32

  def includes?(value : T) : Bool

  # Where a value first is, or nil.
  def index(value : T) : Int32 | ::Nil

  def inspect : String

  def join(separator : String) : String

  # Here rather than on `Enumerable`: the trait is iyi's, written in
  # `src/std`, and every one of its methods that returns a sequence
  # returns one of these. So an `Array` is what a sample ends up holding, and
  # `join` is what it ends up calling.
  # With nothing between: `["a", "b"].join` is `"ab"`.
  def join : String

  # The last `n`, in their order, or all of them when there are fewer.
  def last(n : Int32) : Array(T)

  # `last` on an empty array is a mistake rather than a nil, as `first` is.
  def last : T

  def last? : T | ::Nil

  def map(& : (T -> U)) : Array(U) forall U

  # The element whose key is largest, or smallest, the first of equals; a
  # NaN key is above every other, as `<=>` places it. Empty is a mistake.
  def max_by(& : (T -> U)) : T forall U

  def min_by(& : (T -> U)) : T forall U

  def new(capacity : Int32)

  def new

  # Removes and returns the last element. Empty is a mistake, as with `last`.
  def pop : T

  # The last element or nil, the stack's twin of `shift?`: `while item =
  # stack.pop?` empties it from the top.
  def pop? : T | ::Nil

  # `<<` by the other library's name, and with several values at once: the
  # room for all of them is made in one step.
  def push(value : T) : Array(T)

  def push(*values : T) : Array(T)

  def reduce(initial : U, & : (U, T -> U)) : U forall U

  def reject(& : (T -> Bool)) : Array(T)

  # A copy in the other order.
  def reversed : Array(T)

  def select(& : (T -> Bool)) : Array(T)

  # Removes and returns the first element. The buffer steps past it rather
  # than the rest moving down: moving them made draining a queue quadratic,
  # and `while item = queue.shift?` - how the prelude says a queue is
  # drained - took 1.6 s over 100,000 items. The slot stepped past is still
  # the buffer's chunk, which the collector keeps by the pointer into it,
  # and the next growth copies only what is left.
  def shift : T

  # The first element or nil, which is how a queue is drained: `while
  # item = queue.shift?`.
  def shift? : T | ::Nil

  def size : Int32

  def sort_in_place(& : (T, T -> Int32)) : self

  # The pair for elements that already compare, by `<`. SPEC.md III.1.7a
  # pairs `sort_in_place` with `sorted` and the hint for `sort!` names both,
  # but only `sorted` had this form: "expected to be invoked with a block".
  def sort_in_place : self

  # Sorted on a key each element answers, ascending by `<`: the same pair
  # as above, one name longer. Each element's key is computed once, and the
  # pairs of key and element are what the merge sort orders.
  def sort_in_place_by(& : (T -> U)) : self forall U

  # The copy, with the comparison written out. One body, because the difference
  # between the pair is which array it runs on. The block is handed on through
  # `yield`, not captured: a captured block is kept to call later, and `!` in
  # it was refused as "maybe by a task" although the sort runs it here.
  def sorted(& : (T, T -> Int32)) : Array(T)

  def sorted : Array(T)

  def sorted_by(& : (T -> U)) : Array(T) forall U

  # The sum of the elements, and `T.zero` (src/iyi/number.iyi) when there
  # are none, as `std/enumerable`'s `sum` answers: this one raised "sum of
  # an empty array" where `Set(Int32).new.sum` was 0. `["a", "b"].sum` is a
  # compile error, as in the other library; `join` puts strings together.
  def sum : T

  # The sum of what the block answers for each element, and the block's
  # own zero when there are none.
  def sum(& : (T -> U)) : U forall U

  # `[1, 2, 3]`, the way it is written: an array printed is its elements
  # inspected, so a string inside keeps its quotes and a nil says so. Cast,
  # or `Tuple.new.to_a`'s `Array(NoReturn)` "can't infer block return type".
  def to_s : String

  # The same values as a `Set`, in the order first met.
  def to_set : Set(T)

  def to_unsafe : Pointer(T)

  # Rows into columns: `[[1, 2], [3, 4]].transpose` is `[[1, 3], [2, 4]]`.
  # Rows of different lengths have no columns to give, and are refused with
  # the first row that differs.
  def transpose

  # Keeps only the span, in place, and answers this array: `truncate(1, 2)`
  # leaves the second and third, refusing a start `[](start, count)` refuses.
  def truncate(start : Int32, count : Int32) : Array(T)

  def truncate(range : Range(B, E)) : Array(T) forall B, E

  # Each value once, in the order first met, found through a table: a
  # search of what was kept so far made it quadratic, 284 ms for 200,000
  # elements with 10,000 distinct.
  def uniq : Array(T)

  # Each element whose key is the first of its kind, in the order met: the
  # key is the block's, so `words.uniq(&.downcase)` keeps one spelling.
  def uniq(& : (T -> U)) : Array(T) forall U

  # :nodoc:
  def unsafe_set_size(size : Int32) : Nil

  # In front, in the order written: `[3].unshift(1, 2)` is `[1, 2, 3]`.
  # Every element moves up to make the room, so a queue that grows at the
  # front is quadratic where one that grows at the back and drains with
  # `shift` is not.
  def unshift(value : T) : Array(T)

  def unshift(*values : T) : Array(T)

  # Pairs, element by element, as many as this array holds: a shorter
  # *other* is refused at its first missing index, as the other library does.
  def zip(other : Array(U)) : Array(Tuple(T, U)) forall U

  # The same pairs handed to a block, with no array of them made: the
  # other library's `a.zip(b) { |x, y| ... }`, which a training loop calls
  # a few million times, and which refuses a shorter *other* the same way.
  def zip(other : Array(U), & : (T, U -> _)) : Nil forall U

  # The elements in either, each once, this array's first: `[1, 2] | [2,
  # "a"]` is `[1, 2, "a"]`, whose element type is both arrays'.
  def |(other : Array(U)) : Array(T | U) forall U

  # `Array.new(729, 0)`: *size* copies of *value*, the other library's fill
  # form. A second argument used to be an arity error beside a one-argument
  # form that means capacity, which a port reads as the fill it was.
  def self.new(size : Int32, value : T) : Array(T)

  # `Array(T).new(n) { |i| ... }`: n elements, each the block's answer for
  # its index - a row of a grid, a table of squares.
  def self.new(size : Int32, & : (Int32 -> T)) : Array(T)

  # An array of *capacity* elements that are not written yet. The literal
  # expander fills them through `to_unsafe` immediately afterwards, which is
  # why this is allowed to hand out a size it has not stored anything at.
  def self.unsafe_build(capacity : Int32) : Array(T)
end