/*
 *  Main authors:
 *     Guido Tack <tack@gecode.org>
 *
 *  Copyright:
 *     Guido Tack, 2004
 *
 *  Last modified:
 *     $Date: 2006-08-24 11:25:05 +0200 (Thu, 24 Aug 2006) $ by $Author: schulte $
 *     $Revision: 3559 $
 *
 *  This file is part of Gecode, the generic constraint
 *  development environment:
 *     http://www.gecode.org
 *
 *  See the file "LICENSE" for information on usage and
 *  redistribution of this file, and for a
 *     DISCLAIMER OF ALL WARRANTIES.
 *
 */

namespace Gecode { namespace Set {

  /**
   * \brief %Range iterator for a two-dimensional array
   * \ingroup TaskActorSetView
   */
  class ArrayRanges {
  private:
    int *_ranges;
    int _size;
    int _pos;
  public:
    /// \name Constructors and initialization
    //@{
    /// Default constructor
    ArrayRanges() : _ranges(NULL), _size(0), _pos(0) {}
    /// Initialize with ranges for array \a ranges which is of size \a size
    ArrayRanges(int *ranges, int size)
      : _ranges(ranges), _size(size), _pos(0) {}
    /// Initialize with ranges for array \a ranges which is of size \a size
    void init(int* ranges, int size) {
      _ranges = ranges; _size = size; _pos = 0;
    }
    //@}

    /// \name Iteration control
    //@{
    /// Test whether iterator is still at a range or done
    bool operator()(void) const { return _pos<_size; }
    /// Move iterator to next range (if possible)
    void operator++(void) { _pos++; }
    //@}

    /// \name Range access
    //@{
    /// Return smallest value of range
    int min(void) const { return _ranges[_pos*2]; }
    /// Return largest value of range
    int max(void) const { return _ranges[_pos*2+1]; }
    /// Return width of range (distance between minimum and maximum)
    unsigned int width(void) const {
      return _ranges[_pos*2+1]-_ranges[_pos*2]+1;
    }
    //@}
  };

  forceinline
  ConstantView::ConstantView(void) : ranges(NULL), size(0), domSize(0) {}

  forceinline
  ConstantView::ConstantView(Space* home, const IntSet& dom)
    : ranges(NULL), size(dom.size()), domSize(0) {
    if (size > 0) {
      ranges = static_cast<int*>(home->alloc(2*size*sizeof(int)));
      IntSetRanges dr(dom);
      for (int i=0; dr(); ++dr, i+=2) {
	int min = dr.min(); int max = dr.max();
	ranges[i] = min;
	ranges[i+1] = max;
	domSize += (max-min+1);
      }
    }
  }

  forceinline bool
  ConstantView::assigned(void) const { return true; }

  forceinline unsigned int
  ConstantView::glbSize(void) const { return domSize; }

  forceinline unsigned int
  ConstantView::lubSize(void) const { return domSize; }

  forceinline unsigned int
  ConstantView::unknownSize(void) const { return 0; }

  forceinline bool
  ConstantView::contains(int i) const {
    for (unsigned int j=size; j--; ) {
      if (ranges[2*j+1] < i)
	return false;
      if (ranges[2*j] >= i)
	return true;
    }
    return false;
  }

  forceinline bool
  ConstantView::notContains(int i) const {
    return !contains(i);
  }

  forceinline unsigned int
  ConstantView::cardMin() const { return domSize; }

  forceinline unsigned int
  ConstantView::cardMax() const { return domSize; }

  forceinline int
  ConstantView::lubMin() const {
    return size==0 ? BndSet::MIN_OF_EMPTY : ranges[0];
  }

  forceinline int
  ConstantView::lubMax() const {
    return size==0 ? BndSet::MAX_OF_EMPTY : ranges[size*2-1];
  }

  forceinline int
  ConstantView::glbMin() const { return lubMin(); }

