text: /**
   * @license
   * Copyright 2011 Dan Vanderkam (danvdk@gmail.com)
   * MIT-licensed (http://opensource.org/licenses/MIT)
   */
  
  /**
   * @fileoverview This file contains utility functions used by dygraphs. These
   * are typically static (i.e. not related to any particular dygraph). Examples
   * include date/time formatting functions, basic algorithms (e.g. binary
   * search) and generic DOM-manipulation functions.
   */
  
  /*global Dygraph:false, Node:false */
  "use strict";
  
  import * as DygraphTickers from './dygraph-tickers';
  
  export var LOG_SCALE = 10;
  export var LN_TEN = Math.log(LOG_SCALE);
  
  /**
   * @private
   * @param {number} x
   * @return {number}
   */
  export var log10 = function(x) {
    return Math.log(x) / LN_TEN;
  };
  
  /**
   * @private
   * @param {number} r0
   * @param {number} r1
   * @param {number} pct
   * @return {number}
   */
  export var logRangeFraction = function(r0, r1, pct) {
    // Computing the inverse of toPercentXCoord. The function was arrived at with
    // the following steps:
    //
    // Original calcuation:
    // pct = (log(x) - log(xRange[0])) / (log(xRange[1]) - log(xRange[0])));
    //
    // Multiply both sides by the right-side demoninator.
    // pct * (log(xRange[1] - log(xRange[0]))) = log(x) - log(xRange[0])
    //
    // add log(xRange[0]) to both sides
    // log(xRange[0]) + (pct * (log(xRange[1]) - log(xRange[0])) = log(x);
    //
    // Swap both sides of the equation,
    // log(x) = log(xRange[0]) + (pct * (log(xRange[1]) - log(xRange[0]))
    //
    // Use both sides as the exponent in 10^exp and we're done.
    // x = 10 ^ (log(xRange[0]) + (pct * (log(xRange[1]) - log(xRange[0])))
  
    var logr0 = log10(r0);
    var logr1 = log10(r1);
    var exponent = logr0 + (pct * (logr1 - logr0));
    var value = Math.pow(LOG_SCALE, exponent);
    return value;
  };
  
  /** A dotted line stroke pattern. */
  export var DOTTED_LINE = [2, 2];
  /** A dashed line stroke pattern. */
  export var DASHED_LINE = [7, 3];
  /** A dot dash stroke pattern. */
  export var DOT_DASH_LINE = [7, 2, 2, 2];
  
  // Directions for panning and zooming. Use bit operations when combined
  // values are possible.
  export var HORIZONTAL = 1;
  export var VERTICAL = 2;
  
  /**
   * Return the 2d context for a dygraph canvas.
   *
   * This method is only exposed for the sake of replacing the function in
   * automated tests.
   *
   * @param {!HTMLCanvasElement} canvas
   * @return {!CanvasRenderingContext2D}
   * @private
   */
  export var getContext = function(canvas) {
    return /** @type{!CanvasRenderingContext2D}*/(canvas.getContext("2d"));
  };
  
  /**
   * Add an event handler.
   * @param {!Node} elem The element to add the event to.
   * @param {string} type The type of the event, e.g. 'click' or 'mousemove'.
   * @param {function(Event):(boolean|undefined)} fn The function to call
   *     on the event. The function takes one parameter: the event object.
   * @private
   */
  export var addEvent = function addEvent(elem, type, fn) {
    elem.addEventListener(type, fn, false);
  };
  
  /**
   * Remove an event handler.
   * @param {!Node} elem The element to remove the event from.
   * @param {string} type The type of the event, e.g. 'click' or 'mousemove'.
   * @param {function(Event):(boolean|undefined)} fn The function to call
   *     on the event. The function takes one parameter: the event object.
   */
  export function removeEvent(elem, type, fn) {
    elem.removeEventListener(type, fn, false);
  };
  
  /**
   * Cancels further processing of an event. This is useful to prevent default
   * browser actions, e.g. highlighting text on a double-click.
   * Based on the article at
   * http://www.switchonthecode.com/tutorials/javascript-tutorial-the-scroll-wheel
   * @param {!Event} e The event whose normal behavior should be canceled.
   * @private
   */
  export function cancelEvent(e) {
    e = e ? e : window.event;
    if (e.stopPropagation) {
      e.stopPropagation();
    }
    if (e.preventDefault) {
      e.preventDefault();
    }
    e.cancelBubble = true;
    e.cancel = true;
    e.returnValue = false;
    return false;
  };
  
  /**
   * Convert hsv values to an rgb(r,g,b) string. Taken from MochiKit.Color. This
   * is used to generate default series colors which are evenly spaced on the
   * color wheel.
   * @param { number } hue Range is 0.0-1.0.
   * @param { number } saturation Range is 0.0-1.0.
   * @param { number } value Range is 0.0-1.0.
   * @return { string } "rgb(r,g,b)" where r, g and b range from 0-255.
   * @private
   */
  export function hsvToRGB(hue, saturation, value) {
    var red;
    var green;
    var blue;
    if (saturation === 0) {
      red = value;
      green = value;
      blue = value;
    } else {
      var i = Math.floor(hue * 6);
      var f = (hue * 6) - i;
      var p = value * (1 - saturation);
      var q = value * (1 - (saturation * f));
      var t = value * (1 - (saturation * (1 - f)));
      switch (i) {
        case 1: red = q; green = value; blue = p; break;
        case 2: red = p; green = value; blue = t; break;
        case 3: red = p; green = q; blue = value; break;
        case 4: red = t; green = p; blue = value; break;
        case 5: red = value; green = p; blue = q; break;
        case 6: // fall through
        case 0: red = value; green = t; blue = p; break;
      }
    }
    red = Math.floor(255 * red + 0.5);
    green = Math.floor(255 * green + 0.5);
    blue = Math.floor(255 * blue + 0.5);
    return 'rgb(' + red + ',' + green + ',' + blue + ')';
  };
  
  /**
   * Find the coordinates of an object relative to the top left of the page.
   *
   * @param {Node} obj
   * @return {{x:number,y:number}}
   * @private
   */
  export function findPos(obj) {
    var p = obj.getBoundingClientRect(),
        w = window,
        d = document.documentElement;
  
    return {
      x: p.left + (w.pageXOffset || d.scrollLeft),
      y: p.top  + (w.pageYOffset || d.scrollTop)
    }
  };
  
  /**
   * Returns the x-coordinate of the event in a coordinate system where the
   * top-left corner of the page (not the window) is (0,0).
   * Taken from MochiKit.Signal
   * @param {!Event} e
   * @return {number}
   * @private
   */
  export function pageX(e) {
    return (!e.pageX || e.pageX < 0) ? 0 : e.pageX;
  };
  
  /**
   * Returns the y-coordinate of the event in a coordinate system where the
   * top-left corner of the page (not the window) is (0,0).
   * Taken from MochiKit.Signal
   * @param {!Event} e
   * @return {number}
   * @private
   */
  export function pageY(e) {
    return (!e.pageY || e.pageY < 0) ? 0 : e.pageY;
  };
  
  /**
   * Converts page the x-coordinate of the event to pixel x-coordinates on the
   * canvas (i.e. DOM Coords).
   * @param {!Event} e Drag event.
   * @param {!DygraphInteractionContext} context Interaction context object.
   * @return {number} The amount by which the drag has moved to the right.
   */
  export function dragGetX_(e, context) {
    return pageX(e) - context.px;
  };
  
  /**
   * Converts page the y-coordinate of the event to pixel y-coordinates on the
   * canvas (i.e. DOM Coords).
   * @param {!Event} e Drag event.
   * @param {!DygraphInteractionContext} context Interaction context object.
   * @return {number} The amount by which the drag has moved down.
   */
  export function dragGetY_(e, context) {
    return pageY(e) - context.py;
  };
  
  /**
   * This returns true unless the parameter is 0, null, undefined or NaN.
   * TODO(danvk): rename this function to something like 'isNonZeroNan'.
   *
   * @param {number} x The number to consider.
   * @return {boolean} Whether the number is zero or NaN.
   * @private
   */
  export function isOK(x) {
    return !!x && !isNaN(x);
  };
  
  /**
   * @param {{x:?number,y:?number,yval:?number}} p The point to consider, valid
   *     points are {x, y} objects
   * @param {boolean=} opt_allowNaNY Treat point with y=NaN as valid
   * @return {boolean} Whether the point has numeric x and y.
   * @private
   */
  export function isValidPoint(p, opt_allowNaNY) {
    if (!p) return false;  // null or undefined object
    if (p.yval === null) return false;  // missing point
    if (p.x === null || p.x === undefined) return false;
    if (p.y === null || p.y === undefined) return false;
    if (isNaN(p.x) || (!opt_allowNaNY && isNaN(p.y))) return false;
    return true;
  };
  
  /**
   * Number formatting function which mimicks the behavior of %g in printf, i.e.
   * either exponential or fixed format (without trailing 0s) is used depending on
   * the length of the generated string.  The advantage of this format is that
   * there is a predictable upper bound on the resulting string length,
   * significant figures are not dropped, and normal numbers are not displayed in
   * exponential notation.
   *
   * NOTE: JavaScript's native toPrecision() is NOT a drop-in replacement for %g.
   * It creates strings which are too long for absolute values between 10^-4 and
   * 10^-6, e.g. '0.00001' instead of '1e-5'. See tests/number-format.html for
   * output examples.
   *
   * @param {number} x The number to format
   * @param {number=} opt_precision The precision to use, default 2.
   * @return {string} A string formatted like %g in printf.  The max generated
   *                  string length should be precision + 6 (e.g 1.123e+300).
   */
  export function floatFormat(x, opt_precision) {
    // Avoid invalid precision values; [1, 21] is the valid range.
    var p = Math.min(Math.max(1, opt_precision || 2), 21);
  
    // This is deceptively simple.  The actual algorithm comes from:
    //
    // Max allowed length = p + 4
    // where 4 comes from 'e+n' and '.'.
    //
    // Length of fixed format = 2 + y + p
    // where 2 comes from '0.' and y = # of leading zeroes.
    //
    // Equating the two and solving for y yields y = 2, or 0.00xxxx which is
    // 1.0e-3.
    //
    // Since the behavior of toPrecision() is identical for larger numbers, we
    // don't have to worry about the other bound.
    //
    // Finally, the argument for toExponential() is the number of trailing digits,
    // so we take off 1 for the value before the '.'.
    return (Math.abs(x) < 1.0e-3 && x !== 0.0) ?
        x.toExponential(p - 1) : x.toPrecision(p);
  };
  
  /**
   * Converts '9' to '09' (useful for dates)
   * @param {number} x
   * @return {string}
   * @private
   */
  export function zeropad(x) {
    if (x < 10) return "0" + x; else return "" + x;
  };
  
  /**
   * Date accessors to get the parts of a calendar date (year, month,
   * day, hour, minute, second and millisecond) according to local time,
   * and factory method to call the Date constructor with an array of arguments.
   */
  export var DateAccessorsLocal = {
    getFullYear:     d => d.getFullYear(),
    getMonth:        d => d.getMonth(),
    getDate:         d => d.getDate(),
    getHours:        d => d.getHours(),
    getMinutes:      d => d.getMinutes(),
    getSeconds:      d => d.getSeconds(),
    getMilliseconds: d => d.getMilliseconds(),
    getDay:          d => d.getDay(),
    makeDate:        function(y, m, d, hh, mm, ss, ms) {
      return new Date(y, m, d, hh, mm, ss, ms);
    }
  };
  
  /**
   * Date accessors to get the parts of a calendar date (year, month,
   * day of month, hour, minute, second and millisecond) according to UTC time,
   * and factory method to call the Date constructor with an array of arguments.
   */
  export var DateAccessorsUTC = {
    getFullYear:     d => d.getUTCFullYear(),
    getMonth:        d => d.getUTCMonth(),
    getDate:         d => d.getUTCDate(),
    getHours:        d => d.getUTCHours(),
    getMinutes:      d => d.getUTCMinutes(),
    getSeconds:      d => d.getUTCSeconds(),
    getMilliseconds: d => d.getUTCMilliseconds(),
    getDay:          d => d.getUTCDay(),
    makeDate:        function(y, m, d, hh, mm, ss, ms) {
      return new Date(Date.UTC(y, m, d, hh, mm, ss, ms));
    }
  };
  
  /**
   * Return a string version of the hours, minutes and seconds portion of a date.
   * @param {number} hh The hours (from 0-23)
   * @param {number} mm The minutes (from 0-59)
   * @param {number} ss The seconds (from 0-59)
   * @return {string} A time of the form "HH:MM" or "HH:MM:SS"
   * @private
   */
  export function hmsString_(hh, mm, ss) {
    var ret = zeropad(hh) + ":" + zeropad(mm);
    if (ss) {
      ret += ":" + zeropad(ss);
    }
    return ret;
  };
  
  /**
   * Convert a JS date (millis since epoch) to a formatted string.
   * @param {number} time The JavaScript time value (ms since epoch)
   * @param {boolean} utc Wether output UTC or local time
   * @return {string} A date of one of these forms:
   *     "YYYY/MM/DD", "YYYY/MM/DD HH:MM" or "YYYY/MM/DD HH:MM:SS"
   * @private
   */
  export function dateString_(time, utc) {
    var accessors = utc ? DateAccessorsUTC : DateAccessorsLocal;
    var date = new Date(time);
    var y = accessors.getFullYear(date);
    var m = accessors.getMonth(date);
    var d = accessors.getDate(date);
    var hh = accessors.getHours(date);
    var mm = accessors.getMinutes(date);
    var ss = accessors.getSeconds(date);
    // Get a year string:
    var year = "" + y;
    // Get a 0 padded month string
    var month = zeropad(m + 1);  //months are 0-offset, sigh
    // Get a 0 padded day string
    var day = zeropad(d);
    var frac = hh * 3600 + mm * 60 + ss;
    var ret = year + "/" + month + "/" + day;
    if (frac) {
      ret += " " + hmsString_(hh, mm, ss);
    }
    return ret;
  };
  
  /**
   * Round a number to the specified number of digits past the decimal point.
   * @param {number} num The number to round
   * @param {number} places The number of decimals to which to round
   * @return {number} The rounded number
   * @private
   */
  export function round_(num, places) {
    var shift = Math.pow(10, places);
    return Math.round(num * shift)/shift;
  };
  
  /**
   * Implementation of binary search over an array.
   * Currently does not work when val is outside the range of arry's values.
   * @param {number} val the value to search for
   * @param {Array.<number>} arry is the value over which to search
   * @param {number} abs If abs > 0, find the lowest entry greater than val
   *     If abs < 0, find the highest entry less than val.
   *     If abs == 0, find the entry that equals val.
   * @param {number=} low The first index in arry to consider (optional)
   * @param {number=} high The last index in arry to consider (optional)
   * @return {number} Index of the element, or -1 if it isn't found.
   * @private
   */
  export function binarySearch(val, arry, abs, low, high) {
    if (low === null || low === undefined ||
        high === null || high === undefined) {
      low = 0;
      high = arry.length - 1;
    }
    if (low > high) {
      return -1;
    }
    if (abs === null || abs === undefined) {
      abs = 0;
    }
    var validIndex = function(idx) {
      return idx >= 0 && idx < arry.length;
    };
    var mid = parseInt((low + high) / 2, 10);
    var element = arry[mid];
    var idx;
    if (element == val) {
      return mid;
    } else if (element > val) {
      if (abs > 0) {
        // Accept if element > val, but also if prior element < val.
        idx = mid - 1;
        if (validIndex(idx) && arry[idx] < val) {
          return mid;
        }
      }
      return binarySearch(val, arry, abs, low, mid - 1);
    } else if (element < val) {
      if (abs < 0) {
        // Accept if element < val, but also if prior element > val.
        idx = mid + 1;
        if (validIndex(idx) && arry[idx] > val) {
          return mid;
        }
      }
      return binarySearch(val, arry, abs, mid + 1, high);
    }
    return -1;  // can't actually happen, but makes closure compiler happy
  };
  
  /**
   * Parses a date, returning the number of milliseconds since epoch. This can be
   * passed in as an xValueParser in the Dygraph constructor.
   * TODO(danvk): enumerate formats that this understands.
   *
   * @param {string} dateStr A date in a variety of possible string formats.
   * @return {number} Milliseconds since epoch.
   * @private
   */
  export function dateParser(dateStr) {
    var dateStrSlashed;
    var d;
  
    // Let the system try the format first, with one caveat:
    // YYYY-MM-DD[ HH:MM:SS] is interpreted as UTC by a variety of browsers.
    // dygraphs displays dates in local time, so this will result in surprising
    // inconsistencies. But if you specify "T" or "Z" (i.e. YYYY-MM-DDTHH:MM:SS),
    // then you probably know what you're doing, so we'll let you go ahead.
    // Issue: http://code.google.com/p/dygraphs/issues/detail?id=255
    if (dateStr.search("-") == -1 ||
        dateStr.search("T") != -1 || dateStr.search("Z") != -1) {
      d = dateStrToMillis(dateStr);
      if (d && !isNaN(d)) return d;
    }
  
    if (dateStr.search("-") != -1) {  // e.g. '2009-7-12' or '2009-07-12'
      dateStrSlashed = dateStr.replace("-", "/", "g");
      while (dateStrSlashed.search("-") != -1) {
        dateStrSlashed = dateStrSlashed.replace("-", "/");
      }
      d = dateStrToMillis(dateStrSlashed);
    } else if (dateStr.length == 8) {  // e.g. '20090712'
      // TODO(danvk): remove support for this format. It's confusing.
      dateStrSlashed = dateStr.substr(0,4) + "/" + dateStr.substr(4,2) + "/" +
          dateStr.substr(6,2);
      d = dateStrToMillis(dateStrSlashed);
    } else {
      // Any format that Date.parse will accept, e.g. "2009/07/12" or
      // "2009/07/12 12:34:56"
      d = dateStrToMillis(dateStr);
    }
  
    if (!d || isNaN(d)) {
      console.error("Couldn't parse " + dateStr + " as a date");
    }
    return d;
  };
  
  /**
   * This is identical to JavaScript's built-in Date.parse() method, except that
   * it doesn't get replaced with an incompatible method by aggressive JS
   * libraries like MooTools or Joomla.
   * @param {string} str The date string, e.g. "2011/05/06"
   * @return {number} millis since epoch
   * @private
   */
  export function dateStrToMillis(str) {
    return new Date(str).getTime();
  };
  
  // These functions are all based on MochiKit.
  /**
   * Copies all the properties from o to self.
   *
   * @param {!Object} self
   * @param {!Object} o
   * @return {!Object}
   */
  export function update(self, o) {
    if (typeof(o) != 'undefined' && o !== null) {
      for (var k in o) {
        if (o.hasOwnProperty(k)) {
          self[k] = o[k];
        }
      }
    }
    return self;
  };
  
  /**
   * Copies all the properties from o to self.
   *
   * @param {!Object} self
   * @param {!Object} o
   * @return {!Object}
   * @private
   */
  export function updateDeep(self, o) {
    // Taken from http://stackoverflow.com/questions/384286/javascript-isdom-how-do-you-check-if-a-javascript-object-is-a-dom-object
    function isNode(o) {
      return (
        typeof Node === "object" ? o instanceof Node :
        typeof o === "object" && typeof o.nodeType === "number" && typeof o.nodeName==="string"
      );
    }
  
    if (typeof(o) != 'undefined' && o !== null) {
      for (var k in o) {
        if (o.hasOwnProperty(k)) {
          if (o[k] === null) {
            self[k] = null;
          } else if (isArrayLike(o[k])) {
            self[k] = o[k].slice();
          } else if (isNode(o[k])) {
            // DOM objects are shallowly-copied.
            self[k] = o[k];
          } else if (typeof(o[k]) == 'object') {
            if (typeof(self[k]) != 'object' || self[k] === null) {
              self[k] = {};
            }
            updateDeep(self[k], o[k]);
          } else {
            self[k] = o[k];
          }
        }
      }
    }
    return self;
  };
  
  /**
   * @param {*} o
   * @return {boolean}
   * @private
   */
  export function isArrayLike(o) {
    var typ = typeof(o);
    if (
        (typ != 'object' && !(typ == 'function' &&
          typeof(o.item) == 'function')) ||
        o === null ||
        typeof(o.length) != 'number' ||
        o.nodeType === 3
       ) {
      return false;
    }
    return true;
  };
  
  /**
   * @param {Object} o
   * @return {boolean}
   * @private
   */
  export function isDateLike(o) {
    if (typeof(o) != "object" || o === null ||
        typeof(o.getTime) != 'function') {
      return false;
    }
    return true;
  };
  
  /**
   * Note: this only seems to work for arrays.
   * @param {!Array} o
   * @return {!Array}
   * @private
   */
  export function clone(o) {
    // TODO(danvk): figure out how MochiKit's version works
    var r = [];
    for (var i = 0; i < o.length; i++) {
      if (isArrayLike(o[i])) {
        r.push(clone(o[i]));
      } else {
        r.push(o[i]);
      }
    }
    return r;
  };
  
  /**
   * Create a new canvas element.
   *
   * @return {!HTMLCanvasElement}
   * @private
   */
  export function createCanvas() {
    return document.createElement('canvas');
  };
  
  /**
   * Returns the context's pixel ratio, which is the ratio between the device
   * pixel ratio and the backing store ratio. Typically this is 1 for conventional
   * displays, and > 1 for HiDPI displays (such as the Retina MBP).
   * See http://www.html5rocks.com/en/tutorials/canvas/hidpi/ for more details.
   *
   * @param {!CanvasRenderingContext2D} context The canvas's 2d context.
   * @return {number} The ratio of the device pixel ratio and the backing store
   * ratio for the specified context.
   */
  export function getContextPixelRatio(context) {
    try {
      var devicePixelRatio = window.devicePixelRatio;
      var backingStoreRatio = context.webkitBackingStorePixelRatio ||
                              context.mozBackingStorePixelRatio ||
                              context.msBackingStorePixelRatio ||
                              context.oBackingStorePixelRatio ||
                              context.backingStorePixelRatio || 1;
      if (devicePixelRatio !== undefined) {
        return devicePixelRatio / backingStoreRatio;
      } else {
        // At least devicePixelRatio must be defined for this ratio to make sense.
        // We default backingStoreRatio to 1: this does not exist on some browsers
        // (i.e. desktop Chrome).
        return 1;
      }
    } catch (e) {
      return 1;
    }
  };
  
  /**
   * Checks whether the user is on an Android browser.
   * Android does not fully support the <canvas> tag, e.g. w/r/t/ clipping.
   * @return {boolean}
   * @private
   */
  export function isAndroid() {
    return (/Android/).test(navigator.userAgent);
  };
  
  
  /**
   * TODO(danvk): use @template here when it's better supported for classes.
   * @param {!Array} array
   * @param {number} start
   * @param {number} length
   * @param {function(!Array,?):boolean=} predicate
   * @constructor
   */
  export function Iterator(array, start, length, predicate) {
    start = start || 0;
    length = length || array.length;
    this.hasNext = true; // Use to identify if there's another element.
    this.peek = null; // Use for look-ahead
    this.start_ = start;
    this.array_ = array;
    this.predicate_ = predicate;
    this.end_ = Math.min(array.length, start + length);
    this.nextIdx_ = start - 1; // use -1 so initial advance works.
    this.next(); // ignoring result.
  };
  
  /**
   * @return {Object}
   */
  Iterator.prototype.next = function() {
    if (!this.hasNext) {
      return null;
    }
    var obj = this.peek;
  
    var nextIdx = this.nextIdx_ + 1;
    var found = false;
    while (nextIdx < this.end_) {
      if (!this.predicate_ || this.predicate_(this.array_, nextIdx)) {
        this.peek = this.array_[nextIdx];
        found = true;
        break;
      }
      nextIdx++;
    }
    this.nextIdx_ = nextIdx;
    if (!found) {
      this.hasNext = false;
      this.peek = null;
    }
    return obj;
  };
  
  /**
   * Returns a new iterator over array, between indexes start and
   * start + length, and only returns entries that pass the accept function
   *
   * @param {!Array} array the array to iterate over.
   * @param {number} start the first index to iterate over, 0 if absent.
   * @param {number} length the number of elements in the array to iterate over.
   *     This, along with start, defines a slice of the array, and so length
   *     doesn't imply the number of elements in the iterator when accept doesn't
   *     always accept all values. array.length when absent.
   * @param {function(?):boolean=} opt_predicate a function that takes
   *     parameters array and idx, which returns true when the element should be
   *     returned.  If omitted, all elements are accepted.
   * @private
   */
  export function createIterator(array, start, length, opt_predicate) {
    return new Iterator(array, start, length, opt_predicate);
  };
  
  // Shim layer with setTimeout fallback.
  // From: http://paulirish.com/2011/requestanimationframe-for-smart-animating/
  // Should be called with the window context:
  //   Dygraph.requestAnimFrame.call(window, function() {})
  export var requestAnimFrame = (function() {
    return window.requestAnimationFrame       ||
            window.webkitRequestAnimationFrame ||
            window.mozRequestAnimationFrame    ||
            window.oRequestAnimationFrame      ||
            window.msRequestAnimationFrame     ||
            function (callback) {
              window.setTimeout(callback, 1000 / 60);
            };
  })();
  
  /**
   * Call a function at most maxFrames times at an attempted interval of
   * framePeriodInMillis, then call a cleanup function once. repeatFn is called
   * once immediately, then at most (maxFrames - 1) times asynchronously. If
   * maxFrames==1, then cleanup_fn() is also called synchronously.  This function
   * is used to sequence animation.
   * @param {function(number)} repeatFn Called repeatedly -- takes the frame
   *     number (from 0 to maxFrames-1) as an argument.
   * @param {number} maxFrames The max number of times to call repeatFn
   * @param {number} framePeriodInMillis Max requested time between frames.
   * @param {function()} cleanupFn A function to call after all repeatFn calls.
   * @private
   */
  export function repeatAndCleanup(repeatFn, maxFrames, framePeriodInMillis,
      cleanupFn) {
    var frameNumber = 0;
    var previousFrameNumber;
    var startTime = new Date().getTime();
    repeatFn(frameNumber);
    if (maxFrames == 1) {
      cleanupFn();
      return;
    }
    var maxFrameArg = maxFrames - 1;
  
    (function loop() {
      if (frameNumber >= maxFrames) return;
      requestAnimFrame.call(window, function() {
        // Determine which frame to draw based on the delay so far.  Will skip
        // frames if necessary.
        var currentTime = new Date().getTime();
        var delayInMillis = currentTime - startTime;
        previousFrameNumber = frameNumber;
        frameNumber = Math.floor(delayInMillis / framePeriodInMillis);
        var frameDelta = frameNumber - previousFrameNumber;
        // If we predict that the subsequent repeatFn call will overshoot our
        // total frame target, so our last call will cause a stutter, then jump to
        // the last call immediately.  If we're going to cause a stutter, better
        // to do it faster than slower.
        var predictOvershootStutter = (frameNumber + frameDelta) > maxFrameArg;
        if (predictOvershootStutter || (frameNumber >= maxFrameArg)) {
          repeatFn(maxFrameArg);  // Ensure final call with maxFrameArg.
          cleanupFn();
        } else {
          if (frameDelta !== 0) {  // Don't call repeatFn with duplicate frames.
            repeatFn(frameNumber);
          }
          loop();
        }
      });
    })();
  };
  
  // A whitelist of options that do not change pixel positions.
  var pixelSafeOptions = {
    'annotationClickHandler': true,
    'annotationDblClickHandler': true,
    'annotationMouseOutHandler': true,
    'annotationMouseOverHandler': true,
    'axisLabelColor': true,
    'axisLineColor': true,
    'axisLineWidth': true,
    'clickCallback': true,
    'drawCallback': true,
    'drawHighlightPointCallback': true,
    'drawPoints': true,
    'drawPointCallback': true,
    'drawGrid': true,
    'fillAlpha': true,
    'gridLineColor': true,
    'gridLineWidth': true,
    'hideOverlayOnMouseOut': true,
    'highlightCallback': true,
    'highlightCircleSize': true,
    'interactionModel': true,
    'isZoomedIgnoreProgrammaticZoom': true,
    'labelsDiv': true,
    'labelsDivStyles': true,
    'labelsDivWidth': true,
    'labelsKMB': true,
    'labelsKMG2': true,
    'labelsSeparateLines': true,
    'labelsShowZeroValues': true,
    'legend': true,
    'panEdgeFraction': true,
    'pixelsPerYLabel': true,
    'pointClickCallback': true,
    'pointSize': true,
    'rangeSelectorPlotFillColor': true,
    'rangeSelectorPlotFillGradientColor': true,
    'rangeSelectorPlotStrokeColor': true,
    'rangeSelectorBackgroundStrokeColor': true,
    'rangeSelectorBackgroundLineWidth': true,
    'rangeSelectorPlotLineWidth': true,
    'rangeSelectorForegroundStrokeColor': true,
    'rangeSelectorForegroundLineWidth': true,
    'rangeSelectorAlpha': true,
    'showLabelsOnHighlight': true,
    'showRoller': true,
    'strokeWidth': true,
    'underlayCallback': true,
    'unhighlightCallback': true,
    'zoomCallback': true
  };
  
  /**
   * This function will scan the option list and determine if they
   * require us to recalculate the pixel positions of each point.
   * TODO: move this into dygraph-options.js
   * @param {!Array.<string>} labels a list of options to check.
   * @param {!Object} attrs
   * @return {boolean} true if the graph needs new points else false.
   * @private
   */
  export function isPixelChangingOptionList(labels, attrs) {
    // Assume that we do not require new points.
    // This will change to true if we actually do need new points.
  
    // Create a dictionary of series names for faster lookup.
    // If there are no labels, then the dictionary stays empty.
    var seriesNamesDictionary = { };
    if (labels) {
      for (var i = 1; i < labels.length; i++) {
        seriesNamesDictionary[labels[i]] = true;
      }
    }
  
    // Scan through a flat (i.e. non-nested) object of options.
    // Returns true/false depending on whether new points are needed.
    var scanFlatOptions = function(options) {
      for (var property in options) {
        if (options.hasOwnProperty(property) &&
            !pixelSafeOptions[property]) {
          return true;
        }
      }
      return false;
    };
  
    // Iterate through the list of updated options.
    for (var property in attrs) {
      if (!attrs.hasOwnProperty(property)) continue;
  
      // Find out of this field is actually a series specific options list.
      if (property == 'highlightSeriesOpts' ||
          (seriesNamesDictionary[property] && !attrs.series)) {
        // This property value is a list of options for this series.
        if (scanFlatOptions(attrs[property])) return true;
      } else if (property == 'series' || property == 'axes') {
        // This is twice-nested options list.
        var perSeries = attrs[property];
        for (var series in perSeries) {
          if (perSeries.hasOwnProperty(series) &&
              scanFlatOptions(perSeries[series])) {
            return true;
          }
        }
      } else {
        // If this was not a series specific option list, check if it's a pixel
        // changing property.
        if (!pixelSafeOptions[property]) return true;
      }
    }
  
    return false;
  };
  
  export var Circles = {
    DEFAULT : function(g, name, ctx, canvasx, canvasy, color, radius) {
      ctx.beginPath();
      ctx.fillStyle = color;
      ctx.arc(canvasx, canvasy, radius, 0, 2 * Math.PI, false);
      ctx.fill();
    }
    // For more shapes, include extras/shapes.js
  };
  
  /**
   * Determine whether |data| is delimited by CR, CRLF, LF, LFCR.
   * @param {string} data
   * @return {?string} the delimiter that was detected (or null on failure).
   */
  export function detectLineDelimiter(data) {
    for (var i = 0; i < data.length; i++) {
      var code = data.charAt(i);
      if (code === '\r') {
        // Might actually be "\r\n".
        if (((i + 1) < data.length) && (data.charAt(i + 1) === '\n')) {
          return '\r\n';
        }
        return code;
      }
      if (code === '\n') {
        // Might actually be "\n\r".
        if (((i + 1) < data.length) && (data.charAt(i + 1) === '\r')) {
          return '\n\r';
        }
        return code;
      }
    }
  
    return null;
  };
  
  /**
   * Is one node contained by another?
   * @param {Node} containee The contained node.
   * @param {Node} container The container node.
   * @return {boolean} Whether containee is inside (or equal to) container.
   * @private
   */
  export function isNodeContainedBy(containee, container) {
    if (container === null || containee === null) {
      return false;
    }
    var containeeNode = /** @type {Node} */ (containee);
    while (containeeNode && containeeNode !== container) {
      containeeNode = containeeNode.parentNode;
    }
    return (containeeNode === container);
  };
  
  // This masks some numeric issues in older versions of Firefox,
  // where 1.0/Math.pow(10,2) != Math.pow(10,-2).
  /** @type {function(number,number):number} */
  export function pow(base, exp) {
    if (exp < 0) {
      return 1.0 / Math.pow(base, -exp);
    }
    return Math.pow(base, exp);
  };
  
  var RGBA_RE = /^rgba?\((\d{1,3}),\s*(\d{1,3}),\s*(\d{1,3})(?:,\s*([01](?:\.\d+)?))?\)$/;
  
  /**
   * Helper for toRGB_ which parses strings of the form:
   * rgb(123, 45, 67)
   * rgba(123, 45, 67, 0.5)
   * @return parsed {r,g,b,a?} tuple or null.
   */
  function parseRGBA(rgbStr) {
    var bits = RGBA_RE.exec(rgbStr);
    if (!bits) return null;
    var r = parseInt(bits[1], 10),
        g = parseInt(bits[2], 10),
        b = parseInt(bits[3], 10);
    if (bits[4]) {
      return {r: r, g: g, b: b, a: parseFloat(bits[4])};
    } else {
      return {r: r, g: g, b: b};
    }
  }
  
  /**
   * Converts any valid CSS color (hex, rgb(), named color) to an RGB tuple.
   *
   * @param {!string} colorStr Any valid CSS color string.
   * @return {{r:number,g:number,b:number,a:number?}} Parsed RGB tuple.
   * @private
   */
  export function toRGB_(colorStr) {
    // Strategy: First try to parse colorStr directly. This is fast & avoids DOM
    // manipulation.  If that fails (e.g. for named colors like 'red'), then
    // create a hidden DOM element and parse its computed color.
    var rgb = parseRGBA(colorStr);
    if (rgb) return rgb;
  
    var div = document.createElement('div');
    div.style.backgroundColor = colorStr;
    div.style.visibility = 'hidden';
    document.body.appendChild(div);
    var rgbStr = window.getComputedStyle(div, null).backgroundColor;
    document.body.removeChild(div);
    return parseRGBA(rgbStr);
  };
  
  /**
   * Checks whether the browser supports the &lt;canvas&gt; tag.
   * @param {HTMLCanvasElement=} opt_canvasElement Pass a canvas element as an
   *     optimization if you have one.
   * @return {boolean} Whether the browser supports canvas.
   */
  export function isCanvasSupported(opt_canvasElement) {
    try {
      var canvas = opt_canvasElement || document.createElement("canvas");
      canvas.getContext("2d");
    } catch (e) {
      return false;
    }
    return true;
  };
  
  /**
   * Parses the value as a floating point number. This is like the parseFloat()
   * built-in, but with a few differences:
   * - the empty string is parsed as null, rather than NaN.
   * - if the string cannot be parsed at all, an error is logged.
   * If the string can't be parsed, this method returns null.
   * @param {string} x The string to be parsed
   * @param {number=} opt_line_no The line number from which the string comes.
   * @param {string=} opt_line The text of the line from which the string comes.
   */
  export function parseFloat_(x, opt_line_no, opt_line) {
    var val = parseFloat(x);
    if (!isNaN(val)) return val;
  
    // Try to figure out what happeend.
    // If the value is the empty string, parse it as null.
    if (/^ *$/.test(x)) return null;
  
    // If it was actually "NaN", return it as NaN.
    if (/^ *nan *$/i.test(x)) return NaN;
  
    // Looks like a parsing error.
    var msg = "Unable to parse '" + x + "' as a number";
    if (opt_line !== undefined && opt_line_no !== undefined) {
      msg += " on line " + (1+(opt_line_no||0)) + " ('" + opt_line + "') of CSV.";
    }
    console.error(msg);
  
    return null;
  };
  
  
  // Label constants for the labelsKMB and labelsKMG2 options.
  // (i.e. '100000' -> '100K')
  var KMB_LABELS = [ 'K', 'M', 'B', 'T', 'Q' ];
  var KMG2_BIG_LABELS = [ 'k', 'M', 'G', 'T', 'P', 'E', 'Z', 'Y' ];
  var KMG2_SMALL_LABELS = [ 'm', 'u', 'n', 'p', 'f', 'a', 'z', 'y' ];
  
  /**
   * @private
   * Return a string version of a number. This respects the digitsAfterDecimal
   * and maxNumberWidth options.
   * @param {number} x The number to be formatted
   * @param {Dygraph} opts An options view
   */
  export function numberValueFormatter(x, opts) {
    var sigFigs = opts('sigFigs');
  
    if (sigFigs !== null) {
      // User has opted for a fixed number of significant figures.
      return floatFormat(x, sigFigs);
    }
  
    var digits = opts('digitsAfterDecimal');
    var maxNumberWidth = opts('maxNumberWidth');
  
    var kmb = opts('labelsKMB');
    var kmg2 = opts('labelsKMG2');
  
    var label;
  
    // switch to scientific notation if we underflow or overflow fixed display.
    if (x !== 0.0 &&
        (Math.abs(x) >= Math.pow(10, maxNumberWidth) ||
         Math.abs(x) < Math.pow(10, -digits))) {
      label = x.toExponential(digits);
    } else {
      label = '' + round_(x, digits);
    }
  
    if (kmb || kmg2) {
      var k;
      var k_labels = [];
      var m_labels = [];
      if (kmb) {
        k = 1000;
        k_labels = KMB_LABELS;
      }
      if (kmg2) {
        if (kmb) console.warn("Setting both labelsKMB and labelsKMG2. Pick one!");
        k = 1024;
        k_labels = KMG2_BIG_LABELS;
        m_labels = KMG2_SMALL_LABELS;
      }
  
      var absx = Math.abs(x);
      var n = pow(k, k_labels.length);
      for (var j = k_labels.length - 1; j >= 0; j--, n /= k) {
        if (absx >= n) {
          label = round_(x / n, digits) + k_labels[j];
          break;
        }
      }
      if (kmg2) {
        // TODO(danvk): clean up this logic. Why so different than kmb?
        var x_parts = String(x.toExponential()).split('e-');
        if (x_parts.length === 2 && x_parts[1] >= 3 && x_parts[1] <= 24) {
          if (x_parts[1] % 3 > 0) {
            label = round_(x_parts[0] /
                pow(10, (x_parts[1] % 3)),
                digits);
          } else {
            label = Number(x_parts[0]).toFixed(2);
          }
          label += m_labels[Math.floor(x_parts[1] / 3) - 1];
        }
      }
    }
  
    return label;
  };
  
  /**
   * variant for use as an axisLabelFormatter.
   * @private
   */
  export function numberAxisLabelFormatter(x, granularity, opts) {
    return numberValueFormatter.call(this, x, opts);
  };
  
  /**
   * @type {!Array.<string>}
   * @private
   * @constant
   */
  var SHORT_MONTH_NAMES_ = ['Jan', 'Feb', 'Mar', 'Apr', 'May', 'Jun', 'Jul', 'Aug', 'Sep', 'Oct', 'Nov', 'Dec'];
  
  
  /**
   * Convert a JS date to a string appropriate to display on an axis that
   * is displaying values at the stated granularity. This respects the
   * labelsUTC option.
   * @param {Date} date The date to format
   * @param {number} granularity One of the Dygraph granularity constants
   * @param {Dygraph} opts An options view
   * @return {string} The date formatted as local time
   * @private
   */
  export function dateAxisLabelFormatter(date, granularity, opts) {
    var utc = opts('labelsUTC');
    var accessors = utc ? DateAccessorsUTC : DateAccessorsLocal;
  
    var year = accessors.getFullYear(date),
        month = accessors.getMonth(date),
        day = accessors.getDate(date),
        hours = accessors.getHours(date),
        mins = accessors.getMinutes(date),
        secs = accessors.getSeconds(date),
        millis = accessors.getSeconds(date);
  
    if (granularity >= DygraphTickers.Granularity.DECADAL) {
      return '' + year;
    } else if (granularity >= DygraphTickers.Granularity.MONTHLY) {
      return SHORT_MONTH_NAMES_[month] + '&#160;' + year;
    } else {
      var frac = hours * 3600 + mins * 60 + secs + 1e-3 * millis;
      if (frac === 0 || granularity >= DygraphTickers.Granularity.DAILY) {
        // e.g. '21 Jan' (%d%b)
        return zeropad(day) + '&#160;' + SHORT_MONTH_NAMES_[month];
      } else {
        return hmsString_(hours, mins, secs);
      }
    }
  };
  // alias in case anyone is referencing the old method.
  // Dygraph.dateAxisFormatter = Dygraph.dateAxisLabelFormatter;
  
  /**
   * Return a string version of a JS date for a value label. This respects the
   * labelsUTC option.
   * @param {Date} date The date to be formatted
   * @param {Dygraph} opts An options view
   * @private
   */
  export function dateValueFormatter(d, opts) {
    return dateString_(d, opts('labelsUTC'));
  };
  