gccbndsup.hpp

Go to the documentation of this file.

/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
 *  Main authors:
 *     Patrick Pekczynski <pekczynski@ps.uni-sb.de>
 *
 *  Copyright:
 *     Patrick Pekczynski, 2004
 *
 *  Last modified:
 *     $Date: 2009-01-20 23:44:27 +0100 (Tue, 20 Jan 2009) $ by $Author: schulte $
 *     $Revision: 8082 $
 *
 *  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.
 *
 */

namespace Gecode { namespace Int { namespace GCC {



  class UnReachable {
  public:
    unsigned int minb;
    unsigned int maxb;
    unsigned int eq;
    unsigned int le;
    unsigned int gr;
  };

  template <class View, class Card, bool shared>
  inline ExecStatus
  prop_card(Space& home, ViewArray<View>& x, ViewArray<Card>& k, bool& mod) {
    int n = x.size();
    int m = k.size();
    Region r(home);
    UnReachable* rv = r.alloc<UnReachable>(m);
    for(int i = m; i--; )
      rv[i].minb = rv[i].maxb = rv[i].le = rv[i].gr = rv[i].eq = 0;

    for (int i = n; i--; ) {
      int b = x[i].assigned();
      int min_idx = 0;
      int max_idx = 0;
      min_idx = lookupValue(k,x[i].min());
      if (min_idx == -1) {
        return ES_FAILED;
      }
      if (b) {
        rv[min_idx].minb++;
        rv[min_idx].maxb++;
        rv[min_idx].eq++;
      } else {
        max_idx = lookupValue(k,x[i].max());
        if (max_idx == -1) {
          return ES_FAILED;
        }
        // count the number of variables
        // with lower bound k[min_idx].card()
        rv[min_idx].minb++;

        // count the number of variables
        // with upper bound k[max_idx].card()
        rv[max_idx].maxb++;
      }
    }

    rv[0].le = 0;
    int c_min = 0;
    for (int i = 1; i < m; i++) {
      rv[i].le = c_min + rv[i - 1].maxb;
      c_min += rv[i - 1].maxb;
    }

    rv[m-1].gr = 0;
    int c_max = 0;
    for (int i = m-1; i--; ) {
      rv[i].gr = c_max + rv[i + 1].minb;
      c_max += rv[i + 1].minb;
    }

    for (int i = m; i--; ) {
      int reachable = (int) (x.size() - rv[i].le - rv[i].gr);
      if (!k[i].assigned()) {
        ModEvent me = k[i].lq(home, reachable);
        if (me_failed(me))
          return ES_FAILED;
        mod |= (me_modified(me) && (k[i].max() != reachable));
        mod |= shared && me_modified(me);

        if (rv[i].eq > 0) {
          ModEvent me = k[i].gq(home, (int) rv[i].eq);
          if (me_failed(me))
            return ES_FAILED;
          mod |= (me_modified(me) && (k[i].min() != (int) rv[i].eq));
          mod |= shared && me_modified(me);
        }
      } else {
        // check validity of the cardinality value
        int v = k[i].max();
        if ( !( (int) rv[i].eq <= v && v <= reachable) )
          return ES_FAILED;
      }
    }

    return ES_OK;
  }


  template <class View, class Card>
  inline bool
  card_consistent(int& smin, int& smax, ViewArray<View>& x,
                  ViewArray<Card>& k) {

    int m = k.size();
    int n = x.size();
    for (int i = m; i--; ) {
      smax += k[i].max();
      smin += k[i].min();
    }

    // not enough variables to satifsy cardinality requirements
    if (n < smin) {
      return false;
    }

    // we are using ALL variables
    // not all variables can be assigned
    if (smax < n) {
      return false;
    }

    return true;
  }

  class Rank {
  public:
    int min;
    int max;
  };

  template <class View>
  class MaxInc {
  protected:
    ViewArray<View> x;
  public:
    MaxInc(const ViewArray<View>& x0) : x(x0) {}
    forceinline bool
    operator ()(const int i, const int j) {
      return x[i].max() < x[j].max();
    }
  };

  template <class View>
  class MinInc {
  protected:
    ViewArray<View> x;
  public:
    MinInc(const ViewArray<View>& x0) : x(x0) {}
    forceinline bool
    operator ()(const int i, const int j) {
      return x[i].min() < x[j].min();
    }
  };


