--- a/.issues/ebda8db3f9908e33/new/1221008555.M637662P30017Q16.cole	Sat Feb 06 23:22:43 2010 -0800
+++ b/.issues/ebda8db3f9908e33/new/1221008555.M637662P30017Q16.cole	Sun Feb 07 10:46:23 2010 -0800
@@ -1,8 +1,9 @@
 From: Dmitriy Morozov <morozov@cs.duke.edu>
 Date: Mon, 25 Feb 2008 11:29:27 -0500
-State: new
+State: resolved
 Subject: Efficient EventQueue
 Message-Id: <ebda8db3f9908e33-0-artemis@metatron>
 category: kinetic
+resolution: fixed
 
 Change EventQueue to an efficient implementation, e.g., using a Fibonacci heap.

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/.issues/ebda8db3f9908e33/new/1265568370.M269870P17954Q1.vine	Sun Feb 07 10:46:23 2010 -0800
@@ -0,0 +1,9 @@
+From: Dmitriy Morozov <dmitriy@mrzv.org>
+Date: Sun, 07 Feb 2010 10:45:04
+Subject: Switched to Boost's MultiIndex
+Message-Id: <ebda8db3f9908e33-e9c51216e26b5e19-artemis@vine>
+References: <ebda8db3f9908e33-0-artemis@metatron>
+In-Reply-To: <ebda8db3f9908e33-0-artemis@metatron>
+
+Switched EventQueue to Boost's MultiIndex with a sequence and ordered_non_unique
+indexing.

--- a/include/geometry/kinetic-sort.hpp	Sat Feb 06 23:22:43 2010 -0800
+++ b/include/geometry/kinetic-sort.hpp	Sun Feb 07 10:46:23 2010 -0800
@@ -127,6 +127,8 @@
 	typedef 		typename Simulator::Function		        Function;
 	typedef 		typename Simulator::Time					Time;
 	
+    AssertMsg(simulator->audit_queue(), "Simulator's queue should be properly ordered");
+
 	Time t = simulator->audit_time();
 	rLog(rlKineticSortAudit, "Auditing at %s", tostring(t).c_str());
 
@@ -202,7 +204,6 @@
 	//std::cout << "Difference:         " << next_trajectory - i_trajectory << std::endl;
 
 	i->swap_event_key = simulator->add(next_trajectory - i_trajectory, SwapEvent(this, i));
-	//i->swap_event_key = simulator->add(next_trajectory, SwapEvent(this, i));
 }
 
 /* SwapEvent */

--- a/include/geometry/simulator.h	Sat Feb 06 23:22:43 2010 -0800
+++ b/include/geometry/simulator.h	Sun Feb 07 10:46:23 2010 -0800
@@ -36,6 +36,7 @@
 
                                     Simulator(Time start = FunctionKernel::root(0)):
                                         current_(start)                         {}
+                                    ~Simulator()                                { for (Key cur = queue_.top(); cur != queue_.end(); ++cur) delete *cur; }
 
 
         template<class Event_> 
@@ -45,7 +46,7 @@
         void                        process();
         void                        update(Key k, const Function& f);
         
-        void                        remove(Key k)                               { queue_.remove(k); }
+        void                        remove(Key k)                               { Event* e = *k; queue_.remove(k); delete e; }
         Key                         null_key()                                  { return queue_.end(); }
 
         Time                        current_time() const                        { return current_; }
@@ -57,10 +58,9 @@
         unsigned                    size() const                                { return queue_.size(); }
         unsigned                    event_count() const                         { return count_; }
 
-        std::ostream&               operator<<(std::ostream& out) const;
+        bool                        audit_queue() const;
 
-    private:
-        void                        update(Key i);
+        std::ostream&               operator<<(std::ostream& out) const;
 
     private:
         Time                        current_;

--- a/include/geometry/simulator.hpp	Sat Feb 06 23:22:43 2010 -0800
+++ b/include/geometry/simulator.hpp	Sun Feb 07 10:46:23 2010 -0800
@@ -39,14 +39,18 @@
 
 	while (!ee->root_stack().empty() && ee->root_stack().top() < current_time())
 	{
+        // rLog(rlSimulator, "Popping expired root: %f", ee->root_stack().top());
 		ee->root_stack().pop();
 		sign *= -1;
 	}
