merge_rev: Fast functions for sorted sets of integer
In bit: Classes and Methods for Fast Memory-Efficient Boolean Selections

merge_rev

R Documentation

Fast functions for sorted sets of integer

Description

The merge_ functions allow unary and binary operations on (ascending) sorted vectors of integer(). merge_rev(x) will do in one scan what costs two scans in -rev(x), see also reverse_vector(). Many of these merge_ can optionally scan their input in reverse order (and switch the sign), which again saves extra scans for calling merge_rev(x) first.

Usage

merge_rev(x)

merge_match(x, y, revx = FALSE, revy = FALSE, nomatch = NA_integer_)

merge_in(x, y, revx = FALSE, revy = FALSE)

merge_notin(x, y, revx = FALSE, revy = FALSE)

merge_duplicated(x, revx = FALSE)

merge_anyDuplicated(x, revx = FALSE)

merge_sumDuplicated(x, revx = FALSE)

merge_unique(x, revx = FALSE)

merge_union(
  x,
  y,
  revx = FALSE,
  revy = FALSE,
  method = c("unique", "exact", "all")
)

merge_setdiff(x, y, revx = FALSE, revy = FALSE, method = c("unique", "exact"))

merge_symdiff(x, y, revx = FALSE, revy = FALSE, method = c("unique", "exact"))

merge_intersect(
  x,
  y,
  revx = FALSE,
  revy = FALSE,
  method = c("unique", "exact")
)

merge_setequal(x, y, revx = FALSE, revy = FALSE, method = c("unique", "exact"))

merge_rangein(rx, y, revx = FALSE, revy = FALSE)

merge_rangenotin(rx, y, revx = FALSE, revy = FALSE)

merge_rangesect(rx, y, revx = FALSE, revy = FALSE)

merge_rangediff(rx, y, revx = FALSE, revy = FALSE)

merge_first(x, revx = FALSE)

merge_last(x, revx = FALSE)

merge_firstin(rx, y, revx = FALSE, revy = FALSE)

merge_lastin(rx, y, revx = FALSE, revy = FALSE)

merge_firstnotin(rx, y, revx = FALSE, revy = FALSE)

merge_lastnotin(rx, y, revx = FALSE, revy = FALSE)

Arguments

`x`	a sorted set
`y`	a sorted set
`revx`	default `FALSE`, set to `TRUE` to reverse scan parameter 'x'
`revy`	default `FALSE`, set to `TRUE` to reverse scan parameter 'y'
`nomatch`	integer value returned for non-matched elements, see `match()`
`method`	one of "unique", "exact" (or "all") which governs how to treat ties, see the function descriptions
`rx`	range of integers given as `ri()` or as a two-element `integer()`

Details

These are low-level functions and hence do not check whether the set is actually sorted. Note that the ⁠merge_*⁠ and ⁠merge_range*⁠ functions have no special treatment for NA. If vectors with NA are sorted ith NA in the first positions (na.last=FALSE) and arguments ⁠revx=⁠ or ⁠revy=⁠ have not been used, then NAs are treated like ordinary integers. NA sorted elsewhere or using ⁠revx=⁠ or ⁠revy=⁠ can cause unexpected results (note for example that ⁠revx=⁠ switches the sign on all integers but NAs).

The binary ⁠merge_*⁠ functions have a method="exact" which in both sets treats consecutive occurrences of the same value as if they were different values, more precisely they are handled as if the identity of ties were tuples of ⁠ties, rank(ties)⁠. method="exact" delivers unique output if the input is unique, and in this case works faster than method="unique".

Value

merge_rev(x) returns -rev(x) for integer() and double() and !rev(x) for logical()

Functions

