Ugly, not-to-be-pushed sucking in of all of Boost to get windows to work.
[dyninst.git] / external / 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 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     value_type tmp = x.value();
139
140     /*swap external data*/
141     edata[ boost::get(id, tmp) ]     = i;
142     edata[ boost::get(id, value()) ] = x.i;
143
144     x.value() = value();
145     value() = tmp;
146     i = x.i;
147   }
148    inline const children_type children() const { 
149     return children_type(r, i, n); 
150   }
151   inline size_type index() const { return i; }
152   rep_iterator r;
153   size_type i;
154   size_type n;
155   ID id;
156 };
157
158 template <class RandomAccessContainer, 
159        class Compare = std::less<typename RandomAccessContainer::value_type> >
160 struct compare_array_node {
161   typedef typename RandomAccessContainer::value_type value_type;
162   compare_array_node(const Compare& x) : comp(x) {}
163   compare_array_node(const compare_array_node& x) : comp(x.comp) {}
164
165   template< class node_type >
166   inline bool operator()(const node_type& x, const node_type& y) {
167     return comp(x.value(), y.value());
168   }
169
170   template< class node_type >
171   inline bool operator()(const node_type& x, const node_type& y) const {
172     return comp(x.value(), y.value());
173   }
174   Compare comp;
175 };
176
177
178 } /* namespace adstl */
179
180 #endif /* ADSTL_ARRAY_BINARY_TREE_H */