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