Home Original page

Google OR-Tools: ortools/constraint_solver/routing_filter_committables.h Source File

1

2

3

4

5

6

7

8

9

10

11

12

13

14#ifndef ORTOOLS_CONSTRAINT_SOLVER_ROUTING_FILTER_COMMITTABLES_H_

15#define ORTOOLS_CONSTRAINT_SOLVER_ROUTING_FILTER_COMMITTABLES_H_

16

17#include <algorithm>

18#include <cstddef>

19#include <cstdint>

20#include <limits>

21#include <vector>

22

23#include "absl/log/check.h"

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

27

29

30

31

32template <typename T>

34 public:

36 : current_(value), committed_(value) {}

37

38 const T& Get() const { return current_; }

40

41 void Set(const T& value) { current_ = value; }

42

47

48 void Revert() { current_ = committed_; }

49

50 void Commit() { committed_ = current_; }

51

52 private:

53 T current_;

54 T committed_;

55};

56

57template <typename T>

59 public:

60

62 : elements_(num_elements, {value, value}), changed_(num_elements) {}

63

64

65 size_t Size() const { return elements_.size(); }

66

67

68

69

70 T Get(size_t index) const {

71 DCHECK_LT(index, elements_.size());

72 return elements_[index].current;

73 }

74

75

76

78 DCHECK_LT(index, elements_.size());

79 changed_.Set(index);

80 return elements_[index].current;

81 }

82

83

84 void Set(size_t index, const T& value) {

85 DCHECK_GE(index, 0);

86 DCHECK_LT(index, elements_.size());

87 changed_.Set(index);

88 elements_[index].current = value;

89 }

90

91

93 for (const size_t index : changed_.PositionsSetAtLeastOnce()) {

94 elements_[index].current = elements_[index].committed;

95 }

96 changed_.ResetAllToFalse();

97 }

98

99

101 for (const size_t index : changed_.PositionsSetAtLeastOnce()) {

102 elements_[index].committed = elements_[index].current;

103 }

104 changed_.ResetAllToFalse();

105 }

106

107

109 changed_.ResetAllToFalse();

110 elements_.assign(elements_.size(), {value, value});

111 }

112

113

115 DCHECK_LT(index, elements_.size());

116 return elements_[index].committed;

117 }

118

119

120

121 bool HasChanged(size_t index) const { return changed_[index]; }

122

123

124

126 return changed_.PositionsSetAtLeastOnce();

127 }

128

129

130

131

132

133 private:

134 struct VersionedElement {

135 T current;

136 T committed;

137 };

138

139 std::vector<VersionedElement> elements_;

140

141 SparseBitset<size_t> changed_;

142};

143

152

153

154

155

156

157template <typename T>

160 std::vector<T>& temp_container) {

161 temp_container.clear();

162 const int num_ranges = ranges.Size();

163 for (int i = 0; i < num_ranges; ++i) {

164 const size_t new_begin = temp_container.size();

166 temp_container.insert(temp_container.end(), mutable_input.begin() + begin,

167 mutable_input.begin() + end);

168 ranges.Set(i, {.begin = new_begin, .end = temp_container.size()});

169 }

170 std::swap(mutable_input, temp_container);

171}

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

210 public:

212 : range_of_path_(num_paths, {.begin = 0, .end = 0}),

214 vehicle_breaks_(num_paths),

215 committed_vehicle_breaks_(num_paths),

216 max_num_committed_elements_(16 * num_nodes),

217 num_elements_(0) {

218 nodes_.reserve(max_num_committed_elements_);

219 transit_.reserve(max_num_committed_elements_);

220 travel_.reserve(max_num_committed_elements_);

221 travel_sum_.reserve(max_num_committed_elements_);

222 cumul_.reserve(max_num_committed_elements_);

223 }

224

228

232

236

238

239

241 min = std::max(min, lower_bound);

243 }

244

245

247 max = std::min(max, upper_bound);

249 }

250

251

257

258

261 DCHECK(!other.IsEmpty());

