sort.h

很多二维 三维几何计算算法 C++ 类库

// Copyright (c) 2005  Stanford University (USA).
// All rights reserved.
//
// This file is part of CGAL (www.cgal.org); you can redistribute it and/or
// modify it under the terms of the GNU Lesser General Public License as
// published by the Free Software Foundation; version 2.1 of the License.
// See the file LICENSE.LGPL 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.3-branch/Kinetic_data_structures/include/CGAL/Kinetic/Sort.h $
// $Id: Sort.h 37692 2007-03-29 19:36:13Z drussel $
// 
//
// Author(s)     : Daniel Russel <[e-mail]>

#ifndef CGAL_KINETIC_TESTING_SORT_H
#define CGAL_KINETIC_TESTING_SORT_H
#include <CGAL/Kinetic/basic.h>
#include <CGAL/Kinetic/Active_objects_listener_helper.h>
#include <CGAL/Kinetic/Ref_counted.h>
#include <CGAL/Kinetic/internal/debug_counters.h>
#include <CGAL/Kinetic/Simulator_kds_listener.h>
#include <CGAL/Kinetic/Sort_visitor_base.h>
#include <CGAL/Kinetic/Event_base.h>
#include <algorithm>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <set>

CGAL_KINETIC_BEGIN_NAMESPACE

template <class KDS, class It, class RE>
class Swap_event;

struct Empty_data {};

