Google OR-Tools: ortools/util/sorted_interval

Google OR-Tools: ortools/util/sorted_interval_list.h Source File

14#ifndef ORTOOLS_UTIL_SORTED_INTERVAL_LIST_H_

15#define ORTOOLS_UTIL_SORTED_INTERVAL_LIST_H_

17#include <cstddef>

18#include <cstdint>

19#include <iterator>

20#include <ostream>

21#include <set>

22#include <string>

23#include <utility>

24#include <vector>

26#include "absl/container/inlined_vector.h"

27#include "absl/types/span.h"

36#if !defined(SWIG)

53#endif

58 DLOG_IF(DFATAL, s > e) << "Invalid ClosedInterval(" << s << ", " << e

59 << ")";

60 }

74 template <typename H>

76 return H::combine(std::move(h), interval.start, interval.end);

77 }

79 int64_t start = 0;

80 int64_t end = 0;

81};

83#if !defined(SWIG)

86#endif

89std::ostream& operator<<(std::ostream& out,

90 const std::vector<ClosedInterval>& intervals);

101 absl::Span<const ClosedInterval> intervals);

102

114 public:

117

118#if !defined(SWIG)

120 Domain(const Domain& other) : intervals_(other.intervals_) {}

121

124 intervals_ = other.intervals_;

125 return *this;

126 }

127

129 Domain(Domain&& other) noexcept : intervals_(std::move(other.intervals_)) {}

130

133 intervals_ = std::move(other.intervals_);

134 return *this;

135 }

136#endif

137

139 explicit Domain(int64_t value);

140

145 Domain(int64_t left, int64_t right);

146

151

154

157

163

171

180 absl::Span<const int64_t> flat_intervals);

181

194 const std::vector<std::vector<int64_t> >& intervals);

195

205

214

215#if !defined(SWIG)

224 public:

226 const absl::InlinedVector<ClosedInterval, 1>& intervals)

227 : value_(intervals.empty() ? int64_t{0} : intervals.front().start),

228 it_(intervals.begin()),

229 end_(intervals.end()) {}

230

232

234 if (value_ == it_->end) {

235 ++it_;

236 if (it_ != end_) value_ = it_->start;

237 } else {

238 ++value_;

239 }

240 }

241

243 absl::InlinedVector<ClosedInterval, 1>::const_iterator end) const {

244 return it_ != end;

245 }

246

247 private:

248 int64_t value_;

249 absl::InlinedVector<ClosedInterval, 1>::const_iterator it_;

250 absl::InlinedVector<ClosedInterval, 1>::const_iterator end_;

251 };

254 absl::InlinedVector<ClosedInterval, 1>::const_iterator end() const {

256 }

257 const absl::InlinedVector<ClosedInterval, 1>& intervals;

258 };

261 absl::InlinedVector<ClosedInterval, 1>::const_iterator end() const {

263 }

264 absl::InlinedVector<ClosedInterval, 1> intervals;

265 };

268 return {std::move(this->intervals_)};

269 }

270#endif

271

276

280 int64_t Size() const;

281

287 if (intervals_.size() == 1) {

288 return intervals_[0].end == intervals_[0].start + 1;

289 } else if (intervals_.size() == 2) {

290 return intervals_[0].end == intervals_[0].start &&

291 intervals_[1].end == intervals_[1].start;

292 }

293 return false;

294 }

295

300 int64_t Min() const;

301

306 int64_t Max() const;

307

312

318

325

331

337

344

348 bool Contains(int64_t value) const;

349

353 int64_t Distance(int64_t value) const;

354

359

365

370

378

383

388

393

406

411

425

439

446

453

463

471

476

481

503

507 std::string ToString() const;

508

513

515 return intervals_ == other.intervals_;

516 }

517

519 return intervals_ != other.intervals_;

520 }

521

522 template <typename H>

524 return H::combine(std::move(h), domain.intervals_);

525 }

526

536 absl::InlinedVector<ClosedInterval, 1>::const_iterator begin() const {

537 return intervals_.begin();

538 }

539 absl::InlinedVector<ClosedInterval, 1>::const_iterator end() const {

540 return intervals_.end();

541 }

542

543 private:

544

545 void NegateInPlace();

546

547

548

549 static constexpr int kDomainComplexityLimit = 100;

550

551

552

553

554

555

556 absl::InlinedVector<ClosedInterval, 1> intervals_;

557};

558

559std::ostream& operator<<(std::ostream& out, const Domain& domain);

560

561

563

564

566

574

576 public:

579 return a.start != b.start ? a.start < b.start : a.end < b.end;

580 }

581 };

582 typedef std::set<ClosedInterval, IntervalComparator> IntervalSet;

585

