// Copyright (c) 2000  Tel-Aviv University (Israel).
// 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/Arrangement/include/CGAL/Pm_with_intersections.h,v $
// $Revision: 1.58 $ $Date: 2004/11/22 12:15:46 $
// $Name:  $
//
// Author(s)     : Eyal flato <flato@math.tau.ac.il>

#ifndef CGAL_PLANAR_MAP_WITH_INTERSECTIONS_H
#define CGAL_PLANAR_MAP_WITH_INTERSECTIONS_H

#include <CGAL/Planar_map_2.h>
#include <CGAL/Pm_with_intersections_misc.h>
#ifndef CGAL_NO_PM_DEFAULT_POINT_LOCATION
#include <CGAL/Pm_walk_along_line_point_location.h>
#endif
#include <CGAL/Planar_map_2/Pm_change_notification.h>

#include <CGAL/Sweep_line_2/Pmwx_aggregate_insert.h>
#include <CGAL/Sweep_line_2/Pmwx_aggregate_insert_old.h>

#ifndef CGAL_PM_COUNT_OPERATIONS_TIMES
#define CGAL_PM_START_OP(x) 
#define CGAL_PM_END_OP(x)  
#define CGAL_DEFINE_COUNT_OP_TIMES_OBJECT
#endif

#if defined(CGAL_PM_WITH_INTERSECTIONS_PRINT_DEBUG)
#define CGAL_PM_WITH_INTERSECTIONS_PRINT_DEBUG_MSG(msg) std::cout << msg;
#define CGAL_PM_WITH_INTERSECTIONS_PRINT_DEBUG_CODE(code) code
#else
#define CGAL_PM_WITH_INTERSECTIONS_PRINT_DEBUG_MSG(msg)
#define CGAL_PM_WITH_INTERSECTIONS_PRINT_DEBUG_CODE(code)
#endif

CGAL_BEGIN_NAMESPACE

template<class Planar_map_>
class Planar_map_with_intersections_2 : public Planar_map_
{
public:
  typedef Planar_map_                                       Planar_map;
  typedef Planar_map_with_intersections_2<Planar_map>       Self;
  typedef typename Planar_map::Traits                       Traits;
  typedef typename Planar_map::Traits_wrap                  Pm_traits_wrap;
  typedef Planar_map_with_intersections_traits_wrap<Traits> Pmwx_traits_wrap;
  typedef typename Planar_map::Halfedge_handle              Halfedge_handle;
  typedef typename Planar_map::Vertex_handle                Vertex_handle;
  typedef typename Planar_map::Face_handle                  Face_handle;
  typedef typename Traits::X_monotone_curve_2               X_monotone_curve_2;
  typedef typename Traits::Curve_2                          Curve_2;
  typedef typename Traits::Point_2                          Point_2;

  typedef typename Planar_map::Change_notification
    Change_notification;

  typedef typename Planar_map::Halfedge_iterator            Halfedge_iterator;
    
  // Obsolete, for backward compatability
  typedef Point_2                               Point;
  typedef X_monotone_curve_2                    X_curve;
  typedef Curve_2                               Curve;
  typedef Change_notification                   Pmwx_change_notification;

#ifndef CGAL_CFG_USING_BASE_MEMBER_BUG_3
  using Planar_map::traits;
  using Planar_map::halfedges_end;
  using Planar_map::halfedges_begin;
  using Planar_map::unbounded_face;
  using Planar_map::pl;
#endif

  CGAL_DEFINE_COUNT_OP_TIMES_OBJECT

  // Constructors
  // ------------

  Planar_map_with_intersections_2() :
#ifndef CGAL_NO_PM_DEFAULT_POINT_LOCATION
    Planar_map(new Pmwx_traits_wrap,
               new Pm_walk_along_line_point_location<Planar_map>, NULL),
#else
    Planar_map(new Pmwx_traits_wrap, NULL, NULL),
#endif
    pmwx_use_delete_traits(true), 
    pmwx_use_delete_pl(true)
  { 
    pmwx_traits = (Pmwx_traits_wrap*)traits;
  }    
        
  Planar_map_with_intersections_2(Pm_point_location_base<Planar_map> *pl_ptr) :
    Planar_map(new Pmwx_traits_wrap, pl_ptr, NULL),
    pmwx_use_delete_traits(true), 
    pmwx_use_delete_pl(false)
  {
    pmwx_traits = (Pmwx_traits_wrap*)traits;
  }

  Planar_map_with_intersections_2(const Traits& tr_, 
                                  Pm_point_location_base<Planar_map> *pl_ptr) :
    Planar_map(new Pmwx_traits_wrap(tr_), pl_ptr, NULL),
    pmwx_use_delete_traits(true), 
    pmwx_use_delete_pl(false)
  {
    pmwx_traits = (Pmwx_traits_wrap*)traits;
  }

  Planar_map_with_intersections_2(Pmwx_traits_wrap *tr_ptr,
                                  Pm_point_location_base<Planar_map> *pl_ptr) :
    Planar_map(tr_ptr, pl_ptr, NULL),
    pmwx_use_delete_traits(false), 
    pmwx_use_delete_pl(false)
  {
    pmwx_traits = (Pmwx_traits_wrap*)traits;
  }

  /*! Copy Constructor */
  Planar_map_with_intersections_2(const Self & rhs);

  /*! Planar_map converter */
  Planar_map_with_intersections_2(const Planar_map & pm);

  /*! Destructor */
  ~Planar_map_with_intersections_2();
        
  // Operations
  // ----------

  /*! Obtain the supporting curve of the given halfedge
   * \param he the halfedge
   * \param en the notification object
   * \return the supporting curve of he if exists
   */
  const X_monotone_curve_2 & curve(Halfedge_handle he,
                                   Change_notification * en)
  { 
    if (en == NULL)
      return he->curve();
    if (!en->have_support_curve())
      return he->curve();
    return en->edge_support_curve(he); 
  }

