--- a/SConstruct	Mon Dec 04 22:39:35 2006 -0500
+++ b/SConstruct	Sat Dec 16 15:34:46 2006 -0500
@@ -72,7 +72,8 @@
 #SConscript				(['examples/SConscript',
 #						  'tools/SConscript'],
 #						 exports = ['env', 'external_sources'])
-SConscript				(['examples/SConscript'],
+SConscript				(['examples/SConscript', 
+						  'tests/SConscript'],
 						 exports = ['env', 'external_sources'])
 
 # vim: syntax=python

--- a/examples/triangle/SConscript	Mon Dec 04 22:39:35 2006 -0500
+++ b/examples/triangle/SConscript	Sat Dec 16 15:34:46 2006 -0500
@@ -1,6 +1,6 @@
 Import('*')
 
-Default(env.Program('triangle.cpp'))
+Default(env.Program(['triangle.cpp'] + external_sources))
 
 ## Common variables
 ##libraries = 			['dsrpdb', 'boost_serialization']

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/include/consistencylist.h	Sat Dec 16 15:34:46 2006 -0500
@@ -0,0 +1,223 @@
+/*
+ * Author: Dmitriy Morozov 
+ * Department of Computer Science, Duke University, 2006
+ */
+
+#ifndef __CONSISTENCYLIST_H__
+#define __CONSISTENCYLIST_H__
+
+#include "orderlist.h"
+
+#include <iterator>
+#include <iostream>
+#include <list>
+#include "types.h"
+
+#include <boost/utility.hpp>
+#include <boost/iterator/iterator_adaptor.hpp>
+//#include <boost/type_traits/is_convertible.hpp>
+//#include <boost/utility/enable_if.hpp>
+
+
+template<class T> 		struct 	ConsistencyListNode;
+template<class T>		class   ConsistencyListIterator;
+template<class T>		class   const_ConsistencyListIterator;
+
+/**
+ * ConsistencyList adds consistency order to OrderList which remains unchanged
+ * through the lifetime of the list.
+ */
+template<class T>
+class ConsistencyList: public OrderList<ConsistencyListNode<T> >
+{
+	public:
+		class 			OrderComparison;				
+		class 			LessThanComparison;
+		class 			GreaterThanComparison;
+		class 			ConsistencyComparison;
+
+		/// \name Comparison types
+		/// @{
+		// Explicit typedefs for Doxygen
+		typedef			LessThanComparison							LessThanComparison;
+		typedef			GreaterThanComparison						GreaterThanComparison;
+		typedef			ConsistencyComparison						ConsistencyComparison;
+		/// @}
+	
+		typedef			ConsistencyListNode<T>						NodeType;
+		typedef			ConsistencyList<T>							Self;
+		typedef			OrderList<NodeType >						Parent;
+		
+		typedef			T											value_type;
+		typedef			T&											reference;
+		typedef			const T&									const_reference;
+		typedef			ConsistencyListIterator<T>						iterator;
+		typedef			const_ConsistencyListIterator<T>					const_iterator;
+	
+						ConsistencyList(): sz(0)					{}
+						~ConsistencyList() 							{ clear(); }
+	
+		/// \name Order operations
+		void			swap(iterator i, iterator j);				///< Exchanges the order of simplices pointed to by i and j
+
+		/// \name Container operations
+		/// @{
+		// Explicit calls instead of using declarations for Doxygen
+		iterator		push_back(const_reference x);
+		iterator		insert(iterator predecessor, const_reference x);	///< Inserts x immediately after predecessor (has to be a valid iterator)
+		void			erase(iterator x)							{ Parent::erase(x.get_base()); --sz; }
+
+		void			clear()										{ return Parent::clear(); }	
+		bool			empty() const								{ return Parent::empty(); }
+		SizeType		size()	const								{ return sz; }
+		iterator		begin()										{ return iterator(Parent::begin()); }
+		const_iterator	begin() const								{ return const_iterator(Parent::begin()); }
+		iterator		end()										{ return iterator(Parent::end()); }
+		const_iterator	end() const									{ return const_iterator(Parent::end()); }
+		reference		back()										{ return Parent::back(); }
+		const_reference	back() const								{ return Parent::back(); }
+		void			pop_back()									{ return Parent::pop_back(); }
+		                                                			
+		iterator		last()										{ return iterator(boost::prior(end())); }
+		const_iterator	last() const								{ return const_iterator(boost::prior(end())); }
+		/// @}
+	
+	private:
+		unsigned int	sz;
+};
+
+/// Basic comparison that LessThan and GreaterThan derive from
+template<class T>
+class ConsistencyList<T>::OrderComparison
+{
+	public:
+		typedef			typename ConsistencyList<T>::const_iterator		ComparableType;				
+
+		int 			compare(ComparableType a, ComparableType b) const;				/// (-1,0,1) = a (precedes, ==, succeeds) b 
+};
+
+/// Determines if the first element is less than the second one
+template<class T>
+class ConsistencyList<T>::LessThanComparison: public OrderComparison 
+{
+	public:
+		typedef			OrderComparison								Parent;
+		typedef			typename Parent::ComparableType				ComparableType;				
+		
+		int 			compare(ComparableType a, ComparableType b) const;	
+		bool 			operator()(ComparableType a, ComparableType b) const;
+};
+
+/// Determines if the first element is greater than the second one
+template<class T>
+class ConsistencyList<T>::GreaterThanComparison: public OrderComparison 
+{
+	public:
+		typedef			OrderComparison								Parent;
+		typedef			typename Parent::ComparableType				ComparableType;				
+		
+		int 			compare(ComparableType a, ComparableType b) const;
+		bool 			operator()(ComparableType a, ComparableType b) const;
+};
+
+/// Determines the order of the two elements in the consistency order (that doesn't change during the execution)
+template<class T>
+class ConsistencyList<T>::ConsistencyComparison
+{
+	public:
+		typedef			typename ConsistencyList<T>::const_iterator		ComparableType;				
+		
+		int 			compare(ComparableType a, ComparableType b) const;				///< (-1,0,1) = a (precedes, ==, succeeds) b 
+		bool 			operator()(ComparableType a, ComparableType b) const;		
+};
+
+/// Structure storing auxilliary information requred for each node of ConsistencyList
+template<class T>
+struct ConsistencyListNode
+{
+	ConsistencyListNode(const T& d, unsigned int c):
+		data(d), consistency(c)
+	{}
+	
+	T 				data;
+	OrderType		consistency;
+
+	std::ostream& 		operator<<(std::ostream& out) const					{ return out << data << ": " << consistency; }
+};
+
+template<class T>
+std::ostream&			operator<<(std::ostream& out, const ConsistencyListNode<T>& n)	{ return n.operator<<(out); }
+
+template<class T>
+class ConsistencyListIterator: public boost::iterator_adaptor<ConsistencyListIterator<T>,
+						 								typename ConsistencyList<T>::Parent::iterator,
+						 								T>
+{
+	private:
+		struct			enabler										{};
+		
+	public:
+		typedef			typename ConsistencyList<T>::Parent			ConsistencyListParent;
+		typedef 		boost::iterator_adaptor<ConsistencyListIterator<T>,
+												typename ConsistencyListParent::iterator,
+												T>					Parent;
+		typedef			typename Parent::reference					reference;
+		typedef			typename Parent::base_type					base_type;
+
+						ConsistencyListIterator()					{}
+						ConsistencyListIterator(const typename ConsistencyListParent::iterator& iter):
+    						ConsistencyListIterator::iterator_adaptor_(iter)	
+						{}
+						ConsistencyListIterator(const ConsistencyListIterator<T>& other):
+							ConsistencyListIterator::iterator_adaptor_(other.base())			
+						{}
+
+	private:
+		friend class	boost::iterator_core_access;
+		reference		dereference() const							{ return Parent::base_reference()->data; }
+		base_type&		get_base()									{ return Parent::base_reference(); }
+
+		friend class 	ConsistencyList<T>;
+};
+
+template<class T>
+class const_ConsistencyListIterator: public boost::iterator_adaptor<const_ConsistencyListIterator<T>,
+						 									  typename ConsistencyList<T>::Parent::const_iterator,
+						 									  const T>
+{
+	private:
+		struct			enabler										{};
+		
+	public:
+		typedef			typename ConsistencyList<T>::Parent				ConsistencyListParent;
+		typedef 		boost::iterator_adaptor<const_ConsistencyListIterator<T>,
+												typename ConsistencyListParent::const_iterator,
+												const T>			Parent;
+		typedef			typename Parent::reference					reference;
+		typedef			typename Parent::base_type					base_type;
+
+						const_ConsistencyListIterator()					{}
+						const_ConsistencyListIterator(const typename ConsistencyListParent::const_iterator& iter):
+    						const_ConsistencyListIterator::iterator_adaptor_(iter)	
+						{}
+						const_ConsistencyListIterator(const const_ConsistencyListIterator<T>& other):
+							const_ConsistencyListIterator::iterator_adaptor_(other.base())			
+						{}
+						const_ConsistencyListIterator(const ConsistencyListIterator<T>& other):
+							const_ConsistencyListIterator::iterator_adaptor_(other.base())			
+						{}
+
+	private:
+		friend class	boost::iterator_core_access;
+		reference		dereference() const							{ return Parent::base_reference()->data; }
+		const base_type&
+						get_base()									{ return Parent::base_reference(); }
+
+		friend class 	ConsistencyList<T>::OrderComparison;
+		friend class 	ConsistencyList<T>::ConsistencyComparison;
+};
+
+
+#include "consistencylist.hpp"
+
+#endif // __CONSISTENCYLIST_H__

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/include/consistencylist.hpp	Sat Dec 16 15:34:46 2006 -0500
@@ -0,0 +1,73 @@
+/* Implementations */
+
+template<class T>
+void 
+ConsistencyList<T>::
+swap(iterator i, iterator j)
+{
+	Parent::swap(i.get_base(),j.get_base());
+}
+
+template<class T>
+typename ConsistencyList<T>::iterator 
+ConsistencyList<T>::
+push_back(const_reference x)
+{
+	++sz;
+	return Parent::push_back(NodeType(x, sz));
+}
+
+template<class T>
+typename ConsistencyList<T>::iterator 
+ConsistencyList<T>::
+insert(iterator p, const_reference x)
+{
+	++sz;
+	return Parent::insert(p.get_base(), NodeType(x, sz));
+}
+
+
+/* OrderComparison */
+template<class T>
+int 
+ConsistencyList<T>::
+OrderComparison::compare(ComparableType a, ComparableType b) const
+{
+	typename Parent::OrderComparison cmp;
+	return cmp.compare(a.get_base(), b.get_base());
+}
+
+
+/* LessThanComparison */
+template<class T>
+int ConsistencyList<T>::LessThanComparison::compare(ComparableType a, ComparableType b) const
+{ return Parent::compare(a,b); }
+
+template<class T>
+bool ConsistencyList<T>::LessThanComparison::operator()(ComparableType a, ComparableType b) const
+{ return compare(a,b) == -1; }
+
+
+/* GreaterThanComparison */
+template<class T>
+int ConsistencyList<T>::GreaterThanComparison::compare(ComparableType a, ComparableType b) const
+{ return -Parent::compare(a,b); }
+
+template<class T>
+bool ConsistencyList<T>::GreaterThanComparison::operator()(ComparableType a, ComparableType b) const
+{ return compare(a,b) == -1; }
+
+
+/* ConsistencyComparison */
+template<class T>
+int ConsistencyList<T>::ConsistencyComparison::compare(ComparableType a, ComparableType b) const
+{ 
+	if (a.get_base()->consistency < b.get_base()->consistency) 			return -1;
+	else if (a.get_base()->consistency == b.get_base()->consistency)	return 0;
+	else																return 1;
+}
+
+template<class T>
+bool ConsistencyList<T>::ConsistencyComparison::operator()(ComparableType a, ComparableType b) const
+{ return compare(a,b) == -1; }
+

--- a/include/debug.h	Mon Dec 04 22:39:35 2006 -0500
+++ b/include/debug.h	Sat Dec 16 15:34:46 2006 -0500
@@ -67,6 +67,7 @@
 				extern channel_ct lsfiltration;
 				extern channel_ct lsvineyard;
 				extern channel_ct vertex_transpositions;
+				extern channel_ct orderlist;
 			} // namespace dc
 		} // namespace DEBUGCHANNELS
 	}