263 }

264

265

266 void Add(const Interval& other) { *this = *this + other; }

267

268

271 DCHECK(!other.IsEmpty());

273 }

274

275

277

279 return {.min = std::numeric_limits<int64_t>::min(),

280 .max = std::numeric_limits<int64_t>::max()};

281 }

282 };

283

294

295

296 void PushNode(int node) { nodes_.push_back(node); }

297

298

300 DCHECK_GE(path, 0);

301 DCHECK_LT(path, range_of_path_.Size());

302 DCHECK(!range_of_path_.HasChanged(path));

303 range_of_path_.Set(path,

304 {.begin = num_elements_.Get(), .end = nodes_.size()});

305

306

308 travel_.resize(nodes_.size(), 0);

309 travel_sum_.resize(nodes_.size(), 0);

311 num_elements_.Set(nodes_.size());

313 }

314

315

317 range_of_path_.SetAllAndCommit({.begin = 0, .end = 0});

318 num_elements_.SetAndCommit(0);

319 nodes_.clear();

320 transit_.clear();

321 travel_.clear();

322 travel_sum_.clear();

323 cumul_.clear();

325 }

326

327

329 range_of_path_.Revert();

330 num_elements_.Revert();

331 nodes_.resize(num_elements_.Get());

332 transit_.resize(num_elements_.Get());

333 travel_.resize(num_elements_.Get());

334 travel_sum_.resize(num_elements_.Get());

335 cumul_.resize(num_elements_.Get());

336 span_.Revert();

337 }

338

339

340

341

343 for (const int path : range_of_path_.ChangedIndices()) {

344 committed_vehicle_breaks_[path] = vehicle_breaks_[path];

345 }

346 range_of_path_.Commit();

347 num_elements_.Commit();

348 span_.Commit();

349

350 if (num_elements_.Get() <= max_num_committed_elements_) return;

356 range_of_path_.Commit();

357 num_elements_.SetAndCommit(nodes_.size());

358 }

359

360

362 const auto [begin, end] = range_of_path_.GetCommitted(path);

363 return absl::MakeConstSpan(nodes_.data() + begin, nodes_.data() + end);

364 }

365

366

367 absl::Span<const int> Nodes(int path) const {

368 const auto [begin, end] = range_of_path_.Get(path);

369 return absl::MakeConstSpan(nodes_.data() + begin, nodes_.data() + end);

370 }

371

372

373 absl::Span<const Interval> Transits(int path) const {

374 auto [begin, end] = range_of_path_.Get(path);

375

376

378 return absl::MakeConstSpan(transit_.data() + begin, transit_.data() + end);

379 }

380

381

383 auto [begin, end] = range_of_path_.Get(path);

384

385

387 return absl::MakeSpan(transit_.data() + begin, transit_.data() + end);

388 }

389

390

392 auto [begin, end] = range_of_path_.GetCommitted(path);

394 return absl::MakeConstSpan(travel_.data() + begin, travel_.data() + end);

395 }

396

397

398 absl::Span<const int64_t> Travels(int path) const {

399 auto [begin, end] = range_of_path_.Get(path);

401 return absl::MakeConstSpan(travel_.data() + begin, travel_.data() + end);

402 }

403

404

406 auto [begin, end] = range_of_path_.Get(path);

408 return absl::MakeSpan(travel_.data() + begin, travel_.data() + end);

409 }

410

411

412 absl::Span<const int64_t> TravelSums(int path) const {

413 const auto [begin, end] = range_of_path_.Get(path);

414 return absl::MakeConstSpan(travel_sum_.data() + begin,

415 travel_sum_.data() + end);

416 }

417

418

420 const auto [begin, end] = range_of_path_.Get(path);

421 return absl::MakeSpan(travel_sum_.data() + begin, travel_sum_.data() + end);

422 }

423

424

425 absl::Span<const Interval> Cumuls(int path) const {

426 const auto [begin, end] = range_of_path_.Get(path);

427 return absl::MakeConstSpan(cumul_.data() + begin, cumul_.data() + end);

428 }

