---
title: "Priority Queues"
output: rmarkdown::html_vignette
vignette: >
  %\VignetteIndexEntry{Priority Queues}
  %\VignetteEngine{knitr::rmarkdown}
  %\VignetteEncoding{UTF-8}
---
```{r setup, include = FALSE}
knitr::opts_chunk$set(collapse = TRUE, comment = "#>")
if(requireNamespace("pkgload", quietly = TRUE)) {
  pkgload::load_all(".", quiet = TRUE)
} else if(requireNamespace("Immutables", quietly = TRUE)) {
  library(Immutables)
} else {
  stop("Need either installed 'Immutables' or the 'pkgload' package to render this vignette.")
}
```


## Priority queue basics

`priority_queue` is a persistent structure that associates elements with priority values, typically numeric or character (string). They provide
fast access to elements by min or max priority, and insertion of new 
elements with given priorities. 

All operations are persistent, and return modified copies. Peeking at the min/max returns the stored element (which may be any type), 
popping returns a list with `$value` containing the stored element, `$priority` the priority,
and `$remaining` the rest of the priority queue without those elements.

```{r}
x <- priority_queue("task_a", "task_b", "task_c", priorities = c(3, 1, 2))
x

peek_min(x)
res <- pop_max(x)

res$value
res$priority
res$remaining
```

The `as_priority_queue()` variant builds a queue from a vector or list of elements paired with a priority vector. useful when priorities are already in a separate vector.

```{r}
q <- as_priority_queue(letters[1:4], priorities = c(3, 1, 2, 1))
q
```

## Priority ties

In the case of multiple identical priorities, peek/pop for min/max return a *single element*, in their original insertion order. Their "all" counterparts (`peek_all_min`, `pop_all_max`, etc.) return two priorities: in `$elements` the elements peeked/popped and in `$remaining` the other elements. `peek_all_max` and `pop_all_max` behave symmetrically on the maximum-priority tie run.
```{r}
y <- priority_queue() |>
  insert("Jones", priority = "B") |>
  insert("Smith", priority = "A") |>
  insert("Adams", priority = "A")

peek_min(y)
peek_all_min(y)

res1 <- pop_min(y)
res1$value
res1$priority
res1$remaining

res2 <- pop_all_min(y)

res2$elements
res2$remaining
```
Priority queues can be converted to R lists with `as.list()`. The `drop_meta` parameter defaulting to `FALSE` controls whether priority values are included.

```{r}
as.list(res2$elements) |> str()
as.list(res2$elements, drop_meta = TRUE) |> str()
```

## Empty queues

Peek/pop helpers are non-throwing on empty queues, `length()` allows for empty checking.

```{r}
empty_q <- priority_queue()
length(empty_q)
peek_min(empty_q)
pop_min(empty_q)
```

## Priority values

`min_priority()` and `max_priority()` return the current extrema *priority* (not the stored element), in O(1) via cached monoid state.

```{r}
q <- priority_queue("a", "b", "c", priorities = c(3, 1, 2))
min_priority(q)
max_priority(q)
min_priority(priority_queue())  # NULL when empty
```

## Named priorities

Priority queues can carry names, set either at construction or on `insert()`. Names support read-only indexing via `[`, `[[`, and `$`. This is the *only* indexing form `priority_queue` supports. Positional indexing and all replacement forms (`[<-`, `[[<-`, `$<-`) error; cast to `as_flexseq()` first to mutate.

```{r}
q <- priority_queue(a = "task-a", b = "task-b", priorities = c(2, 1)) |>
  insert("task-c", priority = 3, name = "c")

q[["b"]]
q[c("a", "c")]

try(q[1])         # positional indexing blocked
try(q$a <- "!!")  # replacement blocked
```

## Transforming, iterating, merging

`fapply()` maps a function over queue elements while preserving priorities. The function receives `(value, priority)`, or `(value, priority, name)` if it accepts a third argument — priorities and names are passed in read-only, and the return value replaces the stored element.

```{r}
q <- priority_queue("alice", "bob", "carol", priorities = c(3, 1, 2))
fapply(q, function(value, priority) toupper(value))
```

`loop()` (re-exported from the **coro** package) walks the queue in priority-ascending order, yielding bare values. Traversal is driven by repeated `pop_min()`, so full traversal is $O(n \log n)$ ($O(\log n)$ per step); ties within equal priority follow insertion order.

```{r}
q <- priority_queue("task_a", "task_b", "task_c", priorities = c(3, 1, 2))
loop(for (v in q) print(v))
```

Use `fapply()` if your callback needs the priority alongside the value, or cast with `as_flexseq()` for insertion-order iteration. Plain `for (v in q)` (without `loop()`) yields raw finger-tree internals rather than elements — always wrap with `loop()`.

`merge(x, y)` combines two priority queues into a new one containing every entry from both, in O(log(min(m, n))). The `.pq_min` / `.pq_max` monoids recompute automatically on the merged tree, so extremum queries work immediately on the result.

```{r}
a <- priority_queue("x", "y", priorities = c(5, 1))
b <- priority_queue("z", priorities = 3)
m <- merge(a, b)
length(m)
peek_min(m)
peek_max(m)
```

Both queues must share the same priority type and monoid set; mismatches error (rather than being silently harmonized). Both inputs are left unmodified.

For full sequence-style operations, cast with `as_flexseq()`. This returns
payload items only; priority metadata and any custom monoids are dropped. To
instead obtain a `flexseq` of entry records (`value` + `priority`), compose
with `as.list()`.

```{r}
y <- priority_queue() |>
  insert("Jones", priority = "B") |>
  insert("Smith", priority = "A") |>
  insert("Adams", priority = "A")

as_flexseq(y)
as_flexseq(as.list(y))
```