epoc32/include/stdapis/boost/graph/detail/array_binary_tree.hpp
author William Roberts <williamr@symbian.org>
Wed, 31 Mar 2010 12:27:01 +0100
branchSymbian2
changeset 3 e1b950c65cb4
permissions -rw-r--r--
Attempt to represent the S^2->S^3 header reorganisation as a series of "hg rename" operations
     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 ADSTL_ARRAY_BINARY_TREE_HPP
    12 #define ADSTL_ARRAY_BINARY_TREE_HPP
    13 
    14 #include <iterator>
    15 #include <functional>
    16 #include <boost/config.hpp>
    17 
    18 namespace adstl {
    19   /*
    20     Note: array_binary_tree is a completey balanced binary tree
    21    */
    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 bool operator==(const iterator& x) const { return i == x.i; }
    67       inline bool operator!=(const iterator& x) const 
    68         { return !(*this == x); }
    69       rep_iterator r;
    70       size_type i;
    71       size_type n;
    72       ID id;
    73     };
    74     inline children_type() : i(0), n(0) { }
    75     inline children_type(const children_type& x)
    76       : r(x.r), i(x.i), n(x.n), id(x.id) { }
    77     inline children_type& operator=(const children_type& x) {
    78       r = x.r; i = x.i; n = x.n; 
    79       /*egcs generate a warning*/
    80       id = x.id; 
    81       return *this;
    82     }
    83     inline children_type(rep_iterator rr,
    84                          size_type ii, 
    85                          size_type nn,
    86                          const ID& _id) : r(rr), i(ii), n(nn), id(_id) { }
    87     inline iterator begin() { return iterator(r, 2 * i + 1, n, id); }
    88     inline iterator end() { return iterator(r, 2 * i + 1 + size(), n, id); }
    89     inline size_type size() const {
    90       size_type c = 2 * i + 1;
    91       size_type s;
    92       if      (c + 1 < n) s = 2;
    93       else if (c < n)     s = 1;
    94       else                s = 0;
    95       return s;
    96     }
    97     rep_iterator r;
    98     size_type i;
    99     size_type n;
   100     ID id;
   101   };
   102   inline array_binary_tree_node() : i(0), n(0) { }
   103   inline array_binary_tree_node(const array_binary_tree_node& x) 
   104     : r(x.r), i(x.i), n(x.n), id(x.id) { }
   105   inline ArrayBinaryTreeNode& operator=(const ArrayBinaryTreeNode& x) {
   106     r = x.r;
   107     i = x.i; 
   108     n = x.n; 
   109     /*egcs generate a warning*/
   110     id = x.id; 
   111     return *this;
   112   }
   113   inline array_binary_tree_node(rep_iterator start, 
   114                                 rep_iterator end, 
   115                                 rep_iterator pos, const ID& _id)
   116     : r(start), i(pos - start), n(end - start), id(_id) { }
   117   inline array_binary_tree_node(rep_iterator rr, 
   118                                 size_type ii, 
   119                                 size_type nn, const ID& _id) 
   120     : r(rr), i(ii), n(nn), id(_id) { }
   121   inline value_type& value() { return *(r + i); }
   122   inline const value_type& value() const { return *(r + i); }
   123   inline ArrayBinaryTreeNode parent() const {
   124     return ArrayBinaryTreeNode(r, (i - 1) / 2, n, id);
   125   }
   126   inline bool has_parent() const { return i != 0; }
   127   inline children_type children() { return children_type(r, i, n, id); }
   128   /*
   129   inline void swap(array_binary_tree_node x) {
   130     value_type tmp = x.value();
   131     x.value() = value();
   132     value() = tmp;
   133     i = x.i;
   134   }
   135   */
   136   template <class ExternalData>
   137   inline void swap(ArrayBinaryTreeNode x, ExternalData& edata ) {
   138     using boost::get;
   139 
   140     value_type tmp = x.value();
   141 
   142     /*swap external data*/
   143     edata[ get(id, tmp) ]     = i;
   144     edata[ get(id, value()) ] = x.i;
   145 
   146     x.value() = value();
   147     value() = tmp;
   148     i = x.i;
   149   }
   150    inline const children_type children() const { 
   151     return children_type(r, i, n); 
   152   }
   153   inline size_type index() const { return i; }
   154   rep_iterator r;
   155   size_type i;
   156   size_type n;
   157   ID id;
   158 };
   159 
   160 template <class RandomAccessContainer, 
   161        class Compare = std::less<typename RandomAccessContainer::value_type> >
   162 struct compare_array_node {
   163   typedef typename RandomAccessContainer::value_type value_type;
   164   compare_array_node(const Compare& x) : comp(x) {}
   165   compare_array_node(const compare_array_node& x) : comp(x.comp) {}
   166 
   167   template< class node_type >
   168   inline bool operator()(const node_type& x, const node_type& y) {
   169     return comp(x.value(), y.value());
   170   }
   171 
   172   template< class node_type >
   173   inline bool operator()(const node_type& x, const node_type& y) const {
   174     return comp(x.value(), y.value());
   175   }
   176   Compare comp;
   177 };
   178 
   179 
   180 } /* namespace adstl */
   181 
   182 #endif /* ADSTL_ARRAY_BINARY_TREE_H */