merge_match(): returns integer positions of sorted set x in sorted set y, see match(x, y, ...)
merge_in(): returns logical existence of sorted set x in sorted set y, see x %in% y
merge_notin(): returns logical in-existence of sorted set x in sorted set y, see !(x %in% y)
merge_duplicated(): returns the duplicated status of a sorted set x, see duplicated()
merge_anyDuplicated(): returns the anyDuplicated status of a sorted set x, see anyDuplicated()
merge_sumDuplicated(): returns the sumDuplicated status of a sorted set x, see bit_sumDuplicated()
merge_unique(): returns unique elements of sorted set x, see unique()
merge_union(): returns union of two sorted sets. Default method='unique' returns a unique sorted set, see union(); method='exact' returns a sorted set with the maximum number of ties in either input set; method='all' returns a sorted set with the sum of ties in both input sets.
merge_setdiff(): returns sorted set x minus sorted set y Default method='unique' returns a unique sorted set, see setdiff(); ethod='exact' returns a sorted set with sum(x ties) minus sum(y ties);
merge_symdiff(): returns those elements that are in sorted set y xor() in sorted set y Default method='unique' returns the sorted unique set complement, see symdiff(); method='exact' returns a sorted set set complement with ⁠abs(sum(x ties) - sum(y ties))⁠.
merge_intersect(): returns the intersection of two sorted sets x and y Default method='unique' returns the sorted unique intersect, see intersect(); method='exact' returns the intersect with the minium number of ties in either set;
merge_setequal(): returns TRUE for equal sorted sets and FALSE otherwise Default method='unique' compares the sets after removing ties, see setequal(); method='exact' compares the sets without removing ties;
merge_rangein(): returns logical existence of range rx in sorted set y, see merge_in()
merge_rangenotin(): returns logical in-existence of range rx in sorted set y, see merge_notin()
merge_rangesect(): returns the intersection of range rx and sorted set y, see merge_intersect()
merge_rangediff(): returns range rx minus sorted set y, see merge_setdiff()
merge_first(): quickly returns the first element of a sorted set x (or NA if x is empty), hence x[1] or merge_rev(x)[1]
merge_last(): quickly returns the last element of a sorted set x, (or NA if x is empty), hence x[n] or merge_rev(x)[n]
merge_firstin(): quickly returns the first common element of a range rx and a sorted set y, (or NA if the intersection is empty), hence merge_first(merge_rangesect(rx, y))
merge_lastin(): quickly returns the last common element of a range rx and a sorted set y, (or NA if the intersection is empty), hence merge_last(merge_rangesect(rx, y))
merge_firstnotin(): quickly returns the first element of a range rx which is not in a sorted set y (or NA if all rx are in y), hence merge_first(merge_rangediff(rx, y))
merge_lastnotin(): quickly returns the last element of a range rx which is not in a sorted set y (or NA if all rx are in y), hence merge_last(merge_rangediff(rx, y))

Note

xx OPTIMIZATION OPPORTUNITY These are low-level functions could be optimized with initial binary search (not findInterval, which coerces to double).

Examples

merge_rev(1:9)

merge_match(1:7, 3:9)
#' merge_match(merge_rev(1:7), 3:9)
merge_match(merge_rev(1:7), 3:9, revx=TRUE)
merge_match(merge_rev(1:7), 3:9, revy=TRUE)
merge_match(merge_rev(1:7), merge_rev(3:9))

merge_in(1:7, 3:9)
merge_notin(1:7, 3:9)

merge_anyDuplicated(c(1L, 1L, 2L, 3L))
merge_duplicated(c(1L, 1L, 2L, 3L))
merge_unique(c(1L, 1L, 2L, 3L))

merge_union(c(1L, 2L, 2L, 2L), c(2L, 2L, 3L))
merge_union(c(1L, 2L, 2L, 2L), c(2L, 2L, 3L), method="exact")
merge_union(c(1L, 2L, 2L, 2L), c(2L, 2L, 3L), method="all")

merge_setdiff(c(1L, 2L, 2L, 2L), c(2L, 2L, 3L))
merge_setdiff(c(1L, 2L, 2L, 2L), c(2L, 2L, 3L), method="exact")
merge_setdiff(c(1L, 2L, 2L), c(2L, 2L, 2L, 3L), method="exact")

merge_symdiff(c(1L, 2L, 2L, 2L), c(2L, 2L, 3L))
merge_symdiff(c(1L, 2L, 2L, 2L), c(2L, 2L, 3L), method="exact")
merge_symdiff(c(1L, 2L, 2L), c(2L, 2L, 2L, 3L), method="exact")

merge_intersect(c(1L, 2L, 2L, 2L), c(2L, 2L, 3L))
merge_intersect(c(1L, 2L, 2L, 2L), c(2L, 2L, 3L), method="exact")

merge_setequal(c(1L, 2L, 2L), c(1L, 2L))
merge_setequal(c(1L, 2L, 2L), c(1L, 2L, 2L))
merge_setequal(c(1L, 2L, 2L), c(1L, 2L), method="exact")
merge_setequal(c(1L, 2L, 2L), c(1L, 2L, 2L), method="exact")

bit documentation built on April 4, 2025, 3:09 a.m.