  // finds the intersection of <cv> directed <direction_right> with the
  // halfedge <he>. The returned intersections is based on the intersection
  // of the supporting curves (if they exist).
  bool
  directed_nearest_intersection_with_halfedge(const X_monotone_curve_2 & cv,
                                              Halfedge_handle he,
                                              const Point_2 & ref_point,
                                              bool direction_right,
                                              Point_2 & xp1,
                                              Point_2 & xp2,
                                              X_monotone_curve_2 & overlap_cv,
                                              Change_notification * en)
  {
    Object res = (direction_right) ?
      pmwx_traits->nearest_intersection_to_right(cv, curve(he, en), ref_point)
      :
      pmwx_traits->nearest_intersection_to_left(cv, curve(he, en), ref_point);

    if (res.is_empty())
      return (false);
                
    /*
     * check for an intersection on the real curves. assume there is none.
     *
     * since we are checking on the parent, we should make sure that the 
     * intersection point is on the halfedge_cv and not only on the parent.
     * do not worry: we will get the same intersection point for the correct
     * halfedge_cv as well, and therefore we can throw it away if it's 
     * not on halfedge_cv
     * no need to check for cv because the checked side of it is not 
     * in the arrangement yet so there is no possibility for an 
     * intersection point not on cv.
     */

    const X_monotone_curve_2 & he_cv = he->curve();
    
    if (CGAL::assign(xp1, res)) {
      // The intersection is a point:
      xp2 = xp1;        //! \todo is this really needed?
      if (traits->point_in_x_range(he_cv, xp1) &&
 	  traits->curve_compare_y_at_x(xp1, he_cv) == EQUAL) {
        return true;
      }
      return false;
    }

    if (CGAL::assign(overlap_cv, res)) {
      // There is an overlap, the intersection is a subcurve:

      xp1 = pmwx_traits->curve_source(overlap_cv);
      xp2 = pmwx_traits->curve_target(overlap_cv);

      if (!is_left_low(xp1, xp2))
        std::swap(xp1, xp2);

      Point_2 left_point =
        traits->point_leftlow_most(pmwx_traits->curve_source(he_cv),
                                   pmwx_traits->curve_target(he_cv));
      Point_2 right_point =
        traits->point_righttop_most(pmwx_traits->curve_source(he_cv),
                                    pmwx_traits->curve_target(he_cv));
  
      if (is_left_low(xp1, left_point))
        xp1 = left_point;

      if (is_left_low(right_point, xp2))
        xp2 = right_point;

      if (is_left_low(xp1, xp2))
        return (true);

      return (false);
    }

    return (false);
  }


  // input: cv.source is on vh
  // is_overlap is true if cv overlaps prev_halfedge around vh.
  void find_face_of_curve_around_vertex(const X_monotone_curve_2 & cv, 
                                        const X_monotone_curve_2 & orig_cv, 
                                        const Vertex_handle & vh,
                                        Halfedge_handle & prev_halfedge,
                                        Point_2 & overlap_end_pt,
                                        bool & is_overlap,
                                        X_monotone_curve_2 & overlap_cv,
                                        Change_notification * en)
  {
    CGAL_PM_START_OP(1);
     
    typename Planar_map::Halfedge_around_vertex_circulator next, prev, start, 
      last_next_checked;
    X_monotone_curve_2 xcv;
    Point_2 xp1, xp2;
    const Point_2 & source_point = pmwx_traits->curve_source(cv);
    const Point_2 & target_point = pmwx_traits->curve_target(cv);
    bool direction_right = is_left_low(source_point, target_point);
    bool b;
                
    last_next_checked = halfedges_end();        
    start = vh->incident_halfedges();
    prev = start;
    next = prev;
    ++next;
    do {
      if ((last_next_checked != prev) && 
          (traits->curves_overlap(cv, prev->curve())))
      {
        // cv overlapps prev->curve()
        b = directed_nearest_intersection_with_halfedge(orig_cv, prev,
                                                        source_point,
                                                        direction_right,
                                                        xp1, xp2, overlap_cv,
                                                        en);
        // Verify that there is indeed an intersection
        CGAL_assertion(b);
        // Verify that there is indeed an overlap
        CGAL_assertion(!point_equal(xp1, xp2));

        // the overlapping part might not start from the source 
        // vertex (in polyline for example), so if this is the case, 
        // we ignore the overlap. 
        if ((point_equal(xp1, source_point)) ||
            (point_equal(xp2, source_point)))
        {
          if (point_equal(vh->point(), xp1)) {
            overlap_end_pt = xp2;
          }
          else {
            CGAL_assertion(point_equal(vh->point(), xp2));
            overlap_end_pt = xp1;
          }
          
          prev_halfedge = prev;
          is_overlap = true;
          CGAL_PM_END_OP(1);
          return;
        }
      }

      // Same check as above is done now to next->curve() to prevent
      // unexpected behavior of is_between_cw when one of the curves
      // overlaps at vh.
      // last_next_checked is set to next so if the test fails
      // (namely, there is no overlap at vh) then it will not 
      // be executed again at the next loop when prev will be this 
      // next. this is for efficiency only.
      if (traits->curves_overlap(cv, next->curve())) {
        last_next_checked = next;
        // cv overlapps next->curve()
        b = directed_nearest_intersection_with_halfedge(orig_cv, next,
                                                        source_point,
                                                        direction_right,
                                                        xp1, xp2, overlap_cv,
                                                        en);
        // Verify that there is indeed an intersection
        CGAL_assertion(b);
        // Verify that there is indeed an overlap
        CGAL_assertion(!point_equal(xp1, xp2));

        // the overlapping part might not start from the source 
        // vertex (in polyline for example), so if this is the case, 
        // we ignore the overlap. 
        if ((point_equal(xp1, source_point)) ||
            (point_equal(xp2, source_point)))
        {
          if (point_equal(vh->point(), xp1)) {
            overlap_end_pt = xp2;
          }
          else {
            CGAL_assertion(point_equal(vh->point(), xp2));
            overlap_end_pt = xp1;
          }
          
          prev_halfedge = next;
          is_overlap = true;
          CGAL_PM_END_OP(1);
          return;
        }
      }
  
      /////////***** Eyal end
      // The following remarked test is not fully correct
      // since there can be an overlap that does not start at vh
      // but elsewhere on cv (e.g., polylines).
      // this condition is redundant if curve_is_between_cw does
      // not return true when overlap occurs, but it is needed
      // since it is not a defined behaviour (in specs).
      //// if (!traits->curves_overlap(cv, next->curve())) ----
      
      if (next != prev) 
      {
        if ((pmwx_traits->curve_is_between_cw(cv, prev->curve(), next->curve(),
                                              vh->point())))
        {
          prev_halfedge = prev;
          is_overlap = false;
          CGAL_PM_END_OP(1);
          return;
        }
      }
      ++next;
      ++prev;
    } while (prev != start);
                
    // assuming no overlapping occurs, the only situation in 
    // which we reached this line is when there is only one 
    // edge from vh
    CGAL_assertion(next == prev);
    prev_halfedge = prev;
    is_overlap = false;
    CGAL_PM_END_OP(1);
    return;
  }
        
