123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420 |
- #ifndef BOOST_INTRUSIVE_SGTREE_ALGORITHMS_HPP
- #define BOOST_INTRUSIVE_SGTREE_ALGORITHMS_HPP
- #include <boost/intrusive/detail/config_begin.hpp>
- #include <boost/intrusive/intrusive_fwd.hpp>
- #include <cstddef>
- #include <boost/intrusive/detail/algo_type.hpp>
- #include <boost/intrusive/bstree_algorithms.hpp>
- #if defined(BOOST_HAS_PRAGMA_ONCE)
- # pragma once
- #endif
- namespace boost {
- namespace intrusive {
- template<class NodeTraits>
- class sgtree_algorithms
- #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
- : public bstree_algorithms<NodeTraits>
- #endif
- {
- public:
- typedef typename NodeTraits::node node;
- typedef NodeTraits node_traits;
- typedef typename NodeTraits::node_ptr node_ptr;
- typedef typename NodeTraits::const_node_ptr const_node_ptr;
-
- private:
- typedef bstree_algorithms<NodeTraits> bstree_algo;
-
- public:
-
-
- struct insert_commit_data
- : bstree_algo::insert_commit_data
- {
- std::size_t depth;
- };
- #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
-
- static node_ptr get_header(const_node_ptr n) BOOST_NOEXCEPT;
-
- static node_ptr begin_node(const_node_ptr header) BOOST_NOEXCEPT;
-
- static node_ptr end_node(const_node_ptr header) BOOST_NOEXCEPT;
-
- static void swap_tree(node_ptr header1, node_ptr header2) BOOST_NOEXCEPT;
-
- static void swap_nodes(node_ptr node1, node_ptr node2) BOOST_NOEXCEPT;
-
- static void swap_nodes(node_ptr node1, node_ptr header1, node_ptr node2, node_ptr header2) BOOST_NOEXCEPT;
-
- static void replace_node(node_ptr node_to_be_replaced, node_ptr new_node) BOOST_NOEXCEPT;
-
- static void replace_node(node_ptr node_to_be_replaced, node_ptr header, node_ptr new_node) BOOST_NOEXCEPT;
-
-
-
- static node_ptr unlink_leftmost_without_rebalance(node_ptr header) BOOST_NOEXCEPT;
-
- static bool unique(const_node_ptr n) BOOST_NOEXCEPT;
-
- static std::size_t size(const_node_ptr header) BOOST_NOEXCEPT;
-
- static node_ptr next_node(node_ptr n) BOOST_NOEXCEPT;
-
- static node_ptr prev_node(node_ptr n) BOOST_NOEXCEPT;
-
- static void init(node_ptr n) BOOST_NOEXCEPT;
-
- static void init_header(node_ptr header) BOOST_NOEXCEPT;
- #endif
-
- template<class AlphaByMaxSize>
- static node_ptr erase(node_ptr header, node_ptr z, std::size_t tree_size, std::size_t &max_tree_size, AlphaByMaxSize alpha_by_maxsize)
- {
- bstree_algo::erase(header, z);
- --tree_size;
- if (tree_size > 0 &&
- tree_size < static_cast<std::size_t>(alpha_by_maxsize(max_tree_size))){
- bstree_algo::rebalance(header);
- max_tree_size = tree_size;
- }
- return z;
- }
- #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
-
- template <class Cloner, class Disposer>
- static void clone
- (const_node_ptr source_header, node_ptr target_header, Cloner cloner, Disposer disposer);
-
- template<class Disposer>
- static void clear_and_dispose(node_ptr header, Disposer disposer) BOOST_NOEXCEPT;
-
- template<class KeyType, class KeyNodePtrCompare>
- static node_ptr lower_bound
- (const_node_ptr header, const KeyType &key, KeyNodePtrCompare comp);
-
- template<class KeyType, class KeyNodePtrCompare>
- static node_ptr upper_bound
- (const_node_ptr header, const KeyType &key, KeyNodePtrCompare comp);
-
- template<class KeyType, class KeyNodePtrCompare>
- static node_ptr find
- (const_node_ptr header, const KeyType &key, KeyNodePtrCompare comp);
-
- template<class KeyType, class KeyNodePtrCompare>
- static std::pair<node_ptr, node_ptr> equal_range
- (const_node_ptr header, const KeyType &key, KeyNodePtrCompare comp);
-
- template<class KeyType, class KeyNodePtrCompare>
- static std::pair<node_ptr, node_ptr> bounded_range
- (const_node_ptr header, const KeyType &lower_key, const KeyType &upper_key, KeyNodePtrCompare comp
- , bool left_closed, bool right_closed);
-
- template<class KeyType, class KeyNodePtrCompare>
- static std::size_t count(const_node_ptr header, const KeyType &key, KeyNodePtrCompare comp);
- #endif
-
- template<class NodePtrCompare, class H_Alpha>
- static node_ptr insert_equal_upper_bound
- (node_ptr h, node_ptr new_node, NodePtrCompare comp
- ,std::size_t tree_size, H_Alpha h_alpha, std::size_t &max_tree_size)
- {
- std::size_t depth;
- bstree_algo::insert_equal_upper_bound(h, new_node, comp, &depth);
- rebalance_after_insertion(new_node, depth, tree_size+1, h_alpha, max_tree_size);
- return new_node;
- }
-
- template<class NodePtrCompare, class H_Alpha>
- static node_ptr insert_equal_lower_bound
- (node_ptr h, node_ptr new_node, NodePtrCompare comp
- ,std::size_t tree_size, H_Alpha h_alpha, std::size_t &max_tree_size)
- {
- std::size_t depth;
- bstree_algo::insert_equal_lower_bound(h, new_node, comp, &depth);
- rebalance_after_insertion(new_node, depth, tree_size+1, h_alpha, max_tree_size);
- return new_node;
- }
-
- template<class NodePtrCompare, class H_Alpha>
- static node_ptr insert_equal
- (node_ptr header, node_ptr hint, node_ptr new_node, NodePtrCompare comp
- ,std::size_t tree_size, H_Alpha h_alpha, std::size_t &max_tree_size)
- {
- std::size_t depth;
- bstree_algo::insert_equal(header, hint, new_node, comp, &depth);
- rebalance_after_insertion(new_node, depth, tree_size+1, h_alpha, max_tree_size);
- return new_node;
- }
-
- template<class H_Alpha>
- static node_ptr insert_before
- (node_ptr header, node_ptr pos, node_ptr new_node
- ,std::size_t tree_size, H_Alpha h_alpha, std::size_t &max_tree_size)
- {
- std::size_t depth;
- bstree_algo::insert_before(header, pos, new_node, &depth);
- rebalance_after_insertion(new_node, depth, tree_size+1, h_alpha, max_tree_size);
- return new_node;
- }
-
- template<class H_Alpha>
- static void push_back(node_ptr header, node_ptr new_node
- ,std::size_t tree_size, H_Alpha h_alpha, std::size_t &max_tree_size) BOOST_NOEXCEPT
- {
- std::size_t depth;
- bstree_algo::push_back(header, new_node, &depth);
- rebalance_after_insertion(new_node, depth, tree_size+1, h_alpha, max_tree_size);
- }
-
- template<class H_Alpha>
- static void push_front(node_ptr header, node_ptr new_node
- ,std::size_t tree_size, H_Alpha h_alpha, std::size_t &max_tree_size) BOOST_NOEXCEPT
- {
- std::size_t depth;
- bstree_algo::push_front(header, new_node, &depth);
- rebalance_after_insertion(new_node, depth, tree_size+1, h_alpha, max_tree_size);
- }
-
- template<class KeyType, class KeyNodePtrCompare>
- static std::pair<node_ptr, bool> insert_unique_check
- (const_node_ptr header, const KeyType &key
- ,KeyNodePtrCompare comp, insert_commit_data &commit_data)
- {
- std::size_t depth;
- std::pair<node_ptr, bool> ret =
- bstree_algo::insert_unique_check(header, key, comp, commit_data, &depth);
- commit_data.depth = depth;
- return ret;
- }
-
- template<class KeyType, class KeyNodePtrCompare>
- static std::pair<node_ptr, bool> insert_unique_check
- (const_node_ptr header, node_ptr hint, const KeyType &key
- ,KeyNodePtrCompare comp, insert_commit_data &commit_data)
- {
- std::size_t depth;
- std::pair<node_ptr, bool> ret =
- bstree_algo::insert_unique_check
- (header, hint, key, comp, commit_data, &depth);
- commit_data.depth = depth;
- return ret;
- }
-
- template<class H_Alpha>
- inline static void insert_unique_commit
- (node_ptr header, node_ptr new_value, const insert_commit_data &commit_data
- ,std::size_t tree_size, H_Alpha h_alpha, std::size_t &max_tree_size)
- { return insert_commit(header, new_value, commit_data, tree_size, h_alpha, max_tree_size); }
-
- template<class NodePtrCompare, class H_Alpha, class AlphaByMaxSize>
- static bool transfer_unique
- ( node_ptr header1, NodePtrCompare comp, std::size_t tree1_size, std::size_t &max_tree1_size
- , node_ptr header2, node_ptr z, std::size_t tree2_size, std::size_t &max_tree2_size
- ,H_Alpha h_alpha, AlphaByMaxSize alpha_by_maxsize)
- {
- insert_commit_data commit_data;
- bool const transferable = insert_unique_check(header1, z, comp, commit_data).second;
- if(transferable){
- erase(header2, z, tree2_size, max_tree2_size, alpha_by_maxsize);
- insert_commit(header1, z, commit_data, tree1_size, h_alpha, max_tree1_size);
- }
- return transferable;
- }
-
- template<class NodePtrCompare, class H_Alpha, class AlphaByMaxSize>
- static void transfer_equal
- ( node_ptr header1, NodePtrCompare comp, std::size_t tree1_size, std::size_t &max_tree1_size
- , node_ptr header2, node_ptr z, std::size_t tree2_size, std::size_t &max_tree2_size
- ,H_Alpha h_alpha, AlphaByMaxSize alpha_by_maxsize)
- {
- insert_commit_data commit_data;
- insert_equal_upper_bound_check(header1, z, comp, commit_data);
- erase(header2, z, tree2_size, max_tree2_size, alpha_by_maxsize);
- insert_commit(header1, z, commit_data, tree1_size, h_alpha, max_tree1_size);
- }
- #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
-
- static bool is_header(const_node_ptr p) BOOST_NOEXCEPT;
-
- static void rebalance(node_ptr header) BOOST_NOEXCEPT;
-
- static node_ptr rebalance_subtree(node_ptr old_root) BOOST_NOEXCEPT
- #endif
-
- private:
- template<class KeyType, class KeyNodePtrCompare>
- static void insert_equal_upper_bound_check
- (node_ptr header, const KeyType &key
- ,KeyNodePtrCompare comp, insert_commit_data &commit_data)
- {
- std::size_t depth;
- bstree_algo::insert_equal_upper_bound_check(header, key, comp, commit_data, &depth);
- commit_data.depth = depth;
- }
- template<class H_Alpha>
- static void insert_commit
- (node_ptr header, node_ptr new_value, const insert_commit_data &commit_data
- ,std::size_t tree_size, H_Alpha h_alpha, std::size_t &max_tree_size) BOOST_NOEXCEPT
- {
- bstree_algo::insert_unique_commit(header, new_value, commit_data);
- rebalance_after_insertion(new_value, commit_data.depth, tree_size+1, h_alpha, max_tree_size);
- }
- template<class H_Alpha>
- static void rebalance_after_insertion
- (node_ptr x, std::size_t depth
- , std::size_t tree_size, H_Alpha h_alpha, std::size_t &max_tree_size) BOOST_NOEXCEPT
- {
- if(tree_size > max_tree_size)
- max_tree_size = tree_size;
- if(tree_size > 2 &&
-
-
-
- depth > h_alpha(tree_size)){
-
-
-
-
-
-
- node_ptr s = x;
- std::size_t size = 1;
- for(std::size_t ancestor = 1; ancestor != depth; ++ancestor){
- const node_ptr s_parent = NodeTraits::get_parent(s);
- const node_ptr s_parent_left = NodeTraits::get_left(s_parent);
-
- const node_ptr s_sibling = s_parent_left == s ? NodeTraits::get_right(s_parent) : s_parent_left;
- size += 1 + bstree_algo::subtree_size(s_sibling);
- s = s_parent;
- if(ancestor > h_alpha(size)){
- bstree_algo::rebalance_subtree(s);
- return;
- }
- }
-
- max_tree_size = tree_size;
- bstree_algo::rebalance_subtree(NodeTraits::get_parent(s));
- }
- }
-
- };
- template<class NodeTraits>
- struct get_algo<SgTreeAlgorithms, NodeTraits>
- {
- typedef sgtree_algorithms<NodeTraits> type;
- };
- template <class ValueTraits, class NodePtrCompare, class ExtraChecker>
- struct get_node_checker<SgTreeAlgorithms, ValueTraits, NodePtrCompare, ExtraChecker>
- {
- typedef detail::bstree_node_checker<ValueTraits, NodePtrCompare, ExtraChecker> type;
- };
- }
- }
- #include <boost/intrusive/detail/config_end.hpp>
- #endif
|