| 57 | } |
| 58 | |
| 59 | bool |
| 60 | GLBndSet::include_full(Space& home, int mi, int ma, SetDelta& d) { |
| 61 | assert(ma >= mi); |
| 62 | assert(fst() != nullptr); |
| 63 | |
| 64 | RangeList* p = nullptr; |
| 65 | RangeList* c = fst(); |
| 66 | |
| 67 | while (c != nullptr) { |
| 68 | if (c->max() >= mi-1) { |
| 69 | if (c->min() > ma+1) { //in a hole before c |
| 70 | _size+=(ma-mi+1); |
| 71 | d._glbMin = mi; |
| 72 | d._glbMax = ma; |
| 73 | RangeList* q = new (home) RangeList(mi,ma,c); |
| 74 | if (p==nullptr) |
| 75 | //the new range is the first |
| 76 | fst(q); |
| 77 | else |
| 78 | p->next(q); |
| 79 | return true; |
| 80 | } |
| 81 | //if the range starts before c, update c->min and size |
| 82 | bool result = false; |
| 83 | if (c->min()>mi) { |
| 84 | _size+=(c->min()-mi); |
| 85 | c->min(mi); |
| 86 | d._glbMin = mi; |
| 87 | result = true; |
| 88 | } else { |
| 89 | d._glbMin = c->max()+1; |
| 90 | } |
| 91 | assert(c->min()<=mi); |
| 92 | assert(c->max()+1>=mi); |
| 93 | if (c->max() >= ma) { |
| 94 | d._glbMax = c->min()-1; |
| 95 | return result; |
| 96 | } |
| 97 | RangeList* q = c; |
| 98 | //sum up the size of holes eaten |
| 99 | int prevMax = c->max(); |
| 100 | int growth = 0; |
| 101 | // invariant: q->min()<=ma+1 |
| 102 | while (q->next() != nullptr && q->next()->min() <= ma+1) { |
| 103 | q = q->next(); |
| 104 | growth += q->min()-prevMax-1; |
| 105 | prevMax = q->max(); |
| 106 | } |
| 107 | assert(growth>=0); |
| 108 | _size+=growth; |
| 109 | if (q->max() < ma) { |
| 110 | _size += ma-q->max(); |
| 111 | d._glbMax = ma; |
| 112 | } else { |
| 113 | d._glbMax = q->min()-1; |
| 114 | } |
| 115 | c->max(std::max(ma,q->max())); |
| 116 | if (c!=q) { |