R/immutables-package.R

In Immutables: Fast and Functional Data Structures

#' Immutables: Fast and Functional Data Structures
#'
#' The `Immutables` R package implements several immutable, or persistent, data
#' structures: operations return modified copies while remaining fast and true
#' to R's side-effect-free functional nature.
#'
#' - `flexseq`s provide list-like operations: indexed and named element access;
#'   push/pop/peek from either end for double-ended queue behavior; insertion,
#'   splitting, and concatenation.
#' - `priority_queue`s associate items with priority values and provide
#'   min and max peek/pop by priority and fast insertion.
#' - `ordered_sequence`s associate items with key values and keep 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`es store items associated with interval ranges, supporting
#'   point as well as interval overlaps/contains/within queries. Items are kept
#'   in start-order enabling ordered sequence operations and sweep-line
#'   algorithms.
#'
#' Backed by monoid-annotated 2-3 fingertrees as described by
#' Hinze and Paterson, most operations are constant time, amortized constant time, or $O(\\log(n))$. Core functions are implemented in C++ (via Rcpp) for speed, with matching pure-R reference implementations using `lambda.r` syntax to match the paper.
#'
#' Finally, the developer API supports the addition of custom structures via combinations of monoids and measures.
#'
#' - Hinze, R. and Paterson, R. (2006), *Finger trees: a simple general-purpose data structure*. \doi{10.1017/S0956796805005769}
#'
#' @keywords internal
#' @import lambda.r
#' @importFrom Rcpp evalCpp
#' @useDynLib Immutables, .registration = TRUE
"_PACKAGE"