--- a/include/filtrationcontainer.h	Mon Dec 04 22:39:35 2006 -0500
+++ b/include/filtrationcontainer.h	Sat Dec 16 15:34:46 2006 -0500
@@ -6,7 +6,7 @@
 #ifndef __FILTRATIONCONTAINER_H__
 #define __FILTRATIONCONTAINER_H__
 
-#include "orderlist.h"
+#include "consistencylist.h"
 #include "cycle.h"
 
 /**
@@ -15,25 +15,25 @@
  * to get Cycle representation.
  */
 template<class FltrSmplx>
-class FiltrationContainer: public OrderList<FltrSmplx>
+class FiltrationContainer: public ConsistencyList<FltrSmplx>
 {
 	public:
 		typedef		FltrSmplx														FiltrationSimplex;
-		typedef		OrderList<FiltrationSimplex>									OrderList;
+		typedef		ConsistencyList<FiltrationSimplex>								ConsistencyList;
 		
 		/// \name Cycles and Trails 
 		/// @{
 		/// Index is and therfore acts like an iterator. The name is preserved for historical reasons.
-		typedef		typename OrderList::iterator									Index;
+		typedef		typename ConsistencyList::iterator								Index;
 		/// const_Index is a const_iterator
-		typedef		typename OrderList::const_iterator								const_Index;
+		typedef		typename ConsistencyList::const_iterator						const_Index;
 		/// @}
 
 		/// \name Cycles and Trails 
 		/// @{
-		typedef		typename OrderList::GreaterThanComparison						CyclesComparator;
-		typedef		typename OrderList::LessThanComparison							TrailsComparator;
-		typedef		typename OrderList::ConsistencyComparison 						ConsistencyComparator;
+		typedef		typename ConsistencyList::GreaterThanComparison					CyclesComparator;
+		typedef		typename ConsistencyList::LessThanComparison					TrailsComparator;
+		typedef		typename ConsistencyList::ConsistencyComparison 				ConsistencyComparator;
 		typedef		::Cycle<Index, CyclesComparator, ConsistencyComparator>			Cycle;
 		typedef		::Cycle<Index, TrailsComparator, ConsistencyComparator>			Trail;
 		/// @}

--- a/include/orderlist.h	Mon Dec 04 22:39:35 2006 -0500
+++ b/include/orderlist.h	Sat Dec 16 15:34:46 2006 -0500
@@ -1,14 +1,24 @@
 /*
  * Author: Dmitriy Morozov 
  * Department of Computer Science, Duke University, 2006
+ *
+ * Implements the simplified order list data strcutre given in ``Two Simplified
+ * Algorithms for Maintaining Order in a List'' by Bender et al.
+ *
+ * Indirection is not implemented, so the insertion cost is amortized O(log n),
+ * while comparison and deletion are O(1).
  */
 
 #ifndef __ORDERLIST_H__
 #define __ORDERLIST_H__
 
+#include "sys.h"
+#include "debug.h"
+
 #include <iterator>
 #include <iostream>
 #include <list>
+
 #include "types.h"
 //#include "counter.h"
 
@@ -25,25 +35,19 @@
 template<class T>		class   const_OrderListIterator;
 
 /**
- * OrderList stores a list of objects while keeping track of two orders: proper order and consistency order.
- * Consistency order is guaranteed not to change, while proper order is affected by the swap() operation.
+ * OrderList stores a list of objects while maintaining their total order under
+ * the operations of insert(), swap(), and delete(). push_back() is provided for
+ * uniformity, OrderComparison member class carries out comparison of the
+ * elements.
  */
 template<class T>
-class OrderList: std::list<OrderListNode<T> >
+class OrderList: public std::list<OrderListNode<T> >
 {
 	public:
 		class 			OrderComparison;				
-		class 			LessThanComparison;
-		class 			GreaterThanComparison;
-		class 			ConsistencyComparison;
 
-		/// \name Comparison types
-		/// @{
-		// Explicit typedefs for Doxygen
-		typedef			LessThanComparison							LessThanComparison;
-		typedef			GreaterThanComparison						GreaterThanComparison;
-		typedef			ConsistencyComparison						ConsistencyComparison;
-		/// @}
+		/// OrderComparison type
+		typedef			OrderComparison								OrderComparison;
 	
 		typedef			OrderListNode<T>							NodeType;
 		typedef			OrderList<T>								Self;
@@ -57,7 +61,7 @@
 	
 						OrderList()									{}
 						~OrderList() 								{ clear(); }
-	
+
 		/// \name Order operations
 		void			swap(iterator i, iterator j);				///< Exchanges the order of simplices pointed to by i and j
 
@@ -65,6 +69,9 @@
 		/// @{
 		// Explicit calls instead of using declarations for Doxygen
 		iterator		push_back(const_reference x);
+		iterator		insert(iterator predecessor, const_reference x);	///< Inserts x immediately after predecessor (has to be a valid iterator)
+		void			erase(iterator x)							{ Parent::erase(x.get_base()); }
+		
 		void			clear()										{ return Parent::clear(); }	
 		bool			empty() const								{ return Parent::empty(); }
 		SizeType		size()	const								{ return Parent::size(); }
@@ -79,6 +86,14 @@
 		iterator		last()										{ return iterator(boost::prior(end())); }
 		const_iterator	last() const								{ return const_iterator(boost::prior(end())); }
 		/// @}
+		
+		/// \name Debugging operations
+		/// @{
+		void			show_elements() const;
+		/// @}
+
+	private:
+		static const float density_threshold = 1.2;
 };
 
 /// Basic comparison that LessThan and GreaterThan derive from
@@ -87,59 +102,27 @@
 {
 	public:
 		typedef			typename OrderList<T>::const_iterator		ComparableType;				
-
 		int 			compare(ComparableType a, ComparableType b) const;				/// (-1,0,1) = a (precedes, ==, succeeds) b 
 };
 
-/// Determines if the first element is less than the second one
-template<class T>
-class OrderList<T>::LessThanComparison: public OrderComparison 
-{
-	public:
-		typedef			OrderComparison								Parent;
-		typedef			typename Parent::ComparableType				ComparableType;				
-		
-		int 			compare(ComparableType a, ComparableType b) const;	
-		bool 			operator()(ComparableType a, ComparableType b) const;
-};
-
-/// Determines if the first element is greater than the second one
-template<class T>
-class OrderList<T>::GreaterThanComparison: public OrderComparison 
-{
-	public:
-		typedef			OrderComparison								Parent;
-		typedef			typename Parent::ComparableType				ComparableType;				
-		
-		int 			compare(ComparableType a, ComparableType b) const;
-		bool 			operator()(ComparableType a, ComparableType b) const;
-};
-
-/// Determines the order of the two elements in the consistency order (that doesn't change during the execution)
-template<class T>
-class OrderList<T>::ConsistencyComparison
-{
-	public:
-		typedef			typename OrderList<T>::const_iterator		ComparableType;				
-		
-		int 			compare(ComparableType a, ComparableType b) const;				///< (-1,0,1) = a (precedes, ==, succeeds) b 
-		bool 			operator()(ComparableType a, ComparableType b) const;		
-};
-
 /// Structure storing auxilliary information requred for each node of OrderList
 template<class T>
 struct OrderListNode
 {
-	OrderListNode(const T& d, unsigned int orig, unsigned int cur):
-		data(d), original(orig), current(cur)
+	OrderListNode(const T& d, unsigned int t):
+		data(d), tag(t)
 	{}
 	
 	T 				data;
-	OrderType		original;
-	OrderType		current;
+	OrderType		tag;
+	
+	std::ostream& 		operator<<(std::ostream& out) const					{ return out << data << ": " << tag; }
 };
 
 template<class T>
+std::ostream&			operator<<(std::ostream& out, const OrderListNode<T>& n)	{ return n.operator<<(out); }
+
+template<class T>
 class OrderListIterator: public boost::iterator_adaptor<OrderListIterator<T>,
 						 								typename OrderList<T>::Parent::iterator,
 						 								T>
@@ -162,7 +145,7 @@
 						OrderListIterator(const OrderListIterator<T>& other):
 							OrderListIterator::iterator_adaptor_(other.base())			
 						{}
-
+	
 	private:
 		friend class	boost::iterator_core_access;
 		reference		dereference() const							{ return Parent::base_reference()->data; }
@@ -204,8 +187,8 @@
 		const base_type&
 						get_base()									{ return Parent::base_reference(); }
 
+		friend class 	OrderList<T>;
 		friend class 	OrderList<T>::OrderComparison;
-		friend class 	OrderList<T>::ConsistencyComparison;
 };
 
 