+
     if (sign == -1)
     {
-        //AssertMsg(ee->root_stack().top() == current_time(), 
-        //          "If sign is negative, we must be in the degenerate case");
         rLog(rlSimulator, "Popping the root because of negative sign (degeneracy)");
+        // rLog(rlSimulator, "Popping the root because of negative sign (degeneracy): %f", ee->root_stack().top());
+        // rLog(rlSimulator, "  Current time: %f", current_time());
+        // AssertMsg(ee->root_stack().top() == current_time(), 
+                 // "If sign is negative, we must be in the degenerate case");
         ee->root_stack().pop();
     }
 
@@ -57,7 +61,8 @@
         rLog(rlSimulator, "Root stack size: %i", ee->root_stack().size());
         rLog(rlSimulator, "Pushing: %s", tostring(ee->root_stack().top()).c_str());
     }
-	return queue_.push(ee);
+	Key k = queue_.push(ee);
+    return k;
 }
 		
 template<class FuncKernel_, template<class Event> class EventComparison_>
@@ -70,7 +75,7 @@
 	FunctionKernel::solve(f, ee->root_stack());
 	while (!ee->root_stack().empty() && ee->root_stack().top() < current_time())
 		ee->root_stack().pop();
-	update(k);
+	queue_.update(k);
 }
 
 template<class FuncKernel_, template<class Event> class EventComparison_>
@@ -86,23 +91,13 @@
     rLog(rlSimulator, "Processing event: %s", intostring(*e).c_str());
 	
 	current_ = e->root_stack().top(); e->root_stack().pop();
-	
+    queue_.update(top);
+
     // Get the top element out of the queue, put it back depending on what process() says
-    EventQueueS             tmp; tmp.prepend(top, queue_);
-
-	if (e->process(this))				{ queue_.prepend(top, tmp); update(top); }
-	else								{ delete e; }
+	if (!(e->process(this)))            { queue_.remove(top);  delete e; }
 
     ++count_;
 }
-
-template<class FuncKernel_, template<class Event> class EventComparison_>
-void
-Simulator<FuncKernel_, EventComparison_>::
-update(Key i)
-{
-	queue_.update(i);
-}
 		
 template<class FuncKernel_, template<class Event> class EventComparison_>
 typename Simulator<FuncKernel_, EventComparison_>::Time
@@ -115,6 +110,27 @@
 	if (e->root_stack().empty()) return current_ + 1;
 	else return FunctionKernel::between(e->root_stack().top(), current_);
 }
+
+template<class FuncKernel_, template<class Event> class EventComparison_>
+bool
+Simulator<FuncKernel_, EventComparison_>::
+audit_queue() const
+{
+	const_Key next = queue_.top();
+    const_Key cur = next++;
+	        
+    while (next != queue_.end())
+    {
+        if (IndirectEventComparison()(*next, *cur))
+        {
+            rError("Events [%s] and [%s] not in order", intostring(**cur).c_str(), intostring(**next).c_str());
+            queue_.print(std::cout, "  ");
+            return false;
+        }
+        cur = next++;
+    }
+    return true;
+}
 		
 template<class FuncKernel_, template<class Event> class EventComparison_>
 std::ostream&

--- a/include/topology/lsvineyard.h	Sat Feb 06 23:22:43 2010 -0800
+++ b/include/topology/lsvineyard.h	Sun Feb 07 10:46:23 2010 -0800
@@ -153,6 +153,10 @@
 operator<<(std::ostream& out, const typename LSVineyard<V,VE,S,C>::VertexIndex& vi)    
 { return out << vi->vertex(); }
 
+template<class V, class VE, class S, class C>
+std::ostream& 
+operator<<(std::ostream& out, const typename LSVineyard<V,VE,S,C>::KineticVertexType& v)    
+{ return out << v.vertex(); }
 
 template<class V, class VE, class S, class C>
 class LSVineyard<V,VE,S,C>::KineticVertexType

