From fa0d7ad80802e2b31d9889936eb6ffd55dab1f43 Mon Sep 17 00:00:00 2001
From: Klaus Weidner <klausw@google.com>
Date: Mon, 17 Dec 2012 17:50:22 -0800
Subject: [PATCH] Fix tick marks for large Y scale ranges

The tick placement logic used a double loop to look for appropriate tick spacing, assuming that a base unit around 10^50 would be sufficient to cover any Y range. Unfortunately this places 10^100 tick marks for Y values around 10^150, leading to excessive resource usage on typical client hardware.

This patch replaces the double loop with a single loop, finding the starting point by explicit calculation.

It also adds a regression test to catch the defective behavior.
---
 auto_tests/tests/range_tests.js |  9 +++++++++
 dygraph-tickers.js              | 38 +++++++++++++++++---------------------
 2 files changed, 26 insertions(+), 21 deletions(-)

diff --git a/auto_tests/tests/range_tests.js b/auto_tests/tests/range_tests.js
index 4fcb822..c2ef95e 100644
--- a/auto_tests/tests/range_tests.js
+++ b/auto_tests/tests/range_tests.js
@@ -161,3 +161,12 @@ RangeTestCase.prototype.testIncludeZeroIncludesZero = function() {
   g.updateOptions({ includeZero : false });
   assertEquals([450, 1050], g.yAxisRange(0));
 }
+
+/**
+ * Verify that very large Y ranges don't break things.
+ */ 
+RangeTestCase.prototype.testHugeRange = function() {
+  var g = new Dygraph("graph", [[0, -1e120], [1, 1e230]], { includeZero : true });
+  assertEqualsDelta(1, -1e229 / g.yAxisRange(0)[0], 0.001);
+  assertEqualsDelta(1, 1.1e230 / g.yAxisRange(0)[1], 0.001);
+}
diff --git a/dygraph-tickers.js b/dygraph-tickers.js
index b340626..457d23c 100644
--- a/dygraph-tickers.js
+++ b/dygraph-tickers.js
@@ -155,30 +155,26 @@ Dygraph.numericTicks = function(a, b, pixels, opts, dygraph, vals) {
       // The first spacing greater than pixelsPerYLabel is what we use.
       // TODO(danvk): version that works on a log scale.
       var kmg2 = opts("labelsKMG2");
-      var mults;
+      var mults, base;
       if (kmg2) {
-        mults = [1, 2, 4, 8];
+        mults = [1, 2, 4, 8, 16];
+        base = 16;
       } else {
-        mults = [1, 2, 5];
+        mults = [1, 2, 5, 10];
+        base = 10;
       }
-      var scale, low_val, high_val;
-      for (i = -10; i < 50; i++) {
-        var base_scale;
-        if (kmg2) {
-          base_scale = pow(16, i);
-        } else {
-          base_scale = pow(10, i);
-        }
-        var spacing = 0;
-        for (j = 0; j < mults.length; j++) {
-          scale = base_scale * mults[j];
-          low_val = Math.floor(a / scale) * scale;
-          high_val = Math.ceil(b / scale) * scale;
-          nTicks = Math.abs(high_val - low_val) / scale;
-          spacing = pixels / nTicks;
-          // wish I could break out of both loops at once...
-          if (spacing > pixels_per_tick) break;
-        }
+
+      var wanted_ticks = pixels / pixels_per_tick;
+      var units_per_tick = Math.abs(b - a) / wanted_ticks;
+      var base_power = Math.floor(Math.log(units_per_tick) / Math.log(base));
+      var base_scale = Math.pow(base, base_power);
+      var scale, low_val, high_val, nTicks, spacing;
+      for (j = 0; j < mults.length; j++) {
+        scale = base_scale * mults[j];
+        low_val = Math.floor(a / scale) * scale;
+        high_val = Math.ceil(b / scale) * scale;
+        nTicks = Math.abs(high_val - low_val) / scale;
+        spacing = pixels / nTicks;
         if (spacing > pixels_per_tick) break;
       }
 
-- 
2.7.4