Fast functions for sorted sets of integer

Source: R/merge.R

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.

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

Value

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

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

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)
#> [1] -9 -8 -7 -6 -5 -4 -3 -2 -1

merge_match(1:7, 3:9)
#> [1] NA NA  1  2  3  4  5
#' merge_match(merge_rev(1:7), 3:9)
merge_match(merge_rev(1:7), 3:9, revx=TRUE)
#> [1] NA NA  1  2  3  4  5
merge_match(merge_rev(1:7), 3:9, revy=TRUE)
#> [1]  3  4  5  6  7 NA NA
merge_match(merge_rev(1:7), merge_rev(3:9))
#> [1]  3  4  5  6  7 NA NA

merge_in(1:7, 3:9)
#> [1] FALSE FALSE  TRUE  TRUE  TRUE  TRUE  TRUE
merge_notin(1:7, 3:9)
#> [1]  TRUE  TRUE FALSE FALSE FALSE FALSE FALSE

merge_anyDuplicated(c(1L, 1L, 2L, 3L))
#> [1] TRUE
merge_duplicated(c(1L, 1L, 2L, 3L))
#> [1] FALSE  TRUE FALSE FALSE
merge_unique(c(1L, 1L, 2L, 3L))
#> [1] 1 2 3

merge_union(c(1L, 2L, 2L, 2L), c(2L, 2L, 3L))
#> [1] 1 2 3
merge_union(c(1L, 2L, 2L, 2L), c(2L, 2L, 3L), method="exact")
#> [1] 1 2 2 2 3
merge_union(c(1L, 2L, 2L, 2L), c(2L, 2L, 3L), method="all")
#> [1] 1 2 2 2 2 2 3

merge_setdiff(c(1L, 2L, 2L, 2L), c(2L, 2L, 3L))
#> [1] 1
merge_setdiff(c(1L, 2L, 2L, 2L), c(2L, 2L, 3L), method="exact")
#> [1] 1 2
merge_setdiff(c(1L, 2L, 2L), c(2L, 2L, 2L, 3L), method="exact")
#> [1] 1

merge_symdiff(c(1L, 2L, 2L, 2L), c(2L, 2L, 3L))
#> [1] 1 3
merge_symdiff(c(1L, 2L, 2L, 2L), c(2L, 2L, 3L), method="exact")
#> [1] 1 2 3
merge_symdiff(c(1L, 2L, 2L), c(2L, 2L, 2L, 3L), method="exact")
#> [1] 1 2 3

merge_intersect(c(1L, 2L, 2L, 2L), c(2L, 2L, 3L))
#> [1] 2
merge_intersect(c(1L, 2L, 2L, 2L), c(2L, 2L, 3L), method="exact")
#> [1] 2 2

merge_setequal(c(1L, 2L, 2L), c(1L, 2L))
#> [1] TRUE
merge_setequal(c(1L, 2L, 2L), c(1L, 2L, 2L))
#> [1] TRUE
merge_setequal(c(1L, 2L, 2L), c(1L, 2L), method="exact")
#> [1] FALSE
merge_setequal(c(1L, 2L, 2L), c(1L, 2L, 2L), method="exact")
#> [1] TRUE