| Title: | An Interval Tree Tool for Real Numbers |
|---|---|
| Description: | This tool can be used to build binary interval trees using real number inputs. The tree supports queries of intervals overlapping a single number or an interval (start, end). Intervals with same bounds but different names are treated as distinct intervals. Insertion of intervals is also allowed. Deletion of intervals is not implemented at this point. See Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars (2008). Computational Geometry: Algorithms and Applications, for a reference. |
| Authors: | Shuye Pu [aut, cre] |
| Maintainer: | Shuye Pu <[email protected]> |
| License: | GPL-2 |
| Version: | 0.1.0 |
| Built: | 2024-09-16 04:01:02 UTC |
| Source: | https://github.com/cran/rIntervalTree |
Method for building a binary interval tree given an IntervalTree object with a defined data slot but an undefined root slot. This method is a wrapper function of the treeFromInterval function. In the first step, the dataframe in the data slot is converted into a list of Interval objects. Then, the treeFromInterval function is called to construct an interval tree using the list as an input, and the root of the resulting interval tree is assigned to the root slot of the IntervalTree object. This method is called implicitly when an IntervalTree object is initialized with a non-empty dataframe.
buildTree(theObject)buildTree(theObject)
theObject |
an IntervalTree object containing a non-empty dataframe. |
an IntervalTree object, with the root being an recursive list of Intervals.
m_ranges <- data.frame(c("A", "B", "C", "D"), c(1,2,3,4), c(5,4,6,10)) I <- new("IntervalTree") I@data <- m_ranges m_interval_tree <- buildTree(I) ## buildTree is called implicitly II <- IntervalTree(data=m_ranges, root=list()) ## buildTree is called implicitly m_interval_tree <- new("IntervalTree", data=m_ranges, root=list())m_ranges <- data.frame(c("A", "B", "C", "D"), c(1,2,3,4), c(5,4,6,10)) I <- new("IntervalTree") I@data <- m_ranges m_interval_tree <- buildTree(I) ## buildTree is called implicitly II <- IntervalTree(data=m_ranges, root=list()) ## buildTree is called implicitly m_interval_tree <- new("IntervalTree", data=m_ranges, root=list())
Method for building a binary interval tree given an IntervalTree object with a defined data slot but an undefined root slot. This method is a wrapper function of the treeFromInterval function. In the first step, the dataframe in the data slot is converted into a list of Interval objects. Then, the treeFromInterval function is called to construct an interval tree using the list as an input, and the root of the resulting interval tree is assigned to the root slot of the IntervalTree object. This method is called implicitly when an IntervalTree object is initialized with a nonempty dataframe.
## S4 method for signature 'IntervalTree' buildTree(theObject)## S4 method for signature 'IntervalTree' buildTree(theObject)
theObject |
an IntervalTree object containing a non-empty dataframe. |
an IntervalTree object, with the root being an recursive list of Intervals.
m_ranges <- data.frame(c("A", "B", "C", "D"), c(1,2,3,4), c(5,4,6,10)) I <- new("IntervalTree") I@data <- m_ranges m_interval_tree <- buildTree(I) ## buildTree is called implicitly II <- IntervalTree(data=m_ranges, root=list()) ## buildTree is called implicitly m_interval_tree <- new("IntervalTree", data=m_ranges, root=list())m_ranges <- data.frame(c("A", "B", "C", "D"), c(1,2,3,4), c(5,4,6,10)) I <- new("IntervalTree") I@data <- m_ranges m_interval_tree <- buildTree(I) ## buildTree is called implicitly II <- IntervalTree(data=m_ranges, root=list()) ## buildTree is called implicitly m_interval_tree <- new("IntervalTree", data=m_ranges, root=list())
Method for enumerating all intervals in a interval tree (a list object).
collectIntervals(aTree)collectIntervals(aTree)
aTree |
a recursive list storing Interval object |
a flattened list of Interval object
i1 <- new("Interval", start=1.1, end=1.2, key="dummy1") i2 <- new("Interval", start=-1.1, end=1.2, key="dummy2") i3 <- new("Interval", start=-10.1, end=-1.2, key="dummy3") i4 <- new("Interval", start=-1.1, end=1.2, key="dummy4") i5 <- new("Interval", start=-10, end=2, key="dummy5") i6 <- new("Interval", start=-8, end=-5, key="dummy6") myList <- list(i1, i2, i3, i4, i5, i6) atree <- treeFromInterval(myList) collectIntervals(atree) collectIntervals(list())i1 <- new("Interval", start=1.1, end=1.2, key="dummy1") i2 <- new("Interval", start=-1.1, end=1.2, key="dummy2") i3 <- new("Interval", start=-10.1, end=-1.2, key="dummy3") i4 <- new("Interval", start=-1.1, end=1.2, key="dummy4") i5 <- new("Interval", start=-10, end=2, key="dummy5") i6 <- new("Interval", start=-8, end=-5, key="dummy6") myList <- list(i1, i2, i3, i4, i5, i6) atree <- treeFromInterval(myList) collectIntervals(atree) collectIntervals(list())
A dataset containing the the mass ranges of chemical compounds with a 10 ppm tolerance. The variables are as follows.
data(compounds)data(compounds)
A data frame with 23 rows and 3 variables
name. name of the compound
low. low bound of the mass
high. high bound of the mass
Method for inserting an Interval into an interval tree (a recursive list). The structure of the final tree is invariant of the order of insertion. Tree balancing is not implemented, therefore, the resulting tree may not be balanced.
insert(aTree, anInterval)insert(aTree, anInterval)
aTree |
an interval tree (a list object) |
anInterval |
an Interval object |
a list object, representing a binary interval tree
i1 <- new("Interval", start=1.1,end=1.2, key="dummy1") i2 <- new("Interval", start=-1.1,end=1.2, key="dummy2") i3 <- new("Interval", start=-10.1,end=-1.2, key="dummy3") i4 <- new("Interval", start=-1.1,end=1.2, key="dummy4") i5 <- new("Interval", start=-10,end=2, key="dummy5") i6 <- new("Interval", start=-8,end=-5, key="dummy6") i7 <- new("Interval", start=80,end=100, key="dummy7") i8 <- new("Interval", start=-80,end=-15, key="dummy8") atree <- list() atree <- insert(atree, i1) atree <- insert(atree, i2) atree <- insert(atree, i3) atree <- insert(atree, i4) atree <- insert(atree, i5) atree <- insert(atree, i6) atree <- insert(atree, i7) atree <- insert(atree, i8) intersectInterval(atree, 85) intersectInterval(atree, 0) intersectInterval(atree, c(-70, -9)) ## Not run: intersectInterval(atree, c(80,0)) ## generate an error ## End(Not run)i1 <- new("Interval", start=1.1,end=1.2, key="dummy1") i2 <- new("Interval", start=-1.1,end=1.2, key="dummy2") i3 <- new("Interval", start=-10.1,end=-1.2, key="dummy3") i4 <- new("Interval", start=-1.1,end=1.2, key="dummy4") i5 <- new("Interval", start=-10,end=2, key="dummy5") i6 <- new("Interval", start=-8,end=-5, key="dummy6") i7 <- new("Interval", start=80,end=100, key="dummy7") i8 <- new("Interval", start=-80,end=-15, key="dummy8") atree <- list() atree <- insert(atree, i1) atree <- insert(atree, i2) atree <- insert(atree, i3) atree <- insert(atree, i4) atree <- insert(atree, i5) atree <- insert(atree, i6) atree <- insert(atree, i7) atree <- insert(atree, i8) intersectInterval(atree, 85) intersectInterval(atree, 0) intersectInterval(atree, c(-70, -9)) ## Not run: intersectInterval(atree, c(80,0)) ## generate an error ## End(Not run)
Method for inserting an interval into an IntervalTree object. Given an ordered pair of numbers denoting the start and end of an interval, the interval is first converted into an Interval object, then the Interval object is inserted by calling the insert() function.
insertInterval(theObject, anInterval)insertInterval(theObject, anInterval)
theObject |
an IntervalTree object |
anInterval |
an interval in the form of (name, start, end). |
an IntervalTree object.
m_ranges <- data.frame(c("A", "B", "C", "D"), c(-1.1,2,3,4), c(5,4,6,10)) m_interval_tree <- new("IntervalTree", data=m_ranges, root=list()) m_interval_tree <- insertInterval(m_interval_tree, c("testInterval1", 2, 5)) res <- insertInterval(m_interval_tree, c("a",2.5,7))m_ranges <- data.frame(c("A", "B", "C", "D"), c(-1.1,2,3,4), c(5,4,6,10)) m_interval_tree <- new("IntervalTree", data=m_ranges, root=list()) m_interval_tree <- insertInterval(m_interval_tree, c("testInterval1", 2, 5)) res <- insertInterval(m_interval_tree, c("a",2.5,7))
Method for inserting an interval into an IntervalTree object. Given an ordered pair of numbers denoting the start and end of an interval, the interval is first converted into an Interval object, then the Interval object is inserted by calling the insert() function.
## S4 method for signature 'IntervalTree,character' insertInterval(theObject, anInterval)## S4 method for signature 'IntervalTree,character' insertInterval(theObject, anInterval)
theObject |
an IntervalTree object |
anInterval |
an interval in the form of (name, start, end). |
an IntervalTree object.
m_ranges <- data.frame(c("A", "B", "C", "D"), c(-1.1,2,3,4), c(5,4,6,10)) m_interval_tree <- new("IntervalTree", data=m_ranges, root=list()) m_interval_tree <- insertInterval(m_interval_tree, c("testInterval2", 200, 500)) res <- insertInterval(m_interval_tree, c("a",-25,7))m_ranges <- data.frame(c("A", "B", "C", "D"), c(-1.1,2,3,4), c(5,4,6,10)) m_interval_tree <- new("IntervalTree", data=m_ranges, root=list()) m_interval_tree <- insertInterval(m_interval_tree, c("testInterval2", 200, 500)) res <- insertInterval(m_interval_tree, c("a",-25,7))
Method for searching the interval tree. Given a single number or an ordered pair of numbers denoting the start and end of an interval, all intervals that overlapping the query interval in the interval tree will be retrieved.
intersectInterval(aTree, someNumbers)intersectInterval(aTree, someNumbers)
aTree |
a list object representing an interval tree |
someNumbers |
a vector of one or two numbers to test for overlap. If two numbers are provided, they are treated as an interval (start, end). |
a list of vectors. Each vector contains (name, start, end) of an interval
i1 <- new("Interval", start=1.1,end=1.2, key="dummy1") i2 <- new("Interval", start=-1.1,end=1.2, key="dummy2") i3 <- new("Interval", start=-10.1,end=-1.2, key="dummy3") i4 <- new("Interval", start=-1.1,end=1.2, key="dummy4") i5 <- new("Interval", start=-10,end=2, key="dummy5") i6 <- new("Interval", start=-8,end=-5, key="dummy6") myList <- list(i1, i2, i3, i4, i5, i6) atree <- treeFromInterval(myList) ## Not run: intersectInterval(atree, c(-16, -26)) # generate an error ## End(Not run) intersectInterval(atree, c(1, 5)) intersectInterval(atree, c(-12, 15)) intersectInterval(atree, 0)i1 <- new("Interval", start=1.1,end=1.2, key="dummy1") i2 <- new("Interval", start=-1.1,end=1.2, key="dummy2") i3 <- new("Interval", start=-10.1,end=-1.2, key="dummy3") i4 <- new("Interval", start=-1.1,end=1.2, key="dummy4") i5 <- new("Interval", start=-10,end=2, key="dummy5") i6 <- new("Interval", start=-8,end=-5, key="dummy6") myList <- list(i1, i2, i3, i4, i5, i6) atree <- treeFromInterval(myList) ## Not run: intersectInterval(atree, c(-16, -26)) # generate an error ## End(Not run) intersectInterval(atree, c(1, 5)) intersectInterval(atree, c(-12, 15)) intersectInterval(atree, 0)
An S4 class to represent a named numeric interval.
startthe lower end of the interval
endthe higher end of the interval
keythe name of the interval
A S4 class to represent interval tree.
dataa dataframe providing the intervals to be stored in the interval tree. The columns are key, start and end of intervals
rootthe root list of the interval tree built upon the data
Method for checking if an interval is overlapping with a single number (start = end) or a pair of numbers (start < end). A pair of intervals (start1, end1) and (start2, end2) are overlapping if (end2 >= start1 and start2 <= end1).
isOverlap(theObject, someNumbers)isOverlap(theObject, someNumbers)
theObject |
an Interval object |
someNumbers |
a vector of one or two numbers to test overlap. If two numbers are provided, they are treated as an interval (start, end) |
a logical value TRUE or FALSE
i1 <- new("Interval", start=1.1, end=1.2, key="dummy") isOverlap(i1, c(1.0, 1.5)) isOverlap(i1, 1.0) ## Not run: isOverlap(i1, c(2.0, 1.5)) # generate an error isOverlap(i1, c(1.0, 1.5, 2)) # generate an error ## End(Not run)i1 <- new("Interval", start=1.1, end=1.2, key="dummy") isOverlap(i1, c(1.0, 1.5)) isOverlap(i1, 1.0) ## Not run: isOverlap(i1, c(2.0, 1.5)) # generate an error isOverlap(i1, c(1.0, 1.5, 2)) # generate an error ## End(Not run)
Method for checking if an interval is overlapping with a single number (start = end) or an ordered pair of numbers (start < end). Two intervals (start1, end1) and (start2, end2) are overlapping if (end2 >= start1 and start2 <= end1).
## S4 method for signature 'Interval,numeric' isOverlap(theObject, someNumbers)## S4 method for signature 'Interval,numeric' isOverlap(theObject, someNumbers)
theObject |
an Interval object |
someNumbers |
a vector of one or two numbers to test overlap. If two numbers are provided, they are treated as an interval (start, end) |
a logical value TRUE or FALSE
i1 <- new("Interval", start=1.1, end=1.2, key="dummy") isOverlap(i1, c(1.0, 1.5)) isOverlap(i1, 1.0) ## Not run: isOverlap(i1, c(2.0, 1.5)) # generate an error isOverlap(i1, c(1.0, 1.5, 2)) # generate an error ## End(Not run)i1 <- new("Interval", start=1.1, end=1.2, key="dummy") isOverlap(i1, c(1.0, 1.5)) isOverlap(i1, 1.0) ## Not run: isOverlap(i1, c(2.0, 1.5)) # generate an error isOverlap(i1, c(1.0, 1.5, 2)) # generate an error ## End(Not run)
Method for searching an IntervalTree object. Given a number or an ordered pair of numbers denoting the start and end of an interval, all intervals that overlapping the query interval in the IntervalTree object will be retrieved.
overlapQuery(theObject, anInterval)overlapQuery(theObject, anInterval)
theObject |
an IntervalTree object |
anInterval |
a vector of one or two numbers to check overlap, if two numbers are provided, they are treated as an interval (start, end). |
a list of vectors. Each vector contains information about an interval (name, start, end).
m_ranges <- data.frame(c("A", "B", "C", "D"), c(-1.1,2,3,4), c(5,4,6,10)) m_interval_tree <- new("IntervalTree", data=m_ranges, root=list()) overlapQuery(m_interval_tree, 4) res <- overlapQuery(m_interval_tree, c(2.5,7)) resm_ranges <- data.frame(c("A", "B", "C", "D"), c(-1.1,2,3,4), c(5,4,6,10)) m_interval_tree <- new("IntervalTree", data=m_ranges, root=list()) overlapQuery(m_interval_tree, 4) res <- overlapQuery(m_interval_tree, c(2.5,7)) res
Method for searching an IntervalTree object. Given a number or an ordered pair of numbers denoting the start and end of an interval, all intervals that overlapping the query interval in the IntervalTree object will be retrieved.
## S4 method for signature 'IntervalTree,numeric' overlapQuery(theObject, anInterval)## S4 method for signature 'IntervalTree,numeric' overlapQuery(theObject, anInterval)
theObject |
an IntervalTree object |
anInterval |
a vector of one or two numbers to check overlap, if two numbers are provided, they are treated as an interval (start, end). |
a list of vectors. Each vector contains information about an interval (name, start, end).
m_ranges <- data.frame(c("A","B","C","D","E","F"), c(-1.1,2,3,4,20,200), c(5,4,6,10,21.2,400)) m_interval_tree <- new("IntervalTree", data=m_ranges, root=list()) overlapQuery(m_interval_tree, 4) res <- overlapQuery(m_interval_tree, c(2.5,7)) resm_ranges <- data.frame(c("A","B","C","D","E","F"), c(-1.1,2,3,4,20,200), c(5,4,6,10,21.2,400)) m_interval_tree <- new("IntervalTree", data=m_ranges, root=list()) overlapQuery(m_interval_tree, 4) res <- overlapQuery(m_interval_tree, c(2.5,7)) res
Method for constructing interval tree for a list of Interval objects. A node in the tree is a list object. As the leftChild and rightChild of each node are nodes themselves, a binary interval tree stored in a recursive list will be produced if this function is executed successfully.
treeFromInterval(interval_list)treeFromInterval(interval_list)
interval_list |
a list of Interval objects |
a list object representing a binary interval tree
i1 <- new("Interval", start=1.1,end=1.2, key="dummy1") i2 <- new("Interval", start=-1.1,end=1.2, key="dummy2") i3 <- new("Interval", start=-10.1,end=-1.2, key="dummy3") i4 <- new("Interval", start=-1.1,end=1.2, key="dummy4") i5 <- new("Interval", start=-10,end=2, key="dummy5") i6 <- new("Interval", start=-8,end=-5, key="dummy6") myList <- list(i1, i2, i3, i4, i5, i6) atree <- treeFromInterval(myList)i1 <- new("Interval", start=1.1,end=1.2, key="dummy1") i2 <- new("Interval", start=-1.1,end=1.2, key="dummy2") i3 <- new("Interval", start=-10.1,end=-1.2, key="dummy3") i4 <- new("Interval", start=-1.1,end=1.2, key="dummy4") i5 <- new("Interval", start=-10,end=2, key="dummy5") i6 <- new("Interval", start=-8,end=-5, key="dummy6") myList <- list(i1, i2, i3, i4, i5, i6) atree <- treeFromInterval(myList)