integerset.cc
Go to the documentation of this file.00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024 #include "set.hh"
00025
00026 namespace Gecode { namespace Set {
00027
00028 BndSet::BndSet(Space* home, const IntSet& is) {
00029 if (is.size()==0) {
00030 fst(NULL); lst(NULL); _size = 0;
00031 } else {
00032 int n = is.size();
00033 RangeList* r = reinterpret_cast<RangeList*>
00034 (home->alloc(sizeof(RangeList)*n));
00035 fst(r); lst(r+n-1);
00036 unsigned int s = 0;
00037 for (int i = n; i--; ) {
00038 s += is.width(i);
00039 r[i].min(is.min(i)); r[i].max(is.max(i));
00040 r[i].prevnext(&r[i-1],&r[i+1]);
00041 }
00042 r[0].prev(&r[-1],NULL);
00043 r[n-1].next(&r[n],NULL);
00044 _size = s;
00045 }
00046 assert(isConsistent());
00047 }
00048
00049 bool
00050 GLBndSet::include_full(Space* home, int mi, int ma) {
00051 assert(ma >= mi);
00052 assert(fst() != NULL);
00053
00054 RangeList* p = NULL;
00055 RangeList* c = fst();
00056 while (c != NULL) {
00057 if (c->max() >= mi-1){
00058 if (c->min() > ma+1) {
00059 _size+=(ma-mi+1);
00060 RangeList* q=new (home) RangeList(mi,ma,NULL,c);
00061 if (p==NULL){
00062 assert(c==fst());
00063 c->prev(NULL,q);
00064 fst(q);
00065 return true;
00066 }
00067 q->prev(NULL, p);
00068 p->next(c, q);
00069 c->prev(p, q);
00070 return true;
00071 }
00072
00073 bool result = false;
00074 if (c->min()>mi) {
00075 _size+=(c->min()-mi);
00076 c->min(mi);
00077 result = true;
00078 }
00079 assert(c->min()<=mi);
00080 assert(c->max()+1>=mi);
00081 if (c->max() >= ma) {
00082 return result; }
00083
00084 RangeList* qp = p;
00085 RangeList* q = c;
00086
00087 int prevMax = c->max();
00088 int growth =0;
00089
00090 while (q->next(qp)!=NULL && q->next(qp)->min()<=ma+1){
00091 RangeList* nq = q->next(qp);
00092 qp = q; q = nq;
00093 growth+=q->min()-prevMax-1;
00094 prevMax=q->max();
00095 }
00096 assert(growth>=0);
00097 _size+=growth;
00098 if (q->max() < ma) {_size+=ma-q->max(); }
00099 c->max(std::max(ma,q->max()));
00100 if (c==q) {
00101 return true; }
00102 RangeList* oldCNext = c->next(p);
00103 assert(oldCNext!=NULL);
00104 c->next(oldCNext, q->next(qp));
00105 if (q->next(qp)==NULL){
00106 assert(q==lst());
00107 lst(c);
00108 } else {
00109 q->next(qp)->prev(q,c);
00110 }
00111 oldCNext->dispose(home,c,q);
00112 return true;
00113 }
00114 RangeList* nc = c->next(p);
00115 p=c; c=nc;
00116 }
00117
00118 assert(mi>max()+1);
00119 RangeList* q = new (home) RangeList(mi, ma, lst(), NULL);
00120 lst()->next(NULL, q);
00121 lst(q);
00122 _size+= q->width();
00123 return true;
00124 }
00125
00126 bool
00127 LUBndSet::exclude_full(Space* home, int mi, int ma) {
00128 assert(ma >= mi);
00129 assert(mi <= max() && ma >= min() &&
00130 (mi > min() || ma < max()));
00131 bool result=false;
00132
00133 RangeList* p = NULL;
00134 RangeList* c = fst();
00135 while (c != NULL) {
00136 if (c->max() >= mi){
00137 if (c->min() > ma) { return result; }
00138
00139 if (c->min()<mi && c->max() > ma) {
00140 RangeList* q =
00141 new (home) RangeList(ma+1,c->max(),c,c->next(p));
00142 c->max(mi-1);
00143 if (c != lst()) {c->next(p)->prev(c,q); }
00144 else { lst(q); }
00145 c->next(c->next(p),q);
00146 _size -= (ma-mi+1);
00147 return true;
00148 }
00149
00150 if (c->max() > ma) {
00151 _size-=(ma-c->min()+1);
00152 c->min(ma+1);
00153 return true;
00154 }
00155
00156 if (c->min() < mi) {
00157 _size-=(c->max()-mi+1);
00158 c->max(mi-1);
00159 result=true;
00160 } else {
00161 _size-=c->width();
00162 RangeList *cendp = p;
00163 RangeList *cend = c;
00164 while ((cend->next(cendp)!=NULL) && (cend->next(cendp)->max()<=ma)){
00165 RangeList *ncend = cend->next(cendp);
00166 cendp=cend; cend=ncend;
00167 _size-=cend->width();
00168 }
00169 if (fst()==c) { fst(cend->next(cendp)); }
00170 else { p->next(c, cend->next(cendp)); }
00171 if (lst()==cend) { lst(p); }
00172 else { cend->next(cendp)->prev(cend,p); }
00173 RangeList* nc=cend->next(cendp);
00174 c->dispose(home,p,cend);
00175 p=cend;
00176 c=nc;
00177 if (c!=NULL && c->min() <= ma ) {
00178 _size-=(ma-c->min()+1);
00179 c->min(ma+1);
00180 }
00181 return true;
00182 }
00183 }
00184 RangeList *nc = c->next(p);
00185 p=c; c=nc;
00186 }
00187 return result;
00188 }
00189
00190 #ifndef NDEBUG
00191 using namespace Gecode::Int;
00192
00193 bool
00194 BndSet::isConsistent(void) const {
00195 if (fst()==NULL) {
00196 if (lst()!=NULL || size()!=0) {
00197 std::cout<<"Strange empty set.\n";
00198 return false;
00199 } else return true;
00200 }
00201
00202 if (fst()!=NULL && lst()==NULL) {
00203 std::cout<<"First is not null, last is.\n";
00204 return false;
00205 }
00206
00207 RangeList *p=NULL;
00208 RangeList *c=fst();
00209
00210 int min = c->min();
00211 int max = c->max();
00212
00213 if (max<min) {
00214 std::cout << "Single range list twisted: ("<<min<<","<<max<<")" ;
00215 return false;
00216 }
00217
00218 RangeList *nc=c->next(p);
00219 p=c; c=nc;
00220 while (c) {
00221 if (max<min) {
00222 std::cout << "1";
00223 return false;
00224 }
00225 if ((max+1)>=c->min()) {
00226 std::cout << "2";
00227 return false;
00228 }
00229 if (c->next(p)==NULL && c!=lst()) {
00230 std::cout << "3";
00231 return false;
00232 }
00233
00234 if (c->next(p)!=NULL && c->next(p)->prev(c->next(p)->next(c))!=c) {
00235 std::cout<<"Prev of next not self.\n";
00236 ((RangeList *)NULL)->min();
00237 return false;
00238 }
00239
00240 min = c->min();
00241 max = c->max();
00242
00243 nc=c->next(p);
00244 p=c; c=nc;
00245 }
00246 return true;
00247 }
00248
00249 #endif
00250
00251 }}
00252
00253
00254