slabs

import gleam/list
import gleam/option

type Entry(a) {
  Vacant(option.Option(Int))
  Occupied(a)
}

pub opaque type Slab(a) {
  Slab(inner: List(Entry(a)), next_id: option.Option(Int), length: Int)
}

pub type SlabError {
  BadIndex(index: Int)
}

/// Create a new slab container
pub fn new() -> Slab(a) {
  Slab(inner: [], next_id: option.None, length: 0)
}

/// Insert an item into the slab
pub fn insert(slab: Slab(a), value: a) -> #(Slab(a), Int) {
  case slab.next_id {
    option.Some(slot_index) -> {
      let index = slab.length - 1 - slot_index

      let #(left, right) =
        slab.inner
        |> list.split(index)

      let assert Ok(Vacant(next_id)) =
        right
        |> list.first

      let right = case right {
        [_, ..rest] -> rest
        [] -> []
      }

      let inner = list.append(left, [Occupied(value), ..right])

      #(Slab(..slab, inner:, next_id:), slot_index)
    }

    option.None -> {
      let index = list.length(slab.inner)
      #(
        Slab(
          ..slab,
          inner: [Occupied(value), ..slab.inner],
          length: slab.length + 1,
        ),
        index,
      )
    }
  }
}

fn insert_accum(
  slab: Slab(a),
  values: List(a),
  acc: List(Int),
) -> #(Slab(a), List(Int)) {
  case values {
    [v, ..rest] -> {
      let #(slab, index) = insert(slab, v)
      insert_accum(slab, rest, [index, ..acc])
    }
    [] -> #(slab, acc)
  }
}

/// Insert several items into the slab
pub fn insert_many(slab: Slab(a), values: List(a)) -> #(Slab(a), List(Int)) {
  insert_accum(slab, values, [])
}

/// Remove an entry from the slab
pub fn remove(slab: Slab(a), index: Int) -> Result(#(Slab(a), a), SlabError) {
  case index >= 0 && index < slab.length {
    True -> {
      let #(left, right) =
        slab.inner
        |> list.split(slab.length - 1 - index)

      let assert Ok(entry) =
        right
        |> list.first

      let right = case right {
        [_, ..rest] -> rest
        [] -> []
      }

      let inner = list.append(left, [Vacant(slab.next_id), ..right])

      // FIXME: Logically this can fail when using an index that's vacant
      let assert Occupied(value) = entry
      Ok(#(Slab(..slab, inner:, next_id: option.Some(index)), value))
    }

    False -> Error(BadIndex(index))
  }
}

fn remove_many_accum(
  slab: Slab(a),
  indexes: List(Int),
  acc: List(a),
) -> #(Slab(a), List(a)) {
  case indexes {
    [index, ..rest] -> {
      case remove(slab, index) {
        Ok(#(slab, value)) -> remove_many_accum(slab, rest, [value, ..acc])
        Error(_) -> remove_many_accum(slab, rest, acc)
      }
    }
    [] -> #(slab, acc)
  }
}

/// Remove several items from a slab at once
pub fn remove_many(slab: Slab(a), indexes: List(Int)) -> #(Slab(a), List(a)) {
  remove_many_accum(slab, indexes, [])
}

fn get_items(items: List(Entry(a)), acc: Int, index: Int) -> option.Option(a) {
  case items {
    [v, _] | [v] if acc == index -> {
      case v {
        Vacant(_) -> option.None
        Occupied(v) -> option.Some(v)
      }
    }

    [_, ..rest] -> get_items(rest, acc - 1, index)

    [] -> option.None
  }
}

/// Index into the slab and retrieve a value
pub fn get(slab: Slab(a), index: Int) -> option.Option(a) {
  get_items(slab.inner, slab.length - 1, index)
}

fn get_values_accum(
  entries: List(Entry(a)),
  index: Int,
  acc: List(#(Int, a)),
) -> List(#(Int, a)) {
  case entries {
    [Occupied(value), ..rest] ->
      get_values_accum(rest, index - 1, [#(index, value), ..acc])
    [_, ..rest] -> get_values_accum(rest, index - 1, acc)
    _ -> acc
  }
}

/// Retrieve a list of the occupied values and their corresponding indexes
pub fn get_values(slab: Slab(a)) -> List(#(Int, a)) {
  get_values_accum(slab.inner, slab.length - 1, [])
}

/// Returns the amount of items in the slab (including vacant slots)
pub fn length(slab: Slab(a)) -> Int {
  slab.length
}