OR-Tools  8.2
SortedDisjointIntervalList

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 390 of file sorted_interval_list.h.

Classes

struct  IntervalComparator
 

Public Types

typedef std::set< ClosedInterval, IntervalComparatorIntervalSet
 
typedef IntervalSet::iterator Iterator
 
typedef IntervalSet::const_iterator ConstIterator
 

Public Member Functions

 SortedDisjointIntervalList ()
 
 SortedDisjointIntervalList (const std::vector< ClosedInterval > &intervals)
 
 SortedDisjointIntervalList (const std::vector< int64 > &starts, const std::vector< int64 > &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 start, int64 end)
 Builds the complement of the interval list on the interval [start, end]. More...
 
Iterator InsertInterval (int64 start, int64 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 value, int64 *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 > &starts, const std::vector< int64 > &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 value) const
 Returns an iterator to either: More...
 
Iterator LastIntervalLessOrEqual (int64 value) const
 
std::string DebugString () const
 
ConstIterator begin () const
 Const iterators for SortedDisjoinIntervalList. More...
 
ConstIterator end () const
 
const ClosedIntervallast () 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 399 of file sorted_interval_list.h.

◆ IntervalSet

Definition at line 397 of file sorted_interval_list.h.

◆ Iterator

typedef IntervalSet::iterator Iterator

Definition at line 398 of file sorted_interval_list.h.

Constructor & Destructor Documentation

◆ SortedDisjointIntervalList() [1/4]

Definition at line 563 of file sorted_interval_list.cc.

◆ SortedDisjointIntervalList() [2/4]

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

Definition at line 575 of file sorted_interval_list.cc.

◆ SortedDisjointIntervalList() [3/4]

SortedDisjointIntervalList ( const std::vector< int64 > &  starts,
const std::vector< int64 > &  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 and one for int.

Definition at line 565 of file sorted_interval_list.cc.

◆ SortedDisjointIntervalList() [4/4]

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

Definition at line 570 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 483 of file sorted_interval_list.h.

◆ BuildComplementOnInterval()

SortedDisjointIntervalList BuildComplementOnInterval ( int64  start,
int64  end 
)

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

Definition at line 583 of file sorted_interval_list.cc.

◆ clear()

void clear ( )
inline

Definition at line 491 of file sorted_interval_list.h.

◆ DebugString()

std::string DebugString ( ) const

Definition at line 744 of file sorted_interval_list.cc.

◆ end()

ConstIterator end ( ) const
inline

Definition at line 484 of file sorted_interval_list.h.

◆ FirstIntervalGreaterOrEqual()

SortedDisjointIntervalList::Iterator FirstIntervalGreaterOrEqual ( int64  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 726 of file sorted_interval_list.cc.

◆ GrowRightByOne()

SortedDisjointIntervalList::Iterator GrowRightByOne ( int64  value,
int64 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 665 of file sorted_interval_list.cc.

◆ InsertInterval()

SortedDisjointIntervalList::Iterator InsertInterval ( int64  start,
int64  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 601 of file sorted_interval_list.cc.

◆ InsertIntervals() [1/2]

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

Definition at line 719 of file sorted_interval_list.cc.

◆ InsertIntervals() [2/2]

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

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

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

Definition at line 714 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 489 of file sorted_interval_list.h.

◆ LastIntervalLessOrEqual()

SortedDisjointIntervalList::Iterator LastIntervalLessOrEqual ( int64  value) const

Definition at line 736 of file sorted_interval_list.cc.

◆ NumIntervals()

int NumIntervals ( ) const
inline

Returns the number of disjoint intervals in the list.

Definition at line 458 of file sorted_interval_list.h.

◆ swap()

void swap ( SortedDisjointIntervalList other)
inline

Definition at line 492 of file sorted_interval_list.h.


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