---
title: "Ordered Sequences: Key-Sorted Storage with Range Queries"
output: rmarkdown::html_vignette
vignette: >
  %\VignetteIndexEntry{Ordered Sequences: Key-Sorted Storage with Range Queries}
  %\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.")
}
```

## Ordered sequence basics

`ordered_sequence` is a persistent structure that associates elements with keys, typically numeric or character (string). They store elements sorted by key, with stable first-in-first-out (FIFO) behavior for duplicate keys, and provide fast key-based lookup, range queries over keys, and insertion.

All operations are persistent, and return modified copies. Peeking by key returns the stored element (which may be any type), popping returns a list with `$value` containing the stored element, `$key` the key, and `$remaining` the rest of the sequence without that element.

```{r}
xs <- ordered_sequence("a1", "b1", "b2", "c1", keys = c(1, 2, 2, 3))
xs
```

The `as_ordered_sequence()` variant builds a sequence from a vector or list of elements paired with a key vector, useful when keys are already in a separate vector.

```{r}
xs2 <- as_ordered_sequence(c(3, 1, 2, 1), keys = letters[1:4])
xs2
```

`as_flexseq(xs)` returns a payload-only `flexseq`; keys and any custom monoids are dropped (see `as.list` to convert and 
preservekey metadata).


## Peek, pop, insert, and range query by key

Insertion is by key, and *keys may be duplicated*. 

```{r}
seq <- as_ordered_sequence(1:3, keys = letters[1:3])
seq2 <- insert(seq, 10, key = "b")
seq2
```

`pop_key()` removes and returns the first match for a key as `$value`/`$key`/`$remaining`. Its "all" counterpart `pop_all_key()` removes the entire tie run for that key, returning `$elements` (an ordered sequence of removed matches) and `$remaining`.

```{r}
one <- pop_key(seq, key = "b")
one$value
one$key
one$remaining

all_two <- pop_all_key(seq, "b")
all_two$elements
all_two$remaining
```

Keys may be counted, and elements accessed; `peek_key()` returns one element, the
first in insertion order. `peek_all_key()` returns an ordered sequence with all
matching keys.

```{r}
count_key(seq, key = "b")
peek_key(seq, key = "b")
peek_all_key(seq, key = "b")
```

Counting and accessing elements over query ranges support inclusive/exclusive on both sides (defaulting to `TRUE`).

```{r}
elements_between(seq, from_key = "b", to_key ="c", include_from = TRUE, include_to = TRUE)
count_between(seq, from_key = "b", to_key = "c", include_from = TRUE, include_to = TRUE)

# exclude "b" keys
elements_between(seq, from_key = "b", to_key ="c", include_from = FALSE, include_to = TRUE)
```


## Key boundaries, and extrema

`lower_bound()` finds the first element with key `>=` a query key; `upper_bound()` finds the first with key strictly `>`. Both return a list with `$found`, `$index`, `$value`, and `$key` (`NULL` fields when no match exists). Together they support successor queries ("find the nearest entry at or above this key") and duplicate counting via index arithmetic.

```{r}
seq <- as_ordered_sequence(1:4, keys = c("b", "d", "d", "f"))

lower_bound(seq, key = "d") |> str()
upper_bound(seq, key = "d") |> str()
```

When the query key falls between or outside existing keys, `lower_bound()` returns the next entry at or above, useful for nearest-match lookups. Both return `found = FALSE` when no keys satisfy the condition.

```{r}
lower_bound(seq, key = "a") |> str()

upper_bound(seq, key = "g") |> str()
```

The difference `upper_bound(x, k)$index - lower_bound(x, k)$index` gives the count of entries with key `k` (this is what `count_key()` does internally).

```{r}
upper_bound(seq, key = "d")$index - lower_bound(seq, key = "d")$index
count_key(seq, key = "d")
```


`min_key()` and `max_key()` return the current minimum and maximum *keys* (not the stored elements).

```{r}
min_key(xs)
max_key(xs)
min_key(ordered_sequence())  # NULL when empty
```

Because keys are stored in sorted order, ordered sequences also support the positional operators inherited from `flexseq` — `peek_at()`, `pop_front()`, `pop_back()`, and `pop_at()`. On an ordered sequence the pops additionally return `$key` (alongside `$value`/`$remaining`), and `key_at()` reads the key at a one-based position without removing anything: the positional companion to `peek_at()` (which reads the value there) and the general form of `min_key()`/`max_key()`.

```{r}
key_at(xs, 2)                          # key at position 2
key_at(xs, 1) == min_key(xs)           # first position holds the minimum key
key_at(xs, length(xs)) == max_key(xs)  # last position holds the maximum key
key_at(xs, 10)                         # NULL when out of bounds

front <- pop_front(xs)                 # positional pop carries the key too
front$value
front$key
```

`nearest_key()` returns the existing key closest to a query, which then composes with `peek_key()` / `pop_key()` to read or remove the matching element. It resolves by order alone at the extremes and on an exact hit, and only needs a distance metric when the query falls strictly between two distinct keys — so it supports `numeric`, `Date`, and `POSIXct` keys there. An equidistant tie between two distinct keys is resolved by `ties` — `"lower"` (default), `"upper"`, or `"both"` (returns both keys). For `character` keys the between-case is undefined ("is `"Ben"` closer to `"Alex"` or `"Charlie"`?") and errors; use `lower_bound()` / `peek_key()` for order-based lookup instead.

```{r}
nearest_key(xs, 2.4)                    # between 2 and 3 -> closer key (2)
nearest_key(xs, 0)                      # below all -> min_key (1)
nearest_key(xs, 2.5, ties = "both")     # exactly between 2 and 3 -> c(2, 3)

