// Copyright (c) 1997  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/Planar_map/include/CGAL/Pm_walk_along_line_point_location.C,v $
// $Revision: 1.18 $ $Date: 2004/08/01 16:38:18 $
// $Name:  $
//
// Author(s)     : Oren Nechushtan <theoren@math.tau.ac.il>
//                 Iddo Hanniel <hanniel@math.tau.ac.il>
#ifndef CGAL_PM_WALK_ALONG_LINE_POINT_LOCATION_C
#define CGAL_PM_WALK_ALONG_LINE_POINT_LOCATION_C

#include <CGAL/Pm_walk_along_line_point_location.h>

//#define CGAL_PM_WALK_DEBUG
//#define CGAL_PM_DEBUG

CGAL_BEGIN_NAMESPACE

//if unbounded face - returns NULL or some edge on unbounded face 
//if its a vertex returns a halfedge pointing _at_ it
template <class Planar_map>
typename Pm_walk_along_line_point_location<Planar_map>::Halfedge_const_handle
Pm_walk_along_line_point_location<Planar_map>::locate(const Point & p, 
                                                      Locate_type & lt) const
{
  Face_const_handle f = pm->unbounded_face(), last = pm->faces_end();  
  // invariant: p always lies in f's interior or holes
  
  Halfedge_const_handle e = pm->halfedges_end(); // closest halfedge so far

  lt = Planar_map::UNBOUNDED_FACE;
  while (f != last) { // stop at innermost level
    last = f;
    Holes_const_iterator it = f->holes_begin(), end = f->holes_end();
    while (it != end && last == f) {     // handle holes
      if (find_closest(p, *it, true, true, e, lt))
        switch (lt) {
         case Planar_map::UNBOUNDED_FACE:
          break;
         case Planar_map::FACE:
          walk_along_line(p,true,true,e,lt);
          switch (lt) {
           case Planar_map::VERTEX:
                    
#ifdef CGAL_PM_DEBUG
            CGAL_assertion(traits->point_equal(e->target()->point(), p));
#endif
                    
           case Planar_map::EDGE:
            return e;
           case Planar_map::FACE:
            f=e->face();
            break;
           default:
            CGAL_assertion(lt == Planar_map::FACE ||
                           lt == Planar_map::EDGE ||
                           lt == Planar_map::VERTEX);
            break;
          }
          break;
         case Planar_map::VERTEX:
                
#ifdef CGAL_PM_DEBUG
                
          CGAL_assertion(traits->point_equal(e->target()->point(), p));
                
#endif
                
         case Planar_map::EDGE:
          return e;
         default:
          CGAL_assertion(lt==Planar_map::UNBOUNDED_FACE||
                         lt==Planar_map::FACE||
                         lt==Planar_map::EDGE||
                         lt==Planar_map::VERTEX);
        }
      ++it;
    }
  }
  if (lt == Planar_map::UNBOUNDED_FACE && f != pm->unbounded_face()) 
    lt = Planar_map::FACE;
  if (e == pm->halfedges_end() && pm->number_of_halfedges() > 0) 
    return Halfedge_const_handle(*(pm->unbounded_face()->holes_begin()));
  
  return e;
}

template <class Planar_map>
typename Pm_walk_along_line_point_location<Planar_map>::Halfedge_handle
Pm_walk_along_line_point_location<Planar_map>::locate(const Point & p, 
						      Locate_type & lt)
{
  ((Bounding_box*)get_bounding_box())->insert(p);
  Halfedge_handle h =
    Halfedge_handle_unconst(((const_Self_ptr)this)->locate(p,lt));
  if (!((Bounding_box*)get_bounding_box())->locate(p,lt,h))
    h=Halfedge_handle_unconst(((const_Self_ptr)this)->locate(p,lt));
  return h;
}

