array_binary_tree.hpp

Boost provides free peer-reviewed portable C++ source libraries. We emphasize libraries that work

//
//=======================================================================
// 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 ADSTL_ARRAY_BINARY_TREE_HPP
#define ADSTL_ARRAY_BINARY_TREE_HPP

#include <iterator>
#include <functional>
#include <boost/config.hpp>

namespace adstl {
  /*
    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 adstl */

#endif /* ADSTL_ARRAY_BINARY_TREE_H */