Ordered Sequences

In Immutables: Fast and Functional Data Structures

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.

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.

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.

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.

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.

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).

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.

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.

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).

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).

min_key(xs)
max_key(xs)
min_key(ordered_sequence())  # NULL when empty

Empty sequences

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

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.

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, aterating, 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).

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.

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.

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.

Immutables documentation built on April 29, 2026, 1:06 a.m.