--- a/include/orderlist.hpp	Mon Dec 04 22:39:35 2006 -0500
+++ b/include/orderlist.hpp	Sat Dec 16 15:34:46 2006 -0500
@@ -1,11 +1,13 @@
 /* Implementations */
 
 template<class T>
-void OrderList<T>::swap(iterator i, iterator j)
+void 
+OrderList<T>::
+swap(iterator i, iterator j)
 {
 	typename Parent::iterator i_base = i.get_base();
 	typename Parent::iterator j_base = j.get_base();
-	std::swap(i_base->current, j_base->current);
+	std::swap(i_base->tag, j_base->tag);
 
 	// Exchange the actual elements in the list --- so that iterators behave as expected
 	typename Parent::iterator after_j = boost::next(j_base);	
@@ -14,54 +16,83 @@
 }
 
 template<class T>
-typename OrderList<T>::iterator OrderList<T>::push_back(const_reference x)
+typename OrderList<T>::iterator 
+OrderList<T>::
+push_back(const_reference x)
 {
-	OrderType index = size();
-	Parent::push_back(NodeType(x, index, index));
+	if (empty()) 
+		Parent::push_back(NodeType(x, 0));
+	else
+		Parent::push_back(NodeType(x, last().get_base()->tag + 1));
+	
 	return last();
 }
 
