source: NonGTP/Boost/boost/graph/detail/array_binary_tree.hpp @ 857

Revision 857, 6.0 KB checked in by igarcia, 19 years ago (diff)
Line 
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
18namespace 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
28class array_binary_tree_node {
29public:
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
158template <class RandomAccessContainer,
159       class Compare = std::less<typename RandomAccessContainer::value_type> >
160struct 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 */
Note: See TracBrowser for help on using the repository browser.