k <- nearest_key(xs, 2.4)               # locate, then act with the keyed helpers
pop_key(xs, k)$value
```

## Empty sequences

Key and range helpers are non-throwing on empty sequences, and `length()` allows for empty checking.

```{r}
empty_os <- ordered_sequence()
length(empty_os)
peek_key(empty_os, 1)
count_between(empty_os, 1, 5)
```

## Named ordered sequences

Ordered sequences can carry names, set either at construction or through `as_ordered_sequence()` on a named list. Names and integer positions both support read-only indexing via `[`, `[[`, and `$`. All replacement forms (`[<-`, `[[<-`, `$<-`) error, because
index-based assignment may break the ordering invariant. Ordered sequences may be cast down with `as_flexseq()` or `as.list()`. Named and unnamed elements cannot be mixed within one sequence.

```{r}
xs_named <- as_ordered_sequence(
  setNames(list("alice", "bob", "carol"), c("a", "b", "c")),
  keys = c(3, 1, 2)
)
xs_named

xs_named[["b"]]
xs_named[c("a", "c")]
xs_named[1]            # positional read also works

try(xs_named$a <- "!!")  # replacement blocked
```

## Transforming, iterating, merging

`fapply()` maps a function over elements while preserving keys and order. The function receives `(value, key)`, or `(value, key, name)` if it accepts a third argument. Keys and names are passed in read-only, and the return value replaces the stored element at the associated key (and name if named).

```{r}
xs_t <- ordered_sequence("alice", "bob", "carol", keys = c(3, 1, 2))
fapply(xs_t, function(value, key) toupper(value))
```

`loop()` (re-exported from the **coro** package) walks the sequence in key-ascending order, yielding bare values. Keys are dropped from each yield; use `fapply()` if your callback needs the key alongside the value, or iterate over `as.list()` when you want a list keyed by name.

```{r}
loop(for (v in xs_t) print(v))
```

Plain `for (v in xs_t)` (without `loop()`) does *not* dispatch to the iteration protocol, it walks the underlying internal structure and yields those rather than sequence elements. Always wrap with `loop()`.

`merge(x, y)` combines two ordered sequences into a new one in key order, preserving left-biased FIFO on duplicate keys (all of `x`'s entries at a tied key precede `y`'s). The general case runs in O(m + n); when the key ranges are disjoint it collapses to O(log(min(m, n))) via concat.

```{r}
a <- as_ordered_sequence(c("a1", "a2", "a3"), keys = c(1, 3, 5))
b <- as_ordered_sequence(c("b1", "b2", "b3"), keys = c(2, 3, 6))
merge(a, b)
```

Both sequences must share the same key type and monoid set; mismatches error. Both inputs are left unmodified.

## Example: scalar matching without replacement

Many potential uses for ordered sequences are handled well by named lists and vectors, where access-by-key is the primary functionality. In some cases we need to dynamically find, add, and remove elements by key, but as `vignette("benchmarks", package = "Immutables")` shows these operations are excessively slow on large base-R structures. Matching without replacement is one such case, often employed for cohort matching purposes in observational studies using propensity scores. Foregoing details, "treated" patients are matched to a subset of distinct "control" patients with similar scores. We start by simulating some populations and scores, and initialize an empty `flexseq` to store matches. We also convert the treated and untreated row numbers (serving as identifiers) to ordered sequences, keyed by their score.

```{r}
set.seed(100)
n_patients <- 200
patients <- data.frame(treated = sample(c(TRUE, FALSE),
                                        n_patients,
                                        prob = c(0.1, 0.9),
                                        replace = TRUE),
                       score = runif(n_patients))

# row numbers act as identifiers
treated_rows <- which(patients$treated)
treated_scores <- patients$score[patients$treated]

untreated_rows <- which(!patients$treated)
untreated_scores <- patients$score[!patients$treated]

matches <- flexseq()

treated_seq <- as_ordered_sequence(treated_rows, keys = treated_scores)
untreated_seq <- as_ordered_sequence(untreated_rows, keys = untreated_scores)
```

Matching itself is a simple greedy selection. Popping treated patients in order, each is matched to their nearest untreated record by score key, using `nearest_key()`. That patient is popped from wherever it was located, and a data frame describing the match is pushed onto the accumulating `flexseq`. This example also illustrates collecting these into a single result data frame for use after.

```{r}
while(length(treated_seq) > 0) {
  # no untreated patients left to match against
  if (length(untreated_seq) == 0L) break

  # pop the first (lowest-score) treated patient
  front_el <- pop_front(treated_seq)
  treated_seq <- front_el$remaining

  treated_pt_score <- front_el$key
  treated_pt_row   <- front_el$value

  # find and remove the nearest-score untreated patient
  match_key <- nearest_key(untreated_seq, treated_pt_score)
  match_el  <- pop_key(untreated_seq, match_key)
  untreated_seq <- match_el$remaining

  untreated_pt_score <- match_el$key
  untreated_pt_row   <- match_el$value

  match_row <- data.frame(treated_pt_row,
                          treated_pt_score,
                          untreated_pt_row,
                          untreated_pt_score)

  matches <- push_back(matches, match_row)
}

match_df <- do.call(rbind, as.list(matches))
head(match_df)
```