1 /* CO_Tree class implementation: non-inline template 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_templates_hh
25 #define PPL_CO_Tree_templates_hh 1
26
27 namespace Parma_Polyhedra_Library {
28
29 template <typename Iterator>
CO_Tree(Iterator i,dimension_type n)30 CO_Tree::CO_Tree(Iterator i, dimension_type n) {
31
32 if (n == 0) {
33 init(0);
34 PPL_ASSERT(OK());
35 return;
36 }
37
38 const dimension_type new_max_depth = integer_log2(n) + 1;
39 reserved_size = (static_cast<dimension_type>(1) << new_max_depth) - 1;
40
41 if (is_greater_than_ratio(n, reserved_size, max_density_percent)
42 && reserved_size != 3) {
43 reserved_size = reserved_size*2 + 1;
44 }
45
46 init(reserved_size);
47
48 tree_iterator root(*this);
49
50 // This is static and with static allocation, to improve performance.
51 // sizeof_to_bits(sizeof(dimension_type)) is the maximum k such that
52 // 2^k-1 is a dimension_type, so it is the maximum tree height.
53 // For each node level, the stack may contain up to 4 elements: two elements
54 // with operation 0, one element with operation 2 and one element
55 // with operation 3. An additional element with operation 1 can be at the
56 // top of the tree.
57 static std::pair<dimension_type, signed char>
58 stack[4U * sizeof_to_bits(sizeof(dimension_type)) + 1U];
59
60 dimension_type stack_first_empty = 0;
61
62 // A pair (n, operation) in the stack means:
63 //
64 // * Go to the parent, if operation is 0.
65 // * Go to the left child, then fill the current tree with n elements, if
66 // operation is 1.
67 // * Go to the right child, then fill the current tree with n elements, if
68 // operation is 2.
69 // * Fill the current tree with n elements, if operation is 3.
70
71 stack[0].first = n;
72 stack[0].second = 3;
73 ++stack_first_empty;
74
75 while (stack_first_empty != 0) {
76
77 // Implement
78 //
79 // <CODE>
80 // top_n = stack.top().first;
81 // top_operation = stack.top().second;
82 // </CODE>
83 const dimension_type top_n = stack[stack_first_empty - 1].first;
84 const signed char top_operation = stack[stack_first_empty - 1].second;
85
86 switch (top_operation) {
87
88 case 0:
89 root.get_parent();
90 --stack_first_empty;
91 continue;
92
93 case 1:
94 root.get_left_child();
95 break;
96
97 case 2:
98 root.get_right_child();
99 break;
100 #ifndef NDEBUG
101 case 3:
102 break;
103
104 default:
105 // We should not be here
106 PPL_UNREACHABLE;
107 #endif
108 }
109
110 // We now visit the current tree
111
112 if (top_n == 0) {
113 --stack_first_empty;
114 }
115 else {
116 if (top_n == 1) {
117 PPL_ASSERT(root.index() == unused_index);
118 root.index() = i.index();
119 new(&(*root)) data_type(*i);
120 ++i;
121 --stack_first_empty;
122 }
123 else {
124 PPL_ASSERT(stack_first_empty + 3 < sizeof(stack)/sizeof(stack[0]));
125
126 const dimension_type half = (top_n + 1) / 2;
127 stack[stack_first_empty - 1].second = 0;
128 stack[stack_first_empty ] = std::make_pair(top_n - half, 2);
129 stack[stack_first_empty + 1] = std::make_pair(1, 3);
130 stack[stack_first_empty + 2].second = 0;
131 stack[stack_first_empty + 3] = std::make_pair(half - 1, 1);
132 stack_first_empty += 4;
133 }
134 }
135 }
136 size_ = n;
137 PPL_ASSERT(OK());
138 }
139
140 } // namespace Parma_Polyhedra_Library
141
142 #endif // !defined(PPL_CO_Tree_templates_hh)
143