SPAR/AIModule/BWTA/vendors/CGAL/CGAL/Arrangement_on_surface_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/Arrangement_on_surface_2.h $
// $Id: Arrangement_on_surface_2.h 50781 2009-07-23 12:28:10Z efif $
// 
//
// Author(s): Ron Wein          <wein@post.tau.ac.il>
//            Efi Fogel         <efif@post.tau.ac.il>
//            Eric Berberich    <ericb@post.tau.ac.il>
//            (based on old version by: Iddo Hanniel,
//                                      Eyal Flato,
//                                      Oren Nechushtan,
//                                      Ester Ezra,
//                                      Shai Hirsch,
//                                      and Eugene Lipovetsky)
#ifndef CGAL_ARRANGEMENT_ON_SURFACE_2_H
#define CGAL_ARRANGEMENT_ON_SURFACE_2_H

#include <boost/mpl/assert.hpp>
#include <CGAL/Arr_tags.h>
#include <CGAL/Arr_enums.h>
#include <CGAL/HalfedgeDS_iterator.h>
#include <CGAL/Arrangement_2/Arrangement_2_iterators.h>
#include <CGAL/In_place_list.h>
#include <CGAL/Arr_default_dcel.h>
#include <CGAL/Arr_observer.h>
#include <CGAL/Arr_accessor.h>
#include <CGAL/Arrangement_2/Arr_traits_adaptor_2.h>
#include <CGAL/function_objects.h>
#include <CGAL/Iterator_project.h>
#include <CGAL/Iterator_transform.h>
#include <map>
#include <vector>
#include <algorithm>

CGAL_BEGIN_NAMESPACE

template <class GeomTraits_, class TopTraits_> 
class Arrangement_on_surface_2
{
public:

  typedef GeomTraits_                                     Geometry_traits_2;
  typedef TopTraits_                                      Topology_traits;

  // first define adaptor ...
  typedef Arr_traits_basic_adaptor_2<Geometry_traits_2>   Traits_adaptor_2;
  
  // .. as it completes (potentially) missing side tags
  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)
  );

public:
  
  typedef Arrangement_on_surface_2<Geometry_traits_2,
                                   Topology_traits>       Self;

  typedef typename Geometry_traits_2::Point_2             Point_2;
  typedef typename Geometry_traits_2::X_monotone_curve_2  X_monotone_curve_2;

  // maybe remove this in a future version (that supports complete handling
  // of all sides)
  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 typename Topology_traits::Dcel                  Dcel;
  typedef typename Dcel::Size                             Size;

protected:

  friend class Arr_observer<Self>;
  friend class Arr_accessor<Self>;
  
  // Internal DCEL types:
  typedef typename Dcel::Vertex                     DVertex;
  typedef typename Dcel::Halfedge                   DHalfedge;
  typedef typename Dcel::Face                       DFace;
  typedef typename Dcel::Outer_ccb                  DOuter_ccb;
  typedef typename Dcel::Inner_ccb                  DInner_ccb;
  typedef typename Dcel::Isolated_vertex            DIso_vertex;

  typedef typename Dcel::difference_type            DDifference;  
  typedef typename Dcel::iterator_category          DIterator_category;

  typedef typename Dcel::Vertex_iterator            DVertex_iter;
  typedef typename Dcel::Vertex_const_iterator      DVertex_const_iter;

  typedef typename Dcel::Halfedge_iterator          DHalfedge_iter;
  typedef typename Dcel::Halfedge_const_iterator    DHalfedge_const_iter;

  typedef typename Dcel::Edge_iterator              DEdge_iter;
  typedef typename Dcel::Edge_const_iterator        DEdge_const_iter;

  typedef typename Dcel::Face_iterator              DFace_iter;
  typedef typename Dcel::Face_const_iterator        DFace_const_iter;

  typedef typename DFace::Outer_ccb_iterator        DOuter_ccb_iter;
  typedef typename DFace::Outer_ccb_const_iterator  DOuter_ccb_const_iter;

  typedef typename DFace::Inner_ccb_iterator        DInner_ccb_iter;
  typedef typename DFace::Inner_ccb_const_iterator  DInner_ccb_const_iter;

  typedef typename DFace::Isolated_vertex_iterator
                                                    DIso_vertex_iter;
  typedef typename DFace::Isolated_vertex_const_iterator
                                                    DIso_vertex_const_iter;

protected:

  class _Is_concrete_vertex
  {
  private:

    const Topology_traits  *m_topol_traits;

  public:

    _Is_concrete_vertex () :
      m_topol_traits (NULL)
    {}

    _Is_concrete_vertex (const Topology_traits * topol_traits) :
      m_topol_traits (topol_traits)
    {}

    bool operator() (const DVertex& v) const
    {
      if (m_topol_traits == NULL)
        return (true);

      return (m_topol_traits->is_concrete_vertex (&v));
    }
  };

  class _Is_valid_vertex
  {
  private:

    const Topology_traits * m_topol_traits;

  public:

    _Is_valid_vertex () :
      m_topol_traits (NULL)
    {}

    _Is_valid_vertex (const Topology_traits * topol_traits) :
      m_topol_traits (topol_traits)
    {}

    bool operator() (const DVertex& v) const
    {
      if (m_topol_traits == NULL)
        return (true);

      return (m_topol_traits->is_valid_vertex (&v));
    }
  };

  class _Is_valid_halfedge
  {
  private:

    const Topology_traits  *m_topol_traits;

  public:

    _Is_valid_halfedge () :
      m_topol_traits (NULL)
    {}

    _Is_valid_halfedge (const Topology_traits * topol_traits) :
      m_topol_traits (topol_traits)
    {}

    bool operator() (const DHalfedge& he) const
    {
      if (m_topol_traits == NULL)
        return (true);

      return (m_topol_traits->is_valid_halfedge (&he));
    }
  };

  class _Is_valid_face
  {
  private:

    const Topology_traits  *m_topol_traits;

  public:

    _Is_valid_face () :
      m_topol_traits (NULL)
    {}

    _Is_valid_face (const Topology_traits * topol_traits) :
      m_topol_traits (topol_traits)
    {}

    bool operator() (const DFace& f) const
    {
      if (m_topol_traits == NULL)
        return (true);

      return (m_topol_traits->is_valid_face (&f));
    }
  };

  class _Is_unbounded_face
  {
  private:

    const Topology_traits * m_topol_traits;

  public:

    _Is_unbounded_face () :
      m_topol_traits (NULL)
    {}

    _Is_unbounded_face (const Topology_traits * topol_traits) :
      m_topol_traits (topol_traits)
    {}

    const Topology_traits * topology_traits() const { return m_topol_traits; }

    bool operator() (const DFace& f) const
    {
      return (m_topol_traits->is_valid_face (&f) &&
              m_topol_traits->is_unbounded (&f));
    }
  };

