37 if (start == end) return absl::StrFormat("[%d]", start);

38 return absl::StrFormat("[%d,%d]", start, end);

39}

42 absl::Span<const ClosedInterval> intervals) {

43 for (int i = 1; i < intervals.size(); ++i) {

44 if (intervals[i - 1].start > intervals[i - 1].end) return false;

45

46 if (intervals[i - 1].end >= intervals[i].start ||

47 intervals[i - 1].end + 1 >= intervals[i].start) {

48 return false;

49 }

50 }

51 return intervals.empty() ? true

52 : intervals.back().start <= intervals.back().end;

53}

106int64_t CeilRatio(int64_t value, int64_t positive_coeff) {

107 DCHECK_GT(positive_coeff, 0);

108 const int64_t result = value / positive_coeff;

109 const int64_t adjust = static_cast<int64_t>(result * positive_coeff < value);

110 return result + adjust;

111}

113int64_t FloorRatio(int64_t value, int64_t positive_coeff) {

114 DCHECK_GT(positive_coeff, 0);

115 const int64_t result = value / positive_coeff;

116 const int64_t adjust = static_cast<int64_t>(result * positive_coeff > value);

117 return result - adjust;

118}

125 const std::vector<ClosedInterval>& intervals) {

126 return out << IntervalsAsString(intervals);

127}

130 return out << IntervalsAsString(domain);

131}

151 : intervals_({UncheckedClosedInterval(left, right)}) {

152 if (left > right) intervals_.clear();

153}

164 std::sort(values.begin(), values.end());

166 for (const int64_t v : values) {

167 if (result.intervals_.empty() || v > result.intervals_.back().end + 1) {

168 result.intervals_.push_back({v, v});

169 } else {

170 result.intervals_.back().end = v;

171 }

172 if (result.intervals_.back().end == std::numeric_limits<int64_t>::max()) {

173 break;

174 }

175 }

176 return result;

177}

181 result.intervals_.assign(intervals.begin(), intervals.end());

182 SortAndRemoveInvalidIntervals(&result.intervals_);

183 UnionOfSortedIntervals(&result.intervals_);

184 return result;

185}

188 absl::Span<const int64_t> flat_intervals) {

189 DCHECK(flat_intervals.size() % 2 == 0) << flat_intervals.size();

191 result.intervals_.reserve(flat_intervals.size() / 2);

192 for (int i = 0; i < flat_intervals.size(); i += 2) {

193 result.intervals_.push_back({flat_intervals[i], flat_intervals[i + 1]});

194 }

195 SortAndRemoveInvalidIntervals(&result.intervals_);

196 UnionOfSortedIntervals(&result.intervals_);

197 return result;

198}

205 const std::vector<std::vector<int64_t>>& intervals) {

207 for (const std::vector<int64_t>& interval : intervals) {

208 if (interval.size() == 1) {

209 result.intervals_.push_back({interval[0], interval[0]});

210 } else {

211 DCHECK_EQ(interval.size(), 2);

212 result.intervals_.push_back({interval[0], interval[1]});

213 }

214 }

215 SortAndRemoveInvalidIntervals(&result.intervals_);

216 UnionOfSortedIntervals(&result.intervals_);

217 return result;

218}

225 int64_t size = 0;

229 }

230

231

233 return size;

234}

238 return intervals_.front().start;

239}

243 return intervals_.back().end;

244}

248 int64_t result = Min();

250 if (interval.start <= 0 && interval.end >= 0) return 0;

251 for (const int64_t b : {interval.start, interval.end}) {

252 if (b > 0 && b <= std::abs(result)) result = b;

253 if (b < 0 && -b < std::abs(result)) result = b;

254 }

255 }

256 return result;

257}

261 if (interval.start <= 0 && interval.end >= 0) {

262 return Domain(interval.start, interval.end);

263 }

264 }

266}

271 if (wanted <= intervals_[0].start) {

272 return intervals_[0].start;

273 }

274 int64_t best_point;