  template <class Card>
  class PartialSum {
  private:
    char* mem;
    size_t _allocated;
    int* sum;
    int* ds;
    int size;
  public:

    PartialSum( int, int, ViewArray<Card>& , bool);
    ~PartialSum(void);


    int firstValue;
    int lastValue;
    int sumup(int, int);
    int minValue(void);
    int maxValue(void);
    int skipNonNullElementsRight(int);
    int skipNonNullElementsLeft(int);
    void* operator new(size_t s);
    void operator delete(void* p);
    bool check_update_max(ViewArray<Card>& k);
    bool check_update_min(ViewArray<Card>& k);
    int getsize(void) const;
    size_t allocated(void) const;
  };

  template <class Card>
  forceinline
  PartialSum<Card>::~PartialSum(void){
    assert(mem != NULL);
    heap.rfree(mem);
  }

  template <class Card>
  forceinline void*
  PartialSum<Card>::operator new(size_t t){
    return heap.ralloc(t);
  }

  template <class Card>
  forceinline void
  PartialSum<Card>::operator delete(void* p){
      heap.rfree(p);
  }

  template <class Card>
  inline
  PartialSum<Card>::PartialSum(int first,
                               int count,
                               ViewArray<Card>& elements,
                               bool up) {
    int i = 0;
    int j = 0;
    // we add three elements at the beginning and two at the end
    size  = count + 5;
    // memory allocation
    size_t sum_size = (size) * sizeof(int);
    size_t ds_size  = (size) * sizeof(int);
    size_t total    = sum_size + ds_size;
    _allocated = total;

    mem = static_cast<char*>(heap.ralloc(total));
    sum = Support::ptr_cast<int*>(mem);
    ds  = Support::ptr_cast<int*>(mem + sum_size);

    for (int z = 0; z < size; z++) {
      sum[z] = 0;
      ds[z]  = 0;
    }

    /*
     * firstValue and lastValue are sentinels
     * indicating whether an end of the sum has been reached
     *
     */
    firstValue = first - 3;
    lastValue  = first + count + 1;


    // the first three elements
    for (i = 3; i--; ){
      sum[i] = i;
    }

    int shift  = count + 2;

    /*
     * copy the bounds into sum
     * optimization only those values being indeed
     * variable bounds
     */
    for (i = 2; i < shift; i++){
      if (up) {
        sum[i + 1] = sum[i] + elements[i - 2].max();
      } else {
        sum[i + 1] = sum[i] + elements[i - 2].min();
      }
    }
    sum[i + 1] = sum[i] + 1;
    sum[i + 2] = sum[i + 1] + 1;


    // check for doublets
    i = count + 3;
    j = i + 1;
    for ( ; i > 0; ){
      while(sum[i] == sum[i - 1]) {
        ds[i] = j;
        i--;
      }
      ds[j] = i;
      i--;
      j = ds[j];
    }
    ds[j] = 0;
    // for the sake of having no seg fault
    ds[0] = 0;
  }

  template <class Card>
  forceinline int
  PartialSum<Card>::sumup(int from, int to){
    if (from <= to) {
      return sum[to - firstValue] - sum[from - firstValue - 1];
    } else {
      return sum[to - firstValue - 1] - sum[from - firstValue];
    }
  }

  template <class Card>
  forceinline int
  PartialSum<Card>::minValue(void){
    return firstValue + 3;
  }

  template <class Card>
  forceinline int
  PartialSum<Card>::maxValue(void){
    return lastValue - 2;
  }


  template <class Card>
  forceinline int
  PartialSum<Card>::skipNonNullElementsRight(int value) {
    value -= firstValue;
    return (ds[value] < value ? value : ds[value]) + firstValue;
  }

  template <class Card>
  forceinline int
  PartialSum<Card>::skipNonNullElementsLeft(int value) {
    value -= firstValue;
    return (ds[value] > value ? ds[ds[value]] : value) + firstValue;
  }

  template <class Card>
  inline bool
  PartialSum<Card>::check_update_max(ViewArray<Card>& k){
    if (k.size() <= size - 5) {
      return true;
    } else {
      for (int i = 3; i < size - 2; i++) {
        if ((sum[i] - sum[i - 1]) != k[i - 3].max()) {
          return true;
        }
      }
      return false;
    }
  }

