# Prio — foundational U32 priority bag for Bend.
# Publish entry for this package. Depends only on Base.
#
# This v1 intentionally ships a sorted priority bag rather than a binary heap.
# The representation is a sorted List, so push is O(n), while peek_min and
# pop_min are O(1) at the front. The API is heap-shaped and can be upgraded
# to a binary-heap representation later without changing callers.
import Base

type Prio is Data:
  P{data: List<&2, U32>}

type Prio.Pop is Data:
  PP{value: U32, rest: Prio}

# Insert while preserving nondecreasing U32 order.
def Prio.insert.go(+xs: List<&2, U32>, +x: U32) -> List<&2, U32>:
  match xs:
    case Nil{}:
      x <> Nil{}
    case h <> t:
      Bool.pick(List<&2, U32>, U32.is_le(x, h),
        x <> h <> t, h <> Prio.insert.go(t, x))

def Prio.insert(xs: List<&2, U32>, +x: U32) -> List<&2, U32>:
  Prio.insert.go(xs, x)

def Prio.empty() -> Prio:
  P{Nil{}}

def Prio.push(q: Prio, x: U32) -> Prio:
  match q:
    case P{xs}:
      P{Prio.insert(xs, x)}

def Prio.peek_min(q: Prio) -> Maybe<&2, U32>:
  match q:
    case P{xs}:
      match xs:
        case Nil{}:
          None{}
        case h <> t:
          Some{h}

def Prio.pop_min.go(xs: List<&2, U32>) -> Maybe<&2, Prio.Pop>:
  match xs:
    case Nil{}:
      None{}
    case h <> t:
      Some{PP{h, P{t}}}

def Prio.pop_min(q: Prio) -> Maybe<&2, Prio.Pop>:
  match q:
    case P{xs}:
      Prio.pop_min.go(xs)

def Prio.size(q: Prio) -> Nat:
  match q:
    case P{xs}:
      List.length(&2, U32, xs)

def Prio.is_empty(q: Prio) -> Bool:
  match q:
    case P{xs}:
      List.is_empty(&2, U32, xs)

def Prio.to_list(q: Prio) -> List<&2, U32>:
  match q:
    case P{xs}:
      xs

def Prio.from_list.go(xs: List<&2, U32>, q: Prio) -> Prio:
  match xs:
    case Nil{}:
      q
    case h <> t:
      Prio.from_list.go(t, Prio.push(q, h))

def Prio.from_list(xs: List<&2, U32>) -> Prio:
  Prio.from_list.go(xs, Prio.empty())