275 int64_t best_distance;

277 if (interval.start <= wanted && wanted <= interval.end) {

278 return wanted;

279 } else if (interval.start >= wanted) {

280 return CapSub(interval.start, wanted) <= best_distance ? interval.start

281 : best_point;

282 } else {

283 best_point = interval.end;

284 best_distance = CapSub(wanted, interval.end);

285 }

286 }

287 return best_point;

288}

291

292

293

294 auto it = std::upper_bound(intervals_.begin(), intervals_.end(),

296 if (it == intervals_.begin()) return input;

297 --it;

298 return input <= it->end ? input : it->end;

299}

302

303

304

305 auto it = std::upper_bound(intervals_.begin(), intervals_.end(),

307 if (it == intervals_.end()) return input;

308 const int64_t candidate = it->start;

309 if (it == intervals_.begin()) return candidate;

310 --it;

311 return input <= it->end ? input : candidate;

312}

316 return intervals_.front().start;

317}

320

321

322

323 auto it = std::upper_bound(intervals_.begin(), intervals_.end(),

325 if (it == intervals_.begin()) return false;

326 --it;

327 return value <= it->end;

328}

332 int64_t min_distance = std::numeric_limits<int64_t>::max();

334 if (value >= interval.start && value <= interval.end) return 0;

335 if (interval.start > value) {

336 min_distance = std::min(min_distance, interval.start - value);

337 break;

338 } else {

339 min_distance = value - interval.end;

340 }

341 }

342 return min_distance;

343}

346 int i = 0;

347 const auto& others = domain.intervals_;

349

350 for (; i < others.size() && interval.end > others[i].end; ++i) {

351 }

352 if (i == others.size()) return false;

353 if (interval.start < others[i].start) return false;

354 }

355 return true;

356}

359 const auto& a = intervals_;

360 const auto& b = domain.intervals_;

361 for (int i = 0, j = 0; i < a.size() && j < b.size();) {

362 if (a[i].start <= b[j].start) {

363 if (a[i].end < b[j].start) {

364

365 ++i;

366 } else {

367 return true;

368 }

369 } else {

370

371 if (b[j].end < a[i].start) {

372 ++j;

373 } else {

374 return true;

375 }

376 }

377 }

378 return false;

379}

384 result.intervals_.reserve(intervals_.size() + 1);

386 if (interval.start != kint64min) {

387 result.intervals_.push_back({next_start, interval.start - 1});

388 }

389 if (interval.end == kint64max) return result;

390 next_start = interval.end + 1;

391 }

392 result.intervals_.push_back({next_start, kint64max});

394 return result;

395}

398 Domain result = *this;

399 result.NegateInPlace();

400 return result;

401}

420 const auto& a = intervals_;

421 const auto& b = domain.intervals_;

422 for (int i = 0, j = 0; i < a.size() && j < b.size();) {

423 if (a[i].start <= b[j].start) {

424 if (a[i].end < b[j].start) {

425

426 ++i;

427 } else {

428

429

430 if (a[i].end <= b[j].end) {

431 result.intervals_.push_back({b[j].start, a[i].end});

432 ++i;

433 } else {

434 result.intervals_.push_back({b[j].start, b[j].end});

435 ++j;

436 }

437 }

438 } else {

439

440 if (b[j].end < a[i].start) {

441 ++j;

442 } else {

443 if (b[j].end <= a[i].end) {

444 result.intervals_.push_back({a[i].start, b[j].end});

445 ++j;

446 } else {

447 result.intervals_.push_back({a[i].start, a[i].end});

448 ++i;

449 }

450 }

451 }

452 }

454 return result;

455}

459 const auto& a = intervals_;

460 const auto& b = domain.intervals_;

461 result.intervals_.resize(a.size() + b.size());

462 std::merge(a.begin(), a.end(), b.begin(), b.end(), result.intervals_.begin());

463 UnionOfSortedIntervals(&result.intervals_);

464 return result;

465}

470

471 const auto& a = intervals_;