public:

  // Forward declerations:
  class Vertex;
  class Halfedge;
  class Face;

  // Definition of the halfedge data-structure itereators and circulators:
  typedef I_Filtered_iterator
    <DVertex_iter, _Is_concrete_vertex,
     Vertex, DDifference,
     DIterator_category>                          Vertex_iterator;
  
  typedef I_Filtered_const_iterator
    <DVertex_const_iter, _Is_concrete_vertex,
     DVertex_iter, Vertex,
     DDifference, DIterator_category>             Vertex_const_iterator;
  
  typedef I_Filtered_iterator
    <DHalfedge_iter, _Is_valid_halfedge, 
     Halfedge, DDifference,
     DIterator_category>                          Halfedge_iterator;
  
  typedef I_Filtered_const_iterator
    <DHalfedge_const_iter, _Is_valid_halfedge,
     DHalfedge_iter, Halfedge, DDifference,
     DIterator_category>                          Halfedge_const_iterator;

  class Edge_iterator :
    public I_Filtered_iterator<DEdge_iter, _Is_valid_halfedge,
                               Halfedge, DDifference,
                               DIterator_category>
  {
    typedef I_Filtered_iterator<DEdge_iter, 
                                _Is_valid_halfedge,
                                Halfedge, DDifference,
                                DIterator_category>          Base;

  public:
 
    Edge_iterator ()
    {}

    Edge_iterator (DEdge_iter iter, DEdge_iter iend,
                   const _Is_valid_halfedge& pred) :
      Base (iter, iend, pred)
    {}

    // Casting to a halfedge iterator.
    operator Halfedge_iterator () const
    {
      return (Halfedge_iterator (DHalfedge_iter (this->current_iterator())));
    }

    operator Halfedge_const_iterator () const
    {
      return (Halfedge_const_iterator 
              (DHalfedge_const_iter (this->current_iterator())));
    }    
  };

  class Edge_const_iterator :
    public I_Filtered_const_iterator<DEdge_const_iter,
                                     _Is_valid_halfedge,
                                     DEdge_iter,
                                     Halfedge, DDifference,
                                     DIterator_category>
  {
    typedef I_Filtered_const_iterator<DEdge_const_iter,
                                      _Is_valid_halfedge,
                                      DEdge_iter,
                                      Halfedge, DDifference,
                                      DIterator_category>    Base;

  public:
 
    Edge_const_iterator ()
    {}

    Edge_const_iterator (Edge_iterator iter) :
      Base (iter.current_iterator(),
            iter.past_the_end(),
            iter.filter())
    {}

    Edge_const_iterator (DEdge_const_iter iter, DEdge_const_iter iend,
                         const _Is_valid_halfedge& pred) :
      Base (iter, iend, pred)
    {}

    // Casting to a halfedge iterator.
    operator Halfedge_const_iterator () const
    {
      return (Halfedge_const_iterator 
              (DHalfedge_const_iter (this->current_iterator())));
    }
  };
  
  typedef I_Filtered_iterator
    <DFace_iter, _Is_valid_face,
     Face, DDifference,
     DIterator_category>                          Face_iterator;
  
  typedef I_Filtered_const_iterator
    <DFace_const_iter, _Is_valid_face, 
     DFace_iter, Face,
     DDifference, DIterator_category>             Face_const_iterator;

  typedef _HalfedgeDS_vertex_circ
    <Halfedge, Halfedge_iterator,
     Bidirectional_circulator_tag>    Halfedge_around_vertex_circulator;

  typedef _HalfedgeDS_vertex_const_circ
    <Halfedge,
     Halfedge_const_iterator,
     Bidirectional_circulator_tag>    Halfedge_around_vertex_const_circulator;

  typedef _HalfedgeDS_facet_circ
    <Halfedge,
     Halfedge_iterator,
     Bidirectional_circulator_tag>    Ccb_halfedge_circulator;

  typedef _HalfedgeDS_facet_const_circ
    <Halfedge,
     Halfedge_const_iterator,
     Bidirectional_circulator_tag>    Ccb_halfedge_const_circulator;

  class Unbounded_face_iterator :
    public I_Filtered_iterator<DFace_iter, _Is_unbounded_face,
                               Face, DDifference,
                               DIterator_category>
  {
    typedef I_Filtered_iterator<DFace_iter,
                                _Is_unbounded_face,
                                Face, DDifference,
                                DIterator_category>         Base;

  public:
 
    Unbounded_face_iterator ()
    {}

    Unbounded_face_iterator (DFace_iter iter, DFace_iter iend,
                             const _Is_unbounded_face & is_unbounded) :
      Base (iter, iend, is_unbounded)
    {}

    // Casting to a face iterator.
    operator Face_iterator () const
    {
      return (Face_iterator (DFace_iter (this->current_iterator()),
                             DFace_iter (this->past_the_end()),
                             _Is_valid_face(this->filter().topology_traits())));
    }

    operator Face_const_iterator () const
    {
      return (Face_const_iterator
              (DFace_const_iter (this->current_iterator()),
               DFace_const_iter (this->past_the_end()),
               _Is_valid_face(this->filter().topology_traits())));
    }    
  };

  class Unbounded_face_const_iterator :
    public I_Filtered_const_iterator<DFace_const_iter,
                                     _Is_unbounded_face, 
                                     DFace_iter, Face,
                                     DDifference,
                                     DIterator_category>
  {
    typedef I_Filtered_const_iterator<DFace_const_iter,
                                      _Is_unbounded_face, 
                                      DFace_iter, Face,
                                      DDifference,
                                      DIterator_category>   Base;

  public:
 
    Unbounded_face_const_iterator ()
    {}

    Unbounded_face_const_iterator (Unbounded_face_iterator iter) :
      Base (iter)
    {}

    Unbounded_face_const_iterator (DFace_const_iter iter,
                                   DFace_const_iter iend,
                                   const _Is_unbounded_face & is_unbounded) :
      Base (iter, iend, is_unbounded)
    {}

    // Casting to a face iterator.
    operator Face_const_iterator () const
    {
      return (Face_const_iterator (DFace_const_iter(this->current_iterator()),
                                   DFace_const_iter(this->past_the_end())));
    }
  };

protected:

  struct _Halfedge_to_ccb_circulator
  {
    typedef DHalfedge*               argument_type;
    typedef Ccb_halfedge_circulator  result_type;
 
    result_type operator() (argument_type s) const
    {
      return Ccb_halfedge_circulator (Halfedge_iterator (s));
    }
  };

  struct _Const_halfedge_to_ccb_circulator
  {
    typedef const DHalfedge*               argument_type;
    typedef Ccb_halfedge_const_circulator  result_type;
 
    result_type operator() (argument_type s) const
    {
      return Ccb_halfedge_const_circulator (Halfedge_const_iterator (s));
    }
  };

  typedef Cast_function_object<DVertex, Vertex>   _Vertex_to_vertex;

public:
  
  typedef Iterator_transform<DOuter_ccb_iter,
                             _Halfedge_to_ccb_circulator>
                                      Outer_ccb_iterator;

  typedef Iterator_transform<DOuter_ccb_const_iter,
                             _Const_halfedge_to_ccb_circulator> 
                                      Outer_ccb_const_iterator;

  typedef Iterator_transform<DInner_ccb_iter,
                             _Halfedge_to_ccb_circulator>
                                      Inner_ccb_iterator;

  typedef Iterator_transform<DInner_ccb_const_iter,
                             _Const_halfedge_to_ccb_circulator> 
                                      Inner_ccb_const_iterator;

  class Isolated_vertex_iterator :
    public Iterator_project<DIso_vertex_iter,
                            _Vertex_to_vertex>
  {
    typedef Iterator_project<DIso_vertex_iter,
                             _Vertex_to_vertex>         Base;

  public:

    Isolated_vertex_iterator ()
    {}

    Isolated_vertex_iterator (DIso_vertex_iter iter) :
      Base (iter)
    {}

    // Casting to a vertex iterator.
    operator Vertex_iterator () const
    {
      return (Vertex_iterator (DVertex_iter (this->ptr())));
    }

    operator Vertex_const_iterator () const
    {
      return (Vertex_const_iterator (DVertex_const_iter (this->ptr())));
    }
  };
  
  class Isolated_vertex_const_iterator :
    public Iterator_project<DIso_vertex_const_iter,
                            _Vertex_to_vertex>
  {
    typedef Iterator_project<DIso_vertex_const_iter,
                             _Vertex_to_vertex>          Base;

  public:

    Isolated_vertex_const_iterator ()
    {}

    Isolated_vertex_const_iterator (Isolated_vertex_iterator iter) :
      Base (iter)
    {}

    Isolated_vertex_const_iterator (DIso_vertex_const_iter iter) :
      Base (iter)
    {}

    // Casting to a vertex iterator.
    operator Vertex_const_iterator () const
    {
      return (Vertex_const_iterator (DVertex_const_iter (this->ptr())));
    }
  };

protected:

  class _Valid_vertex_iterator :
    public I_Filtered_iterator<DVertex_iter,
                               _Is_valid_vertex, Vertex,
                               DDifference,
                               DIterator_category>
  {
    typedef I_Filtered_iterator<DVertex_iter,
                                _Is_valid_vertex, Vertex,
                                DDifference,
                                DIterator_category>               Base;

   public:
  
    _Valid_vertex_iterator ()
    {}

    _Valid_vertex_iterator (DVertex_iter iter, DVertex_iter iend,
                            const _Is_valid_vertex& pred) :
      Base (iter, iend, pred)
    {}

    // Casting to a vertex iterator.
    operator Vertex_iterator () const
    {
      return (Vertex_iterator (DVertex_iter (this->current_iterator())));
    }

    operator Vertex_const_iterator () const
    {
      return (Vertex_const_iterator (DVertex_const_iter
                                     (this->current_iterator())));
    }
  };