--- a/include/topology/lsvineyard.hpp	Sat Feb 06 23:22:43 2010 -0800
+++ b/include/topology/lsvineyard.hpp	Sun Feb 07 10:46:23 2010 -0800
@@ -123,7 +123,6 @@
     KineticSortDS       sort(vertices_.begin(), vertices_.end(), 
                              boost::bind(&LSVineyard::swap, this, bl::_1, bl::_2),
                              &simulator, traj);
-    AssertMsg(sort.audit(&simulator), "Sort audit should succeed");
     
     // Process all the events (compute the vineyard in the process)
     change_evaluator(new KineticEvaluator(*this, simulator, time_count_, traj));
@@ -134,7 +133,7 @@
         rLog(rlLSVineyardDebug, "Processed event");
     }
     rLog(rlLSVineyard, "Processed %d events", simulator.event_count());
-    AssertMsg(sort.audit(&simulator), "Sort audit should succeed");
+    // AssertMsg(sort.audit(&simulator), "Sort audit should succeed");
     
     veval_ = veval;
     change_evaluator(new StaticEvaluator(*this, ++time_count_));
@@ -149,7 +148,7 @@
     VertexIndex b = boost::next(a);
     rLog(rlLSVineyardDebug, "Entered swap");
     rLog(rlLSVineyardDebug, "Vertices: %d %d compare %d", a->vertex(), b->vertex(), vcmp_(a->vertex(), b->vertex()));
-    AssertMsg(!vcmp_(b->vertex(), a->vertex()), "In swap(a,b), a must precede b");
+    AssertMsg(!vcmp_(b->vertex(), a->vertex()), "In swap(a,b), a must precede b");      // true since we are using linear iterpolation
     AssertMsg(a < b, "In swap(a,b), a must precede b");
     transpose_vertices(a);
     AssertMsg(b < a, "In swap(a,b), b must precede a after the transposition");

--- a/include/utilities/eventqueue.h	Sat Feb 06 23:22:43 2010 -0800
+++ b/include/utilities/eventqueue.h	Sun Feb 07 10:46:23 2010 -0800
@@ -5,16 +5,20 @@
 #include <functional>
 #include <boost/utility.hpp>
 
+#include <boost/multi_index_container.hpp>
+#include <boost/multi_index/ordered_index.hpp>
+#include <boost/multi_index/sequenced_index.hpp>
+namespace bmi = boost::multi_index;
+
+#include <utilities/log.h>
+#ifdef LOGGING
+static rlog::RLogChannel* rlEventQueue =             DEF_CHANNEL("utilities/eventqueue", rlog::Log_Debug);
+#endif // LOGGING
+
 #include <iostream>
-#include <cassert>					// TODO: switch to internal debugging system
 #include <string>
 #include <algorithm>
 