template <class Planar_map>
typename Pm_walk_along_line_point_location<Planar_map>::Halfedge_const_handle
Pm_walk_along_line_point_location<Planar_map>::
vertical_ray_shoot(const Point & p, 
                   Locate_type & lt, 
                   bool up) const
{
  Face_const_handle f    = pm->unbounded_face(),
    last = pm->faces_end();  
  // p always lies in f's interior
  Halfedge_const_handle e = pm->halfedges_end(); // closest halfedge so far
  lt = Planar_map::UNBOUNDED_FACE;
  while(f != last) // stop at innermost level
  {
    last = f;
    Holes_const_iterator it  = f->holes_begin(),
      end = f->holes_end();
    // For each hole
    while(it != end && last == f) 
    {
      if (find_closest(p,*it,up,false,e,lt))
      {
        switch (lt)
        {
         case Planar_map::VERTEX:
                  
#ifdef CGAL_PM_DEBUG
          CGAL_assertion(traits->point_equal_x(e->target()->point(), p));
#endif
         case Planar_map::EDGE:
                  
#ifdef CGAL_PM_WALK_DEBUG
          std::cerr << "\ncalling walk_along_line(" << p << "," 
                    << up << ",false," << e->curve() << "," << lt 
                    << ")";
#endif
          walk_along_line(p,up,false,e,lt);
          switch(lt)
          {
           case Planar_map::VERTEX:
            f=e->twin()->face();
            break;
           case Planar_map::EDGE:
                      
#ifdef CGAL_PM_DEBUG
            CGAL_assertion(up ==
                           traits->point_is_left_low(e->target()->point(),
                                                     e->source()->point()));
#endif                      
            f=e->face();
           case Planar_map::UNBOUNDED_FACE:
            break;
           default:
            CGAL_assertion(lt==Planar_map::UNBOUNDED_FACE||
                           lt==Planar_map::EDGE||
                           lt==Planar_map::VERTEX);
            break;
          }
          break;
         default:
          CGAL_assertion(lt == Planar_map::EDGE || lt == Planar_map::VERTEX);
          break;
        }
      }
      ++it;
    }
  }
  if (e==pm->halfedges_end()) 
    lt=Planar_map::UNBOUNDED_FACE;
  
  return e;
}

template <class Planar_map>
typename Pm_walk_along_line_point_location<Planar_map>::Halfedge_handle
Pm_walk_along_line_point_location<Planar_map>::
vertical_ray_shoot(const Point& p, 
                   Locate_type& lt, bool up)
{
  /* Make sure the source point is in the bounding box on the output */
  ((Bounding_box*)get_bounding_box())->insert(p);
  Halfedge_handle h =
    Halfedge_handle_unconst(((const_Self_ptr)this)->vertical_ray_shoot(p,lt,up));
  /* Apply the bounding box on the output */
  if (!((Bounding_box*)get_bounding_box())->vertical_ray_shoot(p,lt,up,h))
  {
    h = Halfedge_handle_unconst(((const_Self_ptr)this)->
                                vertical_ray_shoot(p,lt,up));
    CGAL_assertion(lt!=Planar_map::UNBOUNDED_FACE);
  }
  return h;
}

///IMPLEMENTATION ////////////////////////////////////////

/*
 Point p -  the source of the vertical ray shoot
 bool up -  true if the ray shoot is upwards, otherwise false (downwards)
 bool including - true if the ray includes its source, false otherwise

 The intersection of the vertical ray shoot is represented using:
 Locate_type lt - the type of the intersection
 Halfedge_handle e - an halfedge representing the intersection depending on
{
 lt == point, ( a vertex in the planar map )
      find the first halfedge pointing at p, when going clockwise if 
      highest==true - start from 12 oclock, else start from 6 oclock 
      DEBUG: highest = up or !up ???
 lt == curve, ( an halfedge in the planar map )
      DEBUG: ?
 lt == face, ( a face in the planar map )
      DEBUG: ?
 lt == unbounded face, ( an unbounded face in the planar map)
      DEBUG: ?
}
*/

// This function takes a point p , p is in the face to the side of e.
// We walk along a the vertical line enamating from p (in direction
// up), one each iteration find_closest finds the closest halfedge to
// p (in direction up), the loop stops when find_closest found the
// closest face to p (the condition last_face != face) or we got to
// the unbounded face so there is nothing left to do.