+template<class T>
+typename OrderList<T>::iterator 
+OrderList<T>::
+insert(iterator p, const_reference x)
+{
+	typename Parent::iterator p_base = p.get_base();
+	OrderType tag = (p_base++)->tag + 1;
+	typename Parent::iterator new_base = Parent::insert(p_base, NodeType(x, tag));
+
+	if (p_base->tag != tag)
+		return iterator(new_base);
+
+	// Find non-overflowing region
+	unsigned int num_elements = 1, maximum = 1, lower = tag, upper = tag, level = 0;
+	float inv_density = 1;
+	typename Parent::iterator prev = p_base, next = p_base;
+	--(--prev); ++next; 		// move prev back twice to skip over the newly inserted element
+
+	do
+	{
+		lower &= ~(1 << level);
+		upper |= (1 << level);
+		maximum <<= 1; inv_density *= density_threshold;
+		++level;
+
+		while (prev != Parent::end() && prev->tag >= lower) { --prev; ++num_elements; }
+		while (next != Parent::end() && next->tag <= upper) { ++next; ++num_elements; }
+	} while (inv_density * num_elements >= maximum);
+	++num_elements;			// for the extra element inserted
+
+	Dout(dc::orderlist, num_elements << ", " << lower << ", " << upper);
+	Dout(dc::orderlist, "prev is at the end: " << (prev == Parent::end()));
+	Dout(dc::orderlist, "next is at the end: " << (next == Parent::end()));
+	
+	// Reorder
+	AssertMsg((upper - lower + 1)/num_elements > 0, "Spacing between new tags must be non-zero");
+	for (int i = 0; i < num_elements; ++i)
+	{
+		(++prev)->tag = lower + i*((upper - lower + 1)/num_elements);
+		Dout(dc::orderlist, prev->tag);
+		AssertMsg(prev->tag != 0 || prev == Parent::begin(), "Cannot assign 0 tag except at the beginning of OrderList");
+	}
+
+	AssertMsg(++prev == next, "prev + num_elements != next in OrderList::insert()");
+
+	return iterator(new_base);
+}
+
+template<class T>
+void
+OrderList<T>::
+show_elements() const
+{
+	for (const_iterator cur = begin(); cur != end(); ++cur)
+		std::cout << *(cur.get_base()) << std::endl;
+	std::cout << std::endl;
+}
 
 /* OrderComparison */
 template<class T>
