| 222 | |
| 223 | template<class I> |
| 224 | void |
| 225 | NaryUnion::insert(I& i, RangeList*& u) { |
| 226 | // The current rangelist |
| 227 | RangeList** c = &u; |
| 228 | |
| 229 | while ((*c != nullptr) && i()) |
| 230 | if ((*c)->max+1 < i.min()) { |
| 231 | // Keep range from union |
| 232 | c = &(*c)->next; |
| 233 | } else if (i.max()+1 < (*c)->min) { |
| 234 | // Copy range from iterator |
| 235 | RangeList* t = range(i,f); ++i; |
| 236 | // Insert |
| 237 | t->next = *c; *c = t; c = &t->next; |
| 238 | } else { |
| 239 | // Ranges overlap |
| 240 | // Compute new minimum |
| 241 | (*c)->min = std::min((*c)->min,i.min()); |
| 242 | // Compute new maximum |
| 243 | int max = std::max((*c)->max,i.max()); |
| 244 | |
| 245 | // Scan from the next range in the union |
| 246 | RangeList* s = (*c)->next; |
| 247 | ++i; |
| 248 | |
| 249 | nextb: |
| 250 | if ((s != nullptr) && (s->min <= max+1)) { |
| 251 | max = std::max(max,s->max); |
| 252 | RangeList* t = s; |
| 253 | s = s->next; |
| 254 | // Put deleted element into freelist |
| 255 | t->next = f; f = t; |
| 256 | goto nextb; |
| 257 | } |
| 258 | if (i() && (i.min() <= max+1)) { |
| 259 | max = std::max(max,i.max()); ++i; |
| 260 | goto nextb; |
| 261 | } |
| 262 | // Store computed max and shunt skipped ranges from union |
| 263 | (*c)->max = max; (*c)->next = s; |
| 264 | } |
| 265 | if (*c == nullptr) { |
| 266 | // Copy remaining ranges from iterator |
| 267 | for ( ; i(); ++i) { |
| 268 | RangeList* t = range(i,f); |
| 269 | *c = t; c = &t->next; |
| 270 | } |
| 271 | *c = nullptr; |
| 272 | } |
| 273 | } |
| 274 | |
| 275 | |
| 276 | forceinline |