472 const auto& b = domain.intervals_;

473 result.intervals_.reserve(a.size() * b.size());

476 if (i.start > 0 && j.start > 0) {

477 if (AddOverflows(i.start, j.start)) continue;

478 result.intervals_.push_back({i.start + j.start, CapAdd(i.end, j.end)});

479 } else if (i.end < 0 && j.end < 0) {

480 if (AddOverflows(i.end, j.end)) continue;

481 result.intervals_.push_back({CapAdd(i.start, j.start), i.end + j.end});

482 } else {

483 result.intervals_.push_back(

484 {CapAdd(i.start, j.start), CapAdd(i.end, j.end)});

485 }

486 }

487 }

488

489

490 if (a.size() > 1 && b.size() > 1) {

491 std::sort(result.intervals_.begin(), result.intervals_.end());

492 }

493 UnionOfSortedIntervals(&result.intervals_);

494 return result;

495}

498 if (NumIntervals() > kDomainComplexityLimit) {

500 } else {

501 return *this;

502 }

503}

506 if (exact != nullptr) *exact = true;

507 if (intervals_.empty()) return {};

508 if (coeff == 0) return Domain(0);

509

510 const int64_t abs_coeff = std::abs(coeff);

511 const int64_t size_if_non_trivial = abs_coeff > 1 ? Size() : 0;

512 if (size_if_non_trivial > kDomainComplexityLimit) {

513 if (exact != nullptr) *exact = false;

515 }

516

518 if (abs_coeff > 1) {

519 const int64_t max_value = kint64max / abs_coeff;

520 const int64_t min_value = kint64min / abs_coeff;

521 result.intervals_.reserve(size_if_non_trivial);

523 for (int64_t v = i.start;; ++v) {

524

525 if (v >= min_value && v <= max_value) {

526

527 const int64_t new_value = v * abs_coeff;

528 result.intervals_.push_back({new_value, new_value});

529 }

530

531

532 if (v == i.end) break;

533 }

534 }

535 } else {

536 result = *this;

537 }

538 if (coeff < 0) result.NegateInPlace();

539 return result;

540}

543 Domain result = *this;

544 const int64_t abs_coeff = std::abs(coeff);

546 i.start = CapProd(i.start, abs_coeff);

547 i.end = CapProd(i.end, abs_coeff);

548 }

549 UnionOfSortedIntervals(&result.intervals_);

550 if (coeff < 0) result.NegateInPlace();

551 return result;

552}

560 const int64_t b = CapProd(i.end, j.end);

561 const int64_t c = CapProd(i.start, j.end);

563 new_interval.start = std::min({a, b, c, d});

564 new_interval.end = std::max({a, b, c, d});

565 result.intervals_.push_back(new_interval);

566 }

567 }

568 std::sort(result.intervals_.begin(), result.intervals_.end());

569 UnionOfSortedIntervals(&result.intervals_);

570 return result;

571}

574 CHECK_NE(coeff, 0);

575 Domain result = *this;

576 const int64_t abs_coeff = std::abs(coeff);

578 i.start = i.start / abs_coeff;

579 i.end = i.end / abs_coeff;

580 }

581 UnionOfSortedIntervals(&result.intervals_);

582 if (coeff < 0) result.NegateInPlace();

583 return result;

584}

587 if (coeff == 0) {

589 }

590 Domain result = *this;

591 int new_size = 0;

592 const int64_t abs_coeff = std::abs(coeff);

594 const int64_t start = CeilRatio(i.start, abs_coeff);

595 const int64_t end = FloorRatio(i.end, abs_coeff);

596 if (start > end) continue;

597 if (new_size > 0 && start == result.intervals_[new_size - 1].end + 1) {

598 result.intervals_[new_size - 1].end = end;

599 } else {

600 result.intervals_[new_size++] = {start, end};

601 }

602 }

603 result.intervals_.resize(new_size);

604 result.intervals_.shrink_to_fit();

606 if (coeff < 0) result.NegateInPlace();