  /*! Find the first intersection in the direction cv.source --> cv.target
   * in <face>.
   * The returned <intersection> is the intersection curve of 
   * <cv> and <face>'s boundary.
   * returned <halfedge> is the halfedge on which the intersection occurs,
   * in case of intersection-point halfedge->source will contain this point
   * \return false if no intersection is found and true otherwise.
   */
  bool find_first_intersection_in_face(const Face_handle & face,
                                       const X_monotone_curve_2 & cv,
                                       const X_monotone_curve_2 & orig_cv, 
                                       Halfedge_handle & halfedge,
                                       Point_2 & best_xpnt1,
                                       Point_2 & best_xpnt2,
                                       Change_notification * en)
  {
    CGAL_PM_START_OP(2);
    Halfedge_handle best_halfedge_x;
    typename Planar_map::Ccb_halfedge_circulator che, che_beg;
    Point_2 xpnt, xp1, xp2;
    bool b, better_xcv;
    bool intersection_exist = false;
    const Point_2 & source_point = pmwx_traits->curve_source(cv);
    const Point_2 & target_point = pmwx_traits->curve_target(cv);
    bool direction_right = is_left_low(source_point, target_point);
    
    Point_2 best_point = pmwx_traits->curve_target(cv);
    
    if (!face->is_unbounded()) {
      che = face->outer_ccb();
      che_beg = che;
      do {
        if (intersection_exist) {
          // optimization: comparing the
          // endpoints of the halfedge and the best intersection 
          // point found so far, Improve performance.
          if (direction_right) {
            if (!is_left(leftmost(che->source()->point(),
                                  che->target()->point()),
                         best_point))
            {
              ++che;
              continue;
            }
          } else {
            if (!is_right(rightmost(che->source()->point(),
                                    che->target()->point()),
                          best_point))
            {
              ++che;
              continue;
            }
          }
        }
          
        // optimization: checking the x-range, Highly improve performance.
        if (!in_x_range(orig_cv,che->curve())) {
          ++che;
          continue;
        }
        
        X_monotone_curve_2 overlap_cv;
        b = directed_nearest_intersection_with_halfedge(orig_cv, che,
                                                        source_point,
                                                        direction_right,
                                                        xp1, xp2, overlap_cv,
                                                        en);
        if (b) {
          // direct xp1-xp2 to be like cv
          if (direction_right) {
            if (!is_left_low(xp1, xp2))
              std::swap(xp1, xp2);
          } else {
            if (!is_right_top(xp1, xp2))
              std::swap(xp1, xp2);
          }
          
          xpnt = xp1;
          if (direction_right)
            better_xcv = is_left_low(xpnt, best_point);
          else
            better_xcv = is_right_top(xpnt, best_point);
          if (better_xcv || (!intersection_exist)) {
            // xcv is better
            best_halfedge_x = che;
            best_point = xpnt;
            best_xpnt1 = xp1;
            best_xpnt2 = xp2;
            intersection_exist = true;
          }
        }
        ++che;
      } while (che != che_beg);
    }

    //if (intersection_exist)
    //  {
    //    halfedge = best_halfedge_x;
    
    //    CGAL_PM_END_OP(2);
    //      return intersection_exist;
    //  }

    typename Planar_map::Holes_iterator holes;
    for (holes = face->holes_begin(); holes != face->holes_end(); holes++) {
      che = *holes;
      che_beg = che;
      do {
        if (intersection_exist) {
           if (direction_right) {
             if (!(is_left_low(leftmost(che->source()->point(),
                                        che->target()->point()),
                               best_point)))
             {
               ++che;
               continue;
             }
           } else {
             if (!(is_right_top(rightmost(che->source()->point(),
                                          che->target()->point()),
                                best_point)))
             {
               ++che;
               continue;
             }
           }
        }
        
        if (!in_x_range(orig_cv,che->curve())) {
          ++che;
          continue;
        }

        X_monotone_curve_2 overlap_cv;
        b = directed_nearest_intersection_with_halfedge(orig_cv, che,
                                                        source_point,
                                                        direction_right,
                                                        xp1, xp2, overlap_cv,
                                                        en);
        if (b) {
          // direct xp1-xp2 to be like cv
          if (direction_right) {
            if (!is_left_low(xp1, xp2))
              std::swap(xp1, xp2);
          } else {
            if (!is_right_top(xp1, xp2))
              std::swap(xp1, xp2);
          }
          
          xpnt = xp1;
          if (direction_right)
            better_xcv = is_left_low(xpnt, best_point);
          else
            better_xcv = is_right_top(xpnt, best_point);
          if (better_xcv || (!intersection_exist)) {
            // xcv is better
            best_halfedge_x = che;
            best_point = xpnt;
            best_xpnt1 = xp1;
            best_xpnt2 = xp2;
            intersection_exist = true;
          }
        }
        ++che;
      } while (che != che_beg);
    }
    
    
    halfedge = best_halfedge_x;
    
    CGAL_PM_END_OP(2);
    return intersection_exist;
  }

