// data is two-dimensional array of x,y; we populate y0

d3.layout.stack = function() {

  var values = Object,

      order = d3_layout_stackOrders["default"],

      offset = d3_layout_stackOffsets["zero"],

      out = d3_layout_stackOut,

      x = d3_layout_stackX,

      y = d3_layout_stackY;

  function stack(data, index) {

    // Convert series to canonical two-dimensional representation.

    var series = data.map(function(d, i) {

      return values.call(stack, d, i);

    });

    // Convert each series to canonical [[x,y]] representation.

    var points = series.map(function(d, i) {

      return d.map(function(v, i) {

        return [x.call(stack, v, i), y.call(stack, v, i)];

      });

    });

    // Compute the order of series, and permute them.

    var orders = order.call(stack, points, index);

    series = d3.permute(series, orders);

    points = d3.permute(points, orders);

    // Compute the baseline…

    var offsets = offset.call(stack, points, index);

    // And propagate it to other series.

    var n = series.length,

        m = series[0].length,

        i,

        j,

        o;

    for (j = 0; j < m; ++j) {

      out.call(stack, series[0][j], o = offsets[j], points[0][j][1]);

      for (i = 1; i < n; ++i) {

        out.call(stack, series[i][j], o += points[i - 1][j][1], points[i][j][1]);

      }

    }

    return data;

  }

  stack.values = function(x) {

    if (!arguments.length) return values;

    values = x;

    return stack;

  };

  stack.order = function(x) {

    if (!arguments.length) return order;

    order = typeof x === "function" ? x : d3_layout_stackOrders[x];

    return stack;

  };

  stack.offset = function(x) {

    if (!arguments.length) return offset;

    offset = typeof x === "function" ? x : d3_layout_stackOffsets[x];

    return stack;

  };

  stack.x = function(z) {

    if (!arguments.length) return x;

    x = z;

    return stack;

  };

  stack.y = function(z) {

    if (!arguments.length) return y;

    y = z;

    return stack;

  };

  stack.out = function(z) {

    if (!arguments.length) return out;

    out = z;

    return stack;

  };

  return stack;

}

function d3_layout_stackX(d) {

  return d.x;

}

function d3_layout_stackY(d) {

  return d.y;

}

function d3_layout_stackOut(d, y0, y) {

  d.y0 = y0;

  d.y = y;

}

var d3_layout_stackOrders = {

  "inside-out": function(data) {

    var n = data.length,

        i,

        j,

        max = data.map(d3_layout_stackMaxIndex),

        sums = data.map(d3_layout_stackReduceSum),

        index = d3.range(n).sort(function(a, b) { return max[a] - max[b]; }),

        top = 0,

        bottom = 0,

        tops = [],

        bottoms = [];

    for (i = 0; i < n; ++i) {

      j = index[i];

      if (top < bottom) {

        top += sums[j];

        tops.push(j);

      } else {

        bottom += sums[j];

        bottoms.push(j);

      }

    }

    return bottoms.reverse().concat(tops);

  },

  "reverse": function(data) {

    return d3.range(data.length).reverse();

  },

  "default": function(data) {

    return d3.range(data.length);

  }

};

var d3_layout_stackOffsets = {

  "silhouette": function(data) {

    var n = data.length,

        m = data[0].length,

        sums = [],

        max = 0,

        i,

        j,

        o,

        y0 = [];

    for (j = 0; j < m; ++j) {

      for (i = 0, o = 0; i < n; i++) o += data[i][j][1];

      if (o > max) max = o;

      sums.push(o);

    }

    for (j = 0; j < m; ++j) {

      y0[j] = (max - sums[j]) / 2;

    }

    return y0;

  },

  "wiggle": function(data) {

    var n = data.length,

        x = data[0],

        m = x.length,

        max = 0,

        i,

        j,

        k,

        s1,

        s2,

        s3,

        dx,

        o,

        o0,

        y0 = [];

    y0[0] = o = o0 = 0;

    for (j = 1; j < m; ++j) {

      for (i = 0, s1 = 0; i < n; ++i) s1 += data[i][j][1];

      for (i = 0, s2 = 0, dx = x[j][0] - x[j - 1][0]; i < n; ++i) {

        for (k = 0, s3 = (data[i][j][1] - data[i][j - 1][1]) / (2 * dx); k < i; ++k) {

          s3 += (data[k][j][1] - data[k][j - 1][1]) / dx;

        }

        s2 += s3 * data[i][j][1];

      }

      y0[j] = o -= s1 ? s2 / s1 * dx : 0;

      if (o < o0) o0 = o;

    }

    for (j = 0; j < m; ++j) y0[j] -= o0;

    return y0;

  },

  "expand": function(data) {

    var n = data.length,

        m = data[0].length,

        k = 1 / n,

        i,

        j,

        o,

        y0 = [];

    for (j = 0; j < m; ++j) {

      for (i = 0, o = 0; i < n; i++) o += data[i][j][1];

      if (o) for (i = 0; i < n; i++) data[i][j][1] /= o;

      else for (i = 0; i < n; i++) data[i][j][1] = k;

    }

    for (j = 0; j < m; ++j) y0[j] = 0;

    return y0;

  },

  "zero": function(data) {

    var j = -1,

        m = data[0].length,

        y0 = [];

    while (++j < m) y0[j] = 0;

    return y0;

  }

};

function d3_layout_stackMaxIndex(array) {

  var i = 1,

      j = 0,

      v = array[0][1],

      k,

      n = array.length;

  for (; i < n; ++i) {

    if ((k = array[i][1]) > v) {

      j = i;

      v = k;

    }

  }

  return j;

}

function d3_layout_stackReduceSum(d) {

  return d.reduce(d3_layout_stackSum, 0);

}

function d3_layout_stackSum(p, d) {

  return p + d[1];

}