// Copyright (c) 2003-2004  INRIA Sophia-Antipolis (France).
// All rights reserved.
//
// This file is part of CGAL (www.cgal.org); you may redistribute it under
// the terms of the Q Public License version 1.0.
// See the file LICENSE.QPL distributed with CGAL.
//
// Licensees holding a valid commercial license may use this file in
// accordance with the commercial license agreement provided with the software.
//
// This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
// WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
//
// $Source: /CVSROOT/CGAL/Packages/Mesh_2/include/CGAL/Mesher_level.h,v $
// $Revision: 1.10 $ $Date: 2004/11/18 14:22:26 $
// $Name:  $
//
// Author(s)     : Laurent RINEAU

#ifndef CGAL_MESHER_LEVEL_H
#define CGAL_MESHER_LEVEL_H

#include <utility>

namespace CGAL {

struct Null_mesh_visitor {
  const Null_mesh_visitor& previous_level() const { return *this; }

  template <typename E, typename P>
  void before_conflicts(E, P) const {}

  template <typename E, typename P, typename Z>
  void before_insertion(E, P, Z) const {}

  template <typename V>
  void after_insertion(V) const {}

  template <typename E, typename P, typename Z>
  void after_no_insertion(E, P, Z) const {}
};

struct Null_mesher_level {

  template <typename Visitor>
  void refine(Visitor) {}
  
  template <typename P, typename Z>
  std::pair<bool, bool> test_point_conflict_from_superior(P, Z)
  { 
    return std::make_pair(true, true);
  }

  bool is_algorithm_done() const
  {
    return true;
  }

  template <typename Visitor>
  bool try_to_insert_one_point(Visitor) 
  {
    return true;
  }

  template <typename Visitor>
  bool one_step(Visitor)
  {
    return true;
  }

}; // end Null_mesher_level

template <
  class Triangulation_traits, /**< Traits class that defines operations
                                    from the trianguilation. */
  class Derived, /**< Derived class, that implements methods */
  class Element, /**< Type of elements that this level refines. */
  class Previous = Null_mesher_level /**< Previous level type, 
                                        defaults to \c Null_level
                                               */
  > 
class Mesher_level
{
public:
  /** Type of triangulation that is meshed. */
  typedef typename Triangulation_traits::Triangulation Triangulation;
  /** Type of point that are inserted into the triangulation. */
  typedef typename Triangulation_traits::Point Point;
  /** Type of vertex handles that are returns by insertions into the
      triangulation. */
  typedef typename Triangulation_traits::Vertex_handle Vertex_handle;
  /** Type of the conflict zone for a point that can be inserted. */
  typedef typename Triangulation_traits::Zone Zone;

  typedef Element Element_type;
  typedef Previous Previous_level;

private:
  /** \name Private member functions */
  
  /** Curiously recurring template pattern. */
  //@{
  Derived& derived()
  {
    return static_cast<Derived&>(*this);
  }

  const Derived& derived() const
  {
    return static_cast<const Derived&>(*this);
  }
  //@}

  /** \name Private member datas */

  Previous& previous_level; /**< The previous level of the refinement
                                    process. */
public:
  typedef Mesher_level<Triangulation_traits,
                       Derived,
                       Element,
                       Previous_level> Self;

  /** \name CONSTRUCTORS */
  Mesher_level(Previous_level& previous)
    : previous_level(previous)
  {
  }

  /** \name FUNCTIONS IMPLEMENTED IN THE CLASS \c Derived */

  /**  Access to the triangulation */
  //@{
  Triangulation& triangulation()
  {
    return derived().get_triangulation_ref();
  }

  const Triangulation& triangulation() const
  {
    return derived().get_triangulation_ref();
  }
  //@}

  /** Access to the triangulation traits */
  //@{
  Triangulation_traits& triangulation_traits()
  {
    return derived().get_triangulation_traits();
  }

