### Find objects in the query that overlap those in the subject.
### The next two functions are pre/post processing functions shared
### by the IntervalTree and IntervalForest versions of findOverlaps
### pre-process query (sort and adjust) and partition (if not NULL)
# query be sorted within partition spaces
### post-process result based on overlap type and select
## unname() required because in case 'm' has only 1 row
## 'm[ , 1L]' and 'm[ , 2L]' will return a named atomic vector
## 'm[,2L]' will return a named atomic vector
### findOverlaps method for IntervalTree
"'maxgap' must be a single, non-negative integer"
"'minoverlap' must be a single, positive integer"
### findOverlaps method for IntervalForest
# match query partition to subject partition
# might consider making this the following:
#           function(query, subject, maxgap = 0L, minoverlap = 1L,
#                    type = c("any", "start", "end", "within", "equal"),
#                    select = c("all", "first", "last", "arbitrary"),
#               maxgap = maxgap, minoverlap = minoverlap,
#               type = match.arg(type), select = match.arg(select), drop = drop)
## NULL's are introduced where they do not match
### Same args and signature as countOverlaps() and subsetByOverlaps().
### Convenience wrappers for the 2 most common use cases.
### Extracts the actual regions of intersection between the overlapping ranges.
### Not much value. Could be replaced by 1-liner:
"'query' must be a Ranges of length equal to number of queries"
"'subject' must be a Ranges of length equal to number of subjects"

setGeneric("findOverlaps", signature = c("query", "subject"),
function(query, subject, maxgap = 0L, minoverlap = 1L,
type = c("any", "start", "end", "within", "equal"),
select = c("all", "first", "last", "arbitrary"), ...)
.preProcess_findOverlaps_query <- function(query, maxgap, minoverlap, partitioning=NULL) {
adjust <- (maxgap - minoverlap + 1L) * (width(query) > 0L)
resize(query, width(query) + 2L * adjust, fix = "center")
if (isNotSorted(start(query))) { ## query must be sorted
query_ord <- sort.list(start(query), method = "quick",
for (i in seq(len=length(partitioning))) {
.postProcess_findOverlaps_result <- function(result, unsortedQuery, origQuery, subject, type, minoverlap, maxgap, origSelect)
r <- ranges(result, unsortedQuery, subject)
m <- m[width(r) >= minoverlap, , drop=FALSE]
m[abs(fun(query)[m[,1L]] - fun(subject)[m[,2L]]) <= maxgap, ,
m <- m[width(query)[m[,1L]] - width(r) <= maxgap, , drop=FALSE]
m <- m[!duplicated(m[,1L]), , drop=FALSE]
select = c("all", "first", "last", "arbitrary"))
if (!isSingleNumber(maxgap) || maxgap < 0L)
stop("'maxgap' must be a single, non-negative integer")
if (!isSingleNumber(minoverlap) || minoverlap < 1L)
stop("'minoverlap' must be a single, positive integer")
preprocRes <- .preProcess_findOverlaps_query(query, maxgap, minoverlap)
fun <- paste("overlap_", select, sep = "")
result <- IntervalTreeCall(subject, fun, query, query_ord)
.postProcess_findOverlaps_result(result, unsortedQuery, origQuery, subject, type, minoverlap, maxgap, origSelect)
findOverlaps(query, IntervalTree(subject), maxgap = maxgap,
minoverlap = minoverlap, type = match.arg(type),
select = c("all", "first", "last", "arbitrary"),
ignoreSelf = FALSE, ignoreRedundant = FALSE)
maxgap = maxgap, minoverlap = minoverlap,
findOverlaps(IRanges(query, query), subject, maxgap = maxgap,
type=c("any", "start", "end", "within", "equal"),
select = c("all", "first", "last", "arbitrary"), drop=FALSE)
preprocRes <- .preProcess_findOverlaps_query(query, maxgap, minoverlap, partitioning)
result <- .IntervalForestCall(subject, fun, query, partitionIndices, elementLengths(partitioning), query_ord)
res <- .postProcess_findOverlaps_result(result, unsortedQuery, origQuery, subject, type, minoverlap, maxgap, origSelect)
if (!is.null(names(subject)) && !is.null(names(query))) {
names(subject) <- names(query) # get rid of NA's in names
ans <- lapply(seq_len(length(subject)), function(i) {
findOverlaps(query[[i]], subject[[i]], maxgap = maxgap,
off <- head(c(0L, cumsum(sapply(origSubject, length))), -1)
findOverlaps(ranges(query), ranges(subject), maxgap = maxgap,
select = match.arg(select), drop = drop)
findOverlaps(ranges(query), subject, maxgap = maxgap,
findOverlaps(query, ranges(subject), maxgap = maxgap,
setGeneric("countOverlaps", signature = c("query", "subject"),
type = c("any", "start", "end", "within", "equal"), ...)
counts <- queryHits(findOverlaps(query, subject, maxgap = maxgap,
minoverlap = minoverlap, type = type, ...))
type = c("any", "start", "end", "within", "equal"))
countOverlaps(query, query, maxgap = maxgap,
type = c("any", "start", "end", "within", "equal"), drop = FALSE, ...)
hits <- findOverlaps(query, subject, maxgap = maxgap,
minoverlap = minoverlap, type = type, ...)
new2("CompressedIntegerList", unlistData=res, partitioning = query@partitioning)
type=c("any", "start", "end", "within", "equal"))
countOverlaps(ranges(query), ranges(subject), maxgap = maxgap,
minoverlap = minoverlap, type = match.arg(type))
countOverlaps(ranges(query), subject, maxgap = maxgap,
countOverlaps(query, ranges(subject), maxgap = maxgap,
type=c("any", "start", "end", "within", "equal"), ...)
if (!is.null(names(query)) && !is.null(names(subject))) {
`%over%` <- function(query, subject) overlapsAny(query, subject)
`%within%` <- function(query, subject) overlapsAny(query, subject,
`%outside%` <- function(query, subject) !overlapsAny(query, subject)
setGeneric("subsetByOverlaps", signature = c("query", "subject"),
query[!is.na(findOverlaps(query, subject, maxgap = maxgap,
setMethod("ranges", "Hits", function(x, query, subject) {
if (!is(query, "Ranges") || length(query) != queryLength(x))
stop("'query' must be a Ranges of length equal to number of queries")
if (!is(subject, "Ranges") || length(subject) != subjectLength(x))
stop("'subject' must be a Ranges of length equal to number of subjects")