IsoCounter.hh

Go to the documentation of this file.

#ifndef ISOCOUNTER_HH
#define ISOCOUNTER_HH


#include "casm/container/BaseCounter.hh"

namespace CASM {

  template<typename _Container, typename _value_type, typename _size_type, typename _Access, typename _Compare>
  class IsoCounter;

  namespace CASM_TMP {
    template<typename _Container, typename _value_type, typename _size_type, typename _Access, typename _Compare>
    struct traits<IsoCounter<_Container, _value_type, _size_type, _Access, _Compare> > {
      typedef BaseCounter<IsoCounter<_Container, _value_type, _size_type, _Access, _Compare> > Base;
      typedef _Container Container;
      typedef _value_type value_type;
      typedef _size_type size_type;
      typedef _Access Access;
      typedef _Compare Compare;
    };
  }

  template < typename _Container,
             typename _value_type = typename _Container::value_type,
             typename _size_type = typename _Container::size_type,
             typename _Access = CASM_TMP::BracketAccess<_Container, _value_type, _size_type>,
             typename _Compare = CASM_TMP::MuchLessThan<_value_type> >
  class IsoCounter : public BaseCounter<IsoCounter<_Container, _value_type, _size_type, _Access, _Compare> > {
    typedef typename CASM_TMP::traits<IsoCounter>::Base Base;
    using Base::_valid;
    using Base::_initial;
    using Base::_final;
    using Base::_increment;
    using Base::_current;
    using Base::_upper;
    using Base::_lower;
  public:
    typedef _Container Container;
    typedef _value_type value_type;
    typedef _size_type size_type;
    typedef _Access Access;
    typedef _Compare Compare;

    using Base::valid;
    using Base::size;
    using Base::compare;
    using Base::initial;
    using Base::final;
    using Base::current;
    using Base::operator();
    using Base::operator[];
    using Base::operator bool;

    IsoCounter() : IsoCounter(Container(), Container(), 0, 0) { }

    IsoCounter(const Container &_initial,
               const Container &_final,
               const value_type &_increment,
               const value_type &_sum,
               Access _access = Access(),
               Compare _compare = Compare()) :
      Base(_initial, _final, Array<value_type>(1, _increment), _access, _compare), m_sum_constraint(_sum) {
      _init();
      reset();
    }

    const value_type &increment() const {
      return _increment(0);
    }

    value_type current_sum() const {
      if(size() == 0)
        return 0;
      value_type result(current(0));
      for(size_type i = 1; i < size(); i++) {
        result += current(i);
      }
      return result;
    }

    IsoCounter &operator++() {
      if(!valid())
        return (*this);
      size_type i(0), j(0);
      bool continue_flag = valid();
      value_type next_i, next_j;
      for(i = 0; i + 1 < size(); i++) {
        next_i = current(i) - increment();
        if(compare(_upper(i), next_i) || compare(next_i, _lower(i)))
          continue;
        j = i + 1;
        while(j < size() && !compare(_lower(j), _upper(j)))
          j++;
        if(j == size())
          break;
        next_j = current(j) + increment();
        if(compare(_upper(j), next_j) || compare(next_j, _lower(j))) {
          i = j - 1;
          continue;
        }

        _current(i) = next_i;
        _current(j) = next_j;
        //next_i -= m_increment;

        continue_flag = false;
        break;
      }

      // if the loop finished without breaking, there were no more elements to increment.
      // that means we have reached the last permutation, so we invalidate counter and return
      if(continue_flag || !valid()) {
        _valid() = false;
        return *this;
      }

      j = 0;
      next_j = current(j) + increment();
      //next_i already contains _current(i) from above
      next_i -= increment();
      while(j < i) {

        while(!(compare(_upper(j), next_j)
                || compare(next_j, _lower(j))
                || compare(_upper(i), next_i)
                || compare(next_i, _lower(i)))) {

          _current(i) = next_i;
          next_i -= increment();

          _current(j) = next_j;
          next_j += increment();
        }

        while(j < i && (compare(_upper(i), next_i) || compare(next_i, _lower(i))))
          next_i = current(--i) - increment();

        while(j < i && (compare(_upper(j), next_j) || compare(next_j, _lower(j))))
          next_j = current(++j) + increment();

      }
      return *this;
    }

    void operator++(int) {
      ++(*this);
    }

    void set_sum_constraint(const value_type &new_sum) {
      _sum_constraint() = new_sum;
      reset();
    }

    void set_current(const Container &new_current) {
      if(current().size() != new_current.size()) {
        std::cerr << "CRITICAL ERROR: In IsoCounter::set_current(), new state is incompatible with this counter.\n"
                  << "                Exiting...\n";
        exit(1);
      }
      _current() = new_current;
      _compute_validity();
    }

    void reset() {

      _valid() = size() != 0;

      _current() = initial();

      //Find the residual sum: m_sum_constraint - m_current.sum()
      value_type sum_val(_sum_constraint() - current_sum());

      // if residual sum does not have same sign as increment, nothing can happen
      if(compare(sum_val + sum_val, sum_val) != compare(increment() + increment(), increment())) {
        _valid() = false;
        return;
      }

      size_type i;

      for(i = 0; i < size(); i++) {

        //if(almost_equal(m_initial[i], m_final[i])) //avoid operating on fixed elements
        //continue;

        // if the i'th element isn't fixed, then increment it while decrementing sum_val
        // until one or the other cannot be incremented/decremented further
        while(!(compare(_upper(i), _current(i) + increment())
                || compare(_current(i) + increment(), _lower(i))
                || almost_zero(sum_val))) {
          _current(i) += increment();
          sum_val -= increment();
        }
      }
      if(!almost_zero(sum_val)) {
        _valid() = false;
      }
      return;

    }



  private:
    value_type m_sum_constraint;

    value_type &_sum_constraint() {
      return m_sum_constraint;
    }

    const value_type &_sum_constraint() const {
      return m_sum_constraint;
    }

    bool _compute_validity() {
      value_type S(current_sum());
      _valid() = !(compare(_sum_constraint(), S) || compare(S, _sum_constraint()));
      for(size_type i = 0; i < size() && valid(); i++) {
        _valid() = valid()
                   && compare(_current(i), _upper(i))
                   && compare(_lower(i), _current(i));
      }
      return valid();
    }

    void _init() {
      for(size_type i = 0; i < initial().size(); i++) {
        if(compare(_initial(i), _final(i))) {
          _lower(i) = _initial(i);
          _upper(i) = _final(i);
        }
        else {
          _lower(i) = _final(i);
          _upper(i) = _initial(i);
        }
      }
    }

    value_type &_increment() {
      return Base::_increment(0);
    }

    const value_type &_increment() const {
      return Base::_increment(0);
    }

  };


}


#endif