-// TODO: change inefficient list-based implementation to something heap-based
-// Need a queue that supports deleting arbitrary items (given by iterator), 
-// and maintaining correctness of iterators when different operations (notably 
-// remove and update are performed)
-
 template<class Event_, class EventComparison_>
 class EventQueue
 {
@@ -23,22 +27,29 @@
 		typedef					Event_											Event;
 		typedef					EventComparison_								EventComparison;
 
-		typedef					std::list<Event>								QueueRepresentation;
+        // Not actually a heap, but will work for now
+        typedef                 boost::multi_index_container<Event, 
+                                                             bmi::indexed_by<
+                                                                bmi::sequenced<>,
+                                                                bmi::ordered_non_unique<bmi::identity<Event>, EventComparison >
+                                                             > >
+                                                                                QueueRepresentation;
 		typedef					typename QueueRepresentation::iterator			iterator;
 		typedef					typename QueueRepresentation::const_iterator	const_iterator;
 		
 		EventQueue()			{}
 		
-		const_iterator 			top() const					{ assert(!empty()); return queue_.begin(); }
-		iterator 				top()						{ assert(!empty()); return queue_.begin(); }
-		iterator 				push(Event e)				{ queue_.push_front(e); iterator i = top(); update(i); return i; }
-		void 					pop()						{ assert(!empty()); queue_.erase(queue_.begin()); }
+		const_iterator 			top() const					{ AssertMsg(!empty(), "Queue must not be empty"); return queue_.begin(); }
+		iterator 				top()						{ AssertMsg(!empty(), "Queue must not be empty"); return queue_.begin(); }
+		// iterator 				push(Event e)				{ return queue_.insert(insert_position(e), e).first; }
+		iterator 				push(Event e)				{ iterator i = queue_.push_front(e).first; update(i); return i; }
+		void 					pop()						{ AssertMsg(!empty(), "Queue must not be empty"); queue_.erase(queue_.begin()); }
 		void					remove(iterator i)			{ queue_.erase(i); }
-		void					update(iterator i);
-        void                    prepend(iterator i, 
-                                        EventQueue& other)  { queue_.splice(queue_.begin(), other.queue_, i); }
-        ///< intended for temporary storage of elements from other queues
+        void                    replace(iterator i,
+                                        Event e)            { queue_.replace(i, e); update(i); }
 
+        iterator                begin()                     { return queue_.begin(); }
+        const_iterator          begin() const               { return queue_.begin(); }
 		iterator 				end()						{ return queue_.end(); }
 		const_iterator 			end() const					{ return queue_.end(); }
 		bool					empty() const				{ return queue_.empty(); }
@@ -46,24 +57,21 @@
 
 		std::ostream&			print(std::ostream& out, const std::string& prefix) const;
 
+        iterator                update(iterator i)
+        { 
+            iterator bg = bmi::project<0>(queue_, bmi::get<1>(queue_).lower_bound(*i)); 
+            iterator pos = std::find_if(bg, queue_.end(), std::bind1st(EventComparison(), *i));
+            queue_.replace(i, *i);
+            queue_.relocate(pos, i);
+            return pos; 
+        }
+
 	private:
 		QueueRepresentation		queue_;
 };
 
 
 template<class Event_, class EventComparison_>
-void
-EventQueue<Event_, EventComparison_>::
-update(iterator i)
-{
-	QueueRepresentation tmp;
-	tmp.splice(tmp.end(), queue_, i);
-	//iterator pos = std::find_if(queue_.begin(), queue_.end(), std::not1(std::bind2nd(EventComparison(), *i)));
-	iterator pos = std::find_if(queue_.begin(), queue_.end(), std::bind1st(EventComparison(), *i));
-	queue_.splice(pos, tmp);
-}
-
-template<class Event_, class EventComparison_>
 std::ostream&
 EventQueue<Event_, EventComparison_>::
 print(std::ostream& out, const std::string& prefix) const

--- a/tests/geometry/test-eventqueue.cpp	Sat Feb 06 23:22:43 2010 -0800
+++ b/tests/geometry/test-eventqueue.cpp	Sun Feb 07 10:46:23 2010 -0800
@@ -4,7 +4,7 @@
 
 int main()
 {
-	typedef EventQueue<int, std::less<int> >			EQ;
+	typedef EventQueue<int, std::less<int> >		    EQ;
 	typedef EQ::iterator								iterator;
 	 
 	EQ queue;
@@ -15,8 +15,7 @@
 	iterator j = queue.push(6);
 	queue.push(5);
 
-	*i = 8;
-	queue.update(i);
+	queue.replace(i,8);
 	queue.remove(j);
 
 	while (!queue.empty())

--- a/tests/geometry/test-ksort-linear.cpp	Sat Feb 06 23:22:43 2010 -0800
+++ b/tests/geometry/test-ksort-linear.cpp	Sun Feb 07 10:46:23 2010 -0800
@@ -55,6 +55,7 @@
     // Insert polynomials and sort the list for current time
     list.push_back(Function(2, -2));
     list.push_back(Function(1, 3));
+    list.push_back(Function(-1, 6));
     list.push_back(Function(2));
     list.push_back(Function(2, 2));
     //list.sort(EvaluatedComparison(simulator.current_time()));