// 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; either version 3 of the License, // or (at your option) any later version. // // 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$ // $Id$ // // // Author(s) : Daniel Russel #ifndef CGAL_KINETIC_SIMULATOR_BASE_H_ #define CGAL_KINETIC_SIMULATOR_BASE_H_ #include #include #include #include #include #include namespace CGAL { namespace Kinetic { #ifdef CGAL_KINETIC_CHECK_EXPENSIVE #ifndef CGAL_KINETIC_DISABLE_AUDITING #define CGAL_KINETIC_ENABLE_AUDITING #endif //#warning Kinetic data structures will be audited at run time. #endif //! The simulator /*! The simulator is responsible for maintaining the event queue and processing events in the proper order. It takes a PolynomialKernel and an EventQueue as arguments as well as a flag saying whether the computations are performed exactly or not. This flag affects how it treats the output of the solvers. The PolynomialKernel is used to generate solvers as well as evaluate some predicates on the functions being solved. The Simulator creates two types of notifications, one when time is reversed (DIRECTION_OF_TIME) and one when there is a time at which the kinetic data structures can efficient audit themselves (HAS_AUDIT_TIME). The notification is done through a standard interface describe in CGAL::Listener. The solvers defined by the PolynomialKernel should not be the CGAL::Polynomial::GSL_solver or CGAL::Polynomial::Linear_solver. Use CGAL::Kinetic::GSL_solver or CGAL::KDS::Linear_solver instead as they are more robust in the case of kinetic data structures. Even though time can be "reversed" the future is always with increasing time. When time is reversed the current_time() becomes the negative of the old current_time(). In some cases, this means processing some events (since there needs to be a value of time after the last event and before the next one in order to reverse). Auditing occurs once between each pair of disjoint events. It occurs at a time close to the midpoint between the two event times. It is triggered by the time being advanced beyond the midpoint between the two event times. The Root_enumerator type is not that defined by the Polynomial_kernel since the polynomial kernel needs to have a real solver which returns all roots, where as the Simulator solver can check various invariants and skip even roots and things. This is especially important when performing numeric computations. I cannot put the Instantaneous_kernel in here since that might depend on the static data structure being used. */ template > class Default_simulator: public Ref_counted > { protected: typedef Default_simulator This; //typedef typename Polynomial_kernel_t::Function Poly; typedef typename Queue::Priority Queue_time; public: //typedef Kinetic_kernel_t Kinetic_kernel; //! The polynomial kernel. /*! I don't know that there is any actual use for this, so maybe it should not be exposed. */ typedef Polynomial_kernel_t Function_kernel; //! The solver. //typedef typename Function_kernel::Root_stack Root_stack; //! The current time. /*! This is a Root from the Polynomial package and supports whatever operations they support. See CGAL::Polynomial::Simple_interval_root for an example. */ typedef typename Function_kernel::Root Time; //! A key which uniquely identifies a scheduled event /*! If an event is not actually schedule (for example if it occurs past the last time of interest), it is assigned a special Event_key called null_event(). */ //#ifdef NDEBUG typedef typename Queue::Key Event_key; /*#else typedef typename Queue::Key Queue_key; struct Event_key: public Queue_key { Event_key(){} Event_key(Queue_key k): Queue_key(k){} }; #endif*/ //! The basic number type typedef typename Function_kernel::FT NT; //! Create a simulator passing the start time and the end time. Default_simulator(const Time &start_time, const Time &end_time, Function_kernel fk=Function_kernel()):queue_(start_time, end_time, fk, 100), cur_time_(start_time), //last_event_time_(start_time), mp_(fk.rational_between_roots_object()), //ir_(fk.is_rational_object()), //tr_(fk.to_rational_object()), is_forward_(true) { number_of_events_=0; #ifdef CGAL_KINETIC_ENABLE_AUDITING // make it less than the current time. //std::pair ival= to_interval(cur_time_); //audit_time_=NT(ival.first-10.0); audit_time_= CGAL::to_interval(start_time).second; #endif }; Default_simulator(const Time &start_time, Function_kernel fk=Function_kernel()):queue_(start_time, fk, 100), cur_time_(start_time), //last_event_time_(start_time), mp_(fk.rational_between_roots_object()), //ir_(fk.is_rational_object()), //tr_(fk.to_rational_object()), is_forward_(true) { number_of_events_=0; #ifdef CGAL_KINETIC_ENABLE_AUDITING // make it less than the current time. //std::pair ival= to_interval(cur_time_); //audit_time_=NT(ival.first-10.0); audit_time_= CGAL::to_interval(start_time).second; #endif }; //! Return the current time /*! If an event is currently being processed, then this is the failure time of that event. Otherwise it is between the last event which was processed and the next event to be processed. */ CGAL_GET(Time, current_time, return cur_time_); //! Set the current time to t /*! t must be after (or equal to) current_time(). Any events between current_time() and t are processed in the proper order. */ void set_current_time(const Time &t) { CGAL_precondition_code(CGAL::Comparison_result debug_cr =CGAL::compare(t, cur_time_)); CGAL_precondition(debug_cr != CGAL::SMALLER); /*#ifdef CGAL_KINETIC_CHECK_EXPENSIVE if (current_time() < audit_time_ && t >= audit_time_) { audit_all_kdss(); } #endif*/ while (CGAL::compare(next_event_time(), t) == CGAL::SMALLER && !queue_.empty()) { //Time net= next_event_time(); //CGAL::Comparison_result cr= CGAL::compare(next_event_time(), t); process_next_event(); /*#ifdef CGAL_KINETIC_CHECK_EXPENSIVE if (current_time() < audit_time_ && t >= audit_time_) { audit_all_kdss(); } cur_time_=audit_time_; #endif*/ } if (queue_.is_after_end(t)) { cur_time_= queue_.end_priority(); } else { cur_time_=t; } } //! Not clear if I want two methods void set_interval(const Time &ts, const Time &te) { //CGAL_precondition(t <=cur_time_); if (!queue_.empty()) { std::cerr << queue_ << std::endl; } CGAL_precondition(queue_.empty()); cur_time_=ts; //last_event_time_=ts; queue_.set_interval(ts, te); } //! Return a rational number for current time. /*! This returns a ration number representing the current time. This only returns a valid time if has_rational_current_time() is true. */ NT next_time_representable_as_nt() const { // why did I have this? "&& cur_time_ != end_time()" double ub= to_interval(current_time()).second; if (CGAL::compare(current_time(), next_event_time()) == CGAL::EQUAL || CGAL::compare(Time(ub), next_event_time()) == CGAL::SMALLER) { return NT(ub); } else { //typename Function_kernel::Rational_between_roots bet= kernel_.rational_between_roots_object(); if (current_time() == end_time()) { // really, I do want last_event, but I removed it :-( std::pair ti= CGAL::to_interval(end_time()); if (ti.first == ti.second) { return NT(ti.first); } else { std::cerr << "You cannot currently call this function at the end of time if the end time is not" "exactly representable as a double. Sorry. This is fixable, so complain to me--Daniel" << std::endl; CGAL_error(); return NT(ti.first); } } else { return mp_(current_time(), next_event_time()); } } } //! Returns true if the current time is a rational number and there are no events at the current time /*! precondition that has_rational_current_time(). */ bool has_audit_time() const { #ifdef CGAL_KINETIC_ENABLE_AUDITING return CGAL::compare(Time(audit_time_), current_time()) != CGAL::SMALLER; #else return false; #endif } const NT& audit_time() const { CGAL_precondition(has_audit_time()); #ifdef CGAL_KINETIC_ENABLE_AUDITING CGAL_precondition(queue_.empty() || Time(audit_time_) < next_event_time()); return audit_time_; #else CGAL_precondition(0); static NT z(0); return z; #endif } //! The time of the next event /*! Or end_time() if the queue is empty. */ CGAL_GETNR(Time, next_event_time, return queue_.empty()? end_time(): Time(queue_.front_priority())); CGAL_GETNR(Event_key, next_event, return queue_.empty()? Event_key(): queue_.front()); //! The last time of interest /*! If time is running backwards, then this returns Time::infinity() */ CGAL_GETNR(Time, end_time, return is_forward_? queue_.end_priority(): std::numeric_limits