// -*- c++ -*-
#pragma once

namespace cphstl {
  template <class T, class A = allocator<T> > class hashed_array_tree;

  template <class T, class A>
  class hat_iterator {
  private:
    typedef hat_iterator<T, A> iterator;

  public:
    typedef std::random_access_iterator_tag iterator_category;
    typedef T value_type;
    typedef typename A::pointer pointer;
    typedef typename A::reference reference;
    typedef typename A::difference_type difference_type;
    typedef typename A::size_type size_type;

    hat_iterator() : _pos(0), _hat(0) {}
    hat_iterator(hashed_array_tree<T, A>* hat) : _pos(0), _hat(hat) {}
    hat_iterator(size_type pos, hashed_array_tree<T, A>* hat) :
      _pos(pos), _hat(hat) {}

    iterator operator++(int) {
      size_type x = _pos;
      _pos++;
      return iterator(x, _hat);
    }

    iterator operator--(int) {
      size_type x = _pos;
      _pos--;
      return iterator(x, _hat);
    }

    iterator& operator++() {_pos++; return *this;}
    iterator& operator--() {_pos--; return *this;}

    reference operator*() const {
      return _hat->_top_array[_pos >> _hat->_power][_pos & _hat->_mask];
    }

		pointer operator->() const {
      // return pointer to class object
			return (&**this);
		}

    iterator& operator=(const iterator& it) {
      _pos = it._pos;
      _hat = it._hat;
      return *this;
    }

    iterator& operator+=(const difference_type i) {
      _pos += i;
      return *this;
    }

    iterator& operator-=(const difference_type i) {
      _pos -= i;
      return *this;
    }

    // These comparison operators assumes that the iterators being compared
    // are iterators into the same container.
    bool operator==(const iterator& it) const {return _pos == it._pos;}
    bool operator<(const iterator& it) const {return _pos < it._pos;}
    bool operator<=(const iterator& it) const {return _pos <= it._pos;}
    bool operator>(const iterator& it) const {return _pos > it._pos;}
    bool operator>=(const iterator& it) const {return _pos >= it._pos;}
    bool operator!=(const iterator& it) const {return _pos != it._pos;}

    // There is no bounds checking on these functions.
    iterator operator+(const difference_type i) const {
      return iterator(_pos + i, _hat);
    }

    friend iterator operator+(difference_type i, const iterator& it);

    iterator operator-(const difference_type i) const {
      return iterator(_pos - i, _hat);
    }

    difference_type operator-(const iterator& it) const {
      return _pos - it._pos;
    }

  private:
    size_type _pos;
    hashed_array_tree<T, A>* _hat;
  };

  template<class T, class A>
  hat_iterator<T, A> operator+(typename A::difference_type i,
                            const hat_iterator<T, A>& it) {
    return hat_iterator<T, A>(it._pos + i, it._hat);
  }

  template <class T, class A>
  class hat_const_iterator {
  private:
    typedef hat_const_iterator<T, A> iterator;

  public:
    typedef std::random_access_iterator_tag iterator_category;
    typedef T value_type;
    typedef typename A::pointer pointer;
    typedef typename A::reference reference;
    typedef typename A::const_reference const_reference;
    typedef typename A::difference_type difference_type;
    typedef typename A::size_type size_type;

    hat_const_iterator() : _pos(0), _hat(0) {}
    hat_const_iterator(const hashed_array_tree<T, A>* hat) : _pos(0), _hat(hat) {}
    hat_const_iterator(size_type pos, const hashed_array_tree<T, A>* hat)
      : _pos(pos), _hat(hat) {}

    iterator operator++(int) {
      size_type x = _pos;
      _pos++;
      return iterator(x, _hat);
    }

    iterator operator--(int) {
      size_type x = _pos;
      _pos--;
      return iterator(x, _hat);
    }

    iterator& operator++() {_pos++; return *this;}
    iterator& operator--() {_pos--; return *this;}

    const_reference operator*() const {
      return _hat->_top_array[_pos >> _hat->_power][_pos & _hat->_mask];
    }

    pointer operator->() const {
      // return pointer to class object
			return (&**this);
		}

    iterator& operator=(const iterator& it) {
      _pos = it._pos;
      _hat = it._hat;
      return *this;
    }

    iterator& operator+=(const difference_type i) {
      _pos += i;
      return *this;
    }

    iterator& operator-=(const difference_type i) {
      _pos -= i;
      return *this;
    }

    // These comparison operators assumes that the iterators being compared
    // are iterators into the same container.
    bool operator==(const iterator& it) const {return _pos == it._pos;}
    bool operator<(const iterator& it) const {return _pos < it._pos;}
    bool operator<=(const iterator& it) const {return _pos <= it._pos;}
    bool operator>(const iterator& it) const {return _pos > it._pos;}
    bool operator>=(const iterator& it) const {return _pos >= it._pos;}
    bool operator!=(const iterator& it) const {return _pos != it._pos;}

    // There is no bounds checking on these functions.
    iterator operator+(const difference_type i) const {
      return iterator(_pos + i, _hat);
    }

    friend iterator operator+(difference_type i, const iterator& it);

    iterator operator-(const difference_type i) const {
      return iterator(_pos - i, _hat);
    }

    difference_type operator-(const iterator& it) const {
      return _pos - it._pos;
    }

  private:
    size_type _pos;
    const hashed_array_tree<T, A> *_hat;
  };
};