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"
22#include "ortools/base/macros.h"
23
24namespace 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.
55template <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
143template <class T>
144int 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
152template <class T>
153int 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
162template <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
170template <class T>
172 const int size = nodes_.size();
173 nodes_.assign(size, T());
174}
175
176template <class T>
177void MonoidOperationTree<T>::Reset(int argument_index) {
178 Set(argument_index, T());
179}
180
181template <class T>
182void 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
189template <class T>
190void 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
199template <class T>
200void 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
206template <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
223template <class T>
224template <class Diver>
225void 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)
void DiveInTree(Diver *const diver) const
const T & GetOperand(int argument_index) const
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
int index
Definition: pack.cc:508