two_list_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/Two_list_pointer_event_queue.h $
// $Id: Two_list_pointer_event_queue.h 37472 2007-03-26 08:22:12Z afabri $
// 
//
// Author(s)     : Daniel Russel <[e-mail]>

#ifndef CGAL_KINETIC_BIN_QUEUE_H
#define CGAL_KINETIC_BIN_QUEUE_H
#include <CGAL/Kinetic/basic.h>
#include <iostream>
#include <CGAL/Kinetic/internal/debug_counters.h>
#include <CGAL/In_place_list.h>
#include <functional>
#include <CGAL/assertions.h>
#include <iostream>
#include <CGAL/Kinetic/Ref_counted.h>
#include <CGAL/Kinetic/internal/infinity_or_max.h>
#include <algorithm>
#include <boost/utility.hpp>
#include <boost/type_traits/remove_const.hpp>
#include <CGAL/Kinetic/internal/debug_counters.h>

//int two_list_remaining=0;

//int growth__=0;
//int shrink__=0;
//int queue_insertions__=0;
//int queue_front_insertions__=0;

CGAL_KINETIC_BEGIN_INTERNAL_NAMESPACE


template <class Item>
struct Two_list_pointer_event_queue_key: public Item::Handle
{
  typedef Two_list_pointer_event_queue_key<Item> This;
  typedef typename Item::Handle P;
  Two_list_pointer_event_queue_key(){};
  Two_list_pointer_event_queue_key(Item  *p): Item::Handle(p){}
  std::ostream& write(std::ostream &out) {
    if (Item::Handle::get()) {
      out << "(" << Item::Handle::get() << ": " << *Item::Handle::get() << ")";
    }
    else {
      out << "null";
    }
    return out;
  }
  /*operator bool() const
    {
    return Item::Handle::get() != NULL;
    }*/
  bool is_valid() const {
    return  Item::Handle::get() != NULL;
  }
  /*bool operator!() const
    {
    return Item::Handle::operator!();
    }*/
  bool operator==(const This &o) const
  {
    return Item::Handle::get() == o.get();
  }
  bool operator!=(const This &o) const
  {
    return Item::Handle::get() != o.get();
  }
  //using P::operator<;
  bool operator<(const This& o) const
  {
    return P::get() < o.get();
  }

  Item* pointer() {
    return Item::Handle::get();
  }
  const Item* pointer() const
  {
    return Item::Handle::get();
  }
 
  //using P::operator>;
};

template  <class I>
std::ostream &operator<<(std::ostream &out, Two_list_pointer_event_queue_key<I> k)
{
  k.write(out);
  return out;
}




// The interface for an item stored in the ::Pointer_event_queue
template <class Priority>
class Two_list_event_queue_item:
  public CGAL::In_place_list_base<Two_list_event_queue_item<Priority> >,
  public Ref_counted<Two_list_event_queue_item<Priority> >
{

  typedef Two_list_event_queue_item<Priority> This;

  Two_list_event_queue_item(const Two_list_event_queue_item &o){bool do_not_copy;}
  void operator=(const Two_list_event_queue_item &o) {
    bool do_not_copy;
  }
public:
  typedef Two_list_pointer_event_queue_key<This> Key;
  Two_list_event_queue_item() { /*++two_list_remaining;*/}
  Two_list_event_queue_item(const Priority &t): time_(t){/*++two_list_remaining;*/}
  virtual ~Two_list_event_queue_item(){/*--two_list_remaining;*/
  }

  enum List {FRONT, BACK, INF};

  const Priority& time() const {return time_;};

  List in_list() const
  {
    return front_list_;
  }
  void set_in_list(List lt) {
    front_list_=lt;
  }

  

  bool operator<(const This &o) const {
    CGAL::Comparison_result c= CGAL::compare(time(), o.time());
    if (c != CGAL::EQUAL) return c== CGAL::SMALLER;
    else {
      if (kds() < o.kds()) return true;
      else if (kds() > o.kds()) return false;
      else {
	CGAL::Comparison_result c= compare_concurrent(Key((This*) this),Key((This*) &o));
	return c==CGAL::SMALLER;
      }
    }
  }

  virtual std::ostream& write(std::ostream &out) const{
    out << "Dummy event." << std::endl;
    return out;
  }
  virtual void process() {
    CGAL_assertion(0);
    CGAL_KINETIC_ERROR("Writing dummy queue element.");
  }
  virtual CGAL::Comparison_result compare_concurrent(Key , Key ) const {
    CGAL_assertion(0);
    return CGAL::EQUAL;
  };
  virtual bool merge_concurrent(Key , Key ) {
    CGAL_assertion(0);
    return false;
  }
  virtual void *kds() const{return NULL;}
  virtual void audit(Key) const{};
private:
  Priority time_;
  List front_list_;
};

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