  /*!
   */
  void get_vertex_of_point_on_halfedge
  (
    const Point_2 &point,                     
    Halfedge_handle halfedge,
    Vertex_handle &vertex_of_point, 
    // in case of split it is easy to compute:
    Halfedge_handle &vertex_of_point_prev_halfedge,
    // true if vertex_of_point_prev_halfedge is set :
    bool &vertex_of_point_prev_halfedge_set,
    Change_notification *en)
  {
    CGAL_PM_START_OP(3);
    if (point_equal(point, halfedge->source()->point())) {
      vertex_of_point = halfedge->source();
      vertex_of_point_prev_halfedge_set = false;
    } else if (point_equal(point, halfedge->target()->point())) {
      vertex_of_point = halfedge->target();
      vertex_of_point_prev_halfedge_set = false;
    } else {
      // intersection in the interior - split
      X_monotone_curve_2 split1, split2;
      Halfedge_handle he_split;
      if (point_equal(halfedge->source()->point(), 
                      pmwx_traits->curve_source(halfedge->curve())))
      {
        pmwx_traits->directed_curve_split(halfedge->curve(), 
                                          halfedge->source()->point(), 
                                          point, split1, split2);
        he_split = Planar_map::split_edge(halfedge, split1, split2);
        if (en != NULL) 
          en->split_edge(he_split, he_split->next_halfedge(), split1, split2);
                            
        vertex_of_point = he_split->target();
        vertex_of_point_prev_halfedge = he_split->next_halfedge()->twin();
        vertex_of_point_prev_halfedge_set = true;
      } else {
        Halfedge_handle twin_halfedge = halfedge->twin();
        pmwx_traits->directed_curve_split(twin_halfedge->curve(),
                                          twin_halfedge->source()->point(), 
                                          point, split1, split2);
        he_split = Planar_map::split_edge(twin_halfedge, split1, split2);
        if (en != NULL)
          en->split_edge(he_split, he_split->next_halfedge(), split1, split2);
                            
        // change he_split to be on the current face becase we spliited 
        // the twin_halfedge and not halfedge - this is to be 
        // consistent with 
        // the arrangement code that is based on the fact the the 
        // splitted halfedge
        // is the one that is directed like the curve
        he_split = he_split->next_halfedge()->twin();
        vertex_of_point = he_split->target();
        vertex_of_point_prev_halfedge = he_split->next_halfedge()->twin();
        vertex_of_point_prev_halfedge_set = true;
      }
    }
                
    // in order to enable polyline overlap
    // (a little ugly solution. should be made nicer) : 
    vertex_of_point_prev_halfedge_set = false; 
    CGAL_PM_END_OP(3);
  }

 
  /*! Insert the first part of cv into the face source_face 
   * returning: 
   *   1. inserted edge
   *   2. remaining curve (the part that was not inserted)
   *   3. remaining curve source vertex
   */
  void insert_intersecting_xcurve_in_face_interior
  (const X_monotone_curve_2 & cv,                     // inserted curve
   const X_monotone_curve_2 & orig_cv, 
   Face_handle source_face,
   Halfedge_handle & inserted_halfedge,
   bool & remaining_curve_trivial,
   X_monotone_curve_2 & remaining_curve,
   Vertex_handle & remaining_curve_source_vertex, 
   // in case of split it is easy to compute :
   Halfedge_handle & remaining_curve_prev_halfedge,
   // true if remaining_curve_face is set :
   bool &remaining_curve_prev_halfedge_set,  
   Change_notification * en)
  {
    CGAL_PM_START_OP(4);
    remaining_curve_trivial = false;
    //std::cout << "iisifi " 
    // << "insert_intersecting_xcurve_in_face_interior: " << cv << std::endl;
    Halfedge_handle intersection_he;
    Point_2 xpnt1, xpnt2;
                
    if (find_first_intersection_in_face(source_face, cv, orig_cv,
                                        intersection_he, xpnt1, xpnt2, en))
    {
      Point_2 insert_point;
      X_monotone_curve_2 cv_first_part;
      bool direction_right = is_left_low(pmwx_traits->curve_source(cv),
                                         pmwx_traits->curve_target(cv));

      insert_point = (direction_right) ?
        pmwx_traits->point_leftlow_most(xpnt1, xpnt2) :
        pmwx_traits->point_righttop_most(xpnt1, xpnt2);
                        
      CGAL_assertion(!point_equal(pmwx_traits->curve_source(cv),
                                  insert_point));

      remaining_curve_trivial = point_equal(pmwx_traits->curve_target(cv),
                                            insert_point);
      if (remaining_curve_trivial)
        cv_first_part = cv;
      else
        pmwx_traits->directed_curve_split(cv, pmwx_traits->curve_source(cv),
                                          insert_point, cv_first_part,
                                          remaining_curve);

                        
      CGAL_PM_WITH_INTERSECTIONS_PRINT_DEBUG_CODE(
        std::cout << "cv " << cv << std::endl;
        std::cout << "xpnt1 " << xpnt1 << std::endl;
        std::cout << "xpnt2 " << xpnt2 << std::endl;
        std::cout << "insert_point " << insert_point << std::endl;
        std::cout << "cv_first_part " << cv_first_part << std::endl;
        std::cout << "remaining_curve " << remaining_curve << std::endl;
        std::cout << "intersection_he->curve() " 
                  << intersection_he->curve() << std::endl;
        );
        
      get_vertex_of_point_on_halfedge(insert_point,
                                      intersection_he,
                                      remaining_curve_source_vertex,
                                      remaining_curve_prev_halfedge,
                                      remaining_curve_prev_halfedge_set, 
                                      en);

      inserted_halfedge =
        Planar_map::insert_from_vertex(cv_first_part, 
                                       remaining_curve_source_vertex);
      if (en != NULL) en->add_edge(cv_first_part, inserted_halfedge,
                                   false, false);
      CGAL_PM_END_OP(4);
      return;
    }

    inserted_halfedge = Planar_map::insert_in_face_interior(cv, source_face);
    if (en != NULL) {
      en->add_edge(cv, inserted_halfedge, true, false);
      en->add_hole(source_face, inserted_halfedge);
    }
    //std::cout << "iisifi inserted_halfedge " 
    // << inserted_halfedge->source()->point() <<
    //  " ----> " << inserted_halfedge->target()->point() << std::endl;

    if (point_equal(inserted_halfedge->source()->point(),
                    pmwx_traits->curve_source(cv)))
      remaining_curve_source_vertex = inserted_halfedge->target();
    else
      remaining_curve_source_vertex = inserted_halfedge->source();
    remaining_curve_trivial = true;
    remaining_curve_prev_halfedge_set = false;
    CGAL_PM_END_OP(4);
  }

