Chris@16: // boost heap: node tree iterator helper classes
Chris@16: //
Chris@16: // Copyright (C) 2010 Tim Blechmann
Chris@16: //
Chris@16: // Distributed under the Boost Software License, Version 1.0. (See
Chris@16: // accompanying file LICENSE_1_0.txt or copy at
Chris@16: // http://www.boost.org/LICENSE_1_0.txt)
Chris@16: 
Chris@16: // Disclaimer: Not a Boost library.
Chris@16: 
Chris@16: #ifndef BOOST_HEAP_DETAIL_TREE_ITERATOR_HPP
Chris@16: #define BOOST_HEAP_DETAIL_TREE_ITERATOR_HPP
Chris@16: 
Chris@16: #include <functional>
Chris@16: #include <vector>
Chris@16: 
Chris@16: #include <boost/iterator/iterator_adaptor.hpp>
Chris@16: #include <queue>
Chris@16: 
Chris@16: namespace boost  {
Chris@16: namespace heap   {
Chris@16: namespace detail {
Chris@16: 
Chris@16: 
Chris@16: template<typename type>
Chris@16: struct identity:
Chris@16:     public std::unary_function<type,type>
Chris@16: {
Chris@16:     type& operator()(type& x) const
Chris@16:     { return x; }
Chris@16: 
Chris@16:     const type& operator()(const type& x) const
Chris@16:     { return x; }
Chris@16: };
Chris@16: 
Chris@16: template<typename type>
Chris@16: struct caster:
Chris@16:     public std::unary_function<type,type>
Chris@16: {
Chris@16:     template <typename U>
Chris@16:     type& operator()(U& x) const
Chris@16:     { return static_cast<type&>(x); }
Chris@16: 
Chris@16:     template <typename U>
Chris@16:     const type& operator()(const U& x) const
Chris@16:     { return static_cast<const type&>(x); }
Chris@16: };
Chris@16: 
Chris@16: template<typename Node>
Chris@16: struct dereferencer
Chris@16: {
Chris@16:     template <typename Iterator>
Chris@16:     Node * operator()(Iterator const & it)
Chris@16:     {
Chris@16:         return static_cast<Node *>(*it);
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@16: template<typename Node>
Chris@16: struct pointer_to_reference
Chris@16: {
Chris@16:     template <typename Iterator>
Chris@16:     const Node * operator()(Iterator const & it)
Chris@16:     {
Chris@16:         return static_cast<const Node *>(&*it);
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@16: 
Chris@16: template <typename HandleType,
Chris@16:           typename Alloc,
Chris@16:           typename ValueCompare
Chris@16:          >
Chris@16: struct unordered_tree_iterator_storage
Chris@16: {
Chris@16:     unordered_tree_iterator_storage(ValueCompare const & cmp)
Chris@16:     {}
Chris@16: 
Chris@16:     void push(HandleType h)
Chris@16:     {
Chris@16:         data_.push_back(h);
Chris@16:     }
Chris@16: 
Chris@16:     HandleType const & top(void)
Chris@16:     {
Chris@16:         return data_.back();
Chris@16:     }
Chris@16: 
Chris@16:     void pop(void)
Chris@16:     {
Chris@16:         data_.pop_back();
Chris@16:     }
Chris@16: 
Chris@16:     bool empty(void) const
Chris@16:     {
Chris@16:         return data_.empty();
Chris@16:     }
Chris@16: 
Chris@16:     std::vector<HandleType, typename Alloc::template rebind<HandleType>::other > data_;
Chris@16: };
Chris@16: 
Chris@16: template <typename ValueType,
Chris@16:           typename HandleType,
Chris@16:           typename Alloc,
Chris@16:           typename ValueCompare,
Chris@16:           typename ValueExtractor
Chris@16:          >
Chris@16: struct ordered_tree_iterator_storage:
Chris@16:     ValueExtractor
Chris@16: {
Chris@16:     struct compare_values_by_handle:
Chris@16:         ValueExtractor,
Chris@16:         ValueCompare
Chris@16:     {
Chris@16:         compare_values_by_handle(ValueCompare const & cmp):
Chris@16:             ValueCompare(cmp)
Chris@16:         {}
Chris@16: 
Chris@16:         bool operator()(HandleType const & lhs, HandleType const & rhs) const
Chris@16:         {
Chris@16:             ValueType const & lhs_value = ValueExtractor::operator()(lhs->value);
Chris@16:             ValueType const & rhs_value = ValueExtractor::operator()(rhs->value);
Chris@16:             return ValueCompare::operator()(lhs_value, rhs_value);
Chris@16:         }
Chris@16:     };
Chris@16: 
Chris@16:     ordered_tree_iterator_storage(ValueCompare const & cmp):
Chris@16:         data_(compare_values_by_handle(cmp))
Chris@16:     {}
Chris@16: 
Chris@16:     void push(HandleType h)
Chris@16:     {
Chris@16:         data_.push(h);
Chris@16:     }
Chris@16: 
Chris@16:     void pop(void)
Chris@16:     {
Chris@16:         data_.pop();
Chris@16:     }
Chris@16: 
Chris@16:     HandleType const & top(void)
Chris@16:     {
Chris@16:         return data_.top();
Chris@16:     }
Chris@16: 
Chris@16:     bool empty(void) const
Chris@16:     {
Chris@16:         return data_.empty();
Chris@16:     }
Chris@16: 
Chris@16:     std::priority_queue<HandleType,
Chris@16:                         std::vector<HandleType, typename Alloc::template rebind<HandleType>::other>,
Chris@16:                         compare_values_by_handle> data_;
Chris@16: };
Chris@16: 
Chris@16: 
Chris@16: /* tree iterator helper class
Chris@16:  *
Chris@16:  * Requirements:
Chris@16:  * Node provides child_iterator
Chris@16:  * ValueExtractor can convert Node->value to ValueType
Chris@16:  *
Chris@16:  * */
Chris@16: template <typename Node,
Chris@16:           typename ValueType,
Chris@16:           typename Alloc = std::allocator<Node>,
Chris@16:           typename ValueExtractor = identity<typename Node::value_type>,
Chris@16:           typename PointerExtractor = dereferencer<Node>,
Chris@16:           bool check_null_pointer = false,
Chris@16:           bool ordered_iterator = false,
Chris@16:           typename ValueCompare = std::less<ValueType>
Chris@16:          >
Chris@16: class tree_iterator:
Chris@16:     public boost::iterator_adaptor<tree_iterator<Node,
Chris@16:                                                  ValueType,
Chris@16:                                                  Alloc,
Chris@16:                                                  ValueExtractor,
Chris@16:                                                  PointerExtractor,
Chris@16:                                                  check_null_pointer,
Chris@16:                                                  ordered_iterator,
Chris@16:                                                  ValueCompare
Chris@16:                                                 >,
Chris@16:                                    const Node *,
Chris@16:                                    ValueType,
Chris@16:                                    boost::forward_traversal_tag
Chris@16:                                   >,
Chris@16:     ValueExtractor,
Chris@16:     PointerExtractor
Chris@16: {
Chris@16:     typedef boost::iterator_adaptor<tree_iterator<Node,
Chris@16:                                                   ValueType,
Chris@16:                                                   Alloc,
Chris@16:                                                   ValueExtractor,
Chris@16:                                                   PointerExtractor,
Chris@16:                                                   check_null_pointer,
Chris@16:                                                   ordered_iterator,
Chris@16:                                                   ValueCompare
Chris@16:                                                  >,
Chris@16:                                     const Node *,
Chris@16:                                     ValueType,
Chris@16:                                     boost::forward_traversal_tag
Chris@16:                                    > adaptor_type;
Chris@16: 
Chris@16:     friend class boost::iterator_core_access;
Chris@16: 
Chris@16:     typedef typename boost::mpl::if_c< ordered_iterator,
Chris@16:                                        ordered_tree_iterator_storage<ValueType, const Node*, Alloc, ValueCompare, ValueExtractor>,
Chris@16:                                        unordered_tree_iterator_storage<const Node*, Alloc, ValueCompare>
Chris@16:                                      >::type
Chris@16:         unvisited_node_container;
Chris@16: 
Chris@16: public:
Chris@16:     tree_iterator(void):
Chris@16:         adaptor_type(0), unvisited_nodes(ValueCompare())
Chris@16:     {}
Chris@16: 
Chris@16:     tree_iterator(ValueCompare const & cmp):
Chris@16:         adaptor_type(0), unvisited_nodes(cmp)
Chris@16:     {}
Chris@16: 
Chris@16:     tree_iterator(const Node * it, ValueCompare const & cmp):
Chris@16:         adaptor_type(it), unvisited_nodes(cmp)
Chris@16:     {
Chris@16:         if (it)
Chris@16:             discover_nodes(it);
Chris@16:     }
Chris@16: 
Chris@16:     /* fills the iterator from a list of possible top nodes */
Chris@16:     template <typename NodePointerIterator>
Chris@16:     tree_iterator(NodePointerIterator begin, NodePointerIterator end, const Node * top_node, ValueCompare const & cmp):
Chris@16:         adaptor_type(0), unvisited_nodes(cmp)
Chris@16:     {
Chris@16:         BOOST_STATIC_ASSERT(ordered_iterator);
Chris@16:         if (begin == end)
Chris@16:             return;
Chris@16: 
Chris@16:         adaptor_type::base_reference() = top_node;
Chris@16:         discover_nodes(top_node);
Chris@16: 
Chris@16:         for (NodePointerIterator it = begin; it != end; ++it) {
Chris@16:             const Node * current_node = static_cast<const Node*>(&*it);
Chris@16:             if (current_node != top_node)
Chris@16:                 unvisited_nodes.push(current_node);
Chris@16:         }
Chris@16:     }
Chris@16: 
Chris@16:     bool operator!=(tree_iterator const & rhs) const
Chris@16:     {
Chris@16:         return adaptor_type::base() != rhs.base();
Chris@16:     }
Chris@16: 
Chris@16:     bool operator==(tree_iterator const & rhs) const
Chris@16:     {
Chris@16:         return !operator!=(rhs);
Chris@16:     }
Chris@16: 
Chris@16:     const Node * get_node() const
Chris@16:     {
Chris@16:         return adaptor_type::base_reference();
Chris@16:     }
Chris@16: 
Chris@16: private:
Chris@16:     void increment(void)
Chris@16:     {
Chris@16:         if (unvisited_nodes.empty())
Chris@16:             adaptor_type::base_reference() = 0;
Chris@16:         else {
Chris@16:             const Node * next = unvisited_nodes.top();
Chris@16:             unvisited_nodes.pop();
Chris@16:             discover_nodes(next);
Chris@16:             adaptor_type::base_reference() = next;
Chris@16:         }
Chris@16:     }
Chris@16: 
Chris@16:     ValueType const & dereference() const
Chris@16:     {
Chris@16:         return ValueExtractor::operator()(adaptor_type::base_reference()->value);
Chris@16:     }
Chris@16: 
Chris@16:     void discover_nodes(const Node * n)
Chris@16:     {
Chris@16:         for (typename Node::const_child_iterator it = n->children.begin(); it != n->children.end(); ++it) {
Chris@16:             const Node * n = PointerExtractor::operator()(it);
Chris@16:             if (check_null_pointer && n == NULL)
Chris@16:                 continue;
Chris@16:             unvisited_nodes.push(n);
Chris@16:         }
Chris@16:     }
Chris@16: 
Chris@16:     unvisited_node_container unvisited_nodes;
Chris@16: };
Chris@16: 
Chris@16: template <typename Node, typename NodeList>
Chris@16: struct list_iterator_converter
Chris@16: {
Chris@16:     typename NodeList::const_iterator operator()(const Node * node)
Chris@16:     {
Chris@16:         return NodeList::s_iterator_to(*node);
Chris@16:     }
Chris@16: 
Chris@16:     Node * operator()(typename NodeList::const_iterator it)
Chris@16:     {
Chris@16:         return const_cast<Node*>(static_cast<const Node*>(&*it));
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@16: template <typename Node,
Chris@16:           typename NodeIterator,
Chris@16:           typename ValueType,
Chris@16:           typename ValueExtractor = identity<typename Node::value_type>,
Chris@16:           typename IteratorCoverter = identity<NodeIterator>
Chris@16:          >
Chris@16: class recursive_tree_iterator:
Chris@16:     public boost::iterator_adaptor<recursive_tree_iterator<Node,
Chris@16:                                                            NodeIterator,
Chris@16:                                                            ValueType,
Chris@16:                                                            ValueExtractor,
Chris@16:                                                            IteratorCoverter
Chris@16:                                                           >,
Chris@16:                                     NodeIterator,
Chris@16:                                     ValueType const,
Chris@16:                                     boost::bidirectional_traversal_tag>,
Chris@16:     ValueExtractor, IteratorCoverter
Chris@16: {
Chris@16:     typedef boost::iterator_adaptor<recursive_tree_iterator<Node,
Chris@16:                                                             NodeIterator,
Chris@16:                                                             ValueType,
Chris@16:                                                             ValueExtractor,
Chris@16:                                                             IteratorCoverter
Chris@16:                                                            >,
Chris@16:                                     NodeIterator,
Chris@16:                                     ValueType const,
Chris@16:                                     boost::bidirectional_traversal_tag> adaptor_type;
Chris@16: 
Chris@16:     friend class boost::iterator_core_access;
Chris@16: 
Chris@16: 
Chris@16: public:
Chris@16:     recursive_tree_iterator(void):
Chris@16:         adaptor_type(0)
Chris@16:     {}
Chris@16: 
Chris@16:     explicit recursive_tree_iterator(NodeIterator const & it):
Chris@16:         adaptor_type(it)
Chris@16:     {}
Chris@16: 
Chris@16:     void increment(void)
Chris@16:     {
Chris@16:         NodeIterator next = adaptor_type::base_reference();
Chris@16: 
Chris@16:         const Node * n = get_node(next);
Chris@16:         if (n->children.empty()) {
Chris@16:             const Node * parent = get_node(next)->get_parent();
Chris@16: 
Chris@16:             ++next;
Chris@16: 
Chris@16:             while (true) {
Chris@16:                 if (parent == NULL || next != parent->children.end())
Chris@16:                     break;
Chris@16: 
Chris@16:                 next = IteratorCoverter::operator()(parent);
Chris@16:                 parent = get_node(next)->get_parent();
Chris@16:                 ++next;
Chris@16:             }
Chris@16:         } else
Chris@16:             next = n->children.begin();
Chris@16: 
Chris@16:         adaptor_type::base_reference() = next;
Chris@16:         return;
Chris@16:     }
Chris@16: 
Chris@16:     ValueType const & dereference() const
Chris@16:     {
Chris@16:         return ValueExtractor::operator()(get_node(adaptor_type::base_reference())->value);
Chris@16:     }
Chris@16: 
Chris@16:     static const Node * get_node(NodeIterator const & it)
Chris@16:     {
Chris@16:         return static_cast<const Node *>(&*it);
Chris@16:     }
Chris@16: 
Chris@16:     const Node * get_node() const
Chris@16:     {
Chris@16:         return get_node(adaptor_type::base_reference());
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@16: 
Chris@16: } /* namespace detail */
Chris@16: } /* namespace heap */
Chris@16: } /* namespace boost */
Chris@16: 
Chris@16: #endif /* BOOST_HEAP_DETAIL_TREE_ITERATOR_HPP */