SPAR/AIModule/BWTA/vendors/CGAL/CGAL/Kinetic/Heap_pointer_event_queue.h

Go to the documentation of this file.

// 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; version 2.1 of the License.
// See the file LICENSE.LGPL distributed with CGAL.
//
// 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: svn+ssh://scm.gforge.inria.fr/svn/cgal/branches/CGAL-3.5-branch/Kinetic_data_structures/include/CGAL/Kinetic/Heap_pointer_event_queue.h $
// $Id: Heap_pointer_event_queue.h 40832 2007-11-08 00:27:20Z ameyer $
// 
//
// Author(s)     : Daniel Russel <drussel@alumni.princeton.edu>

#ifndef CGAL_KINETIC_HEAP_POINTER_EVENT_QUEUE_H
#define CGAL_KINETIC_HEAP_POINTER_EVENT_QUEUE_H
#include <CGAL/Kinetic/basic.h>
#include <iostream>
#include <vector>
#include <utility>
#include <functional>
#include <CGAL/assertions.h>
#include <iostream>
#include <CGAL/Kinetic/Ref_counted.h>
#include <CGAL/Kinetic/internal/infinity_or_max.h>
#include <algorithm>

CGAL_KINETIC_BEGIN_INTERNAL_NAMESPACE

template <class Priority>
class Heap_pointer_event_queue_item_handle;

// The interface for an item stored in the ::Heap_pointer_event_queue
template <class Priority>
class Heap_pointer_event_queue_item: public Ref_counted<Heap_pointer_event_queue_item<Priority> >
{
  typedef Ref_counted<Heap_pointer_event_queue_item<Priority> > 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<Priority>  Key;

  Heap_pointer_event_queue_item():bin_(-1), time_(infinity_or_max<Priority>(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 Priority>
class Heap_pointer_event_queue_item_handle: public Ref_counted<Heap_pointer_event_queue_item<Priority> >::Handle
{
  typedef typename Ref_counted<Heap_pointer_event_queue_item<Priority> >::Handle P;
public:
  std::ostream &write(std::ostream &out) const {
    return P::operator*().write(out);
  }
  template <class T>
  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 Priority>
class Heap_pointer_event_queue_dummy_item: public Heap_pointer_event_queue_item<Priority>
{
  typedef Heap_pointer_event_queue_item<Priority> 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 Priority, class Event>
class Heap_pointer_event_queue_item_rep: public internal::Heap_pointer_event_queue_item<Priority>
{
  typedef internal::Heap_pointer_event_queue_item<Priority> P;
public:
  //typedef CGAL::Ref_counted_pointer<Heap_pointer_event_queue_item_rep<Priority, Event> > Pointer;
  //typedef CGAL::Ref_counted_pointer<const Heap_pointer_event_queue_item_rep<Priority, Event> > Const_pointer;
  Heap_pointer_event_queue_item_rep(): internal::Heap_pointer_event_queue_item<Priority>(){}
  Heap_pointer_event_queue_item_rep(const Priority &t, const Event &e,
                                    unsigned int bin): internal::Heap_pointer_event_queue_item<Priority>(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_;
};

CGAL_KINETIC_END_INTERNAL_NAMESPACE

CGAL_KINETIC_BEGIN_NAMESPACE

template <class Priority> class Bin_pointer_event_queue;


template <class FK, bool INF=false>
class Heap_pointer_event_queue
{
public:
  typedef typename FK::Root Priority;
  friend class Bin_pointer_event_queue<Priority>;
  typedef Heap_pointer_event_queue<Priority> This;
  typedef internal::Heap_pointer_event_queue_item<Priority> 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;


  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;

  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<Priority>());
  }

  Heap_pointer_event_queue(const Priority&, FK, int sz=1000) {
    queue_.reserve(sz);
    null_event_= Key(new internal::Heap_pointer_event_queue_dummy_item<Priority>());
  }

  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<Item_handle>::const_iterator it= queue_.begin(); 
         it != queue_.end(); ++it) {
      (* it)->audit(Key(*it));
    }
  }

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


  template <class E>
  Key insert(const Priority &t, const E & e) {
    if (!is_after_end(t)) {
      Item_handle k= new internal::Heap_pointer_event_queue_item_rep<Priority, E>(t, e, queue_.size());
      queue_.push_back(k);
      bubble_up(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_;
    }
  }

  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<unsigned int> (bin) < queue_.size() && bin >= 0);

    // this is a bit more work than strictly necessary
    swap(queue_.size()-1, bin);
    queue_.pop_back();
    if (static_cast<unsigned int>(bin) < queue_.size()) {
      bubble(bin);
    }
    item->set_bin(-1);
    CGAL_expensive_postcondition(is_valid());
  }


  /*
    template <class E>
    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(){}

    };
    };*/


  /*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();
  }


  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];
  }


  Priority front_priority() const
  {
    CGAL_precondition(!queue_.empty());
    return queue_.front()->time();
  }

  const Priority& priority(const Key &item) const
  {
    CGAL_precondition(item);
    return item->time();
  }

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

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




  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();
      }*/
  }

  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);
    }
    }*/

  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);
  }


  Key front() const {
    return Key(queue_.front());
  }


protected:
  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;
  }

  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);
  }

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

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

  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]);
    }
  }
  bool less_than_child(unsigned int  i, unsigned int c) const
  {
    int ch= child(i,c);
    return less_items(i, ch);
  }
  bool less_than_parent(unsigned int i) const
  {
    if (i==0) return false;
    else return less_items(i, parent(i));
  }

  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);
  }

  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;
      }
    }
  }
  void bubble_up(unsigned int i) {
    CGAL_expensive_precondition(i< queue_.size());
    while (less_than_parent(i)) {
      swap(i, parent(i));
      i=parent(i);
    }
  }
  void bubble(unsigned int i) {
    bubble_up(i);
    bubble_down(i);
  }

  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