OR-Tools  8.2
util/permutation.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//
15// Classes for permuting indexable, ordered containers of data without
16// depending on that data to be accessible in any particular way. The
17// client needs to give us two things:
18// 1. a permutation to apply to some container(s) of data, and
19// 2. a description of how to move data around in the container(s).
20//
21// The permutation (1) comes to us in the form of an array argument to
22// PermutationApplier::Apply(), along with index values that tell us
23// where in that array the permutation of interest lies. Typically
24// those index values will span the entire array that describes the
25// permutation.
26//
27// Applying a permutation involves decomposing the permutation into
28// disjoint cycles and walking each element of the underlying data one
29// step around the unique cycle in which it participates. The
30// decomposition into disjoint cycles is done implicitly on the fly as
31// the code in PermutationApplier::Apply() advances through the array
32// describing the permutation. As an important piece of bookkeeping to
33// support the decomposition into cycles, the elements of the
34// permutation array typically get modified somehow to indicate which
35// ones have already been used.
36//
37// At first glance, it would seem that if the containers are
38// indexable, we don't need anything more complicated than just the
39// permutation and the container of data we want to permute; it would
40// seem we can just use the container's operator[] to retrieve and
41// assign elements within the container. Unfortunately it's not so
42// simple because the containers of interest can be indexable without
43// providing any consistent way of accessing their contents that
44// applies to all the containers of interest. For instance, if we
45// could insist that every indexable container must define an lvalue
46// operator[]() we could simply use that for the assignments we need
47// to do while walking around cycles of the permutation. But we cannot
48// insist on any such thing. To see why, consider the PackedArray
49// class template in ortools/util/packed_array.h
50// where operator[] is supplied for rvalues, but because each logical
51// array element is packed across potentially multiple instances of
52// the underlying data type that the C++ language knows about, there
53// is no way to have a C++ reference to an element of a
54// PackedArray. There are other such examples besides PackedArray,
55// too. This is the main reason we need a codified description (2) of
56// how to move data around in the indexable container. That
57// description comes to us via the PermutationApplier constructor's
58// argument which is a PermutationCycleHandler instance. Such an
59// object has three important methods defined: SetTempFromIndex(),
60// SetIndexFromIndex(), and SetIndexFromTemp(). Those methods embody
61// all we need to know about how to move data in the indexable
62// container(s) underlying the PermutationCycleHandler.
63//
64// Another reason we need the description (2) of how to move elements
65// around in the container(s) is that it is often important to permute
66// side-by-side containers of elements according to the same
67// permutation. This situation, too, is covered by defining a
68// PermutationCycleHandler that knows about multiple underlying
69// indexable containers.
70//
71// The above-mentioned PermutationCycleHandler methods embody
72// knowledge of how to assign elements. It happens that
73// PermutationCycleHandler is also a convenient place to embody the
74// knowledge of how to keep track of which permutation elements have
75// been consumed by the process of walking data around cycles. We
76// depend on the PermutationCycleHandler instance we're given to
77// define SetSeen() and Unseen() methods for that purpose.
78//
79// For the common case in which elements can be accessed using
80// operator[](), we provide the class template
81// ArrayIndexCycleHandler.
82
83#ifndef OR_TOOLS_UTIL_PERMUTATION_H_
84#define OR_TOOLS_UTIL_PERMUTATION_H_
85
87#include "ortools/base/macros.h"
88
89namespace operations_research {
90
91// Abstract base class template defining the interface needed by
92// PermutationApplier to handle a single cycle of a permutation.
93template <typename IndexType>
95 public:
96 // Sets the internal temporary storage from the given index in the
97 // underlying container(s).
98 virtual void SetTempFromIndex(IndexType source) = 0;
99
100 // Moves a data element one step along its cycle.
101 virtual void SetIndexFromIndex(IndexType source,
102 IndexType destination) const = 0;
103
104 // Sets a data element from the temporary.
105 virtual void SetIndexFromTemp(IndexType destination) const = 0;
106
107 // Marks an element of the permutation as handled by
108 // PermutationHandler::Apply(), meaning that we have read the
109 // corresponding value from the data to be permuted, and put that
110 // value somewhere (either in the temp or in its ultimate
111 // destination in the data.
112 //
113 // This method must be overridden in implementations where it is
114 // called. If an implementation doesn't call it, no need to
115 // override.
116 virtual void SetSeen(IndexType* unused_permutation_element) const {
117 LOG(FATAL) << "Base implementation of SetSeen() must not be called.";
118 }
119
120 // Returns true iff the given element of the permutation is unseen,
121 // meaning that it has not yet been handled by
122 // PermutationApplier::Apply().
123 //
124 // This method must be overridden in implementations where it is
125 // called. If an implementation doesn't call it, no need to
126 // override.
127 virtual bool Unseen(IndexType unused_permutation_element) const {
128 LOG(FATAL) << "Base implementation of Unseen() must not be called.";
129 return false;
130 }
131
133
134 protected:
136
137 private:
138 DISALLOW_COPY_AND_ASSIGN(PermutationCycleHandler);
139};
140
141// A generic cycle handler class for the common case in which the
142// object to be permuted is indexable with T& operator[](int), and the
143// permutation is represented by a mutable array of nonnegative
144// int-typed index values. To mark a permutation element as seen, we
145// replace it by its ones-complement value.
146template <typename DataType, typename IndexType>
148 public:
149 explicit ArrayIndexCycleHandler(DataType* data) : data_(data) {}
150
151 void SetTempFromIndex(IndexType source) override { temp_ = data_[source]; }
152 void SetIndexFromIndex(IndexType source,
153 IndexType destination) const override {
154 data_[destination] = data_[source];
155 }
156 void SetIndexFromTemp(IndexType destination) const override {
157 data_[destination] = temp_;
158 }
159 void SetSeen(IndexType* permutation_element) const override {
160 *permutation_element = -*permutation_element - 1;
161 }
162 bool Unseen(IndexType permutation_element) const override {
163 return permutation_element >= 0;
164 }
165
166 private:
167 // Pointer to the base of the array of data to be permuted.
168 DataType* data_;
169
170 // Temporary storage for the one extra element we need.
171 DataType temp_;
172
173 DISALLOW_COPY_AND_ASSIGN(ArrayIndexCycleHandler);
174};
175
176// Note that this template is not implemented in an especially
177// performance-sensitive way. In particular, it makes multiple virtual
178// method calls for each element of the permutation.
179template <typename IndexType>
181 public:
183 : cycle_handler_(cycle_handler) {}
184
185 void Apply(IndexType permutation[], int permutation_start,
186 int permutation_end) {
187 for (IndexType current = permutation_start; current < permutation_end;
188 ++current) {
189 IndexType next = permutation[current];
190 // cycle_start is only for debugging.
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);
198 current = next;
199 next = permutation[next];
200 cycle_handler_->SetSeen(&permutation[current]);
201 DCHECK(!cycle_handler_->Unseen(permutation[current]));
202 }
203 cycle_handler_->SetIndexFromTemp(current);
204 // Set current back to the start of this cycle.
205 current = next;
206 }
207 DCHECK_EQ(cycle_start, current);
208 }
209 }
210
211 private:
213
214 DISALLOW_COPY_AND_ASSIGN(PermutationApplier);
215};
216} // namespace operations_research
217#endif // OR_TOOLS_UTIL_PERMUTATION_H_
#define LOG(severity)
Definition: base/logging.h:420
#define DCHECK(condition)
Definition: base/logging.h:884
#define DCHECK_EQ(val1, val2)
Definition: base/logging.h:885
void SetIndexFromIndex(IndexType source, IndexType destination) const override
void SetIndexFromTemp(IndexType destination) const override
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 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
Block * next
const int FATAL
Definition: log_severity.h:32
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...