slatenails

find_rings_2.cc

Oct 16th, 2013
51
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <cstdio>
  2. #include <cstdlib>
  3. #include <deque>
  4. #include <cmath>
  5.  
  6. struct Component
  7. {   int num;
  8.     double scale;
  9. };
  10.  
  11. std::deque<Component> solution;
  12.  
  13. template<class T> inline T abs (T a)
  14. {   return (a > 0) ? a : -a;
  15. }
  16.  
  17. inline bool isZero (double a)
  18. {   return abs<double> (a) < 0.0001;
  19. }
  20.  
  21. inline bool isInteger (double a)
  22. {   return isZero (a - (int) a);
  23. }
  24.  
  25. // =============================================================================
  26. // ringFinder
  27. //
  28. // This is the main algorithm of the ring finder. It tries to use math to find
  29. // the one ring between r0 and r1. If it fails (the ring number is non-integral),
  30. // it finds an intermediate radius (ceil of the ring number times scale) and
  31. // splits the radius at this point, calling this function again to try find the
  32. // rings between r0 - r and r - r1.
  33. //
  34. // This does not always yield into usable results. If at some point r == r0 or
  35. // r == r1, there is no hope of finding the rings, at least with this algorithm,
  36. // as it would fall into an infinite recursion.
  37. // -----------------------------------------------------------------------------
  38. bool ringFinder (double r0, double r1)
  39. {   // Find the scale and number of a ring between r1 and r0.
  40.     double scale = r1 - r0;
  41.     double num = r0 / scale;
  42.  
  43.     // If the ring number is integral, we have found a fitting ring to r0 -> r1!
  44.     if (isInteger (num))
  45.     {   Component cmp;
  46.         cmp.scale = scale;
  47.         cmp.num = (int) ceil (num);
  48.         solution.push_back (cmp);
  49.     }
  50.     else
  51.     {   // If not, find an intermediate <r> between the radii
  52.         double r = ceil (num) * scale;
  53.  
  54.         // If r is the same as r0 or r1, we simply cannot find any rings between
  55.         // r0 and r1. Stop and return failure.
  56.         if (isZero (r0 - r) || isZero (r1 - r))
  57.             return false;
  58.  
  59.         // Split this ring into r0 -> r and r -> r1. Recurse to possibly find
  60.         // the rings for these. If either recurse fails, the entire algorithm
  61.         // fails as well.
  62.         if (!ringFinder (r0, r) || !ringFinder (r, r1))
  63.             return false;
  64.     }
  65.  
  66.     // The algorithm did not fail, thus we succeeded!
  67.     return true;
  68. }
  69.  
  70. int main (int argc, char* argv[])
  71. {   char* endptr0, *endptr1;
  72.     double r0, r1;
  73.  
  74.     if (argc != 3)
  75.     {   fprintf (stderr, "usage: %s <r0> <r1>\n", argv[0]);
  76.         return 1;
  77.     }
  78.  
  79.     r0 = strtod (argv[1], &endptr0);
  80.     r1 = strtod (argv[2], &endptr1);
  81.  
  82.     if (*endptr0 != '\0' || *endptr1 != '\0')
  83.     {   fprintf (stderr, "error: arguments are not numbers\n");
  84.         return 1;
  85.     }
  86.  
  87.     if (r0 > r1)
  88.         std::swap (r0, r1);
  89.  
  90.     if (!ringFinder (r0, r1))
  91.     {   printf ("Failed to find rings for %g - %g\n", r0, r1);
  92.         exit (EXIT_FAILURE);
  93.     }
  94.  
  95.     for (std::deque<Component>::iterator it = solution.begin(); it != solution.end(); ++it)
  96.         printf ("Ring %d, scale by %g (%g -> %g)\n", it->num, it->scale,
  97.             it->num * it->scale, (it->num + 1) * it->scale);
  98. }
RAW Paste Data