## std.lists: Dynamic arrays.
## This module is imported by default.
# reference: https://doc.rust-lang.org/nomicon/vec/vec.html

## The fundamental list type. Heap-allocated.
## Equivalent to Vec<T> in other languages.
@[unsafe] # unsafe on a struct tells us raw field access breaks invariants.
pub type list[T] = struct
  data: ptr T
  capacity: int
  length: int

## A transparent, common alias for a list of bytes.
pub type bytes = list[byte]

## Initialize and return an empty list with inner type T.
pub func init[T]: list[T] =
  { data = nil, capacity = 0, length = 0 } # fixme: nil!!!!!

## Gets the length of a list.
@[inline] # idk what to do with attributes
pub func len[T](self: lent list[T]): uint =
  self.length

pub func empty[T](self: lent list[T]): bool =
  self.length == 0

## Gets the internal capacity of a list.
func cap[T](self: lent list[T]): uint =
  self.capacity

## Expands the capacity of a list.
@[safe]
func grow[T](self: mut list[T]) =
  self.capacity = max(self.length + 1, self.capacity * 2)
  self.data = self.data.realloc(self.capacity * sizeof(T))

## Pushes a new element to the end of a list.
@[safe]
pub func push[T](self: mut list[T], val: T) =
  if self.capacity == self.length then self.grow()
  self.data.set(val, offset = self.length)
  self.length += 1

## Takes ownership of and pushes all the values of a list into another list.
pub func push[T](self: mut list[T], values: list[T]) =
  for val in values do
    self.push(val)

## Removes & returns an element from the end of a list, if it exists.
@[safe]
pub func pop[T](self: mut list[T]): T? =
  if self.length == 0 then
    None
  else
    self.length -= 1
    Some(self.data.get(offset = self.length))

## Returns a reference to an element of a list, if in range.
@[safe]
pub func get[T](self: lent list[T], i: uint): lent T? =
  if i > self.length then
    None
  else # fixme: interior mutability
    Some(lent self.data.get(offset = i))
## Returns a mutable reference to an element of a list, if in range.
@[safe]
pub func get[T](self: mut list[T], i: uint): mut T? =
  if i > self.length then
    None
  else # fixme: interior mutability
    Some(mut self.data.get(offset = i))

## Sets the element of a list to a value.
@[safe]
pub func set[T](self: mut list[T], i: uint, val: T) =
  assert i <= self.length, "index out of bounds"
  Okay(self.data.set(offset = i, val))

## Inserts a value at a location and shifts elements of the list accordingly.
@[safe]
pub func insert[T](self: mut list[T], i: uint, val: T) =
  assert i <= self.length, "index out of bounds"
  if self.capacity == self.length then self.grow()
  self.data.offset(i).copy(self.data.offset(i + 1), self.length - i)
  self.data.set(i, val)
  self.length += 1
## Inserts a list of values at a location and shifts elements of the list accordingly.
pub func insert[T](self: mut list[T], i: uint, vals: list[T]) =
  for val in vals.rev: # inserting backwards avoids counting
    self.insert(val, i)

## Removes a value at a location and shifts elements of the list accordingly.
@[safe]
pub func remove[T](self: mut list[T], i: uint): T? =
  if index < self.length then None
  else
    self.length -= 1
    let res = self.data.get(i)
    self.data.offset(i + 1).copy(self.data.offset(i), self.length - i)
    res

## Gets the last element of a list, if it exists.
pub func last[T](self: lent list[T]): lent T? =
  self.get(self.len - 1)
## Gets the last element of a list mutably, if it exists.
pub func last[T](self: mut list[T]): mut T? =
  self.get(self.len - 1)

# todo: many questions. owned? how does it not free?
pub func iter[T](self: list[T]): ListIter[T] =
  ...

# todo: iteration...
# todo: destructors...
# todo: syntax for inlining + other pragmas... as a macro, perhaps?
# todo: slices

type slice[T] = struct
  data: ptr[T] # hrm...
  length: uint