This file is indexed.

/usr/include/gecode/int/distinct.hh is in libgecode-dev 3.7.1-3.

This file is owned by root:root, with mode 0o644.

The actual contents of the file can be viewed below.

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
 *  Main authors:
 *     Christian Schulte <schulte@gecode.org>
 *     Guido Tack <tack@gecode.org>
 *
 *  Contributing authors:
 *     Gabor Szokoli <szokoli@gecode.org>
 *
 *  Copyright:
 *     Christian Schulte, 2002
 *     Guido Tack, 2004
 *     Gabor Szokoli, 2003
 *
 *  Last modified:
 *     $Date: 2011-10-06 17:27:42 +0200 (Thu, 06 Oct 2011) $ by $Author: schulte $
 *     $Revision: 12423 $
 *
 *  This file is part of Gecode, the generic constraint
 *  development environment:
 *     http://www.gecode.org
 *
 *  Permission is hereby granted, free of charge, to any person obtaining
 *  a copy of this software and associated documentation files (the
 *  "Software"), to deal in the Software without restriction, including
 *  without limitation the rights to use, copy, modify, merge, publish,
 *  distribute, sublicense, and/or sell copies of the Software, and to
 *  permit persons to whom the Software is furnished to do so, subject to
 *  the following conditions:
 *
 *  The above copyright notice and this permission notice shall be
 *  included in all copies or substantial portions of the Software.
 *
 *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
 *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
 *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
 *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
 *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 *
 */

#ifndef __GECODE_INT_DISTINCT_HH__
#define __GECODE_INT_DISTINCT_HH__

#include <gecode/int.hh>

#include <gecode/int/view-val-graph.hh>
#include <gecode/int/rel.hh>

/**
 * \namespace Gecode::Int::Distinct
 * \brief %Distinct propagators
 */

namespace Gecode { namespace Int { namespace Distinct {

  /**
   * \brief Naive value distinct propagator
   *
   * Eliminates values of assigned views of type \a View.
   *
   * Requires \code #include <gecode/int/distinct.hh> \endcode
   * \ingroup FuncIntProp
   */
  template<class View>
  class Val : public NaryPropagator<View,PC_INT_VAL> {
  protected:
    using NaryPropagator<View,PC_INT_VAL>::x;

    /// Constructor for posting
    Val(Home home, ViewArray<View>& x);
    /// Constructor for cloning \a p
    Val(Space& home, bool share, Val<View>& p);
  public:
    /// Copy propagator during cloning
    virtual Actor*     copy(Space& home, bool share);
    /// Perform propagation
    virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
    /// Post propagator for view array \a x
    static ExecStatus post(Home home, ViewArray<View>& x);
  };

  /**
   * \brief Eliminate singletons by naive value propagation
   *
   * This is actually the propagation algorithm for Distinct::Val.
   * It is available as separate function as it is reused for
   * both bounds consistent and domain consistent distinct
   * propagators.
   *
   * If \a complete is true, computes fixpoint, otherwise might not
   * compute fixpoint. This can be helpful when used together with
   * bounds or domain propagation to protect from pathological cases
   * which can be handled more efficiently with bounds propagation.
   */
  template<class View, bool complete>
  ExecStatus prop_val(Space& home, ViewArray<View>&);



  /**
   * \brief Bounds consistent distinct propagator
   *
   * The propagator uses staging: first it uses naive value-based
   * propagation and only then uses bounds consistent propagation.
   * Due to using naive value-based propagation, the propagator
   * might actually achieve stronger consistency than just
   * bounds consistency.
   *
   * The algorithm is taken from:
   *        A. Lopez-Ortiz, C.-G. Quimper, J. Tromp, and P. van Beek.
   *        A fast and simple algorithm for bounds consistency of the
   *        alldifferent constraint. IJCAI-2003.
   *
   * This implementation uses the code that is provided by
   * Peter Van Beek:
   *   http://ai.uwaterloo.ca/~vanbeek/software/software.html
   * The code (originally by John Tromp) here has only been slightly modified
   * to fit %Gecode (taking idempotent/non-idempotent propagation into account)
   * and uses a more efficient layout of datastructures (keeping the number
   * of different arrays small).
   *
   * Requires \code #include <gecode/int/distinct.hh> \endcode
   * \ingroup FuncIntProp
   */
  template<class View>
  class Bnd : public Propagator {
  protected:
    /// Views on which to perform bounds-propagation
    ViewArray<View> x;
    /// Views on which to perform value-propagation (subset of \c x)
    ViewArray<View> y;
    /// Minimum (approximation) of view in \a x
    int min_x;
    /// Maximum (approximation) of view in \a x
    int max_x;
    /// Constructor for posting
    Bnd(Home home, ViewArray<View>& x);
    /// Constructor for cloning \a p
    Bnd(Space& home, bool share, Bnd<View>& p);
  public:
    /// Post propagator for view array \a x
    static ExecStatus post(Home home, ViewArray<View>& x);
    /// Perform propagation
    virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
    /**
     * \brief Cost function
     *
     * If in stage for naive value propagation, the cost is
     * low linear. Otherwise it is low quadratic.
     */
    virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
    /// Copy propagator during cloning
    virtual Actor* copy(Space& home, bool share);
    /// Destructor
    virtual size_t dispose(Space& home);
  };

