Generated on Thu Jan 16 2025 00:00:00 for Gecode by doxygen 1.14.0
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
34namespace Gecode { namespace Iter { namespace Ranges {
35
41
42 template<class I, class J>
43 class Diff : public MinMax {
44 protected:
46 I i;
48 J j;
49 public:
51
52
53 Diff(void);
55 Diff(I& i, J& j);
57 void init(I& i, J& j);
59
61
62
63 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
Diff(void)
Default constructor.
Diff(I &i, J &j)
Initialize with iterator i and j.
void init(I &i, J &j)
Initialize with iterator i and j.
void operator++(void)
Move iterator to next range (if possible)
int ma
Maximum of current range.
int mi
Minimum of current range.
MinMax(void)
Default constructor.
void finish(void)
Set range such that iteration stops
Range iterators.
Definition iter.hh:43
Range and value iterators.
Definition iter.hh:41
Gecode toplevel namespace
#define forceinline
Definition config.hpp:194