## In R-2.12, base::Position() was modified to use seq_along()
## internally. The problem is that seq_along() was a primitive
## that would let the user define methods for it (otherwise it
## would have been worth defining a "seq_along" method for Vector
## objects). So we need to redefine seq_along() locally in order

.ReduceDefault <- function(f, x, init, right = FALSE, accumulate = FALSE)
for (i in rev(ind)) init <- f(x[[i]], init)
function(f, x, right = FALSE, nomatch = NA_integer_)
base_Position(f, x, right = right, nomatch = nomatch)

### A GappedRanges object is a vector of gapped ranges.
### A gapped range is conceptually the union of 1 or more non-overlapping
### More precisely, a gapped range can be represented by a normal IRanges
### object of length >= 1. In particular normality here ensures that the
### individual ranges are non-empty and are separated by non-empty gaps.
### The start of a gapped range is the start of its first range.
### The end of a gapped range is the end of its last range.
### If we ignore the gaps, then a GappedRanges object can be seen as a Ranges
### S3/S4 combo for as.data.frame.GappedRanges
### WARNING: We override the *semantic* of the "[[" method for Ranges objects.
### WARNING: We override the *semantic* of the "elementLengths" method for
"\"c\" method for GappedRanges objects "
# remove NULL elements by setting them to NULL!

setMethod("ngap", "GappedRanges", function(x) {elementLengths(x) - 1L})
as.data.frame.GappedRanges <- function(x, row.names=NULL, optional=FALSE, ...)
ans <- as.data.frame.Ranges(unname(x), row.names, optional, ...)
cat(class(object), " of length ", lo, "\n", sep="")
stop("\"c\" method for GappedRanges objects ",
args[arg_is_null] <- NULL  # remove NULL elements by setting them to NULL!
stop("all arguments in '...' must be ", class(x), " objects (or NULLs)")
x@cnirl <- do.call(c, lapply(args, function(xx) xx@cnirl))

### We call "grouping" the action of dividing a collection of NO objects into
### NG groups (some of them eventually empty). The Grouping class and
### subclasses are containers for representing groupings.
"subscript 'i' must be a vector of integers"
### The default method works on any object 'x' for which 'elementLengths(x)'
### works (e.g. Partitioning, List, list). Not very efficient.
"subscript 'j' must be a vector of integers or NULL"
"subscript 'j' contains NAs or out of bounds indices"
### For storing the grouping implicitly defined by the "duplicated"
### relationship between elements of an arbitrary vector.
### Two additional accessors for H2LGrouping objects.
### 'length(x)' and 'nobj(x)' are the same.
### Should be more efficient than the default method for Grouping objects.
"subscript 'i' must be a vector of integers or NULL"
"subscript 'i' contains NAs or out of bounds indices"
## NAs and "subscript out of bounds" are checked at the C level
### The default method should be as good (if not better) as this.
#        mapped_lows <- setdiff(unique(x@high2low), NA)
#            ii <- as.integer(c(low, x@low2high[[low]]))
### More operations on H2LGrouping objects. These operations are NOT part of
### The rank of group G_i is the number of non-empty groups that are before
### G_i plus one. Or, equivalently, it's the number of non-empty groups with
### togrouprank() returns the mapping from objects to group ranks.
### An important property of togrouprank() is that:
### are identical, where 'neg_idx' is the vector of the indices of
###   neg_idx <- which(grouplength(x) != 0L)
"the 'high2low' slot must contain an integer vector"
"the 'high2low' slot must contain integer values >= 1"
"when mapped, elements in the 'high2low' slot must be mapped "
"the 'low2high' slot must contain a list"
"the 'high2low' and 'low2high' slots must have the same length"
"the 'low2high' slot must contain the reverse mapping "
"\"duplicated\" method for Dups objects "
"'high2low' must be a vector of integers"
### If 'x' is a vector-like object for which "[" and "==" are defined, then
### 'high2low(x)' can be *conceptually* defined with:
### Of course this is *very* inefficient (quadratic in time), its only value
###    [1] NA NA NA  3 NA  1 NA  7  3 NA
### The "high2low" method for Vector objects uses an implementation that
### is O(n*log(n)) in time but it requires that "order" be defined for 'x'
## The 2 lines below are equivalent but much faster than
## ans <- rep.int(NA_integer_, length(x))
### A Partitioning container represents a block-grouping i.e. a grouping
### where each group contains objects that are neighbors in the original
### collection of objects. More formally, a grouping 'x' is a block-grouping
### iff 'togroup(x)' is sorted in increasing order (not necessarily strictly
### increasing). In addition, a Partitioning object can be seen (and
### manipulated) as a Ranges object where all the ranges are adjacent
### starting at 1 (i.e. it covers an integer interval starting at 1
### and with no overlap between the ranges). Therefore the "start/end/width"
### API is implemented on Partitioning objects (in addition to the Grouping
### The Partitioning class is virtual with 2 concrete subclasses:
### Note that we put Ranges before Grouping in order to have Partitioning
### objects inherit the "show" method for Ranges objects.
### The default methods below assume that the "length + start/end/width" API
## The purpose of the code below is to extract 'start(x)[i] - 1'
## (stored in 'ans_shift') and 'width(x)[i]' (stored in 'ans_length')
## in the fastest possible way. Looks like a convoluted way to
## extract those 2 values but it is actually 1000x faster than the
"the names must be a character vector or NULL"
"number of names and number of elements differ"
### PartitioningByEnd uses a compact internal representation that allows
### fast mapping from groups to objects. However, it is not efficient for
## Behaves like a getter for the 'partitioning' slot.
"'x' must be either a list-like object "
"when 'x' is an integer vector, it must be sorted"
## When 'NG' (number of groups) is supplied, then 'x' is considered
## to represent the group assignment of a collection of 'length(x)'
## objects. Therefore the values in 'x' must be >= 1 and <= 'NG'.
## ADDITIONALLY, 'x' must be *sorted* (not strictly) so it can be
## reconstructed from the object returned by PartitioningByEnd()
"'NG' must be either NULL or a single integer"
"when 'NG' is 0, 'x' must be of length 0"
## 'x' is expected to be non-decreasing and with values >= 1
"when 'NG' is supplied, values in 'x' must "
"'names' must be either NULL or a character vector of length "
"'NG' (if supplied) or 'length(x)' (if 'NG' is not supplied)"
"the Ranges object to coerce does not represent a partitioning"
### PartitioningByWidth uses a compact internal representation too. Storing
### the widths instead of the ends would allow the total number of objects
### (nobj(x)) to be greater than 2^31-1 but note that some methods will break
### when this happens, e.g. nobj, end, etc...
"'x' must be either a list-like object or an integer vector"
## reconstructed from the object returned by PartitioningByWidth()
## 'sum(x)' is guaranteed to be <= 'NO'.
### A simple findOverlaps method that doesn't use IntervalTree but works only
### on a subject with *adjacent* ranges sorted non-decreasingly.
### Can be 30% faster or more than the real findOverlaps() (IntervalTree-based)
### when 'query' is such that 'start(query)' and 'end(query)' are also sorted
### non-decreasingly (which is the case if for example 'query' is a
### TODO: Add a "findOverlaps" method for Partitioning,Partitioning in the
### findOverlaps-methods.R file that calls this.
"'subject' must be a Partitioning object"
## If 'query' is a Partitioning object, all hits are guaranteed to be
## Remap hits to original query/subject.