C++ Reference: Algorithms
Go to the documentation of this file.
14 #ifndef OR_TOOLS_ALGORITHMS_DENSE_DOUBLY_LINKED_LIST_H_
15 #define OR_TOOLS_ALGORITHMS_DENSE_DOUBLY_LINKED_LIST_H_
19 #include "ortools/base/logging.h"
37 int Size()
const {
return next_.size(); }
41 int Next(
int i)
const;
42 int Prev(
int i)
const;
48 std::vector<int> next_;
49 std::vector<int> prev_;
57 DCHECK_GE(next_[i], -1);
64 DCHECK_GE(prev_[i], -1);
69 const int prev =
Prev(i);
70 const int next =
Next(i);
71 if (prev >= 0) next_[prev] = next;
72 if (next >= 0) prev_[next] = prev;
73 if (DEBUG_MODE) next_[i] = prev_[i] = -2;
78 : next_(elements.size(), -2), prev_(elements.size(), -2) {
80 for (
const int e : elements) {
83 DCHECK_EQ(-2, prev_[e]) <<
"Duplicate element: " << e;
85 if (last >= 0) next_[last] = e;
88 if (!elements.empty()) next_[elements.back()] = -1;
90 for (
int p : prev_) DCHECK_NE(-2, p);
91 for (
int n : next_) DCHECK_NE(-2, n);
97 #endif // OR_TOOLS_ALGORITHMS_DENSE_DOUBLY_LINKED_LIST_H_
DenseDoublyLinkedList(const T &sorted_elements)