429

430

432 const auto [begin, end] = range_of_path_.Get(path);

433 return absl::MakeSpan(cumul_.data() + begin, cumul_.data() + end);

434 }

435

436

437 Interval Span(int path) const { return span_.Get(path); }

438

439

440

442 DCHECK(range_of_path_.HasChanged(path));

443 return span_.GetMutable(path);

444 }

445

446

447

448 absl::Span<const VehicleBreak> VehicleBreaks(int path) const {

449 return absl::MakeConstSpan(range_of_path_.HasChanged(path)

450 ? vehicle_breaks_[path]

451 : committed_vehicle_breaks_[path]);

452 }

453

454

455

457 DCHECK(range_of_path_.HasChanged(path));

458 return vehicle_breaks_[path];

459 }

460

461

462 int NumNodes(int path) const { return range_of_path_.Get(path).Size(); }

463

465 return absl::MakeConstSpan(range_of_path_.ChangedIndices());

466 }

467

469 return range_of_path_.HasChanged(path);

470 }

471

472 private:

473

474

475

476

477

478

479

480

481

482

483

484

485

486 std::vector<int> nodes_;

487 std::vector<Interval> transit_;

488 std::vector<int64_t> travel_;

489 std::vector<int64_t> travel_sum_;

490 std::vector<Interval> cumul_;

491

492 std::vector<int> temp_ints_;

493 std::vector<Interval> temp_intervals_;

494 std::vector<int64_t> temp_int64s_;

495

496

498

500

501

502 std::vector<std::vector<VehicleBreak>> vehicle_breaks_;

503 std::vector<std::vector<VehicleBreak>> committed_vehicle_breaks_;

504

505

506

507 const size_t max_num_committed_elements_;

508

510};

511

513

515 public:

517 : range_of_path_(num_paths, {.begin = 0, .end = 0}),

518 max_num_committed_elements_(16 * num_nodes),

519 num_elements_(0) {

520 pre_visit_.reserve(max_num_committed_elements_);

521 post_visit_.reserve(max_num_committed_elements_);

522 }

523

525

526

528 DCHECK_GE(path, 0);

529 DCHECK_LT(path, range_of_path_.Size());

530 DCHECK(!range_of_path_.HasChanged(path));

531 size_t num_current_elements = num_elements_.Get();

532 range_of_path_.Set(path, {.begin = num_current_elements,

533 .end = num_current_elements + new_num_nodes});

534

535

536 num_current_elements += new_num_nodes;

537 pre_visit_.resize(num_current_elements, 0);

538 post_visit_.resize(num_current_elements, 0);

539 num_elements_.Set(num_current_elements);

540 }

541

542

544 range_of_path_.SetAllAndCommit({.begin = 0, .end = 0});

545 num_elements_.SetAndCommit(0);

546 pre_visit_.clear();

547 post_visit_.clear();

548 }

549

550

552 range_of_path_.Revert();

553 num_elements_.Revert();

554 pre_visit_.resize(num_elements_.Get());

555 post_visit_.resize(num_elements_.Get());

556 }

557

558

559

560

562 range_of_path_.Commit();

563 num_elements_.Commit();

564

565

566

567 if (num_elements_.Get() <= max_num_committed_elements_) return;

570 range_of_path_.Commit();

571 num_elements_.SetAndCommit(pre_visit_.size());

572 }

573

574

576 auto [begin, end] = range_of_path_.GetCommitted(path);

577 return absl::MakeConstSpan(pre_visit_.data() + begin,

578 pre_visit_.data() + end);

579 }

580

581

582 absl::Span<const int64_t> PreVisits(int path) const {

583 auto [begin, end] = range_of_path_.Get(path);

584 return absl::MakeConstSpan(pre_visit_.data() + begin,

585 pre_visit_.data() + end);

586 }

587

588

590 auto [begin, end] = range_of_path_.Get(path);