public:

  // Definition of handles (equivalent to iterators):
  typedef Vertex_iterator              Vertex_handle;
  typedef Halfedge_iterator            Halfedge_handle;
  typedef Face_iterator                Face_handle;

  typedef Vertex_const_iterator        Vertex_const_handle;
  typedef Halfedge_const_iterator      Halfedge_const_handle;
  typedef Face_const_iterator          Face_const_handle;

  class Vertex : public DVertex
  {
    typedef DVertex               Base;

  public:

    Vertex()
    {}

    CGAL_DEPRECATED bool is_at_infinity() const
    { return (Base::has_null_point()); }

    bool is_at_open_boundary () const
    {
      return (Base::has_null_point());
    }

    Size degree () const
    {
      if (this->is_isolated())
        return (0);

      // Go around the vertex and count the incident halfedges.
      const DHalfedge  *he_first = Base::halfedge();
      const DHalfedge  *he_curr = he_first;
      Size              n = 0;

      if (he_curr != NULL)
      {
        do
        {
          n++;
          he_curr = he_curr->next()->opposite();
        } while (he_curr != he_first);
      }
      return (n);
    }

    Halfedge_around_vertex_circulator incident_halfedges() 
    {
      CGAL_precondition (! this->is_isolated());

      return Halfedge_around_vertex_circulator
        (DHalfedge_iter (Base::halfedge()));
    }

    Halfedge_around_vertex_const_circulator incident_halfedges() const 
    {
      CGAL_precondition (! this->is_isolated());

      return Halfedge_around_vertex_const_circulator
        (DHalfedge_const_iter (Base::halfedge())); 
    }

    Face_handle face()
    {
      CGAL_precondition (this->is_isolated());

      return (DFace_iter (Base::isolated_vertex()->face()));
    }

    Face_const_handle face() const
    {
      CGAL_precondition (this->is_isolated());

      return (DFace_const_iter (Base::isolated_vertex()->face()));
    }

  private:

    // Blocking access to inherited functions from the Dcel::Vertex.
    bool has_null_point () const;
    void set_point (Point_2* );
    void set_boundary (Arr_parameter_space , Arr_parameter_space );
    const DHalfedge* halfedge () const;
    DHalfedge* halfedge ();
    void set_halfedge (DHalfedge* );
    const DIso_vertex* isolated_vertex () const;
    DIso_vertex* isolated_vertex ();
    void set_isolated_vertex (DIso_vertex* );
  };

  class Halfedge : public DHalfedge
  {
    typedef DHalfedge             Base;

  public:

    Halfedge ()
    {}

    bool is_fictitious () const
    {
      return (Base::has_null_curve());
    }

    Vertex_handle source ()
    {
      return (DVertex_iter (Base::opposite()->vertex()));
    }

    Vertex_const_handle source () const
    {
      return (DVertex_const_iter (Base::opposite()->vertex()));
    }
    
    Vertex_handle target ()
    {
      return (DVertex_iter (Base::vertex()));
    }

    Vertex_const_handle target () const
    {
      return (DVertex_const_iter (Base::vertex()));
    }
    
    Face_handle face()
    {
      if (! Base::is_on_inner_ccb())
        return (DFace_iter (Base::outer_ccb()->face()));
      else
        return (DFace_iter (Base::inner_ccb()->face()));
    }

    Face_const_handle face() const
    {
      if (! Base::is_on_inner_ccb())
        return (DFace_const_iter (Base::outer_ccb()->face()));
      else
        return (DFace_const_iter (Base::inner_ccb()->face()));
    }

    Halfedge_handle twin()
    {
      return (DHalfedge_iter (Base::opposite()));
    }

    Halfedge_const_handle twin() const 
    {
      return (DHalfedge_const_iter (Base::opposite()));
    }

    Halfedge_handle prev () 
    { 
      return (DHalfedge_iter (Base::prev()));
    }

    Halfedge_const_handle prev () const 
    { 
      return (DHalfedge_const_iter (Base::prev()));
    }

    Halfedge_handle next () 
    { 
      return (DHalfedge_iter (Base::next()));
    }

    Halfedge_const_handle next () const 
    { 
      return (DHalfedge_const_iter (Base::next()));
    }

    Ccb_halfedge_circulator ccb ()
    { 
      return Ccb_halfedge_circulator (DHalfedge_iter (this));
    }

    Ccb_halfedge_const_circulator ccb () const
    { 
      return Ccb_halfedge_const_circulator (DHalfedge_const_iter (this));
    }

  private:

    // Blocking access to inherited functions from the Dcel::Halfedge.
    bool has_null_curve () const;
    void set_curve (X_monotone_curve_2* );
    const DHalfedge* opposite () const;
    DHalfedge* opposite ();
    void set_opposite (DHalfedge* );
    void set_direction (Arr_halfedge_direction );
    void set_prev (DHalfedge* );
    void set_next (DHalfedge* );
    const DVertex* vertex () const ;
    DVertex* vertex ();
    void set_vertex (DVertex* );
    const DOuter_ccb* outer_ccb () const;
    DOuter_ccb* outer_ccb ();
    void set_outer_ccb (DOuter_ccb* );
    const DInner_ccb* inner_ccb () const;
    DInner_ccb* inner_ccb ();
    void set_inner_ccb (DInner_ccb* );
  };

  class Face : public DFace
  {
    typedef DFace                 Base;

  public:

    Face()
    {}

    Outer_ccb_iterator outer_ccbs_begin() 
    {
      return (DOuter_ccb_iter (Base::outer_ccbs_begin()));
    }

    Outer_ccb_const_iterator outer_ccbs_begin() const
    {
      return (DOuter_ccb_const_iter (Base::outer_ccbs_begin()));
    }
    
    Outer_ccb_iterator outer_ccbs_end() 
    {
      return (DOuter_ccb_iter (Base::outer_ccbs_end()));
    }

    Outer_ccb_const_iterator outer_ccbs_end() const 
    {
      return (DOuter_ccb_const_iter (Base::outer_ccbs_end()));
    }


    Inner_ccb_iterator inner_ccbs_begin() 
    {
      return (DInner_ccb_iter (Base::inner_ccbs_begin()));
    }

    Inner_ccb_const_iterator inner_ccbs_begin() const
    {
      return (DInner_ccb_const_iter (Base::inner_ccbs_begin()));
    }
    
    Inner_ccb_iterator inner_ccbs_end() 
    {
      return (DInner_ccb_iter (Base::inner_ccbs_end()));
    }

    Inner_ccb_const_iterator inner_ccbs_end() const 
    {
      return (DInner_ccb_const_iter (Base::inner_ccbs_end()));
    }


    Isolated_vertex_iterator isolated_vertices_begin ()
    {
      return (DIso_vertex_iter (Base::isolated_vertices_begin()));
    }

    Isolated_vertex_const_iterator isolated_vertices_begin () const
    {
      return (DIso_vertex_const_iter (Base::isolated_vertices_begin()));
    }
    
    Isolated_vertex_iterator isolated_vertices_end () 
    {
      return (DIso_vertex_iter (Base::isolated_vertices_end()));
    }

    Isolated_vertex_const_iterator isolated_vertices_end () const 
    {
      return (DIso_vertex_const_iter (Base::isolated_vertices_end()));
    }



    Ccb_halfedge_circulator outer_ccb () 
    {
      CGAL_precondition (Base::number_of_outer_ccbs() == 1);
      
      DOuter_ccb_iter     iter = Base::outer_ccbs_begin();
      DHalfedge          *he = *iter;

      return Ccb_halfedge_circulator (DHalfedge_iter (he));
    }

    Ccb_halfedge_const_circulator outer_ccb () const
    {
      CGAL_precondition (Base::number_of_outer_ccbs() == 1);

      DOuter_ccb_const_iter  iter = Base::outer_ccbs_begin();
      const DHalfedge       *he = *iter;
 
      return Ccb_halfedge_const_circulator (DHalfedge_const_iter (he));
    }

    Size number_of_holes () const
    {
      return (Base::number_of_inner_ccbs());
    }

    Inner_ccb_iterator holes_begin() 
    {
      return (this->inner_ccbs_begin());
    }

    Inner_ccb_const_iterator holes_begin() const
    {
      return (this->inner_ccbs_begin());
    }
    
    Inner_ccb_iterator holes_end() 
    {
      return (this->inner_ccbs_end());
    }

    Inner_ccb_const_iterator holes_end() const 
    {
      return (this->inner_ccbs_end());
    }

  private:

    // Blocking access to inherited functions from the Dcel::Face.
    void set_unbounded (bool );
    void set_fictitious (bool );
    void add_outer_ccb (DOuter_ccb*, Halfedge* );
    void erase_outer_ccb (DOuter_ccb* );
    void add_inner_ccb (DInner_ccb*, Halfedge* );
    void erase_inner_ccb (DInner_ccb* );
    void add_isolated_vertex (DIso_vertex*, DVertex* );
    void erase_isolated_vertex (DIso_vertex* );
  };

