SPAR/AIModule/BWTA/vendors/CGAL/CGAL/Kinetic/Two_list_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/Two_list_pointer_event_queue.h $
// $Id: Two_list_pointer_event_queue.h 41341 2007-12-27 16:23:41Z spion $
// 
//
// Author(s)     : Daniel Russel <drussel@alumni.princeton.edu>

#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_error();
    CGAL_ERROR("Writing dummy queue element.");
  }
  virtual CGAL::Comparison_result compare_concurrent(Key , Key ) const {
    CGAL_error();
    return CGAL::EQUAL;
  };
  virtual bool merge_concurrent(Key , Key ) {
    CGAL_error();
    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_error();
  }
  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





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;




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

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


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



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


  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
      unmake_event(oi);
      return Key(ni);
    }
    // unreachable

  }


  const Priority& front_priority() const
  {
    CGAL_precondition(!front_.empty());
    return front_.front().time();
  }


  Key front() const
  {
    CGAL_precondition(!front_.empty());
    return Key(const_cast<Item*>(&front_.front()));
  }

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

  bool empty() const
  {
    CGAL_precondition(!front_.empty() || back_.empty());
    return front_.empty() 
      || CGAL::compare(front_.front().time(), end_priority()) == CGAL::LARGER;
  }


  void process_front() {
    CGAL_precondition(!empty());
    CGAL_expensive_precondition(audit());
    if (!front_.empty()) {
      Item *i= &front_.front();
      CGAL_LOG(Log::SOME, "Processing event " << *i << std::endl);
      front_.pop_front();
      CGAL_expensive_postcondition(audit());
      if (front_.empty() && !back_.empty()) grow_front();
      i->process();

      /*if (!front_.empty() && i->time() == front_.front().time()) {
        CGAL_LOG(Log::SOME, "Degeneracy at time "
        << i->time() << " the events are: "
        << *i << " and " << front_.front() << std::endl);
        }*/

      unmake_event(i);
    }
    else {
      CGAL_assertion(back_.empty());
    }
  }

  bool print() const
  {
    write(std::cout);
    return true;
  }

  void write(const Queue &q, std::ostream& out) const {
    for (typename Queue::const_iterator it = q.begin(); it != q.end(); ++it) {
      out << "(" << &*it << ": " << *it << ")";
      out << std::endl;
    }
  }

  bool write(std::ostream &out) const
  {
    write(front_, std::cout);
    out << "--" << ub_ << "--" << std::endl;
    write(back_, std::cout);
    out << std::endl;
    return true;
  }

  Key end_key() const
  {
    return null_event_;
  }

  

  const Priority& end_priority() const
  {
    return end_time_;
  }


  void set_interval(const Priority &start_time, const Priority &end_time) {
    CGAL_precondition(!INF);
    initialize(start_time, end_time);
  }
  
  void audit_events() const {
    for (typename Queue::const_iterator it= front_.begin(); it != front_.end(); ++it) {
      it->audit(Key(const_cast<Item*>(&*it)));
    }
    for (typename Queue::const_iterator it= back_.begin(); it != back_.end(); ++it) {
      it->audit(Key(const_cast<Item*>(&*it)));
    }
  }

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

  void clear() {
    front_.clear();
    back_.clear();
    //all_in_front_=false;
  }

