i6engine  1.0
RangedMap.h
Go to the documentation of this file.
1 /*
2  * i6engine
3  * Copyright (2016) Daniel Bonrath, Michael Baer, All rights reserved.
4  *
5  * This file is part of i6engine; i6engine is free software; you can redistribute it and/or
6  * modify it under the terms of the GNU Lesser General Public
7  * License as published by the Free Software Foundation; either
8  * version 2.1 of the License, or (at your option) any later version.
9  *
10  * This library is distributed in the hope that it will be useful,
11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13  * Lesser General Public License for more details.
14  *
15  * You should have received a copy of the GNU Lesser General Public
16  * License along with this library; if not, write to the Free Software
17  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
18  */
19 
25 #ifndef __I6ENGINE_UTILS_RANGEDMAP_H__
26 #define __I6ENGINE_UTILS_RANGEDMAP_H__
27 
28 #include <fstream>
29 
31 
32 namespace i6e {
33 namespace utils {
34 
38  template<typename Key, typename Value>
39  class RangedMap {
40  struct Element;
41 
42  public:
43  struct iterator {
44  iterator(Element * e) : _cur(e) {
45  }
46 
47  bool valid() const {
48  return _cur != nullptr;
49  }
50 
51  Value operator*() {
52  return _cur->_val;
53  }
54 
55  private:
56  Element * _cur;
57  };
58 
62  RangedMap(const Key & minVal, const Key & maxVal, const Value & def) : _head(nullptr), _merged(false) {
63  _head = new Element(minVal, maxVal, def);
64  }
65 
70  delete _head;
71  }
72 
76  void dump(const std::string & fileName) {
77  std::ofstream of;
78  of.open(fileName.c_str());
79  of << "digraph {\n";
80  _head->dump(of);
81  of << "}";
82  of.close();
83  }
84 
88  Value get(const Key & k) const {
89  Element * e = _head;
90  if (k < e->_start || k > e->_end) {
91  ISIXE_THROW_FAILURE("RangedMap", "Key " << k << " not found");
92  }
93  while (e->_next != nullptr) { // iterate as long as there is no further level
94  Block * b = e->_next;
95  if (k > b->middleSplit) {
96  e = b->right;
97  } else if (k > b->leftSplit) {
98  e = b->mid;
99  } else {
100  e = b->left;
101  }
102  }
103  return e->_val;
104  }
105 
109  void set(const Key k, const Value v) {
110  Element * e = _head;
111  Block * bLast;
112  if (k < e->_start || k > e->_end) {
113  ISIXE_THROW_FAILURE("RangedMap", "Key " << k << " not found");
114  }
115  while(e->_next != nullptr) { // iterate as long as there is no further level
116  bLast = e->_next;
117  if (k > bLast->middleSplit) {
118  e = bLast->right;
119  } else if (k > bLast->leftSplit) {
120  e = bLast->mid;
121  } else {
122  e = bLast->left;
123  }
124  }
125  if (e->_val == v) {
126  return;
127  }
128  _merged = false;
129  if (isMid(e)) {
130  // mid
131  e = tryMergeToLeft(e, k, v, 1);
132  int r = 1;
133  if (_merged) {
134  r = e->_end - e->_start + 1;
135  }
136  e = tryMergeToRight(e, k, v, r);
137  } else if (isLeft(e)) {
138  // left
139  e = tryMergeToRight(e, k, v, 1);
140  int r = 1;
141  if (_merged) {
142  r = e->_end - e->_start + 1;
143  }
144  e = tryMergeToLeft(e, k, v, r);
145  } else if (isRight(e)) {
146  // right
147  e = tryMergeToLeft(e, k, v, 1);
148  int r = 1;
149  if (_merged) {
150  r = e->_end - e->_start + 1;
151  }
152  e = tryMergeToRight(e, k, v, r);
153  }
154 
155  if (!_merged) {
156  if (k == e->_start && k == e->_end) {
157  e->_val = v;
158  } else if (isRight(e) && k == e->_start && !e->_leftNext->isValid()) {
159  e->_leftNext->_start = k;
160  e->_leftNext->_end = k;
161  e->_start++;
162  e->_parent->_next->middleSplit++;
163  e->_leftNext->_val = v;
164  } else if (isLeft(e) && k == e->_end && !e->_rightNext->isValid()) {
165  e->_rightNext->_start = k;
166  e->_rightNext->_end = k;
167  e->_end--;
168  e->_parent->_next->leftSplit--;
169  e->_rightNext->_val = v;
170  } else {
171  Block * b = new Block();
172  if (k == e->_start) {
173  b->left = new Element(k, k, v);
174  b->mid = new Element(k + 1, k, v);
175  b->right = new Element(k + 1, e->_end, e->_val);
176  b->leftSplit = k;
177  b->middleSplit = k;
178  } else if (k == e->_end) {
179  b->left = new Element(e->_start, k - 1, e->_val);
180  b->mid = new Element(k, k - 1, v);
181  b->right = new Element(k, k, v);
182  b->leftSplit = k - 1;
183  b->middleSplit = k - 1;
184  } else {
185  b->left = new Element(e->_start, k - 1, e->_val);
186  b->mid = new Element(k, k, v);
187  b->right = new Element(k + 1, e->_end, e->_val);
188  b->leftSplit = k - 1;
189  b->middleSplit = k;
190  }
191  b->left->_parent = e;
192  b->mid->_parent = e;
193  b->right->_parent = e;
194 
195  // Element neighbours
196  b->left->_leftNext = e->_leftNext;
197  if (e->_leftNext != nullptr) {
198  e->_leftNext->_rightNext = b->left;
199  }
200 
201  b->mid->_leftNext = b->left;
202  b->left->_rightNext = b->mid;
203  b->mid->_rightNext = b->right;
204  b->right->_leftNext = b->mid;
205 
206  b->right->_rightNext = e->_rightNext;
207  if (e->_rightNext != nullptr) {
208  e->_rightNext->_leftNext = b->right;
209  }
210 
211  e->_leftNext = nullptr;
212  e->_rightNext = nullptr;
213 
214  e->_next = b;
215  }
216  }
217  return;
218  }
219 
220  private:
221  struct Block {
222  Element * left;
223  Element * mid;
224  Element * right;
225  Key leftSplit, middleSplit;
226 
227  Block() : left(nullptr), mid(nullptr), right(nullptr), leftSplit(), middleSplit() {
228  }
229 
230  ~Block() {
231  delete left;
232  delete mid;
233  delete right;
234  }
235 
236  void dump(std::ostream & of) {
237  of << "\"" << this << "\"[label=\"Block\\n" << leftSplit << "|" << middleSplit << "\"];" << std::endl;
238  of << "\"" << this << "\"" << " -> " << "\"" << left << "\"" << "[color=red,label=\"L\"];" << std::endl;
239  of << "\"" << this << "\"" << " -> " << "\"" << mid << "\"" << "[color=red,label=\"M\"];" << std::endl;
240  of << "\"" << this << "\"" << " -> " << "\"" << right << "\"" << "[color=red,label=\"R\"];" << std::endl;
241  if (left) left->dump(of);
242  if (mid) mid->dump(of);
243  if (right) right->dump(of);
244  }
245  };
246  struct Element {
247  Element(const Key & s, const Key & e, const Value & v) : _start(s), _end(e), _next(nullptr), _val(v), _leftNext(nullptr), _rightNext(nullptr), _parent(nullptr) {
248  }
249  Key _start, _end;
250  Block * _next;
251  Value _val;
252  Element * _leftNext;
253  Element * _rightNext;
254  Element * _parent;
255 
256  ~Element() {
257  delete _next;
258  }
259 
260  void dump(std::ostream & of) {
261  of << "\"" << this << "\"" << "[label=\"" << _start << "-" << _end << ":" << _val << "\"];" << std::endl;
262  of << "\"" << this << "\"" << " -> " << "\"" << _leftNext << "\"" << "[color=blue];" << std::endl;
263  of << "\"" << this << "\"" << " -> " << "\"" << _rightNext << "\"" << "[color=blue];" << std::endl;
264  of << "\"" << this << "\"" << " -> " << "\"" << _parent << "\"" << "[color=black];" << std::endl;
265  of << "\"" << this << "\"" << " -> " << "\"" << _next << "\"" << "[color=green];" << std::endl;
266  if (_next) _next->dump(of);
267  }
268  bool isValid() const {
269  return _start <= _end;
270  }
271  };
272 
273  Element * _head;
274  bool _merged;
275 
276  void eraseElement(Element * e) {
277  if (e->_leftNext) {
278  e->_leftNext->_rightNext = e->_rightNext;
279  }
280  if (e->_rightNext) {
281  e->_rightNext->_leftNext = e->_leftNext;
282  }
283  }
284 
289  void updateStart(Element * e, const Key k, int range) {
290  Element * previous = e;
291  while (e && e->_start == k) {
292  previous = e;
293  e->_start += range;
294  e = e->_parent;
295  }
296  if (isLeft(previous)) {
297  ISIXE_THROW_FAILURE("RangedMap", "Corrupted structure");
298  } else if (isMid(previous)) {
299  e->_next->leftSplit = previous->_start - 1;
300  } else if (isRight(previous)) {
301  e->_next->middleSplit = previous->_start - 1;
302  }
303  }
304 
309  void updateEnd(Element * e, const Key k, int range) {
310  Element * previous = e;
311  while (e && e->_end == k) {
312  previous = e;
313  e->_end += range;
314  e = e->_parent;
315  }
316  if (isLeft(previous)) {
317  e->_next->leftSplit = previous->_end;
318  } else if (isMid(previous)) {
319  e->_next->middleSplit = previous->_end;
320  } else if (isRight(previous)) {
321  ISIXE_THROW_FAILURE("RangedMap", "Corrupted structure");
322  }
323  }
324 
325  Element * combineBlockOneValid(Element * e) {
326  Element * par = e->_parent;
327 
328  // ultra merge
329  Element * ne = nullptr;
330  Block * nex = par->_next;
331 
332  if (!nex->left->isValid()) {
333  eraseElement(par->_next->left);
334  } else {
335  ne = nex->left;
336  }
337  if (!nex->mid->isValid()) {
338  eraseElement(nex->mid);
339  } else {
340  ne = nex->mid;
341  }
342  if (!nex->right->isValid()) {
343  eraseElement(nex->right);
344  } else {
345  ne = nex->right;
346  }
347  par->_start = ne->_start;
348  par->_end = ne->_end;
349  par->_val = ne->_val;
350  par->_next = ne->_next;
351  if (par->_next) {
352  par->_next->left->_parent = par;
353  par->_next->mid->_parent = par;
354  par->_next->right->_parent = par;
355  } else {
356  par->_leftNext = ne->_leftNext;
357  if (ne->_leftNext) {
358  ne->_leftNext->_rightNext = par;
359  }
360  par->_rightNext = ne->_rightNext;
361  if (ne->_rightNext) {
362  ne->_rightNext->_leftNext = par;
363  }
364  }
365 
366  ne->_next = nullptr;
367  delete nex;
368 
369  return par;
370  }
371 
372  bool isLeft(const Element * e) const {
373  return e->_parent && e == e->_parent->_next->left;
374  }
375 
376  bool isMid(const Element * e) const {
377  return e->_parent && e == e->_parent->_next->mid;
378  }
379 
380  bool isRight(const Element * e) const {
381  return e->_parent && e == e->_parent->_next->right;
382  }
383 
384  void swapLeftMid(Element * el) {
385  Element * em = el->_parent->_next->mid;
386  Element * right = el->_rightNext;
387  Element * r2 = em;
388  while (r2->_next) {
389  r2 = r2->_next->right;
390  }
391 
392  // swap left/mid pointer
393  std::swap(el->_parent->_next->left, el->_parent->_next->mid);
394 
395  // modify linked list pointer
396  right->_leftNext = el->_leftNext;
397  if (el->_leftNext) {
398  el->_leftNext->_rightNext = right;
399  }
400 
401  el->_rightNext = r2->_rightNext;
402  r2->_rightNext->_leftNext = el;
403 
404  r2->_rightNext = el;
405  el->_leftNext = r2;
406 
407  // update inValidMid ranges
408  el->_start = r2->_end + 1;
409  el->_end = r2->_end;
410 
411  // update splits
412  el->_parent->_next->leftSplit = r2->_end;
413  el->_parent->_next->middleSplit = r2->_end;
414  }
415 
416  void swapRightMid(Element * er) {
417  Element * em = er->_parent->_next->mid;
418  Element * left = er->_leftNext;
419  Element * l2 = em;
420  while (l2->_next) {
421  l2 = l2->_next->left;
422  }
423 
424  // swap right/mid pointer
425  std::swap(er->_parent->_next->right, er->_parent->_next->mid);
426 
427  // modify linked list pointer
428  left->_rightNext = er->_rightNext;
429  if (er->_rightNext) {
430  er->_rightNext->_leftNext = left;
431  }
432 
433  er->_leftNext = l2->_leftNext;
434  l2->_leftNext->_rightNext = er;
435 
436  l2->_leftNext = er;
437  er->_rightNext = l2;
438 
439  // update inValidMid ranges
440  er->_start = l2->_start - 1;
441  er->_end = l2->_start - 2;
442 
443  // update splits
444  er->_parent->_next->leftSplit = l2->_start - 1;
445  er->_parent->_next->middleSplit = l2->_start - 1;
446  }
447 
448  std::pair<Element *, bool> tryMergeLeftToMid(Element * e, const Key k, const Value v, int range) {
449  if (k == e->_end && /* e->_rightNext && */ e->_rightNext->_val == v && e->_rightNext->isValid()) {
450  _merged = true;
451  updateStart(e->_rightNext, e->_rightNext->_start, -range);
452  e->_end -= range;
453  if (!e->isValid()) { // range is now empty
454  swapLeftMid(e);
455  } else {
456  e = e->_rightNext;
457  }
458  return std::make_pair(e, true);
459  }
460  return std::make_pair(e, false);
461  }
462 
463  std::pair<Element *, bool> tryMergeRightToMid(Element * e, const Key k, const Value v, int range) {
464  if (k == e->_start && /* e->_leftNext && */ e->_leftNext->_val == v && e->_leftNext->isValid()) {
465  _merged = true;
466  updateEnd(e->_leftNext, e->_leftNext->_end, range);
467  e->_start += range;
468  if (!e->isValid()) { // range is now empty
469  swapRightMid(e);
470  } else {
471  e = e->_leftNext;
472  }
473  return std::make_pair(e, true);
474  }
475  return std::make_pair(e, false);
476  }
477 
478  std::pair<Element *, bool> tryMergeMidToLeft(Element * e, const Key k, const Value v, int range) {
479  if (k == e->_start && /* e->_leftNext && */ e->_leftNext->_val == v) {
480  _merged = true;
481  updateEnd(e->_leftNext, e->_leftNext->_end, range);
482  e->_start += range;
483  return std::make_pair(e->_leftNext, true);
484  }
485  return std::make_pair(e, false);
486  }
487 
488  std::pair<Element *, bool> tryMergeMidToRight(Element * e, const Key k, const Value v, int range) {
489  if (k == e->_end && /* e->_rightNext && */ e->_rightNext->_val == v) {
490  _merged = true;
491  updateStart(e->_rightNext, e->_rightNext->_start, -range);
492  e->_end -= range;
493  return std::make_pair(e->_rightNext, true);
494  }
495  return std::make_pair(e, false);
496  }
497 
498  Element * tryMergeToLeft(Element * e, const Key k, const Value v, int range) {
499  std::pair<Element *, bool> res;
500  if (isLeft(e)) {
501  res = tryMergeLeftToCrossLeftMid(e, k, v, range);
502  if (!res.second) {
503  res = tryMergeLeftToCrossLeftLeft(e, k, v, range);
504  }
505  } else if (isMid(e)) {
506  res = tryMergeMidToLeft(e, k, v, range);
507  } else if (isRight(e)) {
508  res = tryMergeRightToMid(e, k, v, range);
509  if (!res.second) {
510  res = tryMergeRightToLeft(e, k, v, range);
511  }
512  }
513  return res.first;
514  }
515 
516  Element * tryMergeToRight(Element * e, const Key k, const Value v, int range) {
517  std::pair<Element *, bool> res;
518  if (isLeft(e)) {
519  res = tryMergeLeftToMid(e, k, v, range);
520  if (!res.second) {
521  res = tryMergeLeftToRight(e, k, v, range);
522  }
523  } else if (isMid(e)) {
524  res = tryMergeMidToRight(e, k, v, range);
525  } else if (isRight(e)) {
526  res = tryMergeRightToCrossRightMid(e, k, v, range);
527  if (!res.second) {
528  res = tryMergeRightToCrossRightRight(e, k, v, range);
529  }
530  }
531  return res.first;
532  }
533 
534  std::pair<Element *, bool> tryMergeLeftToCrossLeftLeft(Element * e, const Key k, const Value v, int range) {
535  // iff
536  // * we change the left border
537  // * we have a left neighbour
538  // * the left neighbour is invalid (-> we have a left left neighbour)
539  // * the values match
540  if (k == e->_start && e->_leftNext && !e->_leftNext->isValid() && e->_leftNext->_leftNext->_val == v) {
541  _merged = true;
542  Element * target = e->_leftNext->_leftNext;
543  updateEnd(target, target->_end, range);
544  updateStart(e, e->_start, range);
545  // update skipped node
546  e->_leftNext->_start += range;
547  e->_leftNext->_end += range;
548 
549  if (!e->isValid()) {
550  // e->_rightNext can be in subtree
551  if (e->_rightNext->isValid()) {
552  // left is invalid, mid is valid => just swap (swap takes care of subtree)
553  swapLeftMid(e);
554  } else {
555  e = combineBlockOneValid(e->_rightNext);
556  }
557  }
558 
559  return std::make_pair(target, false);
560  }
561  return std::make_pair(e, false);
562  }
563 
564  std::pair<Element *, bool> tryMergeRightToCrossRightRight(Element * e, const Key k, const Value v, int range) {
565  // iff
566  // * we change the right border
567  // * we have a right neighbour
568  // * the right neighbour is invalid (-> we have a right right neighbour)
569  // * the values match
570  if (k == e->_end && e->_rightNext && !e->_rightNext->isValid() && e->_rightNext->_rightNext->_val == v) {
571  _merged = true;
572  Element * target = e->_rightNext->_rightNext;
573  updateStart(target, target->_start, -range);
574  updateEnd(e, e->_end, -range);
575  // update skipped node
576  e->_rightNext->_start -= range;
577  e->_rightNext->_end -= range;
578 
579  if (!e->isValid()) {
580  // e->_leftNext can be in subtree
581  if (e->_leftNext->isValid()) {
582  // right is invalid, mid is valid => just swap (swap takes care of subtree)
583  swapRightMid(e);
584  } else {
585  e = combineBlockOneValid(e->_leftNext);
586  }
587  }
588 
589  return std::make_pair(target, false);
590  }
591  return std::make_pair(e, false);
592  }
593 
594  std::pair<Element *, bool> tryMergeLeftToCrossLeftMid(Element * e, const Key k, const Value v, int range) {
595  if (k == e->_start && e->_leftNext && e->_leftNext->_val == v && e->_leftNext->isValid()) {
596  _merged = true;
597  // merge cross to left
598  // update ranges
599  Element * newE = e->_leftNext;
600 
601  updateEnd(e->_leftNext, e->_leftNext->_end, range);
602  updateStart(e, e->_start, range);
603  if (!e->isValid()) {
604  // e->_rightNext can be in subtree
605  if (e->_rightNext->isValid()) {
606  // left is invalid, mid is valid => just swap (swap takes care of subtree)
607  swapLeftMid(e);
608  } else {
609  e = combineBlockOneValid(e->_rightNext);
610  }
611  }
612  return std::make_pair(newE, true);
613  }
614  return std::make_pair(e, false);
615  }
616 
617  std::pair<Element *, bool> tryMergeRightToCrossRightMid(Element * e, const Key k, const Value v, int range) {
618  if (k == e->_end && e->_rightNext && e->_rightNext->_val == v && e->_rightNext->isValid()) {
619  _merged = true;
620  // merge cross to right
621  // update ranges
622  Element * newE = e->_rightNext;
623 
624  updateStart(e->_rightNext, e->_rightNext->_start, -range);
625  updateEnd(e, e->_end, -range);
626  if (!e->isValid()) {
627  // e->_leftNext can be in subtree
628  if (e->_leftNext->isValid()) {
629  // right is invalid, mid is valid => just swap (swap takes care of subtree)
630  swapRightMid(e);
631  } else {
632  e = combineBlockOneValid(e->_leftNext);
633  }
634  }
635  return std::make_pair(newE, true);
636  }
637  return std::make_pair(e, false);
638  }
639 
640  std::pair<Element *, bool> tryMergeLeftToRight(Element * e, const Key k, const Value v, int range) {
641  if (k == e->_end && /* e->_rightNext && */ !e->_rightNext->isValid() && e->_rightNext->_rightNext->_val == v) {
642  _merged = true;
643  // merge over invalid range
644  updateStart(e->_rightNext->_rightNext, e->_rightNext->_rightNext->_start, -range);
645  // update left and middle node
646  e->_end -= range;
647  e->_rightNext->_start -= range;
648  e->_rightNext->_end -= range;
649  // update the leftSplit
650  e->_parent->_next->leftSplit -= range;
651 
652  Element * newE = e->_rightNext->_rightNext;
653  if (!e->isValid()) {
654  e = combineBlockOneValid(e->_rightNext);
655  // combined was only a leaf node -> we need this node to return
656  // because newE is now a deleted node (combine* copies all data from the valid child to the parent)
657  if (e->_next == nullptr) {
658  newE = e;
659  }
660  } else {
661  // left border can't be merged
662  }
663  return std::make_pair(newE, true);
664  }
665  return std::make_pair(e, false);
666  }
667 
668  std::pair<Element *, bool> tryMergeRightToLeft(Element * e, const Key k, const Value v, int range) {
669  if (k == e->_start && /* e->_leftNext && */ !e->_leftNext->isValid() && e->_leftNext->_leftNext->_val == v) {
670  _merged = true;
671  // merge over invalid range
672  updateEnd(e->_leftNext->_leftNext, e->_leftNext->_leftNext->_end, range);
673  // update right and middle node
674  e->_start += range;
675  e->_leftNext->_start += range;
676  e->_leftNext->_end += range;
677 
678  // update the middleSplit
679  e->_parent->_next->middleSplit += range;
680 
681  Element * newE = e->_leftNext->_leftNext;
682 
683  if (!e->isValid()) {
684  e = combineBlockOneValid(e->_leftNext);
685  // combined was only a leaf node -> we need this node to return
686  // because newE is now a deleted node (combine* copies all data from the valid child to the parent)
687  if (e->_next == nullptr) {
688  newE = e;
689  }
690  } else {
691  // right border can't be merged
692  }
693  return std::make_pair(newE, true);
694  }
695  return std::make_pair(e, false);
696  }
697  };
698 
699 } /* namespace utils */
700 } /* namespace i6e */
701 
702 #endif /* __I6ENGINE_UTILS_RANGEDMAP_H__ */
703 
RangedMap(const Key &minVal, const Key &maxVal, const Value &def)
default constructor
Definition: RangedMap.h:62
#define ISIXE_THROW_FAILURE(module, message)
Definition: Exceptions.h:39
~RangedMap()
destructor
Definition: RangedMap.h:69
void dump(const std::string &fileName)
writes dot graph to given file
Definition: RangedMap.h:76
void set(const Key k, const Value v)
sets value for key
Definition: RangedMap.h:109