The hardware and bandwidth for this mirror is donated by dogado GmbH, the Webhosting and Full Service-Cloud Provider. Check out our Wordpress Tutorial.
If you wish to report a bug, or if you are interested in having us mirror your free-software or open-source project, please feel free to contact us at mirror[@]dogado.de.

immutables

Overview

immutables provides four fast data structures:

flexseq() - Provides list-like operations including indexed and named element access, push/pop/peek from either end for double-ended queue behavior, insertion, splitting, and concatenation.

priority_queue() - Associates items with priority values and provides min and max peek/pop by priority and fast insertion.

ordered_sequence() - Associates items with key values and keeps the elements in sorted order by key. These may be similarly be inserted/popped/peeked by key value as well as position. Keys may be duplicated, with first-in-first-out order within key groups.

interval_index() - Stores items associated with interval ranges, supporting point and interval overlap/containment/subsumption queries. Items are kept in interval-start-order.

A developer API exposes the underlying monoid-annotated finger tree primitives (custom monoids, predicate-based locate/split, validation helpers) for building new structures and indexes.

Quick Tour

flexseq

Construct, then push or pop at either end:

s <- flexseq("a", "b", "c", "d")
s |> push_front("z") |> push_back("e")
#> Unnamed flexseq with 6 elements.
#> 
#> Elements:
#> 
#> [[1]]
#> [1] "z"
#> 
#> [[2]]
#> [1] "a"
#> 
#> ... (skipping 2 elements)
#> 
#> [[5]]
#> [1] "d"
#> 
#> [[6]]
#> [1] "e"
pop_front(s)$remaining
#> Unnamed flexseq with 3 elements.
#> 
#> Elements:
#> 
#> [[1]]
#> [1] "b"
#> 
#> [[2]]
#> [1] "c"
#> 
#> [[3]]
#> [1] "d"

Random-access and positional edits:

s[[3]]
#> [1] "c"
peek_back(s)
#> [1] "d"
insert_at(s, 3, c("x", "y"))
#> Unnamed flexseq with 6 elements.
#> 
#> Elements:
#> 
#> [[1]]
#> [1] "a"
#> 
#> [[2]]
#> [1] "b"
#> 
#> ... (skipping 2 elements)
#> 
#> [[5]]
#> [1] "c"
#> 
#> [[6]]
#> [1] "d"

Map, concatenate, and iterate:

fapply(s, toupper)
#> Unnamed flexseq with 4 elements.
#> 
#> Elements:
#> 
#> [[1]]
#> [1] "A"
#> 
#> [[2]]
#> [1] "B"
#> 
#> [[3]]
#> [1] "C"
#> 
#> [[4]]
#> [1] "D"
c(s, as_flexseq(letters[10:12]))
#> Unnamed flexseq with 7 elements.
#> 
#> Elements:
#> 
#> [[1]]
#> [1] "a"
#> 
#> [[2]]
#> [1] "b"
#> 
#> ... (skipping 3 elements)
#> 
#> [[6]]
#> [1] "k"
#> 
#> [[7]]
#> [1] "l"
loop(for (el in s) print(el))
#> [1] "a"
#> [1] "b"
#> [1] "c"
#> [1] "d"

priority_queue

Construct with priorities, optionally with names, and insert more entries:

q <- priority_queue(a = "task_a", b = "task_b", c = "task_c", priorities = c(3, 1, 2)) |>
  insert("task_d", priority = 1, name = "d")

Peek/pop by min or max priority; the *_all_* variants handle ties:

peek_min(q)
#> [1] "task_b"
pop_max(q)$value
#> [1] "task_a"
pop_all_min(q)$elements
#> Named priority_queue with 2 elements.
#> Minimum priority: 1, Maximum priority: 1
#> 
#> Elements (by priority):
#> 
#> $b (priority 1)
#> [1] "task_b"
#> 
#> $d (priority 1)
#> [1] "task_d"

Read extrema and merge two queues into one:

min_priority(q); max_priority(q)
#> [1] 1
#> [1] 3
merge(q, priority_queue("task_e", priorities = 0))
#> Named priority_queue with 5 elements.
#> Minimum priority: 0, Maximum priority: 3
#> 
#> Elements (by priority):
#> 
#> (priority 0)
#> [1] "task_e"
#> 
#> $b (priority 1)
#> [1] "task_b"
#> 
#> ... (skipping 1 element)
#> 
#> $c (priority 2)
#> [1] "task_c"
#> 
#> $a (priority 3)
#> [1] "task_a"