// The how a dummy item is stored in the ::Two_list_event_queue
/*
  One dummy item is used to represent events which will never happen.
*/
/*template <class Priority>
class Two_list_event_queue_dummy_item: public Two_list_event_queue_item<Priority>
{
  typedef Two_list_event_queue_item<Priority> P;
public:
  Two_list_event_queue_dummy_item(){}
  Two_list_event_queue_dummy_item(const Two_list_event_queue_dummy_item &):
    Two_list_event_queue_item<Priority>(){}
  virtual void process() {
    std::cerr << "Trying to process a NULL event.\n";
    CGAL_assertion(0);
  }
  virtual CGAL::Comparison_result compare_concurrent(typename P::Key , typename P::Key ) const{return CGAL::EQUAL;}
  virtual bool merge_concurrent(typename P::Key, typename P::Key){
    return false;
  }
  virtual std::ostream& write(std::ostream &out) const
  {
    out << "Never";
    return out;
  }
  virtual ~Two_list_event_queue_dummy_item(){}
  };*/

// The how a real item is stored in the ::Two_list_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 Two_list_event_queue_item_rep: public internal::Two_list_event_queue_item<Priority>
{
  typedef  Two_list_event_queue_item<Priority> P;
public:
  Two_list_event_queue_item_rep(): internal::Two_list_event_queue_item<Priority>(){}
  Two_list_event_queue_item_rep(const Priority &t, const Event &e): 
    Two_list_event_queue_item<Priority>(t),
    event_(e){}

  virtual std::ostream& write(std::ostream &out) const
  {
    event_.write(out);
    out << " at " << P::time();
    return out;
  }
  virtual void process() {
    event_.process();
  }
  virtual void audit(typename P::Key k) const {
    event_.audit(k);
  }
  virtual CGAL::Comparison_result compare_concurrent(typename P::Key a, typename P::Key b) const{
    return event_.compare_concurrent(a,b);
  }
  virtual bool merge_concurrent(typename P::Key a, typename P::Key b){
    return event_.merge_concurrent(a,b);;
  }
  virtual void *kds() const{return event_.kds();}

  // Access the actual event
  const Event &event() const
  {
    return event_;
  }

 // Access the actual event
  Event &event()
  {
    return event_;
  }
  
  virtual ~Two_list_event_queue_item_rep(){}

protected:
  Event event_;
};


/* This is needed since the list cannot allocate an element of the abstract base class. I could just make it non-abstract. Why not?*/
/*template <class T>
struct Two_list_event_queue_item_allocator
{
  typedef Two_list_event_queue_dummy_item<T> dummy_value_type;

  typedef Two_list_event_queue_item<T>* pointer;
  typedef std::size_t size_type;
  typedef std::ptrdiff_t difference_type;
  typedef const pointer const_pointer;
  typedef Two_list_event_queue_item<T>& reference;
  typedef const Two_list_event_queue_item<T>& const_reference;
  typedef dummy_value_type value_type;

  Two_list_event_queue_item_allocator(){}
  pointer allocate(size_t sz, void* =0) const
  {
    return static_cast<pointer>(::operator new(sz*sizeof(dummy_value_type)));
  }
  void deallocate(pointer p, size_type ) {
    ::operator delete(static_cast<void*>(p));
  }
  size_type max_size() const throw() {
    return (std::numeric_limits<size_type>::max)()/sizeof(dummy_value_type);
  }
  template <class TT>
  void construct(pointer p, const TT &) {
    new(static_cast<void*>(p)) dummy_value_type();
  }
  void destroy(pointer p) {
    p->~Two_list_event_queue_item<T>();
  }
  };*/

CGAL_KINETIC_END_INTERNAL_NAMESPACE

CGAL_KINETIC_BEGIN_NAMESPACE




//! 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, unsigned int TARGET=8>
class Two_list_pointer_event_queue
{
  typedef typename FK::Root PriorityT;
  typedef typename FK::FT NT;
  typedef Two_list_pointer_event_queue<FK, INF, TARGET> This;
  typedef typename internal::Two_list_event_queue_item<PriorityT> Item;

  typedef typename CGAL::In_place_list<Item, false/*,
						    internal::Two_list_event_queue_item_allocator<PriorityT>*/ > Queue;
  typedef typename Queue::iterator Iterator;




public:
  typedef PriorityT Priority;

  typedef internal::Two_list_pointer_event_queue_key<Item> Key;