591 return absl::MakeSpan(pre_visit_.data() + begin, pre_visit_.data() + end);

592 }

593

594

595

597 auto [begin, end] = range_of_path_.GetCommitted(path);

598 return absl::MakeConstSpan(post_visit_.data() + begin,

599 post_visit_.data() + end);

600 }

601

602

603 absl::Span<const int64_t> PostVisits(int path) const {

604 const auto [begin, end] = range_of_path_.Get(path);

605 return absl::MakeConstSpan(post_visit_.data() + begin,

606 post_visit_.data() + end);

607 }

608

609

611 const auto [begin, end] = range_of_path_.Get(path);

612 return absl::MakeSpan(post_visit_.data() + begin, post_visit_.data() + end);

613 }

614

615

616 int NumNodes(int path) const { return range_of_path_.Get(path).Size(); }

617

619 return absl::MakeConstSpan(range_of_path_.ChangedIndices());

620 }

621

623 return range_of_path_.HasChanged(path);

624 }

625

626 private:

627

628 std::vector<int64_t> pre_visit_;

629 std::vector<int64_t> post_visit_;

630

631 std::vector<int64_t> temp_int64s_;

632

633

635

636

637

638 const size_t max_num_committed_elements_;

639

641};

642

643}

644

645#endif

void Revert()

Definition routing_filter_committables.h:92

bool HasChanged(size_t index) const

Definition routing_filter_committables.h:121

CommittableArray(size_t num_elements, const T &value)

Definition routing_filter_committables.h:61

T Get(size_t index) const

Definition routing_filter_committables.h:70

void Set(size_t index, const T &value)

Definition routing_filter_committables.h:84

void SetAllAndCommit(const T &value)

Definition routing_filter_committables.h:108

void Commit()

Definition routing_filter_committables.h:100

T & GetMutable(size_t index)

Definition routing_filter_committables.h:77

T GetCommitted(size_t index) const

Definition routing_filter_committables.h:114

const std::vector< size_t > & ChangedIndices() const

Definition routing_filter_committables.h:125

size_t Size() const

Definition routing_filter_committables.h:65

const T & GetCommitted() const

Definition routing_filter_committables.h:39

const T & Get() const

Definition routing_filter_committables.h:38

void SetAndCommit(const T &value)

Definition routing_filter_committables.h:43

void Set(const T &value)

Definition routing_filter_committables.h:41

void Commit()

Definition routing_filter_committables.h:50

void Revert()

Definition routing_filter_committables.h:48

CommittableValue(const T &value)

Definition routing_filter_committables.h:35

absl::Span< const int64_t > CommittedTravels(int path) const

Definition routing_filter_committables.h:391

void Reset()

Definition routing_filter_committables.h:316

absl::Span< Interval > MutableCumuls(int path)

Definition routing_filter_committables.h:431

int NumNodes(int path) const

Definition routing_filter_committables.h:462

absl::Span< const int64_t > Travels(int path) const

Definition routing_filter_committables.h:398

absl::Span< const Interval > Cumuls(int path) const

Definition routing_filter_committables.h:425

absl::Span< const size_t > ChangedPaths() const

Definition routing_filter_committables.h:464

DimensionValues(int num_paths, int num_nodes)

Definition routing_filter_committables.h:211

absl::Span< const VehicleBreak > VehicleBreaks(int path) const

Definition routing_filter_committables.h:448

void MakePathFromNewNodes(int path)

Definition routing_filter_committables.h:299

void Revert()

Definition routing_filter_committables.h:328

absl::Span< const Interval > Transits(int path) const

Definition routing_filter_committables.h:373

void Commit()

Definition routing_filter_committables.h:342

absl::Span< const int > Nodes(int path) const

Definition routing_filter_committables.h:367

absl::Span< Interval > MutableTransits(int path)

Definition routing_filter_committables.h:382

Interval & MutableSpan(int path)

Definition routing_filter_committables.h:441

absl::Span< int64_t > MutableTravelSums(int path)

Definition routing_filter_committables.h:419

