C++ Reference

C++ Reference: Algorithms

dense_doubly_linked_list.h
Go to the documentation of this file.
1 // Copyright 2010-2018 Google LLC
2 // Licensed under the Apache License, Version 2.0 (the "License");
3 // you may not use this file except in compliance with the License.
4 // You may obtain a copy of the License at
5 //
6 // http://www.apache.org/licenses/LICENSE-2.0
7 //
8 // Unless required by applicable law or agreed to in writing, software
9 // distributed under the License is distributed on an "AS IS" BASIS,
10 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11 // See the License for the specific language governing permissions and
12 // limitations under the License.
13 
14 #ifndef OR_TOOLS_ALGORITHMS_DENSE_DOUBLY_LINKED_LIST_H_
15 #define OR_TOOLS_ALGORITHMS_DENSE_DOUBLY_LINKED_LIST_H_
16 
17 #include <vector>
18 
19 #include "ortools/base/logging.h"
20 
22 
23 // Specialized doubly-linked list that initially holds [0..n-1] in an arbitrary
24 // (user-specified) and fixed order.
25 // It then supports O(1) removal and access to the next and previous element of
26 // a given (non-removed) element.
27 //
28 // It is very fast and compact: it uses exactly 8*n bytes of memory.
30  public:
31  // You can construct a DenseDoublyLinkedList with any range-iterable class
32  // that also has a size() method. The order of the elements is given by the
33  // user and will never change (modulo the removal of elements).
34  template <class T>
35  explicit DenseDoublyLinkedList(const T& sorted_elements);
36 
37  int Size() const { return next_.size(); }
38 
39  // Next() (resp. Prev()) must be called on elements that haven't yet been
40  // removed. They will return -1 if called on the last (resp. first) element.
41  int Next(int i) const;
42  int Prev(int i) const;
43 
44  // You must not call Remove() twice with the same element.
45  void Remove(int i);
46 
47  private:
48  std::vector<int> next_;
49  std::vector<int> prev_;
50 };
51 
52 // Inline implementations (forced inline for the speed).
53 
54 inline int DenseDoublyLinkedList::Next(int i) const {
55  DCHECK_GE(i, 0);
56  DCHECK_LT(i, Size());
57  DCHECK_GE(next_[i], -1);
58  return next_[i];
59 }
60 
61 inline int DenseDoublyLinkedList::Prev(int i) const {
62  DCHECK_GE(i, 0);
63  DCHECK_LT(i, Size());
64  DCHECK_GE(prev_[i], -1);
65  return prev_[i];
66 }
67 
68 inline void DenseDoublyLinkedList::Remove(int i) {
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; // To catch bugs.
74 }
75 
76 template <class T>
78  : next_(elements.size(), -2), prev_(elements.size(), -2) {
79  int last = -1;
80  for (const int e : elements) {
81  DCHECK_GE(e, 0);
82  DCHECK_LE(e, Size());
83  DCHECK_EQ(-2, prev_[e]) << "Duplicate element: " << e;
84  prev_[e] = last;
85  if (last >= 0) next_[last] = e;
86  last = e;
87  }
88  if (!elements.empty()) next_[elements.back()] = -1;
89  if (DEBUG_MODE) {
90  for (int p : prev_) DCHECK_NE(-2, p);
91  for (int n : next_) DCHECK_NE(-2, n);
92  }
93 }
94 
95 } // namespace operations_research
96 
97 #endif // OR_TOOLS_ALGORITHMS_DENSE_DOUBLY_LINKED_LIST_H_