Generated on Tue Jul 27 2010 21:59:16 for Gecode by doxygen 1.7.1

ranges-operations.hpp

Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Christian Schulte <schulte@gecode.org>
00005  *
00006  *  Copyright:
00007  *     Christian Schulte, 2004
00008  *
00009  *  Last modified:
00010  *     $Date: 2009-11-24 20:31:15 +0100 (Tue, 24 Nov 2009) $ by $Author: schulte $
00011  *     $Revision: 10113 $
00012  *
00013  *  This file is part of Gecode, the generic constraint
00014  *  development environment:
00015  *     http://www.gecode.org
00016  *
00017  *  Permission is hereby granted, free of charge, to any person obtaining
00018  *  a copy of this software and associated documentation files (the
00019  *  "Software"), to deal in the Software without restriction, including
00020  *  without limitation the rights to use, copy, modify, merge, publish,
00021  *  distribute, sublicense, and/or sell copies of the Software, and to
00022  *  permit persons to whom the Software is furnished to do so, subject to
00023  *  the following conditions:
00024  *
00025  *  The above copyright notice and this permission notice shall be
00026  *  included in all copies or substantial portions of the Software.
00027  *
00028  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00029  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00030  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00031  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00032  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00033  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00034  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00035  *
00036  */
00037 
00038 namespace Gecode { namespace Iter { namespace Ranges {
00039 
00047 
00048   template<class I>
00049   unsigned int size(I& i);
00050 
00052   template<class I, class J>
00053   bool equal(I& i, J& j);
00054 
00056   template<class I, class J>
00057   bool subset(I& i, J& j);
00058 
00060   template<class I, class J>
00061   bool disjoint(I& i, J& j);
00062 
00064   enum CompareStatus {
00065     CS_SUBSET,   
00066     CS_DISJOINT, 
00067     CS_NONE      
00068   };
00069 
00071   template<class I, class J>
00072   CompareStatus compare(I& i, J& j);
00074 
00075 
00076   template<class I>
00077   inline unsigned int
00078   size(I& i) {
00079     IsRangeIter<I>();
00080     unsigned int s = 0;
00081     while (i()) {
00082       s += i.width(); ++i;
00083     }
00084     return s;
00085   }
00086 
00087   template<class I, class J>
00088   forceinline bool
00089   equal(I& i, J& j) {
00090     IsRangeIter<I>();
00091     IsRangeIter<J>();
00092     // Are i and j equal?
00093     while (i() && j())
00094       if ((i.min() == j.min()) && (i.max() == j.max())) {
00095         ++i; ++j;
00096       } else {
00097         return false;
00098       }
00099     return !i() && !j();
00100   }
00101 
00102   template<class I, class J>
00103   forceinline bool
00104   subset(I& i, J& j) {
00105     IsRangeIter<I>();
00106     IsRangeIter<J>();
00107     // Is i subset of j?
00108     while (i() && j())
00109       if (j.max() < i.min()) {
00110         ++j;
00111       } else if ((i.min() >= j.min()) && (i.max() <= j.max())) {
00112         ++i;
00113       } else {
00114         return false;
00115       }
00116     return !i();
00117   }
00118 
00119   template<class I, class J>
00120   forceinline bool
00121   disjoint(I& i, J& j) {
00122     IsRangeIter<I>();
00123     IsRangeIter<J>();
00124     // Are i and j disjoint?
00125     while (i() && j())
00126       if (j.max() < i.min()) {
00127         ++j;
00128       } else if (i.max() < j.min()) {
00129         ++i;
00130       } else {
00131         return false;
00132       }
00133     return true;
00134   }
00135 
00136   template<class I, class J>
00137   forceinline CompareStatus
00138   compare(I& i, J& j) {
00139     IsRangeIter<I>();
00140     IsRangeIter<J>();
00141     bool subset = true;
00142     bool disjoint = true;
00143     while (i() && j()) {
00144       if (j.max() < i.min()) {
00145         ++j;
00146       } else if (i.max() < j.min()) {
00147         ++i; subset = false;
00148       } else if ((i.min() >= j.min()) && (i.max() <= j.max())) {
00149         ++i; disjoint = false;
00150       } else if (i.max() <= j.max()) {
00151         ++i; disjoint = false; subset = false;
00152       } else if (j.max() <= i.max()) {
00153         ++j; disjoint = false; subset = false;
00154       }
00155     }
00156     if (i())
00157       subset = false;
00158     if (subset)
00159       return CS_SUBSET;
00160     return disjoint ? CS_DISJOINT : CS_NONE;
00161   }
00162 
00163 }}}
00164 
00165 // STATISTICS: iter-any
00166