Generated on Sat Feb 7 2015 02:01:26 for Gecode by doxygen 1.8.9.1
ranges-diff.hpp
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * Christian Schulte <schulte@gecode.org>
5  *
6  * Copyright:
7  * Christian Schulte, 2004
8  *
9  * Last modified:
10  * $Date: 2010-07-28 17:35:33 +0200 (Wed, 28 Jul 2010) $ by $Author: schulte $
11  * $Revision: 11294 $
12  *
13  * This file is part of Gecode, the generic constraint
14  * development environment:
15  * http://www.gecode.org
16  *
17  * Permission is hereby granted, free of charge, to any person obtaining
18  * a copy of this software and associated documentation files (the
19  * "Software"), to deal in the Software without restriction, including
20  * without limitation the rights to use, copy, modify, merge, publish,
21  * distribute, sublicense, and/or sell copies of the Software, and to
22  * permit persons to whom the Software is furnished to do so, subject to
23  * the following conditions:
24  *
25  * The above copyright notice and this permission notice shall be
26  * included in all copies or substantial portions of the Software.
27  *
28  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
29  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
30  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
31  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
32  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
33  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
34  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35  *
36  */
37 
38 namespace Gecode { namespace Iter { namespace Ranges {
39 
46  template<class I, class J>
47  class Diff : public MinMax {
48  protected:
50  I i;
52  J j;
53  public:
55 
56  Diff(void);
59  Diff(I& i, J& j);
61  void init(I& i, J& j);
63 
65 
66  void operator ++(void);
69  };
70 
71 
72 
73  template<class I, class J>
74  forceinline void
76  // Precondition: mi <= ma
77  // Task: find next mi greater than ma
78  while (true) {
79  if (!i()) break;
80  mi = ma+1;
81  ma = i.max();
82  if (mi > i.max()) {
83  ++i;
84  if (!i()) break;
85  mi = i.min();
86  ma = i.max();
87  }
88  while (j() && (j.max() < mi))
89  ++j;
90  if (j() && (j.min() <= ma)) {
91  // Now the interval [mi ... ma] must be shrunken
92  // Is [mi ... ma] completely consumed?
93  if ((mi >= j.min()) && (ma <= j.max()))
94  continue;
95  // Does [mi ... ma] overlap on the left?
96  if (j.min() <= mi) {
97  mi = j.max()+1;
98  // Search for max!
99  ++j;
100  if (j() && (j.min() <= ma))
101  ma = j.min()-1;
102  } else {
103  ma = j.min()-1;
104  }
105  }
106  return;
107  }
108  finish();
109  }
110 
111  template<class I, class J>
114 
115  template<class I, class J>
117  Diff<I,J>::Diff(I& i0, J& j0)
118  : i(i0), j(j0) {
119  if (!i()) {
120  finish();
121  } else {
122  mi = i.min()-1; ma = mi;
123  operator ++();
124  }
125  }
126 
127  template<class I, class J>
128  forceinline void
129  Diff<I,J>::init(I& i0, J& j0) {
130  i = i0; j = j0;
131  if (!i()) {
132  finish();
133  } else {
134  mi = i.min()-1; ma = mi;
135  operator ++();
136  }
137  }
138 
139 }}}
140 
141 // STATISTICS: iter-any
142 
J j
Iterator to be subtracted.
Definition: ranges-diff.hpp:52
Diff(void)
Default constructor.
void operator++(void)
Move iterator to next range (if possible)
Definition: ranges-diff.hpp:75
I i
Iterator from which to subtract.
Definition: ranges-diff.hpp:50
Base for range iterators with explicit min and max.
Gecode::IntArgs i(4, 1, 2, 3, 4)
void finish(void)
Set range such that iteration stops
int mi
Minimum of current range.
#define forceinline
Definition: config.hpp:132
Gecode toplevel namespace
Range iterator for computing set difference.
Definition: ranges-diff.hpp:47
void init(I &i, J &j)
Initialize with iterator i and j.
int ma
Maximum of current range.