Paret Garbage Collector Mark&Sweep

object Solution {

  type PointerEnvironment = List[Pointer]
  type Store = List[Cell]

  /**
   * Identifies which store cells are not accessible from the given environment (direct nor indirectly),
   * and removes those cells from the store, reporting the number of cells removed.
   *
   * @return A tuple of the number of removed cells and the garbage collected store.
   */
  def collectGarbage(nv: PointerEnvironment, st: Store): (Int, Store) = {
  // Mark all cells that are reachable from pointers in the environment
  val marked = mark(nv)(st, Set.empty)

  // Remove all unmarked cells from the store
  val (removed, newSt) = st.foldLeft((0, List.empty[Cell])) { case ((count, acc), cell) =>
    if (marked.contains(cell.location)) {
      (count, cell :: acc)
    } else {
      (count + 1, acc)
    }
  }
  (removed, newSt.reverse)
}

// Mark all cells that are reachable from pointers in the environment
def mark(nv: PointerEnvironment)(st: Store, marked: Set[Int]): Set[Int] = {
  nv.foldLeft(marked) { case (acc, ptr) =>
    markPointer(ptr)(st, acc)
  }
}

// Mark all cells that are reachable from a pointer
def markPointer(ptr: Pointer)(st: Store, marked: Set[Int]): Set[Int] = {
  if (marked.contains(ptr.location)) { // Already reached
    marked
  } else {
    val cell = st.find(_.location == ptr.location).getOrElse(throw new RuntimeException(s"Invalid pointer: $ptr"))
    markValue(cell.value)(st, marked + ptr.location)
  }
}

// Mark all cells reachable from a Value
def markValue(value: Value)(st: Store, marked: Set[Int]): Set[Int] = {
  value match {
    case ConsV(hd, tl) =>
      markCons(hd, tl)(st, marked)
    case PointerClosV(_, env) =>
      mark(env)(st, marked)
    case BoxV(l) =>
      markBox(l)(st, marked)
    case _ =>
      // primitive values and NilV don't have pointers to other cells, so don't mark anything
      marked
  }
}

// Mark all cells reachable from a Cons cell
def markCons(hd: Value, tl: Value)(st: Store, marked: Set[Int]): Set[Int] = {
  markValue(hd)(st, markValue(tl)(st, marked))
}

// Mark all cells reachable from a Box
def markBox(l: Int)(st: Store, marked: Set[Int]): Set[Int] = {
  val cell = st.find(_.location == l).getOrElse(throw new RuntimeException(s"Invalid box location: $l"))
  markValue(cell.value)(st, marked + l)
}




}