(function(){d3.time = {};

var d3_time = Date;
d3.time.format = function(template) {
  var n = template.length;

  function format(date) {
    var string = [],
        i = -1,
        j = 0,
        c,
        f;
    while (++i < n) {
      if (template.charCodeAt(i) == 37) {
        string.push(
            template.substring(j, i),
            (f = d3_time_formats[c = template.charAt(++i)])
            ? f(date) : c);
        j = i + 1;
      }
    }
    string.push(template.substring(j, i));
    return string.join("");
  }

  format.parse = function(string) {
    var date = new d3_time(1900, 0, 1),
        i = d3_time_parse(date, template, string, 0);
    if (i != string.length) return null;
    if (date.hour12) {
      var hours = date.getHours() % 12;
      date.setHours(date.hour12pm ? hours + 12 : hours);
    }
    delete date.hour12;
    delete date.hour12pm;
    return date;
  };

  format.toString = function() {
    return template;
  };

  return format;
};

function d3_time_parse(date, template, string, j) {
  var c,
      p,
      i = 0,
      n = template.length,
      m = string.length;
  while (i < n) {
    if (j >= m) return -1;
    c = template.charCodeAt(i++);
    if (c == 37) {
      p = d3_time_parsers[template.charAt(i++)];
      if (!p || ((j = p(date, string, j)) < 0)) return -1;
    } else if (c != string.charCodeAt(j++)) {
      return -1;
    }
  }
  return j;
}

var d3_time_zfill2 = d3.format("02d"),
    d3_time_zfill3 = d3.format("03d"),
    d3_time_zfill4 = d3.format("04d"),
    d3_time_sfill2 = d3.format("2d");

var d3_time_formats = {
  a: function(d) { return d3_time_weekdays[d.getDay()].substring(0, 3); },
  A: function(d) { return d3_time_weekdays[d.getDay()]; },
  b: function(d) { return d3_time_months[d.getMonth()].substring(0, 3); },
  B: function(d) { return d3_time_months[d.getMonth()]; },
  c: d3.time.format("%a %b %e %H:%M:%S %Y"),
  d: function(d) { return d3_time_zfill2(d.getDate()); },
  e: function(d) { return d3_time_sfill2(d.getDate()); },
  H: function(d) { return d3_time_zfill2(d.getHours()); },
  I: function(d) { return d3_time_zfill2(d.getHours() % 12 || 12); },
  j: d3_time_dayOfYear,
  L: function(d) { return d3_time_zfill3(d.getMilliseconds()); },
  m: function(d) { return d3_time_zfill2(d.getMonth() + 1); },
  M: function(d) { return d3_time_zfill2(d.getMinutes()); },
  p: function(d) { return d.getHours() >= 12 ? "PM" : "AM"; },
  S: function(d) { return d3_time_zfill2(d.getSeconds()); },
  U: d3_time_weekNumberSunday,
  w: function(d) { return d.getDay(); },
  W: d3_time_weekNumberMonday,
  x: d3.time.format("%m/%d/%y"),
  X: d3.time.format("%H:%M:%S"),
  y: function(d) { return d3_time_zfill2(d.getFullYear() % 100); },
  Y: function(d) { return d3_time_zfill4(d.getFullYear() % 10000); },
  Z: d3_time_zone,
  "%": function(d) { return "%"; }
};

var d3_time_parsers = {
  a: d3_time_parseWeekdayAbbrev,
  A: d3_time_parseWeekday,
  b: d3_time_parseMonthAbbrev,
  B: d3_time_parseMonth,
  c: d3_time_parseLocaleFull,
  d: d3_time_parseDay,
  e: d3_time_parseDay,
  H: d3_time_parseHour24,
  I: d3_time_parseHour12,
  // j: function(d, s, i) { /*TODO day of year [001,366] */ return i; },
  L: d3_time_parseMilliseconds,
  m: d3_time_parseMonthNumber,
  M: d3_time_parseMinutes,
  p: d3_time_parseAmPm,
  S: d3_time_parseSeconds,
  // U: function(d, s, i) { /*TODO week number (sunday) [00,53] */ return i; },
  // w: function(d, s, i) { /*TODO weekday [0,6] */ return i; },
  // W: function(d, s, i) { /*TODO week number (monday) [00,53] */ return i; },
  x: d3_time_parseLocaleDate,
  X: d3_time_parseLocaleTime,
  y: d3_time_parseYear,
  Y: d3_time_parseFullYear
  // ,
  // Z: function(d, s, i) { /*TODO time zone */ return i; },
  // "%": function(d, s, i) { /*TODO literal % */ return i; }
};

// Note: weekday is validated, but does not set the date.
function d3_time_parseWeekdayAbbrev(date, string, i) {
  return string.substring(i, i += 3).toLowerCase() in d3_time_weekdayAbbrevLookup ? i : -1;
}

var d3_time_weekdayAbbrevLookup = {
  sun: 3,
  mon: 3,
  tue: 3,
  wed: 3,
  thu: 3,
  fri: 3,
  sat: 3
};

// Note: weekday is validated, but does not set the date.
function d3_time_parseWeekday(date, string, i) {
  d3_time_weekdayRe.lastIndex = 0;
  var n = d3_time_weekdayRe.exec(string.substring(i, i + 10));
  return n ? i += n[0].length : -1;
}

var d3_time_weekdayRe = /^(?:Sunday|Monday|Tuesday|Wednesday|Thursday|Friday|Saturday)/ig;

var d3_time_weekdays = [
  "Sunday",
  "Monday",
  "Tuesday",
  "Wednesday",
  "Thursday",
  "Friday",
  "Saturday"
];

function d3_time_parseMonthAbbrev(date, string, i) {
  var n = d3_time_monthAbbrevLookup[string.substring(i, i += 3).toLowerCase()];
  return n == null ? -1 : (date.setMonth(n), i);
}

var d3_time_monthAbbrevLookup = {
  jan: 0,
  feb: 1,
  mar: 2,
  apr: 3,
  may: 4,
  jun: 5,
  jul: 6,
  aug: 7,
  sep: 8,
  oct: 9,
  nov: 10,
  dec: 11
};

function d3_time_parseMonth(date, string, i) {
  d3_time_monthRe.lastIndex = 0;
  var n = d3_time_monthRe.exec(string.substring(i, i + 12));
  return n ? (date.setMonth(d3_time_monthLookup[n[0].toLowerCase()]), i += n[0].length) : -1;
}

var d3_time_monthRe = /^(?:January|February|March|April|May|June|July|August|September|October|November|December)/ig;

var d3_time_monthLookup = {
  january: 0,
  february: 1,
  march: 2,
  april: 3,
  may: 4,
  june: 5,
  july: 6,
  august: 7,
  september: 8,
  october: 9,
  november: 10,
  december: 11
};

var d3_time_months = [
  "January",
  "February",
  "March",
  "April",
  "May",
  "June",
  "July",
  "August",
  "September",
  "October",
  "November",
  "December"
];

function d3_time_parseLocaleFull(date, string, i) {
  return d3_time_parse(date, d3_time_formats.c.toString(), string, i);
}

function d3_time_parseLocaleDate(date, string, i) {
  return d3_time_parse(date, d3_time_formats.x.toString(), string, i);
}

function d3_time_parseLocaleTime(date, string, i) {
  return d3_time_parse(date, d3_time_formats.X.toString(), string, i);
}

function d3_time_parseFullYear(date, string, i) {
  d3_time_numberRe.lastIndex = 0;
  var n = d3_time_numberRe.exec(string.substring(i, i + 4));
  return n ? (date.setFullYear(n[0]), i += n[0].length) : -1;
}

function d3_time_parseYear(date, string, i) {
  d3_time_numberRe.lastIndex = 0;
  var n = d3_time_numberRe.exec(string.substring(i, i + 2));
  return n ? (date.setFullYear(d3_time_century() + +n[0]), i += n[0].length) : -1;
}

function d3_time_century() {
  return ~~(new Date().getFullYear() / 1000) * 1000;
}

function d3_time_parseMonthNumber(date, string, i) {
  d3_time_numberRe.lastIndex = 0;
  var n = d3_time_numberRe.exec(string.substring(i, i + 2));
  return n ? (date.setMonth(n[0] - 1), i += n[0].length) : -1;
}

function d3_time_parseDay(date, string, i) {
  d3_time_numberRe.lastIndex = 0;
  var n = d3_time_numberRe.exec(string.substring(i, i + 2));
  return n ? (date.setDate(+n[0]), i += n[0].length) : -1;
}

// Note: we don't validate that the hour is in the range [0,23].
function d3_time_parseHour24(date, string, i) {
  d3_time_numberRe.lastIndex = 0;
  var n = d3_time_numberRe.exec(string.substring(i, i + 2));
  return n ? (date.setHours(+n[0]), i += n[0].length) : -1;
}

// Note: we don't validate that the hour is in the range [1,12].
function d3_time_parseHour12(date, string, i) {
  date.hour12 = true;
  return d3_time_parseHour24(date, string, i);
}

function d3_time_parseMinutes(date, string, i) {
  d3_time_numberRe.lastIndex = 0;
  var n = d3_time_numberRe.exec(string.substring(i, i + 2));
  return n ? (date.setMinutes(+n[0]), i += n[0].length) : -1;
}

function d3_time_parseSeconds(date, string, i) {
  d3_time_numberRe.lastIndex = 0;
  var n = d3_time_numberRe.exec(string.substring(i, i + 2));
  return n ? (date.setSeconds(+n[0]), i += n[0].length) : -1;
}

function d3_time_parseMilliseconds(date, string, i) {
  d3_time_numberRe.lastIndex = 0;
  var n = d3_time_numberRe.exec(string.substring(i, i + 3));
  return n ? (date.setMilliseconds(+n[0]), i += n[0].length) : -1;
}

// Note: we don't look at the next directive.
var d3_time_numberRe = /\s*\d+/;

function d3_time_parseAmPm(date, string, i) {
  var n = d3_time_amPmLookup[string.substring(i, i += 2).toLowerCase()];
  return n == null ? -1 : (date.hour12pm = n, i);
}

var d3_time_amPmLookup = {
  am: 0,
  pm: 1
};

function d3_time_year(d) {
  return new d3_time(d.getFullYear(), 0, 1);
}

function d3_time_daysElapsed(d0, d1) {
  return ~~((d1 - d0) / 864e5 - (d1.getTimezoneOffset() - d0.getTimezoneOffset()) / 1440);
}

function d3_time_dayOfYear(d) {
  return d3_time_zfill3(1 + d3_time_daysElapsed(d3_time_year(d), d));
}

function d3_time_weekNumberSunday(d) {
  var d0 = d3_time_year(d);
  return d3_time_zfill2(~~((d3_time_daysElapsed(d0, d) + d0.getDay()) / 7));
}

function d3_time_weekNumberMonday(d) {
  var d0 = d3_time_year(d);
  return d3_time_zfill2(~~((d3_time_daysElapsed(d0, d) + (d0.getDay() + 6) % 7) / 7));
}

// TODO table of time zone offset names?
function d3_time_zone(d) {
  var z = d.getTimezoneOffset(),
      zs = z > 0 ? "-" : "+",
      zh = ~~(Math.abs(z) / 60),
      zm = Math.abs(z) % 60;
  return zs + d3_time_zfill2(zh) + d3_time_zfill2(zm);
}
d3.time.format.utc = function(template) {
  var local = d3.time.format(template);

  function format(date) {
    try {
      d3_time = d3_time_format_utc;
      var utc = new d3_time();
      utc._ = date;
      return local(utc);
    } finally {
      d3_time = Date;
    }
  }

  format.parse = function(string) {
    try {
      d3_time = d3_time_format_utc;
      var date = local.parse(string);
      return date && date._;
    } finally {
      d3_time = Date;
    }
  };

  format.toString = local.toString;

  return format;
};

function d3_time_format_utc() {
  this._ = new Date(Date.UTC.apply(this, arguments));
}

d3_time_format_utc.prototype = {
  getDate: function() { return this._.getUTCDate(); },
  getDay: function() { return this._.getUTCDay(); },
  getFullYear: function() { return this._.getUTCFullYear(); },
  getHours: function() { return this._.getUTCHours(); },
  getMilliseconds: function() { return this._.getUTCMilliseconds(); },
  getMinutes: function() { return this._.getUTCMinutes(); },
  getMonth: function() { return this._.getUTCMonth(); },
  getSeconds: function() { return this._.getUTCSeconds(); },
  getTimezoneOffset: function() { return 0; },
  valueOf: function() { return this._.getTime(); },
  setDate: function(x) { this._.setUTCDate(x); },
  setDay: function(x) { this._.setUTCDay(x); },
  setFullYear: function(x) { this._.setUTCFullYear(x); },
  setHours: function(x) { this._.setUTCHours(x); },
  setMilliseconds: function(x) { this._.setUTCMilliseconds(x); },
  setMinutes: function(x) { this._.setUTCMinutes(x); },
  setMonth: function(x) { this._.setUTCMonth(x); },
  setSeconds: function(x) { this._.setUTCSeconds(x); }
};
var d3_time_formatIso = d3.time.format.utc("%Y-%m-%dT%H:%M:%S.%LZ");

d3.time.format.iso = Date.prototype.toISOString ? d3_time_formatIsoNative : d3_time_formatIso;

function d3_time_formatIsoNative(date) {
  return date.toISOString();
}

d3_time_formatIsoNative.parse = function(string) {
  return new Date(string);
};

d3_time_formatIsoNative.toString = d3_time_formatIso.toString;
function d3_time_range(floor, step, number) {
  return function(t0, t1, dt) {
    var time = floor(t0), times = [];
    if (time < t0) step(time);
    if (dt > 1) {
      while (time < t1) {
        var date = new Date(+time);
        if (!(number(date) % dt)) times.push(date);
        step(time);
      }
    } else {
      while (time < t1) times.push(new Date(+time)), step(time);
    }
    return times;
  };
}
d3.time.second = function(date) {
  return new Date(~~(date / 1e3) * 1e3);
};

d3.time.second.utc = d3.time.second;
d3.time.seconds = d3_time_range(d3.time.second, function(date) {
  date.setTime(date.getTime() + 1e3);
}, function(date) {
  return date.getSeconds();
});

d3.time.seconds.utc = d3.time.seconds;
d3.time.minute = function(date) {
  return new Date(~~(date / 6e4) * 6e4);
};

d3.time.minute.utc = d3.time.minute;d3.time.minutes = d3_time_range(d3.time.minute, d3_time_minutesStep, function(date) {
  return date.getMinutes();
});

d3.time.minutes.utc = d3_time_range(d3.time.minute, d3_time_minutesStep, function(date) {
  return date.getUTCMinutes();
});

function d3_time_minutesStep(date) {
  date.setTime(date.getTime() + 6e4); // assumes no leap seconds
}
d3.time.hour = function(date) {
  var offset = date.getTimezoneOffset() / 60;
  return new Date((~~(date / 36e5 - offset) + offset) * 36e5);
};

d3.time.hour.utc = function(date) {
  return new Date(~~(date / 36e5) * 36e5);
};
d3.time.hours = d3_time_range(d3.time.hour, d3_time_hoursStep, function(date) {
  return date.getHours();
});

d3.time.hours.utc = d3_time_range(d3.time.hour.utc, d3_time_hoursStep, function(date) {
  return date.getUTCHours();
});

function d3_time_hoursStep(date) {
  date.setTime(date.getTime() + 36e5);
}
d3.time.day = function(date) {
  return new Date(date.getFullYear(), date.getMonth(), date.getDate());
};

d3.time.day.utc = function(date) {
  return new Date(~~(date / 864e5) * 864e5);
};
d3.time.days = d3_time_range(d3.time.day, function(date) {
  date.setDate(date.getDate() + 1);
}, function(date) {
  return date.getDate() - 1;
});

d3.time.days.utc = d3_time_range(d3.time.day.utc, function(date) {
  date.setUTCDate(date.getUTCDate() + 1);
}, function(date) {
  return date.getUTCDate() - 1;
});
d3.time.week = function(date) {
  (date = d3.time.day(date)).setDate(date.getDate() - date.getDay());
  return date;
};

d3.time.week.utc = function(date) {
  (date = d3.time.day.utc(date)).setUTCDate(date.getUTCDate() - date.getUTCDay());
  return date;
};
d3.time.weeks = d3_time_range(d3.time.week, function(date) {
  date.setDate(date.getDate() + 7);
}, function(date) {
  return ~~((date - new Date(date.getFullYear(), 0, 1)) / 6048e5);
});

d3.time.weeks.utc = d3_time_range(d3.time.week.utc, function(date) {
  date.setUTCDate(date.getUTCDate() + 7);
}, function(date) {
  return ~~((date - Date.UTC(date.getUTCFullYear(), 0, 1)) / 6048e5);
});
d3.time.month = function(date) {
  return new Date(date.getFullYear(), date.getMonth(), 1);
};

d3.time.month.utc = function(date) {
  return new Date(Date.UTC(date.getUTCFullYear(), date.getUTCMonth(), 1));
};
d3.time.months = d3_time_range(d3.time.month, function(date) {
  date.setMonth(date.getMonth() + 1);
}, function(date) {
  return date.getMonth();
});

d3.time.months.utc = d3_time_range(d3.time.month.utc, function(date) {
  date.setUTCMonth(date.getUTCMonth() + 1);
}, function(date) {
  return date.getUTCMonth();
});
d3.time.year = function(date) {
  return new Date(date.getFullYear(), 0, 1);
};

d3.time.year.utc = function(date) {
  return new Date(Date.UTC(date.getUTCFullYear(), 0, 1));
};
d3.time.years = d3_time_range(d3.time.year, function(date) {
  date.setFullYear(date.getFullYear() + 1);
}, function(date) {
  return date.getFullYear();
});

d3.time.years.utc = d3_time_range(d3.time.year.utc, function(date) {
  date.setUTCFullYear(date.getUTCFullYear() + 1);
}, function(date) {
  return date.getUTCFullYear();
});
// TODO nice
function d3_time_scale(linear, methods, format) {

  function scale(x) {
    return linear(x);
  }

  scale.invert = function(x) {
    return d3_time_scaleDate(linear.invert(x));
  };

  scale.domain = function(x) {
    if (!arguments.length) return linear.domain().map(d3_time_scaleDate);
    linear.domain(x);
    return scale;
  };

  scale.ticks = function(m, k) {
    var extent = d3_time_scaleExtent(scale.domain());
    if (typeof m !== "function") {
      var span = extent[1] - extent[0],
          target = span / m,
          i = d3.bisect(d3_time_scaleSteps, target, 1, d3_time_scaleSteps.length - 1);
      if (Math.log(target / d3_time_scaleSteps[i - 1]) < Math.log(d3_time_scaleSteps[i] / target)) --i;
      m = methods[i];
      k = m[1];
      m = m[0];
    }
    return m(extent[0], extent[1], k);
  };

  scale.tickFormat = function() {
    return format;
  };

  scale.copy = function() {
    return d3_time_scale(linear.copy(), methods, format);
  };

  // TOOD expose d3_scale_linear_rebind?
  return d3.rebind(scale, linear, "range", "rangeRound", "interpolate", "clamp");
}

// TODO expose d3_scaleExtent?
function d3_time_scaleExtent(domain) {
  var start = domain[0], stop = domain[domain.length - 1];
  return start < stop ? [start, stop] : [stop, start];
}

function d3_time_scaleDate(t) {
  return new Date(t);
}

function d3_time_scaleFormat(formats) {
  return function(date) {
    var i = formats.length - 1, f = formats[i];
    while (!f[1](date)) f = formats[--i];
    return f[0](date);
  };
}

var d3_time_scaleSteps = [
  1e3,    // 1-second
  5e3,    // 5-second
  15e3,   // 15-second
  3e4,    // 30-second
  6e4,    // 1-minute
  3e5,    // 5-minute
  9e5,    // 15-minute
  18e5,   // 30-minute
  36e5,   // 1-hour
  108e5,  // 3-hour
  216e5,  // 6-hour
  432e5,  // 12-hour
  864e5,  // 1-day
  1728e5, // 2-day
  6048e5, // 1-week
  1728e6, // 1-month
  7776e6, // 3-month
  31536e6 // 1-year
];

var d3_time_scaleLocalMethods = [
  [d3.time.seconds, 1],
  [d3.time.seconds, 5],
  [d3.time.seconds, 15],
  [d3.time.seconds, 30],
  [d3.time.minutes, 1],
  [d3.time.minutes, 5],
  [d3.time.minutes, 15],
  [d3.time.minutes, 30],
  [d3.time.hours, 1],
  [d3.time.hours, 3],
  [d3.time.hours, 6],
  [d3.time.hours, 12],
  [d3.time.days, 1],
  [d3.time.days, 2],
  [d3.time.weeks, 1],
  [d3.time.months, 1],
  [d3.time.months, 3],
  [d3.time.years, 1]
];

var d3_time_scaleLocalFormats = [
  [d3.time.format("%Y"), function(d) { return true; }],
  [d3.time.format("%B"), function(d) { return d.getMonth(); }],
  [d3.time.format("%b %d"), function(d) { return d.getDate() != 1; }],
  [d3.time.format("%a %d"), function(d) { return d.getDay() && d.getDate() != 1; }],
  [d3.time.format("%I %p"), function(d) { return d.getHours(); }],
  [d3.time.format("%I:%M"), function(d) { return d.getMinutes(); }],
  [d3.time.format(":%S"), function(d) { return d.getSeconds() || d.getMilliseconds(); }]
];

var d3_time_scaleLocalFormat = d3_time_scaleFormat(d3_time_scaleLocalFormats);

d3.time.scale = function() {
  return d3_time_scale(d3.scale.linear(), d3_time_scaleLocalMethods, d3_time_scaleLocalFormat);
};
var d3_time_scaleUTCMethods = [
  [d3.time.seconds.utc, 1],
  [d3.time.seconds.utc, 5],
  [d3.time.seconds.utc, 15],
  [d3.time.seconds.utc, 30],
  [d3.time.minutes.utc, 1],
  [d3.time.minutes.utc, 5],
  [d3.time.minutes.utc, 15],
  [d3.time.minutes.utc, 30],
  [d3.time.hours.utc, 1],
  [d3.time.hours.utc, 3],
  [d3.time.hours.utc, 6],
  [d3.time.hours.utc, 12],
  [d3.time.days.utc, 1],
  [d3.time.days.utc, 2],
  [d3.time.weeks.utc, 1],
  [d3.time.months.utc, 1],
  [d3.time.months.utc, 3],
  [d3.time.years.utc, 1]
];

var d3_time_scaleUTCFormats = [
  [d3.time.format.utc("%Y"), function(d) { return true; }],
  [d3.time.format.utc("%B"), function(d) { return d.getUTCMonth(); }],
  [d3.time.format.utc("%b %d"), function(d) { return d.getUTCDate() != 1; }],
  [d3.time.format.utc("%a %d"), function(d) { return d.getUTCDay() && d.getUTCDate() != 1; }],
  [d3.time.format.utc("%I %p"), function(d) { return d.getUTCHours(); }],
  [d3.time.format.utc("%I:%M"), function(d) { return d.getUTCMinutes(); }],
  [d3.time.format.utc(":%S"), function(d) { return d.getUTCSeconds() || d.getUTCMilliseconds(); }]
];

var d3_time_scaleUTCFormat = d3_time_scaleFormat(d3_time_scaleUTCFormats);

d3.time.scale.utc = function() {
  return d3_time_scale(d3.scale.linear(), d3_time_scaleUTCMethods, d3_time_scaleUTCFormat);
};
})();