14#ifndef OR_TOOLS_UTIL_MONOID_OPERATION_TREE_H_
15#define OR_TOOLS_UTIL_MONOID_OPERATION_TREE_H_
20#include "absl/strings/str_format.h"
62 const T&
result()
const {
return *result_; }
65 void Reset(
int argument_index);
68 void Set(
int argument_index,
const T& argument);
75 return nodes_[PositionOfLeaf(argument_index)];
79 template <
class Diver>
88 static int ComputeLeafOffset(
int size);
92 static int ComputeNumberOfNodes(
int leaf_offset);
96 void ComputeAbove(
int position);
99 void Compute(
int position);
102 int PositionOfLeaf(
int index)
const {
return leaf_offset_ +
index; }
105 bool IsLeaf(
int position)
const {
return position >= leaf_offset_; }
108 int ArgumentIndexOfLeafPosition(
int position)
const {
110 return position - leaf_offset_;
113 template <
class Diver>
114 void DiveInTree(
int position, Diver* diver)
const;
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; }
125 const int leaf_offset_;
128 const int num_nodes_;
131 std::vector<T> nodes_;
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;
149 return std::max(1, smallest_pow_two_not_less_than_size - 1);
153int MonoidOperationTree<T>::ComputeNumberOfNodes(
int leaf_offset) {
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;
165 leaf_offset_(ComputeLeafOffset(size)),
166 num_nodes_(ComputeNumberOfNodes(leaf_offset_)),
167 nodes_(num_nodes_, T()),
168 result_(&(nodes_[0])) {}
172 const int size = nodes_.size();
173 nodes_.assign(size, T());
178 Set(argument_index, T());
184 const int position = leaf_offset_ + argument_index;
185 nodes_[position] = argument;
186 ComputeAbove(position);
191 int pos = father(position);
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);
210 for (
int i = 0; i < num_nodes_; ++i) {
211 if (((i + 1) & i) == 0) {
213 absl::StrAppendFormat(&out,
"-------------- Layer %d ---------------\n",
217 absl::StrAppendFormat(&out,
"Position %d: %s\n", i,
218 nodes_[i].DebugString());
224template <
class Diver>
227 if (IsLeaf(position)) {
228 const int index = ArgumentIndexOfLeafPosition(position);
229 const T& argument = nodes_[position];
230 diver->OnArgumentReached(
index, argument);
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)) {
237 DiveInTree(left(position), diver);
239 diver->OnComeBackFromLeft(current, left_child, right_child);
242 DiveInTree(right(position), diver);
244 diver->OnComeBackFromRight(current, left_child, right_child);
#define CHECK_LT(val1, val2)
#define DCHECK_GE(val1, val2)
#define DCHECK(condition)
#define DCHECK_EQ(val1, val2)
MonoidOperationTree(int size)
void Set(int argument_index, const T &argument)
void Reset(int argument_index)
std::string DebugString() const
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...