Detailed Description

This class represents a sorted list of disjoint, closed intervals.

When an interval is inserted, all intervals that overlap it or are adjacent to it are merged into one. I.e. [0,14] and [15,30] will be merged to [0,30].

Iterators returned by this class are invalidated by non-const operations.

Definition at line 484 of file sorted_interval_list.h.

Classes
struct	IntervalComparator

Public Types
typedef std::set< ClosedInterval, IntervalComparator >	IntervalSet

typedef IntervalSet::iterator	Iterator

typedef IntervalSet::const_iterator	ConstIterator

Public Member Functions
	SortedDisjointIntervalList ()

	SortedDisjointIntervalList (const std::vector< ClosedInterval > &intervals)

	SortedDisjointIntervalList (const std::vector< int64_t > &starts, const std::vector< int64_t > &ends)
	Creates a SortedDisjointIntervalList and fills it with intervals [starts[i]..ends[i]]. More...

	SortedDisjointIntervalList (const std::vector< int > &starts, const std::vector< int > &ends)

SortedDisjointIntervalList	BuildComplementOnInterval (int64_t start, int64_t end)
	Builds the complement of the interval list on the interval [start, end]. More...

Iterator	InsertInterval (int64_t start, int64_t end)
	Adds the interval [start..end] to the list, and merges overlapping or immediately adjacent intervals ([2, 5] and [6, 7] are adjacent, but [2, 5] and [7, 8] are not). More...

Iterator	GrowRightByOne (int64_t value, int64_t *newly_covered)
	If value is in an interval, increase its end by one, otherwise insert the interval [value, value]. More...

void	InsertIntervals (const std::vector< int64_t > &starts, const std::vector< int64_t > &ends)
	Adds all intervals [starts[i]..ends[i]]. More...

void	InsertIntervals (const std::vector< int > &starts, const std::vector< int > &ends)

int	NumIntervals () const
	Returns the number of disjoint intervals in the list. More...

Iterator	FirstIntervalGreaterOrEqual (int64_t value) const
	Returns an iterator to either: More...

Iterator	LastIntervalLessOrEqual (int64_t value) const

std::string	DebugString () const

ConstIterator	begin () const
	Const iterators for SortedDisjoinIntervalList. More...

ConstIterator	end () const

const ClosedInterval &	last () const
	Returns a const& to the last interval. More...

void	clear ()

void	swap (SortedDisjointIntervalList &other)

Member Typedef Documentation

◆ ConstIterator

typedef IntervalSet::const_iterator ConstIterator

Definition at line 493 of file sorted_interval_list.h.

◆ IntervalSet

typedef std::set<ClosedInterval, IntervalComparator> IntervalSet

Definition at line 491 of file sorted_interval_list.h.

◆ Iterator

typedef IntervalSet::iterator Iterator

Definition at line 492 of file sorted_interval_list.h.

Constructor & Destructor Documentation

◆ SortedDisjointIntervalList() [1/4]

SortedDisjointIntervalList ( )

Definition at line 675 of file sorted_interval_list.cc.

◆ SortedDisjointIntervalList() [2/4]

SortedDisjointIntervalList ( const std::vector< ClosedInterval > & intervals )

explicit

Definition at line 687 of file sorted_interval_list.cc.

◆ SortedDisjointIntervalList() [3/4]

SortedDisjointIntervalList	(	const std::vector< int64_t > &	starts,
		const std::vector< int64_t > &	ends
	)

Creates a SortedDisjointIntervalList and fills it with intervals [starts[i]..ends[i]].

All intervals must be consistent (starts[i] <= ends[i]). There are two version, one for int64_t and one for int.

Definition at line 677 of file sorted_interval_list.cc.

◆ SortedDisjointIntervalList() [4/4]

SortedDisjointIntervalList	(	const std::vector< int > &	starts,
		const std::vector< int > &	ends
	)

Definition at line 682 of file sorted_interval_list.cc.

Member Function Documentation

◆ begin()

ConstIterator begin ( ) const

inline

Const iterators for SortedDisjoinIntervalList.

One example usage is to use range loops in C++: SortedDisjointIntervalList list; ... for (const ClosedInterval& interval : list) { ... }

