SPAR/AIModule/BWTA/vendors/CGAL/CGAL/Basic_sweep_line_2.h

Go to the documentation of this file.

// Copyright (c) 2005, 2009  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.
//
// $URL: svn+ssh://scm.gforge.inria.fr/svn/cgal/branches/CGAL-3.5-branch/Arrangement_on_surface_2/include/CGAL/Basic_sweep_line_2.h $
// $Id: Basic_sweep_line_2.h 50366 2009-07-05 12:56:48Z efif $
// 
//
// Author(s)     : Baruch Zukerman <baruchzu@post.tau.ac.il>
//                 (based on old version by Tali Zvi)

#ifndef CGAL_BASIC_SWEEP_LINE_2_H
#define CGAL_BASIC_SWEEP_LINE_2_H

#include <boost/mpl/assert.hpp>
#include <CGAL/assertions.h>
#include <CGAL/memory.h>
#include <CGAL/Sweep_line_2/Sweep_line_functors.h>
#include <CGAL/Sweep_line_2/Sweep_line_subcurve.h>
#include <CGAL/Sweep_line_2/Sweep_line_event.h>
#include <CGAL/Multiset.h>
#include <CGAL/Arrangement_2/Arr_traits_adaptor_2.h>
#include <CGAL/Arr_tags.h>
#include <vector>
#include <algorithm>
#include <iterator>

#ifndef CGAL_SL_VERBOSE

#define CGAL_SL_DEBUG(a)
#define CGAL_PRINT_INSERT(a)
#define CGAL_PRINT_ERASE(a)
#define CGAL_PRINT_NEW_EVENT(p, e) 
#define CGAL_PRINT(a)

#else

#include <iostream>

#define CGAL_SL_DEBUG(a) {a}
#define CGAL_PRINT_INSERT(a) { std::cout << "+++ inserting "; \
                          (a)->Print(); \
                          std::cout << "    currentPos = "; \
                          PrintEvent(this->m_currentEvent); \
                          std::cout << "\n"; \
                          }
#define CGAL_PRINT_ERASE(a)  { std::cout << "--- erasing " ; \
                          (a)->Print(); }
#define CGAL_PRINT_NEW_EVENT(p, e) \
{ std::cout << "%%% a new event was created at " << (p) << std::endl; \
  (e)->Print(); }
#define CGAL_PRINT(a) { std::cout << a ; }

#endif



CGAL_BEGIN_NAMESPACE

template < class Traits_,
           class Visitor_,
           class Subcurve_ = Sweep_line_subcurve<Traits_>,
           typename Event_ = Sweep_line_event<Traits_, Subcurve_>,
           typename Allocator_ = CGAL_ALLOCATOR(int) >
class Basic_sweep_line_2
{
public:

  typedef Traits_                                       Traits_2;
  typedef Visitor_                                      Visitor;
  typedef Event_                                        Event;
  typedef Subcurve_                                     Subcurve;
  typedef Allocator_                                    Allocator;

  typedef Arr_traits_basic_adaptor_2<Traits_2>          Traits_adaptor_2;
  typedef typename Traits_adaptor_2::Point_2            Point_2;
  typedef typename Traits_adaptor_2::X_monotone_curve_2 X_monotone_curve_2;

  typedef typename Traits_adaptor_2::Arr_left_side_tag   Arr_left_side_tag;
  typedef typename Traits_adaptor_2::Arr_bottom_side_tag Arr_bottom_side_tag;
  typedef typename Traits_adaptor_2::Arr_top_side_tag    Arr_top_side_tag;
  typedef typename Traits_adaptor_2::Arr_right_side_tag  Arr_right_side_tag;

  BOOST_MPL_ASSERT(
      (typename 
       Arr_sane_identified_tagging< Arr_left_side_tag, Arr_bottom_side_tag, 
       Arr_top_side_tag, Arr_right_side_tag >::result)
  );
  
protected:

  typedef typename Arr_are_all_sides_oblivious_tag< 
                     Arr_left_side_tag, Arr_bottom_side_tag, 
                     Arr_top_side_tag, Arr_right_side_tag >::result
  Are_all_sides_oblivious_tag;
  
public:

  typedef CGAL::Compare_events<Traits_adaptor_2, Event> Compare_events;
  typedef Multiset<Event*, Compare_events, Allocator>   Event_queue; 
  typedef typename Event_queue::iterator                Event_queue_iterator;

  typedef typename Event::Subcurve_iterator
    Event_subcurve_iterator;

  typedef Sweep_line_event<Traits_2, Subcurve>          Base_event;
  typedef typename Base_event::Attribute                Attribute;
  
