1 /////////////////////////////////////////////////////////////////////////////
2 //
3 // (C) Copyright Ion Gaztanaga  2014-2014
4 //
5 // Distributed under the Boost Software License, Version 1.0.
6 //    (See accompanying file LICENSE_1_0.txt or copy at
7 //          http://www.boost.org/LICENSE_1_0.txt)
8 //
9 // See http://www.boost.org/libs/intrusive for documentation.
10 //
11 /////////////////////////////////////////////////////////////////////////////
12 
13 #ifndef BOOST_INTRUSIVE_BSTREE_ALGORITHMS_BASE_HPP
14 #define BOOST_INTRUSIVE_BSTREE_ALGORITHMS_BASE_HPP
15 
16 #ifndef BOOST_CONFIG_HPP
17 #  include <boost/config.hpp>
18 #endif
19 
20 #if defined(BOOST_HAS_PRAGMA_ONCE)
21 #  pragma once
22 #endif
23 
24 #include <boost/intrusive/detail/uncast.hpp>
25 
26 namespace boost {
27 namespace intrusive {
28 
29 template<class NodeTraits>
30 class bstree_algorithms_base
31 {
32    public:
33    typedef typename NodeTraits::node            node;
34    typedef NodeTraits                           node_traits;
35    typedef typename NodeTraits::node_ptr        node_ptr;
36    typedef typename NodeTraits::const_node_ptr  const_node_ptr;
37 
38    //! <b>Requires</b>: 'node' is a node from the tree except the header.
39    //!
40    //! <b>Effects</b>: Returns the next node of the tree.
41    //!
42    //! <b>Complexity</b>: Average constant time.
43    //!
44    //! <b>Throws</b>: Nothing.
next_node(const node_ptr & node)45    static node_ptr next_node(const node_ptr & node)
46    {
47       node_ptr const n_right(NodeTraits::get_right(node));
48       if(n_right){
49          return minimum(n_right);
50       }
51       else {
52          node_ptr n(node);
53          node_ptr p(NodeTraits::get_parent(n));
54          while(n == NodeTraits::get_right(p)){
55             n = p;
56             p = NodeTraits::get_parent(p);
57          }
58          return NodeTraits::get_right(n) != p ? p : n;
59       }
60    }
61 
62    //! <b>Requires</b>: 'node' is a node from the tree except the leftmost node.
63    //!
64    //! <b>Effects</b>: Returns the previous node of the tree.
65    //!
66    //! <b>Complexity</b>: Average constant time.
67    //!
68    //! <b>Throws</b>: Nothing.
prev_node(const node_ptr & node)69    static node_ptr prev_node(const node_ptr & node)
70    {
71       if(is_header(node)){
72          return NodeTraits::get_right(node);
73       }
74       else if(NodeTraits::get_left(node)){
75          return maximum(NodeTraits::get_left(node));
76       }
77       else {
78          node_ptr p(node);
79          node_ptr x = NodeTraits::get_parent(p);
80          while(p == NodeTraits::get_left(x)){
81             p = x;
82             x = NodeTraits::get_parent(x);
83          }
84          return x;
85       }
86    }
87 
88    //! <b>Requires</b>: 'node' is a node of a tree but not the header.
89    //!
90    //! <b>Effects</b>: Returns the minimum node of the subtree starting at p.
91    //!
92    //! <b>Complexity</b>: Logarithmic to the size of the subtree.
93    //!
94    //! <b>Throws</b>: Nothing.
minimum(node_ptr node)95    static node_ptr minimum(node_ptr node)
96    {
97       for(node_ptr p_left = NodeTraits::get_left(node)
98          ;p_left
99          ;p_left = NodeTraits::get_left(node)){
100          node = p_left;
101       }
102       return node;
103    }
104 
105    //! <b>Requires</b>: 'node' is a node of a tree but not the header.
106    //!
107    //! <b>Effects</b>: Returns the maximum node of the subtree starting at p.
108    //!
109    //! <b>Complexity</b>: Logarithmic to the size of the subtree.
110    //!
111    //! <b>Throws</b>: Nothing.
maximum(node_ptr node)112    static node_ptr maximum(node_ptr node)
113    {
114       for(node_ptr p_right = NodeTraits::get_right(node)
115          ;p_right
116          ;p_right = NodeTraits::get_right(node)){
117          node = p_right;
118       }
119       return node;
120    }
121 
122    //! <b>Requires</b>: p is a node of a tree.
123    //!
124    //! <b>Effects</b>: Returns true if p is the header of the tree.
125    //!
126    //! <b>Complexity</b>: Constant.
127    //!
128    //! <b>Throws</b>: Nothing.
is_header(const const_node_ptr & p)129    static bool is_header(const const_node_ptr & p)
130    {
131       node_ptr p_left (NodeTraits::get_left(p));
132       node_ptr p_right(NodeTraits::get_right(p));
133       if(!NodeTraits::get_parent(p) || //Header condition when empty tree
134          (p_left && p_right &&         //Header always has leftmost and rightmost
135             (p_left == p_right ||      //Header condition when only node
136                (NodeTraits::get_parent(p_left)  != p ||
137                 NodeTraits::get_parent(p_right) != p ))
138                //When tree size > 1 headers can't be leftmost's
139                //and rightmost's parent
140           )){
141          return true;
142       }
143       return false;
144    }
145 
146    //! <b>Requires</b>: 'node' is a node of the tree or a header node.
147    //!
148    //! <b>Effects</b>: Returns the header of the tree.
149    //!
150    //! <b>Complexity</b>: Logarithmic.
151    //!
152    //! <b>Throws</b>: Nothing.
get_header(const const_node_ptr & node)153    static node_ptr get_header(const const_node_ptr & node)
154    {
155       node_ptr n(detail::uncast(node));
156       node_ptr p(NodeTraits::get_parent(node));
157       //If p is null, then n is the header of an empty tree
158       if(p){
159          //Non-empty tree, check if n is neither root nor header
160          node_ptr pp(NodeTraits::get_parent(p));
161          //If granparent is not equal to n, then n is neither root nor header,
162          //the try the fast path
163          if(n != pp){
164             do{
165                n = p;
166                p = pp;
167                pp = NodeTraits::get_parent(pp);
168             }while(n != pp);
169             n = p;
170          }
171          //Check if n is root or header when size() > 0
172          else if(!bstree_algorithms_base::is_header(n)){
173             n = p;
174          }
175       }
176       return n;
177    }
178 };
179 
180 }  //namespace intrusive
181 }  //namespace boost
182 
183 #endif //BOOST_INTRUSIVE_BSTREE_ALGORITHMS_BASE_HPP
184