protected:

  typedef CGAL_ALLOCATOR(Point_2)                 Points_alloc;
  typedef CGAL_ALLOCATOR(X_monotone_curve_2)      Curves_alloc;

  typedef Arr_observer<Self>                      Observer;
  typedef std::list<Observer*>                    Observers_container;
  typedef typename Observers_container::iterator  Observers_iterator;

  typedef typename Observers_container::reverse_iterator  
                                                  Observers_rev_iterator;

  // Data members:
  Topology_traits          m_topol_traits;  // the topology traits.
  Points_alloc             m_points_alloc;  // allocator for the points.
  Curves_alloc             m_curves_alloc;  // allocator for the curves.
  Observers_container      m_observers;     // pointers to existing observers.
  const Traits_adaptor_2 * m_geom_traits;   // the geometry-traits adaptor.
  bool                     m_own_traits;    // inidicates whether the geometry
                                            // traits should be freed up.
  Arr_boundary_type        m_boundary_types[4];   

public:
  


  Arrangement_on_surface_2 ();

  Arrangement_on_surface_2 (const Self & arr);

  Arrangement_on_surface_2 (const Geometry_traits_2 * geom_traits);



  Self& operator= (const Self & arr);

  void assign (const Self & arr);



  virtual ~Arrangement_on_surface_2 ();

  virtual void clear();



  inline const Traits_adaptor_2 * traits_adaptor () const
  {
    return (m_geom_traits);
  }

  inline const Geometry_traits_2 * geometry_traits () const
  {
    return (m_geom_traits);
  }

  inline Topology_traits * topology_traits ()
  {
    return (&m_topol_traits);
  }
  
  inline const Topology_traits * topology_traits () const
  {
    return (&m_topol_traits);
  }



  bool is_empty () const
  {
    return (m_topol_traits.is_empty_dcel());
  }

  bool is_valid() const;
  
  Size number_of_vertices () const
  {
    return (m_topol_traits.number_of_concrete_vertices());
  }

  Size number_of_isolated_vertices () const
  {
    return (_dcel().size_of_isolated_vertices());
  }

  Size number_of_halfedges () const
  {
    return (m_topol_traits.number_of_valid_halfedges());
  }

  Size number_of_edges () const
  {
    return (m_topol_traits.number_of_valid_halfedges() / 2);
  }

  Size number_of_faces () const
  {
    return (m_topol_traits.number_of_valid_faces());
  }

  Size number_of_unbounded_faces () const
  {
    Unbounded_face_const_iterator    iter = unbounded_faces_begin();
    Unbounded_face_const_iterator    end = unbounded_faces_end();
    Size                             n_unb = 0;

    while (iter != end)
    {
      n_unb++;
      ++iter;
    }

    return (n_unb);
  }



  Vertex_iterator vertices_begin() 
  { 
    return (Vertex_iterator (_dcel().vertices_begin(),
                             _dcel().vertices_end(),
                             _Is_concrete_vertex (&m_topol_traits))); 
  }

  Vertex_iterator vertices_end()
  {
    return (Vertex_iterator (_dcel().vertices_end(),
                             _dcel().vertices_end(),
                             _Is_concrete_vertex (&m_topol_traits))); 
  }

  Vertex_const_iterator vertices_begin() const
  { 
    return (Vertex_const_iterator (_dcel().vertices_begin(),
                                   _dcel().vertices_end(),
                                   _Is_concrete_vertex (&m_topol_traits))); 
  }
  
  Vertex_const_iterator vertices_end() const
  {
    return (Vertex_const_iterator (_dcel().vertices_end(),
                                   _dcel().vertices_end(),
                                   _Is_concrete_vertex (&m_topol_traits))); 
  }



  Halfedge_iterator halfedges_begin() 
  { 
    return (Halfedge_iterator (_dcel().halfedges_begin(),
                               _dcel().halfedges_end(),
                               _Is_valid_halfedge (&m_topol_traits))); 
  }

  Halfedge_iterator halfedges_end()
  {
    return (Halfedge_iterator (_dcel().halfedges_end(),
                               _dcel().halfedges_end(),
                               _Is_valid_halfedge (&m_topol_traits))); 
  }

  Halfedge_const_iterator halfedges_begin() const
  { 
    return (Halfedge_const_iterator (_dcel().halfedges_begin(),
                                     _dcel().halfedges_end(),
                                     _Is_valid_halfedge (&m_topol_traits))); 
  }
  
  Halfedge_const_iterator halfedges_end() const
  {
    return (Halfedge_const_iterator (_dcel().halfedges_end(),
                                     _dcel().halfedges_end(),
                                     _Is_valid_halfedge (&m_topol_traits))); 
  }



  Edge_iterator edges_begin() 
  { 
    return (Edge_iterator (_dcel().edges_begin(),
                           _dcel().edges_end(),
                           _Is_valid_halfedge (&m_topol_traits))); 
  }

  Edge_iterator edges_end()
  {
    return (Edge_iterator (_dcel().edges_end(),
                           _dcel().edges_end(),
                           _Is_valid_halfedge (&m_topol_traits))); 
  }

  Edge_const_iterator edges_begin() const
  { 
    return (Edge_const_iterator (_dcel().edges_begin(),
                                 _dcel().edges_end(),
                                 _Is_valid_halfedge (&m_topol_traits))); 
  }
  
  Edge_const_iterator edges_end() const
  {
    return (Edge_const_iterator (_dcel().edges_end(),
                                 _dcel().edges_end(),
                                 _Is_valid_halfedge (&m_topol_traits))); 
  }



  Face_iterator faces_begin() 
  { 
    return (Face_iterator (_dcel().faces_begin(),
                           _dcel().faces_end(),
                           _Is_valid_face (&m_topol_traits))); 
  }

  Face_iterator faces_end()
  {
    return (Face_iterator (_dcel().faces_end(),
                           _dcel().faces_end(),
                           _Is_valid_face (&m_topol_traits))); 
  }

  Face_const_iterator faces_begin() const
  { 
    return (Face_const_iterator (_dcel().faces_begin(),
                                 _dcel().faces_end(),
                                 _Is_valid_face (&m_topol_traits))); 
  }
  
  Face_const_iterator faces_end() const
  {
    return (Face_const_iterator (_dcel().faces_end(),
                                 _dcel().faces_end(),
                                 _Is_valid_face (&m_topol_traits))); 
  }


  Face_const_handle reference_face() const
  {
    return _const_handle_for(this->topology_traits()->reference_face());
  }
  

  Face_handle reference_face()
  {
    return _handle_for(this->topology_traits()->reference_face());
  }




  Unbounded_face_iterator unbounded_faces_begin() 
  { 
    return Unbounded_face_iterator(_dcel().faces_begin(),
                                   _dcel().faces_end(),
                                   _Is_unbounded_face (&m_topol_traits)); 
  }

  Unbounded_face_iterator unbounded_faces_end()
  {
    return Unbounded_face_iterator(_dcel().faces_end(),
                                   _dcel().faces_end(),
                                   _Is_unbounded_face (&m_topol_traits)); 
  }

  Unbounded_face_const_iterator unbounded_faces_begin() const
  { 
    return Unbounded_face_const_iterator(_dcel().faces_begin(),
                                         _dcel().faces_end(),
                                         _Is_unbounded_face (&m_topol_traits));
  }
  
  Unbounded_face_const_iterator unbounded_faces_end() const
  {
    return Unbounded_face_const_iterator(_dcel().faces_end(),
                                         _dcel().faces_end(),
                                         _Is_unbounded_face (&m_topol_traits));
  }
  

  Vertex_handle non_const_handle (Vertex_const_handle vh)
  {
    DVertex    *p_v = (DVertex*) &(*vh);
    return (Vertex_handle (p_v));
  }

  Halfedge_handle non_const_handle (Halfedge_const_handle hh)
  {
    DHalfedge  *p_he = (DHalfedge*) &(*hh);
    return (Halfedge_handle (p_he));
  }

  Face_handle non_const_handle (Face_const_handle fh)
  {
    DFace      *p_f = (DFace*) &(*fh);
    return (Face_handle (p_f));
  }



  Vertex_handle insert_in_face_interior (const Point_2& p,
                                         Face_handle f);

  Halfedge_handle insert_in_face_interior (const X_monotone_curve_2& cv, 
                                           Face_handle f);

  Halfedge_handle insert_from_left_vertex (const X_monotone_curve_2& cv, 
                                           Vertex_handle v,
                                           Face_handle f = Face_handle());

  Halfedge_handle insert_from_left_vertex (const X_monotone_curve_2& cv,
                                           Halfedge_handle prev);

  Halfedge_handle insert_from_right_vertex (const X_monotone_curve_2& cv, 
                                            Vertex_handle v,
                                            Face_handle f = Face_handle());

  Halfedge_handle insert_from_right_vertex (const X_monotone_curve_2& cv,
                                            Halfedge_handle prev);
  
  Halfedge_handle insert_at_vertices (const X_monotone_curve_2& cv, 
                                      Vertex_handle v1, 
                                      Vertex_handle v2,
                                      Face_handle f = Face_handle());

  Halfedge_handle insert_at_vertices (const X_monotone_curve_2& cv, 
                                      Halfedge_handle h1, 
                                      Vertex_handle v2);

  Halfedge_handle insert_at_vertices (const X_monotone_curve_2 & cv,
                                      Halfedge_handle prev1, 
                                      Halfedge_handle prev2);




  Vertex_handle modify_vertex (Vertex_handle v,
                               const Point_2& p);

  Face_handle remove_isolated_vertex (Vertex_handle v);
  



  Halfedge_handle modify_edge (Halfedge_handle e, 
                               const X_monotone_curve_2& cv);

  Halfedge_handle split_edge (Halfedge_handle e,
                              const X_monotone_curve_2& cv1, 
                              const X_monotone_curve_2& cv2);

  Halfedge_handle merge_edge (Halfedge_handle e1, 
                              Halfedge_handle e2, 
                              const X_monotone_curve_2& cv);              

  Face_handle remove_edge (Halfedge_handle e,
                           bool remove_source = true,
                           bool remove_target = true);
  

