Generated on Sat Feb 7 2015 02:01:23 for Gecode by doxygen 1.8.9.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: 2013-03-11 14:47:11 +0100 (Mon, 11 Mar 2013) $ by $Author: schulte $
11  * $Revision: 13490 $
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:
60  static void init(IntSet& s, I& i) {
62  int n=0;
63  unsigned int size = 0;
64  while (i()) {
65  d[n].min = i.min(); d[n].max = i.max(); size += i.width();
66  ++n; ++i;
67  }
68  if (n > 0) {
69  IntSet::IntSetObject* o = IntSet::IntSetObject::allocate(n);
70  for (int j=n; j--; )
71  o->r[j]=d[j];
72  o->size = size;
73  s.object(o);
74  }
75  }
76  };
77 
79  template<>
80  class IntSetInit<IntSet> {
81  public:
82  static void init(IntSet& s, const IntSet& i) {
83  s.object(i.object());
84  }
85  };
86 
88  template<class I>
90  IntSetInit<I>::init(*this,i);
91  }
92 
94  template<class I>
95  IntSet::IntSet(const I& i) {
96  IntSetInit<I>::init(*this,i);
97  }
98 
100  IntSet::IntSet(const int r[][2], int n) {
101  init(r,n);
102  }
103 
105  IntSet::IntSet(const int r[], int n) {
106  init(r,n);
107  }
108 
110  IntSet::IntSet(int n, int m) {
111  init(n,m);
112  }
113 
114  forceinline int
115  IntSet::min(int i) const {
116  assert(object() != NULL);
117  return static_cast<IntSetObject*>(object())->r[i].min;
118  }
119 
120  forceinline int
121  IntSet::max(int i) const {
122  assert(object() != NULL);
123  return static_cast<IntSetObject*>(object())->r[i].max;
124  }
125 
126  forceinline unsigned int
127  IntSet::width(int i) const {
128  assert(object() != NULL);
129  IntSetObject* o = static_cast<IntSetObject*>(object());
130  return static_cast<unsigned int>(o->r[i].max-o->r[i].min)+1;
131  }
132 
133  forceinline int
134  IntSet::ranges(void) const {
135  IntSetObject* o = static_cast<IntSetObject*>(object());
136  return (o == NULL) ? 0 : o->n;
137  }
138 
139  forceinline bool
140  IntSet::in(int n) const {
141  IntSetObject* o = static_cast<IntSetObject*>(object());
142  if ((o == NULL) || (n < o->r[0].min) || (n > o->r[o->n-1].max))
143  return false;
144  else
145  return o->in(n);
146  }
147 
148  forceinline int
149  IntSet::min(void) const {
150  IntSetObject* o = static_cast<IntSetObject*>(object());
151  return (o == NULL) ? Int::Limits::max : o->r[0].min;
152  }
153 
154  forceinline int
155  IntSet::max(void) const {
156  IntSetObject* o = static_cast<IntSetObject*>(object());
157  return (o == NULL) ? Int::Limits::min : o->r[o->n-1].max;
158  }
159 
160  forceinline unsigned int
161  IntSet::size(void) const {
162  IntSetObject* o = static_cast<IntSetObject*>(object());
163  return (o == NULL) ? 0 : o->size;
164  }
165 
166  forceinline unsigned int
167  IntSet::width(void) const {
168  return static_cast<unsigned int>(max()-min()+1);
169  }
170 
171 
172  /*
173  * Range iterator for integer sets
174  *
175  */
176 
180  void
182  int n = s.ranges();
183  if (n > 0) {
184  i = &static_cast<IntSet::IntSetObject*>(s.object())->r[0]; e = i+n;
185  } else {
186  i = e = NULL;
187  }
188  }
191 
192 
193  forceinline void
195  i++;
196  }
197  forceinline bool
199  return i<e;
200  }
201 
202  forceinline int
203  IntSetRanges::min(void) const {
204  return i->min;
205  }
206  forceinline int
207  IntSetRanges::max(void) const {
208  return i->max;
209  }
210  forceinline unsigned int
211  IntSetRanges::width(void) const {
212  return static_cast<unsigned int>(i->max - i->min) + 1;
213  }
214 
215  /*
216  * Value iterator for integer sets
217  *
218  */
221 
224  IntSetRanges r(s);
226  }
227 
228  forceinline void
230  IntSetRanges r(s);
232  }
233 
234  template<class Char, class Traits>
235  std::basic_ostream<Char,Traits>&
236  operator <<(std::basic_ostream<Char,Traits>& os, const IntSet& is) {
237  std::basic_ostringstream<Char,Traits> s;
238  s.copyfmt(os); s.width(0);
239  s << '{';
240  for (int i = 0; i < is.ranges(); ) {
241  int min = is.min(i);
242  int max = is.max(i);
243  if (min == max)
244  s << min;
245  else
246  s << min << ".." << max;
247  i++;
248  if (i < is.ranges())
249  s << ',';
250  }
251  s << '}';
252  return os << s.str();
253  }
254 
255 }
256 
257 // STATISTICS: int-var
258 
void init(I &i)
Initialize with values from range iterator i.
Range iterator for integer sets.
Definition: int.hh:271
IntSetValues(void)
Default constructor.
Definition: int-set-1.hpp:220
bool in(int n) const
Return whether n is included in the set.
Definition: int-set-1.hpp:140
void operator++(void)
Move iterator to next range (if possible)
Definition: int-set-1.hpp:194
int min(void) const
Return minimum of entire set.
Definition: int-set-1.hpp:149
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:57
void init(const IntSet &s)
Initialize with values for s.
Definition: int-set-1.hpp:229
bool operator()(void) const
Test whether iterator is still at a range or done.
Definition: int-set-1.hpp:198
Array with arbitrary number of elements.
const int max
Largest allowed integer value.
Definition: int.hh:113
unsigned int width(void) const
Return width of set (distance between maximum and minimum)
Definition: int-set-1.hpp:167
void init(const IntSet &s)
Initialize with ranges for set s.
Definition: int-set-1.hpp:181
const int min
Smallest allowed integer value.
Definition: int.hh:115
static void init(IntSet &s, const IntSet &i)
Definition: int-set-1.hpp:82
Heap heap
The single global heap.
Definition: heap.cpp:49
Gecode::IntSet d(v, 7)
Gecode::IntArgs i(4, 1, 2, 3, 4)
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
static void init(IntSet &s, I &i)
Initialize s with iterator i.
Definition: int-set-1.hpp:60
NNF * r
Right subtree.
Definition: bool-expr.cpp:246
int ranges(void) const
Return number of ranges of the specification.
Definition: int-set-1.hpp:134
unsigned int size(I &i)
Size of all ranges of range iterator i.
unsigned int width(int i) const
Return width of range at position i.
Definition: int-set-1.hpp:127
int min(void) const
Return smallest value of range.
Definition: int-set-1.hpp:203
Integer set initialization.
Definition: int-set-1.hpp:57
Integer sets.
Definition: int.hh:171
unsigned int size(void) const
Return size (cardinality) of set.
Definition: int-set-1.hpp:161
IntSet(void)
Initialize as empty set.
Definition: int-set-1.hpp:47
unsigned int width(void) const
Return width of range (distance between minimum and maximum)
Definition: int-set-1.hpp:211
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:75
int max(void) const
Return largest value of range.
Definition: int-set-1.hpp:207
SharedHandle::Object * object(void) const
Access to the shared object.
Definition: core.hpp:2619
#define forceinline
Definition: config.hpp:132
Gecode toplevel namespace
int max(void) const
Return maximum of entire set.
Definition: int-set-1.hpp:155
IntSetRanges(void)
Default constructor.
Definition: int-set-1.hpp:178