Grouping objects
Description
We call grouping an arbitrary mapping from a collection of NO objects to a collection of NG groups, or, more formally, a bipartite graph between integer sets [1, NO] and [1, NG]. Objects mapped to a given group are said to belong to, or to be assigned to, or to be in that group. Additionally, the objects in each group are ordered. So for example the 2 following groupings are considered different:
1 2 3 4 5 6 7 8 9 10 11 
There are no restriction on the mapping e.g. any object can be mapped to 0, 1, or more groups, and can be mapped twice to the same group. Also some or all the groups can be empty.
The Grouping class is a virtual class that formalizes the most general kind of grouping. More specific groupings (e.g. manytoone groupings or blockgroupings) are formalized via specific Grouping subclasses.
This man page documents the core Grouping API, and 3 important Grouping subclasses: ManyToOneGrouping, GroupingRanges, and Partitioning (the last one deriving from the 2 first).
The core Grouping API
Let's give a formal description of the core Grouping API:
Groups G_i are indexed from 1 to NG (1 <= i <= NG).
Objects O_j are indexed from 1 to NO (1 <= j <= NO).
Given that empty groups are allowed, NG can be greater than NO.
If x
is a Grouping object:

length(x)
: Returns the number of groups (NG). 
names(x)
: Returns the names of the groups. 
nobj(x)
: Returns the number of objects (NO).
Going from groups to objects:

