Attempt to represent the S^2->S^3 header reorganisation as a series of "hg rename" operations
2 //=======================================================================
3 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
4 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
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 //=======================================================================
11 #ifndef ADSTL_ARRAY_BINARY_TREE_HPP
12 #define ADSTL_ARRAY_BINARY_TREE_HPP
16 #include <boost/config.hpp>
20 Note: array_binary_tree is a completey balanced binary tree
23 #if !defined BOOST_NO_STD_ITERATOR_TRAITS
24 template <class RandomAccessIterator, class ID>
26 template <class RandomAccessIterator, class ValueType, class ID>
28 class array_binary_tree_node {
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
35 typedef typename std::iterator_traits<RandomAccessIterator>::value_type
38 typedef int difference_type;
39 typedef ValueType value_type;
41 typedef difference_type size_type;
43 struct children_type {
45 : boost::iterator<std::bidirectional_iterator_tag, ArrayBinaryTreeNode,
46 difference_type, array_binary_tree_node*, ArrayBinaryTreeNode&>
47 { // replace with iterator_adaptor implementation -JGS
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*/
57 inline iterator(rep_iterator rr,
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); }
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*/
83 inline children_type(rep_iterator rr,
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;
93 else if (c < n) s = 1;
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) {
109 /*egcs generate a warning*/
113 inline array_binary_tree_node(rep_iterator start,
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,
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);
126 inline bool has_parent() const { return i != 0; }
127 inline children_type children() { return children_type(r, i, n, id); }
129 inline void swap(array_binary_tree_node x) {
130 value_type tmp = x.value();
136 template <class ExternalData>
137 inline void swap(ArrayBinaryTreeNode x, ExternalData& edata ) {
140 value_type tmp = x.value();
142 /*swap external data*/
143 edata[ get(id, tmp) ] = i;
144 edata[ get(id, value()) ] = x.i;
150 inline const children_type children() const {
151 return children_type(r, i, n);
153 inline size_type index() const { return i; }
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) {}
167 template< class node_type >
168 inline bool operator()(const node_type& x, const node_type& y) {
169 return comp(x.value(), y.value());
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());
180 } /* namespace adstl */
182 #endif /* ADSTL_ARRAY_BINARY_TREE_H */