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