/* Simple Bidirectional Iterator */
#include <bool.h>

template <class C> class BiIterator {
private:

    friend class C;  // the container type, e.g., List

    typedef C::Node Node;   // the container must define a Node type

    Node* node;

    BiIterator (Node* node);

public:

    typedef C::Type Type;	// If C is List<int>, then T is int

    BiIterator ();

    bool operator == (const BiIterator<C> &other) const;
    bool operator!= (const BiIterator<C> &other) const;

    //	++i advances the iterator so that it refers to the next element in the container
    // and returns the new value of the iterator
    BiIterator<C>& operator ++ ();

    //	i++ advances the iterator so that it refers to the next element in the container
    //	container, and returns the old value of the iterator.
    BiIterator<C> operator ++ (int);

    //	--i modifies the iterator so that it refers to the previous element in
    //	the container, and returns a reference to the new value of the iterator.
    BiIterator<C>& operator -- ();

    //	i-- modifies the iterator so that it refers to the previous element in
    //	the container, and returns the old value of the iterator.
    BiIterator<C> operator -- (int);
    
    //	*i returns a reference to the element that the iterator refers to. The
    //	value of the element within the container may be updated by assignment
    //	to the returned reference.

    Type& operator * () const;
};


/* inline BiIterator template methods */

template<class C> inline 
BiIterator<C>::BiIterator () : node(NULL) {}

template<class C> inline 
BiIterator<C>::BiIterator (Node* n) : node(n) {}

template<class C> inline 
bool BiIterator<C>::operator != (const BiIterator<C> &other) const 
{
    return (node != other.node);
}
    
template<class C> inline 
bool BiIterator<C>::operator == (const BiIterator<C> &other) const 
{
    return (node == other.node);
}

template<class C> inline 
BiIterator<C>& BiIterator<C>::operator ++ () 
{
    node = node->forw();
    return *this;
}

template<class C> inline 
BiIterator<C> BiIterator<C>::operator ++ (int) 
{
    BiIterator<C> tmp = *this;
    node = node->forw();
    return tmp;
}

template<class C> inline 
BiIterator<C>& BiIterator<C>::operator -- () 
{
    node = node->back();
    return *this;
}

template<class C> inline 
BiIterator<C> BiIterator<C>::operator -- (int) 
{
    BiIterator<C> tmp = *this;
    node = node->back();
    return tmp;
}

template<class C> inline 
BiIterator<C>::Type& BiIterator<C>::operator*() const
{ 
  return node->elem(); 
}