(function (global, factory) {
	typeof exports === 'object' && typeof module !== 'undefined' ? factory(exports, require('vega-dataflow'), require('vega-util'), require('d3-collection'), require('d3-hierarchy')) :
	typeof define === 'function' && define.amd ? define(['exports', 'vega-dataflow', 'vega-util', 'd3-collection', 'd3-hierarchy'], factory) :
	(factory((global.vega = global.vega || {}, global.vega.transforms = global.vega.transforms || {}),global.vega,global.vega,global.d3,global.d3));
}(this, (function (exports,vegaDataflow,vegaUtil,d3Collection,d3Hierarchy) { 'use strict';

/**
  * Nest tuples into a tree structure, grouped by key values.
  * @constructor
  * @param {object} params - The parameters for this operator.
  * @param {Array<function(object): *>} params.keys - The key fields to nest by, in order.
  * @param {function(object): *} [params.key] - Unique key field for each tuple.
  *   If not provided, the tuple id field is used.
  * @param {boolean} [params.generate=false] - A boolean flag indicating if
  *   non-leaf nodes generated by this transform should be included in the
  *   output. The default (false) includes only the input data (leaf nodes)
  *   in the data stream.
  */
function Nest(params) {
  vegaDataflow.Transform.call(this, null, params);
}

Nest.Definition = {
  "type": "Nest",
  "metadata": {"treesource": true, "changes": true},
  "params": [
    { "name": "keys", "type": "field", "array": true },
    { "name": "key", "type": "field" },
    { "name": "generate", "type": "boolean" }
  ]
};

var prototype = vegaUtil.inherits(Nest, vegaDataflow.Transform);

function children(n) {
  return n.values;
}

prototype.transform = function(_, pulse) {
  if (!pulse.source) {
    vegaUtil.error('Nest transform requires an upstream data source.');
  }

  var key = _.key || vegaDataflow.tupleid,
      gen = _.generate,
      mod = _.modified(),
      out = pulse.clone(),
      root, tree$$1, map;

  if (!this.value || mod || pulse.changed()) {
    // collect nodes to remove
    if (gen && this.value) {
      this.value.each(function(node) {
        if (node.children) out.rem.push(node);
      });
    }

    // generate new tree structure
    root = vegaUtil.array(_.keys)
      .reduce(function(n, k) { n.key(k); return n; }, d3Collection.nest())
      .entries(out.source);
    this.value = tree$$1 = d3Hierarchy.hierarchy({values: root}, children);

    // collect nodes to add
    if (gen) {
      tree$$1.each(function(node) {
        if (node.children) {
          node = vegaDataflow.ingest(node.data);
          out.add.push(node);
          out.source.push(node);
        }
      });
    }

    // build lookup table
    map = tree$$1.lookup = {};
    tree$$1.each(function(node) {
      if (vegaDataflow.tupleid(node.data) != null) {
        map[key(node.data)] = node;
      }
    });
  }

  out.source.root = this.value;
  return out;
};

/**
 * Abstract class for tree layout.
 * @constructor
 * @param {object} params - The parameters for this operator.
 */
function HierarchyLayout(params) {
  vegaDataflow.Transform.call(this, null, params);
}

var prototype$2 = vegaUtil.inherits(HierarchyLayout, vegaDataflow.Transform);

prototype$2.transform = function(_, pulse) {
  if (!pulse.source || !pulse.source.root) {
    vegaUtil.error(this.constructor.name
      + ' transform requires a backing tree data source.');
  }

  var layout = this.layout(_.method),
      fields = this.fields,
      root = pulse.source.root,
      as = _.as || fields;

  if (_.field) root.sum(_.field);
  if (_.sort) root.sort(_.sort);

  setParams(layout, this.params, _);
  try {
    this.value = layout(root);
  } catch (err) {
    vegaUtil.error(err);
  }
  root.each(function(node) { setFields(node, fields, as); });

  return pulse.reflow(_.modified()).modifies(as).modifies('leaf');
};

function setParams(layout, params, _) {
  for (var p, i=0, n=params.length; i<n; ++i) {
    p = params[i];
    if (p in _) layout[p](_[p]);
  }
}

function setFields(node, fields, as) {
  var t = node.data;
  for (var i=0, n=fields.length-1; i<n; ++i) {
    t[as[i]] = node[fields[i]];
  }
  t[as[n]] = node.children ? node.children.length : 0;
}

var Output = ['x', 'y', 'r', 'depth', 'children'];

/**
 * Packed circle tree layout.
 * @constructor
 * @param {object} params - The parameters for this operator.
 * @param {function(object): *} params.field - The value field to size nodes.
 */
function Pack(params) {
  HierarchyLayout.call(this, params);
}

Pack.Definition = {
  "type": "Pack",
  "metadata": {"tree": true, "modifies": true},
  "params": [
    { "name": "field", "type": "field" },
    { "name": "sort", "type": "compare" },
    { "name": "padding", "type": "number", "default": 0 },
    { "name": "radius", "type": "field", "default": null },
    { "name": "size", "type": "number", "array": true, "length": 2 },
    { "name": "as", "type": "string", "array": true, "length": 3, "default": Output }
  ]
};

var prototype$1 = vegaUtil.inherits(Pack, HierarchyLayout);

prototype$1.layout = d3Hierarchy.pack;

prototype$1.params = ['size', 'padding'];

prototype$1.fields = Output;

var Output$1 = ["x0", "y0", "x1", "y1", "depth", "children"];

/**
 * Partition tree layout.
 * @constructor
 * @param {object} params - The parameters for this operator.
 * @param {function(object): *} params.field - The value field to size nodes.
 */
function Partition(params) {
  HierarchyLayout.call(this, params);
}

Partition.Definition = {
  "type": "Partition",
  "metadata": {"tree": true, "modifies": true},
  "params": [
    { "name": "field", "type": "field" },
    { "name": "sort", "type": "compare" },
    { "name": "padding", "type": "number", "default": 0 },
    { "name": "round", "type": "boolean", "default": false },
    { "name": "size", "type": "number", "array": true, "length": 2 },
    { "name": "as", "type": "string", "array": true, "length": 4, "default": Output$1 }
  ]
};

var prototype$3 = vegaUtil.inherits(Partition, HierarchyLayout);

prototype$3.layout = d3Hierarchy.partition;

prototype$3.params = ['size', 'round', 'padding'];

prototype$3.fields = Output$1;

/**
  * Stratify a collection of tuples into a tree structure based on
  * id and parent id fields.
  * @constructor
  * @param {object} params - The parameters for this operator.
  * @param {function(object): *} params.key - Unique key field for each tuple.
  * @param {function(object): *} params.parentKey - Field with key for parent tuple.
  */
function Stratify(params) {
  vegaDataflow.Transform.call(this, null, params);
}

Stratify.Definition = {
  "type": "Stratify",
  "metadata": {"treesource": true},
  "params": [
    { "name": "key", "type": "field", "required": true },
    { "name": "parentKey", "type": "field", "required": true  }
  ]
};

var prototype$4 = vegaUtil.inherits(Stratify, vegaDataflow.Transform);

prototype$4.transform = function(_, pulse) {
  if (!pulse.source) {
    vegaUtil.error('Stratify transform requires an upstream data source.');
  }

  var mod = _.modified(), tree$$1, map,
      out = pulse.fork(pulse.ALL).materialize(pulse.SOURCE),
      run = !this.value
         || mod
         || pulse.changed(pulse.ADD_REM)
         || pulse.modified(_.key.fields)
         || pulse.modified(_.parentKey.fields);

  // prevent upstream source pollution
  out.source = out.source.slice();

  if (run) {
    tree$$1 = d3Hierarchy.stratify().id(_.key).parentId(_.parentKey)(out.source);
    map = tree$$1.lookup = {};
    tree$$1.each(function(node) { map[_.key(node.data)] = node; });
    this.value = tree$$1;
  }

  out.source.root = this.value;
  return out;
};

var Layouts = {
  tidy: d3Hierarchy.tree,
  cluster: d3Hierarchy.cluster
};

var Output$2 = ["x", "y", "depth", "children"];

/**
 * Tree layout. Depending on the method parameter, performs either
 * Reingold-Tilford 'tidy' layout or dendrogram 'cluster' layout.
 * @constructor
 * @param {object} params - The parameters for this operator.
 */
function Tree(params) {
  HierarchyLayout.call(this, params);
}

Tree.Definition = {
  "type": "Tree",
  "metadata": {"tree": true, "modifies": true},
  "params": [
    { "name": "field", "type": "field" },
    { "name": "sort", "type": "compare" },
    { "name": "method", "type": "enum", "default": "tidy", "values": ["tidy", "cluster"] },
    { "name": "size", "type": "number", "array": true, "length": 2 },
    { "name": "nodeSize", "type": "number", "array": true, "length": 2 },
    { "name": "as", "type": "string", "array": true, "length": 4, "default": Output$2 }
  ]
};

var prototype$5 = vegaUtil.inherits(Tree, HierarchyLayout);

/**
 * Tree layout generator. Supports both 'tidy' and 'cluster' layouts.
 */
prototype$5.layout = function(method) {
  var m = method || 'tidy';
  if (Layouts.hasOwnProperty(m)) return Layouts[m]();
  else vegaUtil.error('Unrecognized Tree layout method: ' + m);
};

prototype$5.params = ['size', 'nodeSize', 'separation'];

prototype$5.fields = Output$2;

/**
  * Generate tuples representing links between tree nodes.
  * The resulting tuples will contain 'source' and 'target' fields,
  * which point to parent and child node tuples, respectively.
  * @constructor
  * @param {object} params - The parameters for this operator.
  * @param {function(object): *} [params.key] - Unique key field for each tuple.
  *   If not provided, the tuple id field is used.
  */
function TreeLinks(params) {
  vegaDataflow.Transform.call(this, {}, params);
}

TreeLinks.Definition = {
  "type": "TreeLinks",
  "metadata": {"tree": true, "generates": true, "changes": true},
  "params": [
    { "name": "key", "type": "field" }
  ]
};

var prototype$6 = vegaUtil.inherits(TreeLinks, vegaDataflow.Transform);

function parentTuple(node) {
  var p;
  return node.parent
      && (p=node.parent.data)
      && (vegaDataflow.tupleid(p) != null) && p;
}

prototype$6.transform = function(_, pulse) {
  if (!pulse.source || !pulse.source.root) {
    vegaUtil.error('TreeLinks transform requires a backing tree data source.');
  }

  var root = pulse.source.root,
      nodes = root.lookup,
      links = this.value,
      key = _.key || vegaDataflow.tupleid,
      mods = {},
      out = pulse.fork();

  function modify(id) {
    var link = links[id];
    if (link) {
      mods[id] = 1;
      out.mod.push(link);
    }
  }

  // process removed tuples
  // assumes that if a parent node is removed the child will be, too.
  pulse.visit(pulse.REM, function(t) {
    var id = key(t),
        link = links[id];
    if (link) {
      delete links[id];
      out.rem.push(link);
    }
  });

  // create new link instances for added nodes with valid parents
  pulse.visit(pulse.ADD, function(t) {
    var id = key(t), p;
    if (p = parentTuple(nodes[id])) {
      out.add.push(links[id] = vegaDataflow.ingest({source: p, target: t}));
      mods[id] = 1;
    }
  });

  // process modified nodes and their children
  pulse.visit(pulse.MOD, function(t) {
    var id = key(t),
        node = nodes[id],
        kids = node.children;

    modify(id);
    if (kids) for (var i=0, n=kids.length; i<n; ++i) {
      if (!mods[(id=key(kids[i].data))]) modify(id);
    }
  });

  return out;
};

var Tiles = {
  binary: d3Hierarchy.treemapBinary,
  dice: d3Hierarchy.treemapDice,
  slice: d3Hierarchy.treemapSlice,
  slicedice: d3Hierarchy.treemapSliceDice,
  squarify: d3Hierarchy.treemapSquarify,
  resquarify: d3Hierarchy.treemapResquarify
};

var Output$3 = ["x0", "y0", "x1", "y1", "depth", "children"];

/**
 * Treemap layout.
 * @constructor
 * @param {object} params - The parameters for this operator.
 * @param {function(object): *} params.field - The value field to size nodes.
 */
function Treemap(params) {
  HierarchyLayout.call(this, params);
}

Treemap.Definition = {
  "type": "Treemap",
  "metadata": {"tree": true, "modifies": true},
  "params": [
    { "name": "field", "type": "field" },
    { "name": "sort", "type": "compare" },
    { "name": "method", "type": "enum", "default": "squarify",
      "values": ["squarify", "resquarify", "binary", "dice", "slice", "slicedice"] },
    { "name": "padding", "type": "number", "default": 0 },
    { "name": "paddingInner", "type": "number", "default": 0 },
    { "name": "paddingOuter", "type": "number", "default": 0 },
    { "name": "paddingTop", "type": "number", "default": 0 },
    { "name": "paddingRight", "type": "number", "default": 0 },
    { "name": "paddingBottom", "type": "number", "default": 0 },
    { "name": "paddingLeft", "type": "number", "default": 0 },
    { "name": "ratio", "type": "number", "default": 1.618033988749895 },
    { "name": "round", "type": "boolean", "default": false },
    { "name": "size", "type": "number", "array": true, "length": 2 },
    { "name": "as", "type": "string", "array": true, "length": 4, "default": Output$3 }
  ]
};

var prototype$7 = vegaUtil.inherits(Treemap, HierarchyLayout);

/**
 * Treemap layout generator. Adds 'method' and 'ratio' parameters
 * to configure the underlying tile method.
 */
prototype$7.layout = function() {
  var x = d3Hierarchy.treemap();
  x.ratio = function(_) {
    var t = x.tile();
    if (t.ratio) x.tile(t.ratio(_));
  };
  x.method = function(_) {
    if (Tiles.hasOwnProperty(_)) x.tile(Tiles[_]);
    else vegaUtil.error('Unrecognized Treemap layout method: ' + _);
  };
  return x;
};

prototype$7.params = [
  'method', 'ratio', 'size', 'round',
  'padding', 'paddingInner', 'paddingOuter',
  'paddingTop', 'paddingRight', 'paddingBottom', 'paddingLeft'
];

prototype$7.fields = Output$3;

exports.nest = Nest;
exports.pack = Pack;
exports.partition = Partition;
exports.stratify = Stratify;
exports.tree = Tree;
exports.treelinks = TreeLinks;
exports.treemap = Treemap;

Object.defineProperty(exports, '__esModule', { value: true });

})));
