text: /*
   * Top-Down ZDD Construction Library for Frontier-Based Search
   * by Hiroaki Iwashita <iwashita@erato.ist.hokudai.ac.jp>
   * Copyright (c) 2012 Japan Science and Technology Agency
   * $Id: DegreeConstraint.hpp 421 2013-02-25 05:33:17Z iwashita $
   */
  
  #pragma once
  
  #include <cassert>
  #include <map>
  #include <vector>
  
  #include "../DdSpec.hpp"
  
  namespace tdzdd {
  
  template<typename T>
  class LinearConstraints: public PodArrayDdSpec<LinearConstraints<T>,T,2> {
      struct CheckItem {
          int index;
          T weight;
          T addMin;
          T addMax;
          T lowerBound;
          T upperBound;
          bool finalChoice;
  
          CheckItem(int i,
                    T const& w,
                    T const& min,
                    T const& max,
                    T const& lb,
                    T const& ub,
                    bool fc) :
                  index(i),
                  weight(w),
                  addMin(min),
                  addMax(max),
                  lowerBound(lb),
                  upperBound(ub),
                  finalChoice(fc) {
          }
      };
  
      typedef std::vector<CheckItem> Checklist;
  
      int const n;
      std::vector<Checklist> checklists;
      int arraySize;
      int constraintId;
      bool isFalse;
  
  public:
      LinearConstraints(int n) :
              n(n),
              checklists(n + 1),
              arraySize(0),
              constraintId(0),
              isFalse(false) {
          assert(n >= 1);
      }
  
      void addConstraint(std::map<int,T> const& expr, T const& lb, T const& ub) {
          if (isFalse) return;
          T min = 0;
          T max = 0;
          for (typename std::map<int,T>::const_iterator t = expr.begin();
                  t != expr.end(); ++t) {
              T const& w = t->second;
              if (w > 0) max += w;
              else if (w < 0) min += w;
          }
          if (lb <= min && max <= ub) return;
          if (ub < lb || max < lb || ub < min) {
              isFalse = true;
              return;
          }
          if (expr.empty()) return;
  
          min = 0;
          max = 0;
          bool fc = true;
          for (typename std::map<int,T>::const_iterator t = expr.begin();
                  t != expr.end(); ++t) {
              Checklist& list = checklists[t->first];
              T const& w = t->second;
              list.push_back(CheckItem(constraintId, w, min, max, lb, ub, fc));
              if (w > 0) max += w;
              else if (w < 0) min += w;
              fc = false;
          }
          ++constraintId;
      }
  
      void update() {
          std::vector<int> indexMap(constraintId);
          for (int id = 0; id < constraintId; ++id) {
              indexMap[id] = -1;
          }
          std::vector<int> freeIndex;
  
          for (int i = n; i >= 1; --i) {
              Checklist& list = checklists[i];
  
              for (typename Checklist::iterator t = list.begin(); t != list.end();
                      ++t) {
                  int id = t->index;
  
                  if (indexMap[id] < 0) {
                      if (freeIndex.empty()) {
                          indexMap[id] = arraySize++;
                      }
                      else {
                          indexMap[id] = freeIndex.back();
                          freeIndex.pop_back();
                      }
                  }
  
                  t->index = indexMap[id];
              }
  
              for (typename Checklist::iterator t = list.begin(); t != list.end();
                      ++t) {
                  if (t->finalChoice) {
                      freeIndex.push_back(t->index);
                  }
              }
          }
  
          this->setArraySize(arraySize);
      }
  
      int getRoot(T* value) const {
          if (isFalse) return 0;
  
          for (int k = 0; k < arraySize; ++k) {
              value[k] = 0;
          }
  
          return n;
      }
  
      int getChild(T* value, int level, bool take) const {
          Checklist const& list = checklists[level];
  
          for (typename Checklist::const_iterator t = list.begin();
                  t != list.end(); ++t) {
              T& v = value[t->index];
              if (take) v += t->weight;
              if (v + t->addMax < t->lowerBound || t->upperBound < v + t->addMin)
                  return 0;
              if (t->lowerBound <= v + t->addMin
                  && v + t->addMax <= t->upperBound) // state compression
              v = t->lowerBound - t->addMin;
              if (t->finalChoice) v = 0;
          }
  
          return (--level >= 1) ? level : -1;
      }
  };
  
  } // namespace tdzdd
  