this repo has no description
dekker.one
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Patrick Pekczynski <pekczynski@ps.uni-sb.de>
5 *
6 * Copyright:
7 * Patrick Pekczynski, 2004
8 *
9 * This file is part of Gecode, the generic constraint
10 * development environment:
11 * http://www.gecode.org
12 *
13 * Permission is hereby granted, free of charge, to any person obtaining
14 * a copy of this software and associated documentation files (the
15 * "Software"), to deal in the Software without restriction, including
16 * without limitation the rights to use, copy, modify, merge, publish,
17 * distribute, sublicense, and/or sell copies of the Software, and to
18 * permit persons to whom the Software is furnished to do so, subject to
19 * the following conditions:
20 *
21 * The above copyright notice and this permission notice shall be
22 * included in all copies or substantial portions of the Software.
23 *
24 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31 *
32 *
33 */
34
35#ifndef GECODE_INT_SORTED_HH
36#define GECODE_INT_SORTED_HH
37
38#include <gecode/int.hh>
39
40/**
41 * \namespace Gecode::Int::Sorted
42 * \brief %Sorted propagators
43 */
44
45namespace Gecode { namespace Int { namespace Sorted {
46
47 /**
48 * \brief Bounds consistent sortedness propagator
49 *
50 * The algorithm is taken from: Sven Thiel, Efficient Algorithms
51 * for Constraint Propagation and for Processing Tree Descriptions,
52 * PhD thesis, Universität des Saarlandes, Germany, 2004, pages 39-59.
53 *
54 * Requires \code #include <gecode/int/sorted.hh> \endcode
55 * \ingroup FuncIntProp
56 */
57
58 template<class View, bool Perm>
59 class Sorted : public Propagator {
60 protected:
61 /// Views to be sorted
62 ViewArray<View> x;
63 /// Views denoting the sorted version of \a x
64 ViewArray<View> y;
65 /// Permutation variables (none, if Perm is false)
66 ViewArray<View> z;
67 /// Original \a y array
68 ViewArray<View> w;
69 /// connection to dropped view
70 int reachable;
71 /// Constructor for posting
72 Sorted(Home home,
73 ViewArray<View>& x, ViewArray<View>& y, ViewArray<View>& z);
74 /// Constructor for cloning
75 Sorted(Space& home, Sorted<View,Perm>& p);
76 public:
77 /// Delete propagator and return its size
78 virtual size_t dispose(Space& home);
79 /// Copy propagator during cloning
80 virtual Actor* copy(Space& home);
81 /// Cost function returning low linear
82 virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
83 /// Schedule function
84 virtual void reschedule(Space& home);
85 /// Perform propagation
86 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
87 /// Post propagator for views \a x, \a y, and \a z
88 static ExecStatus post(Home home, ViewArray<View>& x, ViewArray<View>& y,
89 ViewArray<View>& z);
90 };
91
92
93}}}
94
95#include <gecode/int/sorted/sortsup.hpp>
96#include <gecode/int/sorted/order.hpp>
97#include <gecode/int/sorted/matching.hpp>
98#include <gecode/int/sorted/narrowing.hpp>
99#include <gecode/int/sorted/propagate.hpp>
100
101#endif
102
103
104// STATISTICS: int-prop
105