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 *
6 * Copyright:
7 * Christian Schulte, 2010
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
36 /**
37 * \brief Iterator over range lists
38 *
39 * \ingroup FuncIterRanges
40 */
41 class RangeListIter {
42 protected:
43 /// Range list class
44 class RangeList : public Support::BlockClient<RangeList,Region> {
45 public:
46 /// Minimum and maximum of a range
47 int min, max;
48 /// Next element
49 RangeList* next;
50 };
51 /// Shared object for allocation
52 class RLIO : public Support::BlockAllocator<RangeList,Region> {
53 public:
54 /// Counter used for reference counting
55 unsigned int use_cnt;
56 /// Initialize
57 RLIO(Region& r);
58 };
59 /// Reference to shared object
60 RLIO* rlio;
61 /// Head of range list
62 RangeList* h;
63 /// Current list element
64 RangeList* c;
65 /// Set range lists
66 void set(RangeList* l);
67 /// Get head of current range list
68 RangeList* get(void) const;
69 /// Create new range possibly from freelist \a f and init
70 RangeList* range(int min, int max, RangeList*& f);
71 /// Create new range possibly and init
72 RangeList* range(int min, int max);
73 /// Create new range possibly from freelist \a f and init
74 template<class I>
75 RangeList* range(I& i, RangeList*& f);
76 /// Create new range possibly and init
77 template<class I>
78 RangeList* range(I& i);
79 /// Copy the iterator \a i to a range list
80 template<class I>
81 RangeList* copy(I& i);
82 public:
83 /// \name Constructors and initialization
84 //@{
85 /// Default constructor
86 RangeListIter(void);
87 /// Copy constructor
88 RangeListIter(const RangeListIter& i);
89 /// Initialize
90 RangeListIter(Region& r);
91 /// Initialize
92 void init(Region& r);
93 /// Assignment operator
94 RangeListIter& operator =(const RangeListIter& i);
95 //@}
96
97 /// \name Iteration control
98 //@{
99 /// Test whether iterator is still at a range or done
100 bool operator ()(void) const;
101 /// Move iterator to next range (if possible)
102 void operator ++(void);
103 /// Reset iterator to start
104 void reset(void);
105 //@}
106
107 /// \name Range access
108 //@{
109 /// Return smallest value of range
110 int min(void) const;
111 /// Return largest value of range
112 int max(void) const;
113 /// Return width of range (distance between minimum and maximum)
114 unsigned int width(void) const;
115 //@}
116
117 /// Destructor
118 ~RangeListIter(void);
119 };
120
121
122 forceinline
123 RangeListIter::RLIO::RLIO(Region& r)
124 : Support::BlockAllocator<RangeList,Region>(r), use_cnt(1) {}
125
126
127 forceinline
128 RangeListIter::RangeListIter(void)
129 : rlio(nullptr), h(nullptr), c(nullptr) {}
130
131 forceinline
132 RangeListIter::RangeListIter(Region& r)
133 : rlio(new (r.ralloc(sizeof(RLIO))) RLIO(r)), h(nullptr), c(nullptr) {}
134
135 forceinline void
136 RangeListIter::init(Region& r) {
137 rlio = new (r.ralloc(sizeof(RLIO))) RLIO(r);
138 h = c = nullptr;
139 }
140
141 forceinline
142 RangeListIter::RangeListIter(const RangeListIter& i)
143 : rlio(i.rlio), h(i.h), c(i.c) {
144 if (rlio != nullptr)
145 rlio->use_cnt++;
146 }
147
148 forceinline RangeListIter&
149 RangeListIter::operator =(const RangeListIter& i) {
150 if (&i != this) {
151 if ((rlio != nullptr) && (--rlio->use_cnt == 0)) {
152 Region& r = rlio->allocator();
153 rlio->~RLIO();
154 r.rfree(rlio,sizeof(RLIO));
155 }
156 rlio = i.rlio;
157 if (rlio != nullptr)
158 rlio->use_cnt++;
159 c=i.c; h=i.h;
160 }
161 return *this;
162 }
163
164 forceinline
165 RangeListIter::~RangeListIter(void) {
166 if ((rlio != nullptr) && (--rlio->use_cnt == 0)) {
167 Region& r = rlio->allocator();
168 rlio->~RLIO();
169 r.rfree(rlio,sizeof(RLIO));
170 }
171 }
172
173
174 forceinline void
175 RangeListIter::set(RangeList* l) {
176 h = c = l;
177 }
178
179 forceinline RangeListIter::RangeList*
180 RangeListIter::get(void) const {
181 return h;
182 }
183
184 forceinline RangeListIter::RangeList*
185 RangeListIter::range(int min, int max, RangeList*& f) {
186 RangeList* t;
187 // Take element from freelist if possible
188 if (f != nullptr) {
189 t = f; f = f->next;
190 } else {
191 t = new (*rlio) RangeList;
192 }
193 t->min = min; t->max = max;
194 return t;
195 }
196
197 forceinline RangeListIter::RangeList*
198 RangeListIter::range(int min, int max) {
199 RangeList* t = new (*rlio) RangeList;
200 t->min = min; t->max = max;
201 return t;
202 }
203
204 template<class I>
205 forceinline RangeListIter::RangeList*
206 RangeListIter::range(I& i, RangeList*& f) {
207 return range(i.min(),i.max(),f);
208 }
209
210 template<class I>
211 forceinline RangeListIter::RangeList*
212 RangeListIter::range(I& i) {
213 return range(i.min(),i.max());
214 }
215
216 template<class I>
217 inline RangeListIter::RangeList*
218 RangeListIter::copy(I& i) {
219 RangeList* h;
220 RangeList** c = &h;
221 for ( ; i(); ++i) {
222 RangeList* t = range(i);
223 *c = t; c = &t->next;
224 }
225 *c = nullptr;
226 return h;
227 }
228
229 forceinline bool
230 RangeListIter::operator ()(void) const {
231 return c != nullptr;
232 }
233
234 forceinline void
235 RangeListIter::operator ++(void) {
236 c = c->next;
237 }
238
239 forceinline void
240 RangeListIter::reset(void) {
241 c = h;
242 }
243
244 forceinline int
245 RangeListIter::min(void) const {
246 return c->min;
247 }
248 forceinline int
249 RangeListIter::max(void) const {
250 return c->max;
251 }
252 forceinline unsigned int
253 RangeListIter::width(void) const {
254 return static_cast<unsigned int>(c->max-c->min)+1;
255 }
256
257}}}
258
259// STATISTICS: iter-any
260