Class IntervalTree<T>

A multi-dimensional interval tree implementation.

Inheritance
Object
IntervalTree<T>
Implements
IEnumerable<Tuple<T[], T[]>>
Inherited Members
Namespace: Advanced.Algorithms.DataStructures
Assembly: Advanced.Algorithms.dll
Syntax
public class IntervalTree<T> : IEnumerable<Tuple<T[], T[]>>, IEnumerable where T : IComparable
Type Parameters
Name Description
T

Constructors

| Improve this Doc View Source

IntervalTree(Int32)

Declaration
public IntervalTree(int dimension)
Parameters
Type Name Description
Int32 dimension

Properties

| Improve this Doc View Source

Count

Declaration
public int Count { get; }
Property Value
Type Description
Int32

Methods

| Improve this Doc View Source

Delete(T[], T[])

Delete this interval from this interval tree. Time complexity : O(d(log(n) + m)) where d is dimensions and m is the number of intervals that overlap with this deleted interval.

Declaration
public void Delete(T[] start, T[] end)
Parameters
Type Name Description
T[] start
T[] end
| Improve this Doc View Source

DoOverlap(T[], T[])

Does this interval overlap with any interval in this interval tree?

Declaration
public bool DoOverlap(T[] start, T[] end)
Parameters
Type Name Description
T[] start
T[] end
Returns
Type Description
Boolean
| Improve this Doc View Source

GetEnumerator()

Declaration
public IEnumerator<Tuple<T[], T[]>> GetEnumerator()
Returns
Type Description
IEnumerator<Tuple<T[], T[]>>
| Improve this Doc View Source

GetOverlaps(T[], T[])

returns a list of matching intervals. Time complexity : O(d(log(n) + m)) where d is dimensions and m is the number of overlaps.

Declaration
public List<Tuple<T[], T[]>> GetOverlaps(T[] start, T[] end)
Parameters
Type Name Description
T[] start
T[] end
Returns
Type Description
List<Tuple<T[], T[]>>
| Improve this Doc View Source

Insert(T[], T[])

Add a new interval to this interval tree. Time complexity : O(d(log(n) + m)) where d is dimensions and m is the number of intervals that overlaps with this inserted interval.

Declaration
public void Insert(T[] start, T[] end)
Parameters
Type Name Description
T[] start
T[] end

Explicit Interface Implementations

| Improve this Doc View Source

IEnumerable.GetEnumerator()

Declaration
IEnumerator IEnumerable.GetEnumerator()
Returns
Type Description
IEnumerator

Implements