absl::Span< int64_t > MutableTravels(int path)

Definition routing_filter_committables.h:405

bool PathHasChanged(int path) const

Definition routing_filter_committables.h:468

std::vector< VehicleBreak > & MutableVehicleBreaks(int path)

Definition routing_filter_committables.h:456

Interval Span(int path) const

Definition routing_filter_committables.h:437

void PushNode(int node)

Definition routing_filter_committables.h:296

absl::Span< const int > CommittedNodes(int path) const

Definition routing_filter_committables.h:361

absl::Span< const int64_t > TravelSums(int path) const

Definition routing_filter_committables.h:412

void Reset()

Definition routing_filter_committables.h:543

absl::Span< const int64_t > PostVisits(int path) const

Definition routing_filter_committables.h:603

absl::Span< const int64_t > CommittedPostVisits(int path) const

Definition routing_filter_committables.h:596

void Revert()

Definition routing_filter_committables.h:551

PrePostVisitValues(int num_paths, int num_nodes)

Definition routing_filter_committables.h:516

absl::Span< int64_t > MutablePostVisits(int path)

Definition routing_filter_committables.h:610

absl::Span< const size_t > ChangedPaths() const

Definition routing_filter_committables.h:618

bool PathHasChanged(int path) const

Definition routing_filter_committables.h:622

DimensionValues::Interval Interval

Definition routing_filter_committables.h:524

int NumNodes(int path) const

Definition routing_filter_committables.h:616

void ChangePathSize(int path, int new_num_nodes)

Definition routing_filter_committables.h:527

absl::Span< int64_t > MutablePreVisits(int path)

Definition routing_filter_committables.h:589

void Commit()

Definition routing_filter_committables.h:561

absl::Span< const int64_t > CommittedPreVisits(int path) const

Definition routing_filter_committables.h:575

absl::Span< const int64_t > PreVisits(int path) const

Definition routing_filter_committables.h:582

int64_t CapAdd(int64_t x, int64_t y)

int64_t CapSub(int64_t x, int64_t y)

ClosedInterval::Iterator end(ClosedInterval interval)

bool PropagateTransitAndSpan(int path, DimensionValues &dimension_values)

void DefragmentRanges(std::vector< T > &mutable_input, CommittableArray< IndexRange > &ranges, std::vector< T > &temp_container)

Definition routing_filter_committables.h:158

ClosedInterval::Iterator begin(ClosedInterval interval)

int64_t min

Definition routing_filter_committables.h:226

static Interval AllIntegers()

Definition routing_filter_committables.h:278

Interval operator+(const Interval &other) const

Definition routing_filter_committables.h:259

bool IncreaseMin(int64_t lower_bound)

Definition routing_filter_committables.h:240

int64_t max

Definition routing_filter_committables.h:227

void Subtract(const Interval &other)

Definition routing_filter_committables.h:276

void Add(const Interval &other)

Definition routing_filter_committables.h:266

bool DecreaseMax(int64_t upper_bound)

Definition routing_filter_committables.h:246

bool operator==(const Interval &other) const

Definition routing_filter_committables.h:233

Interval operator-(const Interval &other) const

Definition routing_filter_committables.h:269

bool operator!=(const Interval &other) const

Definition routing_filter_committables.h:229

bool IntersectWith(const Interval &other)

Definition routing_filter_committables.h:252

bool IsEmpty() const

Definition routing_filter_committables.h:237

bool operator==(const VehicleBreak &other) const

Definition routing_filter_committables.h:289

Interval start

Definition routing_filter_committables.h:285

Interval is_performed

Definition routing_filter_committables.h:288

Interval duration

Definition routing_filter_committables.h:287

Interval end

Definition routing_filter_committables.h:286

bool operator==(const IndexRange &other) const

Definition routing_filter_committables.h:148

IndexRange(Index start, Index end)

size_t begin

Definition routing_filter_committables.h:145

size_t end

Definition routing_filter_committables.h:146

int Size() const

Definition routing_filter_committables.h:147