Generated on Thu Mar 7 2013 10:21:29 for Gecode by doxygen 1.8.3.1
int-set-1.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, 2003
8  *
9  * Last modified:
10  * $Date: 2012-02-22 16:04:20 +1100 (Wed, 22 Feb 2012) $ by $Author: tack $
11  * $Revision: 12537 $
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 #include <sstream>
39 
40 namespace Gecode {
41 
42  /*
43  * Integer sets
44  *
45  */
47  IntSet::IntSet(void) {}
48 
56  template<class I>
57  class IntSetInit {
58  public:
59  static void init(IntSet& s, I& i) {
61  int n=0;
62  unsigned int size = 0;
63  while (i()) {
64  d[n].min = i.min(); d[n].max = i.max(); size += i.width();
65  ++n; ++i;
66  }
67  if (n > 0) {
68  IntSet::IntSetObject* o = IntSet::IntSetObject::allocate(n);
69  for (int j=n; j--; )
70  o->r[j]=d[j];
71  o->size = size;
72  s.object(o);
73  }
74  }
75  };
76 
77  template<>
78  class IntSetInit<IntSet> {
79  public:
80  static void init(IntSet& s, const IntSet& i) {
81  s.object(i.object());
82  }
83  };
84 
85  template<class I>
87  IntSetInit<I>::init(*this,i);
88  }
89 
91  IntSet::IntSet(const int r[][2], int n) {
92  init(r,n);
93  }
94 
96  IntSet::IntSet(const int r[], int n) {
97  init(r,n);
98  }
99 
101  IntSet::IntSet(int n, int m) {
102  init(n,m);
103  }
104 
105  forceinline int
106  IntSet::min(int i) const {
107  assert(object() != NULL);
108  return static_cast<IntSetObject*>(object())->r[i].min;
109  }
110 
111  forceinline int
112  IntSet::max(int i) const {
113  assert(object() != NULL);
114  return static_cast<IntSetObject*>(object())->r[i].max;
115  }
116 
117  forceinline unsigned int
118  IntSet::width(int i) const {
119  assert(object() != NULL);
120  IntSetObject* o = static_cast<IntSetObject*>(object());
121  return static_cast<unsigned int>(o->r[i].max-o->r[i].min)+1;
122  }
123 
124  forceinline int
125  IntSet::ranges(void) const {
126  IntSetObject* o = static_cast<IntSetObject*>(object());
127  return (o == NULL) ? 0 : o->n;
128  }
129 
130  forceinline bool
131  IntSet::in(int n) const {
132  IntSetObject* o = static_cast<IntSetObject*>(object());
133  if ((o == NULL) || (n < o->r[0].min) || (n > o->r[o->n-1].max))
134  return false;
135  else
136  return o->in(n);
137  }
138 
139  forceinline int
140  IntSet::min(void) const {
141  IntSetObject* o = static_cast<IntSetObject*>(object());
142  return (o == NULL) ? Int::Limits::max : o->r[0].min;
143  }
144 
145  forceinline int
146  IntSet::max(void) const {
147  IntSetObject* o = static_cast<IntSetObject*>(object());
148  return (o == NULL) ? Int::Limits::min : o->r[o->n-1].max;
149  }
150 
151  forceinline unsigned int
152  IntSet::size(void) const {
153  IntSetObject* o = static_cast<IntSetObject*>(object());
154  return (o == NULL) ? 0 : o->size;
155  }
156 
157  forceinline unsigned int
158  IntSet::width(void) const {
159  return static_cast<unsigned int>(max()-min()+1);
160  }
161 
162 
163  /*
164  * Range iterator for integer sets
165  *
166  */
167 
171  void
173  int n = s.ranges();
174  if (n > 0) {
175  i = &static_cast<IntSet::IntSetObject*>(s.object())->r[0]; e = i+n;
176  } else {
177  i = e = NULL;
178  }
179  }
182 
183 
184  forceinline void
186  i++;
187  }
188  forceinline bool
190  return i<e;
191  }
192 
193  forceinline int
194  IntSetRanges::min(void) const {
195  return i->min;
196  }
197  forceinline int
198  IntSetRanges::max(void) const {
199  return i->max;
200  }
201  forceinline unsigned int
202  IntSetRanges::width(void) const {
203  return static_cast<unsigned int>(i->max - i->min) + 1;
204  }
205 
206  /*
207  * Value iterator for integer sets
208  *
209  */
212 
215  IntSetRanges r(s);
217  }
218 
219  forceinline void
221  IntSetRanges r(s);
223  }
224 
225  template<class Char, class Traits>
226  std::basic_ostream<Char,Traits>&
227  operator <<(std::basic_ostream<Char,Traits>& os, const IntSet& is) {
228  std::basic_ostringstream<Char,Traits> s;
229  s.copyfmt(os); s.width(0);
230  s << '{';
231  for (int i = 0; i < is.ranges(); ) {
232  int min = is.min(i);
233  int max = is.max(i);
234  if (min == max)
235  s << min;
236  else
237  s << min << ".." << max;
238  i++;
239  if (i < is.ranges())
240  s << ',';
241  }
242  s << '}';
243  return os << s.str();
244  }
245 
246 }
247 
248 // STATISTICS: int-var
249