List.binary_search:
  short: binary search
  description: >
    Performs a binary search on a sorted list.
  return:
    type: 'Int'
    description: >
      Find the first item in the list where the predicate function is true and
      return its index (or `none` if no such item exists). This assumes that
      the predicate function is monotonic over the list's contents. In other
      words, the predicate is false for the first zero or more items in the
      list and then true for the remainder of the list.
  args:
    list:
      type: '[T]'
      description: >
        The sorted list to search.
    predicate:
      type: 'func(x:T->Bool)'
      description: >
        The predicate to look for in the list.
  example: |
    # Find an item:
    assert [10, 20, 30, 40].binary_search(func(x:Int) x == 30) == 3
    # No such item:
    assert [10, 20, 30, 40].binary_search(func(x:Int) x == 25) == none
    # Find an insertion point (where an item would go to preserve sort order):
    assert [10, 20, 30, 40].binary_search(func(x:Int) x >= 25) == 3

List.by:
  short: slice by a step value
  description: >
    Creates a new list with elements spaced by the specified step value.
  return:
    type: '[T]'
    description: >
      A new list with every `step`-th element from the original list.
  args:
    list:
      type: '[T]'
      description: >
        The original list.
    step:
      type: 'Int'
      description: >
        The step value for selecting elements.
  example: |
    assert [1, 2, 3, 4, 5, 6].by(2) == [1, 3, 5]

List.clear:
  short: clear a list
  description: >
    Clears all elements from the list.
  return:
    type: 'Void'
    description: >
      Nothing.
  args:
    list:
      type: '@[T]'
      description: >
        The mutable reference to the list to be cleared.
  example: |
    list := &[10, 20]
    list.clear()
    assert list[] == []

List.counts:
  short: count occurrences
  description: >
    Counts the occurrences of each element in the list.
  return:
    type: '{T=Int}'
    description: >
      A table mapping each element to its count.
  args:
    list:
      type: '[T]'
      description: >
        The list to count elements in.
  example: |
    assert [10, 20, 30, 30, 30].counts() == {10:1, 20:1, 30:3}

List.find:
  short: find an element's index
  description: >
    Finds the index of the first occurrence of an element (if any).
  return:
    type: 'Int?'
    description: >
      The index of the first occurrence or `none` if not found.
  args:
    list:
      type: '[T]'
      description: >
        The list to search through.
    target:
      type: 'T'
      description: >
        The item to search for.
  example: |
    assert [10, 20, 30, 40, 50].find(20) == 2
    assert [10, 20, 30, 40, 50].find(9999) == none

List.from:
  short: slice an array from a start index
  description: >
    Returns a slice of the list starting from a specified index.
  return:
    type: '[T]'
    description: >
      A new list starting from the specified index.
  args:
    list:
      type: '[T]'
      description: >
        The original list.
    first:
      type: 'Int'
      description: >
        The index to start from.
  example: |
    assert [10, 20, 30, 40, 50].from(3) == [30, 40, 50]

List.has:
  short: check for member
  description: >
    Checks if the list has an element.
  return:
    type: 'Bool'
    description: >
      `yes` if the list has the element, `no` otherwise.
  args:
    list:
      type: '[T]'
      description: >
        The list to check.
    target:
      type: 'T'
      description: >
        The element to check for.
  example: |
    assert [10, 20, 30].has(20)

List.heap_pop:
  short: heap pop
  description: >
    Removes and returns the top element of a heap or `none` if the list is empty.
    By default, this is the *minimum* value in the heap.
  return:
    type: 'T?'
    description: >
      The removed top element of the heap or `none` if the list is empty.
  args:
    list:
      type: '@[T]'
      description: >
        The mutable reference to the heap.
    by:
      type: 'func(x,y:T->Int32)'
      default: 'T.compare'
      description: >
        The comparison function used to determine order. If not specified, the
        default comparison function for the item type will be used.
  example: |
    my_heap := &[30, 10, 20]
    my_heap.heapify()
    assert my_heap.heap_pop() == 10

List.heap_push:
  short: heap push
  description: >
    Adds an element to the heap and maintains the heap property. By default, this
    is a *minimum* heap.
  return:
    type: 'Void'
    description: >
      Nothing.
  args:
    list:
      type: '@[T]'
      description: >
        The mutable reference to the heap.
    item:
      type: 'T'
      description: >
        The item to be added.
    by:
      default: 'T.compare'
      description: >
        The comparison function used to determine order. If not specified, the
        default comparison function for the item type will be used.
  example: |
    my_heap : &[Int]
    my_heap.heap_push(10)
    assert my_heap.heap_pop() == 10

