ceph/src/boost/boost/graph/detail/array_binary_tree.hpp

   1 //
   2 //=======================================================================
   3 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
   4 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
   5 //
   6 // Distributed under the Boost Software License, Version 1.0. (See
   7 // accompanying file LICENSE_1_0.txt or copy at
   8 // http://www.boost.org/LICENSE_1_0.txt)
   9 //=======================================================================
  10 //
  11 #ifndef BOOST_ARRAY_BINARY_TREE_HPP
  12 #define BOOST_ARRAY_BINARY_TREE_HPP
  13
  14 #include <iterator>
  15 #include <functional>
  16 #include <boost/config.hpp>
  17
  18 namespace boost
  19 {
  20
  21 /*
  22  * Note: array_binary_tree is a completey balanced binary tree.
  23  */
  24 #if !defined BOOST_NO_STD_ITERATOR_TRAITS
  25 template < class RandomAccessIterator, class ID >
  26 #else
  27 template < class RandomAccessIterator, class ValueType, class ID >
  28 #endif
  29 class array_binary_tree_node
  30 {
  31 public:
  32     typedef array_binary_tree_node ArrayBinaryTreeNode;
  33     typedef RandomAccessIterator rep_iterator;
  34 #if !defined BOOST_NO_STD_ITERATOR_TRAITS
  35     typedef
  36         typename std::iterator_traits< RandomAccessIterator >::difference_type
  37             difference_type;
  38     typedef typename std::iterator_traits< RandomAccessIterator >::value_type
  39         value_type;
  40 #else
  41     typedef int difference_type;
  42     typedef ValueType value_type;
  43 #endif
  44     typedef difference_type size_type;
  45
  46     struct children_type
  47     {
  48         struct iterator
  49         { // replace with iterator_adaptor implementation -JGS
  50             typedef std::bidirectional_iterator_tag iterator_category;
  51             typedef ArrayBinaryTreeNode value_type;
  52             typedef size_type difference_type;
  53             typedef array_binary_tree_node* pointer;
  54             typedef ArrayBinaryTreeNode& reference;
  55
  56             inline iterator() : i(0), n(0) {}
  57             inline iterator(const iterator& x)
  58             : r(x.r), i(x.i), n(x.n), id(x.id)
  59             {
  60             }
  61             inline iterator& operator=(const iterator& x)
  62             {
  63                 r = x.r;
  64                 i = x.i;
  65                 n = x.n;
  66                 /*egcs generate a warning*/
  67                 id = x.id;
  68                 return *this;
  69             }
  70             inline iterator(
  71                 rep_iterator rr, size_type ii, size_type nn, const ID& _id)
  72             : r(rr), i(ii), n(nn), id(_id)
  73             {
  74             }
  75             inline array_binary_tree_node operator*()
  76             {
  77                 return ArrayBinaryTreeNode(r, i, n, id);
  78             }
  79             inline iterator& operator++()
  80             {
  81                 ++i;
  82                 return *this;
  83             }
  84             inline iterator operator++(int)
  85             {
  86                 iterator t = *this;
  87                 ++(*this);
  88                 return t;
  89             }
  90             inline iterator& operator--()
  91             {
  92                 --i;
  93                 return *this;
  94             }
  95             inline iterator operator--(int)
  96             {
  97                 iterator t = *this;
  98                 --(*this);
  99                 return t;
 100             }
 101             inline bool operator==(const iterator& x) const { return i == x.i; }
 102             inline bool operator!=(const iterator& x) const
 103             {
 104                 return !(*this == x);
 105             }
 106             rep_iterator r;
 107             size_type i;
 108             size_type n;
 109             ID id;
 110         };
 111         inline children_type() : i(0), n(0) {}
 112         inline children_type(const children_type& x)
 113         : r(x.r), i(x.i), n(x.n), id(x.id)
 114         {
 115         }
 116         inline children_type& operator=(const children_type& x)
 117         {
 118             r = x.r;
 119             i = x.i;
 120             n = x.n;
 121             /*egcs generate a warning*/
 122             id = x.id;
 123             return *this;
 124         }
 125         inline children_type(
 126             rep_iterator rr, size_type ii, size_type nn, const ID& _id)
 127         : r(rr), i(ii), n(nn), id(_id)
 128         {
 129         }
 130         inline iterator begin() { return iterator(r, 2 * i + 1, n, id); }
 131         inline iterator end() { return iterator(r, 2 * i + 1 + size(), n, id); }
 132         inline size_type size() const
 133         {
 134             size_type c = 2 * i + 1;
 135             size_type s;
 136             if (c + 1 < n)
 137                 s = 2;
 138             else if (c < n)
 139                 s = 1;
 140             else
 141                 s = 0;
 142             return s;
 143         }
 144         rep_iterator r;
 145         size_type i;
 146         size_type n;
 147         ID id;
 148     };
 149     inline array_binary_tree_node() : i(0), n(0) {}
 150     inline array_binary_tree_node(const array_binary_tree_node& x)
 151     : r(x.r), i(x.i), n(x.n), id(x.id)
 152     {
 153     }
 154     inline ArrayBinaryTreeNode& operator=(const ArrayBinaryTreeNode& x)
 155     {
 156         r = x.r;
 157         i = x.i;
 158         n = x.n;
 159         /*egcs generate a warning*/
 160         id = x.id;
 161         return *this;
 162     }
 163     inline array_binary_tree_node(
 164         rep_iterator start, rep_iterator end, rep_iterator pos, const ID& _id)
 165     : r(start), i(pos - start), n(end - start), id(_id)
 166     {
 167     }
 168     inline array_binary_tree_node(
 169         rep_iterator rr, size_type ii, size_type nn, const ID& _id)
 170     : r(rr), i(ii), n(nn), id(_id)
 171     {
 172     }
 173     inline value_type& value() { return *(r + i); }
 174     inline const value_type& value() const { return *(r + i); }
 175     inline ArrayBinaryTreeNode parent() const
 176     {
 177         return ArrayBinaryTreeNode(r, (i - 1) / 2, n, id);
 178     }
 179     inline bool has_parent() const { return i != 0; }
 180     inline children_type children() { return children_type(r, i, n, id); }
 181     /*
 182     inline void swap(array_binary_tree_node x) {
 183       value_type tmp = x.value();
 184       x.value() = value();
 185       value() = tmp;
 186       i = x.i;
 187     }
 188     */
 189     template < class ExternalData >
 190     inline void swap(ArrayBinaryTreeNode x, ExternalData& edata)
 191     {
 192         using boost::get;
 193
 194         value_type tmp = x.value();
 195
 196         /*swap external data*/
 197         edata[get(id, tmp)] = i;
 198         edata[get(id, value())] = x.i;
 199
 200         x.value() = value();
 201         value() = tmp;
 202         i = x.i;
 203     }
 204     inline const children_type children() const
 205     {
 206         return children_type(r, i, n);
 207     }
 208     inline size_type index() const { return i; }
 209     rep_iterator r;
 210     size_type i;
 211     size_type n;
 212     ID id;
 213 };
 214
 215 template < class RandomAccessContainer,
 216     class Compare = std::less< typename RandomAccessContainer::value_type > >
 217 struct compare_array_node
 218 {
 219     typedef typename RandomAccessContainer::value_type value_type;
 220     compare_array_node(const Compare& x) : comp(x) {}
 221     compare_array_node(const compare_array_node& x) : comp(x.comp) {}
 222
 223     template < class node_type >
 224     inline bool operator()(const node_type& x, const node_type& y)
 225     {
 226         return comp(x.value(), y.value());
 227     }
 228
 229     template < class node_type >
 230     inline bool operator()(const node_type& x, const node_type& y) const
 231     {
 232         return comp(x.value(), y.value());
 233     }
 234     Compare comp;
 235 };
 236
 237 } // namespace boost
 238
 239 #endif /* BOOST_ARRAY_BINARY_TREE_HPP */