  template <class Card>
  inline bool
  PartialSum<Card>::check_update_min(ViewArray<Card>& k){
    if (k.size() <= size - 5) {
      return true;
    } else {
      for (int i = 3; i < size - 2; i++) {
        if ((sum[i] - sum[i - 1]) != k[i - 3].min()) {
          return true;
        }
      }
      return false;
    }
  }

  template <class Card>
  forceinline int
  PartialSum<Card>::getsize(void) const {
    return size;
  }
  template <class Card>
  forceinline size_t
  PartialSum<Card>::allocated(void) const {
    return sizeof(PartialSum<Card>) + _allocated;
  }


  class HallInfo {
  public:
    int bounds;
    int t;
    int d;
    int h;
    int s;
    int ps;
    int newBound;
  };



  inline void
  pathset_ps(HallInfo hall[], int start, int end, int to) {
    int k, l;
    for (l=start; (k=l) != end; hall[k].ps=to) {
      l = hall[k].ps;
    }
  }

  inline void
  pathset_s(HallInfo hall[], int start, int end, int to) {
    int k, l;
    for (l=start; (k=l) != end; hall[k].s=to) {
      l = hall[k].s;
    }
  }

  inline void
  pathset_t(HallInfo hall[], int start, int end, int to) {
    int k, l;
    for (l=start; (k=l) != end; hall[k].t=to) {
      l = hall[k].t;
    }
  }

  inline void
  pathset_h(HallInfo hall[], int start, int end, int to) {
    int k, l;
    for (l=start; (k=l) != end; hall[k].h=to) {
      l = hall[k].h;
    }
  }


  forceinline int
  pathmin_h(const HallInfo hall[], int i) {
    while (hall[i].h < i)
      i = hall[i].h;
    return i;
  }
  forceinline int
  pathmin_t(const HallInfo hall[], int i) {
    while (hall[i].t < i)
      i = hall[i].t;
    return i;
  }


  forceinline int
  pathmax_h(const HallInfo hall[], int i) {
    while (hall[i].h > i)
      i = hall[i].h;
    return i;
  }


  forceinline int
  pathmax_t(const HallInfo hall[], int i) {
    while (hall[i].t > i) {
      i = hall[i].t;
    }
    return i;
  }

  forceinline int
  pathmax_s(const HallInfo hall[], int i) {
    while (hall[i].s > i)
      i = hall[i].s;
    return i;
  }

  forceinline int
  pathmax_ps(const HallInfo hall[], int i) {
    while (hall[i].ps > i)
      i = hall[i].ps;
    return i;
  }


  template <class Card>
  void
  reduce_card(Space& home, int cmin, int cmax, ViewArray<Card>& k) {
    if (cmin == cmax) {
      int idx = 0;
      while (k[idx].card() != cmax) {
        idx++;
      }
      k[0] = k[idx];
      k.size(1);
    } else {
      Region r(home);
      bool* zero = r.alloc<bool>(k.size());
      int ks = k.size();
      int zc = 0;
      for (int i = 0; i < ks; i++) {
        bool impossible  = ( (k[i].counter() == 0) &&
                             (k[i].card() < cmin ||
                              k[i].card() > cmax));

        if (impossible) {
          zero[i] = true;
          zc++;
        } else {
          zero[i] = false;
        }
      }


      if (zero[ks - 1]) {
        int m = ks;
        while(zero[m - 1]) {
          m--;
          zc--;
        }
        k.size(m);
      }

      if (zc > 0) {
        int ks = k.size();
        // if there are still zero entries left
        for (int i = 0; i < ks; i++) {
          assert(0 <= i && i < ks);
          if  (zero[i]) {
            if (i == ks - 1) {
              break;
            }
            // this cardinality does not occur
            // remove it
            // we need the next non-null entry
            int j = i + 1;
            assert(0 <= j && j < ks);
            if (j < ks) {
              while (zero[j]) {
                j++;
              }
            }
            if (j > ks - 1) {
              break;
            }
            k[i] = k[j];
            zero[j] = true;
          }
        }
        k.size(ks - zc);
      }

    }

  }

}}}

// STATISTICS: int-prop