  const Triangulation_traits& triangulation_traits() const
  {
    return derived().get_triangulation_traits();
  }
  //@}

  /** Called before the first refinement, to initialized the queue of
      elements that should be refined. */
  void scan_triangulation()
  {
    derived().do_scan_triangulation();
  }

  /** Tells if, as regards the elements of type \c Element, the refinement is
      done. */
  bool no_longer_element_to_refine()
  {
    return derived().is_no_longer_element_to_refine();
  }

  /** Retrieves the next element that could be refined. */
  Element get_next_element()
  {
    return derived().do_get_next_element();
  }

  /** Remove from the list the next element that could be refined. */
  void pop_next_element()
  {
    derived().do_pop_next_element();
  }

  /** Gives the point that should be inserted to refine the element \c e */
  Point refinement_point(const Element& e)
  {
    return derived().get_refinement_point(e);
  }

  /** Actions before testing conflicts for point \c p and element \c e */
  template <typename Mesh_visitor>
  void before_conflicts(const Element& e, const Point& p,
			Mesh_visitor& visitor)
  {
    visitor.before_conflicts(e, p);
    derived().do_before_conflicts(e, p);
  }

  /** Tells if, as regards this level of the refinement process, if the
      point conflicts with something, and do what is needed. The return
      type is made of two booleans:
        - the first one tells if the point can be inserted,
        - in case of, the first one is \c false, the second one tells if
        the tested element should be reconsidered latter.
  */
  std::pair<bool, bool> private_test_point_conflict(const Point& p,
                                                    Zone& zone)
  {
    return derived().do_private_test_point_conflict(p, zone);
  }

  /** Tells if, as regards this level of the refinement process, if the
      point conflicts with something, and do what is needed. The return
      type is made of two booleans:
        - the first one tells if the point can be inserted,
        - in case of, the first one is \c false, the second one tells if
        the tested element should be reconsidered latter.
      This function is called by the superior level, if any.
  */
  std::pair<bool, bool> test_point_conflict_from_superior(const Point& p,
                                                          Zone& zone)
  {
    return derived().do_test_point_conflict_from_superior(p, zone);
  }

  /** 
   * Actions before inserting the point \c p in order to refine the
   * element \c e. The zone of conflicts is \c zone.
   */  
  template <class Mesh_visitor>
  void before_insertion(Element& e, const Point& p, Zone& zone, 
                        Mesh_visitor& visitor)
  {
    visitor.before_insertion(e, p, zone);
    derived().do_before_insertion(e, p, zone);
  }

  /** Actions after having inserted the point.
   *  \param vh is the vertex handle of the inserted point,
   *  \param visitor is the visitor.
   */
  template <class Mesh_visitor>
  void after_insertion(Vertex_handle vh, Mesh_visitor& visitor)
  {
    derived().do_after_insertion(vh);
    visitor.after_insertion(vh);
  }

  /** Actions after testing conflicts for point \c p and element \c e 
   *  if no point is inserted. */
  template <class Mesh_visitor>
  void after_no_insertion(const Element& e, const Point& p, Zone& zone,
			  Mesh_visitor& visitor)
  {
    derived().do_after_no_insertion(e, p, zone);
    visitor.after_no_insertion(e, p, zone);
  }

  /** DEFAULT IMPLEMENTATION FUNCTIONS 
   *
   * This bunch of functions should be implemented in the derived class:
   *
   * Tr& get_triangulation_ref();
   * const Tr& get_triangulation_ref();
   *
   * void do_scan_triangulation();
   *
   * bool is_no_longer_element_to_refine();
   *
   * Element do_get_next_element();
   * 
   * void pop_next_element();
   *
   * Point get_refinement_point(Element);
   *
   * 
   * The next ones have default implementations that do nothing:
   *
   */
//   void do_before_conflicts(const Element&, const Point&)
//   {
//   }
  
//   void do_after_no_insertion(Element, Point, Zone)
//   {
//   }
  
//   std::pair<bool, bool> 
//   do_private_test_point_conflict(Point, Zone)
//   {
//     return std::make_pair(true, true);
//   }

//   std::pair<bool, bool>
//   do_test_point_conflict_from_superior(Point, Zone)
//   {
//     return std::make_pair(true, true);
//   }

//   void do_before_insertion(Element, Point, Zone)
//   {
//   }
  
//   void do_after_insertion(Vertex_handle)
//   {
//   }

