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

// Copyright 1997, 1998, 1999, 2000 University of Notre Dame.

// Copyright 2004, 2005 Trustees of Indiana University

// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek,

//          Doug Gregor, D. Kevin McGrath

//

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

#define BOOST_GRAPH_DETAIL_SPARSE_ORDERING_HPP

#include <boost/config.hpp>

#include <vector>

#include <queue>

#include <boost/pending/queue.hpp>

#include <boost/pending/mutable_queue.hpp>

#include <boost/graph/graph_traits.hpp>

#include <boost/graph/breadth_first_search.hpp>

#include <boost/graph/properties.hpp>

#include <boost/pending/indirect_cmp.hpp>

#include <boost/property_map.hpp>

#include <boost/bind.hpp>

#include <boost/graph/iteration_macros.hpp>

#include <boost/graph/depth_first_search.hpp>

namespace boost {

  namespace sparse {

    // rcm_queue

    //

    // This is a custom queue type used in the

    // *_ordering algorithms.

    // In addition to the normal queue operations, the

    // rcm_queue provides:

    // 

    //   int eccentricity() const;

    //   value_type spouse() const;

    // 

    // yes, it's a bad name...but it works, so use it

    template < class Vertex, class DegreeMap,

               class Container = std::deque<Vertex> >

    class rcm_queue : public std::queue<Vertex, Container> {

      typedef std::queue<Vertex> base;

    public:

      typedef typename base::value_type value_type;

      typedef typename base::size_type size_type;

      /* SGI queue has not had a contructor queue(const Container&) */

      inline rcm_queue(DegreeMap deg)

        : _size(0), Qsize(1), eccen(-1), degree(deg) { }

      inline void pop() {

        if ( !_size ) 

          Qsize = base::size();

        base::pop();

        if ( _size == Qsize-1 ) {

          _size = 0;

          ++eccen;

        } else 

          ++_size;

      }

      inline value_type& front() {

        value_type& u =  base::front();

        if ( _size == 0 ) 

          w = u;

        else if (get(degree,u) < get(degree,w) )

          w = u;

        return u;

      }

      inline const value_type& front() const {

        const value_type& u =  base::front();

        if ( _size == 0 ) 

          w = u;

        else if (get(degree,u) < get(degree,w) )

          w = u;

        return u;

      }

      inline value_type& top() { return front(); }

      inline const value_type& top() const { return front(); }

      inline size_type size() const { return base::size(); }

      inline size_type eccentricity() const { return eccen; }

      inline value_type spouse() const { return w; }

    protected:

      size_type _size;

      size_type Qsize;

      int eccen;

      mutable value_type w;

      DegreeMap degree;

    };

    template <typename Tp, typename Sequence = std::deque<Tp> >

    class sparse_ordering_queue : public boost::queue<Tp, Sequence>{

    public:      

      typedef typename Sequence::iterator iterator;

      typedef typename Sequence::reverse_iterator reverse_iterator;

      typedef queue<Tp,Sequence> base;

      typedef typename Sequence::size_type size_type;

      inline iterator begin() { return this->c.begin(); }

      inline reverse_iterator rbegin() { return this->c.rbegin(); }

      inline iterator end() { return this->c.end(); }

      inline reverse_iterator rend() { return this->c.rend(); }

      inline Tp &operator[](int n) { return this->c[n]; }

      inline size_type size() {return this->c.size(); }

    protected:

      //nothing

    };

  } // namespace sparse 

  // Compute Pseudo peripheral

  //

  // To compute an approximated peripheral for a given vertex. 

  // Used in <tt>king_ordering</tt> algorithm.

  //

  template <class Graph, class Vertex, class ColorMap, class DegreeMap>

  Vertex 

  pseudo_peripheral_pair(Graph& G, const Vertex& u, int& ecc,

                         ColorMap color, DegreeMap degree)

  {

    typedef typename property_traits<ColorMap>::value_type ColorValue;

    typedef color_traits<ColorValue> Color;

    sparse::rcm_queue<Vertex, DegreeMap> Q(degree);

    typename boost::graph_traits<Graph>::vertex_iterator ui, ui_end;

    for (tie(ui, ui_end) = vertices(G); ui != ui_end; ++ui)

      if (get(color, *ui) != Color::red()) put(color, *ui, Color::white());

    breadth_first_visit(G, u, buffer(Q).color_map(color));

    ecc = Q.eccentricity(); 

    return Q.spouse();

  }

  // Find a good starting node

  //

  // This is to find a good starting node for the

  // king_ordering algorithm. "good" is in the sense

  // of the ordering generated by RCM.

  //

  template <class Graph, class Vertex, class Color, class Degree> 

  Vertex find_starting_node(Graph& G, Vertex r, Color color, Degree degree)

  {

    Vertex x, y;

    int eccen_r, eccen_x;

    x = pseudo_peripheral_pair(G, r, eccen_r, color, degree);

    y = pseudo_peripheral_pair(G, x, eccen_x, color, degree);

    while (eccen_x > eccen_r) {

      r = x;

      eccen_r = eccen_x;

      x = y;

      y = pseudo_peripheral_pair(G, x, eccen_x, color, degree);

    }

    return x;

  }

template <typename Graph>

class out_degree_property_map 

  : public put_get_helper<typename graph_traits<Graph>::degree_size_type,

                          out_degree_property_map<Graph> >                  

{

public:

  typedef typename graph_traits<Graph>::vertex_descriptor key_type;

  typedef typename graph_traits<Graph>::degree_size_type value_type;

  typedef value_type reference;

  typedef readable_property_map_tag category;

  out_degree_property_map(const Graph& g) : m_g(g) { }

  value_type operator[](const key_type& v) const {

    return out_degree(v, m_g);

  }

private:

  const Graph& m_g;

};

template <typename Graph>

inline out_degree_property_map<Graph>

make_out_degree_map(const Graph& g) {

  return out_degree_property_map<Graph>(g);

}

} // namespace boost

#endif // BOOST_GRAPH_KING_HPP