Generated on Tue Feb 11 2025 17:33:26 for Gecode by doxygen 1.12.0
val-set.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, 2011
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
34namespace Gecode { namespace Int {
35
36 /*
37 * Value sets
38 *
39 */
42 : fst(NULL), lst(NULL), n(0) {}
43
44 forceinline void
45 ValSet::add(Space& home, int v) {
46 RangeList* c = fst;
47 RangeList** p = &fst;
48 while (c != NULL) {
49 if (v < c->min()) {
50 if (v+1 == c->min()) {
51 c->min(v); n++;
52 return;
53 } else {
54 *p = new (home) RangeList(v,v,c); n++;
55 return;
56 }
57 } else if (v <= c->max()) {
58 // Value already included
59 return;
60 } else if (v == c->max()+1) {
61 if ((c->next() != NULL) && (v+1 == c->next()->min())) {
62 c->next()->min(c->min());
63 *p = c->next();
64 c->dispose(home,c);
65 } else {
66 c->max(v);
67 }
68 n++;
69 return;
70 } else {
71 // FIXME: HOW TO CAST HERE?
72 p = reinterpret_cast<RangeList**>(c->nextRef());
73 c = *p;
74 }
75 }
76 *p = new (home) RangeList(v,v,NULL); n++;
77 lst = *p;
78 }
79
80 forceinline int
81 ValSet::size(void) const {
82 return n;
83 }
84
85 forceinline bool
86 ValSet::empty(void) const {
87 return n == 0;
88 }
89
90 forceinline int
91 ValSet::min(void) const {
92 return fst->min();
93 }
94
95 forceinline int
96 ValSet::max(void) const {
97 return lst->max();
98 }
99
100 forceinline void
102 if (vs.n > 0) {
103 n = vs.n;
104 // Count number of ranges
105 int m = 0;
106 for (RangeList* c = vs.fst; c != NULL; c = c->next())
107 m++;
108 fst = home.alloc<RangeList>(m);
109 lst = fst + (m-1);
110 int i=0;
111 for (RangeList* c = vs.fst; c != NULL; c = c->next()) {
112 fst[i].min(c->min()); fst[i].max(c->max());
113 fst[i].next(fst+i+1);
114 i++;
115 }
116 lst->next(NULL);
117 }
118 }
119
120 forceinline void
122 fst = lst = NULL;
123 }
124
125 forceinline void
127 if (fst != NULL)
128 fst->dispose(home,lst);
129 }
130
133 : c(vs.fst) {}
134
135 forceinline bool
137 return c != NULL;
138 }
139
140 forceinline void
142 c = c->next();
143 }
144
145 forceinline int
147 return c->min();
148 }
149 forceinline int
151 return c->max();
152 }
153
154 forceinline unsigned int
156 return c->width();
157 }
158
159 template<class View>
161 ValSet::compare(View x) const {
162 if (empty() || (x.max() < min()) || (x.min() > max()))
164 ValSet::Ranges vsr(*this);
166 return Iter::Ranges::compare(xr,vsr);
167 }
168
169 template<class View>
170 forceinline bool
171 ValSet::subset(View x) const {
172 if (empty() || (x.min() < min()) || (x.max() > max()))
173 return false;
174 ValSet::Ranges vsr(*this);
176 return Iter::Ranges::subset(xr,vsr);
177 }
178
179}}
180
181// STATISTICS: int-other
int p
Number of positive literals for node type.
int n
Number of negative literals for node type.
friend FloatVal max(const FloatVal &x, const FloatVal &y)
Definition val.hpp:386
friend FloatVal min(const FloatVal &x, const FloatVal &y)
Definition val.hpp:398
Iterator over ranges.
Definition val-set.hh:78
unsigned int width(void) const
Return width of range (distance between minimum and maximum)
Definition val-set.hpp:155
int max(void) const
Return largest value of range.
Definition val-set.hpp:150
bool operator()(void) const
Test whether iterator is still at a range or done.
Definition val-set.hpp:136
void operator++(void)
Move iterator to next range (if possible)
Definition val-set.hpp:141
Ranges(const ValSet &vs)
Initialize.
Definition val-set.hpp:132
int min(void) const
Return smallest value of range.
Definition val-set.hpp:146
Class for storing values of already assigned views.
Definition val-set.hh:44
int size(void) const
Return size (number of values)
Definition val-set.hpp:81
RangeList * fst
First element of range list.
Definition val-set.hh:47
bool subset(View x) const
Whether all values of x are included in the value set.
Definition val-set.hpp:171
ValSet(void)
Initialize.
Definition val-set.hpp:41
bool empty(void) const
Test whether set is empty.
Definition val-set.hpp:86
int max(void) const
Return largest value (provided the set is not empty)
Definition val-set.hpp:96
Iter::Ranges::CompareStatus compare(View x) const
Compare view x with value set.
Definition val-set.hpp:161
void flush(void)
Flush entries.
Definition val-set.hpp:121
void dispose(Space &home)
Dispose value set.
Definition val-set.hpp:126
void update(Space &home, ValSet &vs)
Update value set during cloning.
Definition val-set.hpp:101
int n
Number of stored values (integer precision is sufficient)
Definition val-set.hh:51
RangeList * lst
Last element of range list.
Definition val-set.hh:49
int min(void) const
Return smallest value (provided the set is not empty)
Definition val-set.hpp:91
void add(Space &home, int v)
Add value v to value set.
Definition val-set.hpp:45
Range iterator for integer views.
Definition view.hpp:54
Lists of ranges (intervals)
int max(void) const
Return maximum.
int min(void) const
Return minimum.
void dispose(Space &home, RangeList *l)
Free memory for all elements between this and l (inclusive)
RangeList * next(void) const
Return next element.
Computation spaces.
Definition core.hpp:1742
T * alloc(long unsigned int n)
Allocate block of n objects of type T from space heap.
Definition core.hpp:2837
CompareStatus
Comapre two iterators with each other.
@ CS_DISJOINT
Intersection is empty.
bool subset(I &i, J &j)
Check whether range iterator i is subset of range iterator j.
CompareStatus compare(I &i, J &j)
Check whether range iterator i is a subset of j, or whether they are disjoint.
Gecode toplevel namespace
Post propagator for SetVar x
Definition set.hh:767
#define forceinline
Definition config.hpp:187