  /** \name MESHING PROCESS 
   *
   * The following functions use the functions that are implemented in the
   * derived classes.
   *
   */

  /**
   * Tells it the algorithm is done, regarding elements of type \c Element
   * or elements of previous levels.
   */
  bool is_algorithm_done()
  {
    return ( previous_level.is_algorithm_done() && 
             no_longer_element_to_refine() );
  }

  /** Refines elements of this level and previous levels. */
  template <class Mesh_visitor>
  void refine(Mesh_visitor& visitor)
  {
    while(! is_algorithm_done() )
    {
      previous_level.refine(visitor.previous_level());
      if(! no_longer_element_to_refine() )
        process_one_element(visitor);
    }
  }

  /** 
   * This function takes one element from the queue, and try to refine
   * it. It returns \c true if one point has been inserted.
   * @todo Merge with try_to_refine_element().
   */
  template <class Mesh_visitor>
  bool process_one_element(Mesh_visitor& visitor)
  {
    Element e = get_next_element();

    const std::pair<bool, bool> result = try_to_refine_element(e, visitor);

    if(result.second)
      pop_next_element();
    return result.first;
  }

  template <class Mesh_visitor>
  std::pair<bool, bool>
  try_to_refine_element(Element e, Mesh_visitor& visitor)
  {
    const Point& p = refinement_point(e);

    before_conflicts(e, p, visitor);

    Zone zone =
      triangulation_traits().get_conflicts_zone(triangulation(), p);

    const std::pair<bool, bool> result = test_point_conflict(p, zone);

    if(result.first)
    {
      before_insertion(e, p, zone, visitor);

      Vertex_handle v = triangulation_traits().insert(triangulation(),
							  p, zone);

      after_insertion(v, visitor);

      return std::make_pair(true, true);
    }
    else 
      after_no_insertion(e, p, zone, visitor);
    return result;
  }

  /** Return (can_split_the_element, drop_element). */
  std::pair<bool, bool>
  test_point_conflict(const Point& p, Zone& zone)
  {
    const std::pair<bool, bool> result =
      previous_level.test_point_conflict_from_superior(p, zone);

    if( result.first == false )
      return result;
    return private_test_point_conflict(p, zone);
  }

  /** \name STEP BY STEP FUNCTIONS */

  /**
   * Inserts exactly one point, if possible, and returns \c false if no
   * point has been inserted because the algorithm is done.
   */
  template <class Mesh_visitor>
  bool try_to_insert_one_point(Mesh_visitor& visitor)
  {
    while(! is_algorithm_done() )
    {
      if( previous_level.try_to_insert_one_point(visitor.previous_level()) )
        return true;      
      if(! no_longer_element_to_refine() )
        if( process_one_element(visitor) )
          return true;
    }
    return false;
  }

  /**
   * Applies one step of the algorithm: tries to refine one element of
   * previous level or one element of this level. Return \c false iff 
   * <tt> is_algorithm_done()==true </tt>.
   */
  template <class Mesh_visitor>
  bool one_step(Mesh_visitor& visitor)
  {
    if( ! previous_level.is_algorithm_done() )
      previous_level.one_step(visitor.previous_level());
    else
      if( ! no_longer_element_to_refine() )
        process_one_element(visitor);
    return ! is_algorithm_done();
  }

}; // end Mesher_level

}  // end namespace CGAL

#endif // CGAL_MESHER_LEVEL_H