1 /* CO_Tree class implementation: inline functions.
2 Copyright (C) 2001-2010 Roberto Bagnara <bagnara@cs.unipr.it>
3 Copyright (C) 2010-2016 BUGSENG srl (http://bugseng.com)
4
5 This file is part of the Parma Polyhedra Library (PPL).
6
7 The PPL is free software; you can redistribute it and/or modify it
8 under the terms of the GNU General Public License as published by the
9 Free Software Foundation; either version 3 of the License, or (at your
10 option) any later version.
11
12 The PPL is distributed in the hope that it will be useful, but WITHOUT
13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with this program; if not, write to the Free Software Foundation,
19 Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02111-1307, USA.
20
21 For the most up-to-date information see the Parma Polyhedra Library
22 site: http://bugseng.com/products/ppl/ . */
23
24 #ifndef PPL_CO_Tree_inlines_hh
25 #define PPL_CO_Tree_inlines_hh 1
26
27 #include <cstddef>
28
29 namespace Parma_Polyhedra_Library {
30
31 inline dimension_type
dfs_index(const_iterator itr) const32 CO_Tree::dfs_index(const_iterator itr) const {
33 PPL_ASSERT(itr.current_index != 0);
34 PPL_ASSERT(itr.current_index >= indexes + 1);
35 PPL_ASSERT(itr.current_index <= indexes + reserved_size);
36 const std::ptrdiff_t index = itr.current_index - indexes;
37 return static_cast<dimension_type>(index);
38 }
39
40 inline dimension_type
dfs_index(iterator itr) const41 CO_Tree::dfs_index(iterator itr) const {
42 PPL_ASSERT(itr.current_index != 0);
43 PPL_ASSERT(itr.current_index >= indexes + 1);
44 PPL_ASSERT(itr.current_index <= indexes + reserved_size);
45 const std::ptrdiff_t index = itr.current_index - indexes;
46 return static_cast<dimension_type>(index);
47 }
48
49 inline
CO_Tree()50 CO_Tree::CO_Tree() {
51 init(0);
52 PPL_ASSERT(OK());
53 }
54
55 inline
CO_Tree(const CO_Tree & y)56 CO_Tree::CO_Tree(const CO_Tree& y) {
57 PPL_ASSERT(y.OK());
58 data_allocator = y.data_allocator;
59 init(y.reserved_size);
60 copy_data_from(y);
61 }
62
63 inline CO_Tree&
operator =(const CO_Tree & y)64 CO_Tree::operator=(const CO_Tree& y) {
65 if (this != &y) {
66 destroy();
67 data_allocator = y.data_allocator;
68 init(y.reserved_size);
69 copy_data_from(y);
70 }
71 return *this;
72 }
73
74 inline void
clear()75 CO_Tree::clear() {
76 *this = CO_Tree();
77 }
78
79 inline
~CO_Tree()80 CO_Tree::~CO_Tree() {
81
82 destroy();
83 }
84
85 inline bool
empty() const86 CO_Tree::empty() const {
87 return size_ == 0;
88 }
89
90 inline dimension_type
size() const91 CO_Tree::size() const {
92 return size_;
93 }
94
95 inline dimension_type
max_size()96 CO_Tree::max_size() {
97 return C_Integer<dimension_type>::max/100;
98 }
99
100 inline void
dump_tree() const101 CO_Tree::dump_tree() const {
102 if (empty()) {
103 std::cout << "(empty tree)" << std::endl;
104 }
105 else {
106 dump_subtree(tree_iterator(*const_cast<CO_Tree*>(this)));
107 }
108 }
109
110 inline CO_Tree::iterator
insert(const dimension_type key)111 CO_Tree::insert(const dimension_type key) {
112 if (empty()) {
113 return insert(key, Coefficient_zero());
114 }
115 else {
116 tree_iterator itr(*this);
117 itr.go_down_searching_key(key);
118 if (itr.index() == key) {
119 return iterator(itr);
120 }
121 else {
122 return iterator(insert_precise(key, Coefficient_zero(), itr));
123 }
124 }
125 }
126
127 inline CO_Tree::iterator
insert(dimension_type key,data_type_const_reference data1)128 CO_Tree::insert(dimension_type key, data_type_const_reference data1) {
129 if (empty()) {
130 insert_in_empty_tree(key, data1);
131 tree_iterator itr(*this);
132 PPL_ASSERT(itr.index() != unused_index);
133 return iterator(itr);
134 }
135 else {
136 tree_iterator itr(*this);
137 itr.go_down_searching_key(key);
138 return iterator(insert_precise(key, data1, itr));
139 }
140 }
141
142 inline CO_Tree::iterator
erase(dimension_type key)143 CO_Tree::erase(dimension_type key) {
144 PPL_ASSERT(key != unused_index);
145
146 if (empty()) {
147 return end();
148 }
149
150 tree_iterator itr(*this);
151 itr.go_down_searching_key(key);
152
153 if (itr.index() == key) {
154 return erase(itr);
155 }
156
157 iterator result(itr);
158 if (result.index() < key) {
159 ++result;
160 }
161
162 PPL_ASSERT(result == end() || result.index() > key);
163 #ifndef NDEBUG
164 iterator last = end();
165 --last;
166 PPL_ASSERT((result == end()) == (last.index() < key));
167 #endif
168
169 return result;
170 }
171
172 inline CO_Tree::iterator
erase(iterator itr)173 CO_Tree::erase(iterator itr) {
174 PPL_ASSERT(itr != end());
175 return erase(tree_iterator(itr, *this));
176 }
177
178 inline void
m_swap(CO_Tree & x)179 CO_Tree::m_swap(CO_Tree& x) {
180 using std::swap;
181 swap(max_depth, x.max_depth);
182 swap(indexes, x.indexes);
183 swap(data_allocator, x.data_allocator);
184 swap(data, x.data);
185 swap(reserved_size, x.reserved_size);
186 swap(size_, x.size_);
187 // Cached iterators have been invalidated by the swap,
188 // they must be refreshed here.
189 refresh_cached_iterators();
190 x.refresh_cached_iterators();
191 PPL_ASSERT(structure_OK());
192 PPL_ASSERT(x.structure_OK());
193 }
194
195 inline CO_Tree::iterator
begin()196 CO_Tree::begin() {
197 return iterator(*this);
198 }
199
200 inline const CO_Tree::iterator&
end()201 CO_Tree::end() {
202 return cached_end;
203 }
204
205 inline CO_Tree::const_iterator
begin() const206 CO_Tree::begin() const {
207 return const_iterator(*this);
208 }
209
210 inline const CO_Tree::const_iterator&
end() const211 CO_Tree::end() const {
212 return cached_const_end;
213 }
214
215 inline CO_Tree::const_iterator
cbegin() const216 CO_Tree::cbegin() const {
217 return const_iterator(*this);
218 }
219
220 inline const CO_Tree::const_iterator&
cend() const221 CO_Tree::cend() const {
222 return cached_const_end;
223 }
224
225 inline CO_Tree::iterator
bisect(dimension_type key)226 CO_Tree::bisect(dimension_type key) {
227 if (empty()) {
228 return end();
229 }
230 iterator last = end();
231 --last;
232 return bisect_in(begin(), last, key);
233 }
234
235 inline CO_Tree::const_iterator
bisect(dimension_type key) const236 CO_Tree::bisect(dimension_type key) const {
237 if (empty()) {
238 return end();
239 }
240 const_iterator last = end();
241 --last;
242 return bisect_in(begin(), last, key);
243 }
244
245 inline CO_Tree::iterator
bisect_in(iterator first,iterator last,dimension_type key)246 CO_Tree::bisect_in(iterator first, iterator last, dimension_type key) {
247 PPL_ASSERT(first != end());
248 PPL_ASSERT(last != end());
249 const dimension_type index
250 = bisect_in(dfs_index(first), dfs_index(last), key);
251 return iterator(*this, index);
252 }
253
254 inline CO_Tree::const_iterator
bisect_in(const_iterator first,const_iterator last,dimension_type key) const255 CO_Tree::bisect_in(const_iterator first, const_iterator last,
256 dimension_type key) const {
257 PPL_ASSERT(first != end());
258 PPL_ASSERT(last != end());
259 const dimension_type index
260 = bisect_in(dfs_index(first), dfs_index(last), key);
261 return const_iterator(*this, index);
262 }
263
264 inline CO_Tree::iterator
bisect_near(iterator hint,dimension_type key)265 CO_Tree::bisect_near(iterator hint, dimension_type key) {
266 if (hint == end()) {
267 return bisect(key);
268 }
269 const dimension_type index
270 = bisect_near(dfs_index(hint), key);
271 return iterator(*this, index);
272 }
273
274 inline CO_Tree::const_iterator
bisect_near(const_iterator hint,dimension_type key) const275 CO_Tree::bisect_near(const_iterator hint, dimension_type key) const {
276 if (hint == end()) {
277 return bisect(key);
278 }
279 const dimension_type index = bisect_near(dfs_index(hint), key);
280 return const_iterator(*this, index);
281 }
282
283 inline void
fast_shift(dimension_type i,iterator itr)284 CO_Tree::fast_shift(dimension_type i, iterator itr) {
285 PPL_ASSERT(itr != end());
286 PPL_ASSERT(i <= itr.index());
287 indexes[dfs_index(itr)] = i;
288 PPL_ASSERT(OK());
289 }
290
291 inline void
insert_in_empty_tree(dimension_type key,data_type_const_reference data1)292 CO_Tree::insert_in_empty_tree(dimension_type key,
293 data_type_const_reference data1) {
294 PPL_ASSERT(empty());
295 rebuild_bigger_tree();
296 tree_iterator itr(*this);
297 PPL_ASSERT(itr.index() == unused_index);
298 new(&(*itr)) data_type(data1);
299 // Set the index afterwards, so that if the constructor above throws
300 // the tree's structure is consistent.
301 itr.index() = key;
302 ++size_;
303
304 PPL_ASSERT(OK());
305 }
306
307 inline bool
is_less_than_ratio(dimension_type numer,dimension_type denom,dimension_type ratio)308 CO_Tree::is_less_than_ratio(dimension_type numer, dimension_type denom,
309 dimension_type ratio) {
310 PPL_ASSERT(ratio <= 100);
311 // If these are true, no overflows are possible.
312 PPL_ASSERT(denom <= unused_index/100);
313 PPL_ASSERT(numer <= unused_index/100);
314 return 100*numer < ratio*denom;
315 }
316
317 inline bool
is_greater_than_ratio(dimension_type numer,dimension_type denom,dimension_type ratio)318 CO_Tree::is_greater_than_ratio(dimension_type numer, dimension_type denom,
319 dimension_type ratio) {
320 PPL_ASSERT(ratio <= 100);
321 // If these are true, no overflows are possible.
322 PPL_ASSERT(denom <= unused_index/100);
323 PPL_ASSERT(numer <= unused_index/100);
324 return 100*numer > ratio*denom;
325 }
326
327 inline void
rebuild_smaller_tree()328 CO_Tree::rebuild_smaller_tree() {
329 PPL_ASSERT(reserved_size > 3);
330 CO_Tree new_tree;
331 new_tree.init(reserved_size / 2);
332 new_tree.move_data_from(*this);
333 m_swap(new_tree);
334 PPL_ASSERT(new_tree.structure_OK());
335 PPL_ASSERT(structure_OK());
336 }
337
338 inline void
refresh_cached_iterators()339 CO_Tree::refresh_cached_iterators() {
340 cached_end = iterator(*this, reserved_size + 1);
341 cached_const_end = const_iterator(*this, reserved_size + 1);
342 }
343
344 inline void
move_data_element(data_type & to,data_type & from)345 CO_Tree::move_data_element(data_type& to, data_type& from) {
346 /*
347 The following code is equivalent (but slower):
348
349 <CODE>
350 new(&to) data_type(from);
351 from.~data_type();
352 </CODE>
353 */
354 std::memcpy(&to, &from, sizeof(data_type));
355 }
356
357
358 inline
const_iterator()359 CO_Tree::const_iterator::const_iterator()
360 : current_index(0), current_data(0) {
361 #if PPL_CO_TREE_EXTRA_DEBUG
362 tree = 0;
363 #endif
364 PPL_ASSERT(OK());
365 }
366
367 inline
const_iterator(const CO_Tree & tree1)368 CO_Tree::const_iterator::const_iterator(const CO_Tree& tree1)
369 : current_index(&(tree1.indexes[1])), current_data(&(tree1.data[1])) {
370 #if PPL_CO_TREE_EXTRA_DEBUG
371 tree = &tree1;
372 #endif
373 if (!tree1.empty()) {
374 while (*current_index == unused_index) {
375 ++current_index;
376 ++current_data;
377 }
378 }
379 PPL_ASSERT(OK());
380 }
381
382 inline
const_iterator(const CO_Tree & tree1,dimension_type i)383 CO_Tree::const_iterator::const_iterator(const CO_Tree& tree1,
384 dimension_type i)
385 : current_index(&(tree1.indexes[i])), current_data(&(tree1.data[i])) {
386 #if PPL_CO_TREE_EXTRA_DEBUG
387 tree = &tree1;
388 #endif
389 PPL_ASSERT(i != 0);
390 PPL_ASSERT(i <= tree1.reserved_size + 1);
391 PPL_ASSERT(tree1.empty() || tree1.indexes[i] != unused_index);
392 PPL_ASSERT(OK());
393 }
394
395 inline
const_iterator(const const_iterator & itr2)396 CO_Tree::const_iterator::const_iterator(const const_iterator& itr2) {
397 (*this) = itr2;
398 PPL_ASSERT(OK());
399 }
400
401 inline
const_iterator(const iterator & itr2)402 CO_Tree::const_iterator::const_iterator(const iterator& itr2) {
403 (*this) = itr2;
404 PPL_ASSERT(OK());
405 }
406
407 inline void
m_swap(const_iterator & itr)408 CO_Tree::const_iterator::m_swap(const_iterator& itr) {
409 using std::swap;
410 swap(current_data, itr.current_data);
411 swap(current_index, itr.current_index);
412 #if PPL_CO_TREE_EXTRA_DEBUG
413 swap(tree, itr.tree);
414 #endif
415 PPL_ASSERT(OK());
416 PPL_ASSERT(itr.OK());
417 }
418
419 inline CO_Tree::const_iterator&
operator =(const const_iterator & itr2)420 CO_Tree::const_iterator::operator=(const const_iterator& itr2) {
421 current_index = itr2.current_index;
422 current_data = itr2.current_data;
423 #if PPL_CO_TREE_EXTRA_DEBUG
424 tree = itr2.tree;
425 #endif
426 PPL_ASSERT(OK());
427 return *this;
428 }
429
430 inline CO_Tree::const_iterator&
operator =(const iterator & itr2)431 CO_Tree::const_iterator::operator=(const iterator& itr2) {
432 current_index = itr2.current_index;
433 current_data = itr2.current_data;
434 #if PPL_CO_TREE_EXTRA_DEBUG
435 tree = itr2.tree;
436 #endif
437 PPL_ASSERT(OK());
438 return *this;
439 }
440
441 inline CO_Tree::const_iterator&
operator ++()442 CO_Tree::const_iterator::operator++() {
443 PPL_ASSERT(current_index != 0);
444 PPL_ASSERT(current_data != 0);
445 #if PPL_CO_TREE_EXTRA_DEBUG
446 PPL_ASSERT(current_index != &(tree->indexes[tree->reserved_size + 1]));
447 #endif
448 ++current_index;
449 ++current_data;
450 while (*current_index == unused_index) {
451 ++current_index;
452 ++current_data;
453 }
454 PPL_ASSERT(OK());
455 return *this;
456 }
457
458 inline CO_Tree::const_iterator&
operator --()459 CO_Tree::const_iterator::operator--() {
460 PPL_ASSERT(current_index != 0);
461 PPL_ASSERT(current_data != 0);
462 --current_index;
463 --current_data;
464 while (*current_index == unused_index) {
465 --current_index;
466 --current_data;
467 }
468 PPL_ASSERT(OK());
469 return *this;
470 }
471
472 inline CO_Tree::const_iterator
operator ++(int)473 CO_Tree::const_iterator::operator++(int) {
474 const_iterator itr(*this);
475 ++(*this);
476 return itr;
477 }
478
479 inline CO_Tree::const_iterator
operator --(int)480 CO_Tree::const_iterator::operator--(int) {
481 const_iterator itr(*this);
482 --(*this);
483 return itr;
484 }
485
486 inline Coefficient_traits::const_reference
operator *() const487 CO_Tree::const_iterator::operator*() const {
488 PPL_ASSERT(current_index != 0);
489 PPL_ASSERT(current_data != 0);
490 PPL_ASSERT(OK());
491 #if PPL_CO_TREE_EXTRA_DEBUG
492 PPL_ASSERT(current_index != &(tree->indexes[tree->reserved_size + 1]));
493 #endif
494 return *current_data;
495 }
496
497 inline dimension_type
index() const498 CO_Tree::const_iterator::index() const {
499 PPL_ASSERT(current_index != 0);
500 PPL_ASSERT(current_data != 0);
501 PPL_ASSERT(OK());
502 #if PPL_CO_TREE_EXTRA_DEBUG
503 PPL_ASSERT(current_index != &(tree->indexes[tree->reserved_size + 1]));
504 #endif
505 return *current_index;
506 }
507
508 inline bool
operator ==(const const_iterator & x) const509 CO_Tree::const_iterator::operator==(const const_iterator& x) const {
510 PPL_ASSERT((current_index == x.current_index)
511 == (current_data == x.current_data));
512 PPL_ASSERT(OK());
513 return (current_index == x.current_index);
514 }
515
516 inline bool
operator !=(const const_iterator & x) const517 CO_Tree::const_iterator::operator!=(const const_iterator& x) const {
518 return !(*this == x);
519 }
520
521
522 inline
iterator()523 CO_Tree::iterator::iterator()
524 : current_index(0), current_data(0) {
525 #if PPL_CO_TREE_EXTRA_DEBUG
526 tree = 0;
527 #endif
528 PPL_ASSERT(OK());
529 }
530
531 inline
iterator(CO_Tree & tree1)532 CO_Tree::iterator::iterator(CO_Tree& tree1)
533 : current_index(&(tree1.indexes[1])), current_data(&(tree1.data[1])) {
534 #if PPL_CO_TREE_EXTRA_DEBUG
535 tree = &tree1;
536 #endif
537 if (!tree1.empty()) {
538 while (*current_index == unused_index) {
539 ++current_index;
540 ++current_data;
541 }
542 }
543 PPL_ASSERT(OK());
544 }
545
546 inline
iterator(CO_Tree & tree1,dimension_type i)547 CO_Tree::iterator::iterator(CO_Tree& tree1, dimension_type i)
548 : current_index(&(tree1.indexes[i])), current_data(&(tree1.data[i])) {
549 #if PPL_CO_TREE_EXTRA_DEBUG
550 tree = &tree1;
551 #endif
552 PPL_ASSERT(i != 0);
553 PPL_ASSERT(i <= tree1.reserved_size + 1);
554 PPL_ASSERT(tree1.empty() || tree1.indexes[i] != unused_index);
555 PPL_ASSERT(OK());
556 }
557
558 inline
iterator(const tree_iterator & itr)559 CO_Tree::iterator::iterator(const tree_iterator& itr) {
560 *this = itr;
561 PPL_ASSERT(OK());
562 }
563
564 inline
iterator(const iterator & itr2)565 CO_Tree::iterator::iterator(const iterator& itr2) {
566 (*this) = itr2;
567 PPL_ASSERT(OK());
568 }
569
570 inline void
m_swap(iterator & itr)571 CO_Tree::iterator::m_swap(iterator& itr) {
572 using std::swap;
573 swap(current_data, itr.current_data);
574 swap(current_index, itr.current_index);
575 #if PPL_CO_TREE_EXTRA_DEBUG
576 swap(tree, itr.tree);
577 #endif
578 PPL_ASSERT(OK());
579 PPL_ASSERT(itr.OK());
580 }
581
582 inline CO_Tree::iterator&
operator =(const tree_iterator & itr)583 CO_Tree::iterator::operator=(const tree_iterator& itr) {
584 current_index = &(itr.tree.indexes[itr.dfs_index()]);
585 current_data = &(itr.tree.data[itr.dfs_index()]);
586 #if PPL_CO_TREE_EXTRA_DEBUG
587 tree = &(itr.tree);
588 #endif
589 PPL_ASSERT(OK());
590 return *this;
591 }
592
593 inline CO_Tree::iterator&
operator =(const iterator & itr2)594 CO_Tree::iterator::operator=(const iterator& itr2) {
595 current_index = itr2.current_index;
596 current_data = itr2.current_data;
597 #if PPL_CO_TREE_EXTRA_DEBUG
598 tree = itr2.tree;
599 #endif
600 PPL_ASSERT(OK());
601 return *this;
602 }
603
604 inline CO_Tree::iterator&
operator ++()605 CO_Tree::iterator::operator++() {
606 PPL_ASSERT(current_index != 0);
607 PPL_ASSERT(current_data != 0);
608 #if PPL_CO_TREE_EXTRA_DEBUG
609 PPL_ASSERT(current_index != &(tree->indexes[tree->reserved_size + 1]));
610 #endif
611 ++current_index;
612 ++current_data;
613 while (*current_index == unused_index) {
614 ++current_index;
615 ++current_data;
616 }
617
618 PPL_ASSERT(OK());
619 return *this;
620 }
621
622 inline CO_Tree::iterator&
operator --()623 CO_Tree::iterator::operator--() {
624 PPL_ASSERT(current_index != 0);
625 PPL_ASSERT(current_data != 0);
626 --current_index;
627 --current_data;
628 while (*current_index == unused_index) {
629 --current_index;
630 --current_data;
631 }
632
633 PPL_ASSERT(OK());
634 return *this;
635 }
636
637 inline CO_Tree::iterator
operator ++(int)638 CO_Tree::iterator::operator++(int) {
639 iterator itr(*this);
640 ++(*this);
641 return itr;
642 }
643
644 inline CO_Tree::iterator
operator --(int)645 CO_Tree::iterator::operator--(int) {
646 iterator itr(*this);
647 --(*this);
648 return itr;
649 }
650
651 inline CO_Tree::data_type&
operator *()652 CO_Tree::iterator::operator*() {
653 PPL_ASSERT(current_index != 0);
654 PPL_ASSERT(current_data != 0);
655 PPL_ASSERT(OK());
656 #if PPL_CO_TREE_EXTRA_DEBUG
657 PPL_ASSERT(current_index != &(tree->indexes[tree->reserved_size + 1]));
658 #endif
659 return *current_data;
660 }
661
662 inline Coefficient_traits::const_reference
operator *() const663 CO_Tree::iterator::operator*() const {
664 PPL_ASSERT(current_index != 0);
665 PPL_ASSERT(current_data != 0);
666 PPL_ASSERT(OK());
667 #if PPL_CO_TREE_EXTRA_DEBUG
668 PPL_ASSERT(current_index != &(tree->indexes[tree->reserved_size + 1]));
669 #endif
670 return *current_data;
671 }
672
673 inline dimension_type
index() const674 CO_Tree::iterator::index() const {
675 PPL_ASSERT(current_index != 0);
676 PPL_ASSERT(current_data != 0);
677 PPL_ASSERT(OK());
678 #if PPL_CO_TREE_EXTRA_DEBUG
679 PPL_ASSERT(current_index != &(tree->indexes[tree->reserved_size + 1]));
680 #endif
681 return *current_index;
682 }
683
684 inline bool
operator ==(const iterator & x) const685 CO_Tree::iterator::operator==(const iterator& x) const {
686 PPL_ASSERT((current_index == x.current_index)
687 == (current_data == x.current_data));
688 PPL_ASSERT(OK());
689 return (current_index == x.current_index);
690 }
691
692 inline bool
operator !=(const iterator & x) const693 CO_Tree::iterator::operator!=(const iterator& x) const {
694 return !(*this == x);
695 }
696
697
698 inline
tree_iterator(CO_Tree & tree1)699 CO_Tree::tree_iterator::tree_iterator(CO_Tree& tree1)
700 : tree(tree1) {
701 PPL_ASSERT(tree.reserved_size != 0);
702 get_root();
703 PPL_ASSERT(OK());
704 }
705
706 inline
tree_iterator(CO_Tree & tree1,dimension_type i1)707 CO_Tree::tree_iterator::tree_iterator(CO_Tree& tree1, dimension_type i1)
708 : tree(tree1) {
709 PPL_ASSERT(tree.reserved_size != 0);
710 PPL_ASSERT(i1 <= tree.reserved_size + 1);
711 i = i1;
712 offset = least_significant_one_mask(i);
713 PPL_ASSERT(OK());
714 }
715
716 inline
tree_iterator(const iterator & itr,CO_Tree & tree1)717 CO_Tree::tree_iterator::tree_iterator(const iterator& itr, CO_Tree& tree1)
718 : tree(tree1) {
719 PPL_ASSERT(tree.reserved_size != 0);
720 *this = itr;
721 PPL_ASSERT(OK());
722 }
723
724 inline CO_Tree::tree_iterator&
operator =(const tree_iterator & itr)725 CO_Tree::tree_iterator::operator=(const tree_iterator& itr) {
726 PPL_ASSERT(&tree == &(itr.tree));
727 i = itr.i;
728 offset = itr.offset;
729 return *this;
730 }
731
732 inline CO_Tree::tree_iterator&
operator =(const iterator & itr)733 CO_Tree::tree_iterator::operator=(const iterator& itr) {
734 PPL_ASSERT(itr != tree.end());
735 i = tree.dfs_index(itr);
736 offset = least_significant_one_mask(i);
737 return *this;
738 }
739
740 inline bool
operator ==(const tree_iterator & itr) const741 CO_Tree::tree_iterator::operator==(const tree_iterator& itr) const {
742 return i == itr.i;
743 }
744
745 inline bool
operator !=(const tree_iterator & itr) const746 CO_Tree::tree_iterator::operator!=(const tree_iterator& itr) const {
747 return !(*this == itr);
748 }
749
750 inline void
get_root()751 CO_Tree::tree_iterator::get_root() {
752 i = tree.reserved_size / 2 + 1;
753 offset = i;
754 PPL_ASSERT(OK());
755 }
756
757 inline void
get_left_child()758 CO_Tree::tree_iterator::get_left_child() {
759 PPL_ASSERT(offset != 0);
760 PPL_ASSERT(offset != 1);
761 offset /= 2;
762 i -= offset;
763 PPL_ASSERT(OK());
764 }
765
766 inline void
get_right_child()767 CO_Tree::tree_iterator::get_right_child() {
768 PPL_ASSERT(offset != 0);
769 PPL_ASSERT(offset != 1);
770 offset /= 2;
771 i += offset;
772 PPL_ASSERT(OK());
773 }
774
775 inline void
get_parent()776 CO_Tree::tree_iterator::get_parent() {
777 PPL_ASSERT(!is_root());
778 PPL_ASSERT(offset != 0);
779 i &= ~offset;
780 offset *= 2;
781 i |= offset;
782 PPL_ASSERT(OK());
783 }
784
785 inline void
follow_left_children_with_value()786 CO_Tree::tree_iterator::follow_left_children_with_value() {
787 PPL_ASSERT(index() != unused_index);
788 const dimension_type* p = tree.indexes;
789 p += i;
790 p -= (offset - 1);
791 while (*p == unused_index) {
792 ++p;
793 }
794 const std::ptrdiff_t distance = p - tree.indexes;
795 PPL_ASSERT(distance >= 0);
796 i = static_cast<dimension_type>(distance);
797 offset = least_significant_one_mask(i);
798 PPL_ASSERT(OK());
799 }
800
801 inline void
follow_right_children_with_value()802 CO_Tree::tree_iterator::follow_right_children_with_value() {
803 PPL_ASSERT(index() != unused_index);
804 const dimension_type* p = tree.indexes;
805 p += i;
806 p += (offset - 1);
807 while (*p == unused_index) {
808 --p;
809 }
810 const std::ptrdiff_t distance = p - tree.indexes;
811 PPL_ASSERT(distance >= 0);
812 i = static_cast<dimension_type>(distance);
813 offset = least_significant_one_mask(i);
814 PPL_ASSERT(OK());
815 }
816
817 inline bool
is_root() const818 CO_Tree::tree_iterator::is_root() const {
819 // This is implied by OK(), it is here for reference only.
820 PPL_ASSERT(offset <= (tree.reserved_size / 2 + 1));
821 return offset == (tree.reserved_size / 2 + 1);
822 }
823
824 inline bool
is_right_child() const825 CO_Tree::tree_iterator::is_right_child() const {
826 if (is_root()) {
827 return false;
828 }
829 return (i & (2*offset)) != 0;
830 }
831
832 inline bool
is_leaf() const833 CO_Tree::tree_iterator::is_leaf() const {
834 return offset == 1;
835 }
836
837 inline CO_Tree::data_type&
operator *()838 CO_Tree::tree_iterator::operator*() {
839 return tree.data[i];
840 }
841
842 inline Coefficient_traits::const_reference
operator *() const843 CO_Tree::tree_iterator::operator*() const {
844 return tree.data[i];
845 }
846
847 inline dimension_type&
index()848 CO_Tree::tree_iterator::index() {
849 return tree.indexes[i];
850 }
851
852 inline dimension_type
index() const853 CO_Tree::tree_iterator::index() const {
854 return tree.indexes[i];
855 }
856
857 inline dimension_type
dfs_index() const858 CO_Tree::tree_iterator::dfs_index() const {
859 return i;
860 }
861
862 inline dimension_type
get_offset() const863 CO_Tree::tree_iterator::get_offset() const {
864 return offset;
865 }
866
867 inline CO_Tree::height_t
depth() const868 CO_Tree::tree_iterator::depth() const {
869 return integer_log2((tree.reserved_size + 1) / offset);
870 }
871
872 inline void
swap(CO_Tree & x,CO_Tree & y)873 swap(CO_Tree& x, CO_Tree& y) {
874 x.m_swap(y);
875 }
876
877 inline void
swap(CO_Tree::const_iterator & x,CO_Tree::const_iterator & y)878 swap(CO_Tree::const_iterator& x, CO_Tree::const_iterator& y) {
879 x.m_swap(y);
880 }
881
882 inline void
swap(CO_Tree::iterator & x,CO_Tree::iterator & y)883 swap(CO_Tree::iterator& x, CO_Tree::iterator& y) {
884 x.m_swap(y);
885 }
886
887 } // namespace Parma_Polyhedra_Library
888
889 #endif // !defined(PPL_CO_Tree_inlines_hh)
890