KineticSort can deal with equal trajectories: ar
authorDmitriy Morozov <morozov@cs.duke.edu>
Tue, 26 Feb 2008 16:45:25 -0500
branchar
changeset 72 35500d7f9fca
parent 71 a6c5cb5a17cc
child 73 95f39b0e4701
KineticSort can deal with equal trajectories: UPolynomial::sign_at_negative_infinity() can handle 0 and so can Simulator::add()
include/geometry/polynomial.h
include/geometry/polynomial.hpp
include/geometry/simulator.hpp
tests/geometry/test-kinetic-sort.cpp
--- a/include/geometry/polynomial.h	Tue Feb 26 16:15:12 2008 -0500
+++ b/include/geometry/polynomial.h	Tue Feb 26 16:45:25 2008 -0500
@@ -32,7 +32,7 @@
 		static RootType				root(const T& r)									{ return SynapsTraits<T>::root(r); }
 		static int					sign_at(const RationalFunction& rf, const RootType& r);
 		static RootType				between(const RootType& r1, const RootType& r2)		{ return SynapsTraits<T>::between(r1,r2); }
-		static bool					sign_at_negative_infinity(const RationalFunction& rf);
+		static int					sign_at_negative_infinity(const RationalFunction& rf);
 };
 
 template<class T>
--- a/include/geometry/polynomial.hpp	Tue Feb 26 16:15:12 2008 -0500
+++ b/include/geometry/polynomial.hpp	Tue Feb 26 16:45:25 2008 -0500
@@ -38,16 +38,17 @@
 }
 
 template<class T>
-bool
+int
 UPolynomial<T>::
 sign_at_negative_infinity(const RationalFunction& rf)
 {
 	const Polynomial& num = rf.numerator();
 	const Polynomial& den = rf.denominator();
-	unsigned int ndegree = num.get_degree();
-	unsigned int ddegree = den.get_degree();
+	int ndegree = num.get_degree();
+	int ddegree = den.get_degree();
+    if (ndegree == -1) return 0;          // ndegree == -1 => num == 0, and 0 is 0 at -infinity
 	return !((((ndegree + 1) % 2 == 0) ^ (num[ndegree] > 0)) ^
-		     (((ddegree + 1) % 2 == 0) ^ (den[ddegree] > 0)));
+		     (((ddegree + 1) % 2 == 0) ^ (den[ddegree] > 0))) ? 1:-1;
 }
 
 SynapsTraits<QQ>::RootType
--- a/include/geometry/simulator.hpp	Tue Feb 26 16:15:12 2008 -0500
+++ b/include/geometry/simulator.hpp	Tue Feb 26 16:45:25 2008 -0500
@@ -29,17 +29,20 @@
 {
 	Event* ee = new Event_(e);
 	rLog(rlSimulator, "Solving: %s", tostring(f).c_str());
-	FunctionKernel::solve(f, ee->root_stack());
-    rLog(rlSimulator, "Got solution with root stack size: %i", ee->root_stack().size());
+	int sign = FunctionKernel::sign_at_negative_infinity(f);
+    rLog(rlSimulator, "Sign at -infinity: %i", sign);
+    if (sign != 0)
+    {
+    	FunctionKernel::solve(f, ee->root_stack());
+        rLog(rlSimulator, "Got solution with root stack size: %i", ee->root_stack().size());
+    }
 
-	bool sign = FunctionKernel::sign_at_negative_infinity(f);
-    rLog(rlSimulator, "Sign at -infinity: %i", sign);
 	while (!ee->root_stack().empty() && ee->root_stack().top() < current_time())
 	{
 		ee->root_stack().pop();
-		sign = !sign;
+		sign *= -1;
 	}
-    if (!sign)
+    if (sign == -1)
     {
         AssertMsg(ee->root_stack().top() == current_time(), 
                   "If sign is negative, we must be in the degenerate case");
--- a/tests/geometry/test-kinetic-sort.cpp	Tue Feb 26 16:15:12 2008 -0500
+++ b/tests/geometry/test-kinetic-sort.cpp	Tue Feb 26 16:45:25 2008 -0500
@@ -55,6 +55,7 @@
 	// Insert polynomials and sort the list for current time
 	list.push_back(Polynomial("x^3 - 3"));
 	list.push_back(Polynomial("x^2 - 2*x - 2"));
+	list.push_back(Polynomial("x^2 - 2*x - 2"));
 	list.push_back(Polynomial("2*x - 4"));
 	list.push_back(Polynomial("x"));
 	list.push_back(Polynomial("-x + 4"));
@@ -71,7 +72,7 @@
 
     std::cout << "Examining " << simulator;
 
-	while(!simulator.reached_infinity() && simulator.current_time() < 5)
+	while(!simulator.reached_infinity())
 	{
 		std::cout << "Current time before: " << simulator.current_time() << std::endl;
 		//if (!ks.audit(&simulator)) return 1;