heap_pointer_event_queue.h

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

    struct Event_pointer {
    typedef const Heap_pointer_event_queue_item_rep<Priority, E>* Pointer;
    struct Handle: public  Heap_pointer_event_queue_item_rep<Priority, E>::Const_pointer {
    Handle(Pointer p):
    Heap_pointer_event_queue_item_rep<Priority, E>
    ::Const_pointer(reinterpret_cast<const Heap_pointer_event_queue_item_rep<Priority, E>*>(p)){
    }
    Handle(){}

    };
    };*/

  //! Access a ref counted pointer corresponding to the event with item.
  /*!
    Note, there is a reinterpret cast going on in here, so the type better be correct.

    If you store the return value, please wrap it in an Event_pointer
    to make reference counting work.
  */
  /*template <class E>
    typename Event_pointer<E>::Pointer event(const Key &item, const E &) const {
    return reinterpret_cast<typename Event_pointer<E>::Pointer >( item.get());
    }*/

  template <class E>
  const E& get(const Key &item) const
  {
    CGAL_precondition(item && item != null_event_);
    return reinterpret_cast<internal::Heap_pointer_event_queue_item_rep<Priority, E>*>( item.get())->event();
  }


  template <class E>
  E& get(Key item)
  {
    CGAL_precondition(item && item != null_event_);
    typename internal::Heap_pointer_event_queue_item<Priority> *ptr= item.get();
    typename internal::Heap_pointer_event_queue_item_rep<Priority, E>* nptr
      = reinterpret_cast<internal::Heap_pointer_event_queue_item_rep<Priority, E>*>(ptr);
    return nptr->event();
  }

  //! Replace the event referenced by item with a new event referenced by ne
  /*!  They must have exactly the same times associated with
    them. This is checked when expensive checks are turned on.
  */
  template <class NE>
  Key set(const Key &item, const NE &ne) {
    CGAL_expensive_precondition(is_in_heap(item));
    CGAL_precondition(item && item != null_event_);
    //CGAL_expensive_precondition(item.get()->time() == ne.time());
    CGAL_expensive_precondition(item);
    int bin = item.get()->bin();
    CGAL_expensive_precondition(Key(queue_[bin])==item);
    queue_[bin]= new internal::Heap_pointer_event_queue_item_rep<Priority, NE>(item.get()->time(), ne, bin);
    CGAL_expensive_postcondition(is_valid());
    return queue_[bin];
  }

  //! 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.
  */
  Priority front_priority() const
  {
    CGAL_precondition(!queue_.empty());
    return queue_.front()->time();
  }

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

  //! empty
  bool empty() const
  {
    return queue_.empty();
  }

  //! Clear everything
  void clear() {
    // ref counted pointers are nice.
    queue_.clear();
  }



  //! 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());
    //if (queue_.front()->time() < end_priority()) {
    //CGAL_precondition_code(Item_handle k= queue_.front());
    CGAL_KINETIC_LOG(LOG_SOME, "Processing " << queue_.front() << std::endl);
    Item_handle ih= queue_.front();
    pop_front();
    //std::pop_heap(queue_.begin(), queue_.end());
    ih->process();
    CGAL_expensive_postcondition(is_valid());
    /*}
      else {
      clear();
      }*/
  }

  //! debugging
  bool print() const
  {
    write(std::cout);
    return true;
  }
  /*
    void process_final_events() {
    bool do_i_use_this;
    std::vector<Item_handle> c;
    c.swap(final_events_);
    for (unsigned int i=0; i< c.size(); ++i){
    c[i]->set_processed(true);
    }
    }*/
  //! Write the events in order to out
  /*!  When warnings are turned on, it will print if two events occur
    at the same time.
  */
  bool write(std::ostream &out) const
  {
    //std::cout << "Not writing queue.\n";
    //return true;
#if 0
    std::vector<Item_handle> bins;

    for (unsigned int i=0; i< queue_.size(); ++i) {
      bins.push_back(queue_[i]);
    }

    std::sort(bins.begin(), bins.end(), compare_);

    typename std::vector<Item_handle>::const_iterator curi= bins.begin(), endi= bins.end();
#else
    typename std::vector<Item_handle>::const_iterator curi= queue_.begin(), endi= queue_.end();
#endif
    for (; curi != endi; ++curi) {
      Priority t=(*curi)->time();
      // HACK HACK because CGAL::to_double(t) won't compile with gcc 3.4
      std::pair<double,double> d= CGAL::to_interval(t);
      //CGAL::to_double(t);
      out << "<" << d.first << "..." << d.second << ": ";
      (*curi)->write(out);
      out << ">\n";
    }
    out << std::endl;
#if 0
    for (unsigned int i=1; i< bins.size(); ++i) {
      if (bins[i-1]->time()== bins[i]->time()) {
	out << "Warning, two concurrent events: " << bins[i] << " and "
	    << bins[i-1] << " at time " << bins[i]->time() << std::endl;
      }
    }
#endif

    /*if (!final_events.empty()) {
      out << "Finally: \n";
      for (unsigned int i=0; i< final_events_.size(); ++i){
	final_events_[i]->write(out) << std::endl;
      }
      }*/

    
    //out << std::endl;
    return false;
  }

  Key end_key() const
  {
    return null_event_;
  }

  bool contains(Key k) const {
    return is_in_heap(k);
  }

