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

// Copyright (c) Aaron Windsor 2007

//

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

#define __PLANAR_CANONICAL_ORDERING_HPP__



#include <vector>

#include <list>

#include <boost/config.hpp>

#include <boost/utility.hpp>  //for next and prior

#include <boost/graph/graph_traits.hpp>

#include <boost/property_map.hpp>





namespace boost

{





  template<typename Graph, 

           typename PlanarEmbedding, 

           typename OutputIterator, 

           typename VertexIndexMap>

  void planar_canonical_ordering(const Graph& g, 

                                 PlanarEmbedding embedding, 

                                 OutputIterator ordering, 

                                 VertexIndexMap vm)

  {

    

    typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;

    typedef typename graph_traits<Graph>::edge_descriptor edge_t;

    typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator_t;

    typedef typename graph_traits<Graph>::adjacency_iterator

      adjacency_iterator_t;

    typedef typename std::pair<vertex_t, vertex_t> vertex_pair_t;

    typedef typename property_traits<PlanarEmbedding>::value_type 

      embedding_value_t;

    typedef typename embedding_value_t::const_iterator embedding_iterator_t;

    typedef iterator_property_map

      <typename std::vector<vertex_t>::iterator, VertexIndexMap> 

      vertex_to_vertex_map_t;

    typedef iterator_property_map

      <typename std::vector<std::size_t>::iterator, VertexIndexMap> 

      vertex_to_size_t_map_t;

    

    enum {PROCESSED, 

          UNPROCESSED, 

          ONE_NEIGHBOR_PROCESSED, 

          READY_TO_BE_PROCESSED};

    

    std::vector<vertex_t> processed_neighbor_vector(num_vertices(g));

    vertex_to_vertex_map_t processed_neighbor

      (processed_neighbor_vector.begin(), vm);



    std::vector<std::size_t> status_vector(num_vertices(g), UNPROCESSED);

    vertex_to_size_t_map_t status(status_vector.begin(), vm);



    std::list<vertex_t> ready_to_be_processed;

    

    vertex_t first_vertex = *vertices(g).first;

    vertex_t second_vertex;

    adjacency_iterator_t ai, ai_end;

    for(tie(ai,ai_end) = adjacent_vertices(first_vertex,g); ai != ai_end; ++ai)

      {

        if (*ai == first_vertex)

          continue;

        second_vertex = *ai;

        break;

      }



    ready_to_be_processed.push_back(first_vertex);

    status[first_vertex] = READY_TO_BE_PROCESSED;

    ready_to_be_processed.push_back(second_vertex);

    status[second_vertex] = READY_TO_BE_PROCESSED;



    while(!ready_to_be_processed.empty())

      {

        vertex_t u = ready_to_be_processed.front();

        ready_to_be_processed.pop_front();



        if (status[u] != READY_TO_BE_PROCESSED && u != second_vertex)

          continue;



        embedding_iterator_t ei, ei_start, ei_end;

        embedding_iterator_t next_edge_itr, prior_edge_itr;



        ei_start = embedding[u].begin();

        ei_end = embedding[u].end();

        prior_edge_itr = prior(ei_end);

        while(source(*prior_edge_itr, g) == target(*prior_edge_itr,g))

          prior_edge_itr = prior(prior_edge_itr);



        for(ei = ei_start; ei != ei_end; ++ei)

          {

            

            edge_t e(*ei); // e = (u,v)

            next_edge_itr = next(ei) == ei_end ? ei_start : next(ei);

            vertex_t v = source(e,g) == u ? target(e,g) : source(e,g);



            vertex_t prior_vertex = source(*prior_edge_itr, g) == u ? 

              target(*prior_edge_itr, g) : source(*prior_edge_itr, g);

            vertex_t next_vertex = source(*next_edge_itr, g) == u ? 

              target(*next_edge_itr, g) : source(*next_edge_itr, g);



            // Need prior_vertex, u, v, and next_vertex to all be

            // distinct. This is possible, since the input graph is

            // triangulated. It'll be true all the time in a simple

            // graph, but loops and parallel edges cause some complications.

            if (prior_vertex == v || prior_vertex == u)

              {

                prior_edge_itr = ei;

                continue;

              }



            //Skip any self-loops

            if (u == v)

                continue;

                                                                

            // Move next_edge_itr (and next_vertex) forwards

            // past any loops or parallel edges

            while (next_vertex == v || next_vertex == u)

              {

                next_edge_itr = next(next_edge_itr) == ei_end ?

                  ei_start : next(next_edge_itr);

                next_vertex = source(*next_edge_itr, g) == u ? 

                  target(*next_edge_itr, g) : source(*next_edge_itr, g);

              }





            if (status[v] == UNPROCESSED)

              {

                status[v] = ONE_NEIGHBOR_PROCESSED;

                processed_neighbor[v] = u;

              }

            else if (status[v] == ONE_NEIGHBOR_PROCESSED)

              {

                vertex_t x = processed_neighbor[v];

                //are edges (v,u) and (v,x) adjacent in the planar

                //embedding? if so, set status[v] = 1. otherwise, set

                //status[v] = 2.



                if ((next_vertex == x &&

                     !(first_vertex == u && second_vertex == x)

                     )

                    ||

                    (prior_vertex == x &&

                     !(first_vertex == x && second_vertex == u)

                     )

                    )

                  {

                    status[v] = READY_TO_BE_PROCESSED;

                  }

                else

                  {

                    status[v] = READY_TO_BE_PROCESSED + 1;

                  }                                                        

              }

            else if (status[v] > ONE_NEIGHBOR_PROCESSED)

              {

                //check the two edges before and after (v,u) in the planar

                //embedding, and update status[v] accordingly



                bool processed_before = false;

                if (status[prior_vertex] == PROCESSED)

                  processed_before = true;



                bool processed_after = false;

                if (status[next_vertex] == PROCESSED)

                  processed_after = true;



                if (!processed_before && !processed_after)

                    ++status[v];



                else if (processed_before && processed_after)

                    --status[v];



              }



            if (status[v] == READY_TO_BE_PROCESSED)

              ready_to_be_processed.push_back(v);



            prior_edge_itr = ei;



          }



        status[u] = PROCESSED;

        *ordering = u;

        ++ordering;

        

      }

    

  }





  template<typename Graph, typename PlanarEmbedding, typename OutputIterator>

  void planar_canonical_ordering(const Graph& g, 

                                 PlanarEmbedding embedding, 

                                 OutputIterator ordering

                                 )

  {

    planar_canonical_ordering(g, embedding, ordering, get(vertex_index,g));

  }

 



} //namespace boost



#endif //__PLANAR_CANONICAL_ORDERING_HPP__

