graph/detail/array_binary_tree.hpp

0001 //
0002 //=======================================================================
0003 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
0004 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
0005 //
0006 // Distributed under the Boost Software License, Version 1.0. (See
0007 // accompanying file LICENSE_1_0.txt or copy at
0008 // http://www.boost.org/LICENSE_1_0.txt)
0009 //=======================================================================
0010 //
0011 #ifndef BOOST_ARRAY_BINARY_TREE_HPP
0012 #define BOOST_ARRAY_BINARY_TREE_HPP
0013
0014 #include <iterator>
0015 #include <functional>
0016 #include <boost/config.hpp>
0017
0018 namespace boost
0019 {
0020
0021 /*
0022  * Note: array_binary_tree is a completey balanced binary tree.
0023  */
0024 #if !defined BOOST_NO_STD_ITERATOR_TRAITS
0025 template < class RandomAccessIterator, class ID >
0026 #else
0027 template < class RandomAccessIterator, class ValueType, class ID >
0028 #endif
0029 class array_binary_tree_node
0030 {
0031 public:
0032     typedef array_binary_tree_node ArrayBinaryTreeNode;
0033     typedef RandomAccessIterator rep_iterator;
0034 #if !defined BOOST_NO_STD_ITERATOR_TRAITS
0035     typedef
0036         typename std::iterator_traits< RandomAccessIterator >::difference_type
0037             difference_type;
0038     typedef typename std::iterator_traits< RandomAccessIterator >::value_type
0039         value_type;
0040 #else
0041     typedef int difference_type;
0042     typedef ValueType value_type;
0043 #endif
0044     typedef difference_type size_type;
0045
0046     struct children_type
0047     {
0048         struct iterator
0049         { // replace with iterator_adaptor implementation -JGS
0050             typedef std::bidirectional_iterator_tag iterator_category;
0051             typedef ArrayBinaryTreeNode value_type;
0052             typedef size_type difference_type;
0053             typedef array_binary_tree_node* pointer;
0054             typedef ArrayBinaryTreeNode& reference;
0055
0056             inline iterator() : i(0), n(0) {}
0057             inline iterator(const iterator& x)
0058             : r(x.r), i(x.i), n(x.n), id(x.id)
0059             {
0060             }
0061             inline iterator& operator=(const iterator& x)
0062             {
0063                 r = x.r;
0064                 i = x.i;
0065                 n = x.n;
0066                 /*egcs generate a warning*/
0067                 id = x.id;
0068                 return *this;
0069             }
0070             inline iterator(
0071                 rep_iterator rr, size_type ii, size_type nn, const ID& _id)
0072             : r(rr), i(ii), n(nn), id(_id)
0073             {
0074             }
0075             inline array_binary_tree_node operator*()
0076             {
0077                 return ArrayBinaryTreeNode(r, i, n, id);
0078             }
0079             inline iterator& operator++()
0080             {
0081                 ++i;
0082                 return *this;
0083             }
0084             inline iterator operator++(int)
0085             {
0086                 iterator t = *this;
0087                 ++(*this);
0088                 return t;
0089             }
0090             inline iterator& operator--()
0091             {
0092                 --i;
0093                 return *this;
0094             }
0095             inline iterator operator--(int)
0096             {
0097                 iterator t = *this;
0098                 --(*this);
0099                 return t;
0100             }
0101             inline bool operator==(const iterator& x) const { return i == x.i; }
0102             inline bool operator!=(const iterator& x) const
0103             {
0104                 return !(*this == x);
0105             }
0106             rep_iterator r;
0107             size_type i;
0108             size_type n;
0109             ID id;
0110         };
0111         inline children_type() : i(0), n(0) {}
0112         inline children_type(const children_type& x)
0113         : r(x.r), i(x.i), n(x.n), id(x.id)
0114         {
0115         }
0116         inline children_type& operator=(const children_type& x)
0117         {
0118             r = x.r;
0119             i = x.i;
0120             n = x.n;
0121             /*egcs generate a warning*/
0122             id = x.id;
0123             return *this;
0124         }
0125         inline children_type(
0126             rep_iterator rr, size_type ii, size_type nn, const ID& _id)
0127         : r(rr), i(ii), n(nn), id(_id)
0128         {
0129         }
0130         inline iterator begin() { return iterator(r, 2 * i + 1, n, id); }
0131         inline iterator end() { return iterator(r, 2 * i + 1 + size(), n, id); }
0132         inline size_type size() const
0133         {
0134             size_type c = 2 * i + 1;
0135             size_type s;
0136             if (c + 1 < n)
0137                 s = 2;
0138             else if (c < n)
0139                 s = 1;
0140             else
0141                 s = 0;
0142             return s;
0143         }
0144         rep_iterator r;
0145         size_type i;
0146         size_type n;
0147         ID id;
0148     };
0149     inline array_binary_tree_node() : i(0), n(0) {}
0150     inline array_binary_tree_node(const array_binary_tree_node& x)
0151     : r(x.r), i(x.i), n(x.n), id(x.id)
0152     {
0153     }
0154     inline ArrayBinaryTreeNode& operator=(const ArrayBinaryTreeNode& x)
0155     {
0156         r = x.r;
0157         i = x.i;
0158         n = x.n;
0159         /*egcs generate a warning*/
0160         id = x.id;
0161         return *this;
0162     }
0163     inline array_binary_tree_node(
0164         rep_iterator start, rep_iterator end, rep_iterator pos, const ID& _id)
0165     : r(start), i(pos - start), n(end - start), id(_id)
0166     {
0167     }
0168     inline array_binary_tree_node(
0169         rep_iterator rr, size_type ii, size_type nn, const ID& _id)
0170     : r(rr), i(ii), n(nn), id(_id)
0171     {
0172     }
0173     inline value_type& value() { return *(r + i); }
0174     inline const value_type& value() const { return *(r + i); }
0175     inline ArrayBinaryTreeNode parent() const
0176     {
0177         return ArrayBinaryTreeNode(r, (i - 1) / 2, n, id);
0178     }
0179     inline bool has_parent() const { return i != 0; }
0180     inline children_type children() { return children_type(r, i, n, id); }
0181     /*
0182     inline void swap(array_binary_tree_node x) {
0183       value_type tmp = x.value();
0184       x.value() = value();
0185       value() = tmp;
0186       i = x.i;
0187     }
0188     */
0189     template < class ExternalData >
0190     inline void swap(ArrayBinaryTreeNode x, ExternalData& edata)
0191     {
0192         using boost::get;
0193
0194         value_type tmp = x.value();
0195
0196         /*swap external data*/
0197         edata[get(id, tmp)] = i;
0198         edata[get(id, value())] = x.i;
0199
0200         x.value() = value();
0201         value() = tmp;
0202         i = x.i;
0203     }
0204     inline const children_type children() const
0205     {
0206         return children_type(r, i, n);
0207     }
0208     inline size_type index() const { return i; }
0209     rep_iterator r;
0210     size_type i;
0211     size_type n;
0212     ID id;
0213 };
0214
0215 template < class RandomAccessContainer,
0216     class Compare = std::less< typename RandomAccessContainer::value_type > >
0217 struct compare_array_node
0218 {
0219     typedef typename RandomAccessContainer::value_type value_type;
0220     compare_array_node(const Compare& x) : comp(x) {}
0221     compare_array_node(const compare_array_node& x) : comp(x.comp) {}
0222
0223     template < class node_type >
0224     inline bool operator()(const node_type& x, const node_type& y)
0225     {
0226         return comp(x.value(), y.value());
0227     }
0228
0229     template < class node_type >
0230     inline bool operator()(const node_type& x, const node_type& y) const
0231     {
0232         return comp(x.value(), y.value());
0233     }
0234     Compare comp;
0235 };
0236
0237 } // namespace boost
0238
0239 #endif /* BOOST_ARRAY_BINARY_TREE_HPP */