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