protected:
  void initialize(const Priority &start_time, const Priority &end_time) {
    ub_=CGAL::to_interval(start_time).second;
    // should be nextafter
    step_=1;
    //all_in_front_= false;
    end_time_=end_time;
  }

 void initialize(const Priority &start_time) {
   CGAL_precondition(INF);
   ub_=CGAL::to_interval(start_time).second;
    // should be nextafter
   step_=1;
    //all_in_front_= false;
  }
  bool leq_ub(const Priority &t) const {
    //if (all_in_front_) return true;
    //else 
    // pretty much anything fast will have a fast to_interval, so use it
    std::pair<double,double> iv= CGAL::to_interval(t);
    if (iv.first > ub_) {
      return false;
    } else if (iv.second <= ub_) {
      return true;
    } else {
      return CGAL::compare(t, Priority(ub_)) != CGAL::LARGER;
    }
  }

 
  template <class E>
  Item *make_event(const Priority &t, E &e) {
    typedef typename boost::remove_const<E>::type NCE;
    Item *ni
      = new internal::Two_list_event_queue_item_rep<Priority, NCE>(t, e);
    intrusive_ptr_add_ref(ni);
    return ni;
  }

  void unmake_event(Item *i) {
    intrusive_ptr_release(i);
  }

  bool audit() {
    for (typename Queue::const_iterator it = front_.begin(); it != front_.end(); ++it) {
      Priority t= it->time();
      CGAL_assertion(leq_ub(t));
      CGAL_assertion(it->in_list()== Item::FRONT);
      //CGAL_exactness_assertion(t >= lb_);
    }
    for (typename Queue::const_iterator it = back_.begin(); it != back_.end(); ++it) {
      Priority t= it->time();
      CGAL_assertion(!leq_ub(t));
      CGAL_assertion(it->in_list()== Item::BACK);
    }
#ifndef NDEBUG
    for (unsigned int i=0; i< inf_.size(); ++i) {
      Priority t= inf_[i]->time();
      CGAL_assertion(INF || CGAL::compare(t, end_priority())== CGAL::LARGER);
      CGAL_assertion(inf_[i]->in_list() == Item::INF);
    }
#endif
    {
      typename Queue::const_iterator it = front_.begin();
      ++it;
      for (; it != front_.end(); ++it) {
        Priority tc= it->time();
        Priority tp= boost::prior(it)->time();
#ifndef NDEBUG
        if (CGAL::compare(tc, tp) == CGAL::SMALLER) {
          std::cout << "ERROR: Out of order " << tc << std::endl << tp << std::endl << std::endl;
          ++internal::audit_failures__;
        }
#endif
        //CGAL_assertion(tc >= tp);
      }
    }
    return true;
  }
public:
  bool contains(const Key k) const
  {
    //if (k.pointer()->time() == std::numeric_limits<Priority>::infinity()) return true;
    for (typename Queue::const_iterator it = front_.begin(); it != front_.end(); ++it) {
      if (&*it == k.pointer()) return true;
    }
    for (typename Queue::const_iterator it = back_.begin(); it != back_.end(); ++it) {
      if (&*it == k.pointer()) return true;
    }
#ifndef NDEBUG
    for (unsigned int i=0; i< inf_.size(); ++i) {
      const Key j=inf_[i];
      const Key ki= k;
      if (j==ki) return true;
    }
#else
    if (k.pointer()->in_list() == Item::INF) return true;
#endif
    return false;
  }