protected:



  inline bool is_open(Arr_parameter_space ps_x, Arr_parameter_space ps_y)
    const
  {
    return
      (((ps_x != ARR_INTERIOR) && (m_boundary_types[ps_x] == ARR_OPEN)) ||
       ((ps_y != ARR_INTERIOR) && (m_boundary_types[ps_y] == ARR_OPEN)));
  }
  
  inline void init_boundary_types()
  {
    init_boundary_side(ARR_LEFT_BOUNDARY, Arr_left_side_tag());
    init_boundary_side(ARR_BOTTOM_BOUNDARY, Arr_bottom_side_tag());
    init_boundary_side(ARR_TOP_BOUNDARY, Arr_top_side_tag());
    init_boundary_side(ARR_RIGHT_BOUNDARY, Arr_right_side_tag());
  }

  void init_boundary_side(Arr_parameter_space ps, Arr_oblivious_side_tag)
  {
    m_boundary_types[ps] = ARR_OBLIVIOUS;
  }
    
  void init_boundary_side(Arr_parameter_space ps, Arr_open_side_tag)
  {
    m_boundary_types[ps] = ARR_OPEN;
  }

  void init_boundary_side(Arr_parameter_space ps, Arr_closed_side_tag)
  {
    m_boundary_types[ps] = ARR_CLOSED;
  }

  void init_boundary_side(Arr_parameter_space ps, Arr_contracted_side_tag)
  {
    m_boundary_types[ps] = ARR_CONTRACTION;
  }

  void init_boundary_side(Arr_parameter_space ps, 
                          Arr_identified_side_tag)
  {
    m_boundary_types[ps] = ARR_IDENTIFICATION;
  }

  Point_2 *_new_point (const Point_2& pt)
  {
    Point_2   *p_pt = m_points_alloc.allocate (1);

    m_points_alloc.construct (p_pt, pt);
    return (p_pt);
  }

  void _delete_point (Point_2& pt)
  {
    Point_2   *p_pt = &pt;

    m_points_alloc.destroy (p_pt);
    m_points_alloc.deallocate (p_pt, 1);
  }

  X_monotone_curve_2 *_new_curve (const X_monotone_curve_2& cv)
  {
    X_monotone_curve_2   *p_cv = m_curves_alloc.allocate (1);

    m_curves_alloc.construct (p_cv, cv);
    return (p_cv);
  }

  void _delete_curve (X_monotone_curve_2& cv)
  {
    X_monotone_curve_2   *p_cv = &cv;

    m_curves_alloc.destroy (p_cv);
    m_curves_alloc.deallocate (p_cv, 1);
  }



  inline Dcel& _dcel ()
  {
    return (m_topol_traits.dcel());
  }

  inline const Dcel& _dcel () const
  {
    return (m_topol_traits.dcel());
  }

  inline DVertex* _vertex (Vertex_handle vh) const
  {
    return (&(*vh));
  }

  inline const DVertex* _vertex (Vertex_const_handle vh) const
  {
    return (&(*vh));
  }

  inline DHalfedge* _halfedge (Halfedge_handle hh) const
  {
    return (&(*hh));
  }

  inline const DHalfedge* _halfedge (Halfedge_const_handle hh) const
  {
    return (&(*hh));
  }

  inline DFace* _face (Face_handle fh) const
  {
    return (&(*fh));
  }

  inline const DFace* _face (Face_const_handle fh) const
  {
    return (&(*fh));
  }



  Vertex_handle _handle_for (DVertex *v)
  {
    return (Vertex_handle (v));
  }

  Vertex_const_handle _const_handle_for (const DVertex *v) const
  {
    return (Vertex_const_handle (v));
  }

  Halfedge_handle _handle_for (DHalfedge *he)
  {
    return (Halfedge_handle (he));
  }


  Halfedge_const_handle _const_handle_for (const DHalfedge *he) const
  {
    return (Halfedge_const_handle (he));
  }

  Face_handle _handle_for (DFace *f)
  {
    return (Face_handle (f));
  }

  Face_const_handle _const_handle_for (const DFace *f) const
  {
    return (Face_const_handle (f));
  }


   
  DHalfedge* _locate_around_vertex (DVertex *v,
                                    const X_monotone_curve_2& cv,
                                    Arr_curve_end ind) const;

  unsigned int _halfedge_distance (const DHalfedge *e1,
                                   const DHalfedge *e2) const;

  Comparison_result _compare_vertices_xy (const DVertex *v1,
                                          const DVertex *v2) const
  {
    return (_compare_vertices_xy_impl(v1, v2, Are_all_sides_oblivious_tag()));

  }

  Comparison_result
  _compare_vertices_xy_impl (const DVertex *v1,
                             const DVertex *v2,
                             Arr_all_sides_oblivious_tag) const
  {
    return (m_geom_traits->compare_xy_2_object() (v1->point(), v2->point()));
  }

  Comparison_result
  _compare_vertices_xy_impl (const DVertex *v1,
                             const DVertex *v2,
                             Arr_not_all_sides_oblivious_tag) const;
  
  std::pair <const DVertex*, const DHalfedge*>
  _find_leftmost_vertex_on_open_loop (const DHalfedge *he_before,
                                      const DHalfedge *he_after,
                                      const X_monotone_curve_2& cv,
                                      bool& is_perimetric) const;

  std::pair<int, const DVertex*>
  _find_leftmost_vertex_on_closed_loop (const DHalfedge *he_anchor,
                                        bool& is_perimetric,
                                        bool& at_infinity) const;

  bool _is_inside_new_face (const DHalfedge *prev1,
                            const DHalfedge *prev2,
                            const X_monotone_curve_2& cv) const;

  void _move_outer_ccb (DFace *from_face, DFace *to_face, DHalfedge *he);

  void _move_inner_ccb (DFace *from_face, DFace *to_face, DHalfedge *he);

  void _insert_isolated_vertex (DFace *f, DVertex *v);

  void _move_isolated_vertex (DFace *from_face, DFace *to_face, DVertex *v);

  DVertex* _create_vertex (const Point_2& p);

  DVertex* _create_boundary_vertex (const X_monotone_curve_2& cv,
                                    Arr_curve_end ind,
                                    Arr_parameter_space bx,
                                    Arr_parameter_space by);

  DVertex* _place_and_set_curve_end (DFace *f,
                                     const X_monotone_curve_2& cv,
                                     Arr_curve_end ind,
                                     Arr_parameter_space bx,
                                     Arr_parameter_space by,
                                     DHalfedge **p_pred);
  
  DHalfedge* _insert_in_face_interior (const X_monotone_curve_2& cv,
                                       DFace *f,
                                       DVertex *v1, DVertex *v2,
                                       Comparison_result res);

  DHalfedge* _insert_from_vertex (const X_monotone_curve_2& cv,
                                  DHalfedge *prev,
                                  DVertex *v,
                                  Comparison_result res);

  DHalfedge* _insert_at_vertices (const X_monotone_curve_2& cv,
                                  DHalfedge *prev1, 
                                  DHalfedge *prev2,
                                  Comparison_result res,
                                  bool& new_face);

  void _relocate_in_new_face (DHalfedge *new_he);

  void _relocate_inner_ccbs_in_new_face (DHalfedge *new_he);

  void _relocate_isolated_vertices_in_new_face (DHalfedge *new_he);

  void _modify_vertex (DVertex *v, 
                       const Point_2& p);

  void _modify_edge (DHalfedge *he, 
                     const X_monotone_curve_2& cv);

  bool _are_equal (const DVertex *v,
                   const X_monotone_curve_2& cv, Arr_curve_end ind) const;

  DHalfedge* _split_edge (DHalfedge *e,
                          const Point_2& p,
                          const X_monotone_curve_2& cv1, 
                          const X_monotone_curve_2& cv2);

  DHalfedge* _split_edge (DHalfedge *e,
                          DVertex *v,
                          const X_monotone_curve_2& cv1,
                          const X_monotone_curve_2& cv2);

  DFace *_remove_edge (DHalfedge *e,
                       bool remove_source, bool remove_target);

  void _remove_vertex_if_redundant (DVertex *v, DFace *f);

  void _remove_isolated_vertex (DVertex* v);



  bool _is_valid (Vertex_const_handle v) const;

  bool _is_valid (Halfedge_const_handle he) const;

  bool _is_valid (Face_const_handle f) const;

  bool _is_outer_ccb_valid (const DOuter_ccb *oc,
                            const DHalfedge *first) const;

  bool _is_inner_ccb_valid (const DInner_ccb *ic,
                            const DHalfedge *first) const;

  bool _are_vertices_unique() const;
  
  bool _are_curves_ordered_cw_around_vertrex (Vertex_const_handle v) const;
  