607 return result;

608}

632 CHECK_GT(modulo.Min(), 0);

633 const int64_t max_mod = modulo.Max() - 1;

634 if (Max() >= 0 && Min() <= 0) {

635 return Domain(std::max(Min(), -max_mod), std::min(Max(), max_mod));

636 }

637 if (Min() > 0) {

638 return ModuloHelper(Min(), Max(), modulo);

639 }

640 DCHECK_LT(Max(), 0);

641 return ModuloHelper(-Max(), -Min(), modulo).Negation();

642}

646 CHECK_GT(divisor.Min(), 0);

647 return Domain(std::min(Min() / divisor.Max(), Min() / divisor.Min()),

648 std::max(Max() / divisor.Min(), Max() / divisor.Max()));

649}

653 const Domain abs_domain =

656 {0, std::numeric_limits<int64_t>::max()}));

657 if (abs_domain.Size() >= kDomainComplexityLimit) {

659 result.intervals_.reserve(abs_domain.NumIntervals());

660 for (const auto& interval : abs_domain) {

661 result.intervals_.push_back(

663 CapProd(interval.end, interval.end)));

664 }

665 UnionOfSortedIntervals(&result.intervals_);

666 return result;

667 } else {

668 std::vector<int64_t> values;

669 values.reserve(abs_domain.Size());

670 for (const int64_t value : abs_domain.Values()) {

671 values.push_back(CapProd(value, value));

672 }

674 }

675}

721 int64_t d) const {

723

724 if (Size() < kDomainComplexityLimit) {

725 std::vector<int64_t> values;

726 values.reserve(Size());

727 for (const int64_t value : Values()) {

728 values.push_back(

731 }

733 }

734

735 if (a == 0) {

737 }

738 if (c == 0) {

740 }

741

744 for (const auto& interval : intervals_) {

745 result.intervals_.push_back(EvaluateQuadraticProdInterval(

746 a, b, c, d, interval.start, interval.end));

747 }

748 std::sort(result.intervals_.begin(), result.intervals_.end());

749 UnionOfSortedIntervals(&result.intervals_);

750 return result;

751}

759 if (implied_domain.IsEmpty()) return result;

760

761 int i = 0;

762 int64_t min_point;

763 int64_t max_point;

764 bool started = false;

766

767

768

769

770 if (started && implied_domain.intervals_[i].start < interval.start) {

771 result.intervals_.push_back({min_point, max_point});

772 started = false;

773 }

774

775

776

777

778 for (; i < implied_domain.intervals_.size(); ++i) {

779 const ClosedInterval current = implied_domain.intervals_[i];

780 if (current.end >= interval.start && current.start <= interval.end) {

781

782 const int64_t inter_max = std::min(interval.end, current.end);

783 if (!started) {

784 started = true;

785 min_point = std::max(interval.start, current.start);

786 max_point = inter_max;

787 } else {

788

789

790 DCHECK_GE(inter_max, max_point);

791 max_point = inter_max;

792 }

793 }

794 if (current.end > interval.end) break;

795 }

796 if (i == implied_domain.intervals_.size()) break;

797 }

798 if (started) {

799 result.intervals_.push_back({min_point, max_point});

800 }

802 return result;

803}

806 std::vector<int64_t> result;

808 result.push_back(interval.start);

809 result.push_back(interval.end);

810 }

811 return result;

812}

815 const auto& d1 = intervals_;

816 const auto& d2 = other.intervals_;

817 const int common_size = std::min(d1.size(), d2.size());

818 for (int i = 0; i < common_size; ++i) {

821 if (i1.start < i2.start) return true;

822 if (i1.start > i2.start) return false;

823 if (i1.end < i2.end) return true;

824 if (i1.end > i2.end) return false;

825 }

826 return d1.size() < d2.size();

827}

832 int64_t current_sum = 0.0;

833 int current_index = 0;

835 if (current_index >= k) break;

