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          //return maximum(NodeTraits::get_parent(node));
74       }
75       else if(NodeTraits::get_left(node)){
76          return maximum(NodeTraits::get_left(node));
77       }
78       else {
79          node_ptr p(node);
80          node_ptr x = NodeTraits::get_parent(p);
81          while(p == NodeTraits::get_left(x)){
82             p = x;
83             x = NodeTraits::get_parent(x);
84          }
85          return x;
86       }
87    }
88 
89    //! <b>Requires</b>: 'node' is a node of a tree but not the header.
90    //!
91    //! <b>Effects</b>: Returns the minimum node of the subtree starting at p.
92    //!
93    //! <b>Complexity</b>: Logarithmic to the size of the subtree.
94    //!
95    //! <b>Throws</b>: Nothing.
minimum(node_ptr node)96    static node_ptr minimum(node_ptr node)
97    {
98       for(node_ptr p_left = NodeTraits::get_left(node)
99          ;p_left
100          ;p_left = NodeTraits::get_left(node)){
101          node = p_left;
102       }
103       return node;
104    }
105 
106    //! <b>Requires</b>: 'node' is a node of a tree but not the header.
107    //!
108    //! <b>Effects</b>: Returns the maximum node of the subtree starting at p.
109    //!
110    //! <b>Complexity</b>: Logarithmic to the size of the subtree.
111    //!
112    //! <b>Throws</b>: Nothing.
maximum(node_ptr node)113    static node_ptr maximum(node_ptr node)
114    {
115       for(node_ptr p_right = NodeTraits::get_right(node)
116          ;p_right
117          ;p_right = NodeTraits::get_right(node)){
118          node = p_right;
119       }
120       return node;
121    }
122 
123    //! <b>Requires</b>: p is a node of a tree.
124    //!
125    //! <b>Effects</b>: Returns true if p is the header of the tree.
126    //!
127    //! <b>Complexity</b>: Constant.
128    //!
129    //! <b>Throws</b>: Nothing.
is_header(const const_node_ptr & p)130    static bool is_header(const const_node_ptr & p)
131    {
132       node_ptr p_left (NodeTraits::get_left(p));
133       node_ptr p_right(NodeTraits::get_right(p));
134       if(!NodeTraits::get_parent(p) || //Header condition when empty tree
135          (p_left && p_right &&         //Header always has leftmost and rightmost
136             (p_left == p_right ||      //Header condition when only node
137                (NodeTraits::get_parent(p_left)  != p ||
138                 NodeTraits::get_parent(p_right) != p ))
139                //When tree size > 1 headers can't be leftmost's
140                //and rightmost's parent
141           )){
142          return true;
143       }
144       return false;
145    }
146 
147    //! <b>Requires</b>: 'node' is a node of the tree or a header node.
148    //!
149    //! <b>Effects</b>: Returns the header of the tree.
150    //!
151    //! <b>Complexity</b>: Logarithmic.
152    //!
153    //! <b>Throws</b>: Nothing.
get_header(const const_node_ptr & node)154    static node_ptr get_header(const const_node_ptr & node)
155    {
156       node_ptr n(detail::uncast(node));
157       node_ptr p(NodeTraits::get_parent(node));
158       //If p is null, then n is the header of an empty tree
159       if(p){
160          //Non-empty tree, check if n is neither root nor header
161          node_ptr pp(NodeTraits::get_parent(p));
162          //If granparent is not equal to n, then n is neither root nor header,
163          //the try the fast path
164          if(n != pp){
165             do{
166                n = p;
167                p = pp;
168                pp = NodeTraits::get_parent(pp);
169             }while(n != pp);
170             n = p;
171          }
172          //Check if n is root or header when size() > 0
173          else if(!bstree_algorithms_base::is_header(n)){
174             n = p;
175          }
176       }
177       return n;
178    }
179 };
180 
181 }  //namespace intrusive
182 }  //namespace boost
183 
184 #endif //BOOST_INTRUSIVE_BSTREE_ALGORITHMS_BASE_HPP
185