cgatools::util::IntervalTree< TRange, TBoundary, TValue, Overlap, GetBoundary, BoundaryLess > Class Template Reference

Class that maintains a mapping from key to value, where the key is a type with range semantics, for the purpose of finding the intersection of a range to a set of ranges. More...

#include <RangeIntersector.hpp>

List of all members.

Classes
struct	Node
Public Types
typedef IntervalTree< TRange, TBoundary, TValue, Overlap, GetBoundary, BoundaryLess >	MyType
typedef std::pair< const TRange, TValue >	value_type
typedef const value_type *	QueryResultType
Public Member Functions
	IntervalTree (const Overlap &overlap=Overlap(), const GetBoundary &getBoundary=GetBoundary(), const BoundaryLess &boundaryLess=BoundaryLess())
	Creates empty tree.
	IntervalTree (const MyType &rhs)
	Copy constructor. Provides value copy semantics.
const MyType &	operator= (const MyType &rhs)
	Assignment. Provides value copy semantics.
void	put (const TRange &range, const TValue &value)
	Add a range to the set.
void	intersect (const TRange &range, std::vector< QueryResultType > &result) const
	Find the intersection of the given range with all the ranges in the set.
size_t	size () const
	Number of ranges in the tree.
void	swap (MyType &rhs)
	Swaps the internals of this tree with another.
void	clear ()
	Clear all data.
size_t	getMaxDepth () const
	Debug function: returns tree depth and validates the tree structure.

---

Detailed Description

template<typename TRange, typename TBoundary, typename TValue, typename Overlap, typename GetBoundary, typename BoundaryLess = std::less<TBoundary>>
class cgatools::util::IntervalTree< TRange, TBoundary, TValue, Overlap, GetBoundary, BoundaryLess >

Class that maintains a mapping from key to value, where the key is a type with range semantics, for the purpose of finding the intersection of a range to a set of ranges.

Requirements:

• TRange class {a, b} with two boundaries a and b of type TBoundary with strict total order defined by BoundaryLess operator. Boundaries of a given range are obtained using GetBoundary operator that takes the range as the first argument and the boundary index (0/1) as the second argument.
• Overlap operator such that {a, b} never overlaps {x, y} if b < x. This implementation uses an RB-tree where every node is augmented with the maximum upper range boundary for all ranges in the subtree defined by the node (see CLR book section 15.3, "Interval trees"). The RB-tree itself is a left-leaning RB-tree variant described by Robert Sedgewick: http://www.cs.princeton.edu/~rs/talks/LLRB/LLRB.pdf . The implementation is adopted from: http://www.cs.princeton.edu/~rs/talks/LLRB/Java/RedBlackBST.java . NOTES:
• Currently the tree orders ranges on left boundary and nothing else. Since intersect() returns ranges in the tree order, it may be useful to allow custom comparators for TRange; however, they'd still need to order on the left boundary first for correctness.
• For now I limited the interface to what the old RangeIntersector used to provide; feel free to extend it as needed.
• There are no parent pointers, so if we ever need iterators, we will need to maintain stacks in them (or add parent pointers, which is somewhat costly).

---

Member Function Documentation

template<typename TRange, typename TBoundary, typename TValue, typename Overlap, typename GetBoundary, typename BoundaryLess = std::less<TBoundary>>

size_t cgatools::util::IntervalTree< TRange, TBoundary, TValue, Overlap, GetBoundary, BoundaryLess >::getMaxDepth

(

)

const [inline]

Debug function: returns tree depth and validates the tree structure.

template<typename TRange, typename TBoundary, typename TValue, typename Overlap, typename GetBoundary, typename BoundaryLess = std::less<TBoundary>>

void cgatools::util::IntervalTree< TRange, TBoundary, TValue, Overlap, GetBoundary, BoundaryLess >::intersect	(	const TRange &	range,
		std::vector< QueryResultType > &	result
	)			const [inline]

Find the intersection of the given range with all the ranges in the set.

---

The documentation for this class was generated from the following file:

• RangeIntersector.hpp