//! A simple KDS which maintains objects sorted by their x coordinate
/*!  This does not use Simple_kds_base for now irrelevant
  reasons. Ditto for the lack of protection of any of the fields. The
  code is designed to be read, so read it if you want to figure out
  what is going on.
*/
template <class Traits, class Visitor=Sort_visitor_base> class Sort:
// for ref counted pointers
  public Ref_counted<Sort< Traits, Visitor> >
{
  // for later, please ignore
  typedef typename Traits::Active_points_1_table TTable;
  typedef typename Traits::Kinetic_kernel::Compare_x_1 KLess;
  typedef typename Traits::Instantaneous_kernel::Compare_x_1 IComp;
 
  //typedef typename Traits::Instantaneous_kernel::Compare_x_1 ILess;

  typedef Sort<Traits, Visitor> This;
  // The way the Simulator represents time.
  typedef typename Traits::Simulator::Time Time;
  // The way the Simulator represents time.
  typedef typename Traits::Simulator::NT NT;
  // A label for a moving primitive in the MovingObjectTable
  typedef typename TTable::Key Object_key;


  // STL algorithms want less rather than compare. So we need to convert.
  struct ILess {
    ILess(IComp ic): ic_(ic){}
  
    bool operator()(Object_key a, Object_key b) const {
      bool ret=( ic_(a,b) == CGAL::SMALLER);
      return ret;
    }
    IComp ic_;
  };

  // A label for a certificate so it can be descheduled.
  typedef typename Traits::Simulator::Event_key Event_key;
  // To shorten the names. Use the default choice for the static kernel.
  typedef typename Traits::Instantaneous_kernel Instantaneous_kernel;
  // The table containing the points
  typedef TTable Active_objects_table;
  // the comparators, one for static and one for instantaneous
  typedef KLess Kinetic_less;
  typedef ILess Instantaneous_less;
  struct OD {
    OD(Object_key k): key_(k){}
    Object_key object() const {return key_;}
    Event_key event() const {return event_;}
    void set_event(Event_key k) {
      event_= k;
    }
    operator Object_key() const {
      return key_;
    }
    void swap(OD &o) {
      std::swap(key_, o.key_);
    }
    Object_key key_;
    Event_key event_;
  };
  // this is used to identify pairs of objects in the list
  typedef typename std::list<OD>::iterator iterator;
  // The certificate generator
  /*struct Less {
    typedef typename Traits::Kinetic_kernel::Is_less_x_1 Less_x;
    Less(Less_x x): less_(x){}
    bool operator()(const OD &a, const OD &b) const {
      return less_(a.key(), b.key());
    }
    Less less_;
    }*/
  
  typedef Swap_event<This,iterator, typename KLess::result_type> Event;
  friend class Swap_event<This,iterator, typename KLess::result_type>;
  // Redirects the Simulator notifications to function calls
  typedef typename CGAL::Kinetic::
  Simulator_kds_listener<typename Traits::Simulator::Listener,
			 This> Sim_listener;
  // Redirects the MovingObjectTable notifications to function calls
  typedef typename CGAL::Kinetic::
  Active_objects_listener_helper<typename Active_objects_table::Listener,
				 This> MOT_listener;
public:
  
  // Register this KDS with the MovingObjectTable and the Simulator
  Sort(Traits tr, Visitor v=Visitor()/*, 
       typedef Active_objects_table::Handle aot,
       Kinetic_less kless=tr.kinetic_kernel_object().is_less_x_1_object(),
       Instantaneous_less iless*/): compare_(tr.kinetic_kernel_object().compare_x_1_object()),
				    ik_(tr.instantaneous_kernel_object()),
				    iless_(ik_.compare_x_1_object()), v_(v),
				    aot_(tr.active_points_1_table_handle()),
				    simulator_(tr.simulator_handle()){
    sim_listener_= Sim_listener(simulator_, this);
    mot_listener_= MOT_listener(aot_, this);
    wrote_objects_= false;
  }

  const Visitor& visitor() const {
    return v_;
  }
  Visitor& visitor() {
    return v_;
  }

  /*Traits &traits() {
    return tr_;
  }
  const Traits &traits() const {
    return tr_;
    }*/

  typedef iterator Vertex_handle;

  /* Insert k and update the affected certificates. std::upper_bound
     returns the first place where an item can be inserted in a sorted
     list. Called by the MOT_listener.*/
  iterator insert(Object_key k) {
    NT nt= simulator_->next_time_representable_as_nt();
    simulator_->set_current_time(nt);
    ik_.set_time(nt);
    iterator it = std::upper_bound(sorted_.begin(), sorted_.end(),
				   k, iless_);
    CGAL_KINETIC_LOG(LOG_LOTS, "\nInserting " << k);
    if (it != sorted_.end()) {
      CGAL_KINETIC_LOG(LOG_LOTS, " before " << it->object() <<std::endl;); 
    } else {
      CGAL_KINETIC_LOG(LOG_LOTS, " before end" <<std::endl;); 
    }
    /*if (it != sorted_.end()) {
      v_.remove_edge(prior(it), it);
      }*/
    v_.pre_insert_vertex(k);
    sorted_.insert(it, OD(k));


    rebuild_certificate(prior(it)); 
    //v_.create_edge(prior(it), it);
    if (prior(it) != sorted_.begin()) {
      rebuild_certificate(prior(prior(it)));
      //v_.create_edge(prior(prior(it)), prior(it));
    }

    v_.post_insert_vertex(prior(it));
    CGAL_KINETIC_LOG_WRITE(LOG_LOTS, write(LOG_STREAM));
    CGAL_KINETIC_LOG(LOG_LOTS, std::endl);
    return it;
    //write(std::cout);
  }

  /* Rebuild the certificate for the pair of points *it and *(++it).
     If there is a previous certificate there, deschedule it.*/
  void rebuild_certificate(const iterator it) {
    CGAL_KINETIC_LOG(LOG_LOTS, "Building certifiate for " << it->object() << " and " << next(it)->object()<< std::endl);
    CGAL_precondition(it != sorted_.end());
    if (it->event() != Event_key()) {
      simulator_->delete_event(it->event());
      it->set_event(Event_key());
    }
    if (next(it) == sorted_.end()) return;
    //Less less=kk_.less_x_1_object();
    typename KLess::result_type s
      = compare_( aot_->at(next(it)->object()), aot_->at(it->object()), simulator_->current_time(),
		 simulator_->end_time());
    // the Simulator will detect if the failure time is at infinity
    if (s.will_fail()) {
      Time t= s.failure_time();
      s.pop_failure_time();
      Event e(it, this,s);
      it->set_event( simulator_->new_event(t, e));
    } else {
      it->set_event( simulator_->null_event());
    }
    //} else events_[*it]= simulator_->null_event();
  }



  /* Swap the pair of objects with *it as the first element.  The old
     solver is used to compute the next root between the two points
     being swapped. This method is called by an Event object.*/
  void swap(iterator it, typename KLess::result_type &s) {
    CGAL_KINETIC_LOG(LOG_LOTS, "Swapping " << it->object() << " and " << next(it)->object() << std::endl);
    CGAL_KINETIC_LOG_WRITE(LOG_LOTS, write(LOG_STREAM));
    v_.pre_swap(it, next(it));
    it->set_event(Event_key());
    iterator n= next(it);
    if (n->event() != Event_key()) {
      simulator_->delete_event(n->event());
      n->set_event(Event_key());
    }