588 const std::vector<ClosedInterval>& intervals);

589

595

596

598 const std::vector<int64_t>& ends);

600 const std::vector<int>& ends);

601

606 int64_t end);

607

618

626 const std::vector<int64_t>& ends);

628 const std::vector<int>& ends);

629

634

645

647

660

665

666 void clear() { intervals_.clear(); }

668 intervals_.swap(other.intervals_);

669 }

670

671 private:

672 template <class T>

673 void InsertAll(const std::vector<T>& starts, const std::vector<T>& ends);

674

676};

677

678

679

680#if !defined(SWIG)

682 public:

685

687

688 int64_t operator*() const { return static_cast<int64_t>(current_); }

689

691 ++current_;

692 return *this;

693 }

695

698

700

702 AssertNotFullInt64Range(interval);

703 return Iterator(static_cast<uint64_t>(interval.start));

704 }

706 AssertNotFullInt64Range(interval);

707 return Iterator(static_cast<uint64_t>(interval.end) + 1);

708 }

709

710 private:

711 explicit Iterator(uint64_t current) : current_(current) {}

712

713

714

715 static void AssertNotFullInt64Range(ClosedInterval interval) {

716 DCHECK_NE(static_cast<uint64_t>(interval.start),

717 static_cast<uint64_t>(interval.end) + 1)

718 << "Iteration over the full int64_t range is not supported.";

719 }

720

721

722

723

724

725

726 uint64_t current_;

727};

728#if __cplusplus >= 202002L

729static_assert(std::input_iterator<ClosedInterval::Iterator>);

730#endif

731

732

739#endif

740

741}

742

743#endif

Iterator & operator++()

Definition sorted_interval_list.h:690

bool operator!=(Iterator other) const

Definition sorted_interval_list.h:697

int64_t value_type

Definition sorted_interval_list.h:683

void operator++(int)

Definition sorted_interval_list.h:694

static Iterator Begin(ClosedInterval interval)

Definition sorted_interval_list.h:701

bool operator==(Iterator other) const

Definition sorted_interval_list.h:696

std::ptrdiff_t difference_type

Definition sorted_interval_list.h:684

Iterator(const Iterator &)=default

static Iterator End(ClosedInterval interval)

Definition sorted_interval_list.h:705

int64_t operator*() const

Definition sorted_interval_list.h:688

Iterator & operator=(const Iterator &)=default

Definition sorted_interval_list.h:223

void operator++()

Definition sorted_interval_list.h:233

DomainIterator(const absl::InlinedVector< ClosedInterval, 1 > &intervals)

Definition sorted_interval_list.h:225

int64_t operator*() const

Definition sorted_interval_list.h:231

bool operator!=(absl::InlinedVector< ClosedInterval, 1 >::const_iterator end) const

Definition sorted_interval_list.h:242

Definition sorted_interval_list.h:113

Domain SimplifyUsingImpliedDomain(const Domain &implied_domain) const

static Domain FromVectorIntervals(const std::vector< std::vector< int64_t > > &intervals)

bool OverlapsWith(const Domain &domain) const

DomainIteratorBeginEndWithOwnership Values() const &&

Definition sorted_interval_list.h:267

Domain(Domain &&other) noexcept

Move constructor.

Definition sorted_interval_list.h:129

Domain MultiplicationBy(int64_t coeff, bool *exact=nullptr) const

static Domain FromValues(std::vector< int64_t > values)

bool operator<(const Domain &other) const

friend H AbslHashValue(H h, const Domain &domain)

Definition sorted_interval_list.h:523

int64_t ValueAtOrAfter(int64_t input) const

Domain(const Domain &other)

Copy constructor (mandatory as we define the move constructor).

Definition sorted_interval_list.h:120

std::vector< int64_t > FlattenedIntervals() const

Domain SquareSuperset() const

Domain IntersectionWith(const Domain &domain) const

static Domain LowerOrEqual(int64_t value)

Domain QuadraticSuperset(int64_t a, int64_t b, int64_t c, int64_t d) const

static Domain FromIntervals(absl::Span< const ClosedInterval > intervals)

Domain ContinuousMultiplicationBy(int64_t coeff) const

bool Contains(int64_t value) const

DomainIteratorBeginEnd Values() const &

Definition sorted_interval_list.h:266

Domain PositiveModuloBySuperset(const Domain &modulo) const

Domain AdditionWith(const Domain &domain) const

bool IsIncludedIn(const Domain &domain) const

static Domain FromFlatIntervals(const std::vector< int64_t > &flat_intervals)

int NumIntervals() const

Definition sorted_interval_list.h:532

int64_t SmallestValue() const

Domain()

By default, Domain will be empty.

Definition sorted_interval_list.h:116

int64_t FixedValue() const

