//

//=======================================================================

// 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 */