Generated on Sat Feb 7 2015 02:01:23 for Gecode by doxygen 1.8.9.1
int-set.cpp
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: 2009-12-02 20:42:32 +0100 (Wed, 02 Dec 2009) $ by $Author: schulte $
11  * $Revision: 10174 $
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 <gecode/int.hh>
39 
40 namespace Gecode {
41 
42  IntSet::IntSetObject*
43  IntSet::IntSetObject::allocate(int n) {
44  IntSetObject* o = new IntSetObject;
45  o->n = n;
46  o->r = heap.alloc<Range>(n);
47  return o;
48  }
49 
50  SharedHandle::Object*
51  IntSet::IntSetObject::copy(void) const {
52  IntSetObject* o = allocate(n);
53  o->size = size;
54  for (int i=n; i--; )
55  o->r[i]=r[i];
56  return o;
57  }
58 
59  bool
60  IntSet::IntSetObject::in(int n) const {
61  int l = 0;
62  int r = this->n - 1;
63 
64  while (l <= r) {
65  int m = l + (r - l) / 2;
66  if ((this->r[m].min <= n) && (n <= this->r[m].max)) {
67  return true;
68  } else if (l == r) {
69  return false;
70  } else if (n < this->r[m].min) {
71  r=m-1;
72  } else {
73  l=m+1;
74  }
75  }
76  return false;
77  }
78 
79  IntSet::IntSetObject::~IntSetObject(void) {
80  heap.free<Range>(r,n);
81  }
82 
85  public:
86  bool operator ()(const Range &x, const Range &y);
87  };
88 
89  forceinline bool
90  IntSet::MinInc::operator ()(const Range &x, const Range &y) {
91  return x.min < y.min;
92  }
93 
94  void
95  IntSet::normalize(Range* r, int n) {
96  if (n > 0) {
97  // Sort ranges
98  {
99  MinInc lt_mi;
100  Support::quicksort<Range>(r, n, lt_mi);
101  }
102  // Conjoin continuous ranges
103  {
104  int min = r[0].min;
105  int max = r[0].max;
106  int i = 1;
107  int j = 0;
108  while (i < n) {
109  if (max+1 < r[i].min) {
110  r[j].min = min; r[j].max = max; j++;
111  min = r[i].min; max = r[i].max; i++;
112  } else {
113  max = std::max(max,r[i].max); i++;
114  }
115  }
116  r[j].min = min; r[j].max = max;
117  n=j+1;
118  }
119  IntSetObject* o = IntSetObject::allocate(n);
120  unsigned int s = 0;
121  for (int i=n; i--; ) {
122  s += static_cast<unsigned int>(r[i].max-r[i].min+1);
123  o->r[i]=r[i];
124  }
125  o->size = s;
126  object(o);
127  }
128  }
129 
130  void
131  IntSet::init(const int r[], int n) {
132  Range* dr = heap.alloc<Range>(n);
133  for (int i=n; i--; ) {
134  dr[i].min=r[i]; dr[i].max=r[i];
135  }
136  normalize(&dr[0],n);
137  heap.free(dr,n);
138  }
139 
140  void
141  IntSet::init(const int r[][2], int n) {
142  Range* dr = heap.alloc<Range>(n);
143  int j = 0;
144  for (int i=n; i--; )
145  if (r[i][0] <= r[i][1]) {
146  dr[j].min=r[i][0]; dr[j].max=r[i][1]; j++;
147  }
148  normalize(&dr[0],j);
149  heap.free(dr,n);
150  }
151 
152  void
153  IntSet::init(int n, int m) {
154  if (n <= m) {
155  IntSetObject* o = IntSetObject::allocate(1);
156  o->r[0].min = n; o->r[0].max = m;
157  o->size = static_cast<unsigned int>(m - n + 1);
158  object(o);
159  }
160  }
161 
162  const IntSet IntSet::empty;
163 
164 }
165 
166 // STATISTICS: int-var
167 
NNF * l
Left subtree.
Definition: bool-expr.cpp:244
const FloatNum max
Largest allowed float value.
Definition: float.hh:831
int min(void) const
Return minimum of entire set.
Definition: int-set-1.hpp:149
bool operator()(const Range &x, const Range &y)
Definition: int-set.cpp:90
Heap heap
The single global heap.
Definition: heap.cpp:49
T * alloc(long unsigned int n)
Allocate block of n objects of type T from heap.
Definition: heap.hpp:400
Gecode::IntArgs i(4, 1, 2, 3, 4)
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
NNF * r
Right subtree.
Definition: bool-expr.cpp:246
unsigned int size(I &i)
Size of all ranges of range iterator i.
static const IntSet empty
Empty set.
Definition: int.hh:262
IntSet(void)
Initialize as empty set.
Definition: int-set-1.hpp:47
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:75
void free(T *b, long unsigned int n)
Delete n objects starting at b.
Definition: heap.hpp:426
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:253
SharedHandle::Object * object(void) const
Access to the shared object.
Definition: core.hpp:2619
#define forceinline
Definition: config.hpp:132
Sort ranges according to increasing minimum.
Definition: int-set.cpp:84
Gecode toplevel namespace
int max(void) const
Return maximum of entire set.
Definition: int-set-1.hpp:155