  //! Construct it with a suggested size of sz.
  Two_list_pointer_event_queue(Priority start_time,
			       Priority end_time, 
			       FK, int =0):
    null_event_(new internal::Two_list_event_queue_item<Priority>()){
    CGAL_precondition(!INF);
    initialize(start_time, end_time);
  }

 //! Construct it with a suggested size of sz.
  Two_list_pointer_event_queue(Priority start_time,
			       FK, int =0): 
    null_event_(new internal::Two_list_event_queue_item<Priority>()){
    CGAL_precondition(INF);
    initialize(start_time);
  }

  ~Two_list_pointer_event_queue() {
    // release pointers
    std::vector<Key> all;
    all.reserve(front_.size()+back_.size());
    for (typename Queue::iterator it = front_.begin(); 
	 it != front_.end(); ++it) {
      all.push_back(Key(&*it));
    }
    for (typename Queue::iterator it = back_.begin(); 
	 it != back_.end(); ++it) {
      all.push_back(Key(&*it));
    }
    front_.clear();
    back_.clear();
    for (unsigned int i=0; i< all.size(); ++i) {
      unmake_event(all[i].get());
    }
  }

  
  /*template <class E>
  Key insert_at_end(const E & e) {

  }*/
  

  bool is_after_end(const Priority &t) const {
    if (INF) return false; 
    else return  CGAL::compare(t,end_priority()) == CGAL::LARGER;
  }

  //! 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) {
    CGAL_expensive_precondition(audit());
 

    Item *ni = make_event(t, e);

    //CGAL_exactness_assertion(t >= lbs_);
    //lb_=(std::min)(t, lb_);
    if ( is_after_end(ni->time())){
      return end_key();
    } 


    if (leq_ub(ni->time())) {
      ni->set_in_list(Item::FRONT);
      typename Queue::iterator iit=std::upper_bound(front_.begin(), front_.end(), *ni);
   
      front_.insert(iit, *ni);
      CGAL_expensive_assertion(audit());
      if (front_.size() > 2*max_front_size()) {
	shrink_front();
      }
      //++queue_front_insertions__;
    }  else if (front_.empty()) {
      CGAL_assertion(back_.empty());
      CGAL_assertion(INF || CGAL::compare(t, end_priority()) != CGAL::LARGER);
      //CGAL_assertion(INF || CGAL::compare(end_priority(), std::numeric_limits<Priority>::infinity()) == CGAL::SMALLER);
      if (true){
	//++queue_front_insertions__;
	front_.push_back(*ni);
	ub_= CGAL::to_interval(t).second;
	ni->set_in_list(Item::FRONT);
      } 
    } else {
      ni->set_in_list(Item::BACK);
      back_.push_back(*ni);
    }
    CGAL_expensive_postcondition(audit());
    CGAL_expensive_postcondition(contains(Key(ni)));
    //std::cout << "Made event " << ni << std::endl;
    return Key(ni);
  }

  //! remove the event referenced by item from the queue
  /*!
    \todo Add check that item is actually in the list
  */
  void erase(const Key &item) {
    //std::cout << "Erase event " << item.pointer() << std::endl;
    if (item== end_key()) return;
#ifndef NDEBUG
    if (!contains(item)) {
      std::cerr << "Erasing event not in queue ";
      item->write(std::cerr);
      std::cerr << std::endl;
    }
#endif
    CGAL_expensive_precondition(contains(item));
    CGAL_expensive_precondition(audit());
    Item *i=item.get();
    if (item->in_list() == Item::FRONT) {
      front_.erase(i);
      if (front_.empty() && !back_.empty()) grow_front();
    }
    else if (item->in_list() == Item::BACK) {
      back_.erase(i);
    }
    if (item->in_list() == Item::FRONT || item->in_list() == Item::BACK) {
      unmake_event(i);
    }

    CGAL_expensive_postcondition(audit());
  }

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

  template <class E>
  E& get(const Key &item)  {
    return reinterpret_cast<internal::Two_list_event_queue_item_rep<Priority, E>*>( item.get())->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(contains(item));
    CGAL_precondition(item != end_key());
    Item *oi= item.get();
    typename Item::List front= item->in_list();
    Item *ni= make_event(item->time(), ne);
    ni->set_in_list(front);
    if (front != Item::INF) {
      if (front== Item::FRONT) {
	front_.insert(oi, *ni);
	front_.erase(oi);
      }
      else {
	back_.insert(oi, *ni);
	back_.erase(oi);
      }
      unmake_event(oi);
      return Key(ni);
    }
    else {
#ifndef NDEBUG
      bool found=false;
      for (unsigned int i=0; i< inf_.size(); ++i) {
	if (inf_[i].get() == oi) {
	  inf_[i]=ni;
	  found=true;
	  break;
	}
      }
      CGAL_postcondition(found);
#endif