SPAR/AIModule/BWTA/vendors/CGAL/CGAL/Sweep_line_2/Sweep_line_subcurve.h

Go to the documentation of this file.

// Copyright (c) 2005  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/Sweep_line_2/Sweep_line_subcurve.h $
// $Id: Sweep_line_subcurve.h 41325 2007-12-26 15:39:40Z golubevs $
// 
//
// Author(s)     : Tali Zvi <talizvi@post.tau.ac.il>,
//                 Baruch Zukerman <baruchzu@post.tau.ac.il>
//                 Ron Wein <wein@post.tau.ac.il>

#ifndef CGAL_SWEEP_LINE_SUBCURVE_H
#define CGAL_SWEEP_LINE_SUBCURVE_H

#include <CGAL/Sweep_line_2/Sweep_line_functors.h>
#include <CGAL/Sweep_line_2/Sweep_line_event.h>
#include <CGAL/Multiset.h>
#include <CGAL/assertions.h>

CGAL_BEGIN_NAMESPACE

template<class Traits_>
class Sweep_line_subcurve
{
public:

  typedef Traits_                                    Traits_2;
  typedef typename Traits_2::Point_2                 Point_2;
  typedef typename Traits_2::X_monotone_curve_2      X_monotone_curve_2;

  typedef Sweep_line_subcurve<Traits_2>              Self;
  typedef Curve_comparer<Traits_2, Self>             Compare_curves;
  typedef Multiset<Self*,
                   Compare_curves,
                   CGAL_ALLOCATOR(int)>              Status_line;
  typedef typename Status_line::iterator             Status_line_iterator;

  typedef Sweep_line_event<Traits_2, Self>           Event;

protected:

  // Data members:

  X_monotone_curve_2   m_lastCurve;  // The portion of the curve that lies to
                                     // the right of the last event point 
                                     // that occured on the curve.

  Event            *m_left_event;  // The event associated with the left end.
  Event            *m_right_event; // The event associated with the right end
  
  Status_line_iterator m_hint;     // The location of the subcurve in the
                                   // status line (the Y-structure).

  Self             *m_orig_subcurve1; // The overlapping hierarchy
  Self             *m_orig_subcurve2; // (relevant only in case of overlaps).

public:

  Sweep_line_subcurve () :
    m_orig_subcurve1 (NULL),
    m_orig_subcurve2 (NULL)
  {}

  Sweep_line_subcurve (const X_monotone_curve_2 &curve) :
    m_lastCurve (curve),
    m_orig_subcurve1 (NULL),
    m_orig_subcurve2 (NULL)
  {}

  void init (const X_monotone_curve_2 &curve)
  {
    m_lastCurve = curve;
  }

  ~Sweep_line_subcurve()
  {}

  const X_monotone_curve_2& last_curve () const
  { 
    return (m_lastCurve); 
  }

  X_monotone_curve_2& last_curve()
  { 
    return (m_lastCurve); 
  }

  void set_last_curve (const X_monotone_curve_2 &cv)
  { 
    m_lastCurve = cv; 
  }

  template<class SweepEvent>
  bool is_end_point (const SweepEvent* event) const
  {
    return (m_right_event == (Event*)event);
  }
 
  Event* left_event() const
  {
    return (m_left_event);
  }

  Event* right_event() const
  {
    return (m_right_event);
  }

  template<class SweepEvent>
  void set_left_event (SweepEvent* event)
  {
    m_left_event =(Event*)event;
  }

  template<class SweepEvent>
  void set_right_event(SweepEvent* event)
  {
    m_right_event = (Event*)event;
  }

  Status_line_iterator hint() const 
  {
    return (m_hint);
  }

  void set_hint(Status_line_iterator hint) 
  {
    m_hint = hint;
  }

  Self* originating_subcurve1()
  {
    return (m_orig_subcurve1);
  }

  Self* originating_subcurve2()
  {
    return (m_orig_subcurve2);
  }

  void set_originating_subcurve1 (Self* orig_subcurve1)
  {
    m_orig_subcurve1 = orig_subcurve1;
  }

  void set_originating_subcurve2 (Self* orig_subcurve2)
  {
    m_orig_subcurve2 = orig_subcurve2;
  }

