two_list_pointer_event_queue.h

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

      unmake_event(oi);
      return Key(ni);
    }
    // unreachable

  }

  //! Get the time of the next event to be processed.
  /*!  It is OK to call this if the queue is empty. In that case it
    will just return infinity.
  */
  const Priority& front_priority() const
  {
    CGAL_precondition(!front_.empty());
    return front_.front().time();
  }


  Key front() const
  {
    CGAL_precondition(!front_.empty());
    return Key(const_cast<Item*>(&front_.front()));
  }

  //! Access the time of a particular event
  const Priority& priority(const Key &item) const
  {
    return item->time();
  }

  //! empty
  bool empty() const
  {
    CGAL_precondition(!front_.empty() || back_.empty());
    return front_.empty() 
      || CGAL::compare(front_.front().time(), end_priority()) == CGAL::LARGER;
  }

  //! Remove the next event from the queue and process it.
  /*!
    Processing means that the process() method of the event object is called.
  */
  void process_front() {
    CGAL_precondition(!empty());
    CGAL_expensive_precondition(audit());
    if (!front_.empty()) {
      Item *i= &front_.front();
      CGAL_KINETIC_LOG(LOG_SOME, "Processing event " << *i << std::endl);
      front_.pop_front();
      CGAL_expensive_postcondition(audit());
      if (front_.empty() && !back_.empty()) grow_front();
      i->process();

      /*if (!front_.empty() && i->time() == front_.front().time()) {
	CGAL_KINETIC_LOG(LOG_SOME, "Degeneracy at time "
	<< i->time() << " the events are: "
	<< *i << " and " << front_.front() << std::endl);
	}*/

      unmake_event(i);
    }
    else {
      CGAL_assertion(back_.empty());
    }
  }

  //! debugging
  bool print() const
  {
    write(std::cout);
    return true;
  }

  void write(const Queue &q, std::ostream& out) const {
    for (typename Queue::const_iterator it = q.begin(); it != q.end(); ++it) {
      out << "(" << &*it << ": " << *it << ")";
      out << std::endl;
    }
  }

  bool write(std::ostream &out) const
  {
    write(front_, std::cout);
    out << "--" << ub_ << "--" << std::endl;
    write(back_, std::cout);
    out << std::endl;
    return true;
  }

  Key end_key() const
  {
    return null_event_;
  }

  

  const Priority& end_priority() const
  {
    return end_time_;
  }


  void set_interval(const Priority &start_time, const Priority &end_time) {
    CGAL_precondition(!INF);
    initialize(start_time, end_time);
  }
  
  void audit_events() const {
    for (typename Queue::const_iterator it= front_.begin(); it != front_.end(); ++it) {
      it->audit(Key(const_cast<Item*>(&*it)));
    }
    for (typename Queue::const_iterator it= back_.begin(); it != back_.end(); ++it) {
      it->audit(Key(const_cast<Item*>(&*it)));
    }
  }

  void audit_event(Key k) const {
    k->audit(k);
  }

  void clear() {
    front_.clear();
    back_.clear();
    //all_in_front_=false;
  }

