sort.h

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

    it->swap(*n);
    
    CGAL_KINETIC_LOG(LOG_LOTS, "Updating next certificate " << std::endl);
    if (n != sorted_.end()) {
      rebuild_certificate(n);
    }
    CGAL_KINETIC_LOG(LOG_LOTS, "Updating middle certificate " << std::endl);
    if (s.will_fail()) {
      Time t= s.failure_time(); s.pop_failure_time();
      it->set_event(simulator_->new_event(t, Event(it, this,s)));
    } else {
      it->set_event(simulator_->null_event());
    }
    
   
    CGAL_KINETIC_LOG(LOG_LOTS, "Updating prev certificate " << std::endl);
    if (it != sorted_.begin()) {
      rebuild_certificate(prior(it));
    }
    v_.post_swap(it, n);
    
    CGAL_KINETIC_LOG_WRITE(LOG_LOTS, write(LOG_STREAM));
  }

  void audit_order() const {
    //std::cout << "Auditing order at time " << ik_.time() << std::endl;
    for (typename std::list<OD>::const_iterator it
	   = sorted_.begin(); it->object() != sorted_.back().object(); ++it) {
      if (iless_(*next(it), *it)) {
#ifdef CGAL_KINETIC_CHECK_EXACTNESS
	std::cerr << "ERROR: objects " << it->object() << " and "
		  << next(it)->object() << " are out of order.\n";
	std::cerr << "Kinetic are " << aot_->at(it->object()) << " and " << aot_->at(*next(it)) << std::endl;
	std::cerr << "Time is " << ik_.time() << std::endl; 
	/*std::cerr << "Static are " << ik_.current_coordinates_object()(it->object()) << " and " 
	  << ik_.current_coordinates_object()(next(it)->object()) << std::endl;*/
	std::cerr << "ERROR: order is ";
#else
	if (warned_.find(*it) == warned_.end() ||
	    warned_[*it].find(*next(it)) == warned_[*it].end()) {
	  std::cerr << "WARNING: objects " << it->object() << " and "
		    << next(it)->object() << " are out of order.\n";
	  std::cerr << aot_->at(it->object()) << " and " << aot_->at(next(it)->object()) << std::endl;
	  std::cerr << "Time is " << ik_.time() << std::endl; 
	  std::cerr << "WARNING: order is ";
	}
#endif
	write(std::cerr);
	std::cerr << std::endl;
	++internal::audit_failures__;

	if (!wrote_objects_) {
	  wrote_objects_=true;
	  std::cerr << "Objects are: ";
	  for (typename Active_objects_table::Key_iterator kit= mot_listener_.notifier()->keys_begin();
	       kit != mot_listener_.notifier()->keys_end(); ++kit){
	    std::cerr <<  mot_listener_.notifier()->at(*kit) << std::endl;
	  }
	}
      }
      if (compare_(  aot_->at(it->object()), aot_->at(next(it)->object()), simulator_->current_time()) == CGAL::LARGER) {
#ifdef CGAL_KINETIC_CHECK_EXACTNESS
	std::cerr << "ERROR: kinetic objects " << it->object() << " and "
		  << next(it)->object() << " are out of order.\n";
	std::cerr << "Kinetic are " << aot_->at(it->object()) << " and " << aot_->at(*next(it)) << std::endl;
	std::cerr << "Time is " <<ik_.time() << std::endl; 
	/*std::cerr << "Static are " << ik_.current_coordinates_object()(it->object()) << " and " 
	  << ik_.current_coordinates_object()(next(it)->object()) << std::endl;*/
	std::cerr << "ERROR: order is ";
#else
	if (warned_.find(*it) == warned_.end() ||
	    warned_[*it].find(*next(it)) == warned_[*it].end()) {
	  std::cerr << "WARNING: objects " << it->object() << " and "
		    << next(it)->object() << " are out of order.\n";
	  std::cerr << aot_->at(it->object()) << " and " << aot_->at(next(it)->object()) << std::endl;
	  std::cerr << "Time is " <<ik_.time() << std::endl; 
	  std::cerr << "WARNING: order is ";
	}
#endif
	write(std::cerr);
	std::cerr << std::endl;
	++internal::audit_failures__;

	if (!wrote_objects_) {
	  wrote_objects_=true;
	  std::cerr << "Objects are: ";
	  for (typename Active_objects_table::Key_iterator kit= mot_listener_.notifier()->keys_begin();
	       kit != mot_listener_.notifier()->keys_end(); ++kit){
	    std::cerr <<  mot_listener_.notifier()->at(*kit) << std::endl;
	  }
	}
      }
    }
  }

  /* Verify the structure by checking that the current coordinates are
     properly sorted for time t. This function is called by the Sim_listener.*/
  void audit() const
  {

    if (sorted_.size() <2) return;

    ik_.set_time(simulator_->audit_time());
    CGAL_KINETIC_LOG_WRITE(LOG_LOTS, write(LOG_STREAM));
    CGAL_KINETIC_LOG(LOG_LOTS, std::endl);

    
    //typename Instantaneous_kernel::Less_x_1 less= ik_.less_x_1_object();
    for (typename std::list<OD>::const_iterator it
	   = sorted_.begin(); it->object() != sorted_.back().object(); ++it) {
      CGAL_assertion(it->event() != Event_key());
    }
    CGAL_assertion(sorted_.back().event()==Event_key());

    audit_order();
  }

  /* Update the certificates adjacent to object k. This method is called by
     the MOT_listener. std::equal_range finds all items equal
     to a key in a sorted list (there can only be one).*/
  void set(Object_key k) {
    typename std::list<OD>::iterator it;
    for (it = sorted_.begin(); it != sorted_.end(); ++it){
      if (it->object()==k) break;
    }
    CGAL_assertion(it != sorted_.end());
    v_.change_vertex(it);
    rebuild_certificate(it);
    if (it != sorted_.begin()) rebuild_certificate(--it);
  }

  /* Remove object k and destroy 2 certificates and create one new one.
     This function is called by the MOT_listener.*/
  void erase(Object_key k) {
    iterator it;
    for (it = sorted_.begin(); it != sorted_.end(); ++it){
      if (it->object()==k) break;
    }
    //iterator it =  std::equal_range(sorted_.begin(), sorted_.end(),k).first;
    CGAL_precondition(it != sorted_.end());
    CGAL_precondition(it->object() == k);
    
    v_.pre_remove_vertex(it);
    if (next(it) != Iterator(end())) {
      simulator_->delete_event(it->event());
      it->set_event(Event_key());
    }
    if (it != sorted_.begin()) {
      iterator p= prior(it);
      sorted_.erase(it);
      rebuild_certificate(p);
    } else {
      sorted_.erase(it);
    }
    v_.post_remove_vertex(k);
  }
  template <class It> static It next(It it){ return ++it;}
  template <class It> static It prior(It it){ return --it;}

  void write(std::ostream &out) const {
    out << "Sort:\n";
    for (typename std::list<OD>::const_iterator it
	   = sorted_.begin(); it != sorted_.end(); ++it) {
      out << it->object() << " with event (" << it->event() << ")\n";
    }
    out << std::endl << std::endl;;
  }

  typedef typename std::list<OD>::const_iterator Iterator;
  Iterator begin() const
  {
    return sorted_.begin();
  }
  Iterator end() const
  {
    return sorted_.end();
  }

  Sim_listener sim_listener_;
  MOT_listener mot_listener_;
  // The points in sorted order
  std::list<OD > sorted_;
  // events_[k] is the certificates between k and the object after it
  //std::map<Object_key, Event_key > events_;
  Kinetic_less compare_;
  Instantaneous_kernel ik_;
  Instantaneous_less iless_;
  //#ifndef NDEBUG
  mutable bool wrote_objects_;
  mutable std::map<Object_key, std::set<Object_key> > warned_;
  Visitor v_;
  typename Active_objects_table::Handle aot_;
  typename Traits::Simulator::Handle simulator_;
  //#endif
};

template <class Traits, class Visitor>
std::ostream &operator<<(std::ostream &out, const Sort<Traits, Visitor> &s) {
  s.write(out);
  return out;
}

/* It needs to implement the time() and process() functions and
   operator<< */
template <class Sort, class Id, class Solver>
class Swap_event: public Event_base<Sort*>
{
public:
  Swap_event(Id o, Sort* sorter,
	     const Solver &s): Event_base<Sort*>(sorter),
			       left_object_(o), s_(s){}
  void process() {
    Event_base<Sort*>::kds()->swap(left_object_, s_);
  }
  void write(std::ostream &out) const {
    out << left_object_->object() << "X" << Sort::next(left_object_)->object();
    if (s_.will_fail()) out <<  " next is " << s_.failure_time();
    else out << " out of failures";
  }
  void audit(typename Sort::Event_key 
#ifndef NDEBUG
	     tk
#endif
) const {
    //std::cout << "Auditing event ";
    //write(std::cout);
    //std::cout << std::endl;
    CGAL_assertion(left_object_->event() == tk);
  }
  Id left_object_; Solver s_;
};


CGAL_KINETIC_END_NAMESPACE
#endif