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