-int OrderList<T>::OrderComparison::compare(ComparableType a, ComparableType b) const
+int 
+OrderList<T>::OrderComparison::
+compare(ComparableType a, ComparableType b) const
 {
-	if (a.get_base()->current == b.get_base()->current)			return 0;
-	if (a.get_base()->current < b.get_base()->current)			return -1;
+	if (a.get_base()->tag == b.get_base()->tag)			return 0;
+	if (a.get_base()->tag < b.get_base()->tag)			return -1;
 	return 1;
 }
-
-
-/* LessThanComparison */
-template<class T>
-int OrderList<T>::LessThanComparison::compare(ComparableType a, ComparableType b) const
-{ return Parent::compare(a,b); }
-
-template<class T>
-bool OrderList<T>::LessThanComparison::operator()(ComparableType a, ComparableType b) const
-{ return compare(a,b) == -1; }
-
-
-/* GreaterThanComparison */
-template<class T>
-int OrderList<T>::GreaterThanComparison::compare(ComparableType a, ComparableType b) const
-{ return -Parent::compare(a,b); }
-
-template<class T>
-bool OrderList<T>::GreaterThanComparison::operator()(ComparableType a, ComparableType b) const
-{ return compare(a,b) == -1; }
-
-
-/* ConsistencyComparison */
-template<class T>
-int OrderList<T>::ConsistencyComparison::compare(ComparableType a, ComparableType b) const
-{ 
-	if (a.get_base()->original < b.get_base()->original) 			return -1;
-	else if (a.get_base()->original == b.get_base()->original)		return 0;
-	else															return 1;
-}
-
-template<class T>
-bool OrderList<T>::ConsistencyComparison::operator()(ComparableType a, ComparableType b) const
-{ return compare(a,b) == -1; }
-