Definition at line 578 of file sorted_interval_list.h.

◆ BuildComplementOnInterval()

SortedDisjointIntervalList BuildComplementOnInterval	(	int64_t	start,
		int64_t	end
	)

Builds the complement of the interval list on the interval [start, end].

Definition at line 695 of file sorted_interval_list.cc.

◆ clear()

void clear ( )

inline

Definition at line 586 of file sorted_interval_list.h.

◆ DebugString()

std::string DebugString ( ) const

Definition at line 857 of file sorted_interval_list.cc.

◆ end()

ConstIterator end ( ) const

inline

Definition at line 579 of file sorted_interval_list.h.

◆ FirstIntervalGreaterOrEqual()

SortedDisjointIntervalList::Iterator FirstIntervalGreaterOrEqual ( int64_t value ) const

Returns an iterator to either:

the first interval containing or above the given value, or
the last interval containing or below the given value. Returns end() if no interval fulfills that condition.

If the value is within an interval, both functions will return it.

Definition at line 839 of file sorted_interval_list.cc.

◆ GrowRightByOne()

SortedDisjointIntervalList::Iterator GrowRightByOne	(	int64_t	value,
		int64_t *	newly_covered
	)

If value is in an interval, increase its end by one, otherwise insert the interval [value, value].

In both cases, this returns an iterator to the new/modified interval (possibly merged with others) and fills newly_covered with the new value that was just added in the union of all the intervals.

If this causes an interval ending at kint64max to grow, it will die with a CHECK fail.

Definition at line 778 of file sorted_interval_list.cc.

◆ InsertInterval()

SortedDisjointIntervalList::Iterator InsertInterval	(	int64_t	start,
		int64_t	end
	)

Adds the interval [start..end] to the list, and merges overlapping or immediately adjacent intervals ([2, 5] and [6, 7] are adjacent, but [2, 5] and [7, 8] are not).

Returns an iterator to the inserted interval (possibly merged with others).

If start > end, it does LOG(DFATAL) and returns end() (no interval added).

Definition at line 714 of file sorted_interval_list.cc.

◆ InsertIntervals() [1/2]

void InsertIntervals	(	const std::vector< int > &	starts,
		const std::vector< int > &	ends
	)

Definition at line 832 of file sorted_interval_list.cc.

◆ InsertIntervals() [2/2]

void InsertIntervals	(	const std::vector< int64_t > &	starts,
		const std::vector< int64_t > &	ends
	)

Adds all intervals [starts[i]..ends[i]].

Same behavior as InsertInterval() upon invalid intervals. There's a version with int64_t and int32_t.

Definition at line 827 of file sorted_interval_list.cc.

◆ last()

const ClosedInterval& last ( ) const

inline

Returns a const& to the last interval.

The list must not be empty.

Definition at line 584 of file sorted_interval_list.h.

◆ LastIntervalLessOrEqual()

SortedDisjointIntervalList::Iterator LastIntervalLessOrEqual ( int64_t value ) const

Definition at line 849 of file sorted_interval_list.cc.

◆ NumIntervals()

int NumIntervals ( ) const

inline

Returns the number of disjoint intervals in the list.

Definition at line 553 of file sorted_interval_list.h.

◆ swap()

void swap ( SortedDisjointIntervalList & other )

inline

Definition at line 587 of file sorted_interval_list.h.

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

Detailed Description

Classes

Public Types

Public Member Functions

Member Typedef Documentation

◆ ConstIterator

◆ IntervalSet

◆ Iterator

Constructor & Destructor Documentation

◆ SortedDisjointIntervalList() [1/4]

◆ SortedDisjointIntervalList() [2/4]

◆ SortedDisjointIntervalList() [3/4]

◆ SortedDisjointIntervalList() [4/4]

Member Function Documentation

◆ begin()

◆ BuildComplementOnInterval()

◆ clear()

◆ DebugString()

◆ end()

◆ FirstIntervalGreaterOrEqual()

◆ GrowRightByOne()

◆ InsertInterval()

◆ InsertIntervals() [1/2]

◆ InsertIntervals() [2/2]

◆ last()

◆ LastIntervalLessOrEqual()

◆ NumIntervals()

◆ swap()