// (C) Copyright 2008-2009 SDML (www.sdml.info)
//
// Use, modification and distribution is subject to 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 PREFIX_TREE_ITERATOR_HPP
#define PREFIX_TREE_ITERATOR_HPP

#include <algorithm>
#include <iterator>

namespace gpld {

/**
 * This class is used to iterate over prefix_trees, and to remember positions
 * within one.
 *
 * It will eventually be a bidirectional_iterator.
 *
 * @todo At the moment, prefix_tree iterators mainly provide the ability
 *       to remove data. They do not actually iterate.
 */
template <typename Traits>
class prefix_tree_iterator
{
public:
    /** @name Constructors and Destructors */
    //@{
    prefix_tree_iterator();
    prefix_tree_iterator(prefix_tree_iterator<Traits> const& other);
    prefix_tree_iterator(prefix_tree_iterator<Traits> && other);
    prefix_tree_iterator(prefix_tree_node<Traits> *first, prefix_tree_node<Traits> *last);
    ~prefix_tree_iterator();
    //@}

    prefix_tree_iterator<Traits>& swap(prefix_tree_iterator<Traits> && other);

    prefix_tree_iterator& operator=(prefix_tree_iterator<Traits> const& other);
    prefix_tree_iterator& operator=(prefix_tree_iterator<Traits> && other);

    bool operator==(prefix_tree_iterator<Traits> const& rhs) const;
    
private:
    /** First node in the key. */
    prefix_tree_node<Traits> *_first;
    
    /** Last node in the key. */
    prefix_tree_node<Traits> *_last;
};

/**
 * Default constructor.
 * @remarks Does not leave the iterator in a usable state.
 */
template <typename Traits>
prefix_tree_iterator<Traits>::prefix_tree_iterator()
    : _first(0), _last(0)
{ }

/** Copy constructor. */
template <typename Traits>
prefix_tree_iterator<Traits>::prefix_tree_iterator(prefix_tree_iterator<Traits> const& other)
    : _first(other._first), _last(other._last)
{ }

/** Move constructor. */
template <typename Traits>
prefix_tree_iterator<Traits>::prefix_tree_iterator(prefix_tree_iterator<Traits> && other)
    : _first(std::move(other._first)), _last(std::move(other._last))
{ }

/** Initialization constructor. */
template <typename Traits>
prefix_tree_iterator<Traits>::prefix_tree_iterator(prefix_tree_node<Traits> *first, prefix_tree_node<Traits> *last)
    : _first(first), _last(last)
{ }

/** Default destructor. */
template <typename Traits>
prefix_tree_iterator<Traits>::~prefix_tree_iterator()
{ }

/** Swap operation. */
template <typename Traits>
prefix_tree_iterator<Traits>&
prefix_tree_iterator<Traits>::swap(prefix_tree_iterator<Traits> && other)
{
    using std::swap;
    swap(_first, other._first);
    swap(_last,  other._last);
    return *this;
}

/** Copy assignment operator. */
template <typename Traits>
prefix_tree_iterator<Traits>&
prefix_tree_iterator<Traits>::operator=(prefix_tree_iterator<Traits> const& other)
{
    _first = other._first;
    _last  = other._last;
    return *this;
}

/** Move assignment operator. */
template <typename Traits>
prefix_tree_iterator<Traits>&
prefix_tree_iterator<Traits>::operator=(prefix_tree_iterator<Traits> && other)
{ return swap(other); }

/** Equality comparison operator. */
template <typename Traits>
bool prefix_tree_iterator<Traits>::operator==(prefix_tree_iterator<Traits> const& rhs) const
{ return (_first == rhs._first) && (_last == rhs._last); }


} // end of gpld namespace

#endif