| // 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 */ |