Generated on Thu Apr 5 2018 19:44:19 for Gecode by doxygen 1.8.13
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$ by $Author$
11  * $Revision$
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  bool
51  IntSet::IntSetObject::in(int n) const {
52  int l = 0;
53  int r = this->n - 1;
54 
55  while (l <= r) {
56  int m = l + (r - l) / 2;
57  if ((this->r[m].min <= n) && (n <= this->r[m].max)) {
58  return true;
59  } else if (l == r) {
60  return false;
61  } else if (n < this->r[m].min) {
62  r=m-1;
63  } else {
64  l=m+1;
65  }
66  }
67  return false;
68  }
69 
70  IntSet::IntSetObject::~IntSetObject(void) {
71  heap.free<Range>(r,n);
72  }
73 
76  public:
77  bool operator ()(const Range &x, const Range &y);
78  };
79 
80  forceinline bool
81  IntSet::MinInc::operator ()(const Range &x, const Range &y) {
82  return x.min < y.min;
83  }
84 
85  void
86  IntSet::normalize(Range* r, int n) {
87  if (n > 0) {
88  // Sort ranges
89  {
90  MinInc lt_mi;
91  Support::quicksort<Range>(r, n, lt_mi);
92  }
93  // Conjoin continuous ranges
94  {
95  int min = r[0].min;
96  int max = r[0].max;
97  int i = 1;
98  int j = 0;
99  while (i < n) {
100  if (max+1 < r[i].min) {
101  r[j].min = min; r[j].max = max; j++;
102  min = r[i].min; max = r[i].max; i++;
103  } else {
104  max = std::max(max,r[i].max); i++;
105  }
106  }
107  r[j].min = min; r[j].max = max;
108  n=j+1;
109  }
110  IntSetObject* o = IntSetObject::allocate(n);
111  unsigned int s = 0;
112  for (int i=n; i--; ) {
113  s += static_cast<unsigned int>(r[i].max-r[i].min+1);
114  o->r[i]=r[i];
115  }
116  o->size = s;
117  object(o);
118  }
119  }
120 
121  void
122  IntSet::init(const int r[], int n) {
123  Range* dr = heap.alloc<Range>(n);
124  for (int i=n; i--; ) {
125  dr[i].min=r[i]; dr[i].max=r[i];
126  }
127  normalize(&dr[0],n);
128  heap.free(dr,n);
129  }
130 
131  void
132  IntSet::init(const int r[][2], int n) {
133  Range* dr = heap.alloc<Range>(n);
134  int j = 0;
135  for (int i=n; i--; )
136  if (r[i][0] <= r[i][1]) {
137  dr[j].min=r[i][0]; dr[j].max=r[i][1]; j++;
138  }
139  normalize(&dr[0],j);
140  heap.free(dr,n);
141  }
142 
143  void
144  IntSet::init(int n, int m) {
145  if (n <= m) {
146  IntSetObject* o = IntSetObject::allocate(1);
147  o->r[0].min = n; o->r[0].max = m;
148  o->size = static_cast<unsigned int>(m - n + 1);
149  object(o);
150  }
151  }
152 
153  const IntSet IntSet::empty;
154 
155 }
156 
157 // STATISTICS: int-var
158 
int max(void) const
Return maximum of entire set.
Definition: int-set-1.hpp:155
NNF * l
Left subtree.
Definition: bool-expr.cpp:244
const FloatNum max
Largest allowed float value.
Definition: float.hh:848
#define forceinline
Definition: config.hpp:182
bool operator()(const Range &x, const Range &y)
Definition: int-set.cpp:81
T * alloc(long unsigned int n)
Allocate block of n objects of type T from heap.
Definition: heap.hpp:435
Gecode::IntArgs i(4, 1, 2, 3, 4)
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
SharedHandle::Object * object(void) const
Access to the shared object.
Integer sets.
Definition: int.hh:174
static const IntSet empty
Empty set.
Definition: int.hh:263
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:769
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:71
Post propagator for SetVar SetOpType SetVar y
Definition: set.hh:769
void free(T *b, long unsigned int n)
Delete n objects starting at b.
Definition: heap.hpp:461
int min(void) const
Return minimum of entire set.
Definition: int-set-1.hpp:149
Heap heap
The single global heap.
Definition: heap.cpp:48
Sort ranges according to increasing minimum.
Definition: int-set.cpp:75
Post propagator for SetVar x
Definition: set.hh:769
Gecode toplevel namespace