this repo has no description
dekker.one
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Christian Schulte <schulte@gecode.org>
5 *
6 * Copyright:
7 * Christian Schulte, 2002
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#include <algorithm>
35#include <climits>
36
37namespace Gecode { namespace Int { namespace Linear {
38
39 template<class View>
40 inline void
41 estimate(Term<View>* t, int n, int c, int& l, int &u) {
42 long long int min = c;
43 long long int max = c;
44 for (int i=0; i<n; i++) {
45 long long int a = t[i].a;
46 if (a > 0) {
47 min += a*t[i].x.min();
48 max += a*t[i].x.max();
49 } else {
50 max += a*t[i].x.min();
51 min += a*t[i].x.max();
52 }
53 }
54 if (min < Limits::min)
55 min = Limits::min;
56 if (min > Limits::max)
57 min = Limits::max;
58 l = static_cast<int>(min);
59 if (max < Limits::min)
60 max = Limits::min;
61 if (max > Limits::max)
62 max = Limits::max;
63 u = static_cast<int>(max);
64 }
65
66 /// Sort linear terms by view
67 template<class View>
68 class TermByView {
69 public:
70 forceinline bool
71 operator ()(const Term<View>& a, const Term<View>& b) {
72 return a.x < b.x;
73 }
74 };
75
76 /// Sort linear terms by coefficient size and original position
77 template<class View>
78 class TermBySizePos {
79 public:
80 forceinline bool
81 operator ()(const Term<View>& a, const Term<View>& b) {
82 assert((a.a > 0) && (b.a > 0));
83 return (a.a > b.a) || ((a.a == b.a) && (a.p < b.p));
84 }
85 };
86
87 /// Compute the greatest common divisor of \a a and \a b
88 inline int
89 gcd(int a, int b) {
90 if (b > a)
91 std::swap(a,b);
92 while (b > 0) {
93 int t = b; b = a % b; a = t;
94 }
95 return a;
96 }
97
98
99
100 /** \brief Normalize linear integer constraints
101 *
102 * \param t array of linear terms
103 * \param n size of array
104 * \param t_p array of linear terms over integers with positive coefficients
105 * \param n_p number of postive terms
106 * \param t_n array of linear terms over integers with negative coefficients
107 * \param n_n number of negative terms
108 * \param gcd greatest common divisor of all coefficients
109 *
110 * Replaces all negative coefficients by positive coefficients.
111 *
112 * - Variables occuring multiply in the term array are replaced
113 * by a single occurence: for example, \f$ax+bx\f$ becomes
114 * \f$(a+b)x\f$.
115 * - If in the above simplification the value for \f$(a+b)\f$ (or for
116 * \f$a\f$ and \f$b\f$) exceeds the limits for integers as
117 * defined in Limits::Int, an exception of type
118 * Int::NumericalOverflow is thrown.
119 * - Divides all coefficients by their greatest common divisor and
120 * returns the gcd \a g
121 *
122 * Returns true, if all coefficients are unit coefficients
123 */
124 template<class View>
125 inline bool
126 normalize(Term<View>* t, int &n,
127 Term<View>* &t_p, int &n_p,
128 Term<View>* &t_n, int &n_n,
129 int& g) {
130 // Number terms by position
131 for (int i=0; i<n; i++)
132 t[i].p = i;
133
134 /*
135 * Join coefficients for aliased variables:
136 *
137 */
138 {
139 // Group same variables
140 TermByView<View> tl;
141 Support::quicksort<Term<View>,TermByView<View>>(t,n,tl);
142
143 // Join adjacent variables
144 int i = 0;
145 int j = 0;
146 while (i < n) {
147 Limits::check(t[i].a,"Int::linear");
148 long long int a = t[i].a;
149 int p = t[i].p;
150 View x = t[i].x;
151 while ((++i < n) && (t[i].x == x)) {
152 a += t[i].a;
153 p = std::min(p,t[i].p);
154 Limits::check(a,"Int::linear");
155 }
156 if (a != 0) {
157 t[j].a = static_cast<int>(a); t[j].x = x; t[j].p = p; j++;
158 }
159 }
160 n = j;
161 }
162
163 /*
164 * Partition into positive/negative coefficents
165 *
166 */
167 if (n > 0) {
168 int i = 0;
169 int j = n-1;
170 while (true) {
171 while ((t[j].a < 0) && (--j >= 0)) ;
172 while ((t[i].a > 0) && (++i < n)) ;
173 if (j <= i) break;
174 std::swap(t[i],t[j]);
175 }
176 t_p = t; n_p = i;
177 t_n = t+n_p; n_n = n-n_p;
178 } else {
179 t_p = t; n_p = 0;
180 t_n = t; n_n = 0;
181 }
182
183 /*
184 * Make all coefficients positive
185 *
186 */
187 for (int i=0; i<n_n; i++)
188 t_n[i].a = -t_n[i].a;
189
190 /*
191 * Sort terms into canonical order (to avoid indeterminstic order)
192 */
193 {
194 TermBySizePos<View> tl;
195 Support::quicksort<Term<View>,TermBySizePos<View>>(t_p,n_p,tl);
196 Support::quicksort<Term<View>,TermBySizePos<View>>(t_n,n_n,tl);
197 }
198
199 /*
200 * Compute greatest common divisor
201 *
202 */
203 if ((n > 0) && (g > 0)) {
204 g = t[0].a;
205 for (int i=1; (g > 1) && (i < n); i++)
206 g = gcd(t[i].a,g);
207 if (g > 1)
208 for (int i=n; i--; )
209 t[i].a /= g;
210 } else {
211 g = 1;
212 }
213
214 /*
215 * Test for unit coefficients only
216 *
217 */
218 for (int i=0; i<n; i++)
219 if (t[i].a != 1)
220 return false;
221 return true;
222 }
223
224}}}
225
226// STATISTICS: int-post
227