b-tree-plus-alpha
Loading...
Searching...
No Matches
dynamic_permutation.hpp
1#pragma once
2#include "./bp_tree_template.hpp"
3
4namespace stool
5{
6 namespace bptree
7 {
13 class DynamicPermutation
14 {
15 public:
16 using Tree = typename PermutationContainer::Tree;
17
18 using BPIterator = bptree::BPPostorderIterator<PermutationContainer, PermutationItem, bptree::DEFAULT_MAX_DEGREE_OF_INTERNAL_NODE, false>;
19 using PermIterator = PermutationContainer::PermutationIterator;
20 using NodePointer = bptree::BPNodePointer<PermutationContainer, PermutationItem, bptree::DEFAULT_MAX_DEGREE_OF_INTERNAL_NODE, false>;
21
22 private:
23 Tree pi_tree;
24 Tree inverse_pi_tree;
25
26
27 public:
28 DynamicPermutation()
29 {
30 this->pi_tree.set_linked_tree(&this->inverse_pi_tree);
31 this->inverse_pi_tree.set_linked_tree(&this->pi_tree);
32
33 //this->set_degree(Tree::DEFAULT_MAX_DEGREE_OF_INTERNAL_NODE);
34 }
35
36 ~DynamicPermutation()
37 {
38 this->clear();
39 }
40 DynamicPermutation &operator=(const DynamicPermutation &) = delete;
41 DynamicPermutation(DynamicPermutation &&other) noexcept
42 {
43 this->pi_tree = std::move(other.pi_tree);
44 this->inverse_pi_tree = std::move(other.inverse_pi_tree);
45 this->pi_tree.set_linked_tree(&this->inverse_pi_tree);
46 this->inverse_pi_tree.set_linked_tree(&this->pi_tree);
47 };
48 DynamicPermutation &operator=(DynamicPermutation &&other) noexcept
49 {
50 if (this != &other)
51 {
52
53 this->pi_tree = std::move(other.pi_tree);
54 this->inverse_pi_tree = std::move(other.inverse_pi_tree);
55 this->pi_tree.set_linked_tree(&this->inverse_pi_tree);
56 this->inverse_pi_tree.set_linked_tree(&this->pi_tree);
57
58 // other->clear();
59 }
60 return *this;
61 };
62
63 public:
64 /*
65 void set_degree(uint64_t degree)
66 {
67 this->pi_tree.initialize(degree);
68 this->inverse_pi_tree.initialize(degree);
69 }
70 */
71
72 void swap(DynamicPermutation &perm)
73 {
74 // this->pi_tree.set_linked_tree(&perm.inverse_pi_tree);
75 // perm.pi_tree.set_linked_tree(&this->inverse_pi_tree);
76
77 // this->inverse_pi_tree.set_linked_tree(&perm.pi_tree);
78 // perm.inverse_pi_tree.set_linked_tree(&this->pi_tree);
79
80 this->pi_tree.swap(perm.pi_tree, false);
81 this->inverse_pi_tree.swap(perm.inverse_pi_tree, false);
82 }
83 Tree &get_pi_tree()
84 {
85 return this->pi_tree;
86 }
87 Tree &get_inverse_pi_tree()
88 {
89 return this->inverse_pi_tree;
90 }
91 uint64_t get_max_degree() const
92 {
93 return this->pi_tree.get_max_degree_of_internal_node();
94 }
95
96 template <typename PI_ITERATOR_BEGIN, typename PI_ITERATOR_END>
97 void build(PI_ITERATOR_BEGIN beg, [[maybe_unused]] PI_ITERATOR_END end, uint64_t pi_size, int message_paragraph = stool::Message::SHOW_MESSAGE)
98 {
99
100 if (message_paragraph >= 0 && pi_size > 0)
101 {
102 std::cout << stool::Message::get_paragraph_string(message_paragraph) << "Constructing Dynamic Permutation... " << "(input size = " << pi_size << ")" << std::endl;
103 }
104 std::chrono::system_clock::time_point st1, st2;
105 st1 = std::chrono::system_clock::now();
106
107 this->clear();
108 // this->initialize(degree);
109 // this->pi_tree.initialize(degree);
110 // this->inverse_pi_tree.initialize(degree);
111 this->pi_tree.set_linked_tree(nullptr);
112 this->inverse_pi_tree.set_linked_tree(nullptr);
113
114 PermutationItem default_item;
115 default_item.key = 0;
116 default_item.pointer = 0;
117 this->pi_tree.resize(pi_size, default_item);
118 this->inverse_pi_tree.resize(pi_size, default_item);
119
120 // stool::Printer::print("items", pi);
121
122 this->pi_tree.set_linked_tree(&this->inverse_pi_tree);
123 this->inverse_pi_tree.set_linked_tree(&this->pi_tree);
124
125 uint64_t message_counter = 10000;
126 uint64_t processed_node_counter = 0;
127
128 [[maybe_unused]] uint64_t i = 0;
129 for (auto it = this->pi_tree.get_postorder_iterator_begin(); it != this->pi_tree.get_postorder_iterator_end(); ++it)
130 {
131 message_counter++;
132 processed_node_counter++;
133 if (message_paragraph >= 0 && message_counter > 10000)
134 {
135
136 std::cout << stool::Message::get_paragraph_string(message_paragraph + 1) << "Processing... [" << (processed_node_counter / 1000) << "KB] \r" << std::flush;
137 message_counter = 0;
138 }
139
140 if ((*it).is_leaf())
141 {
142 uint64_t pi_leaf_idx = (*it).get_leaf_container_index();
143 PermutationContainer &leaf = this->pi_tree.get_leaf_container(pi_leaf_idx);
144 std::unordered_map<uint64_t, uint64_t> mapper;
145 for (uint64_t j = 0; j < leaf.size(); j++)
146 {
147 uint64_t idx = this->inverse_pi_tree.compute_path_from_root_to_leaf(*beg);
148 ++beg;
149 const auto &path = this->inverse_pi_tree.get_temporary_path();
150 uint64_t inv_leaf_idx = path[path.size() - 1].get_leaf_container_index();
151 PermutationContainer &inv_leaf = this->inverse_pi_tree.get_leaf_container(inv_leaf_idx);
152
153 // uint64_t x1 = std::min(pi[i] / half_degree, pi_tree_vec_size - 1);
154 auto f = mapper.find(inv_leaf_idx);
155 if (f == mapper.end())
156 {
157 mapper[inv_leaf_idx] = 0;
158 }
159 uint64_t key = mapper[inv_leaf_idx];
160 leaf.set_value(j, PermutationItem(inv_leaf_idx, key));
161 inv_leaf.set_value(idx, PermutationItem(pi_leaf_idx, key));
162
163 mapper[inv_leaf_idx] = key + 1;
164 i++;
165 }
166 }
167 }
168
169 st2 = std::chrono::system_clock::now();
170
171 if (message_paragraph >= 0 && pi_size > 0)
172 {
173 uint64_t sec_time = std::chrono::duration_cast<std::chrono::seconds>(st2 - st1).count();
174 uint64_t ms_time = std::chrono::duration_cast<std::chrono::milliseconds>(st2 - st1).count();
175 uint64_t per_time = ((double)ms_time / (double)pi_size) * 1000000;
176 std::cout << std::endl;
177
178 std::cout << stool::Message::get_paragraph_string(message_paragraph) << "[END], the number of nodes = " << processed_node_counter << ", Elapsed Time: " << sec_time << " sec (" << per_time << " ms/MB)" << std::endl;
179 }
180 }
181
182 void insert(int64_t pi_index, int64_t inverse_pi_index)
183 {
184 assert(pi_index <= (int64_t)this->pi_tree.size());
185 assert(inverse_pi_index<= (int64_t)this->inverse_pi_tree.size());
186
187 uint64_t _size1 = this->inverse_pi_tree.get_leaf_container_vector_size();
188 uint64_t _size2 = this->pi_tree.get_leaf_container_vector_size();
189
190 // std::vector<NodePointer>& path1 = const_cast<std::vector<NodePointer>&>(this->pi_tmp_path);
191 // std::vector<NodePointer>& path2 = const_cast<std::vector<NodePointer>&>(this->inverse_pi_tmp_path);
192
193
194 this->pi_tree.insert(pi_index, PermutationItem(_size1 + 1, UINT8_MAX), 0);
195 this->inverse_pi_tree.insert(inverse_pi_index, PermutationItem(_size2 + 1, UINT8_MAX), 0);
196
197
198
199 // std::vector<NodePointer> path1, path2;
200 uint64_t value_idx1 = this->pi_tree.compute_path_from_root_to_leaf(pi_index);
201 uint64_t value_idx2 = this->inverse_pi_tree.compute_path_from_root_to_leaf(inverse_pi_index);
202 const std::vector<NodePointer> &path1 = this->pi_tree.get_temporary_path();
203 const std::vector<NodePointer> &path2 = this->inverse_pi_tree.get_temporary_path();
204
205 uint64_t idx1 = path1[path1.size() - 1].get_leaf_container_index();
206 uint64_t idx2 = path2[path2.size() - 1].get_leaf_container_index();
207 PermutationContainer &cont1 = this->pi_tree.get_leaf_container(idx1);
208 PermutationContainer &cont2 = this->inverse_pi_tree.get_leaf_container(idx2);
209 uint64_t key = cont1.get_new_key(idx2);
210
211 cont1.set_value(value_idx1, PermutationItem(idx2, key));
212 cont2.set_value(value_idx2, PermutationItem(idx1, key));
213
214
215 }
216 void erase(int64_t pi_index)
217 {
218 uint64_t idx1 = this->pi_tree.compute_path_from_root_to_leaf(pi_index);
219 const std::vector<NodePointer> &path = const_cast<std::vector<NodePointer> &>(this->pi_tree.get_temporary_path());
220 uint64_t inverse_pi_index = this->access(path, idx1);
221 this->pi_tree.remove_using_path(path, idx1);
222 assert(inverse_pi_index < this->inverse_pi_tree.size());
223 this->inverse_pi_tree.remove(inverse_pi_index);
224 assert(this->pi_tree.size() == this->inverse_pi_tree.size());
225 }
226 void clear()
227 {
228
229 this->pi_tree.set_linked_tree(nullptr);
230 this->inverse_pi_tree.set_linked_tree(nullptr);
231 this->pi_tree.clear();
232 this->inverse_pi_tree.clear();
233 this->pi_tree.set_linked_tree(&this->inverse_pi_tree);
234 this->inverse_pi_tree.set_linked_tree(&this->pi_tree);
235 }
236
237 void move_pi_index(int64_t from, int64_t to)
238 {
239 int64_t inverse_pi_index = this->access(from);
240 if (from < to)
241 {
242 this->insert(to + 1, inverse_pi_index);
243 this->erase(from);
244 }
245 else if (from > to)
246 {
247 this->erase(from);
248 this->insert(to, inverse_pi_index);
249 }
250 }
251 void verify() const
252 {
253 assert(this->pi_tree.get_linked_tree() == &this->inverse_pi_tree);
254 assert(this->inverse_pi_tree.get_linked_tree() == &this->pi_tree);
255 }
256 uint64_t size() const
257 {
258 return this->pi_tree.size();
259 }
260
261 int64_t access(const std::vector<NodePointer> &path, uint64_t position_to_leaf_index) const
262 {
263 const NodePointer &leaf_pointer = path[path.size() - 1];
264
265 uint64_t leaf_index = leaf_pointer.get_leaf_container_index();
266 const PermutationContainer &leaf1 = this->pi_tree.get_leaf_container(leaf_index);
267 PermutationItem item = leaf1.at(position_to_leaf_index);
268
269 const PermutationContainer &leaf2 = this->inverse_pi_tree.get_leaf_container(item.pointer);
270 uint64_t idx2 = leaf2.get_index(PermutationItem(leaf_index, item.key));
271
272 uint64_t result = this->inverse_pi_tree.get_value_index(item.pointer, idx2);
273
274 return result;
275 }
276
277 int64_t access(int64_t pi_index) const
278 {
279
280 uint64_t idx1 = this->pi_tree.compute_path_from_root_to_leaf(pi_index);
281 const std::vector<NodePointer> &path = const_cast<std::vector<NodePointer> &>(this->pi_tree.get_temporary_path());
282 return this->access(path, idx1);
283 }
284 int64_t inverse(int64_t inverse_pi_index) const
285 {
286
287 // std::vector<NodePointer> path;
288 uint64_t idx1 = this->inverse_pi_tree.compute_path_from_root_to_leaf(inverse_pi_index);
289 const std::vector<NodePointer> &path = const_cast<std::vector<NodePointer> &>(this->inverse_pi_tree.get_temporary_path());
290
291 assert(path.size() > 0);
292 const NodePointer &leaf_pointer = path[path.size() - 1];
293 uint64_t leaf_index = leaf_pointer.get_leaf_container_index();
294 const PermutationContainer &leaf1 = this->inverse_pi_tree.get_leaf_container(leaf_index);
295 PermutationItem item = leaf1.at(idx1);
296
297 const PermutationContainer &leaf2 = this->pi_tree.get_leaf_container(item.pointer);
298 uint64_t idx2 = leaf2.get_index(PermutationItem(leaf_index, item.key));
299
300 return this->pi_tree.get_value_index(item.pointer, idx2);
301 }
302 std::string to_string() const
303 {
304 std::stringstream ss;
305 auto vec = this->get_pi_vector();
306 ss << stool::DebugPrinter::to_integer_string(vec);
307 return ss.str();
308 }
309
310 std::vector<uint64_t> get_pi_vector() const
311 {
312 std::vector<uint64_t> r;
313 uint64_t size = this->size();
314 for (uint64_t i = 0; i < size; i++)
315 {
316 r.push_back(this->access(i));
317 }
318
319 return r;
320 }
321 std::vector<uint64_t> get_inverse_pi_vector() const
322 {
323 std::vector<uint64_t> r;
324 uint64_t size = this->size();
325 for (uint64_t i = 0; i < size; i++)
326 {
327 r.push_back(this->inverse(i));
328 }
329 return r;
330 }
331 void print(int message_paragraph = stool::Message::SHOW_MESSAGE) const
332 {
333 std::cout << stool::Message::get_paragraph_string(message_paragraph) << "========= DP ========" << std::endl;
334 std::cout << stool::Message::get_paragraph_string(message_paragraph) << "PI: " << std::endl;
335 auto pi_vec = this->get_pi_vector();
336 stool::DebugPrinter::print_integers(pi_vec, stool::Message::get_paragraph_string(message_paragraph) + "pi_vector");
337 this->pi_tree.print_tree();
338 this->pi_tree.print_leaves();
339 std::cout << std::endl;
340 std::cout << "Inv_PI: " << std::endl;
341 auto inv_pi_vec = this->get_inverse_pi_vector();
342 stool::DebugPrinter::print_integers(inv_pi_vec, stool::Message::get_paragraph_string(message_paragraph) +"inverse_pi_vector");
343 this->inverse_pi_tree.print_tree();
344 this->inverse_pi_tree.print_internal_nodes();
345 this->inverse_pi_tree.print_leaves();
346 std::cout << stool::Message::get_paragraph_string(message_paragraph) << "=====================" << std::endl;
347 }
348 void print_information_about_performance(int message_paragraph = stool::Message::SHOW_MESSAGE) const{
349 std::cout << stool::Message::get_paragraph_string(message_paragraph) << "Performance Information (DynamicPermutation)[" << std::endl;
350 this->pi_tree.print_information_about_performance(message_paragraph + 1);
351 this->inverse_pi_tree.print_information_about_performance(message_paragraph + 1);
352 std::cout << stool::Message::get_paragraph_string(message_paragraph) << "]" << std::endl;
353 }
354
355 uint64_t size_in_bytes() const
356 {
357 return this->pi_tree.size_in_bytes() + this->inverse_pi_tree.size_in_bytes();
358 }
359 std::vector<std::string> get_memory_usage_info(int message_paragraph = stool::Message::SHOW_MESSAGE) const
360 {
361 std::vector<std::string> log1 = this->pi_tree.get_memory_usage_info(message_paragraph + 1);
362 std::vector<std::string> log2 = this->inverse_pi_tree.get_memory_usage_info(message_paragraph + 1);
363
364 std::vector<std::string> r;
365 r.push_back("=Dynamic Permutation: " + std::to_string(this->size_in_bytes()) + " bytes ( " + std::to_string(this->size_in_bytes() / this->size()) + " bytes per element) = ");
366 for (std::string &s : log1)
367 {
368 r.push_back(s);
369 }
370 for (std::string &s : log2)
371 {
372 r.push_back(s);
373 }
374 r.push_back("==");
375 return r;
376 }
377 void print_memory_usage(int message_paragraph = stool::Message::SHOW_MESSAGE) const
378 {
379 std::vector<std::string> log = this->get_memory_usage_info(message_paragraph);
380 for (std::string &s : log)
381 {
382 std::cout << s << std::endl;
383 }
384 }
385
386 void sort_leaf_containers()
387 {
388 this->pi_tree.sort_leaf_containers();
389 // this->pi_tree.print_leaf_containers();
390 // this->inverse_pi_tree.print_leaves();
391 this->inverse_pi_tree.sort_leaf_containers();
392 }
393 void print_statistics(int message_paragraph = stool::Message::SHOW_MESSAGE) const
394 {
395 std::cout << stool::Message::get_paragraph_string(message_paragraph) << "Statistics(DynamicPermutation):" << std::endl;
396 std::cout << stool::Message::get_paragraph_string(message_paragraph + 1) << "The size of permutation: " << this->size() << std::endl;
397 std::cout << stool::Message::get_paragraph_string(message_paragraph + 1) << "Estimated memory usage: " << this->size_in_bytes() << " bytes" << std::endl;
398 this->pi_tree.print_statistics(message_paragraph + 1);
399 this->inverse_pi_tree.print_statistics(message_paragraph + 1);
400 std::cout << stool::Message::get_paragraph_string(message_paragraph) << "[END]" << std::endl;
401 }
402 void print_content(int message_paragraph = stool::Message::SHOW_MESSAGE) const
403 {
404 std::cout << stool::Message::get_paragraph_string(message_paragraph) << "Content(DynamicPermutation):" << std::endl;
405 auto pi_vector = this->get_pi_vector();
406 std::cout << stool::Message::get_paragraph_string(message_paragraph + 1) << "PI: \t" << stool::DebugPrinter::to_integer_string(pi_vector) << std::endl;
407 auto inverse_pi_vector = this->get_inverse_pi_vector();
408 std::cout << stool::Message::get_paragraph_string(message_paragraph + 1) << "Inverse PI: \t" << stool::DebugPrinter::to_integer_string(inverse_pi_vector) << std::endl;
409 std::cout << stool::Message::get_paragraph_string(message_paragraph) << "[END]" << std::endl;
410 }
411
412 static void store_to_bytes(DynamicPermutation &dp, std::vector<uint8_t> &output, uint64_t &pos)
413 {
414 dp.pi_tree.sort_leaf_containers();
415 dp.inverse_pi_tree.sort_leaf_containers();
416 Tree::store_to_bytes(dp.pi_tree, output, pos);
417 Tree::store_to_bytes(dp.inverse_pi_tree, output, pos);
418 }
419 static void store_to_file(DynamicPermutation &dp, std::ofstream &os)
420 {
421 Tree::store_to_file(dp.pi_tree, os);
422 Tree::store_to_file(dp.inverse_pi_tree, os);
423 }
424
425 static DynamicPermutation load_from_bytes(const std::vector<uint8_t> &data, uint64_t &pos)
426 {
427 DynamicPermutation r;
428 r.pi_tree.load_from_bytes(data, pos);
429 r.inverse_pi_tree.load_from_bytes(data, pos);
430 return r;
431 }
432
433 static DynamicPermutation load_from_file(std::ifstream &ifs)
434 {
435 DynamicPermutation r;
436 r.pi_tree.load_from_file(ifs);
437 r.inverse_pi_tree.load_from_file(ifs);
438 return r;
439 }
440 };
441 }
442
443}
stool::bptree::BPTree
An implementation of B+-tree [Unchecked AI's Comment].
Definition bp_tree.hpp:24
stool::bptree::BPTree::get_postorder_iterator_begin
PostorderIterator get_postorder_iterator_begin() const
Returns an iterator pointing to the first node in postorder traversal.
Definition bp_tree.hpp:366
stool::bptree::BPTree::get_value_index
uint64_t get_value_index(uint64_t leaf_index, uint64_t position_in_leaf_container) const
Returns the value index at position pos in the B+ tree.
Definition bp_tree.hpp:610
stool::bptree::BPTree::print_statistics
void print_statistics(int message_paragraph=stool::Message::SHOW_MESSAGE) const
Prints statistical information about the B+ tree.
Definition bp_tree.hpp:3038
stool::bptree::BPTree::get_temporary_path
const std::vector< NodePointer > & get_temporary_path() const
Returns the temporary path used during tree operations.
Definition bp_tree.hpp:270
stool::bptree::BPTree::set_linked_tree
void set_linked_tree(BPTree *_tree)
Sets the linked B+ tree.
Definition bp_tree.hpp:2247
stool::bptree::BPTree::size_in_bytes
uint64_t size_in_bytes(bool only_extra_bytes=false) const
Returns the total memory size of the B+ tree.
Definition bp_tree.hpp:930
stool::bptree::BPTree::push_back
void push_back(VALUE value)
Pushes a single value to the B+ tree.
Definition bp_tree.hpp:1851
stool::bptree::BPTree::insert
void insert(uint64_t pos, VALUE value, uint64_t sum_delta)
Inserts a value at a specific position in the B+ tree.
Definition bp_tree.hpp:2122
stool::bptree::BPTree::get_memory_usage_info
std::vector< std::string > get_memory_usage_info(int message_paragraph=stool::Message::SHOW_MESSAGE) const
Returns a vector of strings containing memory usage information about the B+ tree.
Definition bp_tree.hpp:1070
stool::bptree::BPTree::size
uint64_t size() const
Return the number of values stored in this tree.
Definition bp_tree.hpp:316
stool::bptree::BPTree::at
VALUE at(uint64_t pos) const
Returns the value at position pos in the B+ tree.
Definition bp_tree.hpp:574
stool::bptree::BPTree::get_leaf_container_vector_size
uint64_t get_leaf_container_vector_size() const
Return the size of the vector that stores leaf containers.
Definition bp_tree.hpp:345
stool::bptree::BPTree::get_leaf_container
const LEAF_CONTAINER & get_leaf_container(uint64_t leaf_index) const
Returns the leaf container at position leaf_index.
Definition bp_tree.hpp:655
stool::bptree::BPTree::load_from_file
void load_from_file(std::ifstream &ifs)
Builds a B+ tree from serialized data in a file stream.
Definition bp_tree.hpp:2993
stool::bptree::BPTree::load_from_bytes
void load_from_bytes(const std::vector< uint8_t > &data, uint64_t &pos)
Builds a B+ tree from serialized data in a byte vector.
Definition bp_tree.hpp:2969
stool::bptree::BPTree::resize
void resize(uint64_t _size, VALUE default_value)
Resizes the B+ tree to contain a specified number of elements.
Definition bp_tree.hpp:2194
stool::bptree::BPTree::sort_leaf_containers
void sort_leaf_containers()
Sorts the leaf containers in the B+ tree.
Definition bp_tree.hpp:2537
stool::bptree::BPTree::compute_path_from_root_to_leaf
int64_t compute_path_from_root_to_leaf(uint64_t i) const
Computes the path from the root to the leaf at position i.
Definition bp_tree.hpp:1209
stool::bptree::BPTree::get_postorder_iterator_end
PostorderIterator get_postorder_iterator_end() const
Returns an iterator pointing to the end of postorder traversal.
Definition bp_tree.hpp:391
stool::bptree::BPTree::get_max_degree_of_internal_node
uint64_t get_max_degree_of_internal_node() const
Return the max degree of this tree. The number of children of every internal node does not exceed the...
Definition bp_tree.hpp:278
stool::bptree::DynamicPermutation
A dynamic data structure storing a permutation [Unchecked AI's Comment].
Definition dynamic_permutation.hpp:14
stool::bptree::PermutationContainer::PermutationIterator
The forward iterator of values stored in PermutationContainer.
Definition permutation_container.hpp:29
stool::bptree::PermutationContainer
The container stored in the BPTree of DynamicPermutation [Unchecked AI's Comment].
Definition permutation_container.hpp:14
stool::bptree::PermutationItem
The value stored in the BPTree of DynamicPermutation [Unchecked AI's Comment].
Definition permutation_item.hpp:15