| Title: | Fast and Functional Data Structures |
|---|---|
| Description: | Provides fast, side-effect free data structures, including catenable named lists, priority queues, double-ended queues, ordered sequences, and interval indices. Implementation is based on the finger-tree data structure of Hinze and Paterson (2006) <doi:10.1017/S0956796805005769>. |
| Authors: | Shawn T. O'Neil [aut, cre] |
| Maintainer: | Shawn T. O'Neil <[email protected]> |
| License: | MIT + file LICENSE |
| Version: | 1.0.1 |
| Built: | 2026-05-18 10:19:18 UTC |
| Source: | https://github.com/oneilsh/immutables |
Index, replace, and extract elements of a flexseq by position or name.
## S3 method for class 'flexseq' x$name ## S3 replacement method for class 'flexseq' x$name <- value ## S3 method for class 'flexseq' x[i, ...] ## S3 method for class 'flexseq' x[[i, ...]] ## S3 replacement method for class 'flexseq' x[i] <- value ## S3 replacement method for class 'flexseq' x[[i]] <- value## S3 method for class 'flexseq' x$name ## S3 replacement method for class 'flexseq' x$name <- value ## S3 method for class 'flexseq' x[i, ...] ## S3 method for class 'flexseq' x[[i, ...]] ## S3 replacement method for class 'flexseq' x[i] <- value ## S3 replacement method for class 'flexseq' x[[i]] <- value
x |
A |
name |
Element name (for |
value |
Replacement values; recycled to selected index length. |
i |
Positive integer indices, character element names, or logical mask.
For |
... |
Unused. |
Selector behavior:
Integer indexing ([) returns elements in the requested order.
Character indexing ([) returns elements in requested name order; unknown
names become NULL elements in the output.
Logical indexing ([) is positional and follows logical-mask selection.
Replacement behavior:
[<- is persistent and recycles value to the number of selected
positions (with standard R recycling warnings where applicable).
[[<- replaces one element; assigning NULL removes that element.
For $: the matched element.
For $<-: updated tree with one named element replaced.
For [: a new flexseq containing selected elements in query order.
For character indexing, missing names are represented as NULL elements.
For [[: the extracted element (internal name metadata is removed).
For [<-: a new flexseq with selected elements replaced.
For [[<-: a new flexseq with one element replaced.
# $ extracts by name x <- as_flexseq(setNames(as.list(1:3), c("a", "b", "c"))) x$b # $<- replaces by name x <- as_flexseq(setNames(as.list(1:3), c("a", "b", "c"))) x$b <- 20 x$b x <- as_flexseq(letters[1:6]) x x2 <- x[c(2, 4, 6)] x2 # named lookups return NULL for missing names x3 <- as_flexseq(setNames(as.list(letters[1:4]), c("w", "x", "y", "z"))) x4 <- x3[c("y", "missing", "w")] x4 # logical indexing supports recycling x[c(TRUE, FALSE)] # [[ extracts one element x <- as_flexseq(letters[1:5]) x[[3]] x2 <- as_flexseq(setNames(as.list(letters[1:3]), c("a1", "a2", "a3"))) x2[["a2"]] # [<- replaces selected elements x <- as_flexseq(1:6) x x2 <- x x2[c(2, 5)] <- list(20, 50) x2 # character replacement uses element names x3 <- as_flexseq(setNames(as.list(1:4), c("a", "b", "c", "d"))) x3[c("d", "a")] <- list(40, 10) x3 # logical replacement supports recycling x4 <- x x4[c(TRUE, FALSE, TRUE, FALSE, TRUE, FALSE)] <- list(1) x4 # [[<- replaces one element x <- as_flexseq(letters[1:4]) x2 <- x x2[[2]] <- "ZZ" x2 x3 <- as_flexseq(setNames(as.list(1:3), c("x", "y", "z"))) x3[["y"]] <- 99 x3 # assigning NULL removes one element x4 <- as_flexseq(letters[1:4]) x4[[2]] <- NULL x4# $ extracts by name x <- as_flexseq(setNames(as.list(1:3), c("a", "b", "c"))) x$b # $<- replaces by name x <- as_flexseq(setNames(as.list(1:3), c("a", "b", "c"))) x$b <- 20 x$b x <- as_flexseq(letters[1:6]) x x2 <- x[c(2, 4, 6)] x2 # named lookups return NULL for missing names x3 <- as_flexseq(setNames(as.list(letters[1:4]), c("w", "x", "y", "z"))) x4 <- x3[c("y", "missing", "w")] x4 # logical indexing supports recycling x[c(TRUE, FALSE)] # [[ extracts one element x <- as_flexseq(letters[1:5]) x[[3]] x2 <- as_flexseq(setNames(as.list(letters[1:3]), c("a1", "a2", "a3"))) x2[["a2"]] # [<- replaces selected elements x <- as_flexseq(1:6) x x2 <- x x2[c(2, 5)] <- list(20, 50) x2 # character replacement uses element names x3 <- as_flexseq(setNames(as.list(1:4), c("a", "b", "c", "d"))) x3[c("d", "a")] <- list(40, 10) x3 # logical replacement supports recycling x4 <- x x4[c(TRUE, FALSE, TRUE, FALSE, TRUE, FALSE)] <- list(1) x4 # [[<- replaces one element x <- as_flexseq(letters[1:4]) x2 <- x x2[[2]] <- "ZZ" x2 x3 <- as_flexseq(setNames(as.list(1:3), c("x", "y", "z"))) x3[["y"]] <- 99 x3 # assigning NULL removes one element x4 <- as_flexseq(letters[1:4]) x4[[2]] <- NULL x4
Attaches one or more named measure_monoid() definitions to an existing
immutable structure.
add_monoids(t, monoids, overwrite = FALSE)add_monoids(t, monoids, overwrite = FALSE)
t |
Immutable structure ( |
monoids |
Named list of |
overwrite |
Logical; if |
Mechanics:
Each monoid name defines an independent accumulated measure over elements in the tree.
New monoids are computed for all elements and cached in the returned object.
Existing monoids are unchanged unless overwrite = TRUE.
Structural/reserved monoid names cannot be replaced.
Measure-function signatures:
flexseq: measure(entry) where entry is the stored element.
ordered_sequence: measure(entry) where entry is list(value, key).
priority_queue: measure(entry) where entry is list(value, priority).
interval_index: measure(entry) where entry is list(value, start, end).
This operation is persistent: t is not modified.
Use this when you want fast predicate scans (for example with
locate_by_predicate(), split_by_predicate(), split_around_by_predicate())
driven by domain-specific accumulated values.
A persistent copy with updated monoid definitions and cached measures.
measure_monoid(), get_measure(), get_measures()
x <- flexseq(10, 20, 30) running_sum <- measure_monoid(`+`, 0, as.numeric) x2 <- add_monoids(x, list(sum = running_sum)) attr(x2, "measures")$sum # Use the monoid in a split query split_around_by_predicate(x2, function(v) v >= 30, "sum") # Overwrite an existing monoid definition running_count <- measure_monoid(`+`, 0L, function(e) 1L) x3 <- add_monoids(x2, list(sum = running_count), overwrite = TRUE) attr(x3, "measures")$sumx <- flexseq(10, 20, 30) running_sum <- measure_monoid(`+`, 0, as.numeric) x2 <- add_monoids(x, list(sum = running_sum)) attr(x2, "measures")$sum # Use the monoid in a split query split_around_by_predicate(x2, function(v) v >= 30, "sum") # Overwrite an existing monoid definition running_count <- measure_monoid(`+`, 0L, function(e) 1L) x3 <- add_monoids(x2, list(sum = running_count), overwrite = TRUE) attr(x3, "measures")$sum
flexseq
as_flexseq() is the canonical way to obtain a plain flexseq for full
sequence-style operations.
as_flexseq(x)as_flexseq(x)
x |
Input object. |
For base vectors/lists, this builds a new flexseq preserving element order
and names.
For specialized immutable subclasses (priority_queue,
ordered_sequence, interval_index), this intentionally drops subclass
semantics and returns a plain flexseq.
This is an S3 generic. Notable method behavior:
as_flexseq.flexseq(x) returns x unchanged.
as_flexseq.priority_queue(x) returns payload items.
as_flexseq.ordered_sequence(x) returns payload items.
as_flexseq.interval_index(x) returns payload items.
For advanced types, custom monoids are dropped and the rebuilt flexseq
keeps only structural monoids (.size, .named_count). For
priority_queue, a flexseq of full entry records can be obtained by
composing with as.list(): as_flexseq(as.list(x)). For
ordered_sequence and interval_index, as.list() also returns
payload-only lists, so no direct record-preserving cast is provided.
A plain flexseq.
flexseq(), priority_queue(), ordered_sequence(), interval_index()
x <- as_flexseq(1:3) x q <- priority_queue("a", "b", priorities = c(2, 1)) as_flexseq(q) o <- ordered_sequence("a", "b", keys = c(2, 1)) as_flexseq(o)x <- as_flexseq(1:3) x q <- priority_queue("a", "b", priorities = c(2, 1)) as_flexseq(q) o <- ordered_sequence("a", "b", keys = c(2, 1)) as_flexseq(o)
x, start, and end
Constructs an interval_index by pairing each element of x with
corresponding start and end endpoints.
as_interval_index(x, start, end, default_query_bounds = "[)")as_interval_index(x, start, end, default_query_bounds = "[)")
x |
Elements to add. |
start |
Start endpoints with the same length as |
end |
End endpoints with the same length as |
default_query_bounds |
Boundary convention used as the default for
query operations on this index: one of |
Output is ordered by interval start.
Names on x are preserved as element names.
An interval_index.
ix <- as_interval_index(c("a", "b", "c"), start = c(1, 2, 2), end = c(3, 2, 4)) ix as.list(peek_all_point(ix, 2)) # Endpoints can be other comparable types ix_date <- as_interval_index( c("phase1", "phase2"), start = as.Date(c("2024-01-01", "2024-01-10")), end = as.Date(c("2024-01-05", "2024-01-15")) ) ix_dateix <- as_interval_index(c("a", "b", "c"), start = c(1, 2, 2), end = c(3, 2, 4)) ix as.list(peek_all_point(ix, 2)) # Endpoints can be other comparable types ix_date <- as_interval_index( c("phase1", "phase2"), start = as.Date(c("2024-01-01", "2024-01-10")), end = as.Date(c("2024-01-05", "2024-01-15")) ) ix_date
flexseq (coro iterator)Returns a lazy iterator that yields payload elements left-to-right.
Use with loop() as the canonical iteration form:
## S3 method for class 'flexseq' as_iterator(x)## S3 method for class 'flexseq' as_iterator(x)
x |
A |
loop(for (x in s) print(x))
Iteration uses repeated left-view (viewL) and is O(n) total, O(1) amortized
per step. The original x is not modified; the iterator holds a private
cursor over progressively-smaller tails.
For named sequences, internal name metadata is stripped from yielded values
to match peek_front(s) semantics. Access names via as.list() when needed.
Inherited by ordered_sequence and interval_index: for those subclasses
the yielded value is the unwrapped payload (keys / interval endpoints
dropped), in key-ascending / start-position order respectively. See
as_iterator.priority_queue() for the priority-order override.
A coro iterator function.
for directlyWriting for (x in s) ... (without loop()) will not dispatch this method.
R's for walks the object's underlying list storage at the C level and
bypasses S3 length/[[, so it silently yields raw finger-tree internals
(Digit/Empty/Deep nodes) rather than sequence elements. Always wrap with
loop(), or call as.list() first for an eager copy.
s <- flexseq("a", "b", "c") loop(for (x in s) print(x))s <- flexseq("a", "b", "c") loop(for (x in s) print(x))
priority_queue (coro iterator)Returns a lazy iterator that yields payload elements in priority-ascending
order. Use with loop():
## S3 method for class 'priority_queue' as_iterator(x)## S3 method for class 'priority_queue' as_iterator(x)
x |
A |
loop(for (x in pq) print(x))
Traversal is driven by repeated pop_min(): each step is O(log n), so full
traversal is O(n log n). Ties within equal priorities are yielded in FIFO
insertion order (inherited from pop_min()).
The original x is not modified; the iterator holds a private cursor and
partial iteration (e.g. via break) leaves the source intact.
Each yielded value is the bare payload (matching peek_min()). Use
fapply() if your callback needs the priority alongside the value, or cast
with as_flexseq() for insertion-order iteration.
A coro iterator function.
pq <- priority_queue("a", "b", "c", priorities = c(3, 1, 2)) loop(for (x in pq) print(x)) # "b", "c", "a"pq <- priority_queue("a", "b", "c", priorities = c(3, 1, 2)) loop(for (x in pq) print(x)) # "b", "c", "a"
x and keys
Constructs an ordered_sequence by pairing each element of x with the
corresponding key in keys.
as_ordered_sequence(x, keys)as_ordered_sequence(x, keys)
x |
Elements to add. |
keys |
Key values with the same length as |
Output is always sorted by key.
Duplicate keys are allowed; ties preserve input order (stable/FIFO within the same key).
Names on x are preserved as element names.
An ordered_sequence.
xs <- as_ordered_sequence(c("d", "a", "b", "a2"), keys = c(4, 1, 2, 1)) xs length(elements_between(xs, 1, 1)) n <- as_ordered_sequence(setNames(as.list(c("a", "b")), c("ka", "kb")), keys = c(2, 1)) n[["kb"]] # Keys can be other comparable types num_by_chr <- as_ordered_sequence(c(20, 10, 30), keys = c("b", "a", "c")) num_by_chrxs <- as_ordered_sequence(c("d", "a", "b", "a2"), keys = c(4, 1, 2, 1)) xs length(elements_between(xs, 1, 1)) n <- as_ordered_sequence(setNames(as.list(c("a", "b")), c("ka", "kb")), keys = c(2, 1)) n[["kb"]] # Keys can be other comparable types num_by_chr <- as_ordered_sequence(c(20, 10, 30), keys = c("b", "a", "c")) num_by_chr
x and priorities
Constructs a queue by pairing each element of x with the corresponding
value in priorities.
as_priority_queue(x, priorities)as_priority_queue(x, priorities)
x |
Elements to enqueue. |
priorities |
Priorities with the same length as |
x is interpreted element-wise (via list coercion). Names on x are
preserved as queue element names.
All priorities must be non-missing and mutually comparable.
A priority_queue.
x <- as_priority_queue(letters[1:4], priorities = c(3, 1, 2, 1)) x peek_min(x) peek_max(x) # Names are preserved n <- as_priority_queue(setNames(as.list(1:3), c("a", "b", "c")), priorities = c(2, 1, 3)) n[["b"]]x <- as_priority_queue(letters[1:4], priorities = c(3, 1, 2, 1)) x peek_min(x) peek_max(x) # Names are preserved n <- as_priority_queue(setNames(as.list(1:3), c("a", "b", "c")), priorities = c(2, 1, 3)) n[["b"]]
Returns elements in left-to-right sequence order.
## S3 method for class 'flexseq' as.list(x, ...)## S3 method for class 'flexseq' as.list(x, ...)
x |
A |
... |
Unused. |
Returns payload elements in sequence order. If the sequence is fully named, those names are preserved on the returned list.
A base R list of sequence elements.
x <- flexseq("a", "b", "c") as.list(x) n <- flexseq(a = 1, b = 2) as.list(n)x <- flexseq("a", "b", "c") as.list(x) n <- flexseq(a = 1, b = 2) as.list(n)
Coerce Interval Index to List
## S3 method for class 'interval_index' as.list(x, ...)## S3 method for class 'interval_index' as.list(x, ...)
x |
An |
... |
Unused. |
This returns payload values only.
A plain list of payload elements in interval order.
ix <- interval_index("a", "b", "c", start = c(3, 1, 2), end = c(4, 2, 3)) as.list(ix)ix <- interval_index("a", "b", "c", start = c(3, 1, 2), end = c(4, 2, 3)) as.list(ix)
Coerce Ordered Sequence to List
## S3 method for class 'ordered_sequence' as.list(x, ...)## S3 method for class 'ordered_sequence' as.list(x, ...)
x |
An |
... |
Unused. |
Returns payload elements only (keys are omitted) in canonical key order. If entries are named, names are preserved on the returned list.
A plain list of elements in key order.
x <- ordered_sequence("a", "b", "c", keys = c(2, 1, 3)) as.list(x)x <- ordered_sequence("a", "b", "c", keys = c(2, 1, 3)) as.list(x)
Returns queue entries as a plain list of records with fields value and
priority, in queue sequence order.
## S3 method for class 'priority_queue' as.list(x, ..., drop_meta = FALSE)## S3 method for class 'priority_queue' as.list(x, ..., drop_meta = FALSE)
x |
A |
... |
Unused. |
drop_meta |
Logical scalar. When |
Each returned entry is a record with fields value and priority.
Entry names (when present) are preserved on the returned list.
A plain list of queue entry records (drop_meta = FALSE) or payload
values (drop_meta = TRUE).
q <- priority_queue("a", "b", priorities = c(2, 1)) as.list(q) as.list(q, drop_meta = TRUE)q <- priority_queue("a", "b", priorities = c(2, 1)) as.list(q) as.list(q, drop_meta = TRUE)
Concatenate Sequences
## S3 method for class 'flexseq' c(..., recursive = FALSE)## S3 method for class 'flexseq' c(..., recursive = FALSE)
... |
|
recursive |
Unused; must be |
c() is supported for flexseq and returns a new concatenated flexseq.
For priority_queue, ordered_sequence, and interval_index, c() is not
supported because concatenation can violate structure-specific invariants.
Cast first with as_flexseq() when sequence-style concatenation is intended,
noting that this drops ordering and priority metadata.
A concatenated flexseq.
x <- flexseq("a", "b") y <- flexseq("c", "d") c(x, y) q1 <- priority_queue("a", priorities = 2) q2 <- priority_queue("b", priorities = 1) try(c(q1, q2)) c(as_flexseq(q1), as_flexseq(q2)) o1 <- ordered_sequence("a", keys = 1) o2 <- ordered_sequence("b", keys = 2) try(c(o1, o2))x <- flexseq("a", "b") y <- flexseq("c", "d") c(x, y) q1 <- priority_queue("a", priorities = 2) q2 <- priority_queue("b", priorities = 1) try(c(q1, q2)) c(as_flexseq(q1), as_flexseq(q2)) o1 <- ordered_sequence("a", keys = 1) o2 <- ordered_sequence("b", keys = 2) try(c(o1, o2))
Count Elements in a Key Range
count_between(x, from_key, to_key, include_from = TRUE, include_to = TRUE)count_between(x, from_key, to_key, include_from = TRUE, include_to = TRUE)
x |
An |
from_key |
Lower bound key. |
to_key |
Upper bound key. |
include_from |
Include lower bound when |
include_to |
Include upper bound when |
Uses the same range semantics as elements_between() but returns only the
count:
include_from = TRUE uses key >= from_key; otherwise key > from_key.
include_to = TRUE uses key <= to_key; otherwise key < to_key.
Integer count of matches.
x <- ordered_sequence("a", "b", "c", "d", keys = c(1, 2, 2, 3)) count_between(x, 2, 3) count_between(x, 2, 2, include_to = FALSE)x <- ordered_sequence("a", "b", "c", "d", keys = c(1, 2, 2, 3)) count_between(x, 2, 3) count_between(x, 2, 2, include_to = FALSE)
Count Elements Matching One Key
count_key(x, key)count_key(x, key)
x |
An |
key |
Query key. |
Counts multiplicity for a single key. Returns 0L when the key is not
present.
Integer count of matches.
x <- ordered_sequence("a", "b", "c", keys = c(1, 2, 2)) count_key(x, 2) count_key(x, 10)x <- ordered_sequence("a", "b", "c", keys = c(1, 2, 2)) count_key(x, 2) count_key(x, 10)
Return Elements in a Key Range
elements_between(x, from_key, to_key, include_from = TRUE, include_to = TRUE)elements_between(x, from_key, to_key, include_from = TRUE, include_to = TRUE)
x |
An |
from_key |
Lower bound key. |
to_key |
Upper bound key. |
include_from |
Include lower bound when |
include_to |
Include upper bound when |
Range membership is controlled by include_from and include_to:
include_from = TRUE uses key >= from_key; otherwise key > from_key.
include_to = TRUE uses key <= to_key; otherwise key < to_key.
If no elements fall in the range, returns an empty ordered_sequence.
An ordered_sequence of matched elements, in key order. Use
as.list() to convert to a plain list.
x <- ordered_sequence("a", "b", "c", "d", keys = c(1, 2, 2, 3)) elements_between(x, 2, 3) as.list(elements_between(x, 2, 3)) elements_between(x, 2, 2, include_to = FALSE)x <- ordered_sequence("a", "b", "c", "d", keys = c(1, 2, 2, 3)) elements_between(x, 2, 3) as.list(elements_between(x, 2, 3)) elements_between(x, 2, 2, include_to = FALSE)
fapply() is an S3 generic for applying functions over immutable
structures with type-specific dispatch.
fapply(X, FUN, ...)fapply(X, FUN, ...)
X |
Object to apply over. |
FUN |
Function to apply. |
... |
Method-specific arguments. |
fapply() returns a new object and preserves class semantics.
Method signatures:
fapply.flexseq(X, FUN, ..., preserve_custom_monoids = TRUE)
fapply.priority_queue(X, FUN, ..., preserve_custom_monoids = TRUE)
fapply.ordered_sequence(X, FUN, ..., preserve_custom_monoids = TRUE)
fapply.interval_index(X, FUN, ..., preserve_custom_monoids = TRUE)
For priority_queue, ordered_sequence, and interval_index,
FUN receives structured fields (value plus metadata) and should return the
new payload value only; ordering metadata is preserved. The name argument is
optional: callbacks that only take value/metadata also work.
If supported by the method, preserve_custom_monoids = TRUE keeps added user
monoids; FALSE rebuilds with required structural monoids only.
Method-dependent result.
flexseq(), priority_queue(), ordered_sequence(), interval_index()
x <- flexseq("a", "b", "c") fapply(x, toupper) q <- priority_queue(one = "a", two = "b", priorities = c(2, 1)) fapply(q, function(value, priority, name) paste0(value, priority)) o <- ordered_sequence(one = "a", two = "b", keys = c(2, 1)) fapply(o, function(value, key, name) paste0(value, "_", key)) ix <- interval_index(one = "a", two = "b", start = c(1, 3), end = c(2, 4)) fapply(ix, function(value, start, end, name) paste0(value, "[", start, ",", end, "]"))x <- flexseq("a", "b", "c") fapply(x, toupper) q <- priority_queue(one = "a", two = "b", priorities = c(2, 1)) fapply(q, function(value, priority, name) paste0(value, priority)) o <- ordered_sequence(one = "a", two = "b", keys = c(2, 1)) fapply(o, function(value, key, name) paste0(value, "_", key)) ix <- interval_index(one = "a", two = "b", start = c(1, 3), end = c(2, 4)) fapply(ix, function(value, start, end, name) paste0(value, "[", start, ",", end, "]"))
flexseq(...) creates an immutable sequence from ..., preserving element
order and optional names, with efficient persistent updates.
flexseq(...)flexseq(...)
... |
Sequence elements. |
It is list-like in payload flexibility (any R object per element), but
sequence-oriented in API (push_*, peek_*, pop_*, indexing, split/concat).
flexseq is the base general-purpose structure in this package.
Specialized structures such as priority_queue, ordered_sequence, and
interval_index build on related internals but expose narrower semantics.
flexseq operations are persistent: updates return new objects and do not
mutate prior versions.
A flexseq object.
as_flexseq(), priority_queue(), ordered_sequence(), interval_index()
x <- flexseq(1, 2, 3) x y <- push_front(x, 0) y x # unchanged named <- flexseq(a = 1, b = 2) named named[["a"]]x <- flexseq(1, 2, 3) x y <- push_front(x, 0) y x # unchanged named <- flexseq(a = 1, b = 2) named named[["a"]]
Returns the monoid's accumulated measure across the whole (sub)tree at
the root of x. This is the cached value that internal operations use
for O(log n) locate and split.
get_measure(x, monoid_name)get_measure(x, monoid_name)
x |
A flexseq (or any immutables subclass). |
monoid_name |
Name of an attached monoid (e.g. |
On the full tree x, this is the aggregate over every element. After a
split — e.g. s <- split_by_predicate(x, p, "sum") — call
get_measure(s$left, "sum") to read the aggregate of just the left
side in O(1).
For per-element measures, see get_measures().
The cached monoid value at the root of x. Shape depends on
the monoid — typically atomic (e.g. a numeric sum) but may be a list
for built-ins that carry auxiliary state.
get_measures(), measure_monoid(), add_monoids()
sum_m <- measure_monoid(`+`, 0, function(el) el) x <- add_monoids(as_flexseq(c(3, 1, 4, 1, 5, 9, 2, 6)), list(sum = sum_m)) get_measure(x, "sum") # total across the whole tree get_measure(x, ".size") # built-in: element count q <- priority_queue("a", "b", "c", priorities = c(5, 1, 3)) get_measure(q, ".pq_min") # built-in, list-valuedsum_m <- measure_monoid(`+`, 0, function(el) el) x <- add_monoids(as_flexseq(c(3, 1, 4, 1, 5, 9, 2, 6)), list(sum = sum_m)) get_measure(x, "sum") # total across the whole tree get_measure(x, ".size") # built-in: element count q <- priority_queue("a", "b", "c", priorities = c(5, 1, 3)) get_measure(q, ".pq_min") # built-in, list-valued
Applies the named monoid's measure() function to each leaf entry in
sequence order, returning the results as a new flexseq.
get_measures(x, monoid_name)get_measures(x, monoid_name)
x |
A flexseq (or any immutables subclass). |
monoid_name |
Name of an attached monoid. |
Each leaf in a finger tree stores a structure-specific entry
(flexseq: the raw element; ordered_sequence: list(value, key);
priority_queue: list(value, priority); interval_index:
list(value, start, end)). A monoid's measure() function is defined
over that entry shape, and this accessor exposes the per-element
values that would be combined to produce the cached aggregate.
Returns a flexseq rather than a base list so results can be piped
back into other immutables operations; use as.list() or unlist()
to convert.
A plain unnamed flexseq of length length(x). Entry i is
the monoid's measure() applied to the i-th leaf entry.
get_measure(), measure_monoid(), fapply()
sum_m <- measure_monoid(`+`, 0, function(el) el) x <- add_monoids(as_flexseq(c(3, 1, 4, 1, 5, 9)), list(sum = sum_m)) get_measures(x, "sum") |> unlist() q <- priority_queue("a", "b", "c", priorities = c(5, 1, 3)) # Per-element .pq_min measures — each is list(has, priority). get_measures(q, ".pq_min")sum_m <- measure_monoid(`+`, 0, function(el) el) x <- add_monoids(as_flexseq(c(3, 1, 4, 1, 5, 9)), list(sum = sum_m)) get_measures(x, "sum") |> unlist() q <- priority_queue("a", "b", "c", priorities = c(5, 1, 3)) # Per-element .pq_min measures — each is list(has, priority). get_measures(q, ".pq_min")
Inserts an element into a structure-specific position according to class semantics.
insert(x, ...)insert(x, ...)
x |
Object to insert into. |
... |
Method-specific arguments. |
insert() is an S3 generic. Required arguments in ... depend on x:
priority_queue: element, priority (optional name)
ordered_sequence: element, key (optional name)
interval_index: element, start, end (optional name)
This operation is persistent: x is not modified.
Updated object of the same class as x.
priority_queue(), ordered_sequence(), interval_index(),
insert_at()
q <- priority_queue("a", "b", priorities = c(2, 1)) insert(q, "c", priority = 3) o <- ordered_sequence("a", "c", keys = c(1, 3)) insert(o, "b", key = 2) iv <- interval_index("A", "B", start = c(1, 5), end = c(3, 8)) insert(iv, "C", start = 2, end = 6)q <- priority_queue("a", "b", priorities = c(2, 1)) insert(q, "c", priority = 3) o <- ordered_sequence("a", "c", keys = c(1, 3)) insert(o, "b", key = 2) iv <- interval_index("A", "B", start = c(1, 5), end = c(3, 8)) insert(iv, "C", start = 2, end = 6)
Inserts values before the current element at index.
insert_at(x, index, values)insert_at(x, index, values)
x |
A |
index |
One-based insertion position in |
values |
Values to insert. |
values is interpreted as a collection of elements to splice in.
Common cases:
Atomic vector (c("x", "y")): inserts one element per vector entry.
List (list("x", "y")): inserts one element per list entry.
flexseq: inserts all of its elements.
Empty input (list() or flexseq()): no change.
To insert one composite object (for example, a vector or a list) as a single
element, wrap it in list(...).
This operation is persistent: x is not modified.
Updated sequence with inserted values.
x <- flexseq("a", "b", "c", "d") insert_at(x, 3, c("x", "y")) insert_at(x, 1, "start") insert_at(x, length(x) + 1, "end") # Insert one vector as a single element insert_at(x, 3, list(c("u", "v")))x <- flexseq("a", "b", "c", "d") insert_at(x, 3, c("x", "y")) insert_at(x, 1, "start") insert_at(x, length(x) + 1, "end") # Insert one vector as a single element insert_at(x, 3, list(c("u", "v")))
Convenience constructor from ..., start, and end.
interval_index(..., start, end, default_query_bounds = "[)")interval_index(..., start, end, default_query_bounds = "[)")
... |
Elements to add. |
start |
Start endpoints matching |
end |
End endpoints matching |
default_query_bounds |
Boundary convention used as the default for
query operations on this index: one of |
Empty construction is supported: interval_index() returns an empty index.
Output is ordered by interval start.
An interval_index.
ix <- interval_index("a", "b", "c", start = c(1, 2, 2), end = c(3, 2, 4)) ix interval_index()ix <- interval_index("a", "b", "c", start = c(1, 2, 2), end = c(3, 2, 4)) ix interval_index()
Sequence Length
## S3 method for class 'flexseq' length(x)## S3 method for class 'flexseq' length(x)
x |
A |
Uses cached size metadata and runs in O(1).
Number of elements in the sequence.
x <- flexseq("a", "b") length(x) length(flexseq())x <- flexseq("a", "b") length(x) length(flexseq())
Interval Index Length
## S3 method for class 'interval_index' length(x)## S3 method for class 'interval_index' length(x)
x |
An |
Uses cached size metadata and runs in O(1).
Number of indexed intervals.
ix <- interval_index("a", "b", start = c(1, 3), end = c(2, 5)) length(ix) length(interval_index())ix <- interval_index("a", "b", start = c(1, 3), end = c(2, 5)) length(ix) length(interval_index())
Ordered Sequence Length
## S3 method for class 'ordered_sequence' length(x)## S3 method for class 'ordered_sequence' length(x)
x |
An |
Uses cached size metadata and runs in O(1).
Integer length.
x <- ordered_sequence("a", "b", keys = c(2, 1)) length(x) length(ordered_sequence())x <- ordered_sequence("a", "b", keys = c(2, 1)) length(x) length(ordered_sequence())
Priority Queue Length
## S3 method for class 'priority_queue' length(x)## S3 method for class 'priority_queue' length(x)
x |
A |
Uses cached size metadata and runs in O(1).
Integer length.
q <- priority_queue("a", "b", priorities = c(2, 1)) length(q) length(priority_queue())q <- priority_queue("a", "b", priorities = c(2, 1)) length(q) length(priority_queue())
Scans accumulated monoid values and returns the first element where
predicate becomes TRUE, without rebuilding split trees.
locate_by_predicate( t, predicate, monoid_name, accumulator = NULL, include_metadata = FALSE )locate_by_predicate( t, predicate, monoid_name, accumulator = NULL, include_metadata = FALSE )
t |
A |
predicate |
Function applied to accumulated monoid values. |
monoid_name |
Name of the monoid used for scanning. |
accumulator |
Optional starting accumulator value. |
include_metadata |
Logical; include scan metadata. |
This is the read-only analogue of split_around_by_predicate().
As with split helpers, a common setup is a custom monoid created with
measure_monoid() and attached via add_monoids().
value is the matched leaf entry for the input structure:
flexseq: stored user element.
ordered_sequence: list(value, key).
priority_queue: list(value, priority).
interval_index: list(value, start, end).
If include_metadata = FALSE, a list with:
found: logical flag.
value: matched element when found, otherwise NULL.
If include_metadata = TRUE, adds metadata with:
left_measure
hit_measure
right_measure
index
x <- flexseq("a", "b", "c", "d") size_monoid <- measure_monoid(`+`, 0L, function(e) 1L) x2 <- add_monoids(x, list(size = size_monoid)) locate_by_predicate(x2, function(v) v >= 3L, "size") locate_by_predicate(x2, function(v) v >= 3L, "size", include_metadata = TRUE)x <- flexseq("a", "b", "c", "d") size_monoid <- measure_monoid(`+`, 0L, function(e) 1L) x2 <- add_monoids(x, list(size = size_monoid)) locate_by_predicate(x2, function(v) v >= 3L, "size") locate_by_predicate(x2, function(v) v >= 3L, "size", include_metadata = TRUE)
Re-exported coro::loop(). Enables for-loop-style iteration over
immutables structures without needing to load coro separately.
loop(loop)loop(loop)
loop |
A |
NULL, invisibly. Called for side effects.
coro::loop() for full documentation.
s <- flexseq(1, 2, 3) loop(for (x in s) print(x))s <- flexseq(1, 2, 3) loop(for (x in s) print(x))
>= QueryFind First Element with Key >= Query
lower_bound(x, key)lower_bound(x, key)
x |
An |
key |
Query key. |
lower_bound() finds the first element with key >= key. This includes an
exact key match when present, which is useful for starting equality or
inclusive range scans.
A list with fields:
found: logical flag.
index: one-based position of the first match, or NULL.
value: matched element, or NULL.
key: matched key, or NULL.
x <- ordered_sequence("a", "b", "c", keys = c(1, 2, 2)) lower_bound(x, 2) lower_bound(x, 10)x <- ordered_sequence("a", "b", "c", keys = c(1, 2, 2)) lower_bound(x, 2) lower_bound(x, 10)
Returns the largest right endpoint (end) currently present.
max_endpoint(x)max_endpoint(x)
x |
An |
Uses cached .ivx_max_end monoid state.
Maximum right endpoint, or NULL when x is empty.
ix <- interval_index("a", "b", start = c(3, 1), end = c(4, 2)) max_endpoint(ix) max_endpoint(interval_index())ix <- interval_index("a", "b", start = c(3, 1), end = c(4, 2)) max_endpoint(ix) max_endpoint(interval_index())
Returns the largest key currently present in the ordered sequence.
max_key(x)max_key(x)
x |
An |
Uses cached .oms_max_key monoid state.
Maximum key, or NULL when x is empty.
x <- ordered_sequence("a", "b", keys = c(2, 1)) max_key(x) max_key(ordered_sequence())x <- ordered_sequence("a", "b", keys = c(2, 1)) max_key(x) max_key(ordered_sequence())
Returns the current maximum priority scalar in the queue.
max_priority(x)max_priority(x)
x |
A |
Uses cached .pq_max monoid state.
Maximum priority value, or NULL when x is empty.
q <- priority_queue("a", "b", priorities = c(2, 1)) max_priority(q) max_priority(priority_queue())q <- priority_queue("a", "b", priorities = c(2, 1)) max_priority(q) max_priority(priority_queue())
Defines how element-level values are measured and combined as accumulated tree metadata.
measure_monoid(f, i, measure)measure_monoid(f, i, measure)
f |
Associative binary function over measure values. |
i |
Identity value for |
measure |
Function mapping one element to its measure value. |
A measure monoid has three parts:
measure(entry): maps each stored leaf entry to a measure value.
f(left, right): combines two measure values.
i: identity value for f.
Requirements:
f should be associative.
i should satisfy f(i, x) == x and f(x, i) == x.
measure() outputs must be compatible with f and i.
Developer APIs are leaf-entry oriented:
flexseq: entry is the stored user element.
ordered_sequence: entry is list(value, key).
priority_queue: entry is list(value, priority).
interval_index: entry is list(value, start, end).
measure_monoid() only constructs the specification; it becomes active after
being attached to a structure via add_monoids().
An object of class measure_monoid.
sum_m <- measure_monoid(`+`, 0, as.numeric) x <- as_flexseq(1:5) x2 <- add_monoids(x, list(sum = sum_m)) attr(x2, "measures")$sum split_around_by_predicate(x2, function(v) v >= 6, "sum") # Count elements count_m <- measure_monoid(`+`, 0L, function(el) 1L) x3 <- add_monoids(x, list(count = count_m)) attr(x3, "measures")$count # Character-width accumulation width_m <- measure_monoid(`+`, 0L, function(el) nchar(as.character(el))) s <- as_flexseq(c("aa", "b", "cccc")) s2 <- add_monoids(s, list(width = width_m)) attr(s2, "measures")$widthsum_m <- measure_monoid(`+`, 0, as.numeric) x <- as_flexseq(1:5) x2 <- add_monoids(x, list(sum = sum_m)) attr(x2, "measures")$sum split_around_by_predicate(x2, function(v) v >= 6, "sum") # Count elements count_m <- measure_monoid(`+`, 0L, function(el) 1L) x3 <- add_monoids(x, list(count = count_m)) attr(x3, "measures")$count # Character-width accumulation width_m <- measure_monoid(`+`, 0L, function(el) nchar(as.character(el))) s <- as_flexseq(c("aa", "b", "cccc")) s2 <- add_monoids(s, list(width = width_m)) attr(s2, "measures")$width
Returns a new flexseq containing all elements of x followed by all
elements of y. Thin wrapper over c() for API uniformity across the
package's merge methods; c(x, y) and merge(x, y) are equivalent for
flexseq.
## S3 method for class 'flexseq' merge(x, y, ...)## S3 method for class 'flexseq' merge(x, y, ...)
x |
A |
y |
A |
... |
Unused. |
For ordered types (ordered_sequence, interval_index), merge() performs
a proper sorted merge respecting keys/intervals — see merge.ordered_sequence()
and merge.interval_index(). For priority_queue, see
merge.priority_queue().
A new flexseq.
x <- flexseq("a", "b") y <- flexseq("c", "d") merge(x, y)x <- flexseq("a", "b") y <- flexseq("c", "d") merge(x, y)
Returns a new interval_index containing every entry from both inputs,
preserving start-position order. On tied start positions, x's entries
precede y's (left-biased FIFO).
## S3 method for class 'interval_index' merge(x, y, ...)## S3 method for class 'interval_index' merge(x, y, ...)
x |
An |
y |
An |
... |
Unused. |
The merge runs in O(m + n) via a zipper-style traversal on interval starts, with a fast path to O(log(min(m, n))) when the start ranges are disjoint.
Both indices must share the same endpoint type and the same bounds
convention (e.g. "[)" half-open vs. "[]" closed), and the same
monoid set. Mismatches error.
The reserved monoids .ivx_min_end / .ivx_max_end recompute
automatically on the merged tree, so min_endpoint() / max_endpoint()
and interval-relation queries work immediately on the result.
Both inputs are left unmodified.
A new interval_index of size length(x) + length(y).
a <- interval_index("A1", "A2", start = c(1, 5), end = c(4, 8)) b <- interval_index("B1", "B2", start = c(3, 7), end = c(6, 10)) m <- merge(a, b) as.list(m)a <- interval_index("A1", "A2", start = c(1, 5), end = c(4, 8)) b <- interval_index("B1", "B2", start = c(3, 7), end = c(6, 10)) m <- merge(a, b) as.list(m)
Returns a new ordered_sequence containing every entry from both inputs,
preserving key order. On duplicate keys, x's entries precede y's
(left-biased FIFO).
## S3 method for class 'ordered_sequence' merge(x, y, ...)## S3 method for class 'ordered_sequence' merge(x, y, ...)
x |
An |
y |
An |
... |
Unused. |
The merge runs in O(m + n) via a zipper-style traversal, with a fast path
to O(log(min(m, n))) when the key ranges are disjoint (all of x's keys
<= all of y's keys, or vice versa with a strict < to keep
left-biased FIFO intact on equal boundary keys).
Both sequences must share the same key type and the same monoid set; mismatches error rather than being silently harmonized. Merging an empty sequence with a non-empty sequence returns the non-empty one unchanged.
Both inputs are left unmodified.
A new ordered_sequence of size length(x) + length(y).
a <- ordered_sequence("a1", "a2", "a3", keys = c(1, 3, 5)) b <- ordered_sequence("b1", "b2", "b3", keys = c(2, 3, 6)) m <- merge(a, b) as.list(m) # At the tied key 3, "a2" precedes "b2".a <- ordered_sequence("a1", "a2", "a3", keys = c(1, 3, 5)) b <- ordered_sequence("b1", "b2", "b3", keys = c(2, 3, 6)) m <- merge(a, b) as.list(m) # At the tied key 3, "a2" precedes "b2".
Returns a new priority_queue containing every entry from both inputs,
preserving each queue's internal insertion order (entries of x come
first, then entries of y).
## S3 method for class 'priority_queue' merge(x, y, ...)## S3 method for class 'priority_queue' merge(x, y, ...)
x |
A |
y |
A |
... |
Unused. |
The cached .pq_min / .pq_max monoids recompute automatically on the
merged tree, so peek_min() / peek_max() reflect the combined extremum
immediately.
Both queues must share the same priority type and the same monoid set; mismatches error rather than being silently harmonized. Merging an empty queue with a non-empty queue returns the non-empty queue unchanged.
Both inputs are left unmodified.
A new priority_queue of size length(x) + length(y).
a <- priority_queue("x", "y", priorities = c(5, 1)) b <- priority_queue("z", priorities = 3) m <- merge(a, b) peek_min(m) length(m)a <- priority_queue("x", "y", priorities = c(5, 1)) b <- priority_queue("z", priorities = 3) m <- merge(a, b) peek_min(m) length(m)
Returns the smallest left endpoint (start) currently present.
min_endpoint(x)min_endpoint(x)
x |
An |
Because intervals are stored in start order, this reads the first entry's
start.
Minimum left endpoint, or NULL when x is empty.
ix <- interval_index("a", "b", start = c(3, 1), end = c(4, 2)) min_endpoint(ix) min_endpoint(interval_index())ix <- interval_index("a", "b", start = c(3, 1), end = c(4, 2)) min_endpoint(ix) min_endpoint(interval_index())
Returns the smallest key currently present in the ordered sequence.
min_key(x)min_key(x)
x |
An |
This follows sequence key order directly.
Minimum key, or NULL when x is empty.
x <- ordered_sequence("a", "b", keys = c(2, 1)) min_key(x) min_key(ordered_sequence())x <- ordered_sequence("a", "b", keys = c(2, 1)) min_key(x) min_key(ordered_sequence())
Returns the current minimum priority scalar in the queue.
min_priority(x)min_priority(x)
x |
A |
Uses cached .pq_min monoid state.
Minimum priority value, or NULL when x is empty.
q <- priority_queue("a", "b", priorities = c(2, 1)) min_priority(q) min_priority(priority_queue())q <- priority_queue("a", "b", priorities = c(2, 1)) min_priority(q) min_priority(priority_queue())
Convenience constructor from ... and matching keys.
ordered_sequence(..., keys)ordered_sequence(..., keys)
... |
Elements to add. |
keys |
Key values with the same length as |
Empty construction is supported: ordered_sequence() returns an empty
ordered sequence.
Output is always sorted by key, with stable order across duplicate keys.
An ordered_sequence.
xs <- ordered_sequence("bb", "a", "ccc", keys = c(2, 1, 3)) xs lower_bound(xs, 2) num_by_chr <- ordered_sequence(20, 10, 30, keys = c("b", "a", "c")) num_by_chr ordered_sequence()xs <- ordered_sequence("bb", "a", "ccc", keys = c(2, 1, 3)) xs lower_bound(xs, 2) num_by_chr <- ordered_sequence(20, 10, 30, keys = c("b", "a", "c")) num_by_chr ordered_sequence()
Peek All Intervals Containing a Query Interval
peek_all_containing(x, start, end, bounds = NULL)peek_all_containing(x, start, end, bounds = NULL)
x |
An |
start |
Query interval start. |
end |
Query interval end. |
bounds |
Optional boundary override. One of |
The returned interval_index can be inspected with as.list().
An interval_index slice of all matches (possibly empty).
ix <- interval_index("a", "b", "c", start = c(1, 2, 4), end = c(6, 5, 7)) as.list(peek_all_containing(ix, 2, 4))ix <- interval_index("a", "b", "c", start = c(1, 2, 4), end = c(6, 5, 7)) as.list(peek_all_containing(ix, 2, 4))
Returns all elements whose key equals key.
peek_all_key(x, key)peek_all_key(x, key)
x |
An |
key |
Query key. |
The returned ordered_sequence can be inspected with as.list().
An ordered_sequence containing all matches; empty on miss.
x <- ordered_sequence("a", "b", "c", keys = c(1, 2, 2)) out <- peek_all_key(x, 2) as.list(out)x <- ordered_sequence("a", "b", "c", keys = c(1, 2, 2)) out <- peek_all_key(x, 2) as.list(out)
Returns the full maximum-priority tie run as a priority_queue.
peek_all_max(x)peek_all_max(x)
x |
A |
The return is another priority_queue(), use as.list() to convert
the result to a standard R list.
A priority_queue containing all maximum-priority elements in stable
queue order. Returns an empty queue when x is empty.
x <- priority_queue("a", "b", "c", priorities = c(2, 3, 3)) peek_all_max(x)x <- priority_queue("a", "b", "c", priorities = c(2, 3, 3)) peek_all_max(x)
Returns the full minimum-priority tie run as a priority_queue.
peek_all_min(x)peek_all_min(x)
x |
A |
The return is another priority_queue(), use as.list() to convert
the result to a standard R list.
A priority_queue containing all minimum-priority elements in stable
queue order. Returns an empty queue when x is empty.
x <- priority_queue("a", "b", "c", priorities = c(2, 1, 1)) peek_all_min(x)x <- priority_queue("a", "b", "c", priorities = c(2, 1, 1)) peek_all_min(x)
Peek All Intervals Overlapping a Query Interval
peek_all_overlaps(x, start, end, bounds = NULL)peek_all_overlaps(x, start, end, bounds = NULL)
x |
An |
start |
Query interval start. |
end |
Query interval end. |
bounds |
Optional boundary override. One of |
The returned interval_index can be inspected with as.list().
An interval_index slice of all matches (possibly empty).
ix <- interval_index("a", "b", "c", start = c(1, 3, 5), end = c(2, 4, 6)) as.list(peek_all_overlaps(ix, 2, 5))ix <- interval_index("a", "b", "c", start = c(1, 3, 5), end = c(2, 4, 6)) as.list(peek_all_overlaps(ix, 2, 5))
Peek All Intervals Matching a Point
peek_all_point( x, point, bounds = NULL, match_at = c("interval", "start", "end", "either") )peek_all_point( x, point, bounds = NULL, match_at = c("interval", "start", "end", "either") )
x |
An |
point |
Query point. |
bounds |
Optional boundary override. One of |
match_at |
How the query point is matched against each entry. One of
|
The returned interval_index can be inspected with as.list().
An interval_index slice of all matches (possibly empty).
ix <- interval_index("a", "b", "c", start = c(1, 2, 4), end = c(3, 2, 5)) as.list(peek_all_point(ix, 2)) # Entries ending at 3 as.list(peek_all_point(ix, 3, match_at = "end"))ix <- interval_index("a", "b", "c", start = c(1, 2, 4), end = c(3, 2, 5)) as.list(peek_all_point(ix, 2)) # Entries ending at 3 as.list(peek_all_point(ix, 3, match_at = "end"))
Peek All Intervals Within a Query Interval
peek_all_within(x, start, end, bounds = NULL)peek_all_within(x, start, end, bounds = NULL)
x |
An |
start |
Query interval start. |
end |
Query interval end. |
bounds |
Optional boundary override. One of |
The returned interval_index can be inspected with as.list().
An interval_index slice of all matches (possibly empty).
ix <- interval_index("a", "b", "c", start = c(1, 2, 4), end = c(6, 3, 5)) as.list(peek_all_within(ix, 1, 4))ix <- interval_index("a", "b", "c", start = c(1, 2, 4), end = c(6, 3, 5)) as.list(peek_all_within(ix, 1, 4))
Returns the element at a one-based index without modifying the sequence.
peek_at(x, index)peek_at(x, index)
x |
A |
index |
One-based position to read. |
Positive integer indices beyond length(x) return NULL.
Invalid indices (NA, non-integer, <= 0, or length not equal to 1) error.
Element at index, or NULL when index is out of bounds.
x <- flexseq("a", "b", "c") peek_at(x, 2) peek_at(x, 10) try(peek_at(x, 0))x <- flexseq("a", "b", "c") peek_at(x, 2) peek_at(x, 10) try(peek_at(x, 0))
Returns the last element without modifying the sequence.
peek_back(x)peek_back(x)
x |
A |
Returns the payload element without modifying x.
Last element, or NULL when x is empty.
x <- flexseq("a", "b", "c") peek_back(x) peek_back(flexseq())x <- flexseq("a", "b", "c") peek_back(x) peek_back(flexseq())
Peek First Interval Containing a Query Interval
peek_containing(x, start, end, bounds = NULL)peek_containing(x, start, end, bounds = NULL)
x |
An |
start |
Query interval start. |
end |
Query interval end. |
bounds |
Optional boundary override. One of |
Returns the first match in canonical interval order. Use
peek_all_containing() to retrieve all matches as an interval_index slice.
The payload value from the first match, or NULL on no match.
ix <- interval_index("a", "b", "c", start = c(1, 2, 4), end = c(5, 3, 6)) peek_containing(ix, 2, 3)ix <- interval_index("a", "b", "c", start = c(1, 2, 4), end = c(5, 3, 6)) peek_containing(ix, 2, 3)
Returns the first element without modifying the sequence.
peek_front(x)peek_front(x)
x |
A |
Returns the payload element without modifying x.
First element, or NULL when x is empty.
x <- flexseq("a", "b", "c") peek_front(x) peek_front(flexseq())x <- flexseq("a", "b", "c") peek_front(x) peek_front(flexseq())
Returns the first element whose key equals key.
peek_key(x, key)peek_key(x, key)
x |
An |
key |
Query key. |
For duplicate keys, this returns the first element in stable sequence order.
Matched element, or NULL when no matching key exists.
x <- ordered_sequence("a", "b", "c", keys = c(1, 2, 2)) peek_key(x, 2) peek_key(x, 10)x <- ordered_sequence("a", "b", "c", keys = c(1, 2, 2)) peek_key(x, 2) peek_key(x, 10)
Returns the element at the maximum priority without modifying the queue.
peek_max(x)peek_max(x)
x |
A |
Ties are stable: when multiple elements share maximum priority, this returns the earliest element in queue order.
Element at maximum priority, or NULL when x is empty.
x <- priority_queue("a", "b", "c", priorities = c(2, 3, 3)) peek_max(x) peek_max(priority_queue())x <- priority_queue("a", "b", "c", priorities = c(2, 3, 3)) peek_max(x) peek_max(priority_queue())
Returns the element at the minimum priority without modifying the queue.
peek_min(x)peek_min(x)
x |
A |
Ties are stable: when multiple elements share minimum priority, this returns the earliest element in queue order.
Element at minimum priority, or NULL when x is empty.
x <- priority_queue("a", "b", "c", priorities = c(2, 1, 1)) peek_min(x) peek_min(priority_queue())x <- priority_queue("a", "b", "c", priorities = c(2, 1, 1)) peek_min(x) peek_min(priority_queue())
Peek First Interval Overlapping a Query Interval
peek_overlaps(x, start, end, bounds = NULL)peek_overlaps(x, start, end, bounds = NULL)
x |
An |
start |
Query interval start. |
end |
Query interval end. |
bounds |
Optional boundary override. One of |
Returns the first match in canonical interval order. Use
peek_all_overlaps() to retrieve all matches as an interval_index slice.
The payload value from the first match, or NULL on no match.
ix <- interval_index("a", "b", "c", start = c(1, 3, 5), end = c(2, 4, 6)) peek_overlaps(ix, 2, 3) # Boundary override at touching endpoints edge <- interval_index("a", start = 1, end = 3, default_query_bounds = "[)") peek_overlaps(edge, 3, 4) # default "[)": no endpoint overlap peek_overlaps(edge, 3, 4, bounds = "[]") # closed bounds: endpoint overlapsix <- interval_index("a", "b", "c", start = c(1, 3, 5), end = c(2, 4, 6)) peek_overlaps(ix, 2, 3) # Boundary override at touching endpoints edge <- interval_index("a", start = 1, end = 3, default_query_bounds = "[)") peek_overlaps(edge, 3, 4) # default "[)": no endpoint overlap peek_overlaps(edge, 3, 4, bounds = "[]") # closed bounds: endpoint overlaps
Peek First Interval Matching a Point
peek_point( x, point, bounds = NULL, match_at = c("interval", "start", "end", "either") )peek_point( x, point, bounds = NULL, match_at = c("interval", "start", "end", "either") )
x |
An |
point |
Query point. |
bounds |
Optional boundary override. One of |
match_at |
How the query point is matched against each entry. One of
|
Returns the first match in canonical interval order. Use peek_all_point() to
retrieve all matches as an interval_index slice.
The payload value from the first match, or NULL on no match.
ix <- interval_index("a", "b", "c", start = c(1, 2, 4), end = c(3, 2, 5)) peek_point(ix, 2) # Boundary override at an endpoint edge <- interval_index("a", start = 1, end = 3, default_query_bounds = "[)") peek_point(edge, 3) # default "[)": no match at right endpoint peek_point(edge, 3, bounds = "[]") # closed bounds: endpoint matches # Coordinate-equality modes (bounds irrelevant) peek_point(ix, 2, match_at = "start") # entry starting at 2 peek_point(ix, 3, match_at = "end") # entry ending at 3ix <- interval_index("a", "b", "c", start = c(1, 2, 4), end = c(3, 2, 5)) peek_point(ix, 2) # Boundary override at an endpoint edge <- interval_index("a", start = 1, end = 3, default_query_bounds = "[)") peek_point(edge, 3) # default "[)": no match at right endpoint peek_point(edge, 3, bounds = "[]") # closed bounds: endpoint matches # Coordinate-equality modes (bounds irrelevant) peek_point(ix, 2, match_at = "start") # entry starting at 2 peek_point(ix, 3, match_at = "end") # entry ending at 3
Peek First Interval Within a Query Interval
peek_within(x, start, end, bounds = NULL)peek_within(x, start, end, bounds = NULL)
x |
An |
start |
Query interval start. |
end |
Query interval end. |
bounds |
Optional boundary override. One of |
Returns the first match in canonical interval order. Use peek_all_within()
to retrieve all matches as an interval_index slice.
The payload value from the first match, or NULL on no match.
ix <- interval_index("a", "b", "c", start = c(1, 2, 4), end = c(6, 3, 5)) peek_within(ix, 1, 4)ix <- interval_index("a", "b", "c", start = c(1, 2, 4), end = c(6, 3, 5)) peek_within(ix, 1, 4)
Developer-facing visualizer for the finger-tree backing any immutables
structure (flexseq, ordered_sequence, priority_queue,
interval_index). The S3 plot() methods on those classes forward to
this function, but plot_structure() is also callable directly and gives
access to the full node_label API for custom label formatting. Requires
the igraph package (listed in Suggests).
plot_structure( t1, vertex.size = 15, vertex.shape = "rounded_rect", edge.width = 1, label_edges = FALSE, title = NULL, node_label = "value", label.cex = NULL, asp = NA, legend = TRUE, ... )plot_structure( t1, vertex.size = 15, vertex.shape = "rounded_rect", edge.width = 1, label_edges = FALSE, title = NULL, node_label = "value", label.cex = NULL, asp = NA, legend = TRUE, ... )
t1 |
A finger-tree-backed immutables structure. |
vertex.size |
Passed to |
vertex.shape |
Vertex shape. Defaults to |
edge.width |
Edge width passed to |
label_edges |
If |
title |
Optional plot title. |
node_label |
Either one of the preset modes
Measure values are exposed as-is, including list-valued measures
(e.g. the built-in |
label.cex |
Numeric scalar controlling label text size (passed as
|
asp |
Plot aspect ratio (physical y-unit / physical x-unit).
Default |
legend |
If |
... |
Additional arguments passed to |
Invoked for its side effect (draws to the active graphics
device). Returns NULL invisibly.
measure_monoid(), add_monoids()
if (requireNamespace("igraph", quietly = TRUE)) { t <- as_flexseq(letters[1:8]) plot_structure(t, title = "Finger tree") # Label every node with its subtree size (leaves contribute 1). plot_structure(as_flexseq(1:10), node_label = function(node) { paste0(node$type, "\n.size=", node$measures$.size) }) # Custom monoid: subtree sum of numeric payloads. Structural nodes show # the accumulated total; leaves show their own contribution. sum_monoid <- measure_monoid(`+`, 0, function(el) el) xs <- add_monoids(as_flexseq(c(3, 1, 4, 1, 5, 9, 2, 6)), list(sum = sum_monoid)) plot_structure(xs, node_label = function(node) { if(node$type == "Element") sprintf("%g\nsum=%g", node$element, node$measures$sum) else sprintf("%s\nsum=%g", node$type, node$measures$sum) }) # List-valued built-in measure: priority_queue's .pq_min tracks the min # priority seen in a subtree as list(has, priority). Unpack in the label. pq <- priority_queue("task-a", "task-b", "task-c", priorities = c(5, 1, 3)) plot_structure(pq, node_label = function(node) { m <- node$measures$.pq_min if(node$type == "Element") { sprintf("%s\np=%g", node$element$value, node$element$priority) } else if(isTRUE(m$has)) { sprintf("%s\nmin=%g", node$type, m$priority) } else { node$type } }) }if (requireNamespace("igraph", quietly = TRUE)) { t <- as_flexseq(letters[1:8]) plot_structure(t, title = "Finger tree") # Label every node with its subtree size (leaves contribute 1). plot_structure(as_flexseq(1:10), node_label = function(node) { paste0(node$type, "\n.size=", node$measures$.size) }) # Custom monoid: subtree sum of numeric payloads. Structural nodes show # the accumulated total; leaves show their own contribution. sum_monoid <- measure_monoid(`+`, 0, function(el) el) xs <- add_monoids(as_flexseq(c(3, 1, 4, 1, 5, 9, 2, 6)), list(sum = sum_monoid)) plot_structure(xs, node_label = function(node) { if(node$type == "Element") sprintf("%g\nsum=%g", node$element, node$measures$sum) else sprintf("%s\nsum=%g", node$type, node$measures$sum) }) # List-valued built-in measure: priority_queue's .pq_min tracks the min # priority seen in a subtree as list(has, priority). Unpack in the label. pq <- priority_queue("task-a", "task-b", "task-c", priorities = c(5, 1, 3)) plot_structure(pq, node_label = function(node) { m <- node$measures$.pq_min if(node$type == "Element") { sprintf("%s\np=%g", node$element$value, node$element$priority) } else if(isTRUE(m$has)) { sprintf("%s\nmin=%g", node$type, m$priority) } else { node$type } }) }
Pop All Containing Intervals
pop_all_containing(x, start, end, bounds = NULL)pop_all_containing(x, start, end, bounds = NULL)
x |
An |
start |
Query interval start. |
end |
Query interval end. |
bounds |
Optional boundary override. One of |
Use as.list() to convert elements to a standard R list.
A list with elements and remaining, both interval_index objects.
ix <- interval_index("a", "b", "c", start = c(1, 2, 4), end = c(6, 5, 7)) out <- pop_all_containing(ix, 2, 4) as.list(out$elements)ix <- interval_index("a", "b", "c", start = c(1, 2, 4), end = c(6, 5, 7)) out <- pop_all_containing(ix, 2, 4) as.list(out$elements)
Removes and returns all elements whose key equals key.
pop_all_key(x, key)pop_all_key(x, key)
x |
An |
key |
Query key. |
Use as.list() to convert elements to a standard R list.
A list with fields:
elements: ordered_sequence of removed matches.
remaining: ordered_sequence after removal.
x <- ordered_sequence("a", "b", "c", keys = c(1, 2, 2)) out <- pop_all_key(x, 2) as.list(out$elements) out$remainingx <- ordered_sequence("a", "b", "c", keys = c(1, 2, 2)) out <- pop_all_key(x, 2) as.list(out$elements) out$remaining
Removes the full maximum-priority tie run.
pop_all_max(x)pop_all_max(x)
x |
A |
The return elements is another priority_queue(), use as.list() to
convert the result to a standard R list.
A list with fields:
elements: priority_queue of removed maximum-priority elements.
remaining: queue after removal.
x <- priority_queue("a", "b", "c", priorities = c(2, 3, 3)) out <- pop_all_max(x) out$elements out$remainingx <- priority_queue("a", "b", "c", priorities = c(2, 3, 3)) out <- pop_all_max(x) out$elements out$remaining
Removes the full minimum-priority tie run.
pop_all_min(x)pop_all_min(x)
x |
A |
The return elements is another priority_queue(), use as.list() to
convert the result to a standard R list.
A list with fields:
elements: priority_queue of removed minimum-priority elements.
remaining: queue after removal.
x <- priority_queue("a", "b", "c", priorities = c(2, 1, 1)) out <- pop_all_min(x) out$elements out$remainingx <- priority_queue("a", "b", "c", priorities = c(2, 1, 1)) out <- pop_all_min(x) out$elements out$remaining
Pop All Overlapping Intervals
pop_all_overlaps(x, start, end, bounds = NULL)pop_all_overlaps(x, start, end, bounds = NULL)
x |
An |
start |
Query interval start. |
end |
Query interval end. |
bounds |
Optional boundary override. One of |
Use as.list() to convert elements to a standard R list.
A list with elements and remaining, both interval_index objects.
ix <- interval_index("a", "b", "c", start = c(1, 3, 5), end = c(2, 4, 6)) out <- pop_all_overlaps(ix, 2, 5) as.list(out$elements)ix <- interval_index("a", "b", "c", start = c(1, 3, 5), end = c(2, 4, 6)) out <- pop_all_overlaps(ix, 2, 5) as.list(out$elements)
Pop All Intervals Matching a Point
pop_all_point( x, point, bounds = NULL, match_at = c("interval", "start", "end", "either") )pop_all_point( x, point, bounds = NULL, match_at = c("interval", "start", "end", "either") )
x |
An |
point |
Query point. |
bounds |
Optional boundary override. One of |
match_at |
How the query point is matched against each entry. One of
|
Use as.list() to convert elements to a standard R list.
A list with elements and remaining, both interval_index objects.
ix <- interval_index("a", "b", "c", start = c(1, 2, 4), end = c(3, 2, 5)) out <- pop_all_point(ix, 2) as.list(out$elements) # Sweep-line retirement: remove everything ending at x = 3 retired <- pop_all_point(ix, 3, match_at = "end") as.list(retired$elements) as.list(retired$remaining)ix <- interval_index("a", "b", "c", start = c(1, 2, 4), end = c(3, 2, 5)) out <- pop_all_point(ix, 2) as.list(out$elements) # Sweep-line retirement: remove everything ending at x = 3 retired <- pop_all_point(ix, 3, match_at = "end") as.list(retired$elements) as.list(retired$remaining)
Pop All Intervals Within a Query Interval
pop_all_within(x, start, end, bounds = NULL)pop_all_within(x, start, end, bounds = NULL)
x |
An |
start |
Query interval start. |
end |
Query interval end. |
bounds |
Optional boundary override. One of |
Use as.list() to convert elements to a standard R list.
A list with elements and remaining, both interval_index objects.
ix <- interval_index("a", "b", "c", start = c(1, 2, 4), end = c(6, 3, 5)) out <- pop_all_within(ix, 1, 4) as.list(out$elements)ix <- interval_index("a", "b", "c", start = c(1, 2, 4), end = c(6, 3, 5)) out <- pop_all_within(ix, 1, 4) as.list(out$elements)
Returns the selected element and the remaining sequence.
pop_at(x, index)pop_at(x, index)
x |
A |
index |
One-based position to remove. |
This operation is persistent: x is not modified.
Positive integer indices beyond length(x) return a non-throwing miss object
with value = NULL and remaining = x.
Invalid indices (NA, non-integer, <= 0, or length not equal to 1) error.
A list with fields:
value: the element at index, or NULL when index is out of bounds.
remaining: the sequence after removing the selected element.
x <- flexseq("a", "b", "c", "d") out <- pop_at(x, 3) out$value out$remaining x # unchanged pop_at(x, 10) try(pop_at(x, 0))x <- flexseq("a", "b", "c", "d") out <- pop_at(x, 3) out$value out$remaining x # unchanged pop_at(x, 10) try(pop_at(x, 0))
Returns the last element and the remaining sequence.
pop_back(x)pop_back(x)
x |
A |
This operation is persistent: x is not modified.
On empty input, returns a non-throwing miss object with
value = NULL and remaining = x.
A list with fields:
value: the last element, or NULL when x is empty.
remaining: the sequence after removing the last element.
s <- flexseq("a", "b", "c") out <- pop_back(s) out$value out$remaining s # unchanged pop_back(flexseq())s <- flexseq("a", "b", "c") out <- pop_back(s) out$value out$remaining s # unchanged pop_back(flexseq())
Pop First Containing Interval
pop_containing(x, start, end, bounds = NULL)pop_containing(x, start, end, bounds = NULL)
x |
An |
start |
Query interval start. |
end |
Query interval end. |
bounds |
Optional boundary override. One of |
Removes the first match in canonical interval order. On miss, returns a
non-throwing miss object with remaining = x.
Use pop_all_containing() to remove all matches.
A list with element, start, end, and remaining.
On miss: element, start, and end are NULL.
ix <- interval_index("a", "b", "c", start = c(1, 2, 4), end = c(6, 3, 7)) pop_containing(ix, 2, 4)ix <- interval_index("a", "b", "c", start = c(1, 2, 4), end = c(6, 3, 7)) pop_containing(ix, 2, 4)
Returns the first element and the remaining sequence.
pop_front(x)pop_front(x)
x |
A |
This operation is persistent: x is not modified.
On empty input, returns a non-throwing miss object with
value = NULL and remaining = x.
A list with fields:
value: the first element, or NULL when x is empty.
remaining: the sequence after removing the first element.
s <- flexseq("a", "b", "c") out <- pop_front(s) out$value out$remaining s # unchanged pop_front(flexseq())s <- flexseq("a", "b", "c") out <- pop_front(s) out$value out$remaining s # unchanged pop_front(flexseq())
Removes and returns the first element whose key equals key.
pop_key(x, key)pop_key(x, key)
x |
An |
key |
Query key. |
For duplicate keys, the first element in stable sequence order is removed.
A list with fields:
value: removed element, or NULL on miss.
key: removed key, or NULL on miss.
remaining: ordered sequence after removal.
x <- ordered_sequence("a", "b", "c", keys = c(1, 2, 2)) out <- pop_key(x, 2) out$value out$remaining pop_key(x, 10)x <- ordered_sequence("a", "b", "c", keys = c(1, 2, 2)) out <- pop_key(x, 2) out$value out$remaining pop_key(x, 10)
Removes one maximum-priority element and returns it with the remaining queue.
pop_max(x)pop_max(x)
x |
A |
Ties are stable: when multiple elements share maximum priority, the earliest element in queue order is removed.
A list with fields:
value: removed element, or NULL when x is empty.
priority: removed priority, or NULL when x is empty.
remaining: queue after removal.
x <- priority_queue("a", "b", "c", priorities = c(2, 3, 3)) out <- pop_max(x) out$value out$priority out$remaining pop_max(priority_queue())x <- priority_queue("a", "b", "c", priorities = c(2, 3, 3)) out <- pop_max(x) out$value out$priority out$remaining pop_max(priority_queue())
Removes one minimum-priority element and returns it with the remaining queue.
pop_min(x)pop_min(x)
x |
A |
Ties are stable: when multiple elements share minimum priority, the earliest element in queue order is removed.
A list with fields:
value: removed element, or NULL when x is empty.
priority: removed priority, or NULL when x is empty.
remaining: queue after removal.
x <- priority_queue("a", "b", "c", priorities = c(2, 1, 1)) out <- pop_min(x) out$value out$priority out$remaining pop_min(priority_queue())x <- priority_queue("a", "b", "c", priorities = c(2, 1, 1)) out <- pop_min(x) out$value out$priority out$remaining pop_min(priority_queue())
Pop First Overlapping Interval
pop_overlaps(x, start, end, bounds = NULL)pop_overlaps(x, start, end, bounds = NULL)
x |
An |
start |
Query interval start. |
end |
Query interval end. |
bounds |
Optional boundary override. One of |
Removes the first match in canonical interval order. On miss, returns a
non-throwing miss object with remaining = x.
Use pop_all_overlaps() to remove all matches.
A list with element, start, end, and remaining.
On miss: element, start, and end are NULL.
ix <- interval_index("a", "b", "c", start = c(1, 3, 5), end = c(2, 4, 6)) pop_overlaps(ix, 2, 3)ix <- interval_index("a", "b", "c", start = c(1, 3, 5), end = c(2, 4, 6)) pop_overlaps(ix, 2, 3)
Pop First Interval Matching a Point
pop_point( x, point, bounds = NULL, match_at = c("interval", "start", "end", "either") )pop_point( x, point, bounds = NULL, match_at = c("interval", "start", "end", "either") )
x |
An |
point |
Query point. |
bounds |
Optional boundary override. One of |
match_at |
How the query point is matched against each entry. One of
|
Removes the first match in canonical interval order. On miss, returns a
non-throwing miss object with remaining = x.
Use pop_all_point() to remove all matches.
A list with element, start, end, and remaining.
On miss: element, start, and end are NULL.
ix <- interval_index("a", "b", "c", start = c(1, 2, 4), end = c(3, 2, 5)) pop_point(ix, 2)ix <- interval_index("a", "b", "c", start = c(1, 2, 4), end = c(3, 2, 5)) pop_point(ix, 2)
Pop First Interval Within a Query Interval
pop_within(x, start, end, bounds = NULL)pop_within(x, start, end, bounds = NULL)
x |
An |
start |
Query interval start. |
end |
Query interval end. |
bounds |
Optional boundary override. One of |
Removes the first match in canonical interval order. On miss, returns a
non-throwing miss object with remaining = x.
Use pop_all_within() to remove all matches.
A list with element, start, end, and remaining.
On miss: element, start, and end are NULL.
ix <- interval_index("a", "b", "c", start = c(1, 2, 4), end = c(6, 3, 5)) pop_within(ix, 1, 4)ix <- interval_index("a", "b", "c", start = c(1, 2, 4), end = c(6, 3, 5)) pop_within(ix, 1, 4)
Print a flexseq
## S3 method for class 'flexseq' print(x, max_elements = 4L, show_custom_monoids = FALSE, ...)## S3 method for class 'flexseq' print(x, max_elements = 4L, show_custom_monoids = FALSE, ...)
x |
A |
max_elements |
Maximum number of elements shown in preview ( |
show_custom_monoids |
Logical; show attached non-default monoids and their root cached measures. |
... |
Passed through to per-element |
The input x, returned invisibly. Called for its side effect
of printing a formatted preview of the sequence to the console.
x <- as_flexseq(setNames(as.list(1:6), letters[1:6])) print(x, max_elements = 4) y <- as_flexseq(as.list(1:6)) print(y, max_elements = 3)x <- as_flexseq(setNames(as.list(1:6), letters[1:6])) print(x, max_elements = 4) y <- as_flexseq(as.list(1:6)) print(y, max_elements = 3)
Prints a compact summary with interval bounds and a head/tail preview of payload elements.
## S3 method for class 'interval_index' print(x, max_elements = 4L, show_custom_monoids = FALSE, ...)## S3 method for class 'interval_index' print(x, max_elements = 4L, show_custom_monoids = FALSE, ...)
x |
An |
max_elements |
Maximum number of elements shown in the preview. |
show_custom_monoids |
Logical; show attached non-default monoids and their root cached measures. |
... |
Passed through to per-element |
Invisibly returns x.
ix <- interval_index( one = 1, two = 2, three = 3, start = c(20, 30, 10), end = c(25, 37, 24) ) print(ix, max_elements = 4) width_sum <- measure_monoid( `+`, 0, function(entry) as.numeric(entry$end - entry$start) ) ix3 <- add_monoids( interval_index(1, 2, start = c(1, 3), end = c(2, 5)), list(width_sum = width_sum) ) print(ix3, max_elements = 0, show_custom_monoids = TRUE) ix2 <- interval_index(1, 2, 3, start = c(2, 4, 6), end = c(3, 5, 8), default_query_bounds = "[]") print(ix2, max_elements = 3) print(interval_index())ix <- interval_index( one = 1, two = 2, three = 3, start = c(20, 30, 10), end = c(25, 37, 24) ) print(ix, max_elements = 4) width_sum <- measure_monoid( `+`, 0, function(entry) as.numeric(entry$end - entry$start) ) ix3 <- add_monoids( interval_index(1, 2, start = c(1, 3), end = c(2, 5)), list(width_sum = width_sum) ) print(ix3, max_elements = 0, show_custom_monoids = TRUE) ix2 <- interval_index(1, 2, 3, start = c(2, 4, 6), end = c(3, 5, 8), default_query_bounds = "[]") print(ix2, max_elements = 3) print(interval_index())
Prints a compact summary and head/tail preview in key order.
## S3 method for class 'ordered_sequence' print(x, max_elements = 4L, show_custom_monoids = FALSE, ...)## S3 method for class 'ordered_sequence' print(x, max_elements = 4L, show_custom_monoids = FALSE, ...)
x |
An |
max_elements |
Maximum number of elements shown in the preview. |
show_custom_monoids |
Logical; show attached non-default monoids and their root cached measures. |
... |
Passed through to per-element |
Invisibly returns x.
xs <- ordered_sequence(one = "a", two = "b", three = "c", keys = c(20, 30, 10)) print(xs, max_elements = 4) sum_key <- measure_monoid(`+`, 0, function(entry) as.numeric(entry$key)) ys2 <- add_monoids(ordered_sequence("a", "b", keys = c(2, 1)), list(sum_key = sum_key)) print(ys2, max_elements = 0, show_custom_monoids = TRUE) ys <- ordered_sequence("x", "y", "z", keys = c(2, 1, 3)) print(ys, max_elements = 3) print(ordered_sequence())xs <- ordered_sequence(one = "a", two = "b", three = "c", keys = c(20, 30, 10)) print(xs, max_elements = 4) sum_key <- measure_monoid(`+`, 0, function(entry) as.numeric(entry$key)) ys2 <- add_monoids(ordered_sequence("a", "b", keys = c(2, 1)), list(sum_key = sum_key)) print(ys2, max_elements = 0, show_custom_monoids = TRUE) ys <- ordered_sequence("x", "y", "z", keys = c(2, 1, 3)) print(ys, max_elements = 3) print(ordered_sequence())
Prints a compact summary with priority range and a head/tail preview.
## S3 method for class 'priority_queue' print(x, max_elements = 4L, show_custom_monoids = FALSE, ...)## S3 method for class 'priority_queue' print(x, max_elements = 4L, show_custom_monoids = FALSE, ...)
x |
A |
max_elements |
Maximum number of elements shown in the preview. |
show_custom_monoids |
Logical; show attached non-default monoids and their root cached measures. |
... |
Passed through to per-element |
Invisibly returns x.
q <- priority_queue(one = 1, two = 2, three = 3, priorities = c(20, 30, 10)) print(q, max_elements = 4) sum_item <- measure_monoid(`+`, 0, function(entry) as.numeric(entry$value)) q3 <- add_monoids(priority_queue(1, 2, priorities = c(2, 1)), list(sum_item = sum_item)) print(q3, max_elements = 0, show_custom_monoids = TRUE) q2 <- priority_queue(1, 2, 3, priorities = c(2, 1, 3)) print(q2, max_elements = 3) print(priority_queue())q <- priority_queue(one = 1, two = 2, three = 3, priorities = c(20, 30, 10)) print(q, max_elements = 4) sum_item <- measure_monoid(`+`, 0, function(entry) as.numeric(entry$value)) q3 <- add_monoids(priority_queue(1, 2, priorities = c(2, 1)), list(sum_item = sum_item)) print(q3, max_elements = 0, show_custom_monoids = TRUE) q2 <- priority_queue(1, 2, 3, priorities = c(2, 1, 3)) print(q2, max_elements = 3) print(priority_queue())
Creates a priority_queue from elements in ... and matching
priorities.
priority_queue(..., priorities)priority_queue(..., priorities)
... |
Elements to enqueue. |
priorities |
Priorities with the same length as |
Empty construction is supported: priority_queue() returns an empty queue.
If elements are named, names are preserved for name-based reads.
Queue operations are exposed through insert(), peek_*(), pop_*(),
and fapply().
A priority_queue.
x <- priority_queue("a", "b", "c", priorities = c(2, 1, 2)) x peek_min(x) empty_q <- priority_queue() peek_min(empty_q)x <- priority_queue("a", "b", "c", priorities = c(2, 1, 2)) x peek_min(x) empty_q <- priority_queue() peek_min(empty_q)
Returns a new sequence with value appended at the right end.
push_back(x, value)push_back(x, value)
x |
A |
value |
Element to append. |
This operation is persistent: x is not modified.
Elements can be named, but only if all are uniquely named (no missing names).
Updated flexseq.
s <- as_flexseq(letters[1:3]) s2 <- push_back(s, "d") s2 s # unchanged n <- as_flexseq(list(two = 2, three = 3)) new_el <- 4 names(new_el) <- "four" push_back(n, new_el) # Named/unnamed mixes are rejected try(push_back(n, 5))s <- as_flexseq(letters[1:3]) s2 <- push_back(s, "d") s2 s # unchanged n <- as_flexseq(list(two = 2, three = 3)) new_el <- 4 names(new_el) <- "four" push_back(n, new_el) # Named/unnamed mixes are rejected try(push_back(n, 5))
Returns a new sequence with value prepended at the left end.
push_front(x, value)push_front(x, value)
x |
A |
value |
Element to prepend. |
This operation is persistent: x is not modified.
Elements can be named, but only if all are uniquely named (no missing names).
Updated flexseq.
s <- as_flexseq(letters[2:4]) s2 <- push_front(s, "a") s2 s # unchanged n <- as_flexseq(list(two = 2, three = 3)) new_el <- 1 names(new_el) <- "one" push_front(n, new_el) # Named/unnamed mixes are rejected try(push_front(n, 0))s <- as_flexseq(letters[2:4]) s2 <- push_front(s, "a") s2 s # unchanged n <- as_flexseq(list(two = 2, three = 3)) new_el <- 1 names(new_el) <- "one" push_front(n, new_el) # Named/unnamed mixes are rejected try(push_front(n, 0))
Splits at the first point where a predicate function becomes TRUE
while scanning the sequence.
split_around_by_predicate(t, predicate, monoid_name, accumulator = NULL)split_around_by_predicate(t, predicate, monoid_name, accumulator = NULL)
t |
A |
predicate |
Function applied to accumulated monoid values. |
monoid_name |
Name of the monoid used for scanning. |
accumulator |
Optional starting accumulator value. |
This function generally requires the sequence be annotated with
a measure_monoid(); see the examples and measure_monoid()
for more information.
value is the matched leaf entry for the input structure:
flexseq: stored user element.
ordered_sequence: list(value, key).
priority_queue: list(value, priority).
interval_index: list(value, start, end).
left and right preserve subclass when the input is a subclass of
flexseq.
A list with fields:
left: elements before the split point.
value: the matched element at the split point.
right: elements after the split point.
x <- flexseq("a", "b", "c", "d") # Each element e has measure 1; the accumulated measure for # a set of elements is computed by the associative function `+` # along with the identity value 0. size_monoid <- measure_monoid(`+`, 0L, function(e) 1L) x2 <- add_monoids(x, list(size = size_monoid)) # the first time the measure stored in the size monoid # accumulates to greater than or equal to 3 is the 3rd # element in sequence. split_around_by_predicate(x2, function(v) v >= 3L, "size") # Split at the first element split_around_by_predicate(x2, function(v) v >= 1L, "size") # Split at the last element split_around_by_predicate(x2, function(v) v >= 4L, "size")x <- flexseq("a", "b", "c", "d") # Each element e has measure 1; the accumulated measure for # a set of elements is computed by the associative function `+` # along with the identity value 0. size_monoid <- measure_monoid(`+`, 0L, function(e) 1L) x2 <- add_monoids(x, list(size = size_monoid)) # the first time the measure stored in the size monoid # accumulates to greater than or equal to 3 is the 3rd # element in sequence. split_around_by_predicate(x2, function(v) v >= 3L, "size") # Split at the first element split_around_by_predicate(x2, function(v) v >= 1L, "size") # Split at the last element split_around_by_predicate(x2, function(v) v >= 4L, "size")
Splits by a single one-based position or a single element name.
split_at(x, at, pull_index = FALSE)split_at(x, at, pull_index = FALSE)
x |
A |
at |
A single positive integer position or a single character name. |
pull_index |
Controls output shape:
|
split_at(x, at, pull_index = FALSE) is a convenience wrapper around
split_around_by_predicate() using positional scanning.
split_at(x, at, pull_index = TRUE) is the two-way variant using
split_by_predicate().
A split result with shape controlled by pull_index.
x <- flexseq("a", "b", "c", "d") split_at(x, 3) split_at(x, 3, pull_index = TRUE) n <- flexseq(a = 1, b = 2, c = 3) split_at(n, "b")x <- flexseq("a", "b", "c", "d") split_at(x, 3) split_at(x, 3, pull_index = TRUE) n <- flexseq(a = 1, b = 2, c = 3) split_at(n, "b")
Splits at the first point where predicate becomes TRUE while scanning
the sequence.
split_by_predicate(x, predicate, monoid_name)split_by_predicate(x, predicate, monoid_name)
x |
A |
predicate |
Function applied to accumulated monoid values. |
monoid_name |
Name of the monoid used for scanning. |
This is the two-way variant of split_around_by_predicate().
As with split_around_by_predicate(), a common setup is a custom monoid
created with measure_monoid() and attached via add_monoids().
left and right preserve subclass when the input is a subclass of
flexseq.
A list with fields:
left: elements before the split point.
right: elements from the split point onward.
x <- flexseq("a", "b", "c", "d") size_monoid <- measure_monoid(`+`, 0L, function(e) 1L) x2 <- add_monoids(x, list(size = size_monoid)) split_by_predicate(x2, function(v) v >= 3L, "size") # Split at the first element split_by_predicate(x2, function(v) v >= 1L, "size")x <- flexseq("a", "b", "c", "d") size_monoid <- measure_monoid(`+`, 0L, function(e) 1L) x2 <- add_monoids(x, list(size = size_monoid)) split_by_predicate(x2, function(v) v >= 3L, "size") # Split at the first element split_by_predicate(x2, function(v) v >= 1L, "size")
Read indexing returns interval_index subsets while preserving interval/key
order; out-of-order selectors are canonicalized with a warning. Replacement
indexing is blocked.
## S3 method for class 'interval_index' x[i, ...] ## S3 method for class 'interval_index' x[[i, ...]] ## S3 replacement method for class 'interval_index' x[i] <- value ## S3 replacement method for class 'interval_index' x[[i]] <- value ## S3 method for class 'interval_index' x$name ## S3 replacement method for class 'interval_index' x$name <- value## S3 method for class 'interval_index' x[i, ...] ## S3 method for class 'interval_index' x[[i, ...]] ## S3 replacement method for class 'interval_index' x[i] <- value ## S3 replacement method for class 'interval_index' x[[i]] <- value ## S3 method for class 'interval_index' x$name ## S3 replacement method for class 'interval_index' x$name <- value
x |
An |
i |
Index input. |
... |
Unused. |
value |
Replacement value (unsupported). |
name |
Element name (for |
Read indexing preserves canonical interval order in returned subsets.
Integer/character vectors are treated as selectors and canonicalized to interval-order output.
Out-of-order selector vectors trigger a warning and are canonicalized.
Duplicate selectors are rejected.
[[ and $ return payload values.
Replacement indexing ([<-, [[<-, $<-) is unsupported.
Read methods return interval payload values/subsets; replacement forms always error.
For $: the matched payload element.
No return value; always errors because replacement indexing is unsupported.
ix <- interval_index(a = "A", b = "B", c = "C", start = c(1, 3, 5), end = c(2, 4, 6)) ix[c(3, 1)] # warning; result returned in interval order ix[c("c", "a")] # warning; result returned in interval order ix[c(TRUE, FALSE, TRUE)] ix[["b"]] ix$b try(ix[c(2, 2)]) try(ix$b <- "updated")ix <- interval_index(a = "A", b = "B", c = "C", start = c(1, 3, 5), end = c(2, 4, 6)) ix[c(3, 1)] # warning; result returned in interval order ix[c("c", "a")] # warning; result returned in interval order ix[c(TRUE, FALSE, TRUE)] ix[["b"]] ix$b try(ix[c(2, 2)]) try(ix$b <- "updated")
Read indexing treats vectors as selectors and returns subsets in key order. Out-of-order selectors are canonicalized with a warning. Replacement indexing is blocked to prevent order-breaking writes.
## S3 method for class 'ordered_sequence' x[i, ...] ## S3 method for class 'ordered_sequence' x[[i, ...]] ## S3 replacement method for class 'ordered_sequence' x[i] <- value ## S3 replacement method for class 'ordered_sequence' x[[i]] <- value ## S3 method for class 'ordered_sequence' x$name ## S3 replacement method for class 'ordered_sequence' x$name <- value## S3 method for class 'ordered_sequence' x[i, ...] ## S3 method for class 'ordered_sequence' x[[i, ...]] ## S3 replacement method for class 'ordered_sequence' x[i] <- value ## S3 replacement method for class 'ordered_sequence' x[[i]] <- value ## S3 method for class 'ordered_sequence' x$name ## S3 replacement method for class 'ordered_sequence' x$name <- value
x |
An |
i |
Index input. |
... |
Unused. |
value |
Replacement value (unsupported). |
name |
Element name (for |
Vector selectors are treated as membership selectors, not output-order instructions.
Integer/character vectors are normalized to unique positions and returned in canonical sequence order.
Out-of-order selector vectors trigger a warning and are canonicalized.
Duplicate selectors are rejected.
Replacement indexing ([<-, [[<-, $<-) is unsupported.
Read methods return ordered payload values/subsets; replacement forms always error.
x <- ordered_sequence(a = "A", b = "B", c = "C", keys = c(1, 2, 3)) x[c(3, 1)] # warning; result returned in key order x[c("c", "a")] # warning; result returned in key order x[c(TRUE, FALSE, TRUE)] x[["b"]] x$b try(x[c(2, 2)]) try(x$b <- "updated")x <- ordered_sequence(a = "A", b = "B", c = "C", keys = c(1, 2, 3)) x[c(3, 1)] # warning; result returned in key order x[c("c", "a")] # warning; result returned in key order x[c(TRUE, FALSE, TRUE)] x[["b"]] x$b try(x[c(2, 2)]) try(x$b <- "updated")
Name-based indexing is supported for reads only. Positional indexing and all replacement indexing are intentionally blocked to preserve queue-first UX.
## S3 method for class 'priority_queue' x[i, ...] ## S3 method for class 'priority_queue' x[[i, ...]] ## S3 replacement method for class 'priority_queue' x[i] <- value ## S3 replacement method for class 'priority_queue' x[[i]] <- value ## S3 method for class 'priority_queue' x$name ## S3 replacement method for class 'priority_queue' x$name <- value## S3 method for class 'priority_queue' x[i, ...] ## S3 method for class 'priority_queue' x[[i, ...]] ## S3 replacement method for class 'priority_queue' x[i] <- value ## S3 replacement method for class 'priority_queue' x[[i]] <- value ## S3 method for class 'priority_queue' x$name ## S3 replacement method for class 'priority_queue' x$name <- value
x |
A |
i |
Index input. For reads, must be a character name (scalar for |
... |
Unused. |
value |
Replacement value (unsupported). |
name |
Element name (for |
priority_queue supports name-based read indexing only.
[: character vector of names, returns a priority_queue subset.
[[ and $: scalar name, return the payload value.
Positional indexing and all replacement indexing forms are unsupported.
For $/[[/[: queue payload values or queue subsets by name.
Replacement forms always error.
q <- priority_queue(a = "task-a", b = "task-b", priorities = c(2, 1)) q["a"] q[["b"]] q$b try(q[1]) try(q$a <- "updated")q <- priority_queue(a = "task-a", b = "task-b", priorities = c(2, 1)) q["a"] q[["b"]] q$b try(q[1]) try(q$a <- "updated")
Convenience wrapper around base::unlist() over as.list().
## S3 method for class 'flexseq' unlist(x, recursive = TRUE, use.names = TRUE)## S3 method for class 'flexseq' unlist(x, recursive = TRUE, use.names = TRUE)
x |
A |
recursive |
Passed through to |
use.names |
Passed through to |
For priority_queue, this unwraps queue entries to payload items before
unlisting (equivalent to unlist(as.list(x, drop_meta = TRUE), ...)).
Inherited by ordered_sequence and interval_index through the shared
class stack.
An atomic vector built from as.list.flexseq().
x <- flexseq(1, 2, 3) unlist(x) q <- priority_queue("a", "b", priorities = c(2, 1)) unlist(q)x <- flexseq(1, 2, 3) unlist(x) q <- priority_queue("a", "b", priorities = c(2, 1)) unlist(q)
> QueryFind First Element with Key > Query
upper_bound(x, key)upper_bound(x, key)
x |
An |
key |
Query key. |
upper_bound() finds the first element with key > key. This skips exact
key matches, which is useful for exclusive range endpoints and for finding
the position immediately after a duplicate-key run.
A list with fields:
found: logical flag.
index: one-based position of the first match, or NULL.
value: matched element, or NULL.
key: matched key, or NULL.
x <- ordered_sequence("a", "b", "c", keys = c(1, 2, 2)) upper_bound(x, 2) upper_bound(x, 10)x <- ordered_sequence("a", "b", "c", keys = c(1, 2, 2)) upper_bound(x, 2) upper_bound(x, 10)
Checks that trees are either fully unnamed or fully named with unique, non-empty names.
validate_name_state(t)validate_name_state(t)
t |
FingerTree. |
Intended for debugging and tests, not hot runtime paths.
TRUE invisibly; errors if name invariants are violated.
x <- as_flexseq(setNames(as.list(letters[1:4]), letters[1:4])) validate_name_state(x)x <- as_flexseq(setNames(as.list(letters[1:4]), letters[1:4])) validate_name_state(x)
Performs expensive full-tree auditing of:
structural attributes (monoids/measures) consistency
global name-state invariants
validate_tree(t)validate_tree(t)
t |
FingerTree. |
Intended for debugging and tests, not hot runtime paths.
TRUE invisibly; errors if invariant violations are found.
x <- as_flexseq(letters[1:10]) validate_tree(x)x <- as_flexseq(letters[1:10]) validate_tree(x)