List.heapify:
  short: convert a list into a heap
  description: >
    Converts a list into a heap.
  return:
    type: 'Void'
    description: >
      Nothing.
  args:
    list:
      type: '@[T]'
      description: >
        The mutable reference to the list to be heapified.
    by:
      type: 'func(x,y:T->Int32)'
      default: 'T.compare'
      description: >
        The comparison function used to determine order. If not specified, the
        default comparison function for the item type will be used.
  example: |
    my_heap := &[30, 10, 20]
    my_heap.heapify()

List.insert:
  short: add an item to a list
  description: >
    Inserts an element at a specified position in the list.
  return:
    type: 'Void'
    description: >
      Nothing.
  args:
    list:
      type: '@[T]'
      description: >
        The mutable reference to the list.
    item:
      type: 'T'
      description: >
        The item to be inserted.
    at:
      type: 'Int'
      default: '0'
      description: >
        The index at which to insert the item.
  note: >
    Since indices are 1-indexed and negative indices mean "starting from the
    back", an index of `0` means "after the last item".
  example: |
    list := &[10, 20]
    list.insert(30)
    assert list == [10, 20, 30]

    list.insert(999, at=2)
    assert list == [10, 999, 20, 30]

List.insert_all:
  short: add multiple items to a list
  description: >
    Inserts a list of items at a specified position in the list.
  return:
    type: 'Void'
    description: >
      Nothing.
  args:
    list:
      type: '@[T]'
      description: >
        The mutable reference to the list.
    items:
      type: '[T]'
      description: >
        The items to be inserted.
    at:
      type: 'Int'
      default: '0'
      description: >
        The index at which to insert the item.
  note: >
    Since indices are 1-indexed and negative indices mean "starting from the
    back", an index of `0` means "after the last item".
  example: |
    list := &[10, 20]
    list.insert_all([30, 40])
    assert list == [10, 20, 30, 40]

    list.insert_all([99, 100], at=2)
    assert list == [10, 99, 100, 20, 30, 40]

List.pairs:
  short: iterate over pairs of elements
  description: >
    Returns an iterator that yields each unordered pair of distinct elements
    exactly once (equivalent to iterating `a` at index `i` and `b` at every
    later index `j > i`). The iterator yields two values per iteration, so a
    loop over it binds two variables: `for a, b in list.pairs()`. Mutating the
    list after making the iterator does not affect what it yields.
  return:
    type: 'func(a:&T, b:&T -> Bool)'
    description: >
      An iterator function that yields each pair of elements.
  args:
    list:
      type: '[T]'
      description: >
        The list whose element pairs will be iterated.
  example: |
    assert ["$a$b" for a, b in [1, 2, 3].pairs()] == ["12", "13", "23"]

List.pop:
  short: pop an item from a list
  description: >
    Removes and returns an item from the list. If the given index is present in
    the list, the item at that index will be removed and the list will become one
    element shorter.
  return:
    type: 'T?'
    description: >
      `none` if the list is empty or the given index does not exist in the list,
      otherwise the item at the given index.
  args:
    list:
      type: '&[T]'
      description: >
        The list to remove an item from.
    index:
      type: 'Int'
      default: '-1'
      description: >
        The index from which to remove the item.
  note: >
    Since negative indices are counted from the back, the default behavior is
    to pop the last value.
  example: |
    list := &[10, 20, 30, 40]

    assert list.pop() == 40
    assert list[] == [10, 20, 30]

    assert list.pop(index=2) == 20
    assert list[] == [10, 30]

List.random:
  short: pick a random element
  description: >
    Selects a random element from the list.
  return:
    type: 'T?'
    description: >
      A random element from the list or `none` if the list is empty.
  args:
    list:
      type: '[T]'
      description: >
        The list from which to select a random element.
    random:
      type: 'func(min,max:Int64->Int64)?'
      default: 'none'
      description: >
        If provided, this function will be used to get a random index in the list. Returned
        values must be between `min` and `max` (inclusive). (Used for deterministic pseudorandom number
        generation)
  example: |
    nums := [10, 20, 30]
    pick := nums.random()!
    assert nums.has(pick)
    empty : [Int]
    assert empty.random() == none

