ceph/src/boost/boost/heap/detail/tree_iterator.hpp

   1 // boost heap: node tree iterator helper classes
   2 //
   3 // Copyright (C) 2010 Tim Blechmann
   4 //
   5 // Distributed under the Boost Software License, Version 1.0. (See
   6 // accompanying file LICENSE_1_0.txt or copy at
   7 // http://www.boost.org/LICENSE_1_0.txt)
   8
   9 #ifndef BOOST_HEAP_DETAIL_TREE_ITERATOR_HPP
  10 #define BOOST_HEAP_DETAIL_TREE_ITERATOR_HPP
  11
  12 #include <functional>
  13 #include <vector>
  14
  15 #include <boost/core/allocator_access.hpp>
  16 #include <boost/iterator/iterator_adaptor.hpp>
  17 #include <boost/type_traits/conditional.hpp>
  18 #include <queue>
  19
  20 namespace boost  {
  21 namespace heap   {
  22 namespace detail {
  23
  24
  25 template<typename type>
  26 struct identity
  27 {
  28     type& operator()(type& x) const BOOST_NOEXCEPT
  29     { return x; }
  30
  31     const type& operator()(const type& x) const BOOST_NOEXCEPT
  32     { return x; }
  33 };
  34
  35 template<typename Node>
  36 struct dereferencer
  37 {
  38     template <typename Iterator>
  39     Node * operator()(Iterator const & it)
  40     {
  41         return static_cast<Node *>(*it);
  42     }
  43 };
  44
  45 template<typename Node>
  46 struct pointer_to_reference
  47 {
  48     template <typename Iterator>
  49     const Node * operator()(Iterator const & it)
  50     {
  51         return static_cast<const Node *>(&*it);
  52     }
  53 };
  54
  55
  56 template <typename HandleType,
  57           typename Alloc,
  58           typename ValueCompare
  59          >
  60 struct unordered_tree_iterator_storage
  61 {
  62     unordered_tree_iterator_storage(ValueCompare const & cmp)
  63     {}
  64
  65     void push(HandleType h)
  66     {
  67         data_.push_back(h);
  68     }
  69
  70     HandleType const & top(void)
  71     {
  72         return data_.back();
  73     }
  74
  75     void pop(void)
  76     {
  77         data_.pop_back();
  78     }
  79
  80     bool empty(void) const
  81     {
  82         return data_.empty();
  83     }
  84
  85     std::vector<HandleType, typename boost::allocator_rebind<Alloc, HandleType>::type> data_;
  86 };
  87
  88 template <typename ValueType,
  89           typename HandleType,
  90           typename Alloc,
  91           typename ValueCompare,
  92           typename ValueExtractor
  93          >
  94 struct ordered_tree_iterator_storage:
  95     ValueExtractor
  96 {
  97     struct compare_values_by_handle:
  98         ValueExtractor,
  99         ValueCompare
 100     {
 101         compare_values_by_handle(ValueCompare const & cmp):
 102             ValueCompare(cmp)
 103         {}
 104
 105         bool operator()(HandleType const & lhs, HandleType const & rhs) const
 106         {
 107             ValueType const & lhs_value = ValueExtractor::operator()(lhs->value);
 108             ValueType const & rhs_value = ValueExtractor::operator()(rhs->value);
 109             return ValueCompare::operator()(lhs_value, rhs_value);
 110         }
 111     };
 112
 113     ordered_tree_iterator_storage(ValueCompare const & cmp):
 114         data_(compare_values_by_handle(cmp))
 115     {}
 116
 117     void push(HandleType h)
 118     {
 119         data_.push(h);
 120     }
 121
 122     void pop(void)
 123     {
 124         data_.pop();
 125     }
 126
 127     HandleType const & top(void)
 128     {
 129         return data_.top();
 130     }
 131
 132     bool empty(void) const BOOST_NOEXCEPT
 133     {
 134         return data_.empty();
 135     }
 136
 137     std::priority_queue<HandleType,
 138                         std::vector<HandleType, typename boost::allocator_rebind<Alloc, HandleType>::type>,
 139                         compare_values_by_handle> data_;
 140 };
 141
 142
 143 /* tree iterator helper class
 144  *
 145  * Requirements:
 146  * Node provides child_iterator
 147  * ValueExtractor can convert Node->value to ValueType
 148  *
 149  * */
 150 template <typename Node,
 151           typename ValueType,
 152           typename Alloc = std::allocator<Node>,
 153           typename ValueExtractor = identity<typename Node::value_type>,
 154           typename PointerExtractor = dereferencer<Node>,
 155           bool check_null_pointer = false,
 156           bool ordered_iterator = false,
 157           typename ValueCompare = std::less<ValueType>
 158          >
 159 class tree_iterator:
 160     public boost::iterator_adaptor<tree_iterator<Node,
 161                                                  ValueType,
 162                                                  Alloc,
 163                                                  ValueExtractor,
 164                                                  PointerExtractor,
 165                                                  check_null_pointer,
 166                                                  ordered_iterator,
 167                                                  ValueCompare
 168                                                 >,
 169                                    const Node *,
 170                                    ValueType,
 171                                    boost::forward_traversal_tag
 172                                   >,
 173     ValueExtractor,
 174     PointerExtractor
 175 {
 176     typedef boost::iterator_adaptor<tree_iterator<Node,
 177                                                   ValueType,
 178                                                   Alloc,
 179                                                   ValueExtractor,
 180                                                   PointerExtractor,
 181                                                   check_null_pointer,
 182                                                   ordered_iterator,
 183                                                   ValueCompare
 184                                                  >,
 185                                     const Node *,
 186                                     ValueType,
 187                                     boost::forward_traversal_tag
 188                                    > adaptor_type;
 189
 190     friend class boost::iterator_core_access;
 191
 192     typedef typename boost::conditional< ordered_iterator,
 193                                        ordered_tree_iterator_storage<ValueType, const Node*, Alloc, ValueCompare, ValueExtractor>,
 194                                        unordered_tree_iterator_storage<const Node*, Alloc, ValueCompare>
 195                                      >::type
 196         unvisited_node_container;
 197
 198 public:
 199     tree_iterator(void):
 200         adaptor_type(0), unvisited_nodes(ValueCompare())
 201     {}
 202
 203     tree_iterator(ValueCompare const & cmp):
 204         adaptor_type(0), unvisited_nodes(cmp)
 205     {}
 206
 207     tree_iterator(const Node * it, ValueCompare const & cmp):
 208         adaptor_type(it), unvisited_nodes(cmp)
 209     {
 210         if (it)
 211             discover_nodes(it);
 212     }
 213
 214     /* fills the iterator from a list of possible top nodes */
 215     template <typename NodePointerIterator>
 216     tree_iterator(NodePointerIterator begin, NodePointerIterator end, const Node * top_node, ValueCompare const & cmp):
 217         adaptor_type(0), unvisited_nodes(cmp)
 218     {
 219         BOOST_STATIC_ASSERT(ordered_iterator);
 220         if (begin == end)
 221             return;
 222
 223         adaptor_type::base_reference() = top_node;
 224         discover_nodes(top_node);
 225
 226         for (NodePointerIterator it = begin; it != end; ++it) {
 227             const Node * current_node = static_cast<const Node*>(&*it);
 228             if (current_node != top_node)
 229                 unvisited_nodes.push(current_node);
 230         }
 231     }
 232
 233     bool operator!=(tree_iterator const & rhs) const
 234     {
 235         return adaptor_type::base() != rhs.base();
 236     }
 237
 238     bool operator==(tree_iterator const & rhs) const
 239     {
 240         return !operator!=(rhs);
 241     }
 242
 243     const Node * get_node() const
 244     {
 245         return adaptor_type::base_reference();
 246     }
 247
 248 private:
 249     void increment(void)
 250     {
 251         if (unvisited_nodes.empty())
 252             adaptor_type::base_reference() = 0;
 253         else {
 254             const Node * next = unvisited_nodes.top();
 255             unvisited_nodes.pop();
 256             discover_nodes(next);
 257             adaptor_type::base_reference() = next;
 258         }
 259     }
 260
 261     ValueType const & dereference() const
 262     {
 263         return ValueExtractor::operator()(adaptor_type::base_reference()->value);
 264     }
 265
 266     void discover_nodes(const Node * n)
 267     {
 268         for (typename Node::const_child_iterator it = n->children.begin(); it != n->children.end(); ++it) {
 269             const Node * n = PointerExtractor::operator()(it);
 270             if (check_null_pointer && n == NULL)
 271                 continue;
 272             unvisited_nodes.push(n);
 273         }
 274     }
 275
 276     unvisited_node_container unvisited_nodes;
 277 };
 278
 279 template <typename Node, typename NodeList>
 280 struct list_iterator_converter
 281 {
 282     typename NodeList::const_iterator operator()(const Node * node)
 283     {
 284         return NodeList::s_iterator_to(*node);
 285     }
 286
 287     Node * operator()(typename NodeList::const_iterator it)
 288     {
 289         return const_cast<Node*>(static_cast<const Node*>(&*it));
 290     }
 291 };
 292
 293 template <typename Node,
 294           typename NodeIterator,
 295           typename ValueType,
 296           typename ValueExtractor = identity<typename Node::value_type>,
 297           typename IteratorCoverter = identity<NodeIterator>
 298          >
 299 class recursive_tree_iterator:
 300     public boost::iterator_adaptor<recursive_tree_iterator<Node,
 301                                                            NodeIterator,
 302                                                            ValueType,
 303                                                            ValueExtractor,
 304                                                            IteratorCoverter
 305                                                           >,
 306                                     NodeIterator,
 307                                     ValueType const,
 308                                     boost::bidirectional_traversal_tag>,
 309     ValueExtractor, IteratorCoverter
 310 {
 311     typedef boost::iterator_adaptor<recursive_tree_iterator<Node,
 312                                                             NodeIterator,
 313                                                             ValueType,
 314                                                             ValueExtractor,
 315                                                             IteratorCoverter
 316                                                            >,
 317                                     NodeIterator,
 318                                     ValueType const,
 319                                     boost::bidirectional_traversal_tag> adaptor_type;
 320
 321     friend class boost::iterator_core_access;
 322
 323
 324 public:
 325     recursive_tree_iterator(void):
 326         adaptor_type(0)
 327     {}
 328
 329     explicit recursive_tree_iterator(NodeIterator const & it):
 330         adaptor_type(it)
 331     {}
 332
 333     void increment(void)
 334     {
 335         NodeIterator next = adaptor_type::base_reference();
 336
 337         const Node * n = get_node(next);
 338         if (n->children.empty()) {
 339             const Node * parent = get_node(next)->get_parent();
 340
 341             ++next;
 342
 343             while (true) {
 344                 if (parent == NULL || next != parent->children.end())
 345                     break;
 346
 347                 next = IteratorCoverter::operator()(parent);
 348                 parent = get_node(next)->get_parent();
 349                 ++next;
 350             }
 351         } else
 352             next = n->children.begin();
 353
 354         adaptor_type::base_reference() = next;
 355         return;
 356     }
 357
 358     ValueType const & dereference() const
 359     {
 360         return ValueExtractor::operator()(get_node(adaptor_type::base_reference())->value);
 361     }
 362
 363     static const Node * get_node(NodeIterator const & it)
 364     {
 365         return static_cast<const Node *>(&*it);
 366     }
 367
 368     const Node * get_node() const
 369     {
 370         return get_node(adaptor_type::base_reference());
 371     }
 372 };
 373
 374
 375 } /* namespace detail */
 376 } /* namespace heap */
 377 } /* namespace boost */
 378
 379 #endif /* BOOST_HEAP_DETAIL_TREE_ITERATOR_HPP */