  forceinline int
  ConstantView::glbMax() const { return lubMax(); }

  forceinline ModEvent
  ConstantView::cardMin(Space* home,unsigned int c) {
    return c<=domSize ? ME_SET_NONE : ME_SET_FAILED;
  }

  forceinline ModEvent
  ConstantView::cardMax(Space* home,unsigned int c) {
    return c>=domSize ? ME_SET_NONE : ME_SET_FAILED;
  }

  forceinline ModEvent
  ConstantView::include(Space* home,int c) {
    return contains(c) ? ME_SET_NONE : ME_SET_FAILED;
  }

  forceinline ModEvent
  ConstantView::exclude(Space* home,int c) {
    return contains(c) ? ME_SET_FAILED : ME_SET_NONE;
  }

  forceinline ModEvent
  ConstantView::intersect(Space* home,int c) {
    return (size==0 ||
	    (size==1 &&
	     ranges[0]==ranges[1] && ranges[0]==c)) ?
      ME_SET_NONE : ME_SET_FAILED;
  }

  forceinline ModEvent
  ConstantView::intersect(Space* home,int i,int j) {
    return (glbMin()>=i && glbMax()<=j) ?
      ME_SET_NONE : ME_SET_FAILED;
  }

  forceinline ModEvent
  ConstantView::include(Space* home,int i,int j) {
    Iter::Ranges::Singleton single(i,j);
    ArrayRanges ar(ranges, size);
    return (single() && Iter::Ranges::subset(single, ar)) ?
      ME_SET_NONE : ME_SET_FAILED;
  }

  forceinline ModEvent
  ConstantView::exclude(Space* home,int i,int j) {
    Iter::Ranges::Singleton single(i,j);
    ArrayRanges ar(ranges, size);
    return (single() && Iter::Ranges::subset(single, ar)) ?
      ME_SET_FAILED : ME_SET_NONE;
  }

  template <class I> ModEvent
  ConstantView::excludeI(Space* home,I& i) {
    ArrayRanges ar(ranges, size);
    return (i() && Iter::Ranges::subset(i, ar)) ? ME_SET_FAILED : ME_SET_NONE;
  }

  template <class I> ModEvent
  ConstantView::includeI(Space* home,I& i) {
    ArrayRanges ar(ranges, size);
    return Iter::Ranges::subset(i, ar) ? ME_SET_NONE : ME_SET_FAILED;
  }

  template <class I> ModEvent
  ConstantView::intersectI(Space* home,I& i) {
    ArrayRanges ar(ranges, size);
    return Iter::Ranges::subset(ar, i) ? ME_SET_NONE : ME_SET_FAILED;
  }

  forceinline void
  ConstantView::subscribe(Space* home,Propagator*,PropCond,bool) {}
  forceinline void
  ConstantView::cancel(Space* home, Propagator*,PropCond) {}

  forceinline ModEvent
  ConstantView::pme(const Propagator*) {
    return ME_SET_NONE;
  }
  forceinline PropModEvent
  ConstantView::pme(ModEvent me) {
    return SetVarImp::pme(me);
  }

  forceinline void
  ConstantView::update(Space* home, bool share, ConstantView& p) {
    // dispose old ranges
    if (size>0) {
      home->reuse(ranges, 2*size*sizeof(int));
    }

    domSize = p.domSize;
    size = p.size;
    if (size == 0) {
      ranges = NULL;
    } else {
      // copy ranges from p
      ranges = static_cast<int*>(home->alloc(2*size*sizeof(int)));
      for (unsigned int i=size; i--; ) {
	ranges[2*i]   = p.ranges[2*i];
	ranges[2*i+1] = p.ranges[2*i+1];
      }
    }
  }

  forceinline
  EmptyView::EmptyView(void) {}


  forceinline bool
  EmptyView::assigned(void) const { return true; }

  forceinline unsigned int
  EmptyView::glbSize(void) const { return 0; }

