/* -*- C++ -*-

 * lemon/topology.h - Part of LEMON, a generic C++ optimization library

 *

 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

 * (Egervary Research Group on Combinatorial Optimization, EGRES).

 *

 * Permission to use, modify and distribute this software is granted

 * provided that this copyright notice appears in all copies. For

 * precise terms see the accompanying LICENSE file.

 *

 * This software is provided "AS IS" with no warranty of any kind,

 * express or implied, and with no claim as to its suitability for any

 * purpose.

 *

 */

#include<lemon/invalid.h>

#include <list>

/// \ingroup gutils

/// \file

/// \brief Euler tour

///

///This file provides an Euler tour iterator and ways to check

///if a graph is euler.

namespace lemon {

  ///Euler iterator in directed graphs.

  /// \ingroup gutils

  ///This iterator converts to the \c Edge type of the graph and using

  ///the ++ operator it provides an Euler tour of the graph (if there exists).

  ///

  ///For example

  ///if the given graph if Euler (i.e it has only one nontrivial component

  ///and the in-degree is equal to the out-degree for all nodes),

  ///the the following code will print the edge IDs according to an

  ///Euler tour of \c g.

  ///\code

  ///  for(EulerIt<ListGraph> e(g),e!=INVALID;++e) {

  ///    std::cout << g.id(e) << std::eol;

  ///  }

  ///\endcode

  ///If \c g is not Euler then the resulted tour will not be full or closed.

  ///\todo Test required

  template<class Graph>

  class EulerIt 

  {

    typedef typename Graph::Node Node;

    typedef typename Graph::NodeIt NodeIt;

    typedef typename Graph::Edge Edge;

    typedef typename Graph::EdgeIt EdgeIt;

    typedef typename Graph::OutEdgeIt OutEdgeIt;

    typedef typename Graph::InEdgeIt InEdgeIt;

    const Graph &g;

    typename Graph::NodeMap<OutEdgeIt> nedge;

    std::list<Edge> euler;

  public:

    ///Constructor

    ///\param _g A directed graph.

    ///\param start The starting point of the tour. If it is not given

    ///       tho tour will start from the first node.

    EulerIt(const Graph &_g,typename Graph::Node start=INVALID)

      : g(_g), nedge(g)

    {

      if(start==INVALID) start=NodeIt(g);

      for(NodeIt n(g);n!=INVALID;++n) nedge[n]=OutEdgeIt(g,n);

      while(nedge[start]!=INVALID) {

	euler.push_back(nedge[start]);

	Node next=g.target(nedge[start]);

	++nedge[start];

	start=next;

      }

    }

    ///Edge Conversion

    operator Edge() { return euler.empty()?INVALID:euler.front(); }

    bool operator==(Invalid) { return euler.empty(); }

    bool operator!=(Invalid) { return !euler.empty(); }

    ///Next edge of the tour

    EulerIt &operator++() {

      Node s=g.target(euler.front());

      euler.pop_front();

      //This produces a warning.Strange.

      //std::list<Edge>::iterator next=euler.begin();

      typename std::list<Edge>::iterator next=euler.begin();

      while(nedge[s]!=INVALID) {

	euler.insert(next,nedge[s]);

	Node n=g.target(nedge[s]);

	++nedge[s];

	s=n;

      }

      return *this;

    }

    ///Postfix incrementation

    ///\warning This gives back an Edge, not an EulerIt!

    ///\todo Is this what we want?

    Edge operator++(int) 

    {

      Edge e=*this;

      ++(*this);

      return e;

    }

  };

  ///Checks if the graph is Euler

  /// \ingroup gutils

  ///Checks if the graph is Euler. It works for both directed and

  ///undirected graphs.

  ///\todo What to do with the isolated points?

  ///\todo Test required

  template<class Graph>

#ifdef DOXYGEN

  bool

#else

  typename enable_if<typename Graph::UndirTag,bool>::type

#endif

  euler(const Graph &g) 

  {

    for(typename Graph::NodeIt n(g);n!=INVALID;++n)

      if(countIncEdges(g,n)%2) return false;

    return true;

  }

  template<class Graph>

  typename disable_if<typename Graph::UndirTag,bool>::type

  isEuler(const Graph &g) 

  {

    for(typename Graph::NodeIt n(g);n!=INVALID;++n)

      if(countInEdges(g,n)!=countOutEdges(g,n)) return false;

    return true;

  }

}