/*
 *  Main authors:
 *     Christian Schulte <schulte@gecode.org>
 *
 *  Copyright:
 *     Christian Schulte, 2004
 *
 *  Last modified:
 *     $Date: 2006-04-11 15:58:37 +0200 (Tue, 11 Apr 2006) $ by $Author: tack $
 *     $Revision: 3188 $
 *
 *  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 Iter { namespace Ranges {

  /**
   * \defgroup FuncIterRangesOp Operations on range iterators
   *
   * Requires \code #include "gecode/iter.hh" \endcode
   * \ingroup FuncIterRanges
   */

  //@{
  /// Size of all ranges of range iterator \a i
  template <class I>
  unsigned int size(I& i);

  /// Check whether range iterators \a i and \a j are equal
  template <class I, class J>
  bool equal(I& i, J& j);

  /// Check whether range iterator \a i is subset of range iterator \a j
  template <class I, class J>
  bool subset(I& i, J& j);

  /// Check whether range iterators \a i and \a j are disjoint
  template <class I, class J>
  bool disjoint(I& i, J& j);

  /// Is one iterator subsumed by another, or is the intersection empty?
  enum SubsumtionStatus {
    SS_SUBSUMED, ///< Subsumed (subset)
    SS_EMPTY,    ///< Intersection is empty
    SS_NONE      ///< Neither of the above
  };

  /// Check whether range iterator \a i subsumes \a j, or whether intersection is empty
  template <class I, class J>
  SubsumtionStatus subsumes(I& i, J& j);
  //@}


  template <class I>
  inline unsigned int
  size(I& i) {
    unsigned int s = 0;
    while (i()) {
      s += i.width(); ++i;
    }
    return s;
  }

  template <class I, class J>
  forceinline bool
  equal(I& i, J& j) {
    // Are i and j equal?
    while (i() && j())
      if ((i.min() == j.min()) && (i.max() == j.max())) {
	++i; ++j;
      } else {
	return false;
      }
    return !i() && !j();
  }

  template <class I, class J>
  forceinline bool
  subset(I& i, J& j) {
    // Is i subset of j?
    while (i() && j())
      if (j.max() < i.min()) {
	++j;
      } else if ((i.min() >= j.min()) && (i.max() <= j.max())) {
	++i;
      } else {
	return false;
      }
    return !i();
  }

  template <class I, class J>
  forceinline bool
  disjoint(I& i, J& j) {
    // Are i and j disjoint?
    while (i() && j())
      if (j.max() < i.min()) {
	++j;
      } else if (i.max() < j.min()) {
	++i;
      } else {
	return false;
      }
    return true;
  }

  template <class I, class J>
  inline SubsumtionStatus
  subsumes(I& i, J& j) {
    bool subsumed = true;
    bool empty    = true;
    while (i() && j()) {
      if (i.max() < j.min()) {
	++i;
      } else if (j.max() < i.min()) {
	++j; subsumed = false;
      } else if ((j.min() >= i.min()) && (j.max() <= i.max())) {
	++j; empty = false;
      } else if (j.max() <= i.max()) {
	++j; empty = false; subsumed = false;
      } else if (i.max() <= j.max()) {
	++i; empty = false; subsumed = false;
      }
    }
    if (j())
      subsumed = false;
    if (subsumed)
      return SS_SUBSUMED;
    return empty ? SS_EMPTY : SS_NONE;
  }

}}}

// STATISTICS: iter-any