protected:
  unsigned int select(Queue &source, Queue &target/*, bool binf*/) {
    CGAL_assertion_code(unsigned int sz= source.size() + target.size();)
    int count=0;
    Iterator it= source.begin();
    while (it != source.end()) {
      // CGAL_assertion(it->time() >= a);
    
      if (leq_ub(it->time())) {
        Item *i= &*it;
        Iterator t= boost::next(it);
        source.erase(it);
        it=t;
        target.push_back(*i);
        ++count;
      }
      else {
        ++it;
      }
    }
    CGAL_assertion(sz==source.size() + target.size());
    return count;
  }

  /*NT step() const{
    return (std::max)(ub_-lb_, NT(1));
    }*/

  NT av(NT a, NT b) const
  {
    return .5*(a+b);
  }

  template <class It>
  void set_front(It b, It e, typename Item::List val) {
    for (; b!= e; ++b) {
      b->set_in_list(val);
    }
  }
  template <class C, class It>
  void make_inf(C &c, It b, It e) {
    for (It cit = b; cit != e; ++cit) {
      CGAL_assertion(INF || CGAL::compare(cit->time(), end_priority()) == CGAL::LARGER);
      //std::cout << "Dropping inf event " << &*cit << std::endl;
#ifndef NDEBUG
      inf_.push_back(&*cit);
#endif
      cit->set_in_list(Item::INF);
      It p= boost::prior(cit);
      c.erase(cit);
      unmake_event(&*cit);
      cit=p;
    }
    //c.erase(b, e);
  }

  void grow_front(Queue &cand, int recursive_count=0) {
    const bool dprint=false;
    CGAL_assertion(front_.empty());
    CGAL_assertion(!cand.empty());
    //CGAL_assertion(!all_in_front_);
    CGAL_assertion(step_ != 0);
    if (dprint) std::cout << "Growing front from " << ub_ << " with step " 
                          << step_ << "(" << recursive_count << ") ";

    //CGAL_assertion(ub_<end_split());
    if (cand.size() + front_.size() < max_front_size()) {
      if (dprint) std::cout << "Setting ub to end of " << end_time_ << std::endl;
      front_.splice(front_.end(), cand);
      return;
    }

    //CGAL_assertion(!too_big(ub_));

    /*if ( CGAL::compare(end_priority(), Priority(ub_)) == CGAL::SMALLER) {
      all_in_front_=true;
      //ub_=end_split();
      }*/

    CGAL_assertion_code(unsigned int num=)
      select(cand, front_/*, all_in_front_*/);
    CGAL_assertion(front_.size() >= num);
    /*if (all_in_front_) {
      make_inf(cand, cand.begin(), cand.end());
      } else*/
    if (front_.empty()) {
      if (recursive_count > 10) {
        // do something
        std::cerr << "Too many recursions " << std::endl;
        //all_in_front_=true;
        ub_=CGAL::to_interval(end_time_).second; //CGAL::to_interval(end_time_).second*2;// std::numeric_limits<double>::infinity();
        /*unsigned int num=*/ select(cand, front_/*, all_in_front_*/);
        select(back_, front_);
        make_inf(cand, cand.begin(), cand.end());
        make_inf(back_, back_.begin(), back_.end());
        //grow_front(cand, recursive_count+1);
      } else {
        if (dprint) {
          std::cout << "undershot." << std::endl;
          write(front_, std::cout);
          std::cout << "-- " << ub_ << "--\n";
          write(cand, std::cout);
          std::cout << "--\n";
          write(back_, std::cout);
        }
        ub_+= step_;
        step_*=2.0;
        CGAL_assertion(step_!=0);
        cand.splice(cand.end(), back_);
        grow_front(cand, recursive_count+1);
      }
    } else {
      //      unsigned int ncand= cand.size();
      back_.splice(back_.begin(), cand);
      if (front_.size() >  max_front_size()) {
        if (recursive_count > 10) {
          //std::cerr << "Gave up on isolating front. Let with size " << front_.size() << " ub=" << ub_ << "step=" << step_ <<  "\n";
          return;
        } else {
          // keep the bit length shortish
          double frac= .75+.25*max_front_size()/static_cast<double>(front_.size()+1);
          double ostep= step_;
          CGAL_assertion(frac < 1.1);
          CGAL_assertion(frac >= 0.0);
          //double rfrac= std::ceil(frac*256.0)/256.0;
          step_*=frac;
          //else nstep = step_*.6;
          //CGAL_assertion(nstep >0);
          cand.swap(front_);
          //ub_=lb_;
          if (step_ == 0) {
            CGAL_ERROR( "underflow in queue ");
            CGAL_ERROR_WRITE(write(LOG_STREAM));
            CGAL_assertion(cand.empty());
            step_=.0000001;
            return;
          } else {
            //CGAL_assertion(!all_in_front_);
            
            if (dprint) {
              std::cout << "...overshot" << std::endl;
              write(front_, std::cout);
              std::cout << "-- " << ub_ << "(" <<step_ << ")" << "--\n";
              write(cand, std::cout);
              std::cout << "--\n";
              write(back_, std::cout);
            }
            ub_=ub_-ostep+step_;  
            grow_front(cand, recursive_count+1);
          }
        }
      }
      else {
        if (dprint) std::cout << std::endl;
      }
    }
    CGAL_postcondition(cand.empty());
  }

  void grow_front() {
    //++growth__;
    //std::cout << "Growing front from " << ub_ << std::endl;
    //CGAL_assertion(is_valid());
    CGAL_precondition(!back_.empty());
    CGAL_precondition(front_.empty());
    CGAL_assertion_code(unsigned int sz= front_.size()+back_.size()+ inf_.size());
    Queue cand;
    cand.splice(cand.begin(), back_);
    ub_ += step_;
    grow_front(cand);
    set_front(front_.begin(), front_.end(), Item::FRONT);
    front_.sort();
    ub_= CGAL::to_interval(front_.back().time()).second;
    // hmmmm, now I should make a second pass to merge. Ick.

    CGAL_assertion(sz==front_.size()+back_.size() + inf_.size());
    CGAL_assertion(audit());
    //std::cout << "to " << ub_ << std::endl;
  }

  void shrink_front() {
    //++shrink__;
    //std::cout << "Shrinking front from " << ub_ << std::endl;
    typename Queue::iterator it=front_.begin();
    unsigned int mf= max_front_size();
    for (unsigned int i=0; i < mf; ++i) {
      ++it;
    }

    // use tii_ so that it does not subdivide

    double split =  CGAL::to_interval(it->time()).second;
    if (!INF && (CGAL::compare(end_priority(), it->time())==CGAL::SMALLER
                 || CGAL::compare(end_priority(), Priority(split))==CGAL::SMALLER)) {
      std::cout << "Past end in Queue " << end_priority() << ", "
                << it->time() << ", " << Priority(split) << std::endl;
      //all_in_front_=true;
      ub_= CGAL::to_interval(end_time_).second;
      set_front(back_.begin(), back_.end(), Item::FRONT);
      front_.splice(front_.end(), back_);

      while (it != front_.end()) {
        if (CGAL::compare(it->time(), end_priority())==CGAL::LARGER) break;
      }
      set_front(it, front_.end(), Item::INF);
      std::vector<Item*> temp;
      for (typename Queue::iterator c= it; c != front_.end(); ++c) {
        temp.push_back(&*c);
#ifndef NDEBUG
        inf_.push_back(&*c);
#endif
        //std::cout << "Dropping inf event " << &*c << std::endl;
      }
      front_.erase(it, front_.end());

   
    
      for (unsigned int i=0; i< temp.size(); ++i) {
        unmake_event(temp[i]);
      }
    } else {
      while (CGAL::compare(it->time(), Priority(split)) != CGAL::LARGER
             && it != front_.end()) ++it;
      
      if (it != front_.end()) {
        
        set_front(it, front_.end(), Item::BACK);
        back_.splice(back_.begin(), front_, it, front_.end());
        double oub=ub_;
        //all_in_front_=false;
        ub_ = split;
        //CGAL_assertion(!too_big(ub_));
        //CGAL_assertion(ub_ <= end_split());
        step_= std::abs(ub_-oub);
        if (step_<=0) {
          /*if (dprint) std::cout << "fixing step since " << oub 
            << " equals new bound" << std::endl;*/
          CGAL_ERROR("Roundoff error in split " << split << " " << ub_ << " "
                             <<  oub);
          step_=.00001;
        }
        //CGAL_assertion(!all_in_front_);
        /*CGAL_postcondition_code(if (step_<0) std::cerr << step_ << std::endl;);
        CGAL_postcondition_code(if (step_<0) std::cerr << ub_ << std::endl;);
        CGAL_postcondition_code(if (step_<0) std::cerr << oub << std::endl;);
        CGAL_postcondition_code(if (step_<0) std::cerr << front_.back().time() << std::endl;);
        CGAL_postcondition_code(if (step_==0) for (typename Queue::const_iterator it=front_.begin(); it != front_.end(); ++it) std::cout << *it << std::endl);
        CGAL_postcondition(step_>=0);*/
      }
    }
  }

  /*NT end_split() const
    {
    return end_split_;
    }*/

  /*const Priority& end_time() const
    {
    return end_time_;
    }*/

  unsigned int max_front_size() const
  {
    return TARGET;
    //return (std::max)(4U, static_cast<unsigned int>(std::sqrt(static_cast<double>(front_.size()+back_.size()))));
  }

  //typename FK::To_isolating_interval tii_;
  Queue front_, back_;
#ifndef NDEBUG
  std::vector<Key> inf_;
#endif
  double ub_;
  double step_;
  //bool all_in_front_;
  Priority end_time_;
  Key null_event_;
  //NT end_split_;
};

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


CGAL_KINETIC_END_NAMESPACE
#endif