  typedef Sweep_line_subcurve<Traits_2>                 Base_subcurve;
  typedef class Curve_comparer<Traits_2, Base_subcurve> Compare_curves;
  typedef Multiset<Base_subcurve*,
                   Compare_curves, 
                   Allocator>                           Status_line;
  typedef typename Status_line::iterator                Status_line_iterator;

  typedef typename Allocator::template rebind<Event>    Event_alloc_rebind;
  typedef typename Event_alloc_rebind::other            Event_alloc;

  typedef typename Allocator::template rebind<Subcurve> Subcurve_alloc_rebind;
  typedef typename Subcurve_alloc_rebind::other         Subcurve_alloc;


protected:

  struct CompEventPtr
  {
    Comparison_result operator() (Event *e1, Event *e2) const
    {
      if (e1 < e2)
        return (SMALLER);
      if (e1 > e2)
        return (LARGER);
      return (EQUAL);
    }
  };

  typedef Multiset<Event*, CompEventPtr>           Allocated_events_set;
  typedef typename Allocated_events_set::iterator  Allocated_events_iterator;

  // Data members:
  const Traits_adaptor_2 * m_traits;// A traits-class object.
  bool              m_traitsOwner;  // Whether this object was allocated by
                                    // this class (and thus should be freed).

  Event            *m_currentEvent; // The current event.

  Compare_curves   m_statusLineCurveLess;
                                     // Comparison functor for the status line.

  Compare_events   m_queueEventLess; // Comparison functor for the event queue.

  Event_queue     *m_queue;          // The event queue (the X-structure).

  Subcurve        *m_subCurves;      // An array of the subcurves.
  Status_line      m_statusLine;     // The status line (the Y-structure).

  Allocated_events_set m_allocated_events;
                                     // The events that have been allocated
                                     // (and have not yet been deallocated).

  Status_line_iterator m_status_line_insert_hint;
                                     // An iterator of the status line, which
                                     // is used as a hint for insertions.

  bool             m_is_event_on_above;
                                     // Indicates if the current event is on
                                     // the interior of existing curve. This 
                                     // may happen only with events that are
                                     // associated with isolated query points.

  Event_alloc    m_eventAlloc;       // An allocator for the events objects.
  Subcurve_alloc m_subCurveAlloc;    // An allocator for the subcurve objects.

  Event          m_masterEvent;      // A master Event (created once by the
                                     // constructor) for the allocator's usage.

  Subcurve       m_masterSubcurve;   // A master Subcurve (created once by the
                                     // constructor) for the allocator's usage.

  unsigned int   m_num_of_subCurves; // Number of subcurves.

  Visitor       *m_visitor;          // The sweep-line visitor that will be
                                     // notified during the sweep.

public:

  Basic_sweep_line_2 (Visitor *visitor);

  Basic_sweep_line_2 (const Traits_2 *traits, Visitor *visitor);

  virtual ~Basic_sweep_line_2 ();

  template<class CurveInputIterator>
  void sweep (CurveInputIterator curves_begin,
              CurveInputIterator curves_end)
  {
    m_visitor->before_sweep();
    _init_sweep(curves_begin, curves_end);
    //m_visitor ->after_init();
    _sweep();
    _complete_sweep();
    m_visitor ->after_sweep();
  }

  template<class CurveInputIterator, class PointInputIterator>
  void sweep (CurveInputIterator curves_begin,
              CurveInputIterator curves_end,
              PointInputIterator action_points_begin,
              PointInputIterator action_points_end)
  {
    m_visitor->before_sweep();
    _init_sweep(curves_begin, curves_end);
    _init_points(action_points_begin, action_points_end, Base_event::ACTION);
    //m_visitor ->after_init();
    _sweep();
    _complete_sweep();
    m_visitor ->after_sweep();
  }

  template<class CurveInputIterator, class ActionPointItr,class QueryPointItr>
  void sweep (CurveInputIterator curves_begin,
              CurveInputIterator curves_end,
              ActionPointItr action_points_begin,
              ActionPointItr action_points_end,
              QueryPointItr query_points_begin,
              QueryPointItr query_points_end)
  {
    m_visitor->before_sweep();
    _init_sweep(curves_begin, curves_end);
    _init_points(action_points_begin, action_points_end, Base_event::ACTION);
    _init_points(query_points_begin, query_points_end, Base_event::QUERY);
    //m_visitor ->after_init();
    _sweep();
    _complete_sweep();
    m_visitor ->after_sweep();
  }

  Status_line_iterator status_line_begin ()
  {
    return (m_statusLine.begin());
  }

  Status_line_iterator status_line_end()
  {
    return (m_statusLine.end());
  }

