OR-Tools  8.2
monoid_operation_tree.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_UTIL_MONOID_OPERATION_TREE_H_
15 #define OR_TOOLS_UTIL_MONOID_OPERATION_TREE_H_
16 
17 #include <algorithm>
18 #include <string>
19 
20 #include "absl/strings/str_format.h"
21 #include "ortools/base/logging.h"
22 #include "ortools/base/macros.h"
23 
24 namespace operations_research {
25 
26 // A monoid is an algebraic structure consisting of a set S with an associative
27 // binary operation * :S x S -> S that has an identity element.
28 // Associative means a*(b*c) = (a*b)*c for all a,b,c in S.
29 // An identity element is an element e in S such that for all a in S,
30 // e*a = a*e = a.
31 // See http://en.wikipedia.org/wiki/Monoid for more details.
32 //
33 // A MonoidOperationTree is a data structure that maintains a product
34 // a_1 * a_2 * ... * a_n for a given (fixed) n, and that supports the
35 // following functions:
36 // - Setting the k-th operand to a given value in O(log n) calls to the *
37 // operation
38 // - Querying the result in O(1)
39 //
40 // Note that the monoid is not required to be commutative.
41 //
42 // The parameter class T represents an element of the set S.
43 // It must:
44 // * Have a public no-argument constructor producing the identity element.
45 // * Have a = operator method that sets its value to the given one.
46 // * Have a Compute(const T& left, const T& right) method that sets its value
47 // to the result of the binary operation for the two given operands.
48 // * Have a string DebugString() const method.
49 //
50 // Possible use cases are:
51 // * Maintain a sum or a product of doubles, with a guarantee that the queried
52 // result is independent of the order of past numerical issues
53 // * Maintain a product of identically sized square matrices, which is an
54 // example of use with non-commutative operations.
55 template <class T>
57  public:
58  // Constructs a MonoidOperationTree able to store 'size' operands.
59  explicit MonoidOperationTree(int size);
60 
61  // Returns the root of the tree, containing the result of the operation.
62  const T& result() const { return *result_; }
63 
64  // Resets the argument of given index.
65  void Reset(int argument_index);
66 
67  // Sets the argument of given index.
68  void Set(int argument_index, const T& argument);
69 
70  // Resets all arguments.
71  void Clear();
72 
73  // Returns the leaf node corresponding to the given argument index.
74  const T& GetOperand(int argument_index) const {
75  return nodes_[PositionOfLeaf(argument_index)];
76  }
77 
78  // Dive down a branch of the operation tree, and then come back up.
79  template <class Diver>
80  void DiveInTree(Diver* const diver) const {
81  DiveInTree(0, diver);
82  }
83 
84  std::string DebugString() const;
85 
86  private:
87  // Computes the index of the first leaf for the given size.
88  static int ComputeLeafOffset(int size);
89 
90  // Computes the total number of nodes we need to store non-leaf nodes and
91  // leaf nodes.
92  static int ComputeNumberOfNodes(int leaf_offset);
93 
94  // Computes the whole path from the node of given position up to the root,
95  // excluding the bottom node.
96  void ComputeAbove(int position);
97 
98  // Computes the node of given position, and no other.
99  void Compute(int position);
100 
101  // Returns the position of the leaf node of given index.
102  int PositionOfLeaf(int index) const { return leaf_offset_ + index; }
103 
104  // Returns true if the node of given position is a leaf.
105  bool IsLeaf(int position) const { return position >= leaf_offset_; }
106 
107  // Returns the index of the argument stored in the node of given position.
108  int ArgumentIndexOfLeafPosition(int position) const {
109  DCHECK(IsLeaf(position));
110  return position - leaf_offset_;
111  }
112 
113  template <class Diver>
114  void DiveInTree(int position, Diver* diver) const;
115 
116  static int father(int pos) { return (pos - 1) >> 1; }
117  static int left(int pos) { return (pos << 1) + 1; }
118  static int right(int pos) { return (pos + 1) << 1; }
119 
120  // The number of arguments that can be stored in this tree. That is, the
121  // number of used leaves. (There may be unused leaves, too)
122  const int size_;
123 
124  // The index of the first leaf.
125  const int leaf_offset_;
126 
127  // Number of nodes, both non-leaves and leaves.
128  const int num_nodes_;
129 
130  // All the nodes, both non-leaves and leaves.
131  std::vector<T> nodes_;
132 
133  // A pointer to the root node
134  T const* result_;
135 
136  DISALLOW_COPY_AND_ASSIGN(MonoidOperationTree);
137 };
138 
139 // --------------------------------------------------------------------- //
140 // Implementation
141 // --------------------------------------------------------------------- //
142 
143 template <class T>
144 int MonoidOperationTree<T>::ComputeLeafOffset(int size) {
145  int smallest_pow_two_not_less_than_size = 1;
146  while (smallest_pow_two_not_less_than_size < size) {
147  smallest_pow_two_not_less_than_size <<= 1;
148  }
149  return std::max(1, smallest_pow_two_not_less_than_size - 1);
150 }
151 
152 template <class T>
153 int MonoidOperationTree<T>::ComputeNumberOfNodes(int leaf_offset) {
154  // leaf_offset should be a power of 2 minus 1.
155  DCHECK_EQ(0, (leaf_offset) & (leaf_offset + 1));
156  const int num_leaves = leaf_offset + 1;
157  const int num_nodes = leaf_offset + num_leaves;
158  DCHECK_GE(num_nodes, 3); // We need at least the root and its 2 children
159  return num_nodes;
160 }
161 
162 template <class T>
164  : size_(size),
165  leaf_offset_(ComputeLeafOffset(size)),
166  num_nodes_(ComputeNumberOfNodes(leaf_offset_)),
167  nodes_(num_nodes_, T()),
168  result_(&(nodes_[0])) {}
169 
170 template <class T>
172  const int size = nodes_.size();
173  nodes_.assign(size, T());
174 }
175 
176 template <class T>
177 void MonoidOperationTree<T>::Reset(int argument_index) {
178  Set(argument_index, T());
179 }
180 
181 template <class T>
182 void MonoidOperationTree<T>::Set(int argument_index, const T& argument) {
183  CHECK_LT(argument_index, size_);
184  const int position = leaf_offset_ + argument_index;
185  nodes_[position] = argument;
186  ComputeAbove(position);
187 }
188 
189 template <class T>
190 void MonoidOperationTree<T>::ComputeAbove(int position) {
191  int pos = father(position);
192  while (pos > 0) {
193  Compute(pos);
194  pos = father(pos);
195  }
196  Compute(0);
197 }
198 
199 template <class T>
200 void MonoidOperationTree<T>::Compute(int position) {
201  const T& left_child = nodes_[left(position)];
202  const T& right_child = nodes_[right(position)];
203  nodes_[position].Compute(left_child, right_child);
204 }
205 
206 template <class T>
208  std::string out;
209  int layer = 0;
210  for (int i = 0; i < num_nodes_; ++i) {
211  if (((i + 1) & i) == 0) {
212  // New layer
213  absl::StrAppendFormat(&out, "-------------- Layer %d ---------------\n",
214  layer);
215  ++layer;
216  }
217  absl::StrAppendFormat(&out, "Position %d: %s\n", i,
218  nodes_[i].DebugString());
219  }
220  return out;
221 }
222 
223 template <class T>
224 template <class Diver>
225 void MonoidOperationTree<T>::DiveInTree(int position, Diver* diver) const {
226  // Are we at a leaf?
227  if (IsLeaf(position)) {
228  const int index = ArgumentIndexOfLeafPosition(position);
229  const T& argument = nodes_[position];
230  diver->OnArgumentReached(index, argument);
231  } else {
232  const T& current = nodes_[position];
233  const T& left_child = nodes_[left(position)];
234  const T& right_child = nodes_[right(position)];
235  if (diver->ChooseGoLeft(current, left_child, right_child)) {
236  // Go left
237  DiveInTree(left(position), diver);
238  // Come back up
239  diver->OnComeBackFromLeft(current, left_child, right_child);
240  } else {
241  // Go right
242  DiveInTree(right(position), diver);
243  // Come back up
244  diver->OnComeBackFromRight(current, left_child, right_child);
245  }
246  }
247 }
248 
249 } // namespace operations_research
250 
251 #endif // OR_TOOLS_UTIL_MONOID_OPERATION_TREE_H_
int64 max
Definition: alldiff_cst.cc:139
#define CHECK_LT(val1, val2)
Definition: base/logging.h:700
#define DCHECK_GE(val1, val2)
Definition: base/logging.h:889
#define DCHECK(condition)
Definition: base/logging.h:884
#define DCHECK_EQ(val1, val2)
Definition: base/logging.h:885
void Set(int argument_index, const T &argument)
const T & GetOperand(int argument_index) const
void DiveInTree(Diver *const diver) const
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
int index
Definition: pack.cc:508