83#ifndef OR_TOOLS_UTIL_PERMUTATION_H_
84#define OR_TOOLS_UTIL_PERMUTATION_H_
93template <
typename IndexType>
102 IndexType destination)
const = 0;
116 virtual void SetSeen(IndexType* unused_permutation_element)
const {
117 LOG(
FATAL) <<
"Base implementation of SetSeen() must not be called.";
127 virtual bool Unseen(IndexType unused_permutation_element)
const {
128 LOG(
FATAL) <<
"Base implementation of Unseen() must not be called.";
146template <
typename DataType,
typename IndexType>
153 IndexType destination)
const override {
154 data_[destination] = data_[source];
157 data_[destination] = temp_;
159 void SetSeen(IndexType* permutation_element)
const override {
160 *permutation_element = -*permutation_element - 1;
162 bool Unseen(IndexType permutation_element)
const override {
163 return permutation_element >= 0;
179template <
typename IndexType>
183 : cycle_handler_(cycle_handler) {}
185 void Apply(IndexType permutation[],
int permutation_start,
186 int permutation_end) {
187 for (IndexType current = permutation_start; current < permutation_end;
189 IndexType
next = permutation[current];
191 const IndexType cycle_start = current;
192 if (cycle_handler_->Unseen(
next)) {
193 cycle_handler_->SetSeen(&permutation[current]);
194 DCHECK(!cycle_handler_->Unseen(permutation[current]));
195 cycle_handler_->SetTempFromIndex(current);
196 while (cycle_handler_->Unseen(permutation[
next])) {
197 cycle_handler_->SetIndexFromIndex(
next, current);
200 cycle_handler_->SetSeen(&permutation[current]);
201 DCHECK(!cycle_handler_->Unseen(permutation[current]));
203 cycle_handler_->SetIndexFromTemp(current);
#define DCHECK(condition)
#define DCHECK_EQ(val1, val2)
void SetIndexFromIndex(IndexType source, IndexType destination) const override
void SetIndexFromTemp(IndexType destination) const override
ArrayIndexCycleHandler(DataType *data)
bool Unseen(IndexType permutation_element) const override
void SetTempFromIndex(IndexType source) override
void SetSeen(IndexType *permutation_element) const override
PermutationApplier(PermutationCycleHandler< IndexType > *cycle_handler)
void Apply(IndexType permutation[], int permutation_start, int permutation_end)
virtual void SetIndexFromTemp(IndexType destination) const =0
virtual ~PermutationCycleHandler()
virtual bool Unseen(IndexType unused_permutation_element) const
virtual void SetTempFromIndex(IndexType source)=0
virtual void SetSeen(IndexType *unused_permutation_element) const
virtual void SetIndexFromIndex(IndexType source, IndexType destination) const =0
PermutationCycleHandler()
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...