protected:



  void _register_observer (Observer *p_obs)
  {
    m_observers.push_back (p_obs);
  }

  bool _unregister_observer (Observer *p_obs)
  {
    Observers_iterator   iter;
    Observers_iterator   end = m_observers.end();

    for (iter = m_observers.begin(); iter != end; ++iter)
    {
      if ((*iter) == p_obs)
      {
        // Remove the p_ob pointer from the list of observers.
        m_observers.erase (iter);
        return (true);
      }
    }

    // If we reached here, the observer was not registered.
    return (false);
  }

protected:

  /* Notify the observers on global arrangement operations: */

  void _notify_before_assign (const Self& arr)
  {
    Observers_iterator   iter;
    Observers_iterator   end = m_observers.end();

    for (iter = m_observers.begin(); iter != end; ++iter)
      (*iter)->before_assign (arr);
  }

  void _notify_after_assign ()
  {
    Observers_rev_iterator   iter;
    Observers_rev_iterator   end = m_observers.rend();

    for (iter = m_observers.rbegin(); iter != end; ++iter)
      (*iter)->after_assign();
  }

  void _notify_before_clear ()
  {
    Observers_iterator   iter;
    Observers_iterator   end = m_observers.end();

    for (iter = m_observers.begin(); iter != end; ++iter)
      (*iter)->before_clear();
  }

  void _notify_after_clear ()
  {
    Observers_rev_iterator   iter;
    Observers_rev_iterator   end = m_observers.rend();

    for (iter = m_observers.rbegin(); iter != end; ++iter)
      (*iter)->after_clear ();
  }

  void _notify_before_global_change ()
  {
    Observers_iterator   iter;

    Observers_iterator   end = m_observers.end();

    for (iter = m_observers.begin(); iter != end; ++iter)
      (*iter)->before_global_change();

  }

  void _notify_after_global_change ()
  {
    Observers_rev_iterator   iter;
    Observers_rev_iterator   end = m_observers.rend();

    for (iter = m_observers.rbegin(); iter != end; ++iter)
      (*iter)->after_global_change();
  }

  /* Notify the observers on local changes in the arrangement: */

  void _notify_before_create_vertex (const Point_2& p)
  {
    Observers_iterator   iter;
    Observers_iterator   end = m_observers.end();

    for (iter = m_observers.begin(); iter != end; ++iter)
      (*iter)->before_create_vertex (p);
  }

  void _notify_after_create_vertex (Vertex_handle v)
  {
    Observers_rev_iterator   iter;
    Observers_rev_iterator   end = m_observers.rend();

    for (iter = m_observers.rbegin(); iter != end; ++iter)
      (*iter)->after_create_vertex (v);
  }

  void _notify_before_create_boundary_vertex (const X_monotone_curve_2& cv,
                                              Arr_curve_end ind,
                                              Arr_parameter_space bx,
                                              Arr_parameter_space by)
  {
    Observers_iterator   iter;
    Observers_iterator   end = m_observers.end();

    for (iter = m_observers.begin(); iter != end; ++iter)
      (*iter)->before_create_boundary_vertex (cv, ind, bx, by);
  }

  void _notify_after_create_boundary_vertex (Vertex_handle v)
  {
    Observers_rev_iterator   iter;
    Observers_rev_iterator   end = m_observers.rend();

    for (iter = m_observers.rbegin(); iter != end; ++iter)
      (*iter)->after_create_boundary_vertex (v);
  }

  void _notify_before_create_edge (const X_monotone_curve_2& c,
                                   Vertex_handle v1, Vertex_handle v2)
  {
    Observers_iterator   iter;
    Observers_iterator   end = m_observers.end();

    for (iter = m_observers.begin(); iter != end; ++iter)
      (*iter)->before_create_edge (c, v1, v2);
  }

  void _notify_after_create_edge (Halfedge_handle e)
  {
    Observers_rev_iterator   iter;
    Observers_rev_iterator   end = m_observers.rend();

    for (iter = m_observers.rbegin(); iter != end; ++iter)
      (*iter)->after_create_edge (e);
  }

  void _notify_before_modify_vertex (Vertex_handle v,
                                     const Point_2& p)
  {
    Observers_iterator   iter;
    Observers_iterator   end = m_observers.end();

    for (iter = m_observers.begin(); iter != end; ++iter)
      (*iter)->before_modify_vertex (v, p);
  }

  void _notify_after_modify_vertex (Vertex_handle v)
  {
    Observers_rev_iterator   iter;
    Observers_rev_iterator   end = m_observers.rend();

    for (iter = m_observers.rbegin(); iter != end; ++iter)
      (*iter)->after_modify_vertex (v);
  }

  void _notify_before_modify_edge (Halfedge_handle e,
                                   const X_monotone_curve_2& c)
  {
    Observers_iterator   iter;
    Observers_iterator   end = m_observers.end();

    for (iter = m_observers.begin(); iter != end; ++iter)
      (*iter)->before_modify_edge (e, c);
  }

  void _notify_after_modify_edge (Halfedge_handle e)
  {
    Observers_rev_iterator   iter;
    Observers_rev_iterator   end = m_observers.rend();

    for (iter = m_observers.rbegin(); iter != end; ++iter)
      (*iter)->after_modify_edge (e);
  }

  void _notify_before_split_edge (Halfedge_handle e,
                                  Vertex_handle v,
                                  const X_monotone_curve_2& c1,
                                  const X_monotone_curve_2& c2)
  {
    Observers_iterator   iter;
    Observers_iterator   end = m_observers.end();

    for (iter = m_observers.begin(); iter != end; ++iter)
      (*iter)->before_split_edge (e, v, c1, c2);
  }

  void _notify_after_split_edge (Halfedge_handle e1,
                                 Halfedge_handle e2)
  {
    Observers_rev_iterator   iter;
    Observers_rev_iterator   end = m_observers.rend();

    for (iter = m_observers.rbegin(); iter != end; ++iter)
      (*iter)->after_split_edge (e1, e2);
  }

  void _notify_before_split_fictitious_edge (Halfedge_handle e,
                                             Vertex_handle v)
  {
    Observers_iterator   iter;
    Observers_iterator   end = m_observers.end();

    for (iter = m_observers.begin(); iter != end; ++iter)
      (*iter)->before_split_fictitious_edge (e, v);
  }

  void _notify_after_split_fictitious_edge (Halfedge_handle e1,
                                            Halfedge_handle e2)
  {
    Observers_rev_iterator   iter;
    Observers_rev_iterator   end = m_observers.rend();

    for (iter = m_observers.rbegin(); iter != end; ++iter)
      (*iter)->after_split_fictitious_edge (e1, e2);
  }

  void _notify_before_split_face (Face_handle f,
                                  Halfedge_handle e)
  {
    Observers_iterator   iter;
    Observers_iterator   end = m_observers.end();

    for (iter = m_observers.begin(); iter != end; ++iter)
      (*iter)->before_split_face (f, e);
  }

  void _notify_after_split_face (Face_handle f,
                                 Face_handle new_f,
                                 bool is_hole)
  {
    Observers_rev_iterator   iter;
    Observers_rev_iterator   end = m_observers.rend();

    for (iter = m_observers.rbegin(); iter != end; ++iter)
      (*iter)->after_split_face (f, new_f, is_hole);
  }

  void _notify_before_split_outer_ccb (Face_handle f,
                                       Ccb_halfedge_circulator h,
                                       Halfedge_handle e)
  {
    Observers_iterator   iter;
    Observers_iterator   end = m_observers.end();

    for (iter = m_observers.begin(); iter != end; ++iter)
      (*iter)->before_split_outer_ccb (f, h, e);
  }

  void _notify_after_split_outer_ccb (Face_handle f,
                                      Ccb_halfedge_circulator h1,
                                      Ccb_halfedge_circulator h2)
  {
    Observers_rev_iterator   iter;
    Observers_rev_iterator   end = m_observers.rend();

    for (iter = m_observers.rbegin(); iter != end; ++iter)
      (*iter)->after_split_outer_ccb (f, h1, h2);
  }

  void _notify_before_split_inner_ccb (Face_handle f,
                                       Ccb_halfedge_circulator h,
                                       Halfedge_handle e)
  {
    Observers_iterator   iter;
    Observers_iterator   end = m_observers.end();

    for (iter = m_observers.begin(); iter != end; ++iter)
      (*iter)->before_split_inner_ccb (f, h, e);
  }

  void _notify_after_split_inner_ccb (Face_handle f,
                                      Ccb_halfedge_circulator h1,
                                      Ccb_halfedge_circulator h2)
  {
    Observers_rev_iterator   iter;
    Observers_rev_iterator   end = m_observers.rend();

    for (iter = m_observers.rbegin(); iter != end; ++iter)
      (*iter)->after_split_inner_ccb (f, h1, h2);
  }

  void _notify_before_add_outer_ccb (Face_handle f,
                                     Halfedge_handle e)
  {
    Observers_iterator   iter;
    Observers_iterator   end = m_observers.end();

    for (iter = m_observers.begin(); iter != end; ++iter)
      (*iter)->before_add_outer_ccb (f, e);
  }

  void _notify_after_add_outer_ccb (Ccb_halfedge_circulator h)
  {
    Observers_rev_iterator   iter;
    Observers_rev_iterator   end = m_observers.rend();

    for (iter = m_observers.rbegin(); iter != end; ++iter)
      (*iter)->after_add_outer_ccb (h);
  }

  void _notify_before_add_inner_ccb (Face_handle f,
                                     Halfedge_handle e)
  {
    Observers_iterator   iter;
    Observers_iterator   end = m_observers.end();

    for (iter = m_observers.begin(); iter != end; ++iter)
      (*iter)->before_add_inner_ccb (f, e);
  }

  void _notify_after_add_inner_ccb (Ccb_halfedge_circulator h)
  {
    Observers_rev_iterator   iter;
    Observers_rev_iterator   end = m_observers.rend();

    for (iter = m_observers.rbegin(); iter != end; ++iter)
      (*iter)->after_add_inner_ccb (h);
  }

  void _notify_before_add_isolated_vertex (Face_handle f,
                                           Vertex_handle v)
  {
    Observers_iterator   iter;
    Observers_iterator   end = m_observers.end();

    for (iter = m_observers.begin(); iter != end; ++iter)
      (*iter)->before_add_isolated_vertex (f, v);
  }

  void _notify_after_add_isolated_vertex (Vertex_handle v)
  {
    Observers_rev_iterator   iter;
    Observers_rev_iterator   end = m_observers.rend();

    for (iter = m_observers.rbegin(); iter != end; ++iter)
      (*iter)->after_add_isolated_vertex (v);
  }

  void _notify_before_merge_edge (Halfedge_handle e1,
                                  Halfedge_handle e2,
                                  const X_monotone_curve_2& c)
  {
    Observers_iterator   iter;
    Observers_iterator   end = m_observers.end();

    for (iter = m_observers.begin(); iter != end; ++iter)
      (*iter)->before_merge_edge (e1, e2, c);
  }

  void _notify_after_merge_edge (Halfedge_handle e)
  {
    Observers_rev_iterator   iter;
    Observers_rev_iterator   end = m_observers.rend();

    for (iter = m_observers.rbegin(); iter != end; ++iter)
      (*iter)->after_merge_edge (e);
  }

  void _notify_before_merge_fictitious_edge (Halfedge_handle e1,
                                             Halfedge_handle e2)
  {
    Observers_iterator   iter;
    Observers_iterator   end = m_observers.end();

    for (iter = m_observers.begin(); iter != end; ++iter)
      (*iter)->before_merge_fictitious_edge (e1, e2);
  }

  void _notify_after_merge_fictitious_edge (Halfedge_handle e)
  {
    Observers_rev_iterator   iter;
    Observers_rev_iterator   end = m_observers.rend();

    for (iter = m_observers.rbegin(); iter != end; ++iter)
      (*iter)->after_merge_fictitious_edge (e);
  }

  void _notify_before_merge_face (Face_handle f1,
                                  Face_handle f2,
                                  Halfedge_handle e)
  {
    Observers_iterator   iter;
    Observers_iterator   end = m_observers.end();

    for (iter = m_observers.begin(); iter != end; ++iter)
      (*iter)->before_merge_face (f1, f2, e);
  }

  void _notify_after_merge_face (Face_handle f)
  {
    Observers_rev_iterator   iter;
    Observers_rev_iterator   end = m_observers.rend();

    for (iter = m_observers.rbegin(); iter != end; ++iter)
      (*iter)->after_merge_face (f);
  }

  void _notify_before_merge_outer_ccb (Face_handle f,
                                       Ccb_halfedge_circulator h1,
                                       Ccb_halfedge_circulator h2,
                                       Halfedge_handle e)
  {
    Observers_iterator   iter;
    Observers_iterator   end = m_observers.end();

    for (iter = m_observers.begin(); iter != end; ++iter)
      (*iter)->before_merge_outer_ccb (f, h1, h2, e);
  }

  void _notify_after_merge_outer_ccb (Face_handle f,
                                      Ccb_halfedge_circulator h)
  {
    Observers_rev_iterator   iter;
    Observers_rev_iterator   end = m_observers.rend();

    for (iter = m_observers.rbegin(); iter != end; ++iter)
      (*iter)->after_merge_outer_ccb (f, h);
  }

  void _notify_before_merge_inner_ccb (Face_handle f,
                                       Ccb_halfedge_circulator h1,
                                       Ccb_halfedge_circulator h2,
                                       Halfedge_handle e)
  {
    Observers_iterator   iter;
    Observers_iterator   end = m_observers.end();

    for (iter = m_observers.begin(); iter != end; ++iter)
      (*iter)->before_merge_inner_ccb (f, h1, h2, e);
  }

  void _notify_after_merge_inner_ccb (Face_handle f,
                                      Ccb_halfedge_circulator h)
  {
    Observers_rev_iterator   iter;
    Observers_rev_iterator   end = m_observers.rend();

    for (iter = m_observers.rbegin(); iter != end; ++iter)
      (*iter)->after_merge_inner_ccb (f, h);
  }

  void _notify_before_move_outer_ccb (Face_handle from_f,
                                      Face_handle to_f,
                                      Ccb_halfedge_circulator h)
  {
    Observers_iterator   iter;
    Observers_iterator   end = m_observers.end();

    for (iter = m_observers.begin(); iter != end; ++iter)
      (*iter)->before_move_outer_ccb (from_f, to_f, h);
  }

  void _notify_after_move_outer_ccb (Ccb_halfedge_circulator h)
  {
    Observers_rev_iterator   iter;
    Observers_rev_iterator   end = m_observers.rend();

    for (iter = m_observers.rbegin(); iter != end; ++iter)
      (*iter)->after_move_outer_ccb (h);
  }

  void _notify_before_move_inner_ccb (Face_handle from_f,
                                      Face_handle to_f,
                                      Ccb_halfedge_circulator h)
  {
    Observers_iterator   iter;
    Observers_iterator   end = m_observers.end();

    for (iter = m_observers.begin(); iter != end; ++iter)
      (*iter)->before_move_inner_ccb (from_f, to_f, h);
  }

  void _notify_after_move_inner_ccb (Ccb_halfedge_circulator h)
  {
    Observers_rev_iterator   iter;
    Observers_rev_iterator   end = m_observers.rend();

    for (iter = m_observers.rbegin(); iter != end; ++iter)
      (*iter)->after_move_inner_ccb (h);
  }

  void _notify_before_move_isolated_vertex (Face_handle from_f,
                                            Face_handle to_f,
                                            Vertex_handle v)
  {
    Observers_iterator   iter;
    Observers_iterator   end = m_observers.end();

    for (iter = m_observers.begin(); iter != end; ++iter)
      (*iter)->before_move_isolated_vertex (from_f, to_f, v);
  }


  void _notify_after_move_isolated_vertex (Vertex_handle v)
  {
    Observers_rev_iterator   iter;
    Observers_rev_iterator   end = m_observers.rend();

    for (iter = m_observers.rbegin(); iter != end; ++iter)
      (*iter)->after_move_isolated_vertex (v);
  }

  void _notify_before_remove_vertex (Vertex_handle v)
  {
    Observers_iterator   iter;
    Observers_iterator   end = m_observers.end();

    for (iter = m_observers.begin(); iter != end; ++iter)
      (*iter)->before_remove_vertex (v);
  }

  void _notify_after_remove_vertex ()
  {
    Observers_rev_iterator   iter;
    Observers_rev_iterator   end = m_observers.rend();

    for (iter = m_observers.rbegin(); iter != end; ++iter)
      (*iter)->after_remove_vertex ();
  }

  void _notify_before_remove_edge (Halfedge_handle e)
  {
    Observers_iterator   iter;
    Observers_iterator   end = m_observers.end();

    for (iter = m_observers.begin(); iter != end; ++iter)
      (*iter)->before_remove_edge (e);
  }

  void _notify_after_remove_edge ()
  {
    Observers_rev_iterator   iter;
    Observers_rev_iterator   end = m_observers.rend();

    for (iter = m_observers.rbegin(); iter != end; ++iter)
      (*iter)->after_remove_edge ();
  }

  void _notify_before_remove_outer_ccb (Face_handle f,
                                        Ccb_halfedge_circulator h)
  {
    Observers_iterator   iter;
    Observers_iterator   end = m_observers.end();

    for (iter = m_observers.begin(); iter != end; ++iter)
      (*iter)->before_remove_outer_ccb (f, h);
  }

  void _notify_after_remove_outer_ccb (Face_handle f)
  {
    Observers_rev_iterator   iter;
    Observers_rev_iterator   end = m_observers.rend();

    for (iter = m_observers.rbegin(); iter != end; ++iter)
      (*iter)->after_remove_outer_ccb (f);
  }

  void _notify_before_remove_inner_ccb (Face_handle f,
                                        Ccb_halfedge_circulator h)
  {
    Observers_iterator   iter;
    Observers_iterator   end = m_observers.end();

    for (iter = m_observers.begin(); iter != end; ++iter)
      (*iter)->before_remove_inner_ccb (f, h);
  }

  void _notify_after_remove_inner_ccb (Face_handle f)
  {
    Observers_rev_iterator   iter;
    Observers_rev_iterator   end = m_observers.rend();

    for (iter = m_observers.rbegin(); iter != end; ++iter)
      (*iter)->after_remove_inner_ccb (f);
  }

};