x[[i]]
: Returns the indices of the objects (the j's) that belong to G_i. This provides the mapping from groups to objects. 
grouplengths(x, i=NULL)
: Returns the number of objects in G_i. Works in a vectorized fashion (unlikex[[i]]
).grouplengths(x)
is equivalent togrouplengths(x, seq_len(length(x)))
. Ifi
is not NULL,grouplengths(x, i)
is equivalent tosapply(i, function(ii) length(x[[ii]]))
.
Note to developers: Given that length
, names
and [[
are expected to work on any Grouping object, those objects can be seen as
List objects. More precisely, the Grouping class actually extends
the IntegerList class. In particular, many other "list" operations
like as.list
, elementNROWS
, and unlist
, etc...
should work outofthebox on any Grouping object.
ManyToOneGrouping objects
The ManyToOneGrouping class is a virtual subclass of Grouping for representing manytoone groupings, that is, groupings where each object in the original collection of objects belongs to exactly one group.
The grouping of an empty collection of objects in an arbitrary number of (necessarily empty) groups is a valid ManyToOneGrouping object.
Note that, for a ManyToOneGrouping object, if NG is 0 then NO must also be 0.
The ManyToOneGrouping API extends the core Grouping API by adding a couple more operations for going from groups to objects:

members(x, i)
: Equivalent tox[[i]]
ifi
is a single integer. Otherwise, ifi
is an integer vector of arbitrary length, it's equivalent tosort(unlist(sapply(i, function(ii) x[[ii]])))
. 
vmembers(x, L)
: A version ofmembers
that works in a vectorized fashion with respect to theL
argument (L
must be a list of integer vectors). Returnslapply(L, function(i) members(x, i))
.
And also by adding operations for going from objects to groups:

togroup(x, j=NULL)
: Returns the index i of the group that O_j belongs to. This provides the mapping from objects to groups (manytoone mapping). Works in a vectorized fashion.togroup(x)
is equivalent totogroup(x, seq_len(nobj(x)))
: both return the entire mapping in an integer vector of length NO. Ifj
is not NULL,togroup(x, j)
is equivalent toy < togroup(x); y[j]
. 
togrouplength(x, j=NULL)
: Returns the number of objects that belong to the same group as O_j (including O_j itself). Equivalent togrouplengths(x, togroup(x, j))
.
One important property of any ManyToOneGrouping object x
is
that unlist(as.list(x))
is always a permutation of
seq_len(nobj(x))
. This is a direct consequence of the fact
that every object in the grouping belongs to one group and only
one.
2 ManyToOneGrouping concrete subclasses: H2LGrouping, Dups and SimpleManyToOneGrouping
[DOCUMENT ME]
Constructors:

H2LGrouping(high2low=integer())
: [DOCUMENT ME] 
Dups(high2low=integer())
: [DOCUMENT ME] 
ManyToOneGrouping(..., compress=TRUE)
: Collect...
into aManyToOneGrouping
. The arguments will be coerced to integer vectors and combined into a list, unless there is a single list argument, which is taken to be an integer list. The resulting integer list should have a structure analogous to that ofGrouping
itself: each element represents a group in terms of the subscripts of the members. Ifcompress
isTRUE
, the representation uses aCompressedList
, otherwise aSimpleList
.
ManyToManyGrouping objects
The ManyToManyGrouping class is a virtual subclass of Grouping for representing manytomany groupings, that is, groupings where each object in the original collection of objects belongs to any number of groups.
Constructors:

ManyToManyGrouping(x, compress=TRUE)
: Collect...
into aManyToManyGrouping
. The arguments will be coerced to integer vectors and combined into a list, unless there is a single list argument, which is taken to be an integer list. The resulting integer list should have a structure analogous to that ofGrouping
itself: each element represents a group in terms of the subscripts of the members. Ifcompress
isTRUE
, the representation uses aCompressedList
, otherwise aSimpleList
.
GroupingRanges objects
The GroupingRanges class is a virtual subclass of Grouping for representing
blockgroupings, that is, groupings where each group is a block of
adjacent elements in the original collection of objects. GroupingRanges
objects support the Ranges API (e.g. start
, end
,
width
, etc...) in addition to the Grouping API.
See ?Ranges
for a description of the Ranges API.
Partitioning objects
The Partitioning class is a virtual subclass of GroupingRanges for representing blockgroupings where the blocks fully cover the original collection of objects and don't overlap. Since this makes them manytoone groupings, the Partitioning class is also a subclass of ManyToOneGrouping. An additional constraint of Partitioning objects is that the blocks must be ordered by ascending position with respect to the original collection of objects.
The Partitioning virtual class itself has 3 concrete subclasses: PartitioningByEnd (only stores the end of the groups, allowing fast mapping from groups to objects), and PartitioningByWidth (only stores the width of the groups), and PartitioningMap which contains PartitioningByEnd and two additional slots to reorder and relist the object to a related mapping.
Constructors:

PartitioningByEnd(x=integer(), NG=NULL, names=NULL)
:x
must be either a listlike object or a sorted integer vector.NG
must be eitherNULL
or a single integer.names
must be eitherNULL
or a character vector of lengthNG
(if supplied) orlength(x)
(ifNG
is not supplied).Returns the following PartitioningByEnd object
y
:If
x
is a listlike object, then the returned objecty
has the same length asx
and is such thatwidth(y)
is identical toelementNROWS(x)
.If
x
is an integer vector andNG
is not supplied, thenx
must be sorted (checked) and contain nonNA nonnegative values (NOT checked). The returned objecty
has the same length asx
and is such thatend(y)
is identical tox
.If
x
is an integer vector andNG
is supplied, thenx
must be sorted (checked) and contain values >= 1 and <=NG
(checked). The returned objecty
is of lengthNG
and is such thattogroup(y)
is identical tox
.
If the
names
argument is supplied, it is used to name the partitions. 
PartitioningByWidth(x=integer(), NG=NULL, names=NULL)
:x
must be either a listlike object or an integer vector.NG
must be eitherNULL
or a single integer.names
must be eitherNULL
or a character vector of lengthNG
(if supplied) orlength(x)
(ifNG
is not supplied).Returns the following PartitioningByWidth object
y
:If
x
is a listlike object, then the returned objecty
has the same length asx
and is such thatwidth(y)
is identical toelementNROWS(x)
.If
x
is an integer vector andNG
is not supplied, thenx
must contain nonNA nonnegative values (NOT checked). The returned objecty
has the same length asx
and is such thatwidth(y)
is identical tox
.If
x
is an integer vector andNG
is supplied, thenx
must be sorted (checked) and contain values >= 1 and <=NG
(checked). The returned objecty
is of lengthNG
and is such thattogroup(y)
is identical tox
.
If the
names
argument is supplied, it is used to name the partitions. 
PartitioningMap(x=integer(), mapOrder=integer())
:x
is a listlike object or a sorted integer vector used to construct a PartitioningByEnd object.mapOrder
numeric vector of the mapped order.Returns a PartitioningMap object.
Note that these constructors don't recycle their names
argument
(to remain consistent with what `names<`
does on standard
vectors).
Coercions to Grouping objects
These types can be coerced to different derivatives of Grouping objects:
 factor

Analogous to calling
split
with the factor. Returns a ManyToOneGrouping if there are no NAs, otherwise a ManyToManyGrouping. If a factor is explicitly converted to a ManytoOneGrouping, then any NAs are placed in the last group.  vector

A vector is effectively treated as a factor, but more efficiently. The order of the groups is not defined.
 FactorList

Same as the factor coercion, except using the interaction of every factor in the list. The interaction has an NA wherever any of the elements has one. Every element must have the same length.
 DataFrame

Effectively converted via a FactorList by coercing each column to a factor.
 grouping

Equivalent Grouping representation of the base R
grouping
object.  Hits

Returns roughly the same object as
as(x, "List")
, except it is a ManyToManyGrouping, i.e., it knows the number of right nodes.
Author(s)
Hervé Pagès, Michael Lawrence
See Also
IntegerListclass, Rangesclass, IRangesclass, successiveIRanges, cumsum, diff
Examples
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103  showClass("Grouping") # shows (some of) the known subclasses
## 
## A. H2LGrouping OBJECTS
## 
high2low < c(NA, NA, 2, 2, NA, NA, NA, 6, NA, 1, 2, NA, 6, NA, NA, 2)
h2l < H2LGrouping(high2low)
h2l
## The core Grouping API:
length(h2l)
nobj(h2l) # same as 'length(h2l)' for H2LGrouping objects
h2l[[1]]
h2l[[2]]
h2l[[3]]
h2l[[4]]
h2l[[5]]
grouplengths(h2l) # same as 'unname(sapply(h2l, length))'
grouplengths(h2l, 5:2)
members(h2l, 5:2) # all the members are put together and sorted
togroup(h2l)
togroup(h2l, 5:2)
togrouplength(h2l) # same as 'grouplengths(h2l, togroup(h2l))'
togrouplength(h2l, 5:2)
## The List API:
as.list(h2l)
sapply(h2l, length)
## 
## B. Dups OBJECTS
## 
dups1 < as(h2l, "Dups")
dups1
duplicated(dups1) # same as 'duplicated(togroup(dups1))'
### The purpose of a Dups object is to describe the groups of duplicated
### elements in a vectorlike object:
x < c(2, 77, 4, 4, 7, 2, 8, 8, 4, 99)
x_high2low < high2low(x)
x_high2low # same length as 'x'
dups2 < Dups(x_high2low)
dups2
togroup(dups2)
duplicated(dups2)
togrouplength(dups2) # frequency for each element
table(x)
## 
## C. Partitioning OBJECTS
## 
pbe1 < PartitioningByEnd(c(4, 7, 7, 8, 15), names=LETTERS[1:5])
pbe1 # the 3rd partition is empty
## The core Grouping API:
length(pbe1)
nobj(pbe1)
pbe1[[1]]
pbe1[[2]]
pbe1[[3]]
grouplengths(pbe1) # same as 'unname(sapply(pbe1, length))'
# and 'width(pbe1)'
togroup(pbe1)
togrouplength(pbe1) # same as 'grouplengths(pbe1, togroup(pbe1))'
names(pbe1)
## The Ranges core API:
start(pbe1)
end(pbe1)
width(pbe1)
## The List API:
as.list(pbe1)
sapply(pbe1, length)
## Replacing the names:
names(pbe1)[3] < "empty partition"
pbe1
## Coercion to an IRanges object:
as(pbe1, "IRanges")
## Other examples:
PartitioningByEnd(c(0, 0, 19), names=LETTERS[1:3])
PartitioningByEnd() # no partition
PartitioningByEnd(integer(9)) # all partitions are empty
x < c(1L, 5L, 5L, 6L, 8L)
pbe2 < PartitioningByEnd(x, NG=10L)
stopifnot(identical(togroup(pbe2), x))
pbw2 < PartitioningByWidth(x, NG=10L)
stopifnot(identical(togroup(pbw2), x))
## 
## D. RELATIONSHIP BETWEEN Partitioning OBJECTS AND successiveIRanges()
## 
mywidths < c(4, 3, 0, 1, 7)
## The 3 following calls produce the same ranges:
ir < successiveIRanges(mywidths) # IRanges instance.
pbe < PartitioningByEnd(cumsum(mywidths)) # PartitioningByEnd instance.
pbw < PartitioningByWidth(mywidths) # PartitioningByWidth instance.
stopifnot(identical(as(ir, "PartitioningByEnd"), pbe))
stopifnot(identical(as(ir, "PartitioningByWidth"), pbw))
