#include <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)

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

SortedDisjointIntervalList	BuildComplementOnInterval (int64_t start, int64_t end)

Iterator	InsertInterval (int64_t start, int64_t end)

Iterator	GrowRightByOne (int64_t value, int64_t *newly_covered)

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

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

int	NumIntervals () const

Iterator	FirstIntervalGreaterOrEqual (int64_t value) const

Iterator	LastIntervalLessOrEqual (int64_t value) const

std::string	DebugString () const

ConstIterator	begin () const

ConstIterator	end () const

const ClosedInterval &	last () const

void	clear ()

void	swap (SortedDisjointIntervalList &other)

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.

Todo: (user): Templatize the class on the type of the bounds.

Definition at line 517 of file sorted_interval_list.h.

Member Typedef Documentation

◆ ConstIterator

IntervalSet::const_iterator operations_research::SortedDisjointIntervalList::ConstIterator

Definition at line 526 of file sorted_interval_list.h.

◆ IntervalSet

std::set<ClosedInterval, IntervalComparator> operations_research::SortedDisjointIntervalList::IntervalSet

Definition at line 524 of file sorted_interval_list.h.

◆ Iterator

IntervalSet::iterator operations_research::SortedDisjointIntervalList::Iterator

Definition at line 525 of file sorted_interval_list.h.

Constructor & Destructor Documentation

◆ SortedDisjointIntervalList() [1/4]

operations_research::SortedDisjointIntervalList::SortedDisjointIntervalList ( )

Definition at line 733 of file sorted_interval_list.cc.

◆ SortedDisjointIntervalList() [2/4]

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

explicit

Definition at line 745 of file sorted_interval_list.cc.

◆ SortedDisjointIntervalList() [3/4]

operations_research::SortedDisjointIntervalList::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.

Todo: (user): Explain why we favored this API to the more natural input std::vector<ClosedInterval> or std::vector<std::pair<int, int>>.

Definition at line 735 of file sorted_interval_list.cc.

◆ SortedDisjointIntervalList() [4/4]

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

Definition at line 740 of file sorted_interval_list.cc.

Member Function Documentation

◆ begin()

ConstIterator operations_research::SortedDisjointIntervalList::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 611 of file sorted_interval_list.h.

◆ BuildComplementOnInterval()

SortedDisjointIntervalList operations_research::SortedDisjointIntervalList::BuildComplementOnInterval	(	int64_t	start,
		int64_t	end )

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

Definition at line 753 of file sorted_interval_list.cc.

◆ clear()

void operations_research::SortedDisjointIntervalList::clear ( )

inline

Definition at line 619 of file sorted_interval_list.h.

◆ DebugString()

std::string operations_research::SortedDisjointIntervalList::DebugString ( ) const

Definition at line 915 of file sorted_interval_list.cc.

◆ end()

ConstIterator operations_research::SortedDisjointIntervalList::end ( ) const

inline

Definition at line 612 of file sorted_interval_list.h.

◆ FirstIntervalGreaterOrEqual()

SortedDisjointIntervalList::Iterator operations_research::SortedDisjointIntervalList::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 897 of file sorted_interval_list.cc.

◆ GrowRightByOne()

SortedDisjointIntervalList::Iterator operations_research::SortedDisjointIntervalList::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.

No interval containing or adjacent to "value" on the left (i.e. below).

No interval adjacent to "value" on the right: insert a singleton.

There is an interval adjacent to "value" on the right. Extend it by one. Note that we already know that there won't be a merge with another interval on the left, since there were no interval adjacent to "value" on the left.

At this point, "it_prev" points to an interval containing or adjacent to "value" on the left: grow it by one, and if it now touches the next interval, merge with it.

We need to merge it_prev with 'it'.

Definition at line 836 of file sorted_interval_list.cc.

◆ InsertInterval()

SortedDisjointIntervalList::Iterator operations_research::SortedDisjointIntervalList::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).

start > end could mean an empty interval, but we prefer to LOG(DFATAL) anyway. Really, the user should never give us that.

Todo: (user): tune the algorithm below if it proves to be a bottleneck. For example, one could try to avoid an insertion if it's not needed (when the interval merges with a single existing interval or is fully contained by one).

Iterate over the previous iterators whose end is after (or almost at) our start. After this, "it1" will point to the first interval that needs to be merged with the current interval (possibly pointing to the current interval itself, if no "earlier" interval should be merged).

Ditto, on the other side: "it2" will point to the interval after the last one that should be merged with the current interval.

[it1..it2) is the range (inclusive on it1, exclusive on it2) of intervals that should be merged together. We'll set it3 = it2-1 and erase [it1..it3) and set *it3 to the merged interval.

HACK(user): set iterators point to const values. Which is expected, because if one alters a set element's value, then it collapses the set property! But in this very special case, we know that we can just overwrite it->start, so we do it.

Definition at line 772 of file sorted_interval_list.cc.

◆ InsertIntervals() [1/2]

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

Todo: (user): treat kint32min and kint32max as their kint64 variants.

Definition at line 890 of file sorted_interval_list.cc.

◆ InsertIntervals() [2/2]

void operations_research::SortedDisjointIntervalList::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 885 of file sorted_interval_list.cc.

◆ last()

const ClosedInterval & operations_research::SortedDisjointIntervalList::last ( ) const

inline

Returns a const& to the last interval. The list must not be empty.

Definition at line 617 of file sorted_interval_list.h.

◆ LastIntervalLessOrEqual()

SortedDisjointIntervalList::Iterator operations_research::SortedDisjointIntervalList::LastIntervalLessOrEqual ( int64_t value ) const

Definition at line 907 of file sorted_interval_list.cc.

◆ NumIntervals()

int operations_research::SortedDisjointIntervalList::NumIntervals ( ) const

inline

Returns the number of disjoint intervals in the list.

Definition at line 586 of file sorted_interval_list.h.

◆ swap()

void operations_research::SortedDisjointIntervalList::swap ( SortedDisjointIntervalList & other )

inline

Definition at line 620 of file sorted_interval_list.h.

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

ortools/util/sorted_interval_list.h
ortools/util/sorted_interval_list.cc

Classes

Public Types

Public Member Functions

Detailed Description

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()