  // source_prev_halfedge->face() is the face we are working on
  // source_prev_halfedge->target() is the vertex on whice cv's source is
  // assuming cv does not overlap an edge from source_prev_halfedge->target()
  // insert the first part of cv into face where cv's source is on the 
  // boundary of face
  // returning: 
  //   1. inserted edge
  //   2. remaining curve (the part that was not inserted)
  //   3. remaining curve source vertex 
  void insert_intersecting_xcurve_from_boundary_of_face
  (const X_monotone_curve_2 & cv,                     // inserted curve
   const X_monotone_curve_2 & orig_cv, 
   Halfedge_handle source_prev_halfedge,
   Halfedge_handle & inserted_halfedge,
   bool & remaining_curve_trivial,
   X_monotone_curve_2 & remaining_curve,
   Vertex_handle & remaining_curve_source_vertex, 
   // in case of split it is easy to compute :
   Halfedge_handle & remaining_curve_prev_halfedge, 
   // true if remaining_curve_face is set :
   bool &remaining_curve_prev_halfedge_set,  
   Change_notification * en)
  {
    CGAL_PM_START_OP(5);
    remaining_curve_trivial = false;
    //std::cout << "iifbof " 
    // << "insert_intersecting_xcurve_from_boundary_of_face: " 
    // << cv << std::endl;
    //std::cout << "iifbof " 
    // << "         source_prev_halfedge: " 
    // << source_prev_halfedge->source()->point() <<
    //   " ----> " << source_prev_halfedge->target()->point() << std::endl;
    Halfedge_handle intersection_he;
    Point_2 xpnt1, xpnt2;
    Face_handle orig_face = source_prev_halfedge->face();
                
    if (find_first_intersection_in_face(source_prev_halfedge->face(),
                                        cv, orig_cv, intersection_he,
                                        xpnt1, xpnt2, en))
    {
      Point_2 insert_point;
      X_monotone_curve_2 cv_first_part;

      // keep the source vertex. We can't rely on 
      // source_prev_halfedge->target() because it might be changed if 
      // source_prev_halfedge is intersected by the new curve
      Vertex_handle source_vertex(source_prev_halfedge->target());

      bool direction_right = is_left_low(pmwx_traits->curve_source(cv),
                                         pmwx_traits->curve_target(cv));
      insert_point = (direction_right) ?
        pmwx_traits->point_leftlow_most(xpnt1, xpnt2) :
        pmwx_traits->point_righttop_most(xpnt1, xpnt2);

      CGAL_assertion(!point_equal(pmwx_traits->curve_source(cv),
                                  insert_point));

      remaining_curve_trivial = point_equal(pmwx_traits->curve_target(cv),
                                            insert_point);
      if (remaining_curve_trivial)
        cv_first_part = cv;
      else
        pmwx_traits->directed_curve_split(cv, pmwx_traits->curve_source(cv),
                                          insert_point, cv_first_part,
                                          remaining_curve);
                        
      get_vertex_of_point_on_halfedge(insert_point, intersection_he,
                                      remaining_curve_source_vertex,
                                      remaining_curve_prev_halfedge,
                                      remaining_curve_prev_halfedge_set, en);
                        
      //std::cout << "iifbob " << "insert_at_vertices: " << 
      //  cv_first_part << 
      //  "   vx1: "<< source_prev_halfedge->target()->point() <<
      //  "   prev_src: "<< source_prev_halfedge->source()->point() <<
      //  "   vx2: "<< remaining_curve_source_vertex->point() << std::endl;
      CGAL_PM_WITH_INTERSECTIONS_PRINT_DEBUG_CODE(
        std::cout << "cv " << cv << std::endl;
        std::cout << "xpnt1 " << xpnt1 << std::endl;
        std::cout << "xpnt2 " << xpnt2 << std::endl;
        std::cout << "insert_point " << insert_point << std::endl;
        std::cout << "cv_first_part " << cv_first_part << std::endl;
        std::cout << "remaining_curve " << remaining_curve << std::endl;
        std::cout << "intersection_he->curve() " 
                  << intersection_he->curve() << std::endl;
        );
      
      inserted_halfedge = 
        Planar_map::insert_at_vertices(cv_first_part, source_vertex, 
                                       remaining_curve_source_vertex);
      if (en != NULL) 
      {
        en->add_edge(cv_first_part, inserted_halfedge, true, false);
        if (inserted_halfedge->face() == orig_face)
          en->split_face(inserted_halfedge->face(), 
                         inserted_halfedge->twin()->face());
        else
          en->split_face(inserted_halfedge->twin()->face(), 
                         inserted_halfedge->face());
      }
      CGAL_PM_END_OP(5);
      return;
    }

    inserted_halfedge = 
      Planar_map::insert_from_vertex(cv, source_prev_halfedge->target()); 
    if (en != NULL) 
      en->add_edge(cv, inserted_halfedge,true, false);
    if (point_equal(inserted_halfedge->source()->point(),
                    pmwx_traits->curve_source(cv)))
      remaining_curve_source_vertex = inserted_halfedge->target();
    else
      remaining_curve_source_vertex = inserted_halfedge->source();
    remaining_curve_trivial = true;
    remaining_curve_prev_halfedge_set = false;
    CGAL_PM_END_OP(5);
  }

