ranges-operations.icc

00001 /*
00002  *  Main authors:
00003  *     Christian Schulte <schulte@gecode.org>
00004  *
00005  *  Copyright:
00006  *     Christian Schulte, 2004
00007  *
00008  *  Last modified:
00009  *     $Date: 2006-04-11 15:58:37 +0200 (Tue, 11 Apr 2006) $ by $Author: tack $
00010  *     $Revision: 3188 $
00011  *
00012  *  This file is part of Gecode, the generic constraint
00013  *  development environment:
00014  *     http://www.gecode.org
00015  *
00016  *  See the file "LICENSE" for information on usage and
00017  *  redistribution of this file, and for a
00018  *     DISCLAIMER OF ALL WARRANTIES.
00019  *
00020  */
00021 
00022 namespace Gecode { namespace Iter { namespace Ranges {
00023 
00032 
00033   template <class I>
00034   unsigned int size(I& i);
00035 
00037   template <class I, class J>
00038   bool equal(I& i, J& j);
00039 
00041   template <class I, class J>
00042   bool subset(I& i, J& j);
00043 
00045   template <class I, class J>
00046   bool disjoint(I& i, J& j);
00047 
00049   enum SubsumtionStatus {
00050     SS_SUBSUMED, 
00051     SS_EMPTY,    
00052     SS_NONE      
00053   };
00054 
00056   template <class I, class J>
00057   SubsumtionStatus subsumes(I& i, J& j);
00059 
00060 
00061   template <class I>
00062   inline unsigned int
00063   size(I& i) {
00064     unsigned int s = 0;
00065     while (i()) {
00066       s += i.width(); ++i;
00067     }
00068     return s;
00069   }
00070 
00071   template <class I, class J>
00072   forceinline bool
00073   equal(I& i, J& j) {
00074     // Are i and j equal?
00075     while (i() && j())
00076       if ((i.min() == j.min()) && (i.max() == j.max())) {
00077         ++i; ++j;
00078       } else {
00079         return false;
00080       }
00081     return !i() && !j();
00082   }
00083 
00084   template <class I, class J>
00085   forceinline bool
00086   subset(I& i, J& j) {
00087     // Is i subset of j?
00088     while (i() && j())
00089       if (j.max() < i.min()) {
00090         ++j;
00091       } else if ((i.min() >= j.min()) && (i.max() <= j.max())) {
00092         ++i;
00093       } else {
00094         return false;
00095       }
00096     return !i();
00097   }
00098 
00099   template <class I, class J>
00100   forceinline bool
00101   disjoint(I& i, J& j) {
00102     // Are i and j disjoint?
00103     while (i() && j())
00104       if (j.max() < i.min()) {
00105         ++j;
00106       } else if (i.max() < j.min()) {
00107         ++i;
00108       } else {
00109         return false;
00110       }
00111     return true;
00112   }
00113 
00114   template <class I, class J>
00115   inline SubsumtionStatus
00116   subsumes(I& i, J& j) {
00117     bool subsumed = true;
00118     bool empty    = true;
00119     while (i() && j()) {
00120       if (i.max() < j.min()) {
00121         ++i;
00122       } else if (j.max() < i.min()) {
00123         ++j; subsumed = false;
00124       } else if ((j.min() >= i.min()) && (j.max() <= i.max())) {
00125         ++j; empty = false;
00126       } else if (j.max() <= i.max()) {
00127         ++j; empty = false; subsumed = false;
00128       } else if (i.max() <= j.max()) {
00129         ++i; empty = false; subsumed = false;
00130       }
00131     }
00132     if (j())
00133       subsumed = false;
00134     if (subsumed)
00135       return SS_SUBSUMED;
00136     return empty ? SS_EMPTY : SS_NONE;
00137   }
00138 
00139 }}}
00140 
00141 // STATISTICS: iter-any
00142