Google OR-Tools v9.15
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
operations_research::SortedDisjointIntervalList Class Reference

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

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

Member Typedef Documentation

◆ ConstIterator

typedef IntervalSet::const_iterator operations_research::SortedDisjointIntervalList::ConstIterator

Definition at line 584 of file sorted_interval_list.h.

◆ IntervalSet

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

Definition at line 582 of file sorted_interval_list.h.

◆ Iterator

typedef IntervalSet::iterator operations_research::SortedDisjointIntervalList::Iterator

Definition at line 583 of file sorted_interval_list.h.

Constructor & Destructor Documentation

◆ SortedDisjointIntervalList() [1/4]

operations_research::SortedDisjointIntervalList::SortedDisjointIntervalList ( )

Definition at line 849 of file sorted_interval_list.cc.

◆ SortedDisjointIntervalList() [2/4]

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

Definition at line 861 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.

Definition at line 851 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 856 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 658 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 869 of file sorted_interval_list.cc.

◆ clear()

void operations_research::SortedDisjointIntervalList::clear ( )
inline

Definition at line 666 of file sorted_interval_list.h.

◆ DebugString()

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

Definition at line 989 of file sorted_interval_list.cc.

◆ end()

ConstIterator operations_research::SortedDisjointIntervalList::end ( ) const
inline

Definition at line 659 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 971 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).

Definition at line 888 of file sorted_interval_list.cc.

◆ InsertIntervals() [1/2]

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

Definition at line 964 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 959 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 664 of file sorted_interval_list.h.

◆ LastIntervalLessOrEqual()

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

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

◆ swap()

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

Definition at line 667 of file sorted_interval_list.h.

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