List.remove_at:
  short: remove an item by index
  description: >
    Removes elements from the list starting at a specified index.
  return:
    type: 'Void'
    description: >
      Nothing.
  args:
    list:
      type: '@[T]'
      description: >
        The mutable reference to the list.
    at:
      type: 'Int'
      default: '-1'
      description: >
        The index at which to start removing elements.
    count:
      type: 'Int'
      default: '1'
      description: >
        The number of elements to remove.
  note: >
    Since negative indices are counted from the back, the default behavior is
    to remove the last item.
  example: |
    list := &[10, 20, 30, 40, 50]
    list.remove_at(2)
    assert list == [10, 30, 40, 50]

    list.remove_at(2, count=2)
    assert list == [10, 50]

List.remove_item:
  short: remove an item by value
  description: >
    Removes all occurrences of a specified item from the list.
  return:
    type: 'Void'
    description: >
      Nothing.
  args:
    list:
      type: '@[T]'
      description: >
        The mutable reference to the list.
    item:
      type: 'T'
      description: >
        The item to be removed.
    max_count:
      type: 'Int'
      default: '-1'
      description: >
        The maximum number of occurrences to remove.
  note: >
    A negative `max_count` means "remove all occurrences".
  example: |
    list := &[10, 20, 10, 20, 30]
    list.remove_item(10)
    assert list == [20, 20, 30]

    list.remove_item(20, max_count=1)
    assert list == [20, 30]

List.reversed:
  short: get a reversed list
  description: >
    Returns a reversed slice of the list.
  return:
    type: '[T]'
    description: >
      A slice of the list with elements in reverse order.
  args:
    list:
      type: '[T]'
      description: >
        The list to be reversed.
  example: |
    assert [10, 20, 30].reversed() == [30, 20, 10]

List.sample:
  short: weighted random choices
  description: >
    Selects a sample of elements from the list, optionally with weighted
    probabilities.
  return:
    type: '[T]'
    description: >
      A list of sampled elements from the list.
  errors: >
    Errors will be raised if any of the following conditions occurs:
    - The given list has no elements and `count >= 1`
    - `count < 0` (negative count)
    - The number of weights provided doesn't match the length of the list. 
    - Any weight in the weights list is negative, infinite, or `NaN`
    - The sum of the given weights is zero (zero probability for every element).
  args:
    list:
      type: '[T]'
      description: >
        The list to sample from.
    count:
      type: 'Int'
      description: >
        The number of elements to sample.
    weights:
      type: '[Num]?'
      default: 'none'
      description: >
        The probability weights for each element in the list. These
        values do not need to add up to any particular number, they are relative
        weights. If no weights are given, elements will be sampled with uniform
        probability.
    random:
      type: 'func(->Num)?'
      default: 'none'
      description: >
        If provided, this function will be used to get random values for
        sampling the list. The provided function should return random numbers
        between `0.0` (inclusive) and `1.0` (exclusive). (Used for deterministic
        pseudorandom number generation)
  example: |
    _ := [10, 20, 30].sample(2, weights=[90%, 5%, 5%]) # E.g. [10, 10]

List.shuffle:
  short: shuffle a list in place
  description: >
    Shuffles the elements of the list in place.
  return:
    type: 'Void'
    description: >
      Nothing.
  args:
    list:
      type: '@[T]'
      description: >
        The mutable reference to the list to be shuffled.
    random:
      type: 'func(min,max:Int64->Int64)?'
      default: 'none'
      description: >
        If provided, this function will be used to get a random index in the list. Returned
        values must be between `min` and `max` (inclusive). (Used for deterministic pseudorandom number
        generation)
  example: |
    nums := &[10, 20, 30, 40]
    nums.shuffle()
    # E.g. [20, 40, 10, 30]

List.shuffled:
  short: return a shuffled list
  description: >
    Creates a new list with elements shuffled.
  return:
    type: '[T]'
    description: >
      A new list with shuffled elements.
  args:
    list:
      type: '[T]'
      description: >
        The list to be shuffled.
    random:
      type: 'func(min,max:Int64->Int64)?'
      default: 'none'
      description: >
        If provided, this function will be used to get a random index in the list. Returned
        values must be between `min` and `max` (inclusive). (Used for deterministic pseudorandom number
        generation)
  example: |
    nums := [10, 20, 30, 40]
    _ := nums.shuffled()
    # E.g. [20, 40, 10, 30]