template <class Planar_map>
void Pm_walk_along_line_point_location<Planar_map>::
walk_along_line(const Point & p,
                bool up,
                bool including, 
                // bool type,
                Halfedge_const_handle& e,
                Locate_type& lt) const 
{ 
  bool type = including;
  Face_const_handle face = (type || lt!=Planar_map::VERTEX) ? e->face() : 
    e->twin()->face();    // hold the current face find_closest found.
  Face_const_handle last_face;  // hold the last face find_closest found.

  do {
    last_face = face;
    /*
        
          x
         /
        x
        
        p

        A situation where CGAL_assertion(f!=pm->unbounded_face()) doesn't hold.
    */

#ifdef CGAL_PM_WALK_DEBUG

    std::cerr << "\n pre find_closest(" << p << ", , " << up 
              << "," << including << ",(" << e->source()->point() 
              << "," << e->target()->point()  << ")," << lt << ");";
#endif

    if (face != pm->unbounded_face()) 
    {

#ifdef CGAL_PM_DEBUG

      bool found = 

#endif
        
        find_closest(p, face->outer_ccb(), up, including, e, lt);

#ifdef CGAL_PM_DEBUG
      
      CGAL_assertion(found);
      
#endif
    }
        
    face =
      (type || lt != Planar_map::VERTEX) ? e->face() : e->twin()->face();
  }
  while((type == (lt==Planar_map::UNBOUNDED_FACE)) && last_face != face);
}

/*!
The function gets a face circulator, a point p, direction (up/down), 
and returns the edge that is closest to the point in the given direction. 
An edge is returned in all cases. The info about the location type is returned 
in the Locate_type lt (vertex/edge/face).
 */