  /*!
   */
  Halfedge_handle
  insert_intersecting_xcurve(const X_monotone_curve_2 & cv_, // inserted curve
                             Vertex_handle & source_vertex,
                             // to be set by the function :  
                             Vertex_handle & target_vertex, 
                             bool source_valid,
                             Change_notification * en = NULL)
  {
    CGAL_PM_START_OP(6);
    //if a vertex on which an endpoint of cv_ is known then set cv to 
    //have this endpoint as it's source
    // at the end source_vertex and target_vertex will contain the
    // end-vertices of cv
    Vertex_handle curr_vertex = source_vertex;
    X_monotone_curve_2 cv = cv_; 
    X_monotone_curve_2 orig_cv = cv;
    X_monotone_curve_2 split1, split2;
    Point_2 overlap_end_pt;
    Halfedge_handle inserted_he, prev_halfedge, last_edge;
    bool is_overlap;
    bool next_face_valid = false;
    bool remaining_curve_trivial = false; 

    const Point_2 & source_point = pmwx_traits->curve_source(cv);
    
    if (!source_valid) {
      /* If the source is invalid, we need to locate the source if exists,
       * or create it by splitting an existing halfedge or insertion of the
       * new curve
       */
      CGAL_PM_WITH_INTERSECTIONS_PRINT_DEBUG_MSG("!");

      typename Planar_map::Locate_type lt;
      Halfedge_handle he;
      //-- locate pmwx_traits->curve_source(cv)
      CGAL_PM_START_OP(7);
      he = locate(source_point, lt);
      CGAL_PM_END_OP(7);
                        
      if (lt == Planar_map::VERTEX) {
        // The source point exists! We simply set the source appropriately
        source_vertex = he->target();
        curr_vertex = source_vertex;
      } else if (lt == Planar_map::EDGE) {
        /* The source point does not exist, but it lies on an existng
         * halfedge. In this case we split the halfedge and set the source
         * vertex appropriately
         */
        Halfedge_handle he_split;
        X_monotone_curve_2 split1, split2;
        if (point_equal(he->source()->point(),
                        pmwx_traits->curve_source(he->curve())))
        {
          pmwx_traits->directed_curve_split(he->curve(),
                                            he->source()->point(),
                                            source_point, split1, split2);
          he_split = Planar_map::split_edge(he, split1, split2);
        } else {
          Halfedge_handle twin_he = he->twin();
          pmwx_traits->directed_curve_split(twin_he->curve(),
                                            twin_he->source()->point(),
                                            source_point, split1, split2);
          he_split = Planar_map::split_edge(twin_he, split1, split2);
        }
        if (en != NULL) 
          en->split_edge(he_split, he_split->next_halfedge(), split1, split2);
        source_vertex = he_split->target();
        curr_vertex = source_vertex;
      } else {
        // The source point lies inside the unbounded or a general face.
        Face_handle face = (lt == Planar_map::UNBOUNDED_FACE) ?
          unbounded_face() : he->face();
        // insert_intersecting_xcurve_in_face_interior(curr_vertex)
        X_monotone_curve_2 remaining_curve; 
        insert_intersecting_xcurve_in_face_interior(cv, orig_cv, face,
                                                    inserted_he,
                                                    remaining_curve_trivial,
                                                    remaining_curve,    
                                                    curr_vertex,
                                                    prev_halfedge,
                                                    next_face_valid, en);
        if (!remaining_curve_trivial)
          cv = remaining_curve;
        last_edge = inserted_he;
        target_vertex = curr_vertex; // temporary - can be changed later
        source_vertex = (inserted_he->source() == curr_vertex) ?
          inserted_he->target() : inserted_he->source();
        //inserted_edges.push_back(inserted_he);
      }
                        
      // by now: curr_vertex and source_vertex are set
    }
                
    while (!remaining_curve_trivial) {
      CGAL_PM_WITH_INTERSECTIONS_PRINT_DEBUG_MSG("@");

      Halfedge_handle he_split;
      X_monotone_curve_2 split1, split2;

      if (!next_face_valid) { 
        CGAL_PM_WITH_INTERSECTIONS_PRINT_DEBUG_MSG("#");

        //-- locate cv around curr_vertex
        //std::cout << "iis " << " ---- curr_vertex: " 
        //<< curr_vertex->point() << std::endl;
        X_monotone_curve_2 overlap_cv;
        find_face_of_curve_around_vertex(cv, orig_cv, curr_vertex,
                                         prev_halfedge, overlap_end_pt,
                                         is_overlap, overlap_cv, en);
        //std::cout << "iis " << " ---- prev_halfedge: " 
        //<< prev_halfedge->source()->point() <<
        //   "  ---->  " << prev_halfedge->target()->point() << std::endl;
        if (is_overlap) {
          // if overlaps an edge from curr_vertex 
          CGAL_PM_WITH_INTERSECTIONS_PRINT_DEBUG_MSG("$");

          // rem: prev_halfedge->target == curr_vertex
          if (point_equal(prev_halfedge->source()->point(), overlap_end_pt)) {
            // whole edge is overlapped, proceed to its other end
            CGAL_PM_WITH_INTERSECTIONS_PRINT_DEBUG_MSG("%");

            if (en != NULL) 
              en->add_edge(overlap_cv, prev_halfedge, false, true);
            last_edge = prev_halfedge;
            // update cv
                        
            CGAL_assertion(point_equal(pmwx_traits->curve_source(cv),
                                       curr_vertex->point()));
            remaining_curve_trivial =
              point_equal(pmwx_traits->curve_target(cv),
                          prev_halfedge->source()->point());
            if (!remaining_curve_trivial) {
              pmwx_traits->directed_curve_split(cv, curr_vertex->point(), 
                 prev_halfedge->source()->point(), split1, split2);
              cv = split2;
            }
            curr_vertex = prev_halfedge->source();
          } else { 
            // otherwise - split prev_halfedge and let curr_vertex 
            //be the splitting point
            CGAL_PM_WITH_INTERSECTIONS_PRINT_DEBUG_MSG("^");

            if (point_equal(prev_halfedge->twin()->source()->point(), 
                            pmwx_traits->curve_source(prev_halfedge->twin()
                                                      ->curve())))
            {
              pmwx_traits->directed_curve_split(prev_halfedge->curve(),
                                                curr_vertex->point(), 
                 overlap_end_pt, split1, split2);
                                
              // split prev_halfedge->twin() so that the splitted edge 
              // source will be the same as split1's source
              he_split = 
                Planar_map::split_edge(prev_halfedge->twin(), split1, split2);
              if (en != NULL) {
                en->split_edge(he_split, he_split->next_halfedge(), 
                               split1, split2);
                en->add_edge(overlap_cv, he_split, true, true);
              }
              last_edge = he_split;
                            
              // update cv
              remaining_curve_trivial =
                point_equal(pmwx_traits->curve_target(cv),
                            he_split->target()->point());
              if (!remaining_curve_trivial) {
                pmwx_traits->directed_curve_split(cv,
                                                  pmwx_traits->
                                                  curve_source(cv),
                                                  he_split->target()->point(),
                                                  split1, split2);
                cv = split2;
              }
              curr_vertex = he_split->target();
            } else {
              pmwx_traits->
                directed_curve_split(prev_halfedge->twin()->curve(), 
                                     pmwx_traits->
                                     curve_source(prev_halfedge->twin()->
                                                  curve()), overlap_end_pt,
                                     split1, split2);
                        
              // split prev_halfedge->twin() so that the splitted
              //  edge 
              // source will be the same as split1's source
              he_split = Planar_map::split_edge(prev_halfedge, split1, split2);
              if (en != NULL) {
                en->split_edge(he_split, he_split->next_halfedge(), 
                               split1, split2);
                en->add_edge(overlap_cv, he_split->next_halfedge()->twin(),
                             true, true);
              }
              last_edge = he_split->next_halfedge()->twin();

              // update cv
              remaining_curve_trivial =
                point_equal(pmwx_traits->curve_target(cv),
                            he_split->
                            next_halfedge()->twin()->target()->point());
              if (!remaining_curve_trivial) {
                pmwx_traits->directed_curve_split(cv,
                                                  pmwx_traits->
                                                  curve_source(cv),
                                                  he_split->next_halfedge()->
                                                  twin()->target()->point(),
                                                  split1, split2);
                cv = split2;
              }
              curr_vertex = he_split->next_halfedge()->twin()->target();

            }
          }
                                        
          target_vertex = curr_vertex; // temporary -can be changed later
          next_face_valid = false; 
          continue;
        }
        // if not overlap then in face
        next_face_valid = true;
      }
                        
      // now - we are sure that cv is in the interior of
      // prev_halfedge->face (does not overlaps an halfedge around 
      // curr_vertex)
                        
      CGAL_PM_WITH_INTERSECTIONS_PRINT_DEBUG_MSG("&");

      X_monotone_curve_2 remaining_curve;
      insert_intersecting_xcurve_from_boundary_of_face(cv, orig_cv,
                                                       prev_halfedge,
                                                       inserted_he,
                                                       remaining_curve_trivial,
                                                       remaining_curve,
                                                       curr_vertex,
                                                       prev_halfedge,
                                                       next_face_valid, en);
      if (!remaining_curve_trivial)
        cv = remaining_curve;
      last_edge = inserted_he;

      target_vertex = curr_vertex; // temporary - can be changed later
    }

    if (!point_equal(last_edge->target()->point(),
                     pmwx_traits->curve_target(cv_)))
      last_edge = last_edge->twin();
    CGAL_PM_END_OP(6);
    return last_edge; 
  }

