lib.bend source

lib.bend on the hub · documented module

# 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 Basetype 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}:      xsdef 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())