  forceinline unsigned int
  EmptyView::lubSize(void) const { return 0; }

  forceinline unsigned int
  EmptyView::unknownSize(void) const { return 0; }

  forceinline bool
  EmptyView::contains(int) const { return false; }

  forceinline bool
  EmptyView::notContains(int) const { return true; }

  forceinline unsigned int
  EmptyView::cardMin() const { return 0; }

  forceinline unsigned int
  EmptyView::cardMax() const { return 0; }

  forceinline int
  EmptyView::lubMin() const { return 0; }

  forceinline int
  EmptyView::lubMax() const { return 0; }

  forceinline int
  EmptyView::glbMin() const { return 0; }

  forceinline int
  EmptyView::glbMax() const { return 0; }

  forceinline ModEvent
  EmptyView::cardMin(Space* home,unsigned int c) {
    return c==0 ? ME_SET_NONE : ME_SET_FAILED;
  }

  forceinline ModEvent
  EmptyView::cardMax(Space* home,unsigned int c) {
    return ME_SET_NONE;
  }


  forceinline ModEvent
  EmptyView::include(Space* home,int) {
    return ME_SET_FAILED;
  }

  forceinline ModEvent
  EmptyView::exclude(Space* home,int) { return ME_SET_NONE; }

  forceinline ModEvent
  EmptyView::intersect(Space* home,int) { return ME_SET_NONE; }

  forceinline ModEvent
  EmptyView::intersect(Space* home,int,int) { return ME_SET_NONE; }

  forceinline ModEvent
  EmptyView::include(Space* home,int,int) {
    return ME_SET_FAILED; }

  forceinline ModEvent
  EmptyView::exclude(Space* home,int,int) { return ME_SET_NONE; }

  template <class I> ModEvent
  EmptyView::excludeI(Space* home,I&) { return ME_SET_NONE; }

  template <class I> ModEvent
  EmptyView::includeI(Space* home,I& i) {
    return i() ? ME_SET_FAILED : ME_SET_NONE;
  }

  template <class I> ModEvent
  EmptyView::intersectI(Space* home,I&) {
    return ME_SET_NONE;
  }

  forceinline void
  EmptyView::subscribe(Space* home,Propagator*,PropCond,bool) {}
  forceinline void
  EmptyView::cancel(Space* home, Propagator*,PropCond) {}

  forceinline ModEvent
  EmptyView::pme(const Propagator*) {
    return ME_SET_NONE;
  }
  forceinline PropModEvent
  EmptyView::pme(ModEvent me) {
    return SetVarImp::pme(me);
  }

  forceinline void
  EmptyView::update(Space* home, bool, EmptyView&) {}



  // Constant universe variable

  forceinline
  UniverseView::UniverseView(void) {}

  forceinline bool
  UniverseView::assigned(void) const { return true; }

  forceinline unsigned int
  UniverseView::glbSize(void) const { return Limits::Set::card_max; }

  forceinline unsigned int
  UniverseView::lubSize(void) const { return Limits::Set::card_max; }

  forceinline unsigned int
  UniverseView::unknownSize(void) const { return 0; }

  forceinline bool
  UniverseView::contains(int) const { return true; }

  forceinline bool
  UniverseView::notContains(int) const { return false; }

  forceinline unsigned int
  UniverseView::cardMin() const { return Limits::Set::card_max; }

  forceinline unsigned int
  UniverseView::cardMax() const { return Limits::Set::card_max; }

  forceinline int
  UniverseView::lubMin() const { return Limits::Set::card_max; }

  forceinline int
  UniverseView::lubMax() const { return Limits::Set::card_max; }

  forceinline int
  UniverseView::glbMin() const { return Limits::Set::card_max; }

  forceinline int
  UniverseView::glbMax() const { return Limits::Set::card_max; }

  forceinline ModEvent
  UniverseView::cardMin(Space* home,unsigned int c) {
    return c>Limits::Set::card_max ? ME_SET_FAILED : ME_SET_NONE;
  }