  template <class OutputIterator>
  OutputIterator all_leaves (OutputIterator oi)
  {
    if (m_orig_subcurve1 == NULL)
    {
      *oi = this;
      ++oi;
      return (oi);
    }

    oi = m_orig_subcurve1->all_leaves (oi);
    oi = m_orig_subcurve2->all_leaves (oi);
    return (oi);
  }

  template <class OutputIterator>
  OutputIterator all_nodes (OutputIterator oi)
  {
    *oi = this;
    ++oi;

    if (m_orig_subcurve1 == NULL)
      return (oi);

    oi = m_orig_subcurve1->get_all_inner_nodes (oi);
    oi = m_orig_subcurve2->get_all_inner_nodes (oi);
    return (oi);
  }

  bool is_inner_node (Self *s)
  {
    if (this == s)
      return (true);

    if (m_orig_subcurve1 == NULL)
      return (false);

    return (m_orig_subcurve1->is_inner_node (s) ||
            m_orig_subcurve2->is_inner_node (s));
  }

  bool is_leaf (Self* s)
  {
    if (m_orig_subcurve1 == NULL)
      return (this == s);

    return (m_orig_subcurve1->is_leaf (s) ||
            m_orig_subcurve2->is_leaf (s));
  }

  bool has_same_leaves (Self *s)
  {
    std::list<Self*>   my_leaves;
    std::list<Self*>   other_leaves;
    
    this->all_leaves (std::back_inserter (my_leaves));
    s->all_leaves (std::back_inserter (other_leaves));

    typename std::list<Self*>::iterator  iter;

    for(iter = my_leaves.begin(); iter != my_leaves.end(); ++iter)
    {
      if (std::find(other_leaves.begin(), other_leaves.end(), *iter) ==
          other_leaves.end())
        return (false);
    }

    for(iter = other_leaves.begin(); iter != other_leaves.end(); ++iter)
    {
      if (std::find(my_leaves.begin(), my_leaves.end(), *iter) ==
          my_leaves.end())
        return (false);
    }

    return (true);
  }

  bool has_common_leaf (Self *s)
  {
    std::list<Self*>   my_leaves;
    std::list<Self*>   other_leaves;
    
    this->all_leaves (std::back_inserter (my_leaves));
    s->all_leaves (std::back_inserter (other_leaves));

    typename std::list<Self*>::iterator  iter;

    for (iter = my_leaves.begin(); iter != my_leaves.end(); ++iter)
    {
      if (std::find(other_leaves.begin(), other_leaves.end(), *iter) !=
          other_leaves.end())
        return (true);
    }
    return (false);
  }

  template <class OutputIterator>
  OutputIterator distinct_nodes(Self *s, OutputIterator oi)
  {
    if (m_orig_subcurve1 == NULL)
    {
      if (s->is_leaf(this))
      {
        *oi = this;
        ++oi;
      }
      return (oi);
    }

    if (! s->is_inner_node (m_orig_subcurve1))
    {
      *oi = m_orig_subcurve1;
      ++oi;
    }
    else
    {
      oi = m_orig_subcurve1->distinct_nodes (s, oi);
    }

    if (! s->is_inner_node (m_orig_subcurve2))
    {
      *oi = m_orig_subcurve2;
      ++oi;
    }
    else
    {
      oi = m_orig_subcurve2->distinct_nodes (s, oi);
    }

    return (oi);
  }

  unsigned int overlap_depth()
  {
    if (m_orig_subcurve1 == NULL)
      return (1);

    unsigned int   depth1 = m_orig_subcurve1->overlap_depth();
    unsigned int   depth2 = m_orig_subcurve2->overlap_depth();

    if (depth1 > depth2)
      return (depth1 + 1);
    else
      return (depth2 + 1);
  }
 
#ifdef CGAL_SL_VERBOSE
  void Print() const;
#endif
};

#ifdef CGAL_SL_VERBOSE
  template<class Traits>
  void Sweep_line_subcurve<Traits>::Print() const
  {
    std::cout << "Curve " << this 
              << "  (" << m_lastCurve << ") " << std::endl;
  }
#endif

CGAL_END_NAMESPACE

#endif