import “../core/identity”; import “../core/noop”; import “geo”; import “stream”; import “area”; import “cartesian”; import “spherical”;

d3.geo.bounds = (function() {

var λ0, φ0, λ1, φ1, // bounds
    λ_, // previous λ-coordinate
    λ__, φ__, // first point
    p0, // previous 3D point
    dλSum,
    ranges,
    range;

var bound = {
  point: point,
  lineStart: lineStart,
  lineEnd: lineEnd,

  polygonStart: function() {
    bound.point = ringPoint;
    bound.lineStart = ringStart;
    bound.lineEnd = ringEnd;
    dλSum = 0;
    d3_geo_area.polygonStart();
  },
  polygonEnd: function() {
    d3_geo_area.polygonEnd();
    bound.point = point;
    bound.lineStart = lineStart;
    bound.lineEnd = lineEnd;
    if (d3_geo_areaRingSum < 0) λ0 = -(λ1 = 180), φ0 = -(φ1 = 90);
    else if (dλSum > ε) φ1 = 90;
    else if (dλSum < -ε) φ0 = -90;
    range[0] = λ0, range[1] = λ1;
  }
};

function point(λ, φ) {
  ranges.push(range = [λ0 = λ, λ1 = λ]);
  if (φ < φ0) φ0 = φ;
  if (φ > φ1) φ1 = φ;
}

function linePoint(λ, φ) {
  var p = d3_geo_cartesian([λ * d3_radians, φ * d3_radians]);
  if (p0) {
    var normal = d3_geo_cartesianCross(p0, p),
        equatorial = [normal[1], -normal[0], 0],
        inflection = d3_geo_cartesianCross(equatorial, normal);
    d3_geo_cartesianNormalize(inflection);
    inflection = d3_geo_spherical(inflection);
    var dλ = λ - λ_,
        s = dλ > 0 ? 1 : -1,
        λi = inflection[0] * d3_degrees * s,
        antimeridian = Math.abs(dλ) > 180;
    if (antimeridian ^ (s * λ_ < λi && λi < s * λ)) {
      var φi = inflection[1] * d3_degrees;
      if (φi > φ1) φ1 = φi;
    } else if (λi = (λi + 360) % 360 - 180, antimeridian ^ (s * λ_ < λi && λi < s * λ)) {
      var φi = -inflection[1] * d3_degrees;
      if (φi < φ0) φ0 = φi;
    } else {
      if (φ < φ0) φ0 = φ;
      if (φ > φ1) φ1 = φ;
    }
    if (antimeridian) {
      if (λ < λ_) {
        if (angle(λ0, λ) > angle(λ0, λ1)) λ1 = λ;
      } else {
        if (angle(λ, λ1) > angle(λ0, λ1)) λ0 = λ;
      }
    } else {
      if (λ1 >= λ0) {
        if (λ < λ0) λ0 = λ;
        if (λ > λ1) λ1 = λ;
      } else {
        if (λ > λ_) {
          if (angle(λ0, λ) > angle(λ0, λ1)) λ1 = λ;
        } else {
          if (angle(λ, λ1) > angle(λ0, λ1)) λ0 = λ;
        }
      }
    }
  } else {
    point(λ, φ);
  }
  p0 = p, λ_ = λ;
}

function lineStart() { bound.point = linePoint; }
function lineEnd() {
  range[0] = λ0, range[1] = λ1;
  bound.point = point;
  p0 = null;
}

function ringPoint(λ, φ) {
  if (p0) {
    var dλ = λ - λ_;
    dλSum += Math.abs(dλ) > 180 ? dλ + (dλ > 0 ? 360 : -360) : dλ;
  } else λ__ = λ, φ__ = φ;
  d3_geo_area.point(λ, φ);
  linePoint(λ, φ);
}

function ringStart() {
  d3_geo_area.lineStart();
}

function ringEnd() {
  ringPoint(λ__, φ__);
  d3_geo_area.lineEnd();
  if (Math.abs(dλSum) > ε) λ0 = -(λ1 = 180);
  range[0] = λ0, range[1] = λ1;
  p0 = null;
}

// Finds the left-right distance between two longitudes.
// This is almost the same as (λ1 - λ0 + 360°) % 360°, except that we want
// the distance between ±180° to be 360°.
function angle(λ0, λ1) { return (λ1 -= λ0) < 0 ? λ1 + 360 : λ1; }

function compareRanges(a, b) { return a[0] - b[0]; }

function withinRange(x, range) {
  return range[0] <= range[1] ? range[0] <= x && x <= range[1] : x < range[0] || range[1] < x;
}

return function(feature) {
  φ1 = λ1 = -(λ0 = φ0 = Infinity);
  ranges = [];

  d3.geo.stream(feature, bound);

  var n = ranges.length;
  if (n) {
    // First, sort ranges by their minimum longitudes.
    ranges.sort(compareRanges);

    // Then, merge any ranges that overlap.
    for (var i = 1, a = ranges[0], b, merged = [a]; i < n; ++i) {
      b = ranges[i];
      if (withinRange(b[0], a) || withinRange(b[1], a)) {
        if (angle(a[0], b[1]) > angle(a[0], a[1])) a[1] = b[1];
        if (angle(b[0], a[1]) > angle(a[0], a[1])) a[0] = b[0];
      } else {
        merged.push(a = b);
      }
    }

    // Finally, find the largest gap between the merged ranges.
    // The final bounding box will be the inverse of this gap.
    var best = -Infinity, dλ;
    for (var n = merged.length - 1, i = 0, a = merged[n], b; i <= n; a = b, ++i) {
      b = merged[i];
      if ((dλ = angle(a[1], b[0])) > best) best = dλ, λ0 = b[0], λ1 = a[1];
    }
  }
  ranges = range = null;

  return λ0 === Infinity || φ0 === Infinity
      ? [[NaN, NaN], [NaN, NaN]]
      : [[λ0, φ0], [λ1, φ1]];
};

})();