template <class Planar_map>
bool Pm_walk_along_line_point_location<Planar_map>::
find_closest(const Point & p,
	     const Ccb_halfedge_const_circulator & c,
	     bool up, bool including, // bool type,
	     Halfedge_const_handle & e,
	     Locate_type & lt) const
{
  // for possible future implementation (if the ray includes its source).
  //including - if the ray includes its source or not. 
  //type == true : was called from locate, 
  //              should return the edge that points to the face p is in.
  //type == false: was called from vertical ray shoot 
  //               should return the edge right above, or if vertex above - 
  //               should return the first edge in ccb order
  bool type = including; 

  // is this the first relevant edge found
  bool intersection = e != pm->halfedges_end(); 
  // used to answer is it known that ray shoot intersects curves?

  // inside flips from false to true according to the number of edges found
  // above p. odd number - p is inside, even - p outside the face.
  // its like a counter to the number of edges above p.
  bool inside = false; // used to calculate if point is inside ccb

  //an iterator on all the halfedges
  Ccb_halfedge_const_circulator curr = c;

  //the main loop
  do {
#ifdef CGAL_PM_WALK_DEBUG
    std::cout << curr->source()->point()<<" towards "
              << curr->target()->point()<<std::endl;
#endif

    // ecv holds the closest curve to p found so far.
    const X_curve & cv = curr->curve();
    const X_curve & ecv = intersection ? e->curve() : cv;   // dummy ref to cv
    const Point & p1 = traits->curve_source(cv),
                & p2 = traits->curve_target(cv);
    bool in_x_range = true;

    if (type) {//we are in locate - lexicographic x range
      in_x_range = ((traits->point_is_left_low(p, p1) !=
		    traits->point_is_left_low(p, p2)) || 
		    (traits->point_equal(p, p1))   || 
		    (traits->point_equal(p, p2)));
    }
    else { //we are in vertical ray shoot
      in_x_range = traits->point_in_x_range(cv, p);
    }

    
    Comparison_result res = EQUAL;

    if (in_x_range)
      res = traits->curve_compare_y_at_x(p, cv);

    //continue only if we're in x range, 
    //and the halfedge is above us (if up) / below (if down)
    if (res == (up ? SMALLER: LARGER)) {
      /* cv is a non vertical curve intersecting the vertical ray shoot 
             x
           / 
         x |     ( for a vertical ray shoot upwards )
           |
           p

         The vertical case is excluded for lexicographically the curve
         is not intersecting with the ray:

         x        |  x
         |        | /
         x   =>   |x 
         |        |
         p        p
      */

      if (traits->point_is_left_low(p, p1) !=
          traits->point_is_left_low(p, p2))
      {
        // p is lexicographically between p1 and p2.
        // count parity of curves intersecting ray in their interior
        inside = !inside;
      }
      //if this curve is better for us than all the others : 
      //or its the first in the right x-range, or its the closest
      if (!intersection ||   
      // if we had an intersection in the previous iteration.
          traits->curves_compare_y_at_x(ecv, cv , p) == 
          (up ? LARGER : SMALLER))
        // we know that curr is above (or below, if up false) p.
      {
        // orient e leftlow
        if ( up == traits->point_is_left_low(curr->target()->point(),
                                             curr->source()->point()))
          e = curr ;
        else
          e = curr->twin();

#ifdef CGAL_PM_WALK_DEBUG
        std::cout<<"e is "<< e->source()->point()<<" towards "
                 << e->target()->point()<<std::endl;
#endif  

        if (!type)  //used for vertical ray shoot
          if (!traits->curve_is_vertical(cv)) {
            if (traits->point_equal_x(e->source()->point(),p)) {
              // p is below (above if not up) e->source().  
              e = e->twin();
              lt=Planar_map::VERTEX;
            } else if (traits->point_equal_x(e->target()->point(),p)) {
              lt = Planar_map::VERTEX;
            } else
              lt = Planar_map::EDGE;
          } else // for p is within e'th x range
            lt=Planar_map::VERTEX;
        // the vertical ray intersects a vertex or an edge.
        intersection = true;   
      } 
      //if there was intersection in the previous run, and the compare-y_at_x 
      //returned equal, that is in one of the cases: 
      else if (e != curr && e != curr->twin() && 
                 traits->curves_compare_y_at_x(ecv, cv , p) == EQUAL)
      {
        /*
         * The common edge point of cv and ecv is on the vertical ray
         * emanating from p. q is assigned with this common edge point.
         * first intersection point of ray and curve is an end point like
         *
         *                  x x
         *  x--x---x        |/ 
         *     |            x
         *     |            |
         *     p       or   p
         *
         */

	//q will hold the intersection point of cv and ecv
        Point q = traits->curve_source(cv);
        if ((traits->compare_x(p, q) != EQUAL) ||
	    //the next 2 lines are written to deal with cases 
	    //that one of the curves is vertical
          (!traits->point_equal(q, traits->curve_source(ecv)) &&
           !traits->point_equal(q, traits->curve_target(ecv))))
          q = traits->curve_target(cv);

	//check which curve (cv or ecv) is closer in the meaning of clockwise
        if ((up ? traits->curves_compare_y_at_x_from_bottom(ecv, cv, q) :
             traits->curves_compare_y_at_x_from_top(ecv,cv,q)) == LARGER)
        {
	  //if type == vertical ray shoot we want to return the edge that points 
	  //           towards q
	  //if type == locate -  
          // ecv is closer to p than cv.
         if (type != (traits->point_equal(curr->target()->point(), q)))
            // means we're under cv (so we take the outer edge part).
            e = curr;      
          else
            // means we're above cv (between cv and ecv) and so
            // we take the inner edge part.
            e = curr->twin();  

	 //idit - was moved, and to change to suit down ray shoot
	 //in this case q is upper point of a vertical edge. 
	 //in this case we have to take (in locate) the halfedge that q is its 
	 //source
	 //in vertical ray shoot we we have to take the halfedge that q is its 
	 //target
	 if (traits->curve_is_vertical(cv)) {
	   if (traits->point_is_left_low
	       (traits->curve_leftlow_most(cv), q))
	   {
	     // special treatment for this special case:
	     // vertical segment downward - here we should take
	     // the opposite direction
	     if (type != (traits->point_equal(curr->target()->point(), q))) 
	       e = curr->twin();
	     else
	       e = curr;
	   }
	 }
        }


        if (!type) lt=Planar_map::VERTEX; 
        // lt should be already Planar_map::VERTEX

      }

#ifdef CGAL_PM_DEBUG

      else {
        CGAL_assertion(traits->curves_compare_y_at_x(ecv, cv , p) == 
                       (!up ? LARGER : SMALLER) ||
                       e==curr || e==curr->twin());
      }

#endif // CGAL_PM_DEBUG

    } else if (in_x_range && res == EQUAL) {
      if (!including) {
        /* The vertical ray shoot is not including p itself,
           thus we are interested only in vertical curves that
           extend upwards
           Remark:
           The Locate type is always EDGE
        */
        if (traits->curve_is_vertical(cv) && 
            traits->point_is_right_top(traits->curve_righttop_most(cv), p))
        {
          /*
              x       x
              |       |
             p=x  or  p
                      |
                      x
          */
          lt = Planar_map::EDGE;
          if (up==traits->point_is_left_low(curr->target()->point(),
                                            curr->source()->point()))
            e = curr;
          else 
            e = curr->twin();

#ifdef CGAL_PM_WALK_DEBUG

          std::cerr << "\n find_closest(" 
                    << p << ", , " << up << "," << including 
                    << ",(" << "," << e->target()->point() 
                    << ")," << lt << ");";

#endif

          return true;
        }
      }
      else // including
      {
        // p is in interior of curr->curve();
        if ( !traits->point_equal(p,traits->curve_source(cv)) && 
             !traits->point_equal(p,traits->curve_target(cv)))
        {
          lt = Planar_map::EDGE;
          if (up==traits->point_is_left_low(curr->target()->point(),
                                            curr->source()->point()))
            e = curr;
          else 
            e = curr->twin();
        }
        else // end point
        {
          lt = Planar_map::VERTEX;

#ifdef CGAL_PM_DEBUG
                  
          CGAL_assertion(curr!=pm->halfedges_end());

#endif
          if (traits->point_equal(curr->target()->point(),p))
            e = find_vertex_representation(curr,p,up);        
          else
            e = find_vertex_representation(curr->twin(),p,up);

#ifdef CGAL_PM_DEBUG
          CGAL_assertion(traits->point_equal(e->target()->point(),p));

#endif

        }

#ifdef CGAL_PM_WALK_DEBUG

        std::cerr << "\n find_closest(" 
                  << p << ", , " << up << "," << including 
                  << ",(" << e->source()->point() 
                  << "," << e->target()->point()  
                  << ")," << lt 
                  << ");";

#endif

        return true;
      }
    }
    ++curr;
  } while (curr != c);

  if (!intersection) {
    lt = Planar_map::UNBOUNDED_FACE;
    return false;
  }
  if (type) lt = (inside ? Planar_map::FACE : Planar_map::UNBOUNDED_FACE);
  

#ifdef CGAL_PM_WALK_DEBUG

  std::cerr << "\n find_closest(" << p << ", , " << up << "," << including 
            << ",(" << e->source()->point() << "," << e->target()->point()  
            << ")," << lt << ");";

  if (lt == Planar_map::FACE && e == pm->halfedges_end())
    std::cout << "Error - e is pm->halfedges_end() while lt is face"
              << std::endl;
  
  if (lt == Planar_map::FACE && e->face()->is_unbounded()){
    std::cout << "Error - e->face is unbounded while lt is face"
              << std::endl;
    if ( !(e->twin()->face()->is_unbounded()) )
      std::cout << "Probably confused with twin halfedge" << std::endl;
  }
  
  if (lt == Planar_map::UNBOUNDED_FACE && !(e->face()->is_unbounded()) ){
    std::cout << "Error - lt is UNBOUNDED_FACE, but e is on a bounded face"
              << std::endl;
    if (e->twin()->face()->is_unbounded())
      std::cout << "Probably confused with twin halfedge" << std::endl;
  }
  
#endif

  return true;
}

CGAL_END_NAMESPACE

#endif
