this repo has no description
dekker.one
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Christian Schulte <schulte@gecode.org>
5 * Guido Tack <tack@gecode.org>
6 *
7 * Copyright:
8 * Guido Tack, 2004
9 * Christian Schulte, 2005
10 *
11 * This file is part of Gecode, the generic constraint
12 * development environment:
13 * http://www.gecode.org
14 *
15 * Permission is hereby granted, free of charge, to any person obtaining
16 * a copy of this software and associated documentation files (the
17 * "Software"), to deal in the Software without restriction, including
18 * without limitation the rights to use, copy, modify, merge, publish,
19 * distribute, sublicense, and/or sell copies of the Software, and to
20 * permit persons to whom the Software is furnished to do so, subject to
21 * the following conditions:
22 *
23 * The above copyright notice and this permission notice shall be
24 * included in all copies or substantial portions of the Software.
25 *
26 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
27 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
28 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
29 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
30 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
31 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
32 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
33 *
34 */
35
36namespace Gecode { namespace Iter { namespace Ranges {
37
38 /**
39 * \brief Range iterator for computing the complement (described by template arguments)
40 *
41 * The complement is computed with respect to a given universe set
42 * provided as template arguments (\a UMIN ... \a UMAX). The universe
43 * must always be a superset!
44 *
45 * \ingroup FuncIterRanges
46 */
47
48 template<int UMIN, int UMAX, class I>
49 class Compl : public MinMax {
50 protected:
51 /// Iterator to compute complement for
52 I i;
53 /// Initialize
54 void start(void);
55 public:
56 /// \name Constructors and initialization
57 //@{
58 /// Default constructor
59 Compl(void);
60 /// Initialize with iterator \a i
61 Compl(I& i);
62 /// Initialize with iterator \a i
63 void init(I& i);
64 //@}
65
66 /// \name Iteration control
67 //@{
68 /// Move iterator to next range (if possible)
69 void operator ++(void);
70 //@}
71 };
72
73
74 /**
75 * \brief Range iterator for computing the complement (described by values)
76 *
77 * The complement is computed with respect to a given universe set
78 * provided as arguments upon initialization. The universe
79 * must always be a superset!
80 *
81 * \ingroup FuncIterRanges
82 */
83
84 template<class I>
85 class ComplVal : public MinMax {
86 protected:
87 /// Values describing the universe set
88 int UMIN, UMAX;
89 /// Iterator to compute complement for
90 I i;
91 /// Initialize
92 void start(void);
93 public:
94 /// \name Constructors and initialization
95 //@{
96 /// Default constructor
97 ComplVal(void);
98 /// Initialize with iterator \a i
99 ComplVal(int umin, int umax, I& i);
100 /// Initialize with iterator \a i
101 void init(int umin, int umax, I& i);
102 //@}
103
104 /// \name Iteration control
105 //@{
106 /// Move iterator to next range (if possible)
107 void operator ++(void);
108 //@}
109 };
110
111
112 template<int UMIN, int UMAX, class I>
113 forceinline void
114 Compl<UMIN,UMAX,I>::start(void) {
115 if (i()) {
116 assert((i.min() >= UMIN) && (i.max() <= UMAX));
117 if (i.min() > UMIN) {
118 mi = UMIN;
119 ma = i.min()-1;
120 } else if (i.max() < UMAX) {
121 mi = i.max()+1;
122 ++i;
123 ma = i() ? (i.min()-1) : UMAX;
124 } else {
125 finish();
126 }
127 } else {
128 mi = UMIN;
129 ma = UMAX;
130 }
131 }
132
133 template<int UMIN, int UMAX, class I>
134 forceinline
135 Compl<UMIN,UMAX,I>::Compl(void) {}
136
137 template<int UMIN, int UMAX, class I>
138 forceinline
139 Compl<UMIN,UMAX,I>::Compl(I& i0) : i(i0) {
140 start();
141 }
142
143 template<int UMIN, int UMAX, class I>
144 forceinline void
145 Compl<UMIN,UMAX,I>::init(I& i0) {
146 i=i0; start();
147 }
148
149 template<int UMIN, int UMAX, class I>
150 forceinline void
151 Compl<UMIN,UMAX,I>::operator ++(void) {
152 assert(!i() || (i.max() <= UMAX));
153 if (i() && (i.max() < UMAX)) {
154 mi = i.max()+1;
155 ++i;
156 ma = i() ? (i.min()-1) : UMAX;
157 } else {
158 finish();
159 }
160 }
161
162 template<class I>
163 forceinline void
164 ComplVal<I>::start(void) {
165 if (i()) {
166 assert((i.min() >= UMIN) && (i.max() <= UMAX));
167 if (i.min() > UMIN) {
168 mi = UMIN;
169 ma = i.min()-1;
170 } else if (i.max() < UMAX) {
171 mi = i.max()+1;
172 ++i;
173 ma = i() ? (i.min()-1) : UMAX;
174 } else {
175 finish();
176 }
177 } else {
178 mi = UMIN;
179 ma = UMAX;
180 }
181 }
182
183 template<class I>
184 forceinline
185 ComplVal<I>::ComplVal(void) {}
186
187 template<class I>
188 forceinline
189 ComplVal<I>::ComplVal(int umin, int umax, I& i0)
190 : UMIN(umin), UMAX(umax), i(i0) {
191 start();
192 }
193
194 template<class I>
195 forceinline void
196 ComplVal<I>::init(int umin, int umax, I& i0) {
197 UMIN=umin; UMAX=umax; i=i0; start();
198 }
199
200 template<class I>
201 forceinline void
202 ComplVal<I>::operator ++(void) {
203 assert(!i() || (i.max() <= UMAX));
204 if (i() && (i.max() < UMAX)) {
205 mi = i.max()+1;
206 ++i;
207 ma = i() ? (i.min()-1) : UMAX;
208 } else {
209 finish();
210 }
211 }
212
213}}}
214
215// STATISTICS: iter-any
216