  forceinline ModEvent
  UniverseView::cardMax(Space* home,unsigned int c) {
    return c>=Limits::Set::card_max ? ME_SET_NONE : ME_SET_FAILED;
  }


  forceinline ModEvent
  UniverseView::include(Space* home,int) {
    return ME_SET_NONE;
  }

  forceinline ModEvent
  UniverseView::exclude(Space* home,int) { return ME_SET_FAILED; }

  forceinline ModEvent
  UniverseView::intersect(Space* home,int) { return ME_SET_FAILED; }

  forceinline ModEvent
  UniverseView::include(Space* home,int,int) { return ME_SET_NONE; }

  forceinline ModEvent
  UniverseView::exclude(Space* home,int,int) { return ME_SET_FAILED; }

  template <class I> ModEvent
  UniverseView::excludeI(Space* home,I& i) {
    return i() ? ME_SET_FAILED : ME_SET_NONE;
  }

  template <class I> forceinline ModEvent
  UniverseView::includeI(Space* home,I&) { return ME_SET_NONE; }

  forceinline ModEvent
  UniverseView::intersect(Space* home,int i,int j) {
    return (i>Limits::Set::int_min ||
	    i<Limits::Set::int_max) ? ME_SET_FAILED : ME_SET_NONE;
  }

  template <class I> forceinline ModEvent
  UniverseView::intersectI(Space* home,I& i) {
    return (i() &&
	    (i.min()>Limits::Set::int_min ||
	     i.max()<Limits::Set::int_max) ) ?
      ME_SET_FAILED : ME_SET_NONE;
  }

  forceinline void
  UniverseView::subscribe(Space* home,Propagator*,PropCond,bool) {}
  forceinline void
  UniverseView::cancel(Space* home, Propagator*,PropCond) {}

  forceinline ModEvent
  UniverseView::pme(const Propagator*) {
    return ME_SET_NONE;
  }
  forceinline PropModEvent
  UniverseView::pme(ModEvent me) {
    return SetVarImp::pme(me);
  }

  forceinline void
  UniverseView::update(Space* home, bool, UniverseView&) {}




  /*
   * Iterators
   *
   */

  /**
   * \brief %Range iterator for least upper bound of constantly empty set view
   * \ingroup TaskActorSetView
   */
  template <>
  class LubRanges<EmptyView> : public Iter::Ranges::Empty {
  public:
    /// \name Constructors and initialization
    //@{
    /// Default constructor
    LubRanges(void) {}
    /// Initialize with ranges for view \a x
    LubRanges(const EmptyView& x) {}
    /// Initialize with ranges for view \a x
    void init(const EmptyView& x) {}
    //@}
  };

  /**
   * \brief %Range iterator for greatesr lower bound of constantly empty set view
   * \ingroup TaskActorSetView
   */
  template <>
  class GlbRanges<EmptyView> : public Iter::Ranges::Empty {
  public:
    /// \name Constructors and initialization
    //@{
    /// Default constructor
    GlbRanges(void) {}
    /// Initialize with ranges for view \a x
    GlbRanges(const EmptyView& x) {}
    /// Initialize with ranges for view \a x
    void init(const EmptyView& x) {}
    //@}
  };

  /**
   * \brief %Range iterator for least upper bound of constant universe set view
   * \ingroup TaskActorSetView
   */
  template <>
  class LubRanges<UniverseView> : public Iter::Ranges::Singleton {
  public:
    /// \name Constructors and initialization
    //@{
    /// Default constructor
    LubRanges(void)
      : Iter::Ranges::Singleton(Limits::Set::int_min,
				Limits::Set::int_max) {}
    /// Initialize with ranges for view \a x
    LubRanges(const UniverseView& x)
      : Iter::Ranges::Singleton(Limits::Set::int_min,
				Limits::Set::int_max) {}
    /// Initialize with ranges for view \a x
    void init(const UniverseView& x) {}
    //@}
  };