--- a/src/debug.cpp	Mon Dec 04 22:39:35 2006 -0500
+++ b/src/debug.cpp	Sat Dec 16 15:34:46 2006 -0500
@@ -19,6 +19,7 @@
 				channel_ct lsfiltration("LSFILTRATION");
 				channel_ct lsvineyard("LSVINEYARD");
 				channel_ct vertex_transpositions("VERTEX_TRANSPOS");
+				channel_ct orderlist("ORDERLIST");
 			}
     	} // namespace DEBUGCHANNELS
 

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/tests/SConscript	Sat Dec 16 15:34:46 2006 -0500
@@ -0,0 +1,6 @@
+Import('*')
+
+sources = 			['test-orderlist.cpp', 'test-consistencylist.cpp']
+
+for s in sources:
+	Default(env.Program([s] + external_sources))

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/tests/test-consistencylist.cpp	Sat Dec 16 15:34:46 2006 -0500
@@ -0,0 +1,57 @@
+#include "consistencylist.h"
+#include <iostream>
+
+typedef ConsistencyList<int> 		OList;
+typedef OList::OrderComparison		Comparison;
+typedef OList::iterator 			iterator;
+
+int main()
+{
+#ifdef CWDEBUG
+	dionysus::debug::init();
+
+	//Debug(dc::orderlist.on());
+#endif
+		
+	OList list; Comparison cmp;
+	iterator i20 = list.push_back(20);
+	iterator i50 = list.push_back(50);
+	list.show_elements();
+	
+	iterator i30 = list.insert(i20, 30);
+	list.show_elements();
+	
+	iterator i40 = list.insert(i30, 40);
+	iterator i60 = list.insert(i50, 60);
+	list.show_elements();
+	
+	iterator i70 = list.push_back(70);
+	iterator i45 = list.insert(i40,45);
+	iterator i25 = list.insert(i20,25);
+	iterator i35 = list.insert(i30,35);
+	iterator i55 = list.insert(i50,55);
+	iterator i65 = list.insert(i60,65);
+	iterator i57 = list.insert(i55,57);
+	std::cout << "Before swaps" << std::endl;
+	list.show_elements();
+
+	list.swap(i45, i50);
+	list.swap(i45, i65);
+	std::cout << "After swaps" << std::endl;
+	list.show_elements();
+	
+	std::cout << *(++list.end()) << std::endl;
+	std::cout << *(--list.end()) << std::endl;
+	std::cout << std::endl;
+
+	for (int i = 0; i < 100000; ++i)
+	{
+		list.insert(i20,i);
+	}
+	list.show_elements();
+	
+	std::cout << "20 < 30: " << cmp.compare(i20,i30) << std::endl;
+	std::cout << "60 < 40: " << cmp.compare(i60,i40) << std::endl;
+	std::cout << "50 < 70: " << cmp.compare(i50,i70) << std::endl;
+	std::cout << "60 < 70: " << cmp.compare(i60,i70) << std::endl;
+}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/tests/test-orderlist.cpp	Sat Dec 16 15:34:46 2006 -0500
@@ -0,0 +1,45 @@
+#include "orderlist.h"
+#include <iostream>
+
+typedef OrderList<int> 					OList;
+typedef OList::OrderComparison		Comparison;
+typedef OList::iterator 			iterator;
+
+int main()
+{
+#ifdef CWDEBUG
+	dionysus::debug::init();
+
+	Debug(dc::orderlist.on());
+#endif
+		
+	OList list; Comparison cmp;
+	iterator i20 = list.push_back(20);
+	iterator i50 = list.push_back(50);
+	list.show_elements();
+	
+	iterator i30 = list.insert(i20, 30);
+	list.show_elements();
+	
+	iterator i40 = list.insert(i30, 40);
+	iterator i60 = list.insert(i50, 60);
+	list.show_elements();
+	
+	iterator i70 = list.push_back(70);
+	iterator i45 = list.insert(i40,45);
+	iterator i25 = list.insert(i20,25);
+	iterator i35 = list.insert(i30,35);
+	iterator i55 = list.insert(i50,55);
+	iterator i65 = list.insert(i60,65);
+	iterator i57 = list.insert(i55,57);
+	list.show_elements();
+
+	std::cout << *(++list.end()) << std::endl;
+	std::cout << *(--list.end()) << std::endl;
+	std::cout << std::endl;
+	
+	std::cout << "20 < 30: " << cmp.compare(i20,i30) << std::endl;
+	std::cout << "60 < 40: " << cmp.compare(i60,i40) << std::endl;
+	std::cout << "50 < 70: " << cmp.compare(i50,i70) << std::endl;
+	std::cout << "60 < 70: " << cmp.compare(i60,i70) << std::endl;
+}