Generated on Fri Oct 19 11:25:03 2018 for Gecode by doxygen 1.6.3

post.hpp

Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Christian Schulte <schulte@gecode.org>
00005  *
00006  *  Copyright:
00007  *     Christian Schulte, 2002
00008  *
00009  *  This file is part of Gecode, the generic constraint
00010  *  development environment:
00011  *     http://www.gecode.org
00012  *
00013  *  Permission is hereby granted, free of charge, to any person obtaining
00014  *  a copy of this software and associated documentation files (the
00015  *  "Software"), to deal in the Software without restriction, including
00016  *  without limitation the rights to use, copy, modify, merge, publish,
00017  *  distribute, sublicense, and/or sell copies of the Software, and to
00018  *  permit persons to whom the Software is furnished to do so, subject to
00019  *  the following conditions:
00020  *
00021  *  The above copyright notice and this permission notice shall be
00022  *  included in all copies or substantial portions of the Software.
00023  *
00024  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00025  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00026  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00027  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00028  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00029  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00030  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00031  *
00032  */
00033 
00034 #include <algorithm>
00035 #include <climits>
00036 
00037 namespace Gecode { namespace Int { namespace Linear {
00038 
00039   template<class View>
00040   inline void
00041   estimate(Term<View>* t, int n, int c, int& l, int &u) {
00042     long long int min = c;
00043     long long int max = c;
00044     for (int i=0; i<n; i++) {
00045       long long int a = t[i].a;
00046       if (a > 0) {
00047         min += a*t[i].x.min();
00048         max += a*t[i].x.max();
00049       } else {
00050         max += a*t[i].x.min();
00051         min += a*t[i].x.max();
00052       }
00053     }
00054     if (min < Limits::min)
00055       min = Limits::min;
00056     if (min > Limits::max)
00057       min = Limits::max;
00058     l = static_cast<int>(min);
00059     if (max < Limits::min)
00060       max = Limits::min;
00061     if (max > Limits::max)
00062       max = Limits::max;
00063     u = static_cast<int>(max);
00064   }
00065 
00067   template<class View>
00068   class TermLess {
00069   public:
00070     forceinline bool
00071     operator ()(const Term<View>& a, const Term<View>& b) {
00072       return a.x < b.x;
00073     }
00074   };
00075 
00077   inline int
00078   gcd(int a, int b) {
00079     if (b > a)
00080       std::swap(a,b);
00081     while (b > 0) {
00082       int t = b; b = a % b; a = t;
00083     }
00084     return a;
00085   }
00086 
00087 
00088 
00113   template<class View>
00114   inline bool
00115   normalize(Term<View>* t, int &n,
00116             Term<View>* &t_p, int &n_p,
00117             Term<View>* &t_n, int &n_n,
00118             int& g) {
00119     /*
00120      * Join coefficients for aliased variables:
00121      *
00122      */
00123     {
00124       // Group same variables
00125       TermLess<View> tl;
00126       Support::quicksort<Term<View>,TermLess<View> >(t,n,tl);
00127 
00128       // Join adjacent variables
00129       int i = 0;
00130       int j = 0;
00131       while (i < n) {
00132         Limits::check(t[i].a,"Int::linear");
00133         long long int a = t[i].a;
00134         View x = t[i].x;
00135         while ((++i < n) && (t[i].x == x)) {
00136           a += t[i].a;
00137           Limits::check(a,"Int::linear");
00138         }
00139         if (a != 0) {
00140           t[j].a = static_cast<int>(a); t[j].x = x; j++;
00141         }
00142       }
00143       n = j;
00144     }
00145 
00146     /*
00147      * Partition into positive/negative coefficents
00148      *
00149      */
00150     if (n > 0) {
00151       int i = 0;
00152       int j = n-1;
00153       while (true) {
00154         while ((t[j].a < 0) && (--j >= 0)) ;
00155         while ((t[i].a > 0) && (++i <  n)) ;
00156         if (j <= i) break;
00157         std::swap(t[i],t[j]);
00158       }
00159       t_p = t;     n_p = i;
00160       t_n = t+n_p; n_n = n-n_p;
00161     } else {
00162       t_p = t; n_p = 0;
00163       t_n = t; n_n = 0;
00164     }
00165 
00166     /*
00167      * Make all coefficients positive
00168      *
00169      */
00170     for (int i=0; i<n_n; i++)
00171       t_n[i].a = -t_n[i].a;
00172 
00173     /*
00174      * Compute greatest common divisor
00175      *
00176      */
00177     if ((n > 0) && (g > 0)) {
00178       g = t[0].a;
00179       for (int i=1; (g > 1) && (i < n); i++)
00180         g = gcd(t[i].a,g);
00181       if (g > 1)
00182         for (int i=n; i--; )
00183           t[i].a /= g;
00184     } else {
00185       g = 1;
00186     }
00187 
00188     /*
00189      * Test for unit coefficients only
00190      *
00191      */
00192     for (int i=0; i<n; i++)
00193       if (t[i].a != 1)
00194         return false;
00195     return true;
00196   }
00197 
00198 }}}
00199 
00200 // STATISTICS: int-post
00201