  /*! Insert a given curve into the map. One of its endpoints is conditionally
   * the mapping of a given vertex
   */
  Halfedge_handle insert_intersecting_curve(const Curve_2 & c,
                                            Vertex_handle & source_vertex,
                                            bool source_valid,
                                            Change_notification * en = NULL)
  {
    typedef typename Traits::X_monotone_curve_2         X_monotone_curve_2;
    typedef std::list<X_monotone_curve_2>               X_monotone_curve_list;
    typedef typename X_monotone_curve_list::const_iterator
      X_monotone_curve_iter;
    
    Vertex_handle src = source_vertex;
    Vertex_handle trg;
    Halfedge_handle last_he;
    X_monotone_curve_list x_list;
    traits->curve_make_x_monotone(c, std::back_inserter(x_list));

    X_monotone_curve_iter it = x_list.begin();
    last_he = insert_intersecting_xcurve(*it, src, trg, source_valid, en); 
    src = trg;
    for (it++; it != x_list.end(); it++) {
      last_he = insert_intersecting_xcurve(*it, src, trg, true, en); 
      src = trg;
    }

    return last_he;
  }

  /*! Insert a given curve that one of its endpoints is the mapping of a given
   * vertex into the map.
   * \param cv the curve to insert
   * \param src an existing vertex in the map and one the endpoint of cv
   * \param en the notification
   * \return the last inserted halfedge. Its target maps to the target point of
   * the last inserted X-monotone curve
   */
  Halfedge_handle insert_from_vertex(const Curve_2 & cv, Vertex_handle src, 
                                     Change_notification * en = NULL)
  {
    CGAL_precondition(!point_equal(pmwx_traits->curve_source(cv),
                                   pmwx_traits->curve_target(cv)));
    return insert_intersecting_curve(cv, src,  true, en);
  }

  // return the last inserted halfedge whose target points to the last 
  // point of the inserted xcurve
  Halfedge_handle insert(const Curve_2 & c, Change_notification * en = NULL)
  {
    // If curve is x-monotone then its source is different from its target.
    // (which is not true for non x-monotone curves, e.g, triangles.)

    Vertex_handle src;
    return insert_intersecting_curve(c, src, false, en);
  }


  // inserts a given curve container into the map using Eti's sweep
  template <class X_monotone_curve_2_iterator>
  Halfedge_iterator insert_old(const X_monotone_curve_2_iterator & begin,
			       const X_monotone_curve_2_iterator & end,
			       Change_notification * en = NULL)
  {
    typedef Pmwx_aggregate_insert_old<X_monotone_curve_2_iterator, Traits, 
      Self ,Change_notification> Pmwx_agg_insert;
    Pmwx_agg_insert p(traits);
    p.insert_curves(begin, end, *this, en);

    return halfedges_begin();
  }

