// | |
//======================================================================= | |
// Copyright 1997, 1998, 1999, 2000 University of Notre Dame. | |
// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek | |
// | |
// Distributed under the Boost Software License, Version 1.0. (See | |
// accompanying file LICENSE_1_0.txt or copy at | |
// http://www.boost.org/LICENSE_1_0.txt) | |
//======================================================================= | |
// | |
#ifndef BOOST_ARRAY_BINARY_TREE_HPP | |
#define BOOST_ARRAY_BINARY_TREE_HPP | |
#include <iterator> | |
#include <functional> | |
#include <boost/config.hpp> | |
namespace boost { | |
/* | |
* Note: array_binary_tree is a completey balanced binary tree. | |
*/ | |
#if !defined BOOST_NO_STD_ITERATOR_TRAITS | |
template <class RandomAccessIterator, class ID> | |
#else | |
template <class RandomAccessIterator, class ValueType, class ID> | |
#endif | |
class array_binary_tree_node { | |
public: | |
typedef array_binary_tree_node ArrayBinaryTreeNode; | |
typedef RandomAccessIterator rep_iterator; | |
#if !defined BOOST_NO_STD_ITERATOR_TRAITS | |
typedef typename std::iterator_traits<RandomAccessIterator>::difference_type | |
difference_type; | |
typedef typename std::iterator_traits<RandomAccessIterator>::value_type | |
value_type; | |
#else | |
typedef int difference_type; | |
typedef ValueType value_type; | |
#endif | |
typedef difference_type size_type; | |
struct children_type { | |
struct iterator | |
: boost::iterator<std::bidirectional_iterator_tag, ArrayBinaryTreeNode, | |
difference_type, array_binary_tree_node*, ArrayBinaryTreeNode&> | |
{ // replace with iterator_adaptor implementation -JGS | |
inline iterator() : i(0), n(0) { } | |
inline iterator(const iterator& x) : r(x.r), i(x.i), n(x.n), id(x.id) { } | |
inline iterator& operator=(const iterator& x) { | |
r = x.r; i = x.i; n = x.n; | |
/*egcs generate a warning*/ | |
id = x.id; | |
return *this; | |
} | |
inline iterator(rep_iterator rr, | |
size_type ii, | |
size_type nn, | |
const ID& _id) : r(rr), i(ii), n(nn), id(_id) { } | |
inline array_binary_tree_node operator*() { | |
return ArrayBinaryTreeNode(r, i, n, id); } | |
inline iterator& operator++() { ++i; return *this; } | |
inline iterator operator++(int) | |
{ iterator t = *this; ++(*this); return t; } | |
inline bool operator==(const iterator& x) const { return i == x.i; } | |
inline bool operator!=(const iterator& x) const | |
{ return !(*this == x); } | |
rep_iterator r; | |
size_type i; | |
size_type n; | |
ID id; | |
}; | |
inline children_type() : i(0), n(0) { } | |
inline children_type(const children_type& x) | |
: r(x.r), i(x.i), n(x.n), id(x.id) { } | |
inline children_type& operator=(const children_type& x) { | |
r = x.r; i = x.i; n = x.n; | |
/*egcs generate a warning*/ | |
id = x.id; | |
return *this; | |
} | |
inline children_type(rep_iterator rr, | |
size_type ii, | |
size_type nn, | |
const ID& _id) : r(rr), i(ii), n(nn), id(_id) { } | |
inline iterator begin() { return iterator(r, 2 * i + 1, n, id); } | |
inline iterator end() { return iterator(r, 2 * i + 1 + size(), n, id); } | |
inline size_type size() const { | |
size_type c = 2 * i + 1; | |
size_type s; | |
if (c + 1 < n) s = 2; | |
else if (c < n) s = 1; | |
else s = 0; | |
return s; | |
} | |
rep_iterator r; | |
size_type i; | |
size_type n; | |
ID id; | |
}; | |
inline array_binary_tree_node() : i(0), n(0) { } | |
inline array_binary_tree_node(const array_binary_tree_node& x) | |
: r(x.r), i(x.i), n(x.n), id(x.id) { } | |
inline ArrayBinaryTreeNode& operator=(const ArrayBinaryTreeNode& x) { | |
r = x.r; | |
i = x.i; | |
n = x.n; | |
/*egcs generate a warning*/ | |
id = x.id; | |
return *this; | |
} | |
inline array_binary_tree_node(rep_iterator start, | |
rep_iterator end, | |
rep_iterator pos, const ID& _id) | |
: r(start), i(pos - start), n(end - start), id(_id) { } | |
inline array_binary_tree_node(rep_iterator rr, | |
size_type ii, | |
size_type nn, const ID& _id) | |
: r(rr), i(ii), n(nn), id(_id) { } | |
inline value_type& value() { return *(r + i); } | |
inline const value_type& value() const { return *(r + i); } | |
inline ArrayBinaryTreeNode parent() const { | |
return ArrayBinaryTreeNode(r, (i - 1) / 2, n, id); | |
} | |
inline bool has_parent() const { return i != 0; } | |
inline children_type children() { return children_type(r, i, n, id); } | |
/* | |
inline void swap(array_binary_tree_node x) { | |
value_type tmp = x.value(); | |
x.value() = value(); | |
value() = tmp; | |
i = x.i; | |
} | |
*/ | |
template <class ExternalData> | |
inline void swap(ArrayBinaryTreeNode x, ExternalData& edata ) { | |
using boost::get; | |
value_type tmp = x.value(); | |
/*swap external data*/ | |
edata[ get(id, tmp) ] = i; | |
edata[ get(id, value()) ] = x.i; | |
x.value() = value(); | |
value() = tmp; | |
i = x.i; | |
} | |
inline const children_type children() const { | |
return children_type(r, i, n); | |
} | |
inline size_type index() const { return i; } | |
rep_iterator r; | |
size_type i; | |
size_type n; | |
ID id; | |
}; | |
template <class RandomAccessContainer, | |
class Compare = std::less<typename RandomAccessContainer::value_type> > | |
struct compare_array_node { | |
typedef typename RandomAccessContainer::value_type value_type; | |
compare_array_node(const Compare& x) : comp(x) {} | |
compare_array_node(const compare_array_node& x) : comp(x.comp) {} | |
template< class node_type > | |
inline bool operator()(const node_type& x, const node_type& y) { | |
return comp(x.value(), y.value()); | |
} | |
template< class node_type > | |
inline bool operator()(const node_type& x, const node_type& y) const { | |
return comp(x.value(), y.value()); | |
} | |
Compare comp; | |
}; | |
} // namespace boost | |
#endif /* BOOST_ARRAY_BINARY_TREE_HPP */ |