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 34 namespace Gecode { namespace Int { 35 36 /* 37 * Value sets 38 * 39 */ 40 forceinline ValSet(void)41 ValSet::ValSet(void) 42 : fst(nullptr), lst(nullptr), n(0) {} 43 44 forceinline void add(Space & home,int v)45 ValSet::add(Space& home, int v) { 46 RangeList* c = fst; 47 RangeList** p = &fst; 48 while (c != nullptr) { 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() != nullptr) && (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 p = c->nextRef(); 72 c = *p; 73 } 74 } 75 *p = new (home) RangeList(v,v,nullptr); n++; 76 lst = *p; 77 } 78 79 forceinline int size(void) const80 ValSet::size(void) const { 81 return n; 82 } 83 84 forceinline bool empty(void) const85 ValSet::empty(void) const { 86 return n == 0; 87 } 88 89 forceinline int min(void) const90 ValSet::min(void) const { 91 return fst->min(); 92 } 93 94 forceinline int max(void) const95 ValSet::max(void) const { 96 return lst->max(); 97 } 98 99 forceinline void update(Space & home,ValSet & vs)100 ValSet::update(Space& home, ValSet& vs) { 101 if (vs.n > 0) { 102 n = vs.n; 103 // Count number of ranges 104 int m = 0; 105 for (RangeList* c = vs.fst; c != nullptr; c = c->next()) 106 m++; 107 fst = home.alloc<RangeList>(m); 108 lst = fst + (m-1); 109 int i=0; 110 for (RangeList* c = vs.fst; c != nullptr; c = c->next()) { 111 fst[i].min(c->min()); fst[i].max(c->max()); 112 fst[i].next(fst+i+1); 113 i++; 114 } 115 lst->next(nullptr); 116 } 117 } 118 119 forceinline void flush(void)120 ValSet::flush(void) { 121 fst = lst = nullptr; 122 } 123 124 forceinline void dispose(Space & home)125 ValSet::dispose(Space& home) { 126 if (fst != nullptr) 127 fst->dispose(home,lst); 128 } 129 130 forceinline Ranges(const ValSet & vs)131 ValSet::Ranges::Ranges(const ValSet& vs) 132 : c(vs.fst) {} 133 134 forceinline bool operator ()(void) const135 ValSet::Ranges::operator ()(void) const { 136 return c != nullptr; 137 } 138 139 forceinline void operator ++(void)140 ValSet::Ranges::operator ++(void) { 141 c = c->next(); 142 } 143 144 forceinline int min(void) const145 ValSet::Ranges::min(void) const { 146 return c->min(); 147 } 148 forceinline int max(void) const149 ValSet::Ranges::max(void) const { 150 return c->max(); 151 } 152 153 forceinline unsigned int width(void) const154 ValSet::Ranges::width(void) const { 155 return c->width(); 156 } 157 158 template<class View> 159 forceinline Iter::Ranges::CompareStatus compare(View x) const160 ValSet::compare(View x) const { 161 if (empty() || (x.max() < min()) || (x.min() > max())) 162 return Iter::Ranges::CS_DISJOINT; 163 ValSet::Ranges vsr(*this); 164 ViewRanges<View> xr(x); 165 return Iter::Ranges::compare(xr,vsr); 166 } 167 168 template<class View> 169 forceinline bool subset(View x) const170 ValSet::subset(View x) const { 171 if (empty() || (x.min() < min()) || (x.max() > max())) 172 return false; 173 ValSet::Ranges vsr(*this); 174 ViewRanges<View> xr(x); 175 return Iter::Ranges::subset(xr,vsr); 176 } 177 178 }} 179 180 // STATISTICS: int-other 181