//-----------------------------------------------------------------------------
// Declarations of the various global insertion and removal functions.
//-----------------------------------------------------------------------------

// In some compilers there is a template deduction disambiguity between this
// function and the following function receiving two InputIterator.
// For now the solution is to add a dummy variable at the end (referring
// to point-location). Maybe the proper solution is to use boost::enable_if
// together with appropriate tag.
template <class GeomTraits, class TopTraits, class Curve, class PointLocation>
void insert (Arrangement_on_surface_2<GeomTraits, TopTraits>& arr,
             const Curve& c, const PointLocation& pl,
             typename PointLocation::Point_2* = 0);

template <class GeomTraits, class TopTraits, class Curve>
void insert (Arrangement_on_surface_2<GeomTraits, TopTraits>& arr,
                   const Curve& c);

template <class GeomTraits, class TopTraits, class InputIterator>
void insert (Arrangement_on_surface_2<GeomTraits, TopTraits>& arr,
                    InputIterator begin, InputIterator end);

template <class GeomTraits, class TopTraits>
void insert (Arrangement_on_surface_2<GeomTraits, TopTraits>& arr,
             const typename GeomTraits::X_monotone_curve_2& c,
             const Object& obj);

template <class GeomTraits, class TopTraits, class PointLocation>
typename Arrangement_on_surface_2<GeomTraits, TopTraits>::Halfedge_handle
insert_non_intersecting_curve
(Arrangement_on_surface_2<GeomTraits, TopTraits>& arr,
 const typename GeomTraits::X_monotone_curve_2& c,
 const PointLocation& pl);

