ranges-diff.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-08-04 16:05:50 +0200 (Fri, 04 Aug 2006) $ by $Author: schulte $
00010  *     $Revision: 3515 $
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 
00031   template <class I, class J>
00032   class Diff : public MinMax {
00033   protected:
00035     I i;
00037     J j;
00038   public:
00040 
00041 
00042     Diff(void);
00044     Diff(I& i, J& j);
00046     void init(I& i, J& j);
00048 
00050 
00051 
00052     void operator++(void);
00054   };
00055 
00056 
00057 
00058   template <class I, class J>
00059   forceinline void
00060   Diff<I,J>::operator++(void) {
00061     // Precondition: mi <= ma
00062     // Task: find next mi greater than ma
00063   retry:
00064     if (!i()) goto done;
00065     mi = ma+1;
00066     ma = i.max();
00067     if (mi > i.max()) {
00068       ++i;
00069       if (!i()) goto done;
00070       mi = i.min();
00071       ma = i.max();
00072     }
00073     while (j() && (j.max() < mi))
00074       ++j;
00075     if (j() && (j.min() <= ma)) {
00076       // Now the interval [mi ... ma] must be shrunken
00077       // Is [mi ... ma] completely consumed?
00078       if ((mi >= j.min()) && (ma <= j.max()))
00079         goto retry;
00080       // Does [mi ... ma] overlap on the left?
00081       if (j.min() <= mi) {
00082         mi = j.max()+1;
00083         // Search for max!
00084         ++j;
00085         if (j() && (j.min() <= ma))
00086           ma = j.min()-1;
00087       } else {
00088         ma = j.min()-1;
00089       }
00090     }
00091     return;
00092   done:
00093     finish();
00094   }
00095 
00096   template <class I, class J>
00097   forceinline
00098   Diff<I,J>::Diff(void) {}
00099 
00100   template <class I, class J>
00101   forceinline
00102   Diff<I,J>::Diff(I& i0, J& j0)
00103     : i(i0), j(j0) {
00104     if (!i()) {
00105       finish();
00106     } else {
00107       mi = i.min()-1; ma = mi;
00108       operator++();
00109     }
00110   }
00111 
00112   template <class I, class J>
00113   forceinline void
00114   Diff<I,J>::init(I& i0, J& j0) {
00115     i = i0; j = j0;
00116     if (!i()) {
00117       finish();
00118     } else {
00119       mi = i.min()-1; ma = mi;
00120       operator++();
00121     }
00122   }
00123 
00124 }}}
00125 
00126 // STATISTICS: iter-any
00127