node_modules

10 files changed, 387 insertions, 0 deletions

diff --git a/node_modules/toposort/.npmignore b/node_modules/toposort/.npmignore
new file mode 100644
index 000000000..3c3629e64
--- /dev/null
+++ b/node_modules/toposort/.npmignore
@@ -0,0 +1 @@
+node_modules
diff --git a/node_modules/toposort/.travis.yml b/node_modules/toposort/.travis.yml
new file mode 100644
index 000000000..cba9d4a7a
--- /dev/null
+++ b/node_modules/toposort/.travis.yml
@@ -0,0 +1,5 @@
+language: node_js
+node_js:
+  - 0.8
+  - 0.6
+  - 0.10
\ No newline at end of file
diff --git a/node_modules/toposort/License b/node_modules/toposort/License
new file mode 100644
index 000000000..7975a823c
--- /dev/null
+++ b/node_modules/toposort/License
@@ -0,0 +1,21 @@
+
+Toposort - Topological sorting for node.js
+Copyright (c) 2012 by Marcel Klehr <mklehr@gmx.net>
+MIT LICENSE
+Permission is hereby granted, free of charge, to any person obtaining a copy
+of this software and associated documentation files (the "Software"), to deal
+in the Software without restriction, including without limitation the rights
+to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+copies of the Software, and to permit persons to whom the Software is
+furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in
+all copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+THE SOFTWARE.
diff --git a/node_modules/toposort/Makefile b/node_modules/toposort/Makefile
new file mode 100644
index 000000000..0f14dac30
--- /dev/null
+++ b/node_modules/toposort/Makefile
@@ -0,0 +1,11 @@
+
+build: components index.js
+	@component build --dev
+
+components: component.json
+	@component install --dev
+
+clean:
+	rm -fr build components template.js
+
+.PHONY: clean
diff --git a/node_modules/toposort/README.md b/node_modules/toposort/README.md
new file mode 100644
index 000000000..c5d46ce84
--- /dev/null
+++ b/node_modules/toposort/README.md
@@ -0,0 +1,94 @@
+# Toposort
+
+Sort directed acyclic graphs
+
+[![Build Status](https://travis-ci.org/marcelklehr/toposort.png)](https://travis-ci.org/marcelklehr/toposort)
+
+## Installation
+
+`npm install toposort` or `component install marcelklehr/toposort`  
+
+then in your code:
+
+```js
+toposort = require('toposort')
+```
+
+## Usage
+We want to sort the following graph.
+
+![graph](https://raw.githubusercontent.com/marcelklehr/toposort/master/graph.svg)
+
+```js
+// First, we define our edges.
+var graph = [
+  ['put on your shoes', 'tie your shoes']
+, ['put on your shirt', 'put on your jacket']
+, ['put on your shorts', 'put on your jacket']
+, ['put on your shorts', 'put on your shoes']
+]
+
+
+// Now, sort the vertices topologically, to reveal a legal execution order.
+toposort(graph)
+// [ 'put on your shirt'
+// , 'put on your shorts'
+// , 'put on your jacket'
+// , 'put on your shoes'
+// , 'tie your shoes' ]
+```
+
+(Note that there is no defined order for graph parts that are not connected
+ -- you could also put on your jacket after having tied your shoes...)
+
+### Sorting dependencies
+It is usually more convenient to specify *dependencies* instead of "sequences".
+```js
+// This time, edges represent dependencies.
+var graph = [
+  ['tie your shoes', 'put on your shoes']
+, ['put on your jacket', 'put on your shirt']
+, ['put on your shoes', 'put on your shorts']
+, ['put on your jacket', 'put on your shorts']
+]
+
+toposort(graph) 
+// [ 'tie your shoes'
+// , 'put on your shoes'
+// , 'put on your jacket'
+// , 'put on your shirt'
+// , 'put on your shorts' ]
+
+// Now, reversing the list will reveal a legal execution order.
+toposort(graph).reverse() 
+// [ 'put on your shorts'
+// , 'put on your shirt'
+// , 'put on your jacket'
+// , 'put on your shoes'
+// , 'tie your shoes' ]
+```
+
+## API
+
+### toposort(edges)
+
++ edges {Array} An array of directed edges describing a graph. An edge looks like this: `[node1, node2]` (vertices needn't be strings but can be of any type).
+
+Returns: {Array} a list of vertices, sorted from "start" to "end"
+
+### toposort.array(nodes, edges)
+
++ nodes {Array} An array of nodes
++ edges {Array} An array of directed edges. You don't need to mention all `nodes` here.
+
+This is a convenience method that allows you to define nodes that may or may not be connected to any other nodes. The ordering of unconnected nodes is not defined.
+
+Returns: {Array} a list of vertices, sorted from "start" to "end"
+
+## Tests
+
+Run the tests with `node test.js`.
+
+## Legal
+
+MIT License
diff --git a/node_modules/toposort/component.json b/node_modules/toposort/component.json
new file mode 100644
index 000000000..fe12ae200
--- /dev/null
+++ b/node_modules/toposort/component.json
@@ -0,0 +1,24 @@
+{
+  "name": "toposort",
+  "author": "Marcel Klehr <mklehr@gmx.net>",
+  "repo": "marcelklehr/toposort",
+  "description": "Topological sort of directed acyclic graphs (like dependency lists)",
+  "version": "0.2.10",
+  "keywords": [
+    "topological",
+    "sort",
+    "sorting",
+    "graphs",
+    "graph",
+    "dependency",
+    "list",
+    "dependencies",
+    "acyclic"
+  ],
+  "dependencies": {},
+  "development": {},
+  "license": "MIT",
+  "scripts": [
+    "index.js"
+  ]
+}
diff --git a/node_modules/toposort/graph.svg b/node_modules/toposort/graph.svg
new file mode 100644
index 000000000..e14b0d933
--- /dev/null
+++ b/node_modules/toposort/graph.svg
@@ -0,0 +1 @@
+<?xml version="1.0" encoding="UTF-8" standalone="no"?><svg xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:cc="http://creativecommons.org/ns#" xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#" xmlns:svg="http://www.w3.org/2000/svg" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:sodipodi="http://sodipodi.sourceforge.net/DTD/sodipodi-0.dtd" xmlns:inkscape="http://www.inkscape.org/namespaces/inkscape" width="105mm" height="74mm" viewBox="0 0 372.04724 262.20472" id="svg2" version="1.1" inkscape:version="0.91 r13725" sodipodi:docname="graph.svg"><defs id="defs4"><marker inkscape:isstock="true" style="overflow:visible" id="marker1" refx="0" refY="0" orient="auto" inkscape:stockid="Arrow2Mend"><path transform="scale(-0.6,-0.6)" d="M 8.7185878,4.0337352 -2.2072895,0.01601326 8.7185884,-4.0017078 c -1.7454984,2.3720609 -1.7354408,5.6174519 -6e-7,8.035443 z" style="fill:#000000;fill-opacity:1;fill-rule:evenodd;stroke:#000000;stroke-width:0.625;stroke-linejoin:round;stroke-opacity:1" id="path5631" inkscape:connector-curvature="0" /></marker></defs><sodipodi:namedview id="base" pagecolor="#ffffff" bordercolor="#666666" borderopacity="1.0" inkscape:pageopacity="0.0" inkscape:pageshadow="2" inkscape:zoom="2.2873439" inkscape:cx="185.25958" inkscape:cy="186.02362" inkscape:document-units="px" inkscape:current-layer="layer1" showgrid="false" inkscape:window-width="1920" inkscape:window-height="1016" inkscape:window-x="0" inkscape:window-y="27" inkscape:window-maximized="1" /><metadata id="metadata7"><rdf:RDF><cc:Work rdf:about=""><dc:format>image/svg+xml</dc:format><dc:type rdf:resource="http://purl.org/dc/dcmitype/StillImage" /><dc:title></dc:title></cc:Work></rdf:RDF></metadata><g inkscape:label="Layer 1" inkscape:groupmode="layer" id="layer1" transform="translate(0,-790.15748)"><ellipse ry="26.868277" rx="58.268551" cy="923.48041" cx="239.94551" id="ellipse7524" style="opacity:1;fill-opacity:0;stroke:#000000;stroke-width:1.39844525;stroke-miterlimit:4;stroke-opacity:1" /><use x="0" y="0" xlink:href="#path4136" id="use7522" transform="translate(-46.34196,80.00546)" width="100%" height="100%" /><ellipse ry="26.868277" rx="58.268551" cy="1000.4255" cx="91.301498" id="ellipse7526" style="opacity:1;fill-opacity:0;stroke:#000000;stroke-width:1.39844525;stroke-miterlimit:4;stroke-opacity:1" /><use x="0" y="0" xlink:href="#path4136" id="use7520" transform="translate(152.57872,1.3115649)" width="100%" height="100%" /><ellipse style="opacity:1;fill-opacity:0;stroke:#000000;stroke-width:1.39844525;stroke-miterlimit:4;stroke-opacity:1" id="path4136" cx="138.08064" cy="841.289" rx="58.268551" ry="26.868277" /><text xml:space="preserve" style="font-size:15.73250866px;line-height:125%;font-family:sans-serif;fill:#000000;fill-opacity:1;stroke:none;" x="86.9338" y="844.20245" id="text4138" sodipodi:linespacing="125%"><tspan sodipodi:role="line" id="tspan4140" x="86.9338" y="844.20245" style="font-size:10.48833942px">put on your shorts</tspan></text><text xml:space="preserve" style="font-size:15.73250866px;line-height:125%;font-family:sans-serif;fill:#000000;fill-opacity:1;stroke:none;" x="244.90628" y="845.17365" id="text4138-6" sodipodi:linespacing="125%"><tspan sodipodi:role="line" id="tspan4140-7" x="244.90628" y="845.17365" style="font-size:10.48833942px">put on your shirt</tspan></text><text xml:space="preserve" style="font-size:15.73250866px;line-height:125%;font-family:sans-serif;fill:#000000;fill-opacity:1;stroke:none;" x="42.908661" y="924.80731" id="text4138-3" sodipodi:linespacing="125%"><tspan sodipodi:role="line" id="tspan4140-5" x="42.908661" y="924.80731" style="font-size:10.48833942px">put on your shoes</tspan></text><text xml:space="preserve" style="font-size:15.73250866px;line-height:125%;font-family:sans-serif;fill:#000000;fill-opacity:1;stroke:none;" x="192.15384" y="926.74957" id="text4138-3-2" sodipodi:linespacing="125%"><tspan sodipodi:role="line" id="tspan4140-5-9" x="192.15384" y="926.74957" style="font-size:10.48833942px">put on your jacket</tspan></text><text xml:space="preserve" style="font-size:15.73250866px;line-height:125%;font-family:sans-serif;fill:#000000;fill-opacity:1;stroke:none;" x="54.56237" y="1002.4987" id="text4138-3-27" sodipodi:linespacing="125%"><tspan sodipodi:role="line" id="tspan4140-5-0" x="54.56237" y="1002.4987" style="font-size:10.48833942px">tie your shoes</tspan></text><path style="fill:none;stroke:#000000;stroke-width:1.39844525;stroke-linejoin:miter;stroke-miterlimit:4;stroke-opacity:1;marker-end:url(#marker1)" d="M 118.65779,866.21503 92.113228,892.75959" id="path4215" inkscape:connector-curvature="0" sodipodi:nodetypes="cc" /><path style="fill:none;stroke:#000000;stroke-width:1.39844525;stroke-linejoin:miter;stroke-miterlimit:4;stroke-opacity:1;marker-end:url(#marker1)" d="m 151.67664,868.15731 72.51197,28.48684" id="path4217" inkscape:connector-curvature="0" sodipodi:nodetypes="cc" /><path style="fill:none;stroke:#000000;stroke-width:1.39844525;stroke-linejoin:miter;stroke-miterlimit:4;stroke-opacity:1;marker-end:url(#marker1)" d="M 290.2263,869.45217 252.67546,895.3493" id="path4219" inkscape:connector-curvature="0" sodipodi:nodetypes="cc" /><path style="fill:none;stroke:#000000;stroke-width:1.39844525;stroke-linejoin:miter;stroke-miterlimit:4;stroke-opacity:1;marker-end:url(#marker1)" d="m 91.465798,949.08585 0,23.30742" id="path4221" inkscape:connector-curvature="0" sodipodi:nodetypes="cc" /></g></svg>
diff --git a/node_modules/toposort/index.js b/node_modules/toposort/index.js
new file mode 100644
index 000000000..67f131f67
--- /dev/null
+++ b/node_modules/toposort/index.js
@@ -0,0 +1,63 @@
+
+/**
+ * Topological sorting function
+ *
+ * @param {Array} edges
+ * @returns {Array}
+ */
+
+module.exports = exports = function(edges){
+  return toposort(uniqueNodes(edges), edges)
+}
+
+exports.array = toposort
+
+function toposort(nodes, edges) {
+  var cursor = nodes.length
+    , sorted = new Array(cursor)
+    , visited = {}
+    , i = cursor
+
+  while (i--) {
+    if (!visited[i]) visit(nodes[i], i, [])
+  }
+
+  return sorted
+
+  function visit(node, i, predecessors) {
+    if(predecessors.indexOf(node) >= 0) {
+      throw new Error('Cyclic dependency: '+JSON.stringify(node))
+    }
+
+    if (!~nodes.indexOf(node)) {
+      throw new Error('Found unknown node. Make sure to provided all involved nodes. Unknown node: '+JSON.stringify(node))
+    }
+
+    if (visited[i]) return;
+    visited[i] = true
+
+    // outgoing edges
+    var outgoing = edges.filter(function(edge){
+      return edge[0] === node
+    })
+    if (i = outgoing.length) {
+      var preds = predecessors.concat(node)
+      do {
+        var child = outgoing[--i][1]
+        visit(child, nodes.indexOf(child), preds)
+      } while (i)
+    }
+
+    sorted[--cursor] = node
+  }
+}
+
+function uniqueNodes(arr){
+  var res = []
+  for (var i = 0, len = arr.length; i < len; i++) {
+    var edge = arr[i]
+    if (res.indexOf(edge[0]) < 0) res.push(edge[0])
+    if (res.indexOf(edge[1]) < 0) res.push(edge[1])
+  }
+  return res
+}
diff --git a/node_modules/toposort/package.json b/node_modules/toposort/package.json
new file mode 100644
index 000000000..ad388f98e
--- /dev/null
+++ b/node_modules/toposort/package.json
@@ -0,0 +1,29 @@
+{
+  "name": "toposort",
+  "version": "1.0.3",
+  "description": "Topological sort of directed ascyclic graphs (like dependecy lists)",
+  "main": "index.js",
+  "scripts": {
+    "test": "node test.js"
+  },
+  "repository": {
+    "type": "git",
+    "url": "https://github.com/marcelklehr/toposort.git"
+  },
+  "devDependencies": {
+    "vows": "0.7.x"
+  },
+  "keywords": [
+    "topological",
+    "sort",
+    "sorting",
+    "graphs",
+    "graph",
+    "dependency",
+    "list",
+    "dependencies",
+    "acyclic"
+  ],
+  "author": "Marcel Klehr <mklehr@gmx.net>",
+  "license": "MIT"
+}
diff --git a/node_modules/toposort/test.js b/node_modules/toposort/test.js
new file mode 100644
index 000000000..10a58afe6
--- /dev/null
+++ b/node_modules/toposort/test.js
@@ -0,0 +1,138 @@
+var vows = require('vows')
+  , toposort = require('./index')
+  , assert = require('assert')
+
+var suite = vows.describe('toposort')
+suite.addBatch(
+{ 'acyclic graphs':
+  { topic: function() {
+      /*(read downwards)
+      6  3
+      |  |
+      5->2
+      |  |
+      4  1
+      */
+      return toposort(
+      [ ["3", '2']
+      , ["2", "1"]
+      , ["6", "5"]
+      , ["5", "2"]
+      , ["5", "4"]
+      ])
+    }
+  , 'should be sorted correctly': function(er, result) {
+      assert.instanceOf(result, Array)
+      var failed = [], passed
+      // valid permutations
+      ;[ [ '3','6','5','2','1','4' ]
+      , [ '3','6','5','2','4','1' ]
+      , [ '6','3','5','2','1','4' ]
+      , [ '6','5','3','2','1','4' ]
+      , [ '6','5','3','2','4','1' ]
+      , [ '6','5', '4','3','2','1' ]
+      ].forEach(function(solution) {
+        try {
+          assert.deepEqual(result, solution)
+          passed = true
+        }catch (e) {
+          failed.push(e)
+        }
+      })
+      if (!passed) {
+        console.log(failed)
+        throw failed[0];
+      }
+    }
+  }
+, 'simple cyclic graphs':
+  { topic: function() {
+      /*
+      foo<->bar
+      */
+      return toposort(
+      [ ["foo", 'bar']
+      , ["bar", "foo"]// cyclic dependecy
+      ])
+    }
+  , 'should throw an exception': function(_, val) {
+      assert.instanceOf(val, Error)
+    }
+  }
+, 'complex cyclic graphs':
+  { topic: function() {
+      /*
+      foo
+      |
+      bar<-john
+      |     ^
+      ron->tom
+      */
+      return toposort(
+      [ ["foo", 'bar']
+      , ["bar", "ron"]
+      , ["john", "bar"]
+      , ["tom", "john"]
+      , ["ron", "tom"]// cyclic dependecy
+      ])
+    }
+  , 'should throw an exception': function(_, val) {
+      assert.instanceOf(val, Error)
+    }
+  }
+, 'unknown nodes in edges':
+  { topic: function() {
+      return toposort.array(['bla']
+      [ ["foo", 'bar']
+      , ["bar", "ron"]
+      , ["john", "bar"]
+      , ["tom", "john"]
+      , ["ron", "tom"]
+      ])
+    }
+  , 'should throw an exception': function(_, val) {
+      assert.instanceOf(val, Error)
+    }
+  }
+, 'triangular dependency':
+  { topic: function() {
+      /*
+      a-> b
+      |  /
+      c<-
+      */
+      return toposort([
+        ['a', 'b']
+      , ['a', 'c']
+      , ['b', 'c']
+      ]);
+    }
+  , 'shouldn\'t throw an error': function(er, result) {
+      assert.deepEqual(result, ['a', 'b', 'c'])
+    }
+  }
+, 'toposort.array':
+  { topic: function() {
+      return toposort.array(['d', 'c', 'a', 'b'], [['a','b'],['b','c']])
+    }
+  , 'should include unconnected nodes': function(er, result){
+      var i = result.indexOf('d')
+      assert(i >= 0)
+      result.splice(i, 1)
+      assert.deepEqual(result, ['a', 'b', 'c'])
+    }
+  }
+, 'toposort.array mutation':
+  { topic: function() {
+    var array = ['d', 'c', 'a', 'b']
+    toposort.array(array, [['a','b'],['b','c']])
+    return array
+    }
+  , 'should not mutate its arguments': function(er, result){
+     assert.deepEqual(result, ['d', 'c', 'a', 'b'])
+    }
+  }
+})
+.run(null, function() {
+  (suite.results.broken+suite.results.errored) > 0 && process.exit(1)
+})