836 for (int v(interval.start); v <= interval.end; ++v) {

837 if (current_index >= k) break;

838 current_index++;

839 current_sum += v;

840 }

841 }

842 return current_sum;

843}

852 const std::vector<int64_t>& starts, const std::vector<int64_t>& ends) {

854}

857 const std::vector<int>& starts, const std::vector<int>& ends) {

859}

862 const std::vector<ClosedInterval>& intervals) {

865 }

866}

870 int64_t end) {

872 int64_t next_start = start;

875 const int64_t next_end = CapSub(interval.start, 1);

876 if (next_end > end) break;

877 if (next_start <= next_end) {

879 }

880 next_start = CapAdd(interval.end, 1);

881 }

882 if (next_start <= end) {

884 }

885 return interval_list;

886}

889 int64_t start, int64_t end) {

890

891

892 if (start > end) {

893 LOG(DFATAL) << "Invalid interval: " << ClosedInterval({start, end});

894 return intervals_.end();

895 }

896

897 auto result = intervals_.insert({start, end});

898 if (!result.second) return result.first;

899

900

901

902

903

904

905

906

907

908

909 auto it1 = result.first;

910 if (start == kint64min) {

911 it1 = intervals_.begin();

912 } else {

913 const int64_t before_start = start - 1;

914 while (it1 != intervals_.begin()) {

915 auto prev_it = it1;

916 --prev_it;

917 if (prev_it->end < before_start) break;

918 it1 = prev_it;

919 }

920 }

921

922

923

924 auto it2 = result.first;

926 it2 = intervals_.end();

927 } else {

928 const int64_t after_end = end + 1;

929 do {

930 ++it2;

931 } while (it2 != intervals_.end() && it2->start <= after_end);

932 }

933

934

935

936

937 auto it3 = it2;

938 it3--;

939 if (it1 == it3) return it3;

940 const int64_t new_start = std::min(it1->start, start);

941 const int64_t new_end = std::max(it3->end, end);

942 auto it = intervals_.erase(it1, it3);

943

944

945

946

947 const_cast<ClosedInterval*>(&(*it))->start = new_start;

949 return it;

950}

960 const std::vector<int64_t>& starts, const std::vector<int64_t>& ends) {

961 InsertAll(starts, ends);

962}

965 const std::vector<int>& ends) {

966

967 InsertAll(starts, ends);

968}

972 const auto it = intervals_.upper_bound({value, kint64max});

973 if (it == begin()) return it;

974 auto it_prev = it;

975 it_prev--;

976 DCHECK_LE(it_prev->start, value);

977 return it_prev->end >= value ? it_prev : it;

978}

982 const auto it = intervals_.upper_bound({value, kint64max});

983 if (it == begin()) return end();

984 auto it_prev = it;

985 it_prev--;

986 return it_prev;

987}

990 std::string str;

992 str += interval.DebugString();

993 }

994 return str;

995}

Domain SimplifyUsingImpliedDomain(const Domain &implied_domain) const

Definition sorted_interval_list.cc:757

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

Definition sorted_interval_list.cc:204

bool OverlapsWith(const Domain &domain) const

Definition sorted_interval_list.cc:358

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

Definition sorted_interval_list.cc:505

int64_t Max() const

Definition sorted_interval_list.cc:241

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

Definition sorted_interval_list.cc:163

bool operator<(const Domain &other) const

Definition sorted_interval_list.cc:814

int64_t ValueAtOrAfter(int64_t input) const

Definition sorted_interval_list.cc:301

std::vector< int64_t > FlattenedIntervals() const

Definition sorted_interval_list.cc:805

Domain SquareSuperset() const

Definition sorted_interval_list.cc:651

Domain Negation() const

Definition sorted_interval_list.cc:397

Domain IntersectionWith(const Domain &domain) const

Definition sorted_interval_list.cc:418

static Domain LowerOrEqual(int64_t value)

Definition sorted_interval_list.cc:157

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

Definition sorted_interval_list.cc:720

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

Definition sorted_interval_list.cc:179

