heap/detail/tree_iterator.hpp

0001 // boost heap: node tree iterator helper classes
0002 //
0003 // Copyright (C) 2010 Tim Blechmann
0004 //
0005 // Distributed under the Boost Software License, Version 1.0. (See
0006 // accompanying file LICENSE_1_0.txt or copy at
0007 // http://www.boost.org/LICENSE_1_0.txt)
0008
0009 #ifndef BOOST_HEAP_DETAIL_TREE_ITERATOR_HPP
0010 #define BOOST_HEAP_DETAIL_TREE_ITERATOR_HPP
0011
0012 #include <functional>
0013 #include <vector>
0014
0015 #include <boost/core/allocator_access.hpp>
0016 #include <boost/iterator/iterator_adaptor.hpp>
0017 #include <boost/type_traits/conditional.hpp>
0018 #include <queue>
0019
0020 namespace boost  {
0021 namespace heap   {
0022 namespace detail {
0023
0024
0025 template<typename type>
0026 struct identity
0027 {
0028     type& operator()(type& x) const BOOST_NOEXCEPT
0029     { return x; }
0030
0031     const type& operator()(const type& x) const BOOST_NOEXCEPT
0032     { return x; }
0033 };
0034
0035 template<typename Node>
0036 struct dereferencer
0037 {
0038     template <typename Iterator>
0039     Node * operator()(Iterator const & it)
0040     {
0041         return static_cast<Node *>(*it);
0042     }
0043 };
0044
0045 template<typename Node>
0046 struct pointer_to_reference
0047 {
0048     template <typename Iterator>
0049     const Node * operator()(Iterator const & it)
0050     {
0051         return static_cast<const Node *>(&*it);
0052     }
0053 };
0054
0055
0056 template <typename HandleType,
0057           typename Alloc,
0058           typename ValueCompare
0059          >
0060 struct unordered_tree_iterator_storage
0061 {
0062     unordered_tree_iterator_storage(ValueCompare const & cmp)
0063     {}
0064
0065     void push(HandleType h)
0066     {
0067         data_.push_back(h);
0068     }
0069
0070     HandleType const & top(void)
0071     {
0072         return data_.back();
0073     }
0074
0075     void pop(void)
0076     {
0077         data_.pop_back();
0078     }
0079
0080     bool empty(void) const
0081     {
0082         return data_.empty();
0083     }
0084
0085     std::vector<HandleType, typename boost::allocator_rebind<Alloc, HandleType>::type> data_;
0086 };
0087
0088 template <typename ValueType,
0089           typename HandleType,
0090           typename Alloc,
0091           typename ValueCompare,
0092           typename ValueExtractor
0093          >
0094 struct ordered_tree_iterator_storage:
0095     ValueExtractor
0096 {
0097     struct compare_values_by_handle:
0098         ValueExtractor,
0099         ValueCompare
0100     {
0101         compare_values_by_handle(ValueCompare const & cmp):
0102             ValueCompare(cmp)
0103         {}
0104
0105         bool operator()(HandleType const & lhs, HandleType const & rhs) const
0106         {
0107             ValueType const & lhs_value = ValueExtractor::operator()(lhs->value);
0108             ValueType const & rhs_value = ValueExtractor::operator()(rhs->value);
0109             return ValueCompare::operator()(lhs_value, rhs_value);
0110         }
0111     };
0112
0113     ordered_tree_iterator_storage(ValueCompare const & cmp):
0114         data_(compare_values_by_handle(cmp))
0115     {}
0116
0117     void push(HandleType h)
0118     {
0119         data_.push(h);
0120     }
0121
0122     void pop(void)
0123     {
0124         data_.pop();
0125     }
0126
0127     HandleType const & top(void)
0128     {
0129         return data_.top();
0130     }
0131
0132     bool empty(void) const BOOST_NOEXCEPT
0133     {
0134         return data_.empty();
0135     }
0136
0137     std::priority_queue<HandleType,
0138                         std::vector<HandleType, typename boost::allocator_rebind<Alloc, HandleType>::type>,
0139                         compare_values_by_handle> data_;
0140 };
0141
0142
0143 /* tree iterator helper class
0144  *
0145  * Requirements:
0146  * Node provides child_iterator
0147  * ValueExtractor can convert Node->value to ValueType
0148  *
0149  * */
0150 template <typename Node,
0151           typename ValueType,
0152           typename Alloc = std::allocator<Node>,
0153           typename ValueExtractor = identity<typename Node::value_type>,
0154           typename PointerExtractor = dereferencer<Node>,
0155           bool check_null_pointer = false,
0156           bool ordered_iterator = false,
0157           typename ValueCompare = std::less<ValueType>
0158          >
0159 class tree_iterator:
0160     public boost::iterator_adaptor<tree_iterator<Node,
0161                                                  ValueType,
0162                                                  Alloc,
0163                                                  ValueExtractor,
0164                                                  PointerExtractor,
0165                                                  check_null_pointer,
0166                                                  ordered_iterator,
0167                                                  ValueCompare
0168                                                 >,
0169                                    const Node *,
0170                                    ValueType,
0171                                    boost::forward_traversal_tag
0172                                   >,
0173     ValueExtractor,
0174     PointerExtractor
0175 {
0176     typedef boost::iterator_adaptor<tree_iterator<Node,
0177                                                   ValueType,
0178                                                   Alloc,
0179                                                   ValueExtractor,
0180                                                   PointerExtractor,
0181                                                   check_null_pointer,
0182                                                   ordered_iterator,
0183                                                   ValueCompare
0184                                                  >,
0185                                     const Node *,
0186                                     ValueType,
0187                                     boost::forward_traversal_tag
0188                                    > adaptor_type;
0189
0190     friend class boost::iterator_core_access;
0191
0192     typedef typename boost::conditional< ordered_iterator,
0193                                        ordered_tree_iterator_storage<ValueType, const Node*, Alloc, ValueCompare, ValueExtractor>,
0194                                        unordered_tree_iterator_storage<const Node*, Alloc, ValueCompare>
0195                                      >::type
0196         unvisited_node_container;
0197
0198 public:
0199     tree_iterator(void):
0200         adaptor_type(0), unvisited_nodes(ValueCompare())
0201     {}
0202
0203     tree_iterator(ValueCompare const & cmp):
0204         adaptor_type(0), unvisited_nodes(cmp)
0205     {}
0206
0207     tree_iterator(const Node * it, ValueCompare const & cmp):
0208         adaptor_type(it), unvisited_nodes(cmp)
0209     {
0210         if (it)
0211             discover_nodes(it);
0212     }
0213
0214     /* fills the iterator from a list of possible top nodes */
0215     template <typename NodePointerIterator>
0216     tree_iterator(NodePointerIterator begin, NodePointerIterator end, const Node * top_node, ValueCompare const & cmp):
0217         adaptor_type(0), unvisited_nodes(cmp)
0218     {
0219         BOOST_STATIC_ASSERT(ordered_iterator);
0220         if (begin == end)
0221             return;
0222
0223         adaptor_type::base_reference() = top_node;
0224         discover_nodes(top_node);
0225
0226         for (NodePointerIterator it = begin; it != end; ++it) {
0227             const Node * current_node = static_cast<const Node*>(&*it);
0228             if (current_node != top_node)
0229                 unvisited_nodes.push(current_node);
0230         }
0231     }
0232
0233     bool operator!=(tree_iterator const & rhs) const
0234     {
0235         return adaptor_type::base() != rhs.base();
0236     }
0237
0238     bool operator==(tree_iterator const & rhs) const
0239     {
0240         return !operator!=(rhs);
0241     }
0242
0243     const Node * get_node() const
0244     {
0245         return adaptor_type::base_reference();
0246     }
0247
0248 private:
0249     void increment(void)
0250     {
0251         if (unvisited_nodes.empty())
0252             adaptor_type::base_reference() = 0;
0253         else {
0254             const Node * next = unvisited_nodes.top();
0255             unvisited_nodes.pop();
0256             discover_nodes(next);
0257             adaptor_type::base_reference() = next;
0258         }
0259     }
0260
0261     ValueType const & dereference() const
0262     {
0263         return ValueExtractor::operator()(adaptor_type::base_reference()->value);
0264     }
0265
0266     void discover_nodes(const Node * n)
0267     {
0268         for (typename Node::const_child_iterator it = n->children.begin(); it != n->children.end(); ++it) {
0269             const Node * n = PointerExtractor::operator()(it);
0270             if (check_null_pointer && n == NULL)
0271                 continue;
0272             unvisited_nodes.push(n);
0273         }
0274     }
0275
0276     unvisited_node_container unvisited_nodes;
0277 };
0278
0279 template <typename Node, typename NodeList>
0280 struct list_iterator_converter
0281 {
0282     typename NodeList::const_iterator operator()(const Node * node)
0283     {
0284         return NodeList::s_iterator_to(*node);
0285     }
0286
0287     Node * operator()(typename NodeList::const_iterator it)
0288     {
0289         return const_cast<Node*>(static_cast<const Node*>(&*it));
0290     }
0291 };
0292
0293 template <typename Node,
0294           typename NodeIterator,
0295           typename ValueType,
0296           typename ValueExtractor = identity<typename Node::value_type>,
0297           typename IteratorCoverter = identity<NodeIterator>
0298          >
0299 class recursive_tree_iterator:
0300     public boost::iterator_adaptor<recursive_tree_iterator<Node,
0301                                                            NodeIterator,
0302                                                            ValueType,
0303                                                            ValueExtractor,
0304                                                            IteratorCoverter
0305                                                           >,
0306                                     NodeIterator,
0307                                     ValueType const,
0308                                     boost::bidirectional_traversal_tag>,
0309     ValueExtractor, IteratorCoverter
0310 {
0311     typedef boost::iterator_adaptor<recursive_tree_iterator<Node,
0312                                                             NodeIterator,
0313                                                             ValueType,
0314                                                             ValueExtractor,
0315                                                             IteratorCoverter
0316                                                            >,
0317                                     NodeIterator,
0318                                     ValueType const,
0319                                     boost::bidirectional_traversal_tag> adaptor_type;
0320
0321     friend class boost::iterator_core_access;
0322
0323
0324 public:
0325     recursive_tree_iterator(void):
0326         adaptor_type(0)
0327     {}
0328
0329     explicit recursive_tree_iterator(NodeIterator const & it):
0330         adaptor_type(it)
0331     {}
0332
0333     void increment(void)
0334     {
0335         NodeIterator next = adaptor_type::base_reference();
0336
0337         const Node * n = get_node(next);
0338         if (n->children.empty()) {
0339             const Node * parent = get_node(next)->get_parent();
0340
0341             ++next;
0342
0343             while (true) {
0344                 if (parent == NULL || next != parent->children.end())
0345                     break;
0346
0347                 next = IteratorCoverter::operator()(parent);
0348                 parent = get_node(next)->get_parent();
0349                 ++next;
0350             }
0351         } else
0352             next = n->children.begin();
0353
0354         adaptor_type::base_reference() = next;
0355         return;
0356     }
0357
0358     ValueType const & dereference() const
0359     {
0360         return ValueExtractor::operator()(get_node(adaptor_type::base_reference())->value);
0361     }
0362
0363     static const Node * get_node(NodeIterator const & it)
0364     {
0365         return static_cast<const Node *>(&*it);
0366     }
0367
0368     const Node * get_node() const
0369     {
0370         return get_node(adaptor_type::base_reference());
0371     }
0372 };
0373
0374
0375 } /* namespace detail */
0376 } /* namespace heap */
0377 } /* namespace boost */
0378
0379 #endif /* BOOST_HEAP_DETAIL_TREE_ITERATOR_HPP */