#ifndef _REFINER_H_
#define _REFINER_H_

#include <CGAL/basic.h>
#include <CGAL/Polyhedron_3.h>
#include <queue>

template <class  Kernel,  class  Polyhedron>
class CEdge
{
public:
  typedef typename Kernel::FT FT;
  typedef typename Polyhedron::Halfedge_handle Halfedge_handle;

private:
  FT m_sqlen;
  Halfedge_handle m_he;

public:
  // life cycle
  CEdge(const Halfedge_handle& he)
  {
    m_sqlen = squared_len(he);
    m_he = he;
  }
  CEdge(const CEdge& edge)
    : m_sqlen(edge.sqlen()),
    m_he(edge.he())
  {
  }
  ~CEdge() {}

public:
  // squared length of an edge
  static FT squared_len(Halfedge_handle he)
  {
    return CGAL::squared_distance(he->vertex()->point(),
      he->opposite()->vertex()->point());
  }

public:
  // accessors
  FT& sqlen() { return m_sqlen; }
  const FT sqlen() const { return m_sqlen; }

  Halfedge_handle he() { return m_he; }
  const Halfedge_handle he() const { return m_he; }
};

// functor for priority queue
template<class Edge>
struct less // read more priority
{
  bool operator()(const Edge& e1,
    const Edge& e2) const
  {
    return e1.sqlen() < e2.sqlen();
  }
};

template <class  Kernel,  class  Polyhedron>
class Refiner
{
  // types
  typedef typename Kernel::FT FT;
  typedef CEdge<Kernel, Polyhedron> Edge;
  typedef typename Polyhedron::Halfedge_handle Halfedge_handle;
  typedef typename Polyhedron::Edge_iterator   Edge_iterator;
  typedef std::priority_queue<Edge,
    std::vector<Edge>,
    ::less<Edge> > PQueue;
  // data
  PQueue m_queue;
  Polyhedron* m_pMesh;
public :
  // life cycle
  Refiner(Polyhedron* pMesh)
  {
    m_pMesh = pMesh;
  }
  ~Refiner() {}

public :

  void fill_queue(const FT& max_sqlen)
  {
    for(Edge_iterator he = m_pMesh->edges_begin();
      he != m_pMesh->edges_end();
      he++)
      if(Edge::squared_len(he) > max_sqlen)
        m_queue.push(Edge(he));
  }

  void fill_queue()
  {
    for(Edge_iterator he = m_pMesh->edges_begin();
      he != m_pMesh->edges_end();
      he++)
      m_queue.push(Edge(he));
  }

  // run
  void run_nb_splits(const unsigned int nb_splits)
  {
    // fill queue
    fill_queue();

    unsigned int nb = 0;
    while(nb < nb_splits)
    {
      // get a copy of the candidate edge
      Edge edge = m_queue.top();
      m_queue.pop();

      Halfedge_handle he = edge.he();
      // update point
      Halfedge_handle hnew = m_pMesh->split_edge(he);
      hnew->vertex()->point() = CGAL::midpoint(he->vertex()->point(),
        he->opposite()->vertex()->point());

      // hit has been split into two edges
      m_queue.push(Edge(hnew));
      m_queue.push(Edge(he));

      // split facet if possible
      if(!hnew->is_border())
      {
        m_pMesh->split_facet(hnew,hnew->next()->next());
        m_queue.push(Edge(hnew->next()));
      }

      // split facet if possible
      if(!hnew->opposite()->is_border())
      {
        m_pMesh->split_facet(hnew->opposite()->next(),
          hnew->opposite()->next()->next()->next());
        m_queue.push(Edge(hnew->opposite()->prev()));
      }

      nb++;
    } // end while
  } // end run



  // run
  unsigned int operator()(const FT& max_sqlen)
  {
    // fill queue
    fill_queue(max_sqlen);

    unsigned int nb_split = 0;
    while(!m_queue.empty())
    {
      // get a copy of the candidate edge
      Edge edge = m_queue.top();
      m_queue.pop();

      Halfedge_handle he = edge.he();
      FT sqlen = Edge::squared_len(he);
      if(sqlen > max_sqlen)
      {
        // update point
        Halfedge_handle hnew = m_pMesh->split_edge(he);
        hnew->vertex()->point() = CGAL::midpoint(he->vertex()->point(),
          he->opposite()->vertex()->point());

        // hit has been split into two edges
        m_queue.push(Edge(hnew));
        m_queue.push(Edge(he));

        // split facet if possible
        if(!hnew->is_border())
        {
          m_pMesh->split_facet(hnew,hnew->next()->next());
          m_queue.push(Edge(hnew->next()));
        }

        // split facet if possible
        if(!hnew->opposite()->is_border())
        {
          m_pMesh->split_facet(hnew->opposite()->next(),
            hnew->opposite()->next()->next()->next());
          m_queue.push(Edge(hnew->opposite()->prev()));
        }

        nb_split++;
      } // end if(sqlen > max_sqlen)
    } // end while(!m_queue.empty())
    return nb_split;
  } // end run
};

#endif // _REFINER_H_