List.slice:
  short: get a slice of a list
  description: >
    Returns a slice of the list spanning the given indices (inclusive).
  return:
    type: '[T]'
    description: >
      A new list spanning the given indices. Note: negative indices are counted from
      the back of the list, so `-1` refers to the last element, `-2` the
      second-to-last, and so on.
  args:
    list:
      type: '[T]'
      description: >
        The original list.
    from:
      type: 'Int'
      description: >
        The first index to include.
    to:
      type: 'Int'
      description: >
        The last index to include.
  example: |
    assert [10, 20, 30, 40, 50].slice(2, 4) == [20, 30, 40]
    assert [10, 20, 30, 40, 50].slice(-3, -2) == [30, 40]

List.sort:
  short: sort a list
  description: >
    Sorts the elements of the list in place in ascending order (small to large).
  return:
    type: 'Void'
    description: >
      Nothing.
  args:
    list:
      type: '@[T]'
      description: >
        The mutable reference to the list to be sorted.
    by:
      default: 'T.compare'
      description: >
        The comparison function used to determine order. If not specified, the
        default comparison function for the item type will be used.
  example: |
    list := &[40, 10, -30, 20]
    list.sort()
    assert list == [-30, 10, 20, 40]

    list.sort(func(a,b:Int) a.abs() <> b.abs())
    assert list == [10, 20, -30, 40]

List.sorted:
  short: sorted copy of a list
  description: >
    Creates a new list with elements sorted.
  return:
    type: '[T]'
    description: >
      A new list with sorted elements.
  args:
    list:
      type: '[T]'
      description: >
        The list to be sorted.
    by:
      default: 'T.compare'
      description: >
        The comparison function used to determine order. If not specified, the
        default comparison function for the item type will be used.
  example: |
    assert [40, 10, -30, 20].sorted() == [-30, 10, 20, 40]
    assert [40, 10, -30, 20].sorted(
       func(a,b:Int) a.abs() <> b.abs()
    ) == [10, 20, -30, 40]

List.swap:
  short: swap two elements in place
  description: >
    Swaps the elements at two indices in place. Compiles inline, so a swap
    costs one bounds check per index and a single copy-on-write check (a
    two-element multi-assignment swap pays both twice). Swapping an index with
    itself is a no-op. Negative indices count from the back of the list, and
    an out-of-bounds index is a runtime error.
  return:
    type: 'Void'
    description: >
      Nothing.
  args:
    list:
      type: '@[T]'
      description: >
        The mutable reference to the list.
    i:
      type: 'Int'
      description: >
        The index of the first element (1-indexed).
    j:
      type: 'Int'
      description: >
        The index of the second element (1-indexed).
  example: |
    list := &[10, 20, 30]
    list.swap(1, 3)
    assert list == [30, 20, 10]

    list.swap(2, -1)
    assert list == [30, 10, 20]

List.to:
  short: slice a list to an end index
  description: >
    Returns a slice of the list from the start of the original list up to a specified index (inclusive).
  return:
    type: '[T]'
    description: >
      A new list containing elements from the start up to the specified index.
  args:
    list:
      type: '[T]'
      description: >
        The original list.
    last:
      type: 'Int'
      description: >
        The index up to which elements should be included.
  example: |
    assert [10, 20, 30, 40, 50].to(3) == [10, 20, 30]
    assert [10, 20, 30, 40, 50].to(-2) == [10, 20, 30, 40]

List.unique:
  short: get the unique items in a list
  description: >
    Returns a set of the unique elements of the list.
  return:
    type: '{T}'
    description: >
      A set of the unique elements from the list.
  args:
    list:
      type: '[T]'
      description: >
        The list to process.
  example: |
    assert [10, 20, 10, 10, 30].unique() == {10, 20, 30}

List.where:
  short: find an index where a predicate matches
  description: >
    Find the index of the first item that matches a predicate function (if any).
  return:
    type: 'Int'
    description: >
      Returns the index of the first item where the predicate is true or `none` if no
      item matches.
  args:
    list:
      type: '[T]'
      description: >
        The list to search through.
    predicate:
      type: 'func(item:T -> Bool)'
      description: >
        A function that returns `yes` if the item's index should be returned or
        `no` if it should not.
  example: |
    assert ["BC", "ABC", "CD"].where(func(t:Text) t.starts_with("A")) == 2
    assert ["BC", "ABC", "CD"].where(func(t:Text) t.starts_with("X")) == none