  /**
   * \brief Perform bounds consistent distinct propagation
   *
   * This is actually the propagation algorithm for Distinct::Bnd.
   * It is available as separate function as it is reused for
   * both bounds consistent and domain consistent distinct
   * propagators.
   */
  template<class View>
  ExecStatus prop_bnd(Space& home, ViewArray<View>& x, int& min_x, int& max_x);

  /**
   * \brief Perform bounds consistent distinct propagation
   *
   * This is actually the propagation algorithm for Distinct::Bnd.
   * It is available as separate function as it is reused for
   * both bounds consistent and domain consistent distinct
   * propagators.
   */
  template<class View>
  ExecStatus prop_bnd(Space& home, ViewArray<View>& x);


  /// View-value graph for propagation
  template<class View>
  class Graph : public ViewValGraph::Graph<View> {
  public:
    using ViewValGraph::Graph<View>::view;
    using ViewValGraph::Graph<View>::n_view;
    using ViewValGraph::Graph<View>::val;
    using ViewValGraph::Graph<View>::n_val;
    using ViewValGraph::Graph<View>::count;
    using ViewValGraph::Graph<View>::scc;
    using ViewValGraph::Graph<View>::match;
    /// Construct graph as not yet initialized
    Graph(void);
    /// Initialize graph
    ExecStatus init(Space& home, ViewArray<View>& x);
    /// Mark edges in graph, return true if pruning is at all possible
    bool mark(Space& home);
    /// Prune unmarked edges, \a assigned is true if a view got assigned
    ExecStatus prune(Space& home, bool& assigned);
    /// Synchronize graph with new view domains
    bool sync(Space& home);
  };

  /**
   * \brief Propagation controller for domain consistent distinct
   *
   * The propagation controller provides convenient access to
   * performing incremental domain consistent distinct propagation
   * so that the routines can be reused easily.
   *
   * Requires \code #include <gecode/int/distinct.hh> \endcode
   * \ingroup FuncIntProp
   */
  template<class View>
  class DomCtrl {
  protected:
    /// Propagation is performed on a view-value graph
    Graph<View> g;
  public:
    /// Initialize with non-initialized view-value graph
    DomCtrl(void);
    /// Check whether a view-value graph is available
    bool available(void);
    /// Initialize view-value graph for views \a x
    ExecStatus init(Space& home, ViewArray<View>& x);
    /// Synchronize available view-value graph
    ExecStatus sync(Space& home);
    /// Perform propagation, \a assigned is true if a view gets assigned
    ExecStatus propagate(Space& home, bool& assigned);
  };

  /**
   * \brief Domain consistent distinct propagator
   *
   * The propagator uses staging: first it uses naive value-based
   * propagation and only then uses domain consistent propagation.
   *
   * The algorithm is taken from:
   *    Jean-Charles RĂ©gin, A filtering algorithm for constraints
   *    of difference in CSPs, Proceedings of the Twelfth National
   *    Conference on Artificial Intelligence, pages 362--367.
   *    Seattle, WA, USA, 1994.
   *
   * Requires \code #include <gecode/int/distinct.hh> \endcode
   * \ingroup FuncIntProp
   */
  template<class View>
  class Dom : public NaryPropagator<View,PC_INT_DOM> {
  protected:
    using NaryPropagator<View,PC_INT_DOM>::x;
    /// Propagation controller
    DomCtrl<View> dc;
    /// Constructor for cloning \a p
    Dom(Space& home, bool share, Dom<View>& p);
    /// Constructor for posting
    Dom(Home home, ViewArray<View>& x);
  public:
    /// Perform propagation
    virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
    /**
     * \brief Cost function
     *
     * If in stage for naive value propagation, the cost is
     * low linear. Otherwise it is high quadratic.
     */
    virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
    /// Copy propagator during cloning
    virtual Actor* copy(Space& home, bool share);
    /// Post propagator for views \a x
    static ExecStatus post(Home home, ViewArray<View>& x);
  };

  /**
   * \brief Ternary domain consistent distinct propagator
   *
   * Requires \code #include <gecode/int/distinct.hh> \endcode
   * \ingroup FuncIntProp
   */
  template<class View>
  class TerDom : public TernaryPropagator<View,PC_INT_DOM> {
  protected:
    using TernaryPropagator<View,PC_INT_DOM>::x0;
    using TernaryPropagator<View,PC_INT_DOM>::x1;
    using TernaryPropagator<View,PC_INT_DOM>::x2;

    /// Constructor for cloning \a p
    TerDom(Space& home, bool share, TerDom<View>& p);
    /// Constructor for posting
    TerDom(Home home, View x0, View x1, View x2);
  public:
    /// Perform propagation
    virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
    /// Copy propagator during cloning
    virtual Actor* copy(Space& home, bool share);
    /// Post propagator for views \a x
    static  ExecStatus post(Home home, View x0, View x1, View x2);
  };

}}}

#include <gecode/int/distinct/val.hpp>
#include <gecode/int/distinct/bnd.hpp>
#include <gecode/int/distinct/ter-dom.hpp>
#include <gecode/int/distinct/graph.hpp>
#include <gecode/int/distinct/dom-ctrl.hpp>
#include <gecode/int/distinct/dom.hpp>

#endif

// STATISTICS: int-prop