// 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_HEAP_POINTER_EVENT_QUEUE_H #define CGAL_KINETIC_HEAP_POINTER_EVENT_QUEUE_H #include #include #include #include #include #include #include #include #include #include namespace CGAL { namespace Kinetic { namespace internal { template class Heap_pointer_event_queue_item_handle; // The interface for an item stored in the ::Heap_pointer_event_queue template class Heap_pointer_event_queue_item: public Ref_counted > { typedef Ref_counted > P; public: /* struct Key: public typename P::Handle { Key(){} Key(Item_handle h): P::Handle(h){} bool is_valid() const { return this->get() != NULL; } };*/ typedef Heap_pointer_event_queue_item_handle Key; Heap_pointer_event_queue_item():bin_(-1), time_(infinity_or_max(Priority(0))){} Heap_pointer_event_queue_item(int bin, const Priority &t): bin_(bin), time_(t){} virtual std::ostream& write(std::ostream &out) const =0; const Priority& time() const {return time_;}; virtual void process() =0; virtual void audit(Key) const=0; virtual void *kds() const =0; virtual CGAL::Comparison_result compare_concurrent(Key a, Key b) const =0; void set_bin(int bin) const { bin_=bin;} int bin() const {return bin_;}; virtual ~Heap_pointer_event_queue_item(){} //virtual const void *event() const=0; private: mutable int bin_; Priority time_; }; CGAL_OUTPUT1(Heap_pointer_event_queue_item) template class Heap_pointer_event_queue_item_handle: public Ref_counted >::Handle { typedef typename Ref_counted >::Handle P; public: std::ostream &write(std::ostream &out) const { return P::operator*().write(out); } template Heap_pointer_event_queue_item_handle(T* t): P(t){} Heap_pointer_event_queue_item_handle(){} Heap_pointer_event_queue_item_handle(const P&p): P(p){} }; CGAL_OUTPUT1(Heap_pointer_event_queue_item_handle) // The how a dummy item is stored in the ::Heap_pointer_event_queue /* One dummy item is used to represent events which will never happen. */ template class Heap_pointer_event_queue_dummy_item: public Heap_pointer_event_queue_item { typedef Heap_pointer_event_queue_item P; public: Heap_pointer_event_queue_dummy_item(): P(-2, internal::infinity_or_max(Priority())){} virtual void process() { } virtual void *kds() const {return NULL;} virtual CGAL::Comparison_result compare_concurrent(typename P::Key a, typename P::Key b) const { if (a < b) return CGAL::SMALLER; else if (b < a) return CGAL::LARGER; else return CGAL::EQUAL; //return CGAL::compare(a,b); } virtual std::ostream& write(std::ostream &out) const { out << "Never."; return out; } virtual void audit(typename P::Key) const { std::cout << "Auditing a dummy event" << std::endl; } virtual ~Heap_pointer_event_queue_dummy_item(){} }; // The how a real item is stored in the ::Heap_pointer_event_queue /* This just stores an object of type Event and passes the virtual calls on to it. The object is reference counted so you don't have to worry about the queue deleting it or not. */ template class Heap_pointer_event_queue_item_rep: public internal::Heap_pointer_event_queue_item { typedef internal::Heap_pointer_event_queue_item P; public: //typedef CGAL::Ref_counted_pointer > Pointer; //typedef CGAL::Ref_counted_pointer > Const_pointer; Heap_pointer_event_queue_item_rep(): internal::Heap_pointer_event_queue_item(){} Heap_pointer_event_queue_item_rep(const Priority &t, const Event &e, unsigned int bin): internal::Heap_pointer_event_queue_item(bin, t), event_(e){} virtual void process() { event_.process(); } virtual void *kds() const {return event_.kds();} virtual CGAL::Comparison_result compare_concurrent(typename P::Key a, typename P::Key b) const { return event_.compare_concurrent(a,b); } virtual void audit(typename P::Key k) const { event_.audit(k); } virtual std::ostream& write(std::ostream &out) const { out << "("; event_.write(out); out << ")"; return out; } // Access the actual event /* There is no non-const access so you can't change the time. */ const Event &event() const { return event_; } Event &event() { return event_; } void set_event(const Event &e) { event_=e; } virtual ~Heap_pointer_event_queue_item_rep(){} protected: Event event_; }; } } } //namespace CGAL::Kinetic::internal namespace CGAL { namespace Kinetic { template class Bin_pointer_event_queue; //! The priority queue for holding many different types of events. /*! This queue allows the priorities to be updated and for elements to be removed. The events are stored behind an interface and accessed through virtual functions allowing many different types of events to be stored in the queue at once, as long as they all share the same Priority. Currently the items in the queue are refence counted. This imposes some overhead, but makes accessing them much simpler since you don't have to worry about them being processed (and deleted or not). I am not sure which is better. */ template class Heap_pointer_event_queue { public: typedef typename FK::Root Priority; friend class Bin_pointer_event_queue; typedef Heap_pointer_event_queue This; typedef internal::Heap_pointer_event_queue_item Item; typedef typename Item::Handle Item_handle; typedef enum Child {FIRST=0, SECOND=1} Child; class Compare { public: Compare(){} bool operator()(Item_handle i0, Item_handle i1) const { CGAL::Comparison_result cr= CGAL::compare(i0->time(), i1->time()); if (cr == CGAL::SMALLER) return true; else if (cr == CGAL::LARGER) return false; else { if (i0->kds() < i1->kds()) return true; else if (i0->kds() > i1->kds()) return false; else { cr= i0->compare_concurrent(Key(i0), Key(i1)); if (cr == CGAL::SMALLER) return true; else if (cr == CGAL::LARGER) return false; else { //CGAL_error(); return false; } } } } }; //typedef Priority_t Priority; //! The key to identify something in the queue. /*! It uses a prettified version of the ref counted pointer. */ typedef typename Item::Key Key; /*struct Key: public Item_handle { Key(){}; Key(Item*i): Item_handle(i){} Key(Item_handle ih): Item_handle(ih){} static Key null() { return Key(); } };*/ //typedef Item_handle Key; //! Construct it with a suggested size of sz. Heap_pointer_event_queue(const Priority&, const Priority &end, FK, int sz=1000): end_(end) { queue_.reserve(sz); null_event_= Key(new internal::Heap_pointer_event_queue_dummy_item()); } Heap_pointer_event_queue(const Priority&, FK, int sz=1000) { queue_.reserve(sz); null_event_= Key(new internal::Heap_pointer_event_queue_dummy_item()); } const Priority& end_priority() const { return end_; } void set_interval(const Priority &, const Priority &e) { end_=e; } bool is_after_end(const Priority &t) const { if (INF) return false; else return CGAL::compare(t,end_priority()) == CGAL::LARGER; } void audit_events() const { for (typename std::vector::const_iterator it= queue_.begin(); it != queue_.end(); ++it) { (* it)->audit(Key(*it)); } } void audit_event(Key k) const { k->audit(k); } //! insert value_type into the queue and return a reference to it /*! The reference can be used to update or erase it. */ template Key insert(const Priority &t, const E & e) { if (!is_after_end(t)) { Item_handle k= new internal::Heap_pointer_event_queue_item_rep(t, e, static_cast(queue_.size())); queue_.push_back(k); bubble_up(static_cast(queue_.size()-1)); //std::push_heap(queue_.begin(), queue_.end()); CGAL_expensive_postcondition(is_valid()); CGAL_postcondition(k->bin() != -1); return Key(k); } else { return null_event_; } } //! remove the event referenced by item from the queue void erase(const Key &item) { if (item == end_key()) return; CGAL_expensive_precondition(item != Key()); CGAL_expensive_precondition(is_in_heap(item)); int bin= item->bin(); //if (bin ==-1) return; CGAL_precondition(static_cast (bin) < queue_.size() && bin >= 0); // this is a bit more work than strictly necessary swap(static_cast(queue_.size()-1), bin); queue_.pop_back(); if (static_cast(bin) < queue_.size()) { bubble(bin); } item->set_bin(-1); CGAL_expensive_postcondition(is_valid()); } //! The pointer type to use to access an event of type E. /* template struct Event_pointer { typedef const Heap_pointer_event_queue_item_rep* Pointer; struct Handle: public Heap_pointer_event_queue_item_rep::Const_pointer { Handle(Pointer p): Heap_pointer_event_queue_item_rep ::Const_pointer(reinterpret_cast*>(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 typename Event_pointer::Pointer event(const Key &item, const E &) const { return reinterpret_cast::Pointer >( item.get()); }*/ template const E& get(const Key &item) const { CGAL_precondition(item && item != null_event_); return reinterpret_cast*>( item.get())->event(); } template E& get(Key item) { CGAL_precondition(item && item != null_event_); typename internal::Heap_pointer_event_queue_item *ptr= item.get(); typename internal::Heap_pointer_event_queue_item_rep* nptr = reinterpret_cast*>(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 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(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(bool(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_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 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 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::const_iterator curi= bins.begin(), endi= bins.end(); #else typename std::vector::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 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); } Key front() const { return Key(queue_.front()); } protected: //! Stores the priorities and data and a refersence back to the _queue std::vector queue_; Compare compare_; //std::vector 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(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(j) >= queue_.size()) return true; else if (static_cast(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, static_cast(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(ibin(); CGAL_assertion(static_cast(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)); } #endif return true; } }; template std::ostream &operator<<(std::ostream &out, const Heap_pointer_event_queue &q) { q.write(out); return out; } } } //namespace CGAL::Kinetic #endif