Domain ContinuousMultiplicationBy(int64_t coeff) const

Definition sorted_interval_list.cc:542

bool Contains(int64_t value) const

Definition sorted_interval_list.cc:319

DomainIteratorBeginEnd Values() const &

Domain PositiveModuloBySuperset(const Domain &modulo) const

Definition sorted_interval_list.cc:630

int64_t Min() const

Definition sorted_interval_list.cc:236

Domain AdditionWith(const Domain &domain) const

Definition sorted_interval_list.cc:468

bool IsIncludedIn(const Domain &domain) const

Definition sorted_interval_list.cc:345

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

Definition sorted_interval_list.cc:200

bool IsEmpty() const

Definition sorted_interval_list.cc:220

int64_t SmallestValue() const

Definition sorted_interval_list.cc:246

Domain()

By default, Domain will be empty.

int64_t FixedValue() const

Definition sorted_interval_list.cc:314

int64_t Size() const

Definition sorted_interval_list.cc:224

Domain DivisionBy(int64_t coeff) const

Definition sorted_interval_list.cc:573

int64_t Distance(int64_t value) const

Definition sorted_interval_list.cc:331

std::string ToString() const

Definition sorted_interval_list.cc:829

static Domain AllValues()

Definition sorted_interval_list.cc:155

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

Definition sorted_interval_list.cc:187

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

Domain PositiveDivisionBySuperset(const Domain &divisor) const

Definition sorted_interval_list.cc:644

Domain RelaxIfTooComplex() const

Definition sorted_interval_list.cc:497

static Domain GreaterOrEqual(int64_t value)

Definition sorted_interval_list.cc:159

Domain UnionWith(const Domain &domain) const

Definition sorted_interval_list.cc:457

Domain Complement() const

Definition sorted_interval_list.cc:381

bool IsFixed() const

Definition sorted_interval_list.cc:222

Domain PartAroundZero() const

Definition sorted_interval_list.cc:259

Domain InverseMultiplicationBy(int64_t coeff) const

Definition sorted_interval_list.cc:586

int64_t ValueAtOrBefore(int64_t input) const

Definition sorted_interval_list.cc:290

int64_t ClosestValue(int64_t wanted) const

Definition sorted_interval_list.cc:269

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

Definition sorted_interval_list.cc:959

SortedDisjointIntervalList()

Definition sorted_interval_list.cc:849

Iterator LastIntervalLessOrEqual(int64_t value) const

Definition sorted_interval_list.cc:981

std::string DebugString() const

Definition sorted_interval_list.cc:989

Iterator InsertInterval(int64_t start, int64_t end)

Definition sorted_interval_list.cc:888

ConstIterator begin() const

SortedDisjointIntervalList BuildComplementOnInterval(int64_t start, int64_t end)

Definition sorted_interval_list.cc:869

IntervalSet::iterator Iterator

Iterator FirstIntervalGreaterOrEqual(int64_t value) const

Definition sorted_interval_list.cc:971

ConstIterator end() const

int64_t CapAdd(int64_t x, int64_t y)

int64_t FloorRatio(int64_t value, int64_t positive_coeff)

Definition sorted_interval_list.cc:113

int64_t CapSub(int64_t x, int64_t y)

int64_t CeilRatio(int64_t value, int64_t positive_coeff)

Definition sorted_interval_list.cc:106

ClosedInterval::Iterator end(ClosedInterval interval)

int64_t SumOfKMinValueInDomain(const Domain &domain, int k)

Definition sorted_interval_list.cc:831

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

bool AddOverflows(int64_t x, int64_t y)

int64_t CapProd(int64_t x, int64_t y)

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

Definition sorted_interval_list.cc:41

int64_t SumOfKMaxValueInDomain(const Domain &domain, int k)

Definition sorted_interval_list.cc:845

static int input(yyscan_t yyscanner)

std::string DebugString() const

Definition sorted_interval_list.cc:36

static const int64_t kint64max

static const int64_t kint64min