std.list

func int_list() -> &IntList {
  return new IntList { items: new I32Values[8]{}, count: 0 };
}

func int_list_with_capacity(capacity: i32) -> &IntList {
  return new IntList { items: new I32Values[capacity < 1 ? 1 : capacity]{}, count: 0 };
}

func int_list_from(values: &I32Values) -> &IntList {
  let items: &I32Values = new I32Values[#values < 1 ? 1 : #values]{};
  items.copy(0, values, 0, #values);
  return new IntList { items: items, count: #values };
}

func long_list() -> &LongList {
  return new LongList { items: new I64Values[8]{}, count: 0 };
}

func ref_list() -> &RefList {
  return new RefList { items: new AnyValues[8]{}, count: 0 };
}

func IntList.len(self: &IntList) -> i32 {
  return self->count;
}

func IntList.capacity(self: &IntList) -> i32 {
  return #self->items;
}

func IntList.is_empty(self: &IntList) -> i32 {
  return self->count == 0;
}

func IntList.reserve(self: &IntList, capacity: i32) {
  if (capacity <= #self->items) { return; }
  var next: i32 = #self->items;
  loop grow() {
    next = next * 2;
    if (next >= capacity) { break grow(); }
    continue grow();
  }
  let bigger: &I32Values = new I32Values[next]{};
  bigger.copy(0, self->items, 0, self->count);
  self->items = bigger;
}

func IntList.push(self: &IntList, value: i32) {
  self.reserve(self->count + 1);
  self->items[self->count] = value;
  self->count = self->count + 1;
}

func IntList.pop(self: &IntList) -> (i32, i32) {
  if (self->count == 0) { return (0, 0); }
  self->count = self->count - 1;
  return (self->items[self->count], 1);
}

func IntList.at(self: &IntList, index: i32) -> i32 {
  if (index < 0 || index >= self->count) { unreachable; }
  return self->items[index];
}

func IntList.get_or(self: &IntList, index: i32, fallback: i32) -> i32 {
  if (index < 0 || index >= self->count) { return fallback; }
  return self->items[index];
}

func IntList.set(self: &IntList, index: i32, value: i32) {
  if (index < 0 || index >= self->count) { return; }
  self->items[index] = value;
}

func IntList.insert(self: &IntList, index: i32, value: i32) {
  let at: i32 = index < 0 ? 0 : (index > self->count ? self->count : index);
  self.reserve(self->count + 1);
  // Copy backwards through the overlap: `array.copy` handles overlapping ranges correctly
  // (it is specified as if through an intermediate), so one call moves the whole tail.
  self->items.copy(at + 1, self->items, at, self->count - at);
  self->items[at] = value;
  self->count = self->count + 1;
}

func IntList.remove(self: &IntList, index: i32) -> (i32, i32) {
  if (index < 0 || index >= self->count) { return (0, 0); }
  let removed: i32 = self->items[index];
  self->items.copy(index, self->items, index + 1, self->count - index - 1);
  self->count = self->count - 1;
  return (removed, 1);
}

func IntList.clear(self: &IntList) {
  self->count = 0;
}

func IntList.index_of(self: &IntList, value: i32) -> i32 {
  for i in 0..self->count {
    if (self->items[i] == value) { return i; }
  }
  return -1;
}

func IntList.contains(self: &IntList, value: i32) -> i32 {
  return self.index_of(value) >= 0;
}

func IntList.sum(self: &IntList) -> i32 {
  var total: i32 = 0;
  for i in 0..self->count {
    total = total + self->items[i];
  }
  return total;
}

func IntList.min(self: &IntList) -> (i32, i32) {
  if (self->count == 0) { return (0, 0); }
  var best: i32 = self->items[0];
  for i in 1..self->count {
    if (self->items[i] < best) { best = self->items[i]; }
  }
  return (best, 1);
}

func IntList.max(self: &IntList) -> (i32, i32) {
  if (self->count == 0) { return (0, 0); }
  var best: i32 = self->items[0];
  for i in 1..self->count {
    if (self->items[i] > best) { best = self->items[i]; }
  }
  return (best, 1);
}

func IntList.reverse(self: &IntList) {
  var lo: i32 = 0;
  var hi: i32 = self->count - 1;
  loop swap() {
    if (lo >= hi) { break swap(); }
    let t: i32 = self->items[lo];
    self->items[lo] = self->items[hi];
    self->items[hi] = t;
    lo = lo + 1;
    hi = hi - 1;
    continue swap();
  }
}

func IntList.extend(self: &IntList, other: &IntList) {
  self.reserve(self->count + other->count);
  self->items.copy(self->count, other->items, 0, other->count);
  self->count = self->count + other->count;
}

func IntList.clone(self: &IntList) -> &IntList {
  let items: &I32Values = new I32Values[#self->items]{};
  items.copy(0, self->items, 0, self->count);
  return new IntList { items: items, count: self->count };
}

func IntList.to_array(self: &IntList) -> &I32Values {
  let out: &I32Values = new I32Values[self->count]{};
  out.copy(0, self->items, 0, self->count);
  return out;
}

func LongList.len(self: &LongList) -> i32 {
  return self->count;
}

func LongList.is_empty(self: &LongList) -> i32 {
  return self->count == 0;
}

func LongList.push(self: &LongList, value: i64) {
  if (self->count == #self->items) {
    let bigger: &I64Values = new I64Values[#self->items * 2]{};
    bigger.copy(0, self->items, 0, self->count);
    self->items = bigger;
  }
  self->items[self->count] = value;
  self->count = self->count + 1;
}

func LongList.pop(self: &LongList) -> (i64, i32) {
  if (self->count == 0) { return (0, 0); }
  self->count = self->count - 1;
  return (self->items[self->count], 1);
}

func LongList.at(self: &LongList, index: i32) -> i64 {
  if (index < 0 || index >= self->count) { unreachable; }
  return self->items[index];
}

func LongList.set(self: &LongList, index: i32, value: i64) {
  if (index < 0 || index >= self->count) { return; }
  self->items[index] = value;
}

func LongList.clear(self: &LongList) {
  self->count = 0;
}

func LongList.sum(self: &LongList) -> i64 {
  var total: i64 = 0;
  for i in 0..self->count {
    total = total + self->items[i];
  }
  return total;
}

func RefList.len(self: &RefList) -> i32 {
  return self->count;
}

func RefList.is_empty(self: &RefList) -> i32 {
  return self->count == 0;
}

func RefList.push(self: &RefList, value: ?any) {
  if (self->count == #self->items) {
    let bigger: &AnyValues = new AnyValues[#self->items * 2]{};
    bigger.copy(0, self->items, 0, self->count);
    self->items = bigger;
  }
  self->items[self->count] = value;
  self->count = self->count + 1;
}

func RefList.pop(self: &RefList) -> (?any, i32) {
  if (self->count == 0) { return (null, 0); }
  self->count = self->count - 1;
  let value: ?any = self->items[self->count];
  // Drop the list's own reference so a popped object can be collected while the list
  // lives on. Without this, a long-lived list pins every object it ever held.
  self->items[self->count] = null;
  return (value, 1);
}

func RefList.at(self: &RefList, index: i32) -> ?any {
  if (index < 0 || index >= self->count) { return null; }
  return self->items[index];
}

func RefList.set(self: &RefList, index: i32, value: ?any) {
  if (index < 0 || index >= self->count) { return; }
  self->items[index] = value;
}

func RefList.clear(self: &RefList) {
  self->items.fill(0, null, self->count);
  self->count = 0;
}

struct IntList {
  items: mut &I32Values,
  count: mut i32,
}

struct LongList {
  items: mut &I64Values,
  count: mut i32,
}

struct RefList {
  items: mut &AnyValues,
  count: mut i32,
}