ceph/src/boost/libs/graph/include/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  * Note: array_binary_tree is a completey balanced binary tree.
  22  */
  23 #if !defined BOOST_NO_STD_ITERATOR_TRAITS
  24   template <class RandomAccessIterator, class ID>
  25 #else
  26   template <class RandomAccessIterator, class ValueType, class ID>
  27 #endif
  28 class array_binary_tree_node {
  29 public:
  30   typedef array_binary_tree_node ArrayBinaryTreeNode;
  31   typedef RandomAccessIterator rep_iterator;
  32 #if !defined BOOST_NO_STD_ITERATOR_TRAITS
  33   typedef typename std::iterator_traits<RandomAccessIterator>::difference_type
  34           difference_type;
  35   typedef typename std::iterator_traits<RandomAccessIterator>::value_type
  36           value_type;
  37 #else
  38   typedef int difference_type;
  39   typedef ValueType value_type;
  40 #endif
  41   typedef difference_type size_type;
  42
  43   struct children_type {
  44     struct iterator
  45         : boost::iterator<std::bidirectional_iterator_tag, ArrayBinaryTreeNode,
  46                        difference_type, array_binary_tree_node*, ArrayBinaryTreeNode&>
  47     { // replace with iterator_adaptor implementation -JGS
  48
  49       inline iterator() : i(0), n(0) { }
  50       inline iterator(const iterator& x) : r(x.r), i(x.i), n(x.n), id(x.id) { }
  51       inline iterator& operator=(const iterator& x) {
  52         r = x.r; i = x.i; n = x.n;
  53         /*egcs generate a warning*/
  54         id = x.id;
  55         return *this;
  56       }
  57       inline iterator(rep_iterator rr,
  58                       size_type ii,
  59                       size_type nn,
  60                       const ID& _id) : r(rr), i(ii), n(nn), id(_id) { }
  61       inline array_binary_tree_node operator*() {
  62         return ArrayBinaryTreeNode(r, i, n, id); }
  63       inline iterator& operator++() { ++i; return *this; }
  64       inline iterator operator++(int)
  65         { iterator t = *this; ++(*this); return t; }
  66       inline iterator& operator--() { --i; return *this; }
  67       inline iterator operator--(int)
  68         { iterator t = *this; --(*this); return t; }
  69       inline bool operator==(const iterator& x) const { return i == x.i; }
  70       inline bool operator!=(const iterator& x) const
  71         { return !(*this == x); }
  72       rep_iterator r;
  73       size_type i;
  74       size_type n;
  75       ID id;
  76     };
  77     inline children_type() : i(0), n(0) { }
  78     inline children_type(const children_type& x)
  79       : r(x.r), i(x.i), n(x.n), id(x.id) { }
  80     inline children_type& operator=(const children_type& x) {
  81       r = x.r; i = x.i; n = x.n;
  82       /*egcs generate a warning*/
  83       id = x.id;
  84       return *this;
  85     }
  86     inline children_type(rep_iterator rr,
  87                          size_type ii,
  88                          size_type nn,
  89                          const ID& _id) : r(rr), i(ii), n(nn), id(_id) { }
  90     inline iterator begin() { return iterator(r, 2 * i + 1, n, id); }
  91     inline iterator end() { return iterator(r, 2 * i + 1 + size(), n, id); }
  92     inline size_type size() const {
  93       size_type c = 2 * i + 1;
  94       size_type s;
  95       if      (c + 1 < n) s = 2;
  96       else if (c < n)     s = 1;
  97       else                s = 0;
  98       return s;
  99     }
 100     rep_iterator r;
 101     size_type i;
 102     size_type n;
 103     ID id;
 104   };
 105   inline array_binary_tree_node() : i(0), n(0) { }
 106   inline array_binary_tree_node(const array_binary_tree_node& x)
 107     : r(x.r), i(x.i), n(x.n), id(x.id) { }
 108   inline ArrayBinaryTreeNode& operator=(const ArrayBinaryTreeNode& x) {
 109     r = x.r;
 110     i = x.i;
 111     n = x.n;
 112     /*egcs generate a warning*/
 113     id = x.id;
 114     return *this;
 115   }
 116   inline array_binary_tree_node(rep_iterator start,
 117                                 rep_iterator end,
 118                                 rep_iterator pos, const ID& _id)
 119     : r(start), i(pos - start), n(end - start), id(_id) { }
 120   inline array_binary_tree_node(rep_iterator rr,
 121                                 size_type ii,
 122                                 size_type nn, const ID& _id)
 123     : r(rr), i(ii), n(nn), id(_id) { }
 124   inline value_type& value() { return *(r + i); }
 125   inline const value_type& value() const { return *(r + i); }
 126   inline ArrayBinaryTreeNode parent() const {
 127     return ArrayBinaryTreeNode(r, (i - 1) / 2, n, id);
 128   }
 129   inline bool has_parent() const { return i != 0; }
 130   inline children_type children() { return children_type(r, i, n, id); }
 131   /*
 132   inline void swap(array_binary_tree_node x) {
 133     value_type tmp = x.value();
 134     x.value() = value();
 135     value() = tmp;
 136     i = x.i;
 137   }
 138   */
 139   template <class ExternalData>
 140   inline void swap(ArrayBinaryTreeNode x, ExternalData& edata ) {
 141     using boost::get;
 142
 143     value_type tmp = x.value();
 144
 145     /*swap external data*/
 146     edata[ get(id, tmp) ]     = i;
 147     edata[ get(id, value()) ] = x.i;
 148
 149     x.value() = value();
 150     value() = tmp;
 151     i = x.i;
 152   }
 153    inline const children_type children() const {
 154     return children_type(r, i, n);
 155   }
 156   inline size_type index() const { return i; }
 157   rep_iterator r;
 158   size_type i;
 159   size_type n;
 160   ID id;
 161 };
 162
 163 template <class RandomAccessContainer,
 164        class Compare = std::less<typename RandomAccessContainer::value_type> >
 165 struct compare_array_node {
 166   typedef typename RandomAccessContainer::value_type value_type;
 167   compare_array_node(const Compare& x) : comp(x) {}
 168   compare_array_node(const compare_array_node& x) : comp(x.comp) {}
 169
 170   template< class node_type >
 171   inline bool operator()(const node_type& x, const node_type& y) {
 172     return comp(x.value(), y.value());
 173   }
 174
 175   template< class node_type >
 176   inline bool operator()(const node_type& x, const node_type& y) const {
 177     return comp(x.value(), y.value());
 178   }
 179   Compare comp;
 180 };
 181
 182 } // namespace boost
 183
 184 #endif /* BOOST_ARRAY_BINARY_TREE_HPP */