Domain DivisionBy(int64_t coeff) const

int64_t Distance(int64_t value) const

std::string ToString() const

Domain & operator=(const Domain &other)

Copy operator (mandatory as we define the move operator).

Definition sorted_interval_list.h:123

static Domain AllValues()

static Domain FromFlatSpanOfIntervals(absl::Span< const int64_t > flat_intervals)

absl::InlinedVector< ClosedInterval, 1 >::const_iterator end() const

Definition sorted_interval_list.h:539

Domain PositiveDivisionBySuperset(const Domain &divisor) const

Domain RelaxIfTooComplex() const

absl::InlinedVector< ClosedInterval, 1 >::const_iterator begin() const

Definition sorted_interval_list.h:536

static Domain GreaterOrEqual(int64_t value)

Domain UnionWith(const Domain &domain) const

ClosedInterval back() const

Definition sorted_interval_list.h:534

Domain Complement() const

bool operator==(const Domain &other) const

Definition sorted_interval_list.h:514

Domain & operator=(Domain &&other) noexcept

Move operator.

Definition sorted_interval_list.h:132

ClosedInterval operator[](int i) const

Definition sorted_interval_list.h:535

Domain PartAroundZero() const

ClosedInterval front() const

Definition sorted_interval_list.h:533

Domain InverseMultiplicationBy(int64_t coeff) const

int64_t ValueAtOrBefore(int64_t input) const

bool operator!=(const Domain &other) const

Definition sorted_interval_list.h:518

bool HasTwoValues() const

Definition sorted_interval_list.h:286

int64_t ClosestValue(int64_t wanted) const

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

void swap(SortedDisjointIntervalList &other) noexcept

Definition sorted_interval_list.h:667

SortedDisjointIntervalList()

Iterator LastIntervalLessOrEqual(int64_t value) const

std::string DebugString() const

Iterator InsertInterval(int64_t start, int64_t end)

const ClosedInterval & last() const

Definition sorted_interval_list.h:664

ConstIterator begin() const

Definition sorted_interval_list.h:658

int NumIntervals() const

Definition sorted_interval_list.h:633

SortedDisjointIntervalList BuildComplementOnInterval(int64_t start, int64_t end)

IntervalSet::const_iterator ConstIterator

Definition sorted_interval_list.h:584

std::set< ClosedInterval, IntervalComparator > IntervalSet

Definition sorted_interval_list.h:582

IntervalSet::iterator Iterator

Definition sorted_interval_list.h:583

Iterator FirstIntervalGreaterOrEqual(int64_t value) const

void clear()

Definition sorted_interval_list.h:666

ConstIterator end() const

Definition sorted_interval_list.h:659

ClosedInterval::Iterator end(ClosedInterval interval)

Definition sorted_interval_list.h:736

int64_t SumOfKMinValueInDomain(const Domain &domain, int k)

std::ostream & operator<<(std::ostream &out, const Assignment &assignment)

bool IntervalsAreSortedAndNonAdjacent(absl::Span< const ClosedInterval > intervals)

ClosedInterval::Iterator begin(ClosedInterval interval)

Definition sorted_interval_list.h:733

int64_t SumOfKMaxValueInDomain(const Domain &domain, int k)

static int input(yyscan_t yyscanner)

constexpr bool operator==(const ClosedInterval &other) const

Definition sorted_interval_list.h:63

int64_t end

Definition sorted_interval_list.h:80

std::string DebugString() const

constexpr bool operator<(const ClosedInterval &other) const

Definition sorted_interval_list.h:70

int64_t start

Definition sorted_interval_list.h:79

ClosedInterval(int64_t v)

Definition sorted_interval_list.h:56

ClosedInterval()

Definition sorted_interval_list.h:55

friend H AbslHashValue(H h, const ClosedInterval &interval)

Definition sorted_interval_list.h:75

ClosedInterval(int64_t s, int64_t e)

Definition sorted_interval_list.h:57

Definition sorted_interval_list.h:259

absl::InlinedVector< ClosedInterval, 1 >::const_iterator end() const

Definition sorted_interval_list.h:261

absl::InlinedVector< ClosedInterval, 1 > intervals

Definition sorted_interval_list.h:264

DomainIterator begin() const

Definition sorted_interval_list.h:260

Definition sorted_interval_list.h:252

absl::InlinedVector< ClosedInterval, 1 >::const_iterator end() const

Definition sorted_interval_list.h:254

DomainIterator begin() const

Definition sorted_interval_list.h:253

const absl::InlinedVector< ClosedInterval, 1 > & intervals

Definition sorted_interval_list.h:257

bool operator()(const ClosedInterval &a, const ClosedInterval &b) const

Definition sorted_interval_list.h:578