229 typedef typename T::node leaf_node;
230 typedef typename leaf_node::node_ptr leaf_node_ptr;
231 typedef typename T::nonleaf_node nonleaf_node;
232 typedef std::vector<nonleaf_node> nonleaf_node_pool_type;
234 tree_builder(nonleaf_node_pool_type& pool) : m_pool(pool), m_pool_pos(pool.begin()), m_pool_pos_end(pool.end())
237 nonleaf_node* build(
const leaf_node_ptr& left_leaf_node)
243 leaf_node_ptr node1 = left_leaf_node;
245 std::vector<nonleaf_node*> node_list;
248 leaf_node_ptr node2 = node1->next;
249 nonleaf_node* parent_node = make_parent_node(node1.get(), node2.get());
250 node_list.push_back(parent_node);
252 if (!node2 || !node2->next)
259 return build_tree_non_leaf(node_list);
265 assert(m_pool_pos != m_pool_pos_end);
267 nonleaf_node* parent_node = &(*m_pool_pos);
269 node1->parent = parent_node;
270 parent_node->left = node1;
273 node2->parent = parent_node;
274 parent_node->right = node2;
277 fill_nonleaf_parent_node(parent_node, node1, node2);
281 void fill_nonleaf_parent_node(nonleaf_node* parent_node,
const node_base* left_node,
const node_base* right_node)
286 parent_node->low = left_node->
is_leaf ?
static_cast<const leaf_node*
>(left_node)->key
287 :
static_cast<const nonleaf_node*
>(left_node)->low;
292 throw general_error(
"fill_nonleaf_parent_node: Having a left node is prerequisite.");
303 const auto* p =
static_cast<const leaf_node*
>(right_node);
305 parent_node->high = p->next->key;
307 parent_node->high = p->key;
311 parent_node->high =
static_cast<const nonleaf_node*
>(right_node)->high;
316 parent_node->high = left_node->
is_leaf ?
static_cast<const leaf_node*
>(left_node)->key
317 :
static_cast<const nonleaf_node*
>(left_node)->high;
321 nonleaf_node* build_tree_non_leaf(
const std::vector<nonleaf_node*>& node_list)
323 size_t node_count = node_list.size();
326 return node_list.front();
328 else if (node_count == 0)
331 std::vector<nonleaf_node*> new_node_list;
332 nonleaf_node* node1 =
nullptr;
333 typename std::vector<nonleaf_node*>::const_iterator it = node_list.begin();
334 typename std::vector<nonleaf_node*>::const_iterator it_end = node_list.end();
335 for (
bool even_itr =
false; it != it_end; ++it, even_itr = !even_itr)
339 nonleaf_node* node2 = *it;
340 nonleaf_node* parent_node = make_parent_node(node1, node2);
341 new_node_list.push_back(parent_node);
352 nonleaf_node* parent_node = make_parent_node(node1,
nullptr);
353 new_node_list.push_back(parent_node);
357 return build_tree_non_leaf(new_node_list);
360 nonleaf_node_pool_type& m_pool;
361 typename nonleaf_node_pool_type::iterator m_pool_pos;
362 typename nonleaf_node_pool_type::iterator m_pool_pos_end;
395size_t count_leaf_nodes(
const node<KeyT, ValueT>* left_end,
const node<KeyT, ValueT>* right_end)
428 using node_list_type = std::vector<const node_base*>;
429 using tree_type =
typename TraitsT::tree_type;
432 static size_t dump(std::ostream& os,
const tree_type& tree,
const node_base* root_node)
437 node_list_type node_list;
438 node_list.push_back(root_node);
439 return dump_layer(os, tree, node_list, 0);
443 static size_t dump_layer(
444 std::ostream& os,
const tree_type& tree,
const node_list_type& node_list,
unsigned int level)
446 using leaf_type =
typename TraitsT::leaf_type;
447 using nonleaf_type =
typename TraitsT::nonleaf_type;
448 using to_string =
typename TraitsT::to_string;
450 if (node_list.empty())
453 size_t node_count = node_list.size();
455 bool is_leaf = node_list.front()->is_leaf;
456 os <<
"level " << level <<
':' << std::endl;
457 os <<
" type: " << (is_leaf ?
"leaf" :
"non-leaf") << std::endl;
458 os <<
" nodes:" << std::endl;
460 node_list_type new_list;
468 os <<
"*'" << std::endl;
474 const auto* pl =
static_cast<const leaf_type*
>(p);
475 os << to_string{tree}(*pl) <<
"'" << std::endl;
479 const auto* pnl =
static_cast<const nonleaf_type*
>(p);
480 os << to_string{tree}(*pnl) <<
"'" << std::endl;
484 new_list.push_back(pnl->left);
486 new_list.push_back(pnl->right);
490 if (!new_list.empty())
491 node_count += dump_layer(os, tree, new_list, level + 1);