protected:
  //! Stores the priorities and data and a refersence back to the _queue
  std::vector<Item_handle> queue_;
  Compare compare_;
  //std::vector<Item_handle> final_events_;
  Key null_event_;
  Priority end_;

  bool is_in_heap(Key k) const
  {
    for (unsigned int i=0; i< queue_.size(); ++i) {
      if (queue_[i]==k) return true;
    }
    return false;
  }

  //! Exchange the position of two bins
  void swap(unsigned int i, unsigned int j) {
    std::swap(queue_[i], queue_[j]);
    int bin= queue_[i]->bin();
    queue_[i]->set_bin(queue_[j]->bin());
    queue_[j]->set_bin(bin);
  }

  //! heap order parent
  int parent(unsigned int i) const
  {
    return (static_cast<int>(i)-1)/2;
  };

  //! heap order child
  unsigned int child(unsigned int i, Child which) const
  {
    return 2*i+1+which;
  }

  //! Compare the items of two indices
  bool less_items(unsigned int i, unsigned int j) const
  {
    if (static_cast<unsigned int>(j) >= queue_.size()) return true;
    else if (static_cast<unsigned int>(i) >= queue_.size()) return false;
    else {
      return compare_(queue_[i], queue_[j]);
    }
  }
  //! Check if item i is less than its c'th child
  bool less_than_child(unsigned int  i, unsigned int c) const
  {
    int ch= child(i,c);
    return less_items(i, ch);
  }
  //! check of item i is less than its parent
  bool less_than_parent(unsigned int i) const
  {
    if (i==0) return false;
    else return less_items(i, parent(i));
  }

  //! remove the front of the queue and fix the heap property
  void pop_front() {
    CGAL_expensive_precondition(!empty());
    Item_handle item= queue_.front();
    swap(0, queue_.size()-1);
    queue_.back()->set_bin(-1);
    queue_.pop_back();
    if (!queue_.empty()) bubble_down(0);
  }

  //! Make sure that item i is not less than its parents and fix
  void bubble_down(unsigned int i) {
    CGAL_expensive_precondition(i<queue_.size());
    while (i < queue_.size()) {
      unsigned int lc= child(i,FIRST), rc= child(i,SECOND);
      if (!less_items(rc, lc)) {        // make the sorting stable
	if (less_items(lc, i)) {
	  swap(i, lc);
	  i=lc;
	} else break;
      }
      else {
	if (less_items(rc, i)) {
	  swap(i, rc);
	  i=rc;
	} else break;
      }
    }
  }
  //! make sure the heap order is respected above item i
  void bubble_up(unsigned int i) {
    CGAL_expensive_precondition(i< queue_.size());
    while (less_than_parent(i)) {
      swap(i, parent(i));
      i=parent(i);
    }
  }
  //! both buttles
  void bubble(unsigned int i) {
    bubble_up(i);
    bubble_down(i);
  }

  //! debugging
  bool is_valid() const
  {
    for (unsigned int i=0; i< queue_.size(); ++i) {
      //int bin= i;
      int back= queue_[i]->bin();
      CGAL_assertion(static_cast<unsigned int>(back)==i || write(std::cerr));
      CGAL_assertion(!less_than_parent(i) || write(std::cerr));
      //CGAL_assertion(less_than_child(i, FIRST));
      //CGAL_assertion(less_than_child(i, SECOND));
    }
    return true;
  }

};

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


CGAL_KINETIC_END_NAMESPACE
#endif