--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/include/geometry/linear-kernel.h	Fri Feb 05 11:49:52 2010 -0800
@@ -0,0 +1,46 @@
+#ifndef __LINEAR_KERNEL_H__
+#define __LINEAR_KERNEL_H__
+
+#include <stack>
+#include <iostream>
+#include <boost/operators.hpp>
+
+template<class T>
+class LinearKernel
+{
+	public:
+        struct                      Function;
+
+		typedef						T					                                RootType;
+		typedef						std::stack<RootType>								RootStack;
+
+		static void					solve(const Function& f, RootStack& stack)          { if (f.a1 != 0) stack.push(-f.a0/f.a1); }
+		static RootType				root(const T& r)									{ return r; }
+		static int					sign_at(const Function& f, const RootType& r)       { RootType y = f(r); if (y < 0) return -1; if (y > 0) return 1; return 0; }
+		static RootType				between(const RootType& r1, const RootType& r2)		{ return (r1 + r2)/2; }
+		static int					sign_at_negative_infinity(const Function& f)        { if (f.a1 < 0) return 1; if (f.a1 > 0) return -1; return 0; }
+};
+
+template<class T>
+struct LinearKernel<T>::Function: boost::additive<Function>
+{
+        typedef                     T                                                   RootType;
+
+                                    Function(RootType aa0, RootType aa1 = 0):
+                                        a0(aa0), a1(aa1)                                {}
+
+        RootType                    operator()(RootType r) const                        { return a1 * r + a0; }
+        Function&                   operator+=(const Function& other)                   { a1 += other.a1; a0 += other.a0; return *this; }
+        Function&                   operator-=(const Function& other)                   { a1 -= other.a1; a0 -= other.a0; return *this; }
+        std::ostream&               operator<<(std::ostream& out) const                 { out << a1 << "*x + " << a0; return out; }
+
+        RootType                    a0, a1;
+};
+
+// TODO: need to make this generic
+std::ostream&                       operator<<(std::ostream& out, const LinearKernel<double>::Function& f)
+{
+    return f.operator<<(out);
+}
+
+#endif

--- a/tests/geometry/CMakeLists.txt	Fri Feb 05 11:07:42 2010 -0800
+++ b/tests/geometry/CMakeLists.txt	Fri Feb 05 11:49:52 2010 -0800
@@ -1,5 +1,6 @@
 set							(targets
 							 euclidean
+                             test-ksort-linear
 							 test-eventqueue)
 
 if                          (use_synaps)

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/tests/geometry/test-ksort-linear.cpp	Fri Feb 05 11:49:52 2010 -0800
@@ -0,0 +1,87 @@
+#include <geometry/simulator.h>
+#include <geometry/kinetic-sort.h>
+#include <geometry/linear-kernel.h>
+#include <iostream>
+
+#include <boost/utility.hpp>
+#include <boost/bind.hpp>
+
+#include <utilities/log.h>
+
+typedef     double                          FieldType;
+//typedef       ZZ                              FieldType;
+//typedef       QQ                              FieldType;
+typedef     LinearKernel<FieldType>         LKernel;
+typedef     LKernel::Function               Function;
+typedef     std::list<Function>             SortDS;
+typedef     SortDS::iterator                SortDSIterator;
+typedef     Simulator<LKernel>              SimulatorFT;
+
+class TrajectoryExtractor
+{
+    public:
+        Function                operator()(SortDSIterator i) const          { return *i; }
+};
+
+typedef     KineticSort<SortDSIterator, TrajectoryExtractor, SimulatorFT>       KineticSortDS;
+
+struct EvaluatedComparison: public std::binary_function<const Function&, const Function&, bool>
+{
+                                EvaluatedComparison(FieldType v): vv(v) {}
+    bool                        operator()(const Function& p1, const Function& p2)              
+                                { return p1(vv) < p2(vv); }
+    FieldType                   vv;
+};
+
+void swap(SortDS* s, SortDSIterator i, SimulatorFT* simulator)
+{
+    std::cout << "Swapping " << *i << " " << *boost::next(i) << std::endl;
+    s->splice(i, *s, boost::next(i));
+}
+
+int main(int argc, char** argv)
+{
+#ifdef LOGGING
+    rlog::RLogInit(argc, argv);
+
+    stderrLog.subscribeTo( RLOG_CHANNEL("error") );
+    stdoutLog.subscribeTo( RLOG_CHANNEL("geometry/simulator") );
+    stdoutLog.subscribeTo( RLOG_CHANNEL("geometry/kinetic-sort") );
+#endif
+
+    SimulatorFT     simulator;
+    SortDS          list;
+
+    // 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(2));
+    list.push_back(Function(2, 2));
+    //list.sort(EvaluatedComparison(simulator.current_time()));
+    list.sort(EvaluatedComparison(0));
+
+    // Print out the list
+    for (SortDS::const_iterator cur = list.begin(); cur != list.end(); ++cur)
+        std::cout << *cur << std::endl;
+
+    // Setup kinetic sort
+    KineticSortDS   ks(list.begin(), list.end(), boost::bind(swap, &list, _1, _2), &simulator);
+
+    std::cout << "Examining " << simulator;
+
+    while(!simulator.reached_infinity())
+    {
+        std::cout << "Current time before: " << simulator.current_time() << std::endl;
+        //if (!ks.audit(&simulator)) return 1;
+        ks.audit(&simulator);
+        std::cout << "Examining " << simulator;
+        simulator.process();
+        std::cout << "Current time after: " << simulator.current_time() << std::endl;
+    }
+    ks.audit(&simulator);
+    std::cout << "Examining " << simulator;
+
+    std::cout << "Done at " << simulator.current_time() << std::endl;
+    for (SortDS::const_iterator cur = list.begin(); cur != list.end(); ++cur)
+        std::cout << "  " << *cur << std::endl;    
+}