  /**
   * \brief %Range iterator for greatest lower bound of constant universe set view
   * \ingroup TaskActorSetView
   */
  template <>
  class GlbRanges<UniverseView> : public Iter::Ranges::Singleton {
  public:
    /// \name Constructors and initialization
    //@{
    /// Default constructor
    GlbRanges(void)
      : Iter::Ranges::Singleton(Limits::Set::int_min,
				Limits::Set::int_max) {}
    /// Initialize with ranges for view \a x
    GlbRanges(const UniverseView& x)
      : Iter::Ranges::Singleton(Limits::Set::int_min,
				Limits::Set::int_max) {}
    /// Initialize with ranges for view \a x
    void init(const UniverseView& x) {}
    //@}
  };


  /**
   * \brief %Range iterator for least upper bound of constant set view
   * \ingroup TaskActorSetView
   */
  template <>
  class LubRanges<ConstantView> {
  private:
    ArrayRanges ar;
  public:
    /// \name Constructors and initialization
    //@{
    /// Default constructor
    LubRanges(void) {}
    /// Initialize with ranges for view \a x
    LubRanges(const ConstantView& x) : ar(x.ranges,x.size) {}
    /// Initialize with ranges for view \a x
    void init(const ConstantView& x) {
      ar.init(x.ranges,x.size);
    }
    //@}

    /// \name Iteration control
    //@{
    /// Test whether iterator is still at a value or done
    bool operator()(void) const { return ar(); }
    /// Move iterator to next value (if possible)
    void operator++(void) { ++ar; }
    //@}

    /// \name Range access
    //@{
    /// Return smallest value of range
    int min(void) const { return ar.min(); }
    /// Return largest value of range
    int max(void) const { return ar.max(); }
    /// Return width of range (distance between minimum and maximum)
    unsigned int width(void) const { return ar.width(); }
    //@}
  };

  /**
   * \brief %Range iterator for greatest lower bound of constant set view
   * \ingroup TaskActorSetView
   */
  template <>
  class GlbRanges<ConstantView> : public LubRanges<ConstantView> {
  public:
    /// \name Constructors and initialization
    //@{
    /// Default constructor
    GlbRanges(void) {}
    /// Initialize with ranges for view \a x
    GlbRanges(const ConstantView& x) : LubRanges<ConstantView>(x) {}
    /// Initialize with ranges for view \a x
    void init(const ConstantView& x) {
      LubRanges<ConstantView>::init(x);
    }
    //@}
  };
}


  /*
   * Testing
   *
   */
  forceinline bool
  same(const Set::ConstantView& x, const Set::ConstantView& y) {
    if ((x.size != y.size) || (x.domSize != y.domSize))
      return false;
    for (int i=x.size; i--; )
      if (x.ranges[2*i]   != y.ranges[2*i] ||
	  x.ranges[2*i+1] != y.ranges[2*i+1])
	return false;
    return true;
  }
  forceinline bool
  before(const Set::ConstantView& x, const Set::ConstantView& y) {
    if (x.size < y.size)
      return true;
    if (x.domSize < y.domSize)
      return true;
    for (int i=x.size; i--; )
      if (x.ranges[2*i]   < y.ranges[2*i] ||
	  x.ranges[2*i+1] < y.ranges[2*i+1])
	return true;
    return false;
  }


  forceinline bool
  same(const Set::EmptyView&, const Set::EmptyView&) {
    return true;
  }
  forceinline bool
  before(const Set::EmptyView&, const Set::EmptyView&) {
    return false;
  }

  forceinline bool
  same(const Set::UniverseView&, const Set::UniverseView&) {
    return true;
  }
  forceinline bool
  before(const Set::UniverseView&, const Set::UniverseView&) {
    return false;
  }

}

// STATISTICS: set-var