  unsigned int status_line_size() const
  {
    return (m_statusLine.size());
  }

  bool is_status_line_empty() const
  {
    return (m_statusLine.empty());
  }

  Event_queue_iterator event_queue_begin()
  {
    return (m_queue.begin());
  }

  Event_queue_iterator event_queue_end()
  {
    return (m_queue.end());
  }

  unsigned int event_queue_size() const
  {
    return (m_queue.size());
  }

  bool is_event_queue_empty() const
  {
    return (m_queue.empty());
  }

  void stop_sweep();

  void deallocate_event(Event* event);

  Event* current_event()
  {
    return (m_currentEvent);
  }

  const Traits_2 * traits ()
  {
    return m_traits;
  }

protected:

  void _sweep();

  template <class PointInputIterator>
  void _init_points (PointInputIterator points_begin,
                     PointInputIterator points_end,
                     Attribute type)
  {
    PointInputIterator   pit;
    for (pit = points_begin; pit != points_end; ++pit)
      _init_point (*pit, type);

    return;
  }

  template<class CurveInputIterator>
  void _init_curves (CurveInputIterator curves_begin,
                     CurveInputIterator curves_end)
  {
    CurveInputIterator   cit;
    unsigned int         index = 0;

    for (cit = curves_begin; cit != curves_end; ++cit, ++index)
      _init_curve (*cit, index);

    return;
  }

  template<class CurveInputIterator>
  void _init_sweep (CurveInputIterator curves_begin,
                    CurveInputIterator curves_end)
  {
    m_num_of_subCurves = std::distance (curves_begin, curves_end);

    _init_structures();

    // Initialize the curves.
    _init_curves (curves_begin, curves_end);
    return;
  }

  virtual void _init_structures ();

  virtual void _complete_sweep();

  void _init_point (const Point_2& pt, Attribute type);

  void _init_curve (const X_monotone_curve_2& curve, unsigned int index);

  void _init_curve_end (const X_monotone_curve_2& cv,
                        Arr_curve_end ind,
                        Subcurve* sc);
  
  virtual void _handle_left_curves();

  void _handle_event_without_left_curves ();

  void _sort_left_curves ();

  virtual void _handle_right_curves ();

  virtual bool _add_curve_to_right (Event* event, Subcurve* curve,
                                    bool overlap_exist = false);

  void _remove_curve_from_status_line (Subcurve *leftCurve);
 
  Event* _allocate_event (const Point_2& pt, Attribute type,
                          Arr_parameter_space ps_x, Arr_parameter_space ps_y);

  Event* _allocate_event_at_open_boundary (Attribute type,
                                           Arr_parameter_space ps_x,
                                           Arr_parameter_space ps_y);

  std::pair<Event*, bool> _push_event (const Point_2& pt,
                                       Attribute type,
                                       Arr_parameter_space ps_x,
                                       Arr_parameter_space ps_y,
                                       Subcurve* sc = NULL);

  std::pair<Event*, bool> _push_event (const X_monotone_curve_2& cv,
                                       Arr_curve_end ind,
                                       Attribute type,
                                       Arr_parameter_space ps_x,
                                       Arr_parameter_space ps_y,
                                       Subcurve* sc = NULL);

  void _update_event_at_open_boundary(Event* e,
                                      const X_monotone_curve_2& cv,
                                      Arr_curve_end ind,
                                      bool is_new)
  {
    _update_event_at_open_boundary(e, cv, ind, is_new, 
                                   Are_all_sides_oblivious_tag());
  }

  void _update_event_at_open_boundary(Event* e,
                                      const X_monotone_curve_2& cv,
                                      Arr_curve_end ind,
                                      bool is_new,
                                      Arr_not_all_sides_oblivious_tag)
  {
    m_visitor->update_event (e, cv, ind, is_new);
  }

  void _update_event_at_open_boundary(Event* /* e */,
                                      const X_monotone_curve_2& /* cv */,
                                      Arr_curve_end /* ind */,
                                      bool /* is_new */,
                                      Arr_all_sides_oblivious_tag)
  {
    CGAL_error();
  }

#ifdef CGAL_SL_VERBOSE
  void PrintEventQueue();
  void PrintSubCurves();
  void PrintStatusLine();
  void PrintOpenBoundaryType(Arr_parameter_space x, Arr_parameter_space y);
  void PrintEvent(const Event* e);
#endif

};

//DEBUG UTILITIES
#ifdef CGAL_SL_VERBOSE
  #include <CGAL/Sweep_line_2/Sweep_line_2_debug.h>
#endif

CGAL_END_NAMESPACE

#include <CGAL/Sweep_line_2/Basic_sweep_line_2_impl.h>

#endif