ordered_sequence

Construct sorted by key (duplicates allowed, ties FIFO):

xs <- ordered_sequence("a1", "b1", "b2", "c1", keys = c(1, 2, 2, 3))
peek_key(xs, 2)
#> [1] "b1"
peek_all_key(xs, 2)
#> Unnamed ordered_sequence with 2 elements.
#> 
#> Elements (by key order):
#> 
#> [[1]] (key 2)
#> [1] "b1"
#> 
#> [[2]] (key 2)
#> [1] "b2"

Range queries and successor lookup:

count_between(xs, 1, 2)
#> [1] 3
elements_between(xs, 2, 3, include_to = FALSE)
#> Unnamed ordered_sequence with 2 elements.
#> 
#> Elements (by key order):
#> 
#> [[1]] (key 2)
#> [1] "b1"
#> 
#> [[2]] (key 2)
#> [1] "b2"
lower_bound(xs, 2)$index
#> [1] 2

Extrema and merge:

min_key(xs); max_key(xs)
#> [1] 1
#> [1] 3
merge(xs, ordered_sequence("d1", keys = 4))
#> Unnamed ordered_sequence with 5 elements.
#> 
#> Elements (by key order):
#> 
#> [[1]] (key 1)
#> [1] "a1"
#> 
#> [[2]] (key 2)
#> [1] "b1"
#> 
#> ... (skipping 1 element)
#> 
#> [[4]] (key 3)
#> [1] "c1"
#> 
#> [[5]] (key 4)
#> [1] "d1"

interval_index

Construct with start/end coordinates; entries stay in start order:

ix <- interval_index("A", "B", "C", start = c(1, 2, 4), end = c(3, 4, 5))
peek_point(ix, 2)
#> [1] "A"

Interval-relation queries (overlap, containment), plus sweep-line endpoint matches via match_at:

peek_all_overlaps(ix, start = 2, end = 5)
#> Unnamed interval_index with 3 elements, default query bounds [start, end).
#> 
#> Elements (by interval start order):
#> 
#> [[1]] (interval 1 - 3)
#> [1] "A"
#> 
#> [[2]] (interval 2 - 4)
#> [1] "B"
#> 
#> [[3]] (interval 4 - 5)
#> [1] "C"
peek_all_containing(ix, start = 2, end = 3)
#> Unnamed interval_index with 2 elements, default query bounds [start, end).
#> 
#> Elements (by interval start order):
#> 
#> [[1]] (interval 1 - 3)
#> [1] "A"
#> 
#> [[2]] (interval 2 - 4)
#> [1] "B"
peek_all_point(ix, point = 3, match_at = "end")
#> Unnamed interval_index with 1 element, default query bounds [start, end).
#> 
#> Elements (by interval start order):
#> 
#> [[1]] (interval 1 - 3)
#> [1] "A"

Endpoint extrema and merge:

min_endpoint(ix); max_endpoint(ix)
#> [1] 1
#> [1] 5
merge(ix, interval_index("D", start = 6, end = 8))
#> Unnamed interval_index with 4 elements, default query bounds [start, end).
#> 
#> Elements (by interval start order):
#> 
#> [[1]] (interval 1 - 3)
#> [1] "A"
#> 
#> [[2]] (interval 2 - 4)
#> [1] "B"
#> 
#> [[3]] (interval 4 - 5)
#> [1] "C"
#> 
#> [[4]] (interval 6 - 8)
#> [1] "D"

developer API

Define a custom monoid (here, a running sum) and attach it to any structure:

sum_monoid <- measure_monoid(f = `+`, i = 0, measure = function(el) el)
x <- as_flexseq(c(3, 1, 4, 1, 5, 9, 2, 6)) |>
  add_monoids(list(sum = sum_monoid))
get_measure(x, "sum")
#> [1] 31

Use a monotonic predicate over the cached measure for \(O(\log n)\) locate and split:

locate_by_predicate(x, function(v) v > 10, "sum")
#> $found
#> [1] TRUE
#> 
#> $value
#> [1] 5
split_around_by_predicate(x, function(v) v > 10, "sum")$value
#> [1] 5
validate_tree(x)

These binaries (installable software) and packages are in development.
They may not be fully stable and should be used with caution. We make no claims about them.
Health stats visible at Monitor.