1 #ifndef MULTITREE_IMPL_HPP
2 #define MULTITREE_IMPL_HPP
3
4 #include "multitree.hpp"
5
6 #include <memory>
7
8 namespace terraces {
9 namespace multitree_impl {
10
11 template <typename T>
12 struct array_deleter {
operator ()terraces::multitree_impl::array_deleter13 void operator()(T* ptr) { delete[] ptr; }
14 };
15
16 template <typename T>
make_unique_array(std::size_t size)17 std::unique_ptr<T[], array_deleter<T>> make_unique_array(std::size_t size) {
18 // this may leak memory if allocation or construction of a T fails
19 return std::unique_ptr<T[], array_deleter<T>>{new T[size]};
20 }
21
22 template <typename T>
23 class storage_block {
24 private:
25 std::unique_ptr<T[], array_deleter<T>> begin;
26 index size;
27 index max_size;
28
29 public:
storage_block(index max_size)30 storage_block(index max_size)
31 : begin{make_unique_array<T>(max_size)}, size{0}, max_size{max_size} {}
32
has_space(index required=1)33 bool has_space(index required = 1) { return size + required <= max_size; }
34
get()35 T* get() {
36 assert(has_space());
37 return begin.get() + (size++);
38 }
39
get_range(index required)40 T* get_range(index required) {
41 assert(has_space(required));
42 auto result = begin.get() + size;
43 size += required;
44 return result;
45 }
46 };
47
48 template <typename T>
49 class storage_blocks {
50 private:
51 std::vector<storage_block<T>> m_blocks;
52 index m_block_size;
53
54 public:
storage_blocks(index block_size=1024)55 storage_blocks(index block_size = 1024) : m_blocks{}, m_block_size{block_size} {
56 m_blocks.emplace_back(m_block_size);
57 }
storage_blocks(const storage_blocks<T> & other)58 storage_blocks(const storage_blocks<T>& other) : storage_blocks{other.m_block_size} {}
59 storage_blocks(storage_blocks<T>&& other) = default;
operator =(const storage_blocks<T> & other)60 storage_blocks<T>& operator=(const storage_blocks<T>& other) {
61 m_block_size = other.m_block_size;
62 return *this;
63 }
64 storage_blocks<T>& operator=(storage_blocks<T>&& other) = default;
65
get()66 T* get() {
67 if (!m_blocks.back().has_space()) {
68 m_blocks.emplace_back(m_block_size);
69 }
70 return m_blocks.back().get();
71 }
72
get_range(index required)73 T* get_range(index required) {
74 if (!m_blocks.back().has_space(required)) {
75 m_blocks.emplace_back(required);
76 auto result = m_blocks.back().get_range(required);
77 auto last_it = --m_blocks.end();
78 auto prev_it = --(--m_blocks.end());
79 std::iter_swap(
80 last_it,
81 prev_it); // TODO this might lead to some bad worst-case behaviour
82 return result;
83 }
84 return m_blocks.back().get_range(required);
85 }
86 };
87
make_single_leaf(multitree_node * n,index i)88 inline multitree_node* make_single_leaf(multitree_node* n, index i) {
89 n->type = multitree_node_type::base_single_leaf;
90 n->single_leaf = i;
91 n->num_leaves = 1;
92 n->num_trees = 1;
93 return n;
94 }
95
make_two_leaves(multitree_node * n,index i,index j)96 inline multitree_node* make_two_leaves(multitree_node* n, index i, index j) {
97 n->type = multitree_node_type::base_two_leaves;
98 n->two_leaves = {i, j};
99 n->num_leaves = 2;
100 n->num_trees = 1;
101 return n;
102 }
103
make_unconstrained(multitree_node * n,std::pair<index *,index * > range)104 inline multitree_node* make_unconstrained(multitree_node* n, std::pair<index*, index*> range) {
105 auto begin = range.first;
106 auto end = range.second;
107 n->type = multitree_node_type::base_unconstrained;
108 n->unconstrained = {begin, end};
109 n->num_leaves = (index)(end - begin);
110 n->num_trees = count_unrooted_trees<index>(n->num_leaves);
111 return n;
112 }
113
make_inner_node(multitree_node * n,multitree_node * left,multitree_node * right)114 inline multitree_node* make_inner_node(multitree_node* n, multitree_node* left,
115 multitree_node* right) {
116 n->type = multitree_node_type::inner_node;
117 n->inner_node = {left, right};
118 n->num_leaves = left->num_leaves + right->num_leaves;
119 n->num_trees = left->num_trees * right->num_trees;
120 return n;
121 }
122
make_alternative_array(multitree_node * n,multitree_node * begin,index leaves)123 inline multitree_node* make_alternative_array(multitree_node* n, multitree_node* begin,
124 index leaves) {
125 n->type = multitree_node_type::alternative_array;
126 n->alternative_array = {begin, begin};
127 n->num_leaves = leaves;
128 n->num_trees = 0;
129 return n;
130 }
131
make_unexplored(multitree_node * n,std::pair<index *,index * > range)132 inline multitree_node* make_unexplored(multitree_node* n, std::pair<index*, index*> range) {
133 auto begin = range.first;
134 auto end = range.second;
135 n->type = multitree_node_type::unexplored;
136 n->unexplored = {begin, end};
137 n->num_leaves = (index)(end - begin);
138 n->num_trees = 0;
139 return n;
140 }
141
142 } // namespace multitree_impl
143 } // namespace terraces
144
145 #endif // MULTITREE_IMPL_HPP
146