protected:
  void initialize(const Priority &start_time, const Priority &end_time) {
    ub_=CGAL::to_interval(start_time).second;
    // should be nextafter
    step_=1;
    //all_in_front_= false;
    end_time_=end_time;
  }

 void initialize(const Priority &start_time) {
   CGAL_precondition(INF);
   ub_=CGAL::to_interval(start_time).second;
    // should be nextafter
   step_=1;
    //all_in_front_= false;
  }
  bool leq_ub(const Priority &t) const {
    //if (all_in_front_) return true;
    //else 
    // pretty much anything fast will have a fast to_interval, so use it
    std::pair<double,double> iv= CGAL::to_interval(t);
    if (iv.first > ub_) {
      return false;
    } else if (iv.second <= ub_) {
      return true;
    } else {
      return CGAL::compare(t, Priority(ub_)) != CGAL::LARGER;
    }
  }

 
  template <class E>
  Item *make_event(const Priority &t, E &e) {
    typedef typename boost::remove_const<E>::type NCE;
    Item *ni
      = new internal::Two_list_event_queue_item_rep<Priority, NCE>(t, e);
    intrusive_ptr_add_ref(ni);
    return ni;
  }

  void unmake_event(Item *i) {
    intrusive_ptr_release(i);
  }

  bool audit() {
    for (typename Queue::const_iterator it = front_.begin(); it != front_.end(); ++it) {
      Priority t= it->time();
      CGAL_assertion(leq_ub(t));
      CGAL_assertion(it->in_list()== Item::FRONT);
      //CGAL_exactness_assertion(t >= lb_);
    }
    for (typename Queue::const_iterator it = back_.begin(); it != back_.end(); ++it) {
      Priority t= it->time();
      CGAL_assertion(!leq_ub(t));
      CGAL_assertion(it->in_list()== Item::BACK);
    }
#ifndef NDEBUG
    for (unsigned int i=0; i< inf_.size(); ++i) {
      Priority t= inf_[i]->time();
      CGAL_assertion(INF || CGAL::compare(t, end_priority())== CGAL::LARGER);
      CGAL_assertion(inf_[i]->in_list() == Item::INF);
    }
#endif
    {
      typename Queue::const_iterator it = front_.begin();
      ++it;
      for (; it != front_.end(); ++it) {
	Priority tc= it->time();
	Priority tp= boost::prior(it)->time();
#ifndef NDEBUG
	if (CGAL::compare(tc, tp) == CGAL::SMALLER) {
	  std::cout << "ERROR: Out of order " << tc << std::endl << tp << std::endl << std::endl;
	  ++internal::audit_failures__;
	}
#endif
	//CGAL_assertion(tc >= tp);
      }
    }
    return true;
  }
public:
  bool contains(const Key k) const
  {
    //if (k.pointer()->time() == std::numeric_limits<Priority>::infinity()) return true;
    for (typename Queue::const_iterator it = front_.begin(); it != front_.end(); ++it) {
      if (&*it == k.pointer()) return true;
    }
    for (typename Queue::const_iterator it = back_.begin(); it != back_.end(); ++it) {
      if (&*it == k.pointer()) return true;
    }
#ifndef NDEBUG
    for (unsigned int i=0; i< inf_.size(); ++i) {
      const Key j=inf_[i];
      const Key ki= k;
      if (j==ki) return true;
    }
#else
    if (k.pointer()->in_list() == Item::INF) return true;
#endif
    return false;
  }