template <class GeomTraits, class TopTraits>
typename Arrangement_on_surface_2<GeomTraits, TopTraits>::Halfedge_handle
insert_non_intersecting_curve
(Arrangement_on_surface_2<GeomTraits, TopTraits>& arr,
 const typename GeomTraits::X_monotone_curve_2& c);

template <class GeomTraits, class TopTraits, class InputIterator>
void insert_non_intersecting_curves 
(Arrangement_on_surface_2<GeomTraits, TopTraits>& arr,
 InputIterator begin, InputIterator end);

template <class GeomTraits, class TopTraits>
typename Arrangement_on_surface_2<GeomTraits, TopTraits>::Face_handle
remove_edge (Arrangement_on_surface_2<GeomTraits, TopTraits>& arr,
             typename Arrangement_on_surface_2<GeomTraits,
                                               TopTraits>::Halfedge_handle e);

template <class GeomTraits, class TopTraits, class PointLocation>
typename Arrangement_on_surface_2<GeomTraits, TopTraits>::Vertex_handle
insert_point (Arrangement_on_surface_2<GeomTraits, TopTraits>& arr,
              const typename GeomTraits::Point_2& p,
              const PointLocation& pl);

template <class GeomTraits, class TopTraits>
typename Arrangement_on_surface_2<GeomTraits, TopTraits>::Vertex_handle
insert_point (Arrangement_on_surface_2<GeomTraits, TopTraits>& arr,
              const typename GeomTraits::Point_2& p);

template <class GeomTraits, class TopTraits>
bool
remove_vertex (Arrangement_on_surface_2<GeomTraits, TopTraits>& arr,
               typename Arrangement_on_surface_2<GeomTraits,
                                                 TopTraits>::Vertex_handle v);


template <class GeomTraits, class TopTraits>
bool is_valid (const Arrangement_on_surface_2<GeomTraits, TopTraits>& arr);

template <class GeomTraits, class TopTraits, 
  class OutputIterator, class PointLocation>
OutputIterator zone (Arrangement_on_surface_2<GeomTraits, TopTraits>& arr, 
                     const typename GeomTraits::X_monotone_curve_2& c,
                     OutputIterator oi,
                     const PointLocation& pl);

template <class GeomTraits, class TopTraits, class OutputIterator>
OutputIterator zone (Arrangement_on_surface_2<GeomTraits, TopTraits>& arr, 
                     const typename GeomTraits::X_monotone_curve_2& c,
                     OutputIterator oi);

template <class GeomTraits, class TopTraits, class Curve, class PointLocation>
bool do_intersect (Arrangement_on_surface_2<GeomTraits, TopTraits>& arr, 
                   const Curve& c, const PointLocation& pl);

template <class GeomTraits, class TopTraits, class Curve>
bool do_intersect (Arrangement_on_surface_2<GeomTraits, TopTraits>& arr, 
                   const Curve& c);


CGAL_END_NAMESPACE

// The function definitions can be found under:
#include <CGAL/Arrangement_2/Arrangement_on_surface_2_impl.h>
#include <CGAL/Arrangement_2/Arrangement_on_surface_2_global.h>

#endif