  // inserts a given curve container into the map using Tali's sweep
  template <class X_monotone_curve_2_iterator>
  Halfedge_iterator insert(const X_monotone_curve_2_iterator & begin,
			   const X_monotone_curve_2_iterator & end,
			   Change_notification * en = NULL)
  {
    typedef Pmwx_aggregate_insert<X_monotone_curve_2_iterator, Traits, 
      Self ,Change_notification> Pmwx_agg_insert;
    Pmwx_agg_insert p(traits);
    p.insert_curves(begin, end, *this, en);

    return halfedges_begin();
  }

  // Non intersecting insert methods:

  //! inserts a given curve into the map.
  Halfedge_handle non_intersecting_insert(const X_monotone_curve_2 & cv,
                                          Change_notification * en = NULL)
  { return Planar_map::insert(cv, en); }

  //! iterates through a given range of curves, inserting the curves into the
  // map.
  template <class X_monotone_curve_2_iterator> Halfedge_iterator
  non_intersecting_insert(const X_monotone_curve_2_iterator & begin,
                          const X_monotone_curve_2_iterator & end,
                          Change_notification * en = NULL)
  { return Planar_map::insert(begin, end, en); }

  //! inserts a given curve as a new inner component of a given face.
  Halfedge_handle
  non_intersecting_insert_in_face_interior(const X_monotone_curve_2 & cv, 
                                           Face_handle f,
                                           Change_notification * en = NULL)
  { return Planar_map::insert_in_face_interior(cv, f, en); }

  //! inserts a given curve that one of its endpoints is held by the target
  // vertex of a given halfedge into the map.
  Halfedge_handle
  non_intersecting_insert_from_vertex(const X_monotone_curve_2 & cv, 
                                      Halfedge_handle h,
                                      Change_notification * en = NULL) 
  { return Planar_map::insert_from_vertex(cv, h, en); }

  //! inserts a given curve that both of its endpoints are held by the target
  // vertices of two given halfedges respectively into the map.
  Halfedge_handle
  non_intersecting_insert_at_vertices(const X_monotone_curve_2 & cv, 
                                      Halfedge_handle h1, 
                                      Halfedge_handle h2,
                                      Change_notification * en = NULL)
  { return Planar_map::insert_at_vertices(cv, h1, h2, en); } 

  //! inserts a given curve that one of its endpoints is held by a given vertex
  // into the map.
  Halfedge_handle
  non_intersecting_insert_from_vertex(const X_monotone_curve_2 & cv, 
                                      Vertex_handle v1,
                                      Change_notification * en = NULL) 
  { return Planar_map::insert_from_vertex(cv, v1, en); }

  //! inserts a given curve that both of its endpoints are held by two given
  // vertices respectively into the map.
  Halfedge_handle
  non_intersecting_insert_at_vertices(const X_monotone_curve_2 & cv, 
                                      Vertex_handle v1, Vertex_handle v2,
                                      Change_notification * en = NULL)
  { return Planar_map::insert_at_vertices(cv, v1, v2, en); } 
    
protected:
  bool in_x_range(const X_monotone_curve_2 & cv1,
                  const X_monotone_curve_2 & cv2)
  {
    return  (curve_in_x_range(cv1,cv2) || curve_in_x_range(cv2,cv1));   
  }
  
  bool curve_in_x_range(const X_monotone_curve_2 & cv1,
                        const X_monotone_curve_2 & cv2)
  {
    return ((traits->point_in_x_range(cv1, pmwx_traits->curve_source(cv2)) ||
             traits->point_in_x_range(cv1, pmwx_traits->curve_target(cv2))));
  
  }

  // Data fields:
  Pmwx_traits_wrap * pmwx_traits;
  bool pmwx_use_delete_traits;
  bool pmwx_use_delete_pl;

private:
  bool is_left(const Point_2 &p1, const Point_2 &p2) const
  { return (traits->compare_x(p1, p2) == SMALLER); }

  bool is_right(const Point_2 &p1, const Point_2 &p2) const 
  { return (traits->compare_x(p1, p2) == LARGER); }

  bool is_left_low(const Point_2 &p1, const Point_2 &p2) const
  { return (traits->compare_xy(p1, p2) == SMALLER); }

  bool is_right_top(const Point_2 & p1, const Point_2 & p2) const
  { return is_left_low(p2, p1); }
  
  const Point_2& leftmost(const Point_2 &p1, const Point_2 &p2) const
  { return (is_left(p1, p2) ? p1 : p2); }

  const Point_2& rightmost(const Point_2 &p1, const Point_2 &p2) const
  { return (is_right(p1, p2) ? p1 : p2); }

  /*! returns true iff the two points are the same */
  bool point_equal(const Point_2 & p1, const Point_2 & p2) const
  { return traits->point_equal(p1, p2); }
};

/*! Copy Constructor */
template<class Pm>
Planar_map_with_intersections_2<Pm>::
Planar_map_with_intersections_2(const Self & rhs) :
  Planar_map(rhs),
  pmwx_use_delete_traits(false),
  pmwx_use_delete_pl(false)
{
  pmwx_traits = (Pmwx_traits_wrap*)traits;
}

/*! Copy Constructor */
template<class Pm>
Planar_map_with_intersections_2<Pm>::
Planar_map_with_intersections_2(const Planar_map & pm) : 
  Planar_map(pm),
  pmwx_use_delete_traits(false),
  pmwx_use_delete_pl(false)
{
  pmwx_traits = (Pmwx_traits_wrap*)traits;
}

/*! Destructor */
template<class Pm>
Planar_map_with_intersections_2<Pm>::~Planar_map_with_intersections_2()
{
  if (pmwx_use_delete_traits) delete traits;
  if (pmwx_use_delete_pl) delete pl;
}

CGAL_END_NAMESPACE

#endif