protected:
  unsigned int select(Queue &source, Queue &target/*, bool binf*/) {
    unsigned int sz= source.size() + target.size();if (sz);
    int count=0;
    Iterator it= source.begin();
    while (it != source.end()) {
      // assert(it->time() >= a);
    
      if (leq_ub(it->time())) {
	Item *i= &*it;
	Iterator t= boost::next(it);
	source.erase(it);
	it=t;
	target.push_back(*i);
	++count;
      }
      else {
	++it;
      }
    }
    CGAL_assertion(sz==source.size() + target.size());
    return count;
  }

  /*NT step() const{
    return (std::max)(ub_-lb_, NT(1));
    }*/

  NT av(NT a, NT b) const
  {
    return .5*(a+b);
  }

  template <class It>
  void set_front(It b, It e, typename Item::List val) {
    for (; b!= e; ++b) {
      b->set_in_list(val);
    }
  }
  template <class C, class It>
  void make_inf(C &c, It b, It e) {
    for (It cit = b; cit != e; ++cit) {
      CGAL_assertion(INF || CGAL::compare(cit->time(), end_priority()) == CGAL::LARGER);
      //std::cout << "Dropping inf event " << &*cit << std::endl;
#ifndef NDEBUG
      inf_.push_back(&*cit);
#endif
      cit->set_in_list(Item::INF);
      It p= boost::prior(cit);
      c.erase(cit);
      unmake_event(&*cit);
      cit=p;
    }
    //c.erase(b, e);
  }

  void grow_front(Queue &cand, int recursive_count=0) {
    const bool dprint=false;
    CGAL_assertion(front_.empty());
    CGAL_assertion(!cand.empty());
    //CGAL_assertion(!all_in_front_);
    CGAL_assertion(step_ != 0);
    if (dprint) std::cout << "Growing front from " << ub_ << " with step " 
			  << step_ << "(" << recursive_count << ") ";

    //CGAL_assertion(ub_<end_split());
    if (cand.size() + front_.size() < max_front_size()) {
      if (dprint) std::cout << "Setting ub to end of " << end_time_ << std::endl;
      front_.splice(front_.end(), cand);
      return;
    }

    //CGAL_assertion(!too_big(ub_));

    /*if ( CGAL::compare(end_priority(), Priority(ub_)) == CGAL::SMALLER) {
      all_in_front_=true;
      //ub_=end_split();
      }*/

    CGAL_assertion_code(unsigned int num=)
      select(cand, front_/*, all_in_front_*/);
    CGAL_assertion(front_.size() >= num);
    /*if (all_in_front_) {
      make_inf(cand, cand.begin(), cand.end());
      } else*/
    if (front_.empty()) {
      if (recursive_count > 10) {
	// do something
	std::cerr << "Too many recursions " << std::endl;
	//all_in_front_=true;
	ub_=CGAL::to_interval(end_time_).second; //CGAL::to_interval(end_time_).second*2;// std::numeric_limits<double>::infinity();
	/*unsigned int num=*/ select(cand, front_/*, all_in_front_*/);
	select(back_, front_);
	make_inf(cand, cand.begin(), cand.end());
	make_inf(back_, back_.begin(), back_.end());
	//grow_front(cand, recursive_count+1);
      } else {
	if (dprint) {
	  std::cout << "undershot." << std::endl;
	  write(front_, std::cout);
	  std::cout << "-- " << ub_ << "--\n";
	  write(cand, std::cout);
	  std::cout << "--\n";
	  write(back_, std::cout);
	}
	ub_+= step_;
       	step_*=2.0;
	CGAL_assertion(step_!=0);
	cand.splice(cand.end(), back_);
	grow_front(cand, recursive_count+1);
      }
    } else {
      //      unsigned int ncand= cand.size();
      back_.splice(back_.begin(), cand);
      if (front_.size() >  max_front_size()) {
	if (recursive_count > 10) {
	  //std::cerr << "Gave up on isolating front. Let with size " << front_.size() << " ub=" << ub_ << "step=" << step_ <<  "\n";
	  return;
	} else {
	  // keep the bit length shortish
	  double frac= .75+.25*max_front_size()/static_cast<double>(front_.size()+1);
	  double ostep= step_;
	  CGAL_assertion(frac < 1.1);
	  CGAL_assertion(frac >= 0.0);
	  //double rfrac= std::ceil(frac*256.0)/256.0;
	  step_*=frac;
	  //else nstep = step_*.6;
	  //CGAL_assertion(nstep >0);
	  cand.swap(front_);
	  //ub_=lb_;
	  if (step_ == 0) {
	    CGAL_KINETIC_ERROR( "underflow in queue ");
	    CGAL_KINETIC_ERROR_WRITE(write(LOG_STREAM));
	    CGAL_assertion(cand.empty());
	    step_=.0000001;
	    return;
	  } else {
	    //CGAL_assertion(!all_in_front_);
	    
	    if (dprint) {
	      std::cout << "...overshot" << std::endl;
	      write(front_, std::cout);
	      std::cout << "-- " << ub_ << "(" <<step_ << ")" << "--\n";
	      write(cand, std::cout);
	      std::cout << "--\n";
	      write(back_, std::cout);
	    }
	    ub_=ub_-ostep+step_;  
	    grow_front(cand, recursive_count+1);
	  }
	}
      }
      else {
	if (dprint) std::cout << std::endl;
      }
    }
    CGAL_postcondition(cand.empty());
  }

  void grow_front() {
    //++growth__;
    //std::cout << "Growing front from " << ub_ << std::endl;
    //assert(is_valid());
    CGAL_precondition(!back_.empty());
    CGAL_precondition(front_.empty());
    CGAL_assertion_code(unsigned int sz= front_.size()+back_.size()+ inf_.size());
    Queue cand;
    cand.splice(cand.begin(), back_);
    ub_ += step_;
    grow_front(cand);
    set_front(front_.begin(), front_.end(), Item::FRONT);
    front_.sort();
    ub_= CGAL::to_interval(front_.back().time()).second;
    // hmmmm, now I should make a second pass to merge. Ick.

    CGAL_assertion(sz==front_.size()+back_.size() + inf_.size());
    CGAL_assertion(audit());
    //std::cout << "to " << ub_ << std::endl;
  }

  void shrink_front() {
    //++shrink__;
    //std::cout << "Shrinking front from " << ub_ << std::endl;
    typename Queue::iterator it=front_.begin();
    unsigned int mf= max_front_size();
    for (unsigned int i=0; i < mf; ++i) {
      ++it;
    }

    // use tii_ so that it does not subdivide

    double split =  CGAL::to_interval(it->time()).second;
    if (!INF && (CGAL::compare(end_priority(), it->time())==CGAL::SMALLER
		 || CGAL::compare(end_priority(), Priority(split))==CGAL::SMALLER)) {
      std::cout << "Past end in Queue " << end_priority() << ", "
		<< it->time() << ", " << Priority(split) << std::endl;
      //all_in_front_=true;
      ub_= CGAL::to_interval(end_time_).second;
      set_front(back_.begin(), back_.end(), Item::FRONT);
      front_.splice(front_.end(), back_);

      while (it != front_.end()) {
	if (CGAL::compare(it->time(), end_priority())==CGAL::LARGER) break;
      }
      set_front(it, front_.end(), Item::INF);
      std::vector<Item*> temp;
      for (typename Queue::iterator c= it; c != front_.end(); ++c) {
	temp.push_back(&*c);
#ifndef NDEBUG
	inf_.push_back(&*c);
#endif
	//std::cout << "Dropping inf event " << &*c << std::endl;
      }
      front_.erase(it, front_.end());

   
    
      for (unsigned int i=0; i< temp.size(); ++i) {
	unmake_event(temp[i]);
      }
    } else {
      while (CGAL::compare(it->time(), Priority(split)) != CGAL::LARGER
	     && it != front_.end()) ++it;
      
      if (it != front_.end()) {
	
	set_front(it, front_.end(), Item::BACK);
	back_.splice(back_.begin(), front_, it, front_.end());
	double oub=ub_;
	//all_in_front_=false;
	ub_ = split;
	//CGAL_assertion(!too_big(ub_));
	//CGAL_assertion(ub_ <= end_split());
	step_= std::abs(ub_-oub);
	if (step_<=0) {
	  /*if (dprint) std::cout << "fixing step since " << oub 
	    << " equals new bound" << std::endl;*/
	  CGAL_KINETIC_ERROR("Roundoff error in split " << split << " " << ub_ << " "
			     <<  oub);
	  step_=.00001;
	}
	//CGAL_assertion(!all_in_front_);
	/*CGAL_postcondition_code(if (step_<0) std::cerr << step_ << std::endl;);
	CGAL_postcondition_code(if (step_<0) std::cerr << ub_ << std::endl;);
	CGAL_postcondition_code(if (step_<0) std::cerr << oub << std::endl;);
	CGAL_postcondition_code(if (step_<0) std::cerr << front_.back().time() << std::endl;);
	CGAL_postcondition_code(if (step_==0) for (typename Queue::const_iterator it=front_.begin(); it != front_.end(); ++it) std::cout << *it << std::endl);
	CGAL_postcondition(step_>=0);*/
      }
    }
  }

  /*NT end_split() const
    {
    return end_split_;
    }*/

  /*const Priority& end_time() const
    {
    return end_time_;
    }*/

  unsigned int max_front_size() const
  {
    return TARGET;
    //return (std::max)(4U, static_cast<unsigned int>(std::sqrt(static_cast<double>(front_.size()+back_.size()))));
  }

  //typename FK::To_isolating_interval tii_;
  Queue front_, back_;
#ifndef NDEBUG
  std::vector<Key> inf_;
#endif
  double ub_;
  double step_;
  //bool all_in_front_;
  Priority end_time_;
  Key null_event_;
  //NT end_split_;
};

template <class D, unsigned int T, bool INF>
std::ostream &operator<<(std::ostream &out, const Two_list_pointer_event_queue<D, INF, T> &q)
{
  q.write(out);
  return out;
}


CGAL_KINETIC_END_NAMESPACE
#endif