heap_pointer_event_queue.h

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

// 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.3-branch/Kinetic_data_structures/include/CGAL/Kinetic/Heap_pointer_event_queue.h $
// $Id: Heap_pointer_event_queue.h 36638 2007-02-27 22:45:58Z drussel $
// 
//
// Author(s)     : Daniel Russel <[e-mail]>

#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

// 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 typename P::Handle 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 void 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_;
};

template <class Priority>
inline std::ostream& operator<<(std::ostream &out, const Heap_pointer_event_queue_item<Priority> &i)
{
  i.write(out);
  return i;
}


// 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 void write(std::ostream &out) const
  {
    out << "Never.";
  }
  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 void write(std::ostream &out) const
  {
    out << "(";
    event_.write(out);
    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;

//! 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 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_assertion(0);
	    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<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);
  }

  //! insert value_type into the queue and return a reference to it
  /*!
    The reference can be used to update or erase it.
  */
  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_;
    }
  }

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

  //! The pointer type to use to access an event of type E.

  /*
    template <class E>