From 10505f9346caa4f37bff353e5ad3d0d38fe0296a Mon Sep 17 00:00:00 2001 From: Abraham Raji Date: Mon, 30 Mar 2020 01:10:05 +0200 Subject: Import node-d3-quadtree_1.0.7.orig.tar.gz [dgit import orig node-d3-quadtree_1.0.7.orig.tar.gz] --- .eslintrc.json | 17 + .gitignore | 5 + LICENSE | 27 ++ README.md | 163 +++++++ d3-quadtree.sublime-project | 17 + package.json | 42 ++ rollup.config.js | 36 ++ src/add.js | 84 ++++ src/cover.js | 43 ++ src/data.js | 7 + src/extent.js | 5 + src/find.js | 70 +++ src/index.js | 1 + src/quad.js | 7 + src/quadtree.js | 73 +++ src/remove.js | 62 +++ src/root.js | 3 + src/size.js | 7 + src/visit.js | 16 + src/visitAfter.js | 21 + src/x.js | 7 + src/y.js | 7 + test/add-test.js | 61 +++ test/addAll-test.js | 38 ++ test/benchmark | 39 ++ test/copy-test.js | 51 ++ test/cover-test.js | 79 ++++ test/data-test.js | 17 + test/extent-test.js | 54 +++ test/find-test.js | 34 ++ test/quadtree-test.js | 27 ++ test/remove-test.js | 132 ++++++ test/size-test.js | 17 + test/visit-test.js | 60 +++ test/x-test.js | 31 ++ test/y-test.js | 31 ++ yarn.lock | 1095 +++++++++++++++++++++++++++++++++++++++++++ 37 files changed, 2486 insertions(+) create mode 100644 .eslintrc.json create mode 100644 .gitignore create mode 100644 LICENSE create mode 100644 README.md create mode 100644 d3-quadtree.sublime-project create mode 100644 package.json create mode 100644 rollup.config.js create mode 100644 src/add.js create mode 100644 src/cover.js create mode 100644 src/data.js create mode 100644 src/extent.js create mode 100644 src/find.js create mode 100644 src/index.js create mode 100644 src/quad.js create mode 100644 src/quadtree.js create mode 100644 src/remove.js create mode 100644 src/root.js create mode 100644 src/size.js create mode 100644 src/visit.js create mode 100644 src/visitAfter.js create mode 100644 src/x.js create mode 100644 src/y.js create mode 100644 test/add-test.js create mode 100644 test/addAll-test.js create mode 100755 test/benchmark create mode 100644 test/copy-test.js create mode 100644 test/cover-test.js create mode 100644 test/data-test.js create mode 100644 test/extent-test.js create mode 100644 test/find-test.js create mode 100644 test/quadtree-test.js create mode 100644 test/remove-test.js create mode 100644 test/size-test.js create mode 100644 test/visit-test.js create mode 100644 test/x-test.js create mode 100644 test/y-test.js create mode 100644 yarn.lock diff --git a/.eslintrc.json b/.eslintrc.json new file mode 100644 index 0000000..bd4d195 --- /dev/null +++ b/.eslintrc.json @@ -0,0 +1,17 @@ +{ + "extends": "eslint:recommended", + "parserOptions": { + "sourceType": "module", + "ecmaVersion": 8 + }, + "env": { + "es6": true, + "node": true, + "browser": true + }, + "rules": { + "no-cond-assign": 0, + "no-constant-condition": 0, + "no-sparse-arrays": 0 + } +} diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..8abcf6a --- /dev/null +++ b/.gitignore @@ -0,0 +1,5 @@ +*.sublime-workspace +.DS_Store +dist/ +node_modules +npm-debug.log diff --git a/LICENSE b/LICENSE new file mode 100644 index 0000000..721bd22 --- /dev/null +++ b/LICENSE @@ -0,0 +1,27 @@ +Copyright 2010-2016 Mike Bostock +All rights reserved. + +Redistribution and use in source and binary forms, with or without modification, +are permitted provided that the following conditions are met: + +* Redistributions of source code must retain the above copyright notice, this + list of conditions and the following disclaimer. + +* Redistributions in binary form must reproduce the above copyright notice, + this list of conditions and the following disclaimer in the documentation + and/or other materials provided with the distribution. + +* Neither the name of the author nor the names of contributors may be used to + endorse or promote products derived from this software without specific prior + written permission. + +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND +ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED +WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE +DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR +ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES +(INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; +LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON +ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT +(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS +SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. diff --git a/README.md b/README.md new file mode 100644 index 0000000..05692ff --- /dev/null +++ b/README.md @@ -0,0 +1,163 @@ +# d3-quadtree + +A [quadtree](https://en.wikipedia.org/wiki/Quadtree) recursively partitions two-dimensional space into squares, dividing each square into four equally-sized squares. Each distinct point exists in a unique leaf [node](#nodes); coincident points are represented by a linked list. Quadtrees can accelerate various spatial operations, such as the [Barnes–Hut approximation](https://en.wikipedia.org/wiki/Barnes–Hut_simulation) for computing many-body forces, collision detection, and searching for nearby points. + + + + +## Installing + +If you use NPM, `npm install d3-quadtree`. Otherwise, download the [latest release](https://github.com/d3/d3-quadtree/releases/latest). You can also load directly from [d3js.org](https://d3js.org), either as a [standalone library](https://d3js.org/d3-quadtree.v1.min.js) or as part of [D3](https://github.com/d3/d3). AMD, CommonJS, and vanilla environments are supported. In vanilla, a `d3` global is exported: + +```html + + +``` + +## API Reference + +# d3.quadtree([data[, x, y]]) + [<>](https://github.com/d3/d3-quadtree/blob/master/src/quadtree.js "Source") + +Creates a new, empty quadtree with an empty [extent](#quadtree_extent) and the default [*x*-](#quadtree_x) and [*y*-](#quadtree_y)accessors. If *data* is specified, [adds](#quadtree_addAll) the specified array of data to the quadtree. This is equivalent to: + +```js +var tree = d3.quadtree() + .addAll(data); +``` + +If *x* and *y* are also specified, sets the [*x*-](#quadtree_x) and [*y*-](#quadtree_y) accessors to the specified functions before adding the specified array of data to the quadtree, equivalent to: + +```js +var tree = d3.quadtree() + .x(x) + .y(y) + .addAll(data); +``` + +# quadtree.x([x]) [<>](https://github.com/d3/d3-quadtree/blob/master/src/x.js "Source") + +If *x* is specified, sets the current *x*-coordinate accessor and returns the quadtree. If *x* is not specified, returns the current *x*-accessor, which defaults to: + +```js +function x(d) { + return d[0]; +} +``` + +The *x*-acccessor is used to derive the *x*-coordinate of data when [adding](#quadtree_add) to and [removing](#quadtree_remove) from the tree. It is also used when [finding](#quadtree_find) to re-access the coordinates of data previously added to the tree; therefore, the *x*- and *y*-accessors must be consistent, returning the same value given the same input. + +# quadtree.y([y]) + [<>](https://github.com/d3/d3-quadtree/blob/master/src/y.js "Source") + +If *y* is specified, sets the current *y*-coordinate accessor and returns the quadtree. If *y* is not specified, returns the current *y*-accessor, which defaults to: + +```js +function y(d) { + return d[1]; +} +``` + +The *y*-acccessor is used to derive the *y*-coordinate of data when [adding](#quadtree_add) to and [removing](#quadtree_remove) from the tree. It is also used when [finding](#quadtree_find) to re-access the coordinates of data previously added to the tree; therefore, the *x*- and *y*-accessors must be consistent, returning the same value given the same input. + +# quadtree.extent([*extent*]) + [<>](https://github.com/d3/d3-quadtree/blob/master/src/extent.js "Source") + +If *extent* is specified, expands the quadtree to [cover](#quadtree_cover) the specified points [[*x0*, *y0*], [*x1*, *y1*]] and returns the quadtree. If *extent* is not specified, returns the quadtree’s current extent [[*x0*, *y0*], [*x1*, *y1*]], where *x0* and *y0* are the inclusive lower bounds and *x1* and *y1* are the inclusive upper bounds, or undefined if the quadtree has no extent. The extent may also be expanded by calling [*quadtree*.cover](#quadtree_cover) or [*quadtree*.add](#quadtree_add). + +# quadtree.cover(x, y) + [<>](https://github.com/d3/d3-quadtree/blob/master/src/cover.js "Source") + +Expands the quadtree to cover the specified point ⟨*x*,*y*⟩, and returns the quadtree. If the quadtree’s extent already covers the specified point, this method does nothing. If the quadtree has an extent, the extent is repeatedly doubled to cover the specified point, wrapping the [root](#quadtree_root) [node](#nodes) as necessary; if the quadtree is empty, the extent is initialized to the extent [[⌊*x*⌋, ⌊*y*⌋], [⌈*x*⌉, ⌈*y*⌉]]. (Rounding is necessary such that if the extent is later doubled, the boundaries of existing quadrants do not change due to floating point error.) + +# quadtree.add(datum) + [<>](https://github.com/d3/d3-quadtree/blob/master/src/add.js "Source") + +Adds the specified *datum* to the quadtree, deriving its coordinates ⟨*x*,*y*⟩ using the current [*x*-](#quadtree_x) and [*y*-](#quadtree_y)accessors, and returns the quadtree. If the new point is outside the current [extent](#quadtree_extent) of the quadtree, the quadtree is automatically expanded to [cover](#quadtree_cover) the new point. + +# quadtree.addAll(data) + [<>](https://github.com/d3/d3-quadtree/blob/master/src/add.js "Source") + +Adds the specified array of *data* to the quadtree, deriving each element’s coordinates ⟨*x*,*y*⟩ using the current [*x*-](#quadtree_x) and [*y*-](#quadtree_y)accessors, and return this quadtree. This is approximately equivalent to calling [*quadtree*.add](#quadtree_add) repeatedly: + +```js +for (var i = 0, n = data.length; i < n; ++i) { + quadtree.add(data[i]); +} +``` + +However, this method results in a more compact quadtree because the extent of the *data* is computed first before adding the data. + +# quadtree.remove(datum) + [<>](https://github.com/d3/d3-quadtree/blob/master/src/remove.js "Source") + +Removes the specified *datum* from the quadtree, deriving its coordinates ⟨*x*,*y*⟩ using the current [*x*-](#quadtree_x) and [*y*-](#quadtree_y)accessors, and returns the quadtree. If the specified *datum* does not exist in this quadtree, this method does nothing. + +# quadtree.removeAll(data) + [<>](https://github.com/d3/d3-quadtree/blob/master/src/remove.js "Source") + +Removes the specified *data* from the quadtree, deriving their coordinates ⟨*x*,*y*⟩ using the current [*x*-](#quadtree_x) and [*y*-](#quadtree_y)accessors, and returns the quadtree. If a specified datum does not exist in this quadtree, it is ignored. + +# quadtree.copy() + +Returns a copy of the quadtree. All [nodes](#nodes) in the returned quadtree are identical copies of the corresponding node in the quadtree; however, any data in the quadtree is shared by reference and not copied. + +# quadtree.root() + [<>](https://github.com/d3/d3-quadtree/blob/master/src/root.js "Source") + +Returns the root [node](#nodes) of the quadtree. + +# quadtree.data() + [<>](https://github.com/d3/d3-quadtree/blob/master/src/data.js "Source") + +Returns an array of all data in the quadtree. + +# quadtree.size() + [<>](https://github.com/d3/d3-quadtree/blob/master/src/size.js "Source") + +Returns the total number of data in the quadtree. + +# quadtree.find(x, y[, radius]) + [<>](https://github.com/d3/d3-quadtree/blob/master/src/find.js "Source") + +Returns the datum closest to the position ⟨*x*,*y*⟩ with the given search *radius*. If *radius* is not specified, it defaults to infinity. If there is no datum within the search area, returns undefined. + +# quadtree.visit(callback) + [<>](https://github.com/d3/d3-quadtree/blob/master/src/visit.js "Source") + +Visits each [node](#nodes) in the quadtree in pre-order traversal, invoking the specified *callback* with arguments *node*, *x0*, *y0*, *x1*, *y1* for each node, where *node* is the node being visited, ⟨*x0*, *y0*⟩ are the lower bounds of the node, and ⟨*x1*, *y1*⟩ are the upper bounds, and returns the quadtree. (Assuming that positive *x* is right and positive *y* is down, as is typically the case in Canvas and SVG, ⟨*x0*, *y0*⟩ is the top-left corner and ⟨*x1*, *y1*⟩ is the lower-right corner; however, the coordinate system is arbitrary, so more formally *x0* <= *x1* and *y0* <= *y1*.) + +If the *callback* returns true for a given node, then the children of that node are not visited; otherwise, all child nodes are visited. This can be used to quickly visit only parts of the tree, for example when using the [Barnes–Hut approximation](https://en.wikipedia.org/wiki/Barnes–Hut_simulation). Note, however, that child quadrants are always visited in sibling order: top-left, top-right, bottom-left, bottom-right. In cases such as [search](#quadtree_find), visiting siblings in a specific order may be faster. + +# quadtree.visitAfter(callback) + [<>](https://github.com/d3/d3-quadtree/blob/master/src/visitAfter.js "Source") + +Visits each [node](#nodes) in the quadtree in post-order traversal, invoking the specified *callback* with arguments *node*, *x0*, *y0*, *x1*, *y1* for each node, where *node* is the node being visited, ⟨*x0*, *y0*⟩ are the lower bounds of the node, and ⟨*x1*, *y1*⟩ are the upper bounds, and returns the quadtree. (Assuming that positive *x* is right and positive *y* is down, as is typically the case in Canvas and SVG, ⟨*x0*, *y0*⟩ is the top-left corner and ⟨*x1*, *y1*⟩ is the lower-right corner; however, the coordinate system is arbitrary, so more formally *x0* <= *x1* and *y0* <= *y1*.) Returns *root*. + +### Nodes + +Internal nodes of the quadtree are represented as four-element arrays in left-to-right, top-to-bottom order: + +* `0` - the top-left quadrant, if any. +* `1` - the top-right quadrant, if any. +* `2` - the bottom-left quadrant, if any. +* `3` - the bottom-right quadrant, if any. + +A child quadrant may be undefined if it is empty. + +Leaf nodes are represented as objects with the following properties: + +* `data` - the data associated with this point, as passed to [*quadtree*.add](#quadtree_add). +* `next` - the next datum in this leaf, if any. + +The `length` property may be used to distinguish leaf nodes from internal nodes: it is undefined for leaf nodes, and 4 for internal nodes. For example, to iterate over all data in a leaf node: + +```js +if (!node.length) do console.log(node.data); while (node = node.next); +``` + +The point’s *x*- and *y*-coordinates **must not be modified** while the point is in the quadtree. To update a point’s position, [remove](#quadtree_remove) the point and then re-[add](#quadtree_add) it to the quadtree at the new position. Alternatively, you may discard the existing quadtree entirely and create a new one from scratch; this may be more efficient if many of the points have moved. diff --git a/d3-quadtree.sublime-project b/d3-quadtree.sublime-project new file mode 100644 index 0000000..772dfa5 --- /dev/null +++ b/d3-quadtree.sublime-project @@ -0,0 +1,17 @@ +{ + "folders": [ + { + "path": ".", + "file_exclude_patterns": ["*.sublime-workspace"], + "folder_exclude_patterns": ["dist"] + } + ], + "build_systems": [ + { + "name": "yarn test", + "cmd": ["yarn", "test"], + "file_regex": "\\((...*?):([0-9]*):([0-9]*)\\)", + "working_dir": "$project_path" + } + ] +} diff --git a/package.json b/package.json new file mode 100644 index 0000000..3fd9691 --- /dev/null +++ b/package.json @@ -0,0 +1,42 @@ +{ + "name": "d3-quadtree", + "version": "1.0.7", + "description": "Two-dimensional recursive spatial subdivision.", + "keywords": [ + "d3", + "d3-module", + "quadtree" + ], + "homepage": "https://d3js.org/d3-quadtree/", + "license": "BSD-3-Clause", + "author": { + "name": "Mike Bostock", + "url": "http://bost.ocks.org/mike" + }, + "main": "dist/d3-quadtree.js", + "unpkg": "dist/d3-quadtree.min.js", + "jsdelivr": "dist/d3-quadtree.min.js", + "module": "src/index.js", + "repository": { + "type": "git", + "url": "https://github.com/d3/d3-quadtree.git" + }, + "files": [ + "dist/**/*.js", + "src/**/*.js" + ], + "scripts": { + "pretest": "rollup -c", + "test": "tape 'test/**/*-test.js' && eslint src test", + "prepublishOnly": "rm -rf dist && yarn test", + "postpublish": "git push && git push --tags && cd ../d3.github.com && git pull && cp ../${npm_package_name}/dist/${npm_package_name}.js ${npm_package_name}.v${npm_package_version%%.*}.js && cp ../${npm_package_name}/dist/${npm_package_name}.min.js ${npm_package_name}.v${npm_package_version%%.*}.min.js && git add ${npm_package_name}.v${npm_package_version%%.*}.js ${npm_package_name}.v${npm_package_version%%.*}.min.js && git commit -m \"${npm_package_name} ${npm_package_version}\" && git push && cd - && zip -j dist/${npm_package_name}.zip -- LICENSE README.md dist/${npm_package_name}.js dist/${npm_package_name}.min.js" + }, + "sideEffects": false, + "devDependencies": { + "d3-array": "1 - 2", + "eslint": "6", + "rollup": "1", + "rollup-plugin-terser": "5", + "tape": "4" + } +} diff --git a/rollup.config.js b/rollup.config.js new file mode 100644 index 0000000..804bba8 --- /dev/null +++ b/rollup.config.js @@ -0,0 +1,36 @@ +import {terser} from "rollup-plugin-terser"; +import * as meta from "./package.json"; + +const config = { + input: "src/index.js", + external: Object.keys(meta.dependencies || {}).filter(key => /^d3-/.test(key)), + output: { + file: `dist/${meta.name}.js`, + name: "d3", + format: "umd", + indent: false, + extend: true, + banner: `// ${meta.homepage} v${meta.version} Copyright ${(new Date).getFullYear()} ${meta.author.name}`, + globals: Object.assign({}, ...Object.keys(meta.dependencies || {}).filter(key => /^d3-/.test(key)).map(key => ({[key]: "d3"}))) + }, + plugins: [] +}; + +export default [ + config, + { + ...config, + output: { + ...config.output, + file: `dist/${meta.name}.min.js` + }, + plugins: [ + ...config.plugins, + terser({ + output: { + preamble: config.output.banner + } + }) + ] + } +]; diff --git a/src/add.js b/src/add.js new file mode 100644 index 0000000..ac7c4d1 --- /dev/null +++ b/src/add.js @@ -0,0 +1,84 @@ +export default function(d) { + var x = +this._x.call(null, d), + y = +this._y.call(null, d); + return add(this.cover(x, y), x, y, d); +} + +function add(tree, x, y, d) { + if (isNaN(x) || isNaN(y)) return tree; // ignore invalid points + + var parent, + node = tree._root, + leaf = {data: d}, + x0 = tree._x0, + y0 = tree._y0, + x1 = tree._x1, + y1 = tree._y1, + xm, + ym, + xp, + yp, + right, + bottom, + i, + j; + + // If the tree is empty, initialize the root as a leaf. + if (!node) return tree._root = leaf, tree; + + // Find the existing leaf for the new point, or add it. + while (node.length) { + if (right = x >= (xm = (x0 + x1) / 2)) x0 = xm; else x1 = xm; + if (bottom = y >= (ym = (y0 + y1) / 2)) y0 = ym; else y1 = ym; + if (parent = node, !(node = node[i = bottom << 1 | right])) return parent[i] = leaf, tree; + } + + // Is the new point is exactly coincident with the existing point? + xp = +tree._x.call(null, node.data); + yp = +tree._y.call(null, node.data); + if (x === xp && y === yp) return leaf.next = node, parent ? parent[i] = leaf : tree._root = leaf, tree; + + // Otherwise, split the leaf node until the old and new point are separated. + do { + parent = parent ? parent[i] = new Array(4) : tree._root = new Array(4); + if (right = x >= (xm = (x0 + x1) / 2)) x0 = xm; else x1 = xm; + if (bottom = y >= (ym = (y0 + y1) / 2)) y0 = ym; else y1 = ym; + } while ((i = bottom << 1 | right) === (j = (yp >= ym) << 1 | (xp >= xm))); + return parent[j] = node, parent[i] = leaf, tree; +} + +export function addAll(data) { + var d, i, n = data.length, + x, + y, + xz = new Array(n), + yz = new Array(n), + x0 = Infinity, + y0 = Infinity, + x1 = -Infinity, + y1 = -Infinity; + + // Compute the points and their extent. + for (i = 0; i < n; ++i) { + if (isNaN(x = +this._x.call(null, d = data[i])) || isNaN(y = +this._y.call(null, d))) continue; + xz[i] = x; + yz[i] = y; + if (x < x0) x0 = x; + if (x > x1) x1 = x; + if (y < y0) y0 = y; + if (y > y1) y1 = y; + } + + // If there were no (valid) points, abort. + if (x0 > x1 || y0 > y1) return this; + + // Expand the tree to cover the new points. + this.cover(x0, y0).cover(x1, y1); + + // Add the new points. + for (i = 0; i < n; ++i) { + add(this, xz[i], yz[i], data[i]); + } + + return this; +} diff --git a/src/cover.js b/src/cover.js new file mode 100644 index 0000000..a981a3d --- /dev/null +++ b/src/cover.js @@ -0,0 +1,43 @@ +export default function(x, y) { + if (isNaN(x = +x) || isNaN(y = +y)) return this; // ignore invalid points + + var x0 = this._x0, + y0 = this._y0, + x1 = this._x1, + y1 = this._y1; + + // If the quadtree has no extent, initialize them. + // Integer extent are necessary so that if we later double the extent, + // the existing quadrant boundaries don’t change due to floating point error! + if (isNaN(x0)) { + x1 = (x0 = Math.floor(x)) + 1; + y1 = (y0 = Math.floor(y)) + 1; + } + + // Otherwise, double repeatedly to cover. + else { + var z = x1 - x0, + node = this._root, + parent, + i; + + while (x0 > x || x >= x1 || y0 > y || y >= y1) { + i = (y < y0) << 1 | (x < x0); + parent = new Array(4), parent[i] = node, node = parent, z *= 2; + switch (i) { + case 0: x1 = x0 + z, y1 = y0 + z; break; + case 1: x0 = x1 - z, y1 = y0 + z; break; + case 2: x1 = x0 + z, y0 = y1 - z; break; + case 3: x0 = x1 - z, y0 = y1 - z; break; + } + } + + if (this._root && this._root.length) this._root = node; + } + + this._x0 = x0; + this._y0 = y0; + this._x1 = x1; + this._y1 = y1; + return this; +} diff --git a/src/data.js b/src/data.js new file mode 100644 index 0000000..e934fa9 --- /dev/null +++ b/src/data.js @@ -0,0 +1,7 @@ +export default function() { + var data = []; + this.visit(function(node) { + if (!node.length) do data.push(node.data); while (node = node.next) + }); + return data; +} diff --git a/src/extent.js b/src/extent.js new file mode 100644 index 0000000..9e65a90 --- /dev/null +++ b/src/extent.js @@ -0,0 +1,5 @@ +export default function(_) { + return arguments.length + ? this.cover(+_[0][0], +_[0][1]).cover(+_[1][0], +_[1][1]) + : isNaN(this._x0) ? undefined : [[this._x0, this._y0], [this._x1, this._y1]]; +} diff --git a/src/find.js b/src/find.js new file mode 100644 index 0000000..e9db6c4 --- /dev/null +++ b/src/find.js @@ -0,0 +1,70 @@ +import Quad from "./quad.js"; + +export default function(x, y, radius) { + var data, + x0 = this._x0, + y0 = this._y0, + x1, + y1, + x2, + y2, + x3 = this._x1, + y3 = this._y1, + quads = [], + node = this._root, + q, + i; + + if (node) quads.push(new Quad(node, x0, y0, x3, y3)); + if (radius == null) radius = Infinity; + else { + x0 = x - radius, y0 = y - radius; + x3 = x + radius, y3 = y + radius; + radius *= radius; + } + + while (q = quads.pop()) { + + // Stop searching if this quadrant can’t contain a closer node. + if (!(node = q.node) + || (x1 = q.x0) > x3 + || (y1 = q.y0) > y3 + || (x2 = q.x1) < x0 + || (y2 = q.y1) < y0) continue; + + // Bisect the current quadrant. + if (node.length) { + var xm = (x1 + x2) / 2, + ym = (y1 + y2) / 2; + + quads.push( + new Quad(node[3], xm, ym, x2, y2), + new Quad(node[2], x1, ym, xm, y2), + new Quad(node[1], xm, y1, x2, ym), + new Quad(node[0], x1, y1, xm, ym) + ); + + // Visit the closest quadrant first. + if (i = (y >= ym) << 1 | (x >= xm)) { + q = quads[quads.length - 1]; + quads[quads.length - 1] = quads[quads.length - 1 - i]; + quads[quads.length - 1 - i] = q; + } + } + + // Visit this point. (Visiting coincident points isn’t necessary!) + else { + var dx = x - +this._x.call(null, node.data), + dy = y - +this._y.call(null, node.data), + d2 = dx * dx + dy * dy; + if (d2 < radius) { + var d = Math.sqrt(radius = d2); + x0 = x - d, y0 = y - d; + x3 = x + d, y3 = y + d; + data = node.data; + } + } + } + + return data; +} diff --git a/src/index.js b/src/index.js new file mode 100644 index 0000000..e2b2c31 --- /dev/null +++ b/src/index.js @@ -0,0 +1 @@ +export {default as quadtree} from "./quadtree.js"; diff --git a/src/quad.js b/src/quad.js new file mode 100644 index 0000000..6f714db --- /dev/null +++ b/src/quad.js @@ -0,0 +1,7 @@ +export default function(node, x0, y0, x1, y1) { + this.node = node; + this.x0 = x0; + this.y0 = y0; + this.x1 = x1; + this.y1 = y1; +} diff --git a/src/quadtree.js b/src/quadtree.js new file mode 100644 index 0000000..5d58593 --- /dev/null +++ b/src/quadtree.js @@ -0,0 +1,73 @@ +import tree_add, {addAll as tree_addAll} from "./add.js"; +import tree_cover from "./cover.js"; +import tree_data from "./data.js"; +import tree_extent from "./extent.js"; +import tree_find from "./find.js"; +import tree_remove, {removeAll as tree_removeAll} from "./remove.js"; +import tree_root from "./root.js"; +import tree_size from "./size.js"; +import tree_visit from "./visit.js"; +import tree_visitAfter from "./visitAfter.js"; +import tree_x, {defaultX} from "./x.js"; +import tree_y, {defaultY} from "./y.js"; + +export default function quadtree(nodes, x, y) { + var tree = new Quadtree(x == null ? defaultX : x, y == null ? defaultY : y, NaN, NaN, NaN, NaN); + return nodes == null ? tree : tree.addAll(nodes); +} + +function Quadtree(x, y, x0, y0, x1, y1) { + this._x = x; + this._y = y; + this._x0 = x0; + this._y0 = y0; + this._x1 = x1; + this._y1 = y1; + this._root = undefined; +} + +function leaf_copy(leaf) { + var copy = {data: leaf.data}, next = copy; + while (leaf = leaf.next) next = next.next = {data: leaf.data}; + return copy; +} + +var treeProto = quadtree.prototype = Quadtree.prototype; + +treeProto.copy = function() { + var copy = new Quadtree(this._x, this._y, this._x0, this._y0, this._x1, this._y1), + node = this._root, + nodes, + child; + + if (!node) return copy; + + if (!node.length) return copy._root = leaf_copy(node), copy; + + nodes = [{source: node, target: copy._root = new Array(4)}]; + while (node = nodes.pop()) { + for (var i = 0; i < 4; ++i) { + if (child = node.source[i]) { + if (child.length) nodes.push({source: child, target: node.target[i] = new Array(4)}); + else node.target[i] = leaf_copy(child); + } + } + } + + return copy; +}; + +treeProto.add = tree_add; +treeProto.addAll = tree_addAll; +treeProto.cover = tree_cover; +treeProto.data = tree_data; +treeProto.extent = tree_extent; +treeProto.find = tree_find; +treeProto.remove = tree_remove; +treeProto.removeAll = tree_removeAll; +treeProto.root = tree_root; +treeProto.size = tree_size; +treeProto.visit = tree_visit; +treeProto.visitAfter = tree_visitAfter; +treeProto.x = tree_x; +treeProto.y = tree_y; diff --git a/src/remove.js b/src/remove.js new file mode 100644 index 0000000..0ba27ab --- /dev/null +++ b/src/remove.js @@ -0,0 +1,62 @@ +export default function(d) { + if (isNaN(x = +this._x.call(null, d)) || isNaN(y = +this._y.call(null, d))) return this; // ignore invalid points + + var parent, + node = this._root, + retainer, + previous, + next, + x0 = this._x0, + y0 = this._y0, + x1 = this._x1, + y1 = this._y1, + x, + y, + xm, + ym, + right, + bottom, + i, + j; + + // If the tree is empty, initialize the root as a leaf. + if (!node) return this; + + // Find the leaf node for the point. + // While descending, also retain the deepest parent with a non-removed sibling. + if (node.length) while (true) { + if (right = x >= (xm = (x0 + x1) / 2)) x0 = xm; else x1 = xm; + if (bottom = y >= (ym = (y0 + y1) / 2)) y0 = ym; else y1 = ym; + if (!(parent = node, node = node[i = bottom << 1 | right])) return this; + if (!node.length) break; + if (parent[(i + 1) & 3] || parent[(i + 2) & 3] || parent[(i + 3) & 3]) retainer = parent, j = i; + } + + // Find the point to remove. + while (node.data !== d) if (!(previous = node, node = node.next)) return this; + if (next = node.next) delete node.next; + + // If there are multiple coincident points, remove just the point. + if (previous) return (next ? previous.next = next : delete previous.next), this; + + // If this is the root point, remove it. + if (!parent) return this._root = next, this; + + // Remove this leaf. + next ? parent[i] = next : delete parent[i]; + + // If the parent now contains exactly one leaf, collapse superfluous parents. + if ((node = parent[0] || parent[1] || parent[2] || parent[3]) + && node === (parent[3] || parent[2] || parent[1] || parent[0]) + && !node.length) { + if (retainer) retainer[j] = node; + else this._root = node; + } + + return this; +} + +export function removeAll(data) { + for (var i = 0, n = data.length; i < n; ++i) this.remove(data[i]); + return this; +} diff --git a/src/root.js b/src/root.js new file mode 100644 index 0000000..c32889f --- /dev/null +++ b/src/root.js @@ -0,0 +1,3 @@ +export default function() { + return this._root; +} diff --git a/src/size.js b/src/size.js new file mode 100644 index 0000000..d2d5ab6 --- /dev/null +++ b/src/size.js @@ -0,0 +1,7 @@ +export default function() { + var size = 0; + this.visit(function(node) { + if (!node.length) do ++size; while (node = node.next) + }); + return size; +} diff --git a/src/visit.js b/src/visit.js new file mode 100644 index 0000000..941ab88 --- /dev/null +++ b/src/visit.js @@ -0,0 +1,16 @@ +import Quad from "./quad.js"; + +export default function(callback) { + var quads = [], q, node = this._root, child, x0, y0, x1, y1; + if (node) quads.push(new Quad(node, this._x0, this._y0, this._x1, this._y1)); + while (q = quads.pop()) { + if (!callback(node = q.node, x0 = q.x0, y0 = q.y0, x1 = q.x1, y1 = q.y1) && node.length) { + var xm = (x0 + x1) / 2, ym = (y0 + y1) / 2; + if (child = node[3]) quads.push(new Quad(child, xm, ym, x1, y1)); + if (child = node[2]) quads.push(new Quad(child, x0, ym, xm, y1)); + if (child = node[1]) quads.push(new Quad(child, xm, y0, x1, ym)); + if (child = node[0]) quads.push(new Quad(child, x0, y0, xm, ym)); + } + } + return this; +} diff --git a/src/visitAfter.js b/src/visitAfter.js new file mode 100644 index 0000000..2096655 --- /dev/null +++ b/src/visitAfter.js @@ -0,0 +1,21 @@ +import Quad from "./quad.js"; + +export default function(callback) { + var quads = [], next = [], q; + if (this._root) quads.push(new Quad(this._root, this._x0, this._y0, this._x1, this._y1)); + while (q = quads.pop()) { + var node = q.node; + if (node.length) { + var child, x0 = q.x0, y0 = q.y0, x1 = q.x1, y1 = q.y1, xm = (x0 + x1) / 2, ym = (y0 + y1) / 2; + if (child = node[0]) quads.push(new Quad(child, x0, y0, xm, ym)); + if (child = node[1]) quads.push(new Quad(child, xm, y0, x1, ym)); + if (child = node[2]) quads.push(new Quad(child, x0, ym, xm, y1)); + if (child = node[3]) quads.push(new Quad(child, xm, ym, x1, y1)); + } + next.push(q); + } + while (q = next.pop()) { + callback(q.node, q.x0, q.y0, q.x1, q.y1); + } + return this; +} diff --git a/src/x.js b/src/x.js new file mode 100644 index 0000000..ffea507 --- /dev/null +++ b/src/x.js @@ -0,0 +1,7 @@ +export function defaultX(d) { + return d[0]; +} + +export default function(_) { + return arguments.length ? (this._x = _, this) : this._x; +} diff --git a/src/y.js b/src/y.js new file mode 100644 index 0000000..d2d29cb --- /dev/null +++ b/src/y.js @@ -0,0 +1,7 @@ +export function defaultY(d) { + return d[1]; +} + +export default function(_) { + return arguments.length ? (this._y = _, this) : this._y; +} diff --git a/test/add-test.js b/test/add-test.js new file mode 100644 index 0000000..58eb468 --- /dev/null +++ b/test/add-test.js @@ -0,0 +1,61 @@ +var tape = require("tape"), + d3_quadtree = require("../"); + +tape("quadtree.add(datum) creates a new point and adds it to the quadtree", function(test) { + var q = d3_quadtree.quadtree(); + test.deepEqual(q.add([0.0, 0.0]).root(), {data: [0, 0]}); + test.deepEqual(q.add([0.9, 0.9]).root(), [{data: [0, 0]},,, {data: [0.9, 0.9]}]); + test.deepEqual(q.add([0.9, 0.0]).root(), [{data: [0, 0]}, {data: [0.9, 0]},, {data: [0.9, 0.9]}]); + test.deepEqual(q.add([0.0, 0.9]).root(), [{data: [0, 0]}, {data: [0.9, 0]}, {data: [0, 0.9]}, {data: [0.9, 0.9]}]); + test.deepEqual(q.add([0.4, 0.4]).root(), [[{data: [0, 0]},,, {data: [0.4, 0.4]}], {data: [0.9, 0]}, {data: [0, 0.9]}, {data: [0.9, 0.9]}]); + test.end(); +}); + +tape("quadtree.add(datum) handles points being on the perimeter of the quadtree bounds", function(test) { + var q = d3_quadtree.quadtree().extent([[0, 0], [1, 1]]); + test.deepEqual(q.add([0, 0]).root(), {data: [0, 0]}); + test.deepEqual(q.add([1, 1]).root(), [{data: [0, 0]},,, {data: [1, 1]}]); + test.deepEqual(q.add([1, 0]).root(), [{data: [0, 0]}, {data: [1, 0]},, {data: [1, 1]}]); + test.deepEqual(q.add([0, 1]).root(), [{data: [0, 0]}, {data: [1, 0]}, {data: [0, 1]}, {data: [1, 1]}]); + test.end(); +}); + +tape("quadtree.add(datum) handles points being to the top of the quadtree bounds", function(test) { + var q = d3_quadtree.quadtree().extent([[0, 0], [2, 2]]); + test.deepEqual(q.add([1, -1]).extent(), [[0, -4], [8, 4]]); + test.end(); +}); + +tape("quadtree.add(datum) handles points being to the right of the quadtree bounds", function(test) { + var q = d3_quadtree.quadtree().extent([[0, 0], [2, 2]]); + test.deepEqual(q.add([3, 1]).extent(), [[0, 0], [4, 4]]); + test.end(); +}); + +tape("quadtree.add(datum) handles points being to the bottom of the quadtree bounds", function(test) { + var q = d3_quadtree.quadtree().extent([[0, 0], [2, 2]]); + test.deepEqual(q.add([1, 3]).extent(), [[0, 0], [4, 4]]); + test.end(); +}); + +tape("quadtree.add(datum) handles points being to the left of the quadtree bounds", function(test) { + var q = d3_quadtree.quadtree().extent([[0, 0], [2, 2]]); + test.deepEqual(q.add([-1, 1]).extent(), [[-4, 0], [4, 8]]); + test.end(); +}); + +tape("quadtree.add(datum) handles coincident points by creating a linked list", function(test) { + var q = d3_quadtree.quadtree().extent([[0, 0], [1, 1]]); + test.deepEqual(q.add([0, 0]).root(), {data: [0, 0]}); + test.deepEqual(q.add([1, 0]).root(), [{data: [0, 0]}, {data: [1, 0]},, ]); + test.deepEqual(q.add([0, 1]).root(), [{data: [0, 0]}, {data: [1, 0]}, {data: [0, 1]}, ]); + test.deepEqual(q.add([0, 1]).root(), [{data: [0, 0]}, {data: [1, 0]}, {data: [0, 1], next: {data: [0, 1]}}, ]); + test.end(); +}); + +tape("quadtree.add(datum) implicitly defines trivial bounds for the first point", function(test) { + var q = d3_quadtree.quadtree().add([1, 2]); + test.deepEqual(q.extent(), [[1, 2], [2, 3]]); + test.deepEqual(q.root(), {data: [1, 2]}); + test.end(); +}); diff --git a/test/addAll-test.js b/test/addAll-test.js new file mode 100644 index 0000000..97f1678 --- /dev/null +++ b/test/addAll-test.js @@ -0,0 +1,38 @@ +var tape = require("tape"), + d3_quadtree = require("../"); + +tape("quadtree.addAll(data) creates new points and adds them to the quadtree", function(test) { + var q = d3_quadtree.quadtree(); + test.deepEqual(q.add([0.0, 0.0]).root(), {data: [0, 0]}); + test.deepEqual(q.add([0.9, 0.9]).root(), [{data: [0, 0]},,, {data: [0.9, 0.9]}]); + test.deepEqual(q.add([0.9, 0.0]).root(), [{data: [0, 0]}, {data: [0.9, 0]},, {data: [0.9, 0.9]}]); + test.deepEqual(q.add([0.0, 0.9]).root(), [{data: [0, 0]}, {data: [0.9, 0]}, {data: [0, 0.9]}, {data: [0.9, 0.9]}]); + test.deepEqual(q.add([0.4, 0.4]).root(), [[{data: [0, 0]},,, {data: [0.4, 0.4]}], {data: [0.9, 0]}, {data: [0, 0.9]}, {data: [0.9, 0.9]}]); + test.end(); +}); + +tape("quadtree.addAll(data) ignores points with NaN coordinates", function(test) { + var q = d3_quadtree.quadtree(); + test.deepEqual(q.addAll([[NaN, 0], [0, NaN]]).root(), undefined); + test.equal(q.extent(), undefined); + test.deepEqual(q.addAll([[0, 0], [0.9, 0.9]]).root(), [{data: [0, 0]},,, {data: [0.9, 0.9]}]); + test.deepEqual(q.addAll([[NaN, 0], [0, NaN]]).root(), [{data: [0, 0]},,, {data: [0.9, 0.9]}]); + test.deepEqual(q.extent(), [[0, 0], [1, 1]]); + test.end(); +}); + +tape("quadtree.addAll(data) correctly handles the empty array", function(test) { + var q = d3_quadtree.quadtree(); + test.deepEqual(q.addAll([]).root(), undefined); + test.equal(q.extent(), undefined); + test.deepEqual(q.addAll([[0, 0], [1, 1]]).root(), [{data: [0, 0]},,, {data: [1, 1]}]); + test.deepEqual(q.addAll([]).root(), [{data: [0, 0]},,, {data: [1, 1]}]); + test.deepEqual(q.extent(), [[0, 0], [2, 2]]); + test.end(); +}); + +tape("quadtree.addAll(data) computes the extent of the data before adding", function(test) { + var q = d3_quadtree.quadtree().addAll([[0.4, 0.4], [0, 0], [0.9, 0.9]]); + test.deepEqual(q.root(), [[{data: [0, 0]},,, {data: [0.4, 0.4]}],,, {data: [0.9, 0.9]}]); + test.end(); +}); diff --git a/test/benchmark b/test/benchmark new file mode 100755 index 0000000..dd4c8b5 --- /dev/null +++ b/test/benchmark @@ -0,0 +1,39 @@ +#!/usr/bin/env node + +var d3_array = require("d3-array"), + d3_quadtree = require("../"); + +var n = 1000000, + points1 = new Array(n), + points2 = new Array(n); + +for (var j = 0; j < n; ++j) { + points1[j] = [Math.random() * 99, Math.random() * 99]; +} + +for (var j = 0; j < n; ++j) { + points2[j] = [points1[j][0] + Math.random(), points1[j][1] + Math.random()]; +} + +var start = now(); +var root = d3_quadtree.quadtree().extent([[0, 0], [100, 100]]).addAll(points1); +var end = now(); +console.log("create", Math.round(end - start)); + +var start = now(); +root.visit(function(node, x0, y0, x1, y1) {}); +var end = now(); +console.log("iterate", Math.round(end - start)); + +var start = now(); +for (var j = 0, p; j < n; ++j) { + root.remove(points1[j]); + root.add(points2[j]); +} +var end = now(); +console.log("update", Math.round(end - start)); + +function now() { + var now = process.hrtime(); + return now[0] * 1e3 + now[1] / 1e6; +} diff --git a/test/copy-test.js b/test/copy-test.js new file mode 100644 index 0000000..7c8c027 --- /dev/null +++ b/test/copy-test.js @@ -0,0 +1,51 @@ +var tape = require("tape"), + d3_quadtree = require("../"); + +tape("quadtree.copy() returns a copy of this quadtree", function(test) { + var q0 = d3_quadtree.quadtree().addAll([[0, 0], [1, 0], [0, 1], [1, 1]]); + test.deepEqual(q0.copy(), q0); + test.end(); +}); + +tape("quadtree.copy() isolates changes to the extent", function(test) { + var q0 = d3_quadtree.quadtree().extent([[0, 0], [1, 1]]), + q1 = q0.copy(); + q0.add([2, 2]); + test.deepEqual(q1.extent(), [[0, 0], [2, 2]]); + q1.add([-1, -1]); + test.deepEqual(q0.extent(), [[0, 0], [4, 4]]); + test.end(); +}); + +tape("quadtree.copy() isolates changes to the root when a leaf", function(test) { + var q0 = d3_quadtree.quadtree().extent([[0, 0], [1, 1]]), + q1 = q0.copy(), + p0 = [2, 2]; + q0.add(p0); + test.equal(q1.root(), undefined); + q1 = q0.copy(); + test.deepEqual(q0.root(), {data: [2, 2]}); + test.deepEqual(q1.root(), {data: [2, 2]}); + test.equal(q0.remove(p0), q0); + test.equal(q0.root(), undefined); + test.deepEqual(q1.root(), {data: [2, 2]}); + test.end(); +}); + +tape("quadtree.copy() isolates changes to the root when not a leaf", function(test) { + var p0 = [1, 1], + p1 = [2, 2], + p2 = [3, 3], + q0 = d3_quadtree.quadtree().extent([[0, 0], [4, 4]]).addAll([p0, p1]), + q1 = q0.copy(); + q0.add(p2); + test.deepEqual(q0.extent(), [[0, 0], [8, 8]]); + test.deepEqual(q0.root(), [[{data: [1, 1]},,, [{data: [2, 2]},,, {data: [3, 3]}]],,, ]); + test.deepEqual(q1.extent(), [[0, 0], [8, 8]]); + test.deepEqual(q1.root(), [[{data: [1, 1]},,, {data: [2, 2]}],,, ]); + q1 = q0.copy(); + q0.remove(p2); + test.deepEqual(q1.extent(), [[0, 0], [8, 8]]); + test.deepEqual(q1.root(), [[{data: [1, 1]},,, [{data: [2, 2]},,, {data: [3, 3]}]],,, ]); + test.end(); +}); diff --git a/test/cover-test.js b/test/cover-test.js new file mode 100644 index 0000000..cd49d09 --- /dev/null +++ b/test/cover-test.js @@ -0,0 +1,79 @@ +var tape = require("tape"), + d3_quadtree = require("../"); + +tape("quadtree.cover(x, y) sets a trivial extent if the extent was undefined", function(test) { + test.deepEqual(d3_quadtree.quadtree().cover(1, 2).extent(), [[1, 2], [2, 3]]); + test.end(); +}); + +tape("quadtree.cover(x, y) sets a non-trivial squarified and centered extent if the extent was trivial", function(test) { + test.deepEqual(d3_quadtree.quadtree().cover(0, 0).cover(1, 2).extent(), [[0, 0], [4, 4]]); + test.end(); +}); + +tape("quadtree.cover(x, y) ignores invalid points", function(test) { + test.deepEqual(d3_quadtree.quadtree().cover(0, 0).cover(NaN, 2).extent(), [[0, 0], [1, 1]]); + test.end(); +}); + +tape("quadtree.cover(x, y) repeatedly doubles the existing extent if the extent was non-trivial", function(test) { + test.deepEqual(d3_quadtree.quadtree().cover(0, 0).cover(2, 2).cover(-1, -1).extent(), [[-4, -4], [4, 4]]); + test.deepEqual(d3_quadtree.quadtree().cover(0, 0).cover(2, 2).cover(1, -1).extent(), [[0, -4], [8, 4]]); + test.deepEqual(d3_quadtree.quadtree().cover(0, 0).cover(2, 2).cover(3, -1).extent(), [[0, -4], [8, 4]]); + test.deepEqual(d3_quadtree.quadtree().cover(0, 0).cover(2, 2).cover(3, 1).extent(), [[0, 0], [4, 4]]); + test.deepEqual(d3_quadtree.quadtree().cover(0, 0).cover(2, 2).cover(3, 3).extent(), [[0, 0], [4, 4]]); + test.deepEqual(d3_quadtree.quadtree().cover(0, 0).cover(2, 2).cover(1, 3).extent(), [[0, 0], [4, 4]]); + test.deepEqual(d3_quadtree.quadtree().cover(0, 0).cover(2, 2).cover(-1, 3).extent(), [[-4, 0], [4, 8]]); + test.deepEqual(d3_quadtree.quadtree().cover(0, 0).cover(2, 2).cover(-1, 1).extent(), [[-4, 0], [4, 8]]); + test.deepEqual(d3_quadtree.quadtree().cover(0, 0).cover(2, 2).cover(-3, -3).extent(), [[-4, -4], [4, 4]]); + test.deepEqual(d3_quadtree.quadtree().cover(0, 0).cover(2, 2).cover(3, -3).extent(), [[0, -4], [8, 4]]); + test.deepEqual(d3_quadtree.quadtree().cover(0, 0).cover(2, 2).cover(5, -3).extent(), [[0, -4], [8, 4]]); + test.deepEqual(d3_quadtree.quadtree().cover(0, 0).cover(2, 2).cover(5, 3).extent(), [[0, 0], [8, 8]]); + test.deepEqual(d3_quadtree.quadtree().cover(0, 0).cover(2, 2).cover(5, 5).extent(), [[0, 0], [8, 8]]); + test.deepEqual(d3_quadtree.quadtree().cover(0, 0).cover(2, 2).cover(3, 5).extent(), [[0, 0], [8, 8]]); + test.deepEqual(d3_quadtree.quadtree().cover(0, 0).cover(2, 2).cover(-3, 5).extent(), [[-4, 0], [4, 8]]); + test.deepEqual(d3_quadtree.quadtree().cover(0, 0).cover(2, 2).cover(-3, 3).extent(), [[-4, 0], [4, 8]]); + test.end(); +}); + +tape("quadtree.cover(x, y) repeatedly wraps the root node if it has children", function(test) { + var q = d3_quadtree.quadtree().add([0, 0]).add([2, 2]); + test.deepEqual(q.root(), [{data: [0, 0]},,, {data: [2, 2]}]); + test.deepEqual(q.copy().cover(3, 3).root(), [{data: [0, 0]},,, {data: [2, 2]}]); + test.deepEqual(q.copy().cover(-1, 3).root(), [,[{data: [0, 0]},,, {data: [2, 2]}],, ]); + test.deepEqual(q.copy().cover(3, -1).root(), [,, [{data: [0, 0]},,, {data: [2, 2]}], ]); + test.deepEqual(q.copy().cover(-1, -1).root(), [,,, [{data: [0, 0]},,, {data: [2, 2]}]]); + test.deepEqual(q.copy().cover(5, 5).root(), [[{data: [0, 0]},,, {data: [2, 2]}],,, ]); + test.deepEqual(q.copy().cover(-3, 5).root(), [,[{data: [0, 0]},,, {data: [2, 2]}],, ]); + test.deepEqual(q.copy().cover(5, -3).root(), [,, [{data: [0, 0]},,, {data: [2, 2]}], ]); + test.deepEqual(q.copy().cover(-3, -3).root(), [,,, [{data: [0, 0]},,, {data: [2, 2]}]]); + test.end(); +}); + +tape("quadtree.cover(x, y) does not wrap the root node if it is a leaf", function(test) { + var q = d3_quadtree.quadtree().cover(0, 0).add([2, 2]); + test.deepEqual(q.root(), {data: [2, 2]}); + test.deepEqual(q.copy().cover(3, 3).root(), {data: [2, 2]}); + test.deepEqual(q.copy().cover(-1, 3).root(), {data: [2, 2]}); + test.deepEqual(q.copy().cover(3, -1).root(), {data: [2, 2]}); + test.deepEqual(q.copy().cover(-1, -1).root(), {data: [2, 2]}); + test.deepEqual(q.copy().cover(5, 5).root(), {data: [2, 2]}); + test.deepEqual(q.copy().cover(-3, 5).root(), {data: [2, 2]}); + test.deepEqual(q.copy().cover(5, -3).root(), {data: [2, 2]}); + test.deepEqual(q.copy().cover(-3, -3).root(), {data: [2, 2]}); + test.end(); +}); + +tape("quadtree.cover(x, y) does not wrap the root node if it is undefined", function(test) { + var q = d3_quadtree.quadtree().cover(0, 0).cover(2, 2); + test.equal(q.root(), undefined); + test.equal(q.copy().cover(3, 3).root(), undefined); + test.equal(q.copy().cover(-1, 3).root(), undefined); + test.equal(q.copy().cover(3, -1).root(), undefined); + test.equal(q.copy().cover(-1, -1).root(), undefined); + test.equal(q.copy().cover(5, 5).root(), undefined); + test.equal(q.copy().cover(-3, 5).root(), undefined); + test.equal(q.copy().cover(5, -3).root(), undefined); + test.equal(q.copy().cover(-3, -3).root(), undefined); + test.end(); +}); diff --git a/test/data-test.js b/test/data-test.js new file mode 100644 index 0000000..0f54fa5 --- /dev/null +++ b/test/data-test.js @@ -0,0 +1,17 @@ +var tape = require("tape"), + d3_quadtree = require("../"); + +tape("quadtree.data() returns an array of data in the quadtree", function(test) { + var q = d3_quadtree.quadtree(); + test.deepEqual(q.data(), []); + q.add([0, 0]).add([1, 2]); + test.deepEqual(q.data(), [[0, 0], [1, 2]]); + test.end(); +}); + +tape("quadtree.data() correctly handles coincident nodes", function(test) { + var q = d3_quadtree.quadtree(); + q.add([0, 0]).add([0, 0]); + test.deepEqual(q.data(), [[0, 0], [0, 0]]); + test.end(); +}); diff --git a/test/extent-test.js b/test/extent-test.js new file mode 100644 index 0000000..62d4273 --- /dev/null +++ b/test/extent-test.js @@ -0,0 +1,54 @@ +var tape = require("tape"), + d3_quadtree = require("../"); + +tape("quadtree.extent(extent) extends the extent", function(test) { + test.deepEqual(d3_quadtree.quadtree().extent([[0, 1], [2, 6]]).extent(), [[0, 1], [8, 9]]); + test.end(); +}); + +tape("quadtree.extent() can be inferred by quadtree.cover", function(test) { + var q = d3_quadtree.quadtree(); + test.deepEqual(q.cover(0, 0).extent(), [[0, 0], [1, 1]]); + test.deepEqual(q.cover(2, 4).extent(), [[0, 0], [8, 8]]); + test.end(); +}); + +tape("quadtree.extent() can be inferred by quadtree.add", function(test) { + var q = d3_quadtree.quadtree(); + q.add([0, 0]); + test.deepEqual(q.extent(), [[0, 0], [1, 1]]); + q.add([2, 4]); + test.deepEqual(q.extent(), [[0, 0], [8, 8]]); + test.end(); +}); + +tape("quadtree.extent(extent) squarifies and centers the specified extent", function(test) { + test.deepEqual(d3_quadtree.quadtree().extent([[0, 1], [2, 6]]).extent(), [[0, 1], [8, 9]]); + test.end(); +}); + +tape("quadtree.extent(extent) ignores invalid extents", function(test) { + test.equal(d3_quadtree.quadtree().extent([[1, NaN], [NaN, 0]]).extent(), undefined); + test.equal(d3_quadtree.quadtree().extent([[NaN, 1], [0, NaN]]).extent(), undefined); + test.equal(d3_quadtree.quadtree().extent([[NaN, NaN], [NaN, NaN]]).extent(), undefined); + test.end(); +}); + +tape("quadtree.extent(extent) flips inverted extents", function(test) { + test.deepEqual(d3_quadtree.quadtree().extent([[1, 1], [0, 0]]).extent(), [[0, 0], [2, 2]]); + test.end(); +}); + +tape("quadtree.extent(extent) tolerates partially-valid extents", function(test) { + test.deepEqual(d3_quadtree.quadtree().extent([[NaN, 0], [1, 1]]).extent(), [[1, 1], [2, 2]]); + test.deepEqual(d3_quadtree.quadtree().extent([[0, NaN], [1, 1]]).extent(), [[1, 1], [2, 2]]); + test.deepEqual(d3_quadtree.quadtree().extent([[0, 0], [NaN, 1]]).extent(), [[0, 0], [1, 1]]); + test.deepEqual(d3_quadtree.quadtree().extent([[0, 0], [1, NaN]]).extent(), [[0, 0], [1, 1]]); + test.end(); +}); + +tape("quadtree.extent(extent) allows trivial extents", function(test) { + test.deepEqual(d3_quadtree.quadtree().extent([[0, 0], [0, 0]]).extent(), [[0, 0], [1, 1]]); + test.deepEqual(d3_quadtree.quadtree().extent([[1, 1], [1, 1]]).extent(), [[1, 1], [2, 2]]); + test.end(); +}); diff --git a/test/find-test.js b/test/find-test.js new file mode 100644 index 0000000..82fc217 --- /dev/null +++ b/test/find-test.js @@ -0,0 +1,34 @@ +var tape = require("tape"), + d3_array = require("d3-array"), + d3_quadtree = require("../"); + +tape("quadtree.find(x, y) returns the closest point to the given [x, y]", function(test) { + var dx = 17, + dy = 17, + q = d3_quadtree.quadtree(); + d3_array.range(dx * dy).forEach(function(i) { q.add([i % dx, i / dx | 0]); }); + test.deepEqual(q.find( 0.1, 0.1), [ 0, 0]); + test.deepEqual(q.find( 7.1, 7.1), [ 7, 7]); + test.deepEqual(q.find( 0.1, 15.9), [ 0, 16]); + test.deepEqual(q.find(15.9, 15.9), [16, 16]); + test.end(); +}); + +tape("quadtree.find(x, y, radius) returns the closest point within the search radius to the given [x, y]", function(test) { + var q = d3_quadtree.quadtree([[0, 0], [100, 0], [0, 100], [100, 100]]); + test.deepEqual(q.find(20, 20, Infinity), [0, 0]); + test.deepEqual(q.find(20, 20, 20 * Math.SQRT2 + 1e-6), [0, 0]); + test.equal(q.find(20, 20, 20 * Math.SQRT2 - 1e-6), undefined); + test.deepEqual(q.find(0, 20, 20 + 1e-6), [0, 0]); + test.equal(q.find(0, 20, 20 - 1e-6), undefined); + test.deepEqual(q.find(20, 0, 20 + 1e-6), [0, 0]); + test.equal(q.find(20, 0, 20 - 1e-6), undefined); + test.end(); +}); + +tape("quadtree.find(x, y, null) treats the given radius as Infinity", function(test) { + var q = d3_quadtree.quadtree([[0, 0], [100, 0], [0, 100], [100, 100]]); + test.deepEqual(q.find(20, 20, null), [0, 0]); + test.deepEqual(q.find(20, 20, undefined), [0, 0]); + test.end(); +}); diff --git a/test/quadtree-test.js b/test/quadtree-test.js new file mode 100644 index 0000000..3ba57cc --- /dev/null +++ b/test/quadtree-test.js @@ -0,0 +1,27 @@ +var tape = require("tape"), + d3_quadtree = require("../"); + +tape("d3.quadtree() creates an empty quadtree", function(test) { + var q = d3_quadtree.quadtree(); + test.ok(q instanceof d3_quadtree.quadtree); + test.equal(q.visit(function() { throw new Error; }), q); + test.equal(q.size(), 0); + test.equal(q.extent(), undefined); + test.equal(q.root(), undefined); + test.deepEqual(q.data(), []); + test.end(); +}); + +tape("d3.quadtree(nodes) is equivalent to d3.quadtree().addAll(nodes)", function(test) { + var q = d3_quadtree.quadtree([[0, 0], [1, 1]]); + test.ok(q instanceof d3_quadtree.quadtree); + test.deepEqual(q.root(), [{data: [0, 0]},,, {data: [1, 1]}]); + test.end(); +}); + +tape("d3.quadtree(nodes, x, y) is equivalent to d3.quadtree().x(x).y(y).addAll(nodes)", function(test) { + var q = d3_quadtree.quadtree([{x: 0, y: 0}, {x: 1, y: 1}], function(d) { return d.x; }, function(d) { return d.y; }); + test.ok(q instanceof d3_quadtree.quadtree); + test.deepEqual(q.root(), [{data: {x: 0, y: 0}},,, {data: {x: 1, y: 1}}]); + test.end(); +}); diff --git a/test/remove-test.js b/test/remove-test.js new file mode 100644 index 0000000..e983127 --- /dev/null +++ b/test/remove-test.js @@ -0,0 +1,132 @@ +var tape = require("tape"), + d3_quadtree = require("../"); + +tape("quadtree.remove(datum) removes a point and returns the quadtree", function(test) { + var p0 = [1, 1], + q = d3_quadtree.quadtree().add(p0); + test.deepEqual(q.root(), {data: p0}); + test.equal(q.remove(p0), q); + test.deepEqual(q.root(), undefined); + test.end(); +}); + +tape("quadtree.remove(datum) removes the only point in the quadtree", function(test) { + var p0 = [1, 1], + q = d3_quadtree.quadtree().add(p0); + test.equal(q.remove(p0), q); + test.deepEqual(q.extent(), [[1, 1], [2, 2]]); + test.deepEqual(q.root(), undefined); + test.deepEqual(p0, [1, 1]); + test.end(); +}); + +tape("quadtree.remove(datum) removes a first coincident point at the root in the quadtree", function(test) { + var p0 = [1, 1], + p1 = [1, 1], + q = d3_quadtree.quadtree().addAll([p0, p1]); + test.equal(q.remove(p0), q); + test.deepEqual(q.extent(), [[1, 1], [2, 2]]); + test.equal(q.root().data, p1); + test.deepEqual(p0, [1, 1]); + test.deepEqual(p1, [1, 1]); + test.end(); +}); + +tape("quadtree.remove(datum) removes another coincident point at the root in the quadtree", function(test) { + var p0 = [1, 1], + p1 = [1, 1], + q = d3_quadtree.quadtree().addAll([p0, p1]); + test.equal(q.remove(p1), q); + test.deepEqual(q.extent(), [[1, 1], [2, 2]]); + test.equal(q.root().data, p0); + test.deepEqual(p0, [1, 1]); + test.deepEqual(p1, [1, 1]); + test.end(); +}); + +tape("quadtree.remove(datum) removes a non-root point in the quadtree", function(test) { + var p0 = [0, 0], + p1 = [1, 1], + q = d3_quadtree.quadtree().addAll([p0, p1]); + test.equal(q.remove(p0), q); + test.deepEqual(q.extent(), [[0, 0], [2, 2]]); + test.equal(q.root().data, p1); + test.deepEqual(p0, [0, 0]); + test.deepEqual(p1, [1, 1]); + test.end(); +}); + +tape("quadtree.remove(datum) removes another non-root point in the quadtree", function(test) { + var p0 = [0, 0], + p1 = [1, 1], + q = d3_quadtree.quadtree().addAll([p0, p1]); + test.equal(q.remove(p1), q); + test.deepEqual(q.extent(), [[0, 0], [2, 2]]); + test.equal(q.root().data, p0); + test.deepEqual(p0, [0, 0]); + test.deepEqual(p1, [1, 1]); + test.end(); +}); + +tape("quadtree.remove(datum) ignores a point not in the quadtree", function(test) { + var p0 = [0, 0], + p1 = [1, 1], + q0 = d3_quadtree.quadtree().add(p0), + q1 = d3_quadtree.quadtree().add(p1); + test.equal(q0.remove(p1), q0); + test.deepEqual(q0.extent(), [[0, 0], [1, 1]]); + test.equal(q0.root().data, p0); + test.equal(q1.root().data, p1); + test.end(); +}); + +tape("quadtree.remove(datum) ignores a coincident point not in the quadtree", function(test) { + var p0 = [0, 0], + p1 = [0, 0], + q0 = d3_quadtree.quadtree().add(p0), + q1 = d3_quadtree.quadtree().add(p1); + test.equal(q0.remove(p1), q0); + test.deepEqual(q0.extent(), [[0, 0], [1, 1]]); + test.equal(q0.root().data, p0); + test.equal(q1.root().data, p1); + test.end(); +}); + +tape("quadtree.remove(datum) removes another point in the quadtree", function(test) { + var q = d3_quadtree.quadtree() + .extent([[0, 0], [959, 959]]) + .addAll([[630, 438], [715, 464], [523, 519], [646, 318], [434, 620], [570, 489], [520, 345], [459, 443], [346, 405], [529, 444]]); + test.equal(q.remove(q.find(546, 440)), q); + test.deepEqual(q.extent(), [[0, 0], [1024, 1024]]); + test.deepEqual(q.root(), [ + [ + , + , + , + [ + , + , + {data: [346, 405]}, + {data: [459, 443]} + ] + ], + [ + , + , + [ + {data: [520, 345]}, + {data: [646, 318]}, + [ + , + {data: [630, 438]}, + {data: [570, 489]}, + + ], + {data: [715, 464]} + ], + ], + {data: [434, 620]}, + {data: [523, 519]} + ]); + test.end(); +}); diff --git a/test/size-test.js b/test/size-test.js new file mode 100644 index 0000000..ea82c9a --- /dev/null +++ b/test/size-test.js @@ -0,0 +1,17 @@ +var tape = require("tape"), + d3_quadtree = require("../"); + +tape("quadtree.size() returns the number of points in the quadtree", function(test) { + var q = d3_quadtree.quadtree(); + test.equal(q.size(), 0); + q.add([0, 0]).add([1, 2]); + test.equal(q.size(), 2); + test.end(); +}); + +tape("quadtree.size() correctly counts coincident nodes", function(test) { + var q = d3_quadtree.quadtree(); + q.add([0, 0]).add([0, 0]); + test.equal(q.size(), 2); + test.end(); +}); diff --git a/test/visit-test.js b/test/visit-test.js new file mode 100644 index 0000000..b1b71ef --- /dev/null +++ b/test/visit-test.js @@ -0,0 +1,60 @@ +var tape = require("tape"), + d3_quadtree = require("../"); + +tape("quadtree.visit(callback) visits each node in a quadtree", function(test) { + var results = [], q = d3_quadtree.quadtree() + .addAll([[0, 0], [1, 0], [0, 1], [1, 1]]); + test.equal(q.visit(function(node, x0, y0, x1, y1) { results.push([x0, y0, x1, y1]); }), q); + test.deepEqual(results, [ + [0, 0, 2, 2], + [0, 0, 1, 1], + [1, 0, 2, 1], + [0, 1, 1, 2], + [1, 1, 2, 2] + ]); + test.end(); +}); + +tape("quadtree.visit(callback) applies pre-order traversal", function(test) { + var results = [], q = d3_quadtree.quadtree() + .extent([[0, 0], [960, 960]]) + .addAll([[100, 100], [200, 200], [300, 300]]); + test.equal(q.visit(function(node, x0, y0, x1, y1) { results.push([x0, y0, x1, y1]); }), q); + test.deepEqual(results, [ + [ 0, 0, 1024, 1024], + [ 0, 0, 512, 512], + [ 0, 0, 256, 256], + [ 0, 0, 128, 128], + [128, 128, 256, 256], + [256, 256, 512, 512] + ]); + test.end(); +}); + +tape("quadtree.visit(callback) does not recurse if the callback returns truthy", function(test) { + var results = [], q = d3_quadtree.quadtree() + .extent([[0, 0], [960, 960]]) + .addAll([[100, 100], [700, 700], [800, 800]]); + test.equal(q.visit(function(node, x0, y0, x1, y1) { results.push([x0, y0, x1, y1]); return x0 > 0; }), q); + test.deepEqual(results, [ + [ 0, 0, 1024, 1024], + [ 0, 0, 512, 512], + [512, 512, 1024, 1024] + ]); + test.end(); +}); + +tape("quadtree.visit(callback) on an empty quadtree with no bounds does nothing", function(test) { + var results = [], q = d3_quadtree.quadtree(); + test.equal(q.visit(function(node, x0, y0, x1, y1) { results.push([x0, y0, x1, y1]); }), q); + test.equal(results.length, 0); + test.end(); +}); + +tape("quadtree.visit(callback) on an empty quadtree with bounds does nothing", function(test) { + var results = [], q = d3_quadtree.quadtree() + .extent([[0, 0], [960, 960]]); + test.equal(q.visit(function(node, x0, y0, x1, y1) { results.push([x0, y0, x1, y1]); }), q); + test.deepEqual(results.length, 0); + test.end(); +}); diff --git a/test/x-test.js b/test/x-test.js new file mode 100644 index 0000000..8714961 --- /dev/null +++ b/test/x-test.js @@ -0,0 +1,31 @@ +var tape = require("tape"), + d3_quadtree = require("../"); + +tape("quadtree.x(x) sets the x-accessor used by quadtree.add", function(test) { + var q = d3_quadtree.quadtree().x(x).add({x: 1, 1: 2}); + test.deepEqual(q.extent(), [[1, 2], [2, 3]]); + test.deepEqual(q.root(), {data: {x: 1, 1: 2}}); + test.end(); +}); + +tape("quadtree.x(x) sets the x-accessor used by quadtree.addAll", function(test) { + var q = d3_quadtree.quadtree().x(x).addAll([{x: 1, 1: 2}]); + test.deepEqual(q.extent(), [[1, 2], [2, 3]]); + test.deepEqual(q.root(), {data: {x: 1, 1: 2}}); + test.end(); +}); + +tape("quadtree.x(x) sets the x-accessor used by quadtree.remove", function(test) { + var p0 = {x: 0, 1: 1}, + p1 = {x: 1, 1: 2}, + q = d3_quadtree.quadtree().x(x); + test.deepEqual(q.add(p0).root(), {data: {x: 0, 1: 1}}); + test.deepEqual(q.add(p1).root(), [{data: {x: 0, 1: 1}},,, {data: {x: 1, 1: 2}}]); + test.deepEqual(q.remove(p1).root(), {data: {x: 0, 1: 1}}); + test.equal(q.remove(p0).root(), undefined); + test.end(); +}); + +function x(d) { + return d.x; +} diff --git a/test/y-test.js b/test/y-test.js new file mode 100644 index 0000000..9ea319a --- /dev/null +++ b/test/y-test.js @@ -0,0 +1,31 @@ +var tape = require("tape"), + d3_quadtree = require("../"); + +tape("quadtree.y(y) sets the y-accessor used by quadtree.add", function(test) { + var q = d3_quadtree.quadtree().y(y).add({0: 1, y: 2}); + test.deepEqual(q.extent(), [[1, 2], [2, 3]]); + test.deepEqual(q.root(), {data: {0: 1, y: 2}}); + test.end(); +}); + +tape("quadtree.y(y) sets the y-accessor used by quadtree.addAll", function(test) { + var q = d3_quadtree.quadtree().y(y).addAll([{0: 1, y: 2}]); + test.deepEqual(q.extent(), [[1, 2], [2, 3]]); + test.deepEqual(q.root(), {data: {0: 1, y: 2}}); + test.end(); +}); + +tape("quadtree.y(y) sets the y-accessor used by quadtree.remove", function(test) { + var p0 = {0: 0, y: 1}, + p1 = {0: 1, y: 2}, + q = d3_quadtree.quadtree().y(y); + test.deepEqual(q.add(p0).root(), {data: {0: 0, y: 1}}); + test.deepEqual(q.add(p1).root(), [{data: {0: 0, y: 1}},,, {data: {0: 1, y: 2}}]); + test.deepEqual(q.remove(p1).root(), {data: {0: 0, y: 1}}); + test.equal(q.remove(p0).root(), undefined); + test.end(); +}); + +function y(d) { + return d.y; +} diff --git a/yarn.lock b/yarn.lock new file mode 100644 index 0000000..520dcd7 --- /dev/null +++ b/yarn.lock @@ -0,0 +1,1095 @@ +# THIS IS AN AUTOGENERATED FILE. DO NOT EDIT THIS FILE DIRECTLY. +# yarn lockfile v1 + + +"@babel/code-frame@^7.0.0": + version "7.5.5" + resolved "https://registry.yarnpkg.com/@babel/code-frame/-/code-frame-7.5.5.tgz#bc0782f6d69f7b7d49531219699b988f669a8f9d" + integrity sha512-27d4lZoomVyo51VegxI20xZPuSHusqbQag/ztrBC7wegWoQ1nLREPVSKSW8byhTlzTKyNE4ifaTA6lCp7JjpFw== + dependencies: + "@babel/highlight" "^7.0.0" + +"@babel/highlight@^7.0.0": + version "7.5.0" + resolved "https://registry.yarnpkg.com/@babel/highlight/-/highlight-7.5.0.tgz#56d11312bd9248fa619591d02472be6e8cb32540" + integrity sha512-7dV4eu9gBxoM0dAnj/BCFDW9LFU0zvTrkq0ugM7pnHEgguOEeOz1so2ZghEdzviYzQEED0r4EAgpsBChKy1TRQ== + dependencies: + chalk "^2.0.0" + esutils "^2.0.2" + js-tokens "^4.0.0" + +"@types/estree@0.0.39": + version "0.0.39" + resolved "https://registry.yarnpkg.com/@types/estree/-/estree-0.0.39.tgz#e177e699ee1b8c22d23174caaa7422644389509f" + integrity sha512-EYNwp3bU+98cpU4lAWYYL7Zz+2gryWH1qbdDTidVd6hkiR6weksdbMadyXKXNPEkQFhXM+hVO9ZygomHXp+AIw== + +"@types/node@^12.6.2": + version "12.6.8" + resolved "https://registry.yarnpkg.com/@types/node/-/node-12.6.8.tgz#e469b4bf9d1c9832aee4907ba8a051494357c12c" + integrity sha512-aX+gFgA5GHcDi89KG5keey2zf0WfZk/HAQotEamsK2kbey+8yGKcson0hbK8E+v0NArlCJQCqMP161YhV6ZXLg== + +acorn-jsx@^5.0.0: + version "5.0.1" + resolved "https://registry.yarnpkg.com/acorn-jsx/-/acorn-jsx-5.0.1.tgz#32a064fd925429216a09b141102bfdd185fae40e" + integrity sha512-HJ7CfNHrfJLlNTzIEUTj43LNWGkqpRLxm3YjAlcD0ACydk9XynzYsCBHxut+iqt+1aBXkx9UP/w/ZqMr13XIzg== + +acorn@^6.0.7, acorn@^6.2.0: + version "6.2.1" + resolved "https://registry.yarnpkg.com/acorn/-/acorn-6.2.1.tgz#3ed8422d6dec09e6121cc7a843ca86a330a86b51" + integrity sha512-JD0xT5FCRDNyjDda3Lrg/IxFscp9q4tiYtxE1/nOzlKCk7hIRuYjhq1kCNkbPjMRMZuFq20HNQn1I9k8Oj0E+Q== + +ajv@^6.10.0, ajv@^6.10.2: + version "6.10.2" + resolved "https://registry.yarnpkg.com/ajv/-/ajv-6.10.2.tgz#d3cea04d6b017b2894ad69040fec8b623eb4bd52" + integrity sha512-TXtUUEYHuaTEbLZWIKUr5pmBuhDLy+8KYtPYdcV8qC+pOZL+NKqYwvWSRrVXHn+ZmRRAu8vJTAznH7Oag6RVRw== + dependencies: + fast-deep-equal "^2.0.1" + fast-json-stable-stringify "^2.0.0" + json-schema-traverse "^0.4.1" + uri-js "^4.2.2" + +ansi-escapes@^3.2.0: + version "3.2.0" + resolved "https://registry.yarnpkg.com/ansi-escapes/-/ansi-escapes-3.2.0.tgz#8780b98ff9dbf5638152d1f1fe5c1d7b4442976b" + integrity sha512-cBhpre4ma+U0T1oM5fXg7Dy1Jw7zzwv7lt/GoCpr+hDQJoYnKVPLL4dCvSEFMmQurOQvSrwT7SL/DAlhBI97RQ== + +ansi-regex@^3.0.0: + version "3.0.0" + resolved "https://registry.yarnpkg.com/ansi-regex/-/ansi-regex-3.0.0.tgz#ed0317c322064f79466c02966bddb605ab37d998" + integrity sha1-7QMXwyIGT3lGbAKWa922Bas32Zg= + +ansi-regex@^4.1.0: + version "4.1.0" + resolved "https://registry.yarnpkg.com/ansi-regex/-/ansi-regex-4.1.0.tgz#8b9f8f08cf1acb843756a839ca8c7e3168c51997" + integrity sha512-1apePfXM1UOSqw0o9IiFAovVz9M5S1Dg+4TrDwfMewQ6p/rmMueb7tWZjQ1rx4Loy1ArBggoqGpfqqdI4rondg== + +ansi-styles@^3.2.0, ansi-styles@^3.2.1: + version "3.2.1" + resolved "https://registry.yarnpkg.com/ansi-styles/-/ansi-styles-3.2.1.tgz#41fbb20243e50b12be0f04b8dedbf07520ce841d" + integrity sha512-VT0ZI6kZRdTh8YyJw3SMbYm/u+NqfsAxEpWO0Pf9sq8/e94WxxOpPKx9FR1FlyCtOVDNOQ+8ntlqFxiRc+r5qA== + dependencies: + color-convert "^1.9.0" + +argparse@^1.0.7: + version "1.0.10" + resolved "https://registry.yarnpkg.com/argparse/-/argparse-1.0.10.tgz#bcd6791ea5ae09725e17e5ad988134cd40b3d911" + integrity sha512-o5Roy6tNG4SL/FOkCAN6RzjiakZS25RLYFrcMttJqbdd8BWrnA+fGz57iN5Pb06pvBGvl5gQ0B48dJlslXvoTg== + dependencies: + sprintf-js "~1.0.2" + +astral-regex@^1.0.0: + version "1.0.0" + resolved "https://registry.yarnpkg.com/astral-regex/-/astral-regex-1.0.0.tgz#6c8c3fb827dd43ee3918f27b82782ab7658a6fd9" + integrity sha512-+Ryf6g3BKoRc7jfp7ad8tM4TtMiaWvbF/1/sQcZPkkS7ag3D5nMBCe2UfOTONtAkaG0tO0ij3C5Lwmf1EiyjHg== + +balanced-match@^1.0.0: + version "1.0.0" + resolved "https://registry.yarnpkg.com/balanced-match/-/balanced-match-1.0.0.tgz#89b4d199ab2bee49de164ea02b89ce462d71b767" + integrity sha1-ibTRmasr7kneFk6gK4nORi1xt2c= + +brace-expansion@^1.1.7: + version "1.1.11" + resolved "https://registry.yarnpkg.com/brace-expansion/-/brace-expansion-1.1.11.tgz#3c7fcbf529d87226f3d2f52b966ff5271eb441dd" + integrity sha512-iCuPHDFgrHX7H2vEI/5xpz07zSHB00TpugqhmYtVmMO6518mCuRMoOYFldEBl0g187ufozdaHgWKcYFb61qGiA== + dependencies: + balanced-match "^1.0.0" + concat-map "0.0.1" + +buffer-from@^1.0.0: + version "1.1.1" + resolved "https://registry.yarnpkg.com/buffer-from/-/buffer-from-1.1.1.tgz#32713bc028f75c02fdb710d7c7bcec1f2c6070ef" + integrity sha512-MQcXEUbCKtEo7bhqEs6560Hyd4XaovZlO/k9V3hjVUF/zwW7KBVdSK4gIt/bzwS9MbR5qob+F5jusZsb0YQK2A== + +callsites@^3.0.0: + version "3.1.0" + resolved "https://registry.yarnpkg.com/callsites/-/callsites-3.1.0.tgz#b3630abd8943432f54b3f0519238e33cd7df2f73" + integrity sha512-P8BjAsXvZS+VIDUI11hHCQEv74YT67YUi5JJFNWIqL235sBmjX4+qx9Muvls5ivyNENctx46xQLQ3aTuE7ssaQ== + +chalk@^2.0.0, chalk@^2.1.0, chalk@^2.4.2: + version "2.4.2" + resolved "https://registry.yarnpkg.com/chalk/-/chalk-2.4.2.tgz#cd42541677a54333cf541a49108c1432b44c9424" + integrity sha512-Mti+f9lpJNcwF4tWV8/OrTTtF1gZi+f8FqlyAdouralcFWFQWF2+NgCHShjkCb+IFBLq9buZwE1xckQU4peSuQ== + dependencies: + ansi-styles "^3.2.1" + escape-string-regexp "^1.0.5" + supports-color "^5.3.0" + +chardet@^0.7.0: + version "0.7.0" + resolved "https://registry.yarnpkg.com/chardet/-/chardet-0.7.0.tgz#90094849f0937f2eedc2425d0d28a9e5f0cbad9e" + integrity sha512-mT8iDcrh03qDGRRmoA2hmBJnxpllMR+0/0qlzjqZES6NdiWDcZkCNAk4rPFZ9Q85r27unkiNNg8ZOiwZXBHwcA== + +cli-cursor@^2.1.0: + version "2.1.0" + resolved "https://registry.yarnpkg.com/cli-cursor/-/cli-cursor-2.1.0.tgz#b35dac376479facc3e94747d41d0d0f5238ffcb5" + integrity sha1-s12sN2R5+sw+lHR9QdDQ9SOP/LU= + dependencies: + restore-cursor "^2.0.0" + +cli-width@^2.0.0: + version "2.2.0" + resolved "https://registry.yarnpkg.com/cli-width/-/cli-width-2.2.0.tgz#ff19ede8a9a5e579324147b0c11f0fbcbabed639" + integrity sha1-/xnt6Kml5XkyQUewwR8PvLq+1jk= + +color-convert@^1.9.0: + version "1.9.3" + resolved "https://registry.yarnpkg.com/color-convert/-/color-convert-1.9.3.tgz#bb71850690e1f136567de629d2d5471deda4c1e8" + integrity sha512-QfAUtd+vFdAtFQcC8CCyYt1fYWxSqAiK2cSD6zDB8N3cpsEBAvRxp9zOGg6G/SHHJYAT88/az/IuDGALsNVbGg== + dependencies: + color-name "1.1.3" + +color-name@1.1.3: + version "1.1.3" + resolved "https://registry.yarnpkg.com/color-name/-/color-name-1.1.3.tgz#a7d0558bd89c42f795dd42328f740831ca53bc25" + integrity sha1-p9BVi9icQveV3UIyj3QIMcpTvCU= + +commander@^2.20.0: + version "2.20.0" + resolved "https://registry.yarnpkg.com/commander/-/commander-2.20.0.tgz#d58bb2b5c1ee8f87b0d340027e9e94e222c5a422" + integrity sha512-7j2y+40w61zy6YC2iRNpUe/NwhNyoXrYpHMrSunaMG64nRnaf96zO/KMQR4OyN/UnE5KLyEBnKHd4aG3rskjpQ== + +concat-map@0.0.1: + version "0.0.1" + resolved "https://registry.yarnpkg.com/concat-map/-/concat-map-0.0.1.tgz#d8a96bd77fd68df7793a73036a3ba0d5405d477b" + integrity sha1-2Klr13/Wjfd5OnMDajug1UBdR3s= + +core-util-is@~1.0.0: + version "1.0.2" + resolved "https://registry.yarnpkg.com/core-util-is/-/core-util-is-1.0.2.tgz#b5fd54220aa2bc5ab57aab7140c940754503c1a7" + integrity sha1-tf1UIgqivFq1eqtxQMlAdUUDwac= + +cross-spawn@^6.0.5: + version "6.0.5" + resolved "https://registry.yarnpkg.com/cross-spawn/-/cross-spawn-6.0.5.tgz#4a5ec7c64dfae22c3a14124dbacdee846d80cbc4" + integrity sha512-eTVLrBSt7fjbDygz805pMnstIs2VTBNkRm0qxZd+M7A5XDdxVRWO5MxGBXZhjY4cqLYLdtrGqRf8mBPmzwSpWQ== + dependencies: + nice-try "^1.0.4" + path-key "^2.0.1" + semver "^5.5.0" + shebang-command "^1.2.0" + which "^1.2.9" + +"d3-array@1 - 2": + version "2.2.0" + resolved "https://registry.yarnpkg.com/d3-array/-/d3-array-2.2.0.tgz#a9e966b8f8d78f0888d98db1fb840fc8da8ac5c7" + integrity sha512-eE0QmSh6xToqM3sxHiJYg/QFdNn52ZEgmFE8A8abU8GsHvsIOolqH8B70/8+VGAKm5MlwaExhqR3DLIjOJMLPA== + +debug@^4.0.1: + version "4.1.1" + resolved "https://registry.yarnpkg.com/debug/-/debug-4.1.1.tgz#3b72260255109c6b589cee050f1d516139664791" + integrity sha512-pYAIzeRo8J6KPEaJ0VWOh5Pzkbw/RetuzehGM7QRRX5he4fPHx2rdKMB256ehJCkX+XRQm16eZLqLNS8RSZXZw== + dependencies: + ms "^2.1.1" + +deep-equal@~1.0.1: + version "1.0.1" + resolved "https://registry.yarnpkg.com/deep-equal/-/deep-equal-1.0.1.tgz#f5d260292b660e084eff4cdbc9f08ad3247448b5" + integrity sha1-9dJgKStmDghO/0zbyfCK0yR0SLU= + +deep-is@~0.1.3: + version "0.1.3" + resolved "https://registry.yarnpkg.com/deep-is/-/deep-is-0.1.3.tgz#b369d6fb5dbc13eecf524f91b070feedc357cf34" + integrity sha1-s2nW+128E+7PUk+RsHD+7cNXzzQ= + +define-properties@^1.1.2: + version "1.1.3" + resolved "https://registry.yarnpkg.com/define-properties/-/define-properties-1.1.3.tgz#cf88da6cbee26fe6db7094f61d870cbd84cee9f1" + integrity sha512-3MqfYKj2lLzdMSf8ZIZE/V+Zuy+BgD6f164e8K2w7dgnpKArBDerGYpM46IYYcjnkdPNMjPk9A6VFB8+3SKlXQ== + dependencies: + object-keys "^1.0.12" + +defined@~1.0.0: + version "1.0.0" + resolved "https://registry.yarnpkg.com/defined/-/defined-1.0.0.tgz#c98d9bcef75674188e110969151199e39b1fa693" + integrity sha1-yY2bzvdWdBiOEQlpFRGZ45sfppM= + +doctrine@^3.0.0: + version "3.0.0" + resolved "https://registry.yarnpkg.com/doctrine/-/doctrine-3.0.0.tgz#addebead72a6574db783639dc87a121773973961" + integrity sha512-yS+Q5i3hBf7GBkd4KG8a7eBNNWNGLTaEwwYWUijIYM7zrlYDM0BFXHjjPWlWZ1Rg7UaddZeIDmi9jF3HmqiQ2w== + dependencies: + esutils "^2.0.2" + +emoji-regex@^7.0.1: + version "7.0.3" + resolved "https://registry.yarnpkg.com/emoji-regex/-/emoji-regex-7.0.3.tgz#933a04052860c85e83c122479c4748a8e4c72156" + integrity sha512-CwBLREIQ7LvYFB0WyRvwhq5N5qPhc6PMjD6bYggFlI5YyDgl+0vxq5VHbMOFqLg7hfWzmu8T5Z1QofhmTIhItA== + +es-abstract@^1.5.0: + version "1.13.0" + resolved "https://registry.yarnpkg.com/es-abstract/-/es-abstract-1.13.0.tgz#ac86145fdd5099d8dd49558ccba2eaf9b88e24e9" + integrity sha512-vDZfg/ykNxQVwup/8E1BZhVzFfBxs9NqMzGcvIJrqg5k2/5Za2bWo40dK2J1pgLngZ7c+Shh8lwYtLGyrwPutg== + dependencies: + es-to-primitive "^1.2.0" + function-bind "^1.1.1" + has "^1.0.3" + is-callable "^1.1.4" + is-regex "^1.0.4" + object-keys "^1.0.12" + +es-to-primitive@^1.2.0: + version "1.2.0" + resolved "https://registry.yarnpkg.com/es-to-primitive/-/es-to-primitive-1.2.0.tgz#edf72478033456e8dda8ef09e00ad9650707f377" + integrity sha512-qZryBOJjV//LaxLTV6UC//WewneB3LcXOL9NP++ozKVXsIIIpm/2c13UDiD9Jp2eThsecw9m3jPqDwTyobcdbg== + dependencies: + is-callable "^1.1.4" + is-date-object "^1.0.1" + is-symbol "^1.0.2" + +escape-string-regexp@^1.0.5: + version "1.0.5" + resolved "https://registry.yarnpkg.com/escape-string-regexp/-/escape-string-regexp-1.0.5.tgz#1b61c0562190a8dff6ae3bb2cf0200ca130b86d4" + integrity sha1-G2HAViGQqN/2rjuyzwIAyhMLhtQ= + +eslint-scope@^5.0.0: + version "5.0.0" + resolved "https://registry.yarnpkg.com/eslint-scope/-/eslint-scope-5.0.0.tgz#e87c8887c73e8d1ec84f1ca591645c358bfc8fb9" + integrity sha512-oYrhJW7S0bxAFDvWqzvMPRm6pcgcnWc4QnofCAqRTRfQC0JcwenzGglTtsLyIuuWFfkqDG9vz67cnttSd53djw== + dependencies: + esrecurse "^4.1.0" + estraverse "^4.1.1" + +eslint-utils@^1.3.1: + version "1.4.3" + resolved "https://registry.yarnpkg.com/eslint-utils/-/eslint-utils-1.4.3.tgz#74fec7c54d0776b6f67e0251040b5806564e981f" + integrity sha512-fbBN5W2xdY45KulGXmLHZ3c3FHfVYmKg0IrAKGOkT/464PQsx2UeIzfz1RmEci+KLm1bBaAzZAh8+/E+XAeZ8Q== + dependencies: + eslint-visitor-keys "^1.1.0" + +eslint-visitor-keys@^1.0.0, eslint-visitor-keys@^1.1.0: + version "1.1.0" + resolved "https://registry.yarnpkg.com/eslint-visitor-keys/-/eslint-visitor-keys-1.1.0.tgz#e2a82cea84ff246ad6fb57f9bde5b46621459ec2" + integrity sha512-8y9YjtM1JBJU/A9Kc+SbaOV4y29sSWckBwMHa+FGtVj5gN/sbnKDf6xJUl+8g7FAij9LVaP8C24DUiH/f/2Z9A== + +eslint@6: + version "6.1.0" + resolved "https://registry.yarnpkg.com/eslint/-/eslint-6.1.0.tgz#06438a4a278b1d84fb107d24eaaa35471986e646" + integrity sha512-QhrbdRD7ofuV09IuE2ySWBz0FyXCq0rriLTZXZqaWSI79CVtHVRdkFuFTViiqzZhkCgfOh9USpriuGN2gIpZDQ== + dependencies: + "@babel/code-frame" "^7.0.0" + ajv "^6.10.0" + chalk "^2.1.0" + cross-spawn "^6.0.5" + debug "^4.0.1" + doctrine "^3.0.0" + eslint-scope "^5.0.0" + eslint-utils "^1.3.1" + eslint-visitor-keys "^1.0.0" + espree "^6.0.0" + esquery "^1.0.1" + esutils "^2.0.2" + file-entry-cache "^5.0.1" + functional-red-black-tree "^1.0.1" + glob-parent "^5.0.0" + globals "^11.7.0" + ignore "^4.0.6" + import-fresh "^3.0.0" + imurmurhash "^0.1.4" + inquirer "^6.4.1" + is-glob "^4.0.0" + js-yaml "^3.13.1" + json-stable-stringify-without-jsonify "^1.0.1" + levn "^0.3.0" + lodash "^4.17.14" + minimatch "^3.0.4" + mkdirp "^0.5.1" + natural-compare "^1.4.0" + optionator "^0.8.2" + progress "^2.0.0" + regexpp "^2.0.1" + semver "^6.1.2" + strip-ansi "^5.2.0" + strip-json-comments "^3.0.1" + table "^5.2.3" + text-table "^0.2.0" + v8-compile-cache "^2.0.3" + +espree@^6.0.0: + version "6.0.0" + resolved "https://registry.yarnpkg.com/espree/-/espree-6.0.0.tgz#716fc1f5a245ef5b9a7fdb1d7b0d3f02322e75f6" + integrity sha512-lJvCS6YbCn3ImT3yKkPe0+tJ+mH6ljhGNjHQH9mRtiO6gjhVAOhVXW1yjnwqGwTkK3bGbye+hb00nFNmu0l/1Q== + dependencies: + acorn "^6.0.7" + acorn-jsx "^5.0.0" + eslint-visitor-keys "^1.0.0" + +esprima@^4.0.0: + version "4.0.1" + resolved "https://registry.yarnpkg.com/esprima/-/esprima-4.0.1.tgz#13b04cdb3e6c5d19df91ab6987a8695619b0aa71" + integrity sha512-eGuFFw7Upda+g4p+QHvnW0RyTX/SVeJBDM/gCtMARO0cLuT2HcEKnTPvhjV6aGeqrCB/sbNop0Kszm0jsaWU4A== + +esquery@^1.0.1: + version "1.0.1" + resolved "https://registry.yarnpkg.com/esquery/-/esquery-1.0.1.tgz#406c51658b1f5991a5f9b62b1dc25b00e3e5c708" + integrity sha512-SmiyZ5zIWH9VM+SRUReLS5Q8a7GxtRdxEBVZpm98rJM7Sb+A9DVCndXfkeFUd3byderg+EbDkfnevfCwynWaNA== + dependencies: + estraverse "^4.0.0" + +esrecurse@^4.1.0: + version "4.2.1" + resolved "https://registry.yarnpkg.com/esrecurse/-/esrecurse-4.2.1.tgz#007a3b9fdbc2b3bb87e4879ea19c92fdbd3942cf" + integrity sha512-64RBB++fIOAXPw3P9cy89qfMlvZEXZkqqJkjqqXIvzP5ezRZjW+lPWjw35UX/3EhUPFYbg5ER4JYgDw4007/DQ== + dependencies: + estraverse "^4.1.0" + +estraverse@^4.0.0, estraverse@^4.1.0, estraverse@^4.1.1: + version "4.2.0" + resolved "https://registry.yarnpkg.com/estraverse/-/estraverse-4.2.0.tgz#0dee3fed31fcd469618ce7342099fc1afa0bdb13" + integrity sha1-De4/7TH81GlhjOc0IJn8GvoL2xM= + +estree-walker@^0.6.1: + version "0.6.1" + resolved "https://registry.yarnpkg.com/estree-walker/-/estree-walker-0.6.1.tgz#53049143f40c6eb918b23671d1fe3219f3a1b362" + integrity sha512-SqmZANLWS0mnatqbSfRP5g8OXZC12Fgg1IwNtLsyHDzJizORW4khDfjPqJZsemPWBB2uqykUah5YpQ6epsqC/w== + +esutils@^2.0.2: + version "2.0.2" + resolved "https://registry.yarnpkg.com/esutils/-/esutils-2.0.2.tgz#0abf4f1caa5bcb1f7a9d8acc6dea4faaa04bac9b" + integrity sha1-Cr9PHKpbyx96nYrMbepPqqBLrJs= + +external-editor@^3.0.3: + version "3.1.0" + resolved "https://registry.yarnpkg.com/external-editor/-/external-editor-3.1.0.tgz#cb03f740befae03ea4d283caed2741a83f335495" + integrity sha512-hMQ4CX1p1izmuLYyZqLMO/qGNw10wSv9QDCPfzXfyFrOaCSSoRfqE1Kf1s5an66J5JZC62NewG+mK49jOCtQew== + dependencies: + chardet "^0.7.0" + iconv-lite "^0.4.24" + tmp "^0.0.33" + +fast-deep-equal@^2.0.1: + version "2.0.1" + resolved "https://registry.yarnpkg.com/fast-deep-equal/-/fast-deep-equal-2.0.1.tgz#7b05218ddf9667bf7f370bf7fdb2cb15fdd0aa49" + integrity sha1-ewUhjd+WZ79/Nwv3/bLLFf3Qqkk= + +fast-json-stable-stringify@^2.0.0: + version "2.0.0" + resolved "https://registry.yarnpkg.com/fast-json-stable-stringify/-/fast-json-stable-stringify-2.0.0.tgz#d5142c0caee6b1189f87d3a76111064f86c8bbf2" + integrity sha1-1RQsDK7msRifh9OnYREGT4bIu/I= + +fast-levenshtein@~2.0.4: + version "2.0.6" + resolved "https://registry.yarnpkg.com/fast-levenshtein/-/fast-levenshtein-2.0.6.tgz#3d8a5c66883a16a30ca8643e851f19baa7797917" + integrity sha1-PYpcZog6FqMMqGQ+hR8Zuqd5eRc= + +figures@^2.0.0: + version "2.0.0" + resolved "https://registry.yarnpkg.com/figures/-/figures-2.0.0.tgz#3ab1a2d2a62c8bfb431a0c94cb797a2fce27c962" + integrity sha1-OrGi0qYsi/tDGgyUy3l6L84nyWI= + dependencies: + escape-string-regexp "^1.0.5" + +file-entry-cache@^5.0.1: + version "5.0.1" + resolved "https://registry.yarnpkg.com/file-entry-cache/-/file-entry-cache-5.0.1.tgz#ca0f6efa6dd3d561333fb14515065c2fafdf439c" + integrity sha512-bCg29ictuBaKUwwArK4ouCaqDgLZcysCFLmM/Yn/FDoqndh/9vNuQfXRDvTuXKLxfD/JtZQGKFT8MGcJBK644g== + dependencies: + flat-cache "^2.0.1" + +flat-cache@^2.0.1: + version "2.0.1" + resolved "https://registry.yarnpkg.com/flat-cache/-/flat-cache-2.0.1.tgz#5d296d6f04bda44a4630a301413bdbc2ec085ec0" + integrity sha512-LoQe6yDuUMDzQAEH8sgmh4Md6oZnc/7PjtwjNFSzveXqSHt6ka9fPBuso7IGf9Rz4uqnSnWiFH2B/zj24a5ReA== + dependencies: + flatted "^2.0.0" + rimraf "2.6.3" + write "1.0.3" + +flatted@^2.0.0: + version "2.0.1" + resolved "https://registry.yarnpkg.com/flatted/-/flatted-2.0.1.tgz#69e57caa8f0eacbc281d2e2cb458d46fdb449e08" + integrity sha512-a1hQMktqW9Nmqr5aktAux3JMNqaucxGcjtjWnZLHX7yyPCmlSV3M54nGYbqT8K+0GhF3NBgmJCc3ma+WOgX8Jg== + +for-each@~0.3.3: + version "0.3.3" + resolved "https://registry.yarnpkg.com/for-each/-/for-each-0.3.3.tgz#69b447e88a0a5d32c3e7084f3f1710034b21376e" + integrity sha512-jqYfLp7mo9vIyQf8ykW2v7A+2N4QjeCeI5+Dz9XraiO1ign81wjiH7Fb9vSOWvQfNtmSa4H2RoQTrrXivdUZmw== + dependencies: + is-callable "^1.1.3" + +fs.realpath@^1.0.0: + version "1.0.0" + resolved "https://registry.yarnpkg.com/fs.realpath/-/fs.realpath-1.0.0.tgz#1504ad2523158caa40db4a2787cb01411994ea4f" + integrity sha1-FQStJSMVjKpA20onh8sBQRmU6k8= + +function-bind@^1.0.2, function-bind@^1.1.1, function-bind@~1.1.1: + version "1.1.1" + resolved "https://registry.yarnpkg.com/function-bind/-/function-bind-1.1.1.tgz#a56899d3ea3c9bab874bb9773b7c5ede92f4895d" + integrity sha512-yIovAzMX49sF8Yl58fSCWJ5svSLuaibPxXQJFLmBObTuCr0Mf1KiPopGM9NiFjiYBCbfaa2Fh6breQ6ANVTI0A== + +functional-red-black-tree@^1.0.1: + version "1.0.1" + resolved "https://registry.yarnpkg.com/functional-red-black-tree/-/functional-red-black-tree-1.0.1.tgz#1b0ab3bd553b2a0d6399d29c0e3ea0b252078327" + integrity sha1-GwqzvVU7Kg1jmdKcDj6gslIHgyc= + +glob-parent@^5.0.0: + version "5.0.0" + resolved "https://registry.yarnpkg.com/glob-parent/-/glob-parent-5.0.0.tgz#1dc99f0f39b006d3e92c2c284068382f0c20e954" + integrity sha512-Z2RwiujPRGluePM6j699ktJYxmPpJKCfpGA13jz2hmFZC7gKetzrWvg5KN3+OsIFmydGyZ1AVwERCq1w/ZZwRg== + dependencies: + is-glob "^4.0.1" + +glob@^7.1.3, glob@~7.1.4: + version "7.1.4" + resolved "https://registry.yarnpkg.com/glob/-/glob-7.1.4.tgz#aa608a2f6c577ad357e1ae5a5c26d9a8d1969255" + integrity sha512-hkLPepehmnKk41pUGm3sYxoFs/umurYfYJCerbXEyFIWcAzvpipAgVkBqqT9RBKMGjnq6kMuyYwha6csxbiM1A== + dependencies: + fs.realpath "^1.0.0" + inflight "^1.0.4" + inherits "2" + minimatch "^3.0.4" + once "^1.3.0" + path-is-absolute "^1.0.0" + +globals@^11.7.0: + version "11.12.0" + resolved "https://registry.yarnpkg.com/globals/-/globals-11.12.0.tgz#ab8795338868a0babd8525758018c2a7eb95c42e" + integrity sha512-WOBp/EEGUiIsJSp7wcv/y6MO+lV9UoncWqxuFfm8eBwzWNgyfBd6Gz+IeKQ9jCmyhoH99g15M3T+QaVHFjizVA== + +has-flag@^3.0.0: + version "3.0.0" + resolved "https://registry.yarnpkg.com/has-flag/-/has-flag-3.0.0.tgz#b5d454dc2199ae225699f3467e5a07f3b955bafd" + integrity sha1-tdRU3CGZriJWmfNGfloH87lVuv0= + +has-symbols@^1.0.0: + version "1.0.0" + resolved "https://registry.yarnpkg.com/has-symbols/-/has-symbols-1.0.0.tgz#ba1a8f1af2a0fc39650f5c850367704122063b44" + integrity sha1-uhqPGvKg/DllD1yFA2dwQSIGO0Q= + +has@^1.0.1, has@^1.0.3, has@~1.0.3: + version "1.0.3" + resolved "https://registry.yarnpkg.com/has/-/has-1.0.3.tgz#722d7cbfc1f6aa8241f16dd814e011e1f41e8796" + integrity sha512-f2dvO0VU6Oej7RkWJGrehjbzMAjFp5/VKPp5tTpWIV4JHHZK1/BxbFRtf/siA2SWTe09caDmVtYYzWEIbBS4zw== + dependencies: + function-bind "^1.1.1" + +iconv-lite@^0.4.24: + version "0.4.24" + resolved "https://registry.yarnpkg.com/iconv-lite/-/iconv-lite-0.4.24.tgz#2022b4b25fbddc21d2f524974a474aafe733908b" + integrity sha512-v3MXnZAcvnywkTUEZomIActle7RXXeedOR31wwl7VlyoXO4Qi9arvSenNQWne1TcRwhCL1HwLI21bEqdpj8/rA== + dependencies: + safer-buffer ">= 2.1.2 < 3" + +ignore@^4.0.6: + version "4.0.6" + resolved "https://registry.yarnpkg.com/ignore/-/ignore-4.0.6.tgz#750e3db5862087b4737ebac8207ffd1ef27b25fc" + integrity sha512-cyFDKrqc/YdcWFniJhzI42+AzS+gNwmUzOSFcRCQYwySuBBBy/KjuxWLZ/FHEH6Moq1NizMOBWyTcv8O4OZIMg== + +import-fresh@^3.0.0: + version "3.1.0" + resolved "https://registry.yarnpkg.com/import-fresh/-/import-fresh-3.1.0.tgz#6d33fa1dcef6df930fae003446f33415af905118" + integrity sha512-PpuksHKGt8rXfWEr9m9EHIpgyyaltBy8+eF6GJM0QCAxMgxCfucMF3mjecK2QsJr0amJW7gTqh5/wht0z2UhEQ== + dependencies: + parent-module "^1.0.0" + resolve-from "^4.0.0" + +imurmurhash@^0.1.4: + version "0.1.4" + resolved "https://registry.yarnpkg.com/imurmurhash/-/imurmurhash-0.1.4.tgz#9218b9b2b928a238b13dc4fb6b6d576f231453ea" + integrity sha1-khi5srkoojixPcT7a21XbyMUU+o= + +inflight@^1.0.4: + version "1.0.6" + resolved "https://registry.yarnpkg.com/inflight/-/inflight-1.0.6.tgz#49bd6331d7d02d0c09bc910a1075ba8165b56df9" + integrity sha1-Sb1jMdfQLQwJvJEKEHW6gWW1bfk= + dependencies: + once "^1.3.0" + wrappy "1" + +inherits@2, inherits@~2.0.3, inherits@~2.0.4: + version "2.0.4" + resolved "https://registry.yarnpkg.com/inherits/-/inherits-2.0.4.tgz#0fa2c64f932917c3433a0ded55363aae37416b7c" + integrity sha512-k/vGaX4/Yla3WzyMCvTQOXYeIHvqOKtnqBduzTHpzpQZzAskKMhZ2K+EnBiSM9zGSoIFeMpXKxa4dYeZIQqewQ== + +inquirer@^6.4.1: + version "6.5.0" + resolved "https://registry.yarnpkg.com/inquirer/-/inquirer-6.5.0.tgz#2303317efc9a4ea7ec2e2df6f86569b734accf42" + integrity sha512-scfHejeG/lVZSpvCXpsB4j/wQNPM5JC8kiElOI0OUTwmc1RTpXr4H32/HOlQHcZiYl2z2VElwuCVDRG8vFmbnA== + dependencies: + ansi-escapes "^3.2.0" + chalk "^2.4.2" + cli-cursor "^2.1.0" + cli-width "^2.0.0" + external-editor "^3.0.3" + figures "^2.0.0" + lodash "^4.17.12" + mute-stream "0.0.7" + run-async "^2.2.0" + rxjs "^6.4.0" + string-width "^2.1.0" + strip-ansi "^5.1.0" + through "^2.3.6" + +is-callable@^1.1.3, is-callable@^1.1.4: + version "1.1.4" + resolved "https://registry.yarnpkg.com/is-callable/-/is-callable-1.1.4.tgz#1e1adf219e1eeb684d691f9d6a05ff0d30a24d75" + integrity sha512-r5p9sxJjYnArLjObpjA4xu5EKI3CuKHkJXMhT7kwbpUyIFD1n5PMAsoPvWnvtZiNz7LjkYDRZhd7FlI0eMijEA== + +is-date-object@^1.0.1: + version "1.0.1" + resolved "https://registry.yarnpkg.com/is-date-object/-/is-date-object-1.0.1.tgz#9aa20eb6aeebbff77fbd33e74ca01b33581d3a16" + integrity sha1-mqIOtq7rv/d/vTPnTKAbM1gdOhY= + +is-extglob@^2.1.1: + version "2.1.1" + resolved "https://registry.yarnpkg.com/is-extglob/-/is-extglob-2.1.1.tgz#a88c02535791f02ed37c76a1b9ea9773c833f8c2" + integrity sha1-qIwCU1eR8C7TfHahueqXc8gz+MI= + +is-fullwidth-code-point@^2.0.0: + version "2.0.0" + resolved "https://registry.yarnpkg.com/is-fullwidth-code-point/-/is-fullwidth-code-point-2.0.0.tgz#a3b30a5c4f199183167aaab93beefae3ddfb654f" + integrity sha1-o7MKXE8ZkYMWeqq5O+764937ZU8= + +is-glob@^4.0.0, is-glob@^4.0.1: + version "4.0.1" + resolved "https://registry.yarnpkg.com/is-glob/-/is-glob-4.0.1.tgz#7567dbe9f2f5e2467bc77ab83c4a29482407a5dc" + integrity sha512-5G0tKtBTFImOqDnLB2hG6Bp2qcKEFduo4tZu9MT/H6NQv/ghhy30o55ufafxJ/LdH79LLs2Kfrn85TLKyA7BUg== + dependencies: + is-extglob "^2.1.1" + +is-promise@^2.1.0: + version "2.1.0" + resolved "https://registry.yarnpkg.com/is-promise/-/is-promise-2.1.0.tgz#79a2a9ece7f096e80f36d2b2f3bc16c1ff4bf3fa" + integrity sha1-eaKp7OfwlugPNtKy87wWwf9L8/o= + +is-regex@^1.0.4: + version "1.0.4" + resolved "https://registry.yarnpkg.com/is-regex/-/is-regex-1.0.4.tgz#5517489b547091b0930e095654ced25ee97e9491" + integrity sha1-VRdIm1RwkbCTDglWVM7SXul+lJE= + dependencies: + has "^1.0.1" + +is-symbol@^1.0.2: + version "1.0.2" + resolved "https://registry.yarnpkg.com/is-symbol/-/is-symbol-1.0.2.tgz#a055f6ae57192caee329e7a860118b497a950f38" + integrity sha512-HS8bZ9ox60yCJLH9snBpIwv9pYUAkcuLhSA1oero1UB5y9aiQpRA8y2ex945AOtCZL1lJDeIk3G5LthswI46Lw== + dependencies: + has-symbols "^1.0.0" + +isarray@~1.0.0: + version "1.0.0" + resolved "https://registry.yarnpkg.com/isarray/-/isarray-1.0.0.tgz#bb935d48582cba168c06834957a54a3e07124f11" + integrity sha1-u5NdSFgsuhaMBoNJV6VKPgcSTxE= + +isexe@^2.0.0: + version "2.0.0" + resolved "https://registry.yarnpkg.com/isexe/-/isexe-2.0.0.tgz#e8fbf374dc556ff8947a10dcb0572d633f2cfa10" + integrity sha1-6PvzdNxVb/iUehDcsFctYz8s+hA= + +jest-worker@^24.6.0: + version "24.6.0" + resolved "https://registry.yarnpkg.com/jest-worker/-/jest-worker-24.6.0.tgz#7f81ceae34b7cde0c9827a6980c35b7cdc0161b3" + integrity sha512-jDwgW5W9qGNvpI1tNnvajh0a5IE/PuGLFmHk6aR/BZFz8tSgGw17GsDPXAJ6p91IvYDjOw8GpFbvvZGAK+DPQQ== + dependencies: + merge-stream "^1.0.1" + supports-color "^6.1.0" + +js-tokens@^4.0.0: + version "4.0.0" + resolved "https://registry.yarnpkg.com/js-tokens/-/js-tokens-4.0.0.tgz#19203fb59991df98e3a287050d4647cdeaf32499" + integrity sha512-RdJUflcE3cUzKiMqQgsCu06FPu9UdIJO0beYbPhHN4k6apgJtifcoCtT9bcxOpYBtpD2kCM6Sbzg4CausW/PKQ== + +js-yaml@^3.13.1: + version "3.13.1" + resolved "https://registry.yarnpkg.com/js-yaml/-/js-yaml-3.13.1.tgz#aff151b30bfdfa8e49e05da22e7415e9dfa37847" + integrity sha512-YfbcO7jXDdyj0DGxYVSlSeQNHbD7XPWvrVWeVUujrQEoZzWJIRrCPoyk6kL6IAjAG2IolMK4T0hNUe0HOUs5Jw== + dependencies: + argparse "^1.0.7" + esprima "^4.0.0" + +json-schema-traverse@^0.4.1: + version "0.4.1" + resolved "https://registry.yarnpkg.com/json-schema-traverse/-/json-schema-traverse-0.4.1.tgz#69f6a87d9513ab8bb8fe63bdb0979c448e684660" + integrity sha512-xbbCH5dCYU5T8LcEhhuh7HJ88HXuW3qsI3Y0zOZFKfZEHcpWiHU/Jxzk629Brsab/mMiHQti9wMP+845RPe3Vg== + +json-stable-stringify-without-jsonify@^1.0.1: + version "1.0.1" + resolved "https://registry.yarnpkg.com/json-stable-stringify-without-jsonify/-/json-stable-stringify-without-jsonify-1.0.1.tgz#9db7b59496ad3f3cfef30a75142d2d930ad72651" + integrity sha1-nbe1lJatPzz+8wp1FC0tkwrXJlE= + +levn@^0.3.0, levn@~0.3.0: + version "0.3.0" + resolved "https://registry.yarnpkg.com/levn/-/levn-0.3.0.tgz#3b09924edf9f083c0490fdd4c0bc4421e04764ee" + integrity sha1-OwmSTt+fCDwEkP3UwLxEIeBHZO4= + dependencies: + prelude-ls "~1.1.2" + type-check "~0.3.2" + +lodash@^4.17.12, lodash@^4.17.14: + version "4.17.15" + resolved "https://registry.yarnpkg.com/lodash/-/lodash-4.17.15.tgz#b447f6670a0455bbfeedd11392eff330ea097548" + integrity sha512-8xOcRHvCjnocdS5cpwXQXVzmmh5e5+saE2QGoeQmbKmRS6J3VQppPOIt0MnmE+4xlZoumy0GPG0D0MVIQbNA1A== + +merge-stream@^1.0.1: + version "1.0.1" + resolved "https://registry.yarnpkg.com/merge-stream/-/merge-stream-1.0.1.tgz#4041202d508a342ba00174008df0c251b8c135e1" + integrity sha1-QEEgLVCKNCugAXQAjfDCUbjBNeE= + dependencies: + readable-stream "^2.0.1" + +mimic-fn@^1.0.0: + version "1.2.0" + resolved "https://registry.yarnpkg.com/mimic-fn/-/mimic-fn-1.2.0.tgz#820c86a39334640e99516928bd03fca88057d022" + integrity sha512-jf84uxzwiuiIVKiOLpfYk7N46TSy8ubTonmneY9vrpHNAnp0QBt2BxWV9dO3/j+BoVAb+a5G6YDPW3M5HOdMWQ== + +minimatch@^3.0.4: + version "3.0.4" + resolved "https://registry.yarnpkg.com/minimatch/-/minimatch-3.0.4.tgz#5166e286457f03306064be5497e8dbb0c3d32083" + integrity sha512-yJHVQEhyqPLUTgt9B83PXu6W3rx4MvvHvSUvToogpwoGDOUQ+yDrR0HRot+yOCdCO7u4hX3pWft6kWBBcqh0UA== + dependencies: + brace-expansion "^1.1.7" + +minimist@0.0.8: + version "0.0.8" + resolved "https://registry.yarnpkg.com/minimist/-/minimist-0.0.8.tgz#857fcabfc3397d2625b8228262e86aa7a011b05d" + integrity sha1-hX/Kv8M5fSYluCKCYuhqp6ARsF0= + +minimist@~1.2.0: + version "1.2.0" + resolved "https://registry.yarnpkg.com/minimist/-/minimist-1.2.0.tgz#a35008b20f41383eec1fb914f4cd5df79a264284" + integrity sha1-o1AIsg9BOD7sH7kU9M1d95omQoQ= + +mkdirp@^0.5.1: + version "0.5.1" + resolved "https://registry.yarnpkg.com/mkdirp/-/mkdirp-0.5.1.tgz#30057438eac6cf7f8c4767f38648d6697d75c903" + integrity sha1-MAV0OOrGz3+MR2fzhkjWaX11yQM= + dependencies: + minimist "0.0.8" + +ms@^2.1.1: + version "2.1.2" + resolved "https://registry.yarnpkg.com/ms/-/ms-2.1.2.tgz#d09d1f357b443f493382a8eb3ccd183872ae6009" + integrity sha512-sGkPx+VjMtmA6MX27oA4FBFELFCZZ4S4XqeGOXCv68tT+jb3vk/RyaKWP0PTKyWtmLSM0b+adUTEvbs1PEaH2w== + +mute-stream@0.0.7: + version "0.0.7" + resolved "https://registry.yarnpkg.com/mute-stream/-/mute-stream-0.0.7.tgz#3075ce93bc21b8fab43e1bc4da7e8115ed1e7bab" + integrity sha1-MHXOk7whuPq0PhvE2n6BFe0ee6s= + +natural-compare@^1.4.0: + version "1.4.0" + resolved "https://registry.yarnpkg.com/natural-compare/-/natural-compare-1.4.0.tgz#4abebfeed7541f2c27acfb29bdbbd15c8d5ba4f7" + integrity sha1-Sr6/7tdUHywnrPspvbvRXI1bpPc= + +nice-try@^1.0.4: + version "1.0.5" + resolved "https://registry.yarnpkg.com/nice-try/-/nice-try-1.0.5.tgz#a3378a7696ce7d223e88fc9b764bd7ef1089e366" + integrity sha512-1nh45deeb5olNY7eX82BkPO7SSxR5SSYJiPTrTdFUVYwAl8CKMA5N9PjTYkHiRjisVcxcQ1HXdLhx2qxxJzLNQ== + +object-inspect@~1.6.0: + version "1.6.0" + resolved "https://registry.yarnpkg.com/object-inspect/-/object-inspect-1.6.0.tgz#c70b6cbf72f274aab4c34c0c82f5167bf82cf15b" + integrity sha512-GJzfBZ6DgDAmnuaM3104jR4s1Myxr3Y3zfIyN4z3UdqN69oSRacNK8UhnobDdC+7J2AHCjGwxQubNJfE70SXXQ== + +object-keys@^1.0.12: + version "1.1.1" + resolved "https://registry.yarnpkg.com/object-keys/-/object-keys-1.1.1.tgz#1c47f272df277f3b1daf061677d9c82e2322c60e" + integrity sha512-NuAESUOUMrlIXOfHKzD6bpPu3tYt3xvjNdRIQ+FeT0lNb4K8WR70CaDxhuNguS2XG+GjkyMwOzsN5ZktImfhLA== + +once@^1.3.0: + version "1.4.0" + resolved "https://registry.yarnpkg.com/once/-/once-1.4.0.tgz#583b1aa775961d4b113ac17d9c50baef9dd76bd1" + integrity sha1-WDsap3WWHUsROsF9nFC6753Xa9E= + dependencies: + wrappy "1" + +onetime@^2.0.0: + version "2.0.1" + resolved "https://registry.yarnpkg.com/onetime/-/onetime-2.0.1.tgz#067428230fd67443b2794b22bba528b6867962d4" + integrity sha1-BnQoIw/WdEOyeUsiu6UotoZ5YtQ= + dependencies: + mimic-fn "^1.0.0" + +optionator@^0.8.2: + version "0.8.2" + resolved "https://registry.yarnpkg.com/optionator/-/optionator-0.8.2.tgz#364c5e409d3f4d6301d6c0b4c05bba50180aeb64" + integrity sha1-NkxeQJ0/TWMB1sC0wFu6UBgK62Q= + dependencies: + deep-is "~0.1.3" + fast-levenshtein "~2.0.4" + levn "~0.3.0" + prelude-ls "~1.1.2" + type-check "~0.3.2" + wordwrap "~1.0.0" + +os-tmpdir@~1.0.2: + version "1.0.2" + resolved "https://registry.yarnpkg.com/os-tmpdir/-/os-tmpdir-1.0.2.tgz#bbe67406c79aa85c5cfec766fe5734555dfa1274" + integrity sha1-u+Z0BseaqFxc/sdm/lc0VV36EnQ= + +parent-module@^1.0.0: + version "1.0.1" + resolved "https://registry.yarnpkg.com/parent-module/-/parent-module-1.0.1.tgz#691d2709e78c79fae3a156622452d00762caaaa2" + integrity sha512-GQ2EWRpQV8/o+Aw8YqtfZZPfNRWZYkbidE9k5rpl/hC3vtHHBfGm2Ifi6qWV+coDGkrUKZAxE3Lot5kcsRlh+g== + dependencies: + callsites "^3.0.0" + +path-is-absolute@^1.0.0: + version "1.0.1" + resolved "https://registry.yarnpkg.com/path-is-absolute/-/path-is-absolute-1.0.1.tgz#174b9268735534ffbc7ace6bf53a5a9e1b5c5f5f" + integrity sha1-F0uSaHNVNP+8es5r9TpanhtcX18= + +path-key@^2.0.1: + version "2.0.1" + resolved "https://registry.yarnpkg.com/path-key/-/path-key-2.0.1.tgz#411cadb574c5a140d3a4b1910d40d80cc9f40b40" + integrity sha1-QRyttXTFoUDTpLGRDUDYDMn0C0A= + +path-parse@^1.0.6: + version "1.0.6" + resolved "https://registry.yarnpkg.com/path-parse/-/path-parse-1.0.6.tgz#d62dbb5679405d72c4737ec58600e9ddcf06d24c" + integrity sha512-GSmOT2EbHrINBf9SR7CDELwlJ8AENk3Qn7OikK4nFYAu3Ote2+JYNVvkpAEQm3/TLNEJFD/xZJjzyxg3KBWOzw== + +prelude-ls@~1.1.2: + version "1.1.2" + resolved "https://registry.yarnpkg.com/prelude-ls/-/prelude-ls-1.1.2.tgz#21932a549f5e52ffd9a827f570e04be62a97da54" + integrity sha1-IZMqVJ9eUv/ZqCf1cOBL5iqX2lQ= + +process-nextick-args@~2.0.0: + version "2.0.1" + resolved "https://registry.yarnpkg.com/process-nextick-args/-/process-nextick-args-2.0.1.tgz#7820d9b16120cc55ca9ae7792680ae7dba6d7fe2" + integrity sha512-3ouUOpQhtgrbOa17J7+uxOTpITYWaGP7/AhoR3+A+/1e9skrzelGi/dXzEYyvbxubEF6Wn2ypscTKiKJFFn1ag== + +progress@^2.0.0: + version "2.0.3" + resolved "https://registry.yarnpkg.com/progress/-/progress-2.0.3.tgz#7e8cf8d8f5b8f239c1bc68beb4eb78567d572ef8" + integrity sha512-7PiHtLll5LdnKIMw100I+8xJXR5gW2QwWYkT6iJva0bXitZKa/XMrSbdmg3r2Xnaidz9Qumd0VPaMrZlF9V9sA== + +punycode@^2.1.0: + version "2.1.1" + resolved "https://registry.yarnpkg.com/punycode/-/punycode-2.1.1.tgz#b58b010ac40c22c5657616c8d2c2c02c7bf479ec" + integrity sha512-XRsRjdf+j5ml+y/6GKHPZbrF/8p2Yga0JPtdqTIY2Xe5ohJPD9saDJJLPvp9+NSBprVvevdXZybnj2cv8OEd0A== + +readable-stream@^2.0.1: + version "2.3.6" + resolved "https://registry.yarnpkg.com/readable-stream/-/readable-stream-2.3.6.tgz#b11c27d88b8ff1fbe070643cf94b0c79ae1b0aaf" + integrity sha512-tQtKA9WIAhBF3+VLAseyMqZeBjW0AHJoxOtYqSUZNJxauErmLbVm2FW1y+J/YA9dUrAC39ITejlZWhVIwawkKw== + dependencies: + core-util-is "~1.0.0" + inherits "~2.0.3" + isarray "~1.0.0" + process-nextick-args "~2.0.0" + safe-buffer "~5.1.1" + string_decoder "~1.1.1" + util-deprecate "~1.0.1" + +regexpp@^2.0.1: + version "2.0.1" + resolved "https://registry.yarnpkg.com/regexpp/-/regexpp-2.0.1.tgz#8d19d31cf632482b589049f8281f93dbcba4d07f" + integrity sha512-lv0M6+TkDVniA3aD1Eg0DVpfU/booSu7Eev3TDO/mZKHBfVjgCGTV4t4buppESEYDtkArYFOxTJWv6S5C+iaNw== + +resolve-from@^4.0.0: + version "4.0.0" + resolved "https://registry.yarnpkg.com/resolve-from/-/resolve-from-4.0.0.tgz#4abcd852ad32dd7baabfe9b40e00a36db5f392e6" + integrity sha512-pb/MYmXstAkysRFx8piNI1tGFNQIFA3vkE3Gq4EuA1dF6gHp/+vgZqsCGJapvy8N3Q+4o7FwvquPJcnZ7RYy4g== + +resolve@~1.11.1: + version "1.11.1" + resolved "https://registry.yarnpkg.com/resolve/-/resolve-1.11.1.tgz#ea10d8110376982fef578df8fc30b9ac30a07a3e" + integrity sha512-vIpgF6wfuJOZI7KKKSP+HmiKggadPQAdsp5HiC1mvqnfp0gF1vdwgBWZIdrVft9pgqoMFQN+R7BSWZiBxx+BBw== + dependencies: + path-parse "^1.0.6" + +restore-cursor@^2.0.0: + version "2.0.0" + resolved "https://registry.yarnpkg.com/restore-cursor/-/restore-cursor-2.0.0.tgz#9f7ee287f82fd326d4fd162923d62129eee0dfaf" + integrity sha1-n37ih/gv0ybU/RYpI9YhKe7g368= + dependencies: + onetime "^2.0.0" + signal-exit "^3.0.2" + +resumer@~0.0.0: + version "0.0.0" + resolved "https://registry.yarnpkg.com/resumer/-/resumer-0.0.0.tgz#f1e8f461e4064ba39e82af3cdc2a8c893d076759" + integrity sha1-8ej0YeQGS6Oegq883CqMiT0HZ1k= + dependencies: + through "~2.3.4" + +rimraf@2.6.3: + version "2.6.3" + resolved "https://registry.yarnpkg.com/rimraf/-/rimraf-2.6.3.tgz#b2d104fe0d8fb27cf9e0a1cda8262dd3833c6cab" + integrity sha512-mwqeW5XsA2qAejG46gYdENaxXjx9onRNCfn7L0duuP4hCuTIi/QO7PDK07KJfp1d+izWPrzEJDcSqBa0OZQriA== + dependencies: + glob "^7.1.3" + +rollup-plugin-terser@5: + version "5.1.1" + resolved "https://registry.yarnpkg.com/rollup-plugin-terser/-/rollup-plugin-terser-5.1.1.tgz#e9d2545ec8d467f96ba99b9216d2285aad8d5b66" + integrity sha512-McIMCDEY8EU6Y839C09UopeRR56wXHGdvKKjlfiZG/GrP6wvZQ62u2ko/Xh1MNH2M9WDL+obAAHySljIZYCuPQ== + dependencies: + "@babel/code-frame" "^7.0.0" + jest-worker "^24.6.0" + rollup-pluginutils "^2.8.1" + serialize-javascript "^1.7.0" + terser "^4.1.0" + +rollup-pluginutils@^2.8.1: + version "2.8.1" + resolved "https://registry.yarnpkg.com/rollup-pluginutils/-/rollup-pluginutils-2.8.1.tgz#8fa6dd0697344938ef26c2c09d2488ce9e33ce97" + integrity sha512-J5oAoysWar6GuZo0s+3bZ6sVZAC0pfqKz68De7ZgDi5z63jOVZn1uJL/+z1jeKHNbGII8kAyHF5q8LnxSX5lQg== + dependencies: + estree-walker "^0.6.1" + +rollup@1: + version "1.17.0" + resolved "https://registry.yarnpkg.com/rollup/-/rollup-1.17.0.tgz#47ee8b04514544fc93b39bae06271244c8db7dfa" + integrity sha512-k/j1m0NIsI4SYgCJR4MWPstGJOWfJyd6gycKoMhyoKPVXxm+L49XtbUwZyFsrSU2YXsOkM4u1ll9CS/ZgJBUpw== + dependencies: + "@types/estree" "0.0.39" + "@types/node" "^12.6.2" + acorn "^6.2.0" + +run-async@^2.2.0: + version "2.3.0" + resolved "https://registry.yarnpkg.com/run-async/-/run-async-2.3.0.tgz#0371ab4ae0bdd720d4166d7dfda64ff7a445a6c0" + integrity sha1-A3GrSuC91yDUFm19/aZP96RFpsA= + dependencies: + is-promise "^2.1.0" + +rxjs@^6.4.0: + version "6.5.2" + resolved "https://registry.yarnpkg.com/rxjs/-/rxjs-6.5.2.tgz#2e35ce815cd46d84d02a209fb4e5921e051dbec7" + integrity sha512-HUb7j3kvb7p7eCUHE3FqjoDsC1xfZQ4AHFWfTKSpZ+sAhhz5X1WX0ZuUqWbzB2QhSLp3DoLUG+hMdEDKqWo2Zg== + dependencies: + tslib "^1.9.0" + +safe-buffer@~5.1.0, safe-buffer@~5.1.1: + version "5.1.2" + resolved "https://registry.yarnpkg.com/safe-buffer/-/safe-buffer-5.1.2.tgz#991ec69d296e0313747d59bdfd2b745c35f8828d" + integrity sha512-Gd2UZBJDkXlY7GbJxfsE8/nvKkUEU1G38c1siN6QP6a9PT9MmHB8GnpscSmMJSoF8LOIrt8ud/wPtojys4G6+g== + +"safer-buffer@>= 2.1.2 < 3": + version "2.1.2" + resolved "https://registry.yarnpkg.com/safer-buffer/-/safer-buffer-2.1.2.tgz#44fa161b0187b9549dd84bb91802f9bd8385cd6a" + integrity sha512-YZo3K82SD7Riyi0E1EQPojLz7kpepnSQI9IyPbHHg1XXXevb5dJI7tpyN2ADxGcQbHG7vcyRHk0cbwqcQriUtg== + +semver@^5.5.0: + version "5.7.0" + resolved "https://registry.yarnpkg.com/semver/-/semver-5.7.0.tgz#790a7cf6fea5459bac96110b29b60412dc8ff96b" + integrity sha512-Ya52jSX2u7QKghxeoFGpLwCtGlt7j0oY9DYb5apt9nPlJ42ID+ulTXESnt/qAQcoSERyZ5sl3LDIOw0nAn/5DA== + +semver@^6.1.2: + version "6.3.0" + resolved "https://registry.yarnpkg.com/semver/-/semver-6.3.0.tgz#ee0a64c8af5e8ceea67687b133761e1becbd1d3d" + integrity sha512-b39TBaTSfV6yBrapU89p5fKekE2m/NwnDocOVruQFS1/veMgdzuPcnOM34M6CwxW8jH/lxEa5rBoDeUwu5HHTw== + +serialize-javascript@^1.7.0: + version "1.7.0" + resolved "https://registry.yarnpkg.com/serialize-javascript/-/serialize-javascript-1.7.0.tgz#d6e0dfb2a3832a8c94468e6eb1db97e55a192a65" + integrity sha512-ke8UG8ulpFOxO8f8gRYabHQe/ZntKlcig2Mp+8+URDP1D8vJZ0KUt7LYo07q25Z/+JVSgpr/cui9PIp5H6/+nA== + +shebang-command@^1.2.0: + version "1.2.0" + resolved "https://registry.yarnpkg.com/shebang-command/-/shebang-command-1.2.0.tgz#44aac65b695b03398968c39f363fee5deafdf1ea" + integrity sha1-RKrGW2lbAzmJaMOfNj/uXer98eo= + dependencies: + shebang-regex "^1.0.0" + +shebang-regex@^1.0.0: + version "1.0.0" + resolved "https://registry.yarnpkg.com/shebang-regex/-/shebang-regex-1.0.0.tgz#da42f49740c0b42db2ca9728571cb190c98efea3" + integrity sha1-2kL0l0DAtC2yypcoVxyxkMmO/qM= + +signal-exit@^3.0.2: + version "3.0.2" + resolved "https://registry.yarnpkg.com/signal-exit/-/signal-exit-3.0.2.tgz#b5fdc08f1287ea1178628e415e25132b73646c6d" + integrity sha1-tf3AjxKH6hF4Yo5BXiUTK3NkbG0= + +slice-ansi@^2.1.0: + version "2.1.0" + resolved "https://registry.yarnpkg.com/slice-ansi/-/slice-ansi-2.1.0.tgz#cacd7693461a637a5788d92a7dd4fba068e81636" + integrity sha512-Qu+VC3EwYLldKa1fCxuuvULvSJOKEgk9pi8dZeCVK7TqBfUNTH4sFkk4joj8afVSfAYgJoSOetjx9QWOJ5mYoQ== + dependencies: + ansi-styles "^3.2.0" + astral-regex "^1.0.0" + is-fullwidth-code-point "^2.0.0" + +source-map-support@~0.5.12: + version "0.5.12" + resolved "https://registry.yarnpkg.com/source-map-support/-/source-map-support-0.5.12.tgz#b4f3b10d51857a5af0138d3ce8003b201613d599" + integrity sha512-4h2Pbvyy15EE02G+JOZpUCmqWJuqrs+sEkzewTm++BPi7Hvn/HwcqLAcNxYAyI0x13CpPPn+kMjl+hplXMHITQ== + dependencies: + buffer-from "^1.0.0" + source-map "^0.6.0" + +source-map@^0.6.0, source-map@~0.6.1: + version "0.6.1" + resolved "https://registry.yarnpkg.com/source-map/-/source-map-0.6.1.tgz#74722af32e9614e9c287a8d0bbde48b5e2f1a263" + integrity sha512-UjgapumWlbMhkBgzT7Ykc5YXUT46F0iKu8SGXq0bcwP5dz/h0Plj6enJqjz1Zbq2l5WaqYnrVbwWOWMyF3F47g== + +sprintf-js@~1.0.2: + version "1.0.3" + resolved "https://registry.yarnpkg.com/sprintf-js/-/sprintf-js-1.0.3.tgz#04e6926f662895354f3dd015203633b857297e2c" + integrity sha1-BOaSb2YolTVPPdAVIDYzuFcpfiw= + +string-width@^2.1.0: + version "2.1.1" + resolved "https://registry.yarnpkg.com/string-width/-/string-width-2.1.1.tgz#ab93f27a8dc13d28cac815c462143a6d9012ae9e" + integrity sha512-nOqH59deCq9SRHlxq1Aw85Jnt4w6KvLKqWVik6oA9ZklXLNIOlqg4F2yrT1MVaTjAqvVwdfeZ7w7aCvJD7ugkw== + dependencies: + is-fullwidth-code-point "^2.0.0" + strip-ansi "^4.0.0" + +string-width@^3.0.0: + version "3.1.0" + resolved "https://registry.yarnpkg.com/string-width/-/string-width-3.1.0.tgz#22767be21b62af1081574306f69ac51b62203961" + integrity sha512-vafcv6KjVZKSgz06oM/H6GDBrAtz8vdhQakGjFIvNrHA6y3HCF1CInLy+QLq8dTJPQ1b+KDUqDFctkdRW44e1w== + dependencies: + emoji-regex "^7.0.1" + is-fullwidth-code-point "^2.0.0" + strip-ansi "^5.1.0" + +string.prototype.trim@~1.1.2: + version "1.1.2" + resolved "https://registry.yarnpkg.com/string.prototype.trim/-/string.prototype.trim-1.1.2.tgz#d04de2c89e137f4d7d206f086b5ed2fae6be8cea" + integrity sha1-0E3iyJ4Tf019IG8Ia17S+ua+jOo= + dependencies: + define-properties "^1.1.2" + es-abstract "^1.5.0" + function-bind "^1.0.2" + +string_decoder@~1.1.1: + version "1.1.1" + resolved "https://registry.yarnpkg.com/string_decoder/-/string_decoder-1.1.1.tgz#9cf1611ba62685d7030ae9e4ba34149c3af03fc8" + integrity sha512-n/ShnvDi6FHbbVfviro+WojiFzv+s8MPMHBczVePfUpDJLwoLT0ht1l4YwBCbi8pJAveEEdnkHyPyTP/mzRfwg== + dependencies: + safe-buffer "~5.1.0" + +strip-ansi@^4.0.0: + version "4.0.0" + resolved "https://registry.yarnpkg.com/strip-ansi/-/strip-ansi-4.0.0.tgz#a8479022eb1ac368a871389b635262c505ee368f" + integrity sha1-qEeQIusaw2iocTibY1JixQXuNo8= + dependencies: + ansi-regex "^3.0.0" + +strip-ansi@^5.1.0, strip-ansi@^5.2.0: + version "5.2.0" + resolved "https://registry.yarnpkg.com/strip-ansi/-/strip-ansi-5.2.0.tgz#8c9a536feb6afc962bdfa5b104a5091c1ad9c0ae" + integrity sha512-DuRs1gKbBqsMKIZlrffwlug8MHkcnpjs5VPmL1PAh+mA30U0DTotfDZ0d2UUsXpPmPmMMJ6W773MaA3J+lbiWA== + dependencies: + ansi-regex "^4.1.0" + +strip-json-comments@^3.0.1: + version "3.0.1" + resolved "https://registry.yarnpkg.com/strip-json-comments/-/strip-json-comments-3.0.1.tgz#85713975a91fb87bf1b305cca77395e40d2a64a7" + integrity sha512-VTyMAUfdm047mwKl+u79WIdrZxtFtn+nBxHeb844XBQ9uMNTuTHdx2hc5RiAJYqwTj3wc/xe5HLSdJSkJ+WfZw== + +supports-color@^5.3.0: + version "5.5.0" + resolved "https://registry.yarnpkg.com/supports-color/-/supports-color-5.5.0.tgz#e2e69a44ac8772f78a1ec0b35b689df6530efc8f" + integrity sha512-QjVjwdXIt408MIiAqCX4oUKsgU2EqAGzs2Ppkm4aQYbjm+ZEWEcW4SfFNTr4uMNZma0ey4f5lgLrkB0aX0QMow== + dependencies: + has-flag "^3.0.0" + +supports-color@^6.1.0: + version "6.1.0" + resolved "https://registry.yarnpkg.com/supports-color/-/supports-color-6.1.0.tgz#0764abc69c63d5ac842dd4867e8d025e880df8f3" + integrity sha512-qe1jfm1Mg7Nq/NSh6XE24gPXROEVsWHxC1LIx//XNlD9iw7YZQGjZNjYN7xGaEG6iKdA8EtNFW6R0gjnVXp+wQ== + dependencies: + has-flag "^3.0.0" + +table@^5.2.3: + version "5.4.4" + resolved "https://registry.yarnpkg.com/table/-/table-5.4.4.tgz#6e0f88fdae3692793d1077fd172a4667afe986a6" + integrity sha512-IIfEAUx5QlODLblLrGTTLJA7Tk0iLSGBvgY8essPRVNGHAzThujww1YqHLs6h3HfTg55h++RzLHH5Xw/rfv+mg== + dependencies: + ajv "^6.10.2" + lodash "^4.17.14" + slice-ansi "^2.1.0" + string-width "^3.0.0" + +tape@4: + version "4.11.0" + resolved "https://registry.yarnpkg.com/tape/-/tape-4.11.0.tgz#63d41accd95e45a23a874473051c57fdbc58edc1" + integrity sha512-yixvDMX7q7JIs/omJSzSZrqulOV51EC9dK8dM0TzImTIkHWfe2/kFyL5v+d9C+SrCMaICk59ujsqFAVidDqDaA== + dependencies: + deep-equal "~1.0.1" + defined "~1.0.0" + for-each "~0.3.3" + function-bind "~1.1.1" + glob "~7.1.4" + has "~1.0.3" + inherits "~2.0.4" + minimist "~1.2.0" + object-inspect "~1.6.0" + resolve "~1.11.1" + resumer "~0.0.0" + string.prototype.trim "~1.1.2" + through "~2.3.8" + +terser@^4.1.0: + version "4.1.2" + resolved "https://registry.yarnpkg.com/terser/-/terser-4.1.2.tgz#b2656c8a506f7ce805a3f300a2ff48db022fa391" + integrity sha512-jvNoEQSPXJdssFwqPSgWjsOrb+ELoE+ILpHPKXC83tIxOlh2U75F1KuB2luLD/3a6/7K3Vw5pDn+hvu0C4AzSw== + dependencies: + commander "^2.20.0" + source-map "~0.6.1" + source-map-support "~0.5.12" + +text-table@^0.2.0: + version "0.2.0" + resolved "https://registry.yarnpkg.com/text-table/-/text-table-0.2.0.tgz#7f5ee823ae805207c00af2df4a84ec3fcfa570b4" + integrity sha1-f17oI66AUgfACvLfSoTsP8+lcLQ= + +through@^2.3.6, through@~2.3.4, through@~2.3.8: + version "2.3.8" + resolved "https://registry.yarnpkg.com/through/-/through-2.3.8.tgz#0dd4c9ffaabc357960b1b724115d7e0e86a2e1f5" + integrity sha1-DdTJ/6q8NXlgsbckEV1+Doai4fU= + +tmp@^0.0.33: + version "0.0.33" + resolved "https://registry.yarnpkg.com/tmp/-/tmp-0.0.33.tgz#6d34335889768d21b2bcda0aa277ced3b1bfadf9" + integrity sha512-jRCJlojKnZ3addtTOjdIqoRuPEKBvNXcGYqzO6zWZX8KfKEpnGY5jfggJQ3EjKuu8D4bJRr0y+cYJFmYbImXGw== + dependencies: + os-tmpdir "~1.0.2" + +tslib@^1.9.0: + version "1.10.0" + resolved "https://registry.yarnpkg.com/tslib/-/tslib-1.10.0.tgz#c3c19f95973fb0a62973fb09d90d961ee43e5c8a" + integrity sha512-qOebF53frne81cf0S9B41ByenJ3/IuH8yJKngAX35CmiZySA0khhkovshKK+jGCaMnVomla7gVlIcc3EvKPbTQ== + +type-check@~0.3.2: + version "0.3.2" + resolved "https://registry.yarnpkg.com/type-check/-/type-check-0.3.2.tgz#5884cab512cf1d355e3fb784f30804b2b520db72" + integrity sha1-WITKtRLPHTVeP7eE8wgEsrUg23I= + dependencies: + prelude-ls "~1.1.2" + +uri-js@^4.2.2: + version "4.2.2" + resolved "https://registry.yarnpkg.com/uri-js/-/uri-js-4.2.2.tgz#94c540e1ff772956e2299507c010aea6c8838eb0" + integrity sha512-KY9Frmirql91X2Qgjry0Wd4Y+YTdrdZheS8TFwvkbLWf/G5KNJDCh6pKL5OZctEW4+0Baa5idK2ZQuELRwPznQ== + dependencies: + punycode "^2.1.0" + +util-deprecate@~1.0.1: + version "1.0.2" + resolved "https://registry.yarnpkg.com/util-deprecate/-/util-deprecate-1.0.2.tgz#450d4dc9fa70de732762fbd2d4a28981419a0ccf" + integrity sha1-RQ1Nyfpw3nMnYvvS1KKJgUGaDM8= + +v8-compile-cache@^2.0.3: + version "2.0.3" + resolved "https://registry.yarnpkg.com/v8-compile-cache/-/v8-compile-cache-2.0.3.tgz#00f7494d2ae2b688cfe2899df6ed2c54bef91dbe" + integrity sha512-CNmdbwQMBjwr9Gsmohvm0pbL954tJrNzf6gWL3K+QMQf00PF7ERGrEiLgjuU3mKreLC2MeGhUsNV9ybTbLgd3w== + +which@^1.2.9: + version "1.3.1" + resolved "https://registry.yarnpkg.com/which/-/which-1.3.1.tgz#a45043d54f5805316da8d62f9f50918d3da70b0a" + integrity sha512-HxJdYWq1MTIQbJ3nw0cqssHoTNU267KlrDuGZ1WYlxDStUtKUhOaJmh112/TZmHxxUfuJqPXSOm7tDyas0OSIQ== + dependencies: + isexe "^2.0.0" + +wordwrap@~1.0.0: + version "1.0.0" + resolved "https://registry.yarnpkg.com/wordwrap/-/wordwrap-1.0.0.tgz#27584810891456a4171c8d0226441ade90cbcaeb" + integrity sha1-J1hIEIkUVqQXHI0CJkQa3pDLyus= + +wrappy@1: + version "1.0.2" + resolved "https://registry.yarnpkg.com/wrappy/-/wrappy-1.0.2.tgz#b5243d8f3ec1aa35f1364605bc0d1036e30ab69f" + integrity sha1-tSQ9jz7BqjXxNkYFvA0QNuMKtp8= + +write@1.0.3: + version "1.0.3" + resolved "https://registry.yarnpkg.com/write/-/write-1.0.3.tgz#0800e14523b923a387e415123c865616aae0f5c3" + integrity sha512-/lg70HAjtkUgWPVZhZcm+T4hkL8Zbtp1nFNOn3lRrxnlv50SRBv7cR7RqR+GMsd3hUXy9hWBo4CHTbFTcOYwig== + dependencies: + mkdirp "^0.5.1" -- cgit v1.2.3 From c75b740e34ba0bf08c9d986d04d517ddea701562 Mon Sep 17 00:00:00 2001 From: Pirate Praveen Date: Wed, 16 Dec 2020 09:53:46 +0100 Subject: Import node-d3-quadtree_1.0.7-2.debian.tar.xz [dgit import tarball node-d3-quadtree 1.0.7-2 node-d3-quadtree_1.0.7-2.debian.tar.xz] --- changelog | 66 +++++++++++++++++++++++++++++++++++++++++ clean | 1 + control | 33 +++++++++++++++++++++ copyright | 37 +++++++++++++++++++++++ docs | 1 + gbp.conf | 5 ++++ patches/reproducible_build.diff | 15 ++++++++++ patches/series | 1 + rules | 8 +++++ source/format | 1 + tests/pkg-js/test | 1 + upstream/metadata | 4 +++ watch | 5 ++++ 13 files changed, 178 insertions(+) create mode 100644 changelog create mode 100644 clean create mode 100644 control create mode 100644 copyright create mode 100644 docs create mode 100644 gbp.conf create mode 100644 patches/reproducible_build.diff create mode 100644 patches/series create mode 100755 rules create mode 100644 source/format create mode 100644 tests/pkg-js/test create mode 100644 upstream/metadata create mode 100644 watch diff --git a/changelog b/changelog new file mode 100644 index 0000000..5c954d4 --- /dev/null +++ b/changelog @@ -0,0 +1,66 @@ +node-d3-quadtree (1.0.7-2) unstable; urgency=medium + + [ Debian Janitor ] + * Apply multi-arch hints. + + node-d3-quadtree: Add Multi-Arch: foreign. + + [ Pirate Praveen ] + * Drop unused debian/webpack.config.js + * Use node-rollup-plugin-terser (now available in the archive) + * Bump Standards-Version to 4.5.1 (no changes needed) + * Add node-d3-array to !nocheck build profile + + -- Pirate Praveen Wed, 16 Dec 2020 14:23:46 +0530 + +node-d3-quadtree (1.0.7-1) unstable; urgency=medium + + * Team Upload + + [ Abraham Raji ] + * New upstream version 1.0.7 + * Use secure copyright file specification URI. + * Bump debhelper from old 11 to 12. + * Set debhelper-compat version in Build-Depends. + * Set upstream metadata fields: Bug-Database, Bug-Submit, Repository, + Repository-Browse. + * Update standards version to 4.4.1, no changes needed. + * Changed install path to /usr/share/ in debian/install + * Added no root required + * Bump Standard Version to 4.5.0 + + [ Xavier Guimard ] + * Add debian/gbp.conf + * Use pkg-js-tools auto install + + -- Abraham Raji Sun, 29 Mar 2020 23:10:05 +0000 + +node-d3-quadtree (1.0.6-2) unstable; urgency=medium + + * Reupload to unstable + * Make build reproducible + * Bump Standards-Version to 4.4.0 (no changes needed) + + -- Pirate Praveen Mon, 08 Jul 2019 15:07:38 +0530 + +node-d3-quadtree (1.0.6-1) experimental; urgency=medium + + * New upstream version 1.0.6 + * Bump debhelper compatibility level to 11 + * Bump Standards-Version to 4.3.0 (no changes needed) + * Use salsa.debian.org in Vcs-* fields + * Switch to rollup from webpack (rollup is in main now) + * Switch to pkg-js-tools for tests + + -- Pirate Praveen Wed, 19 Jun 2019 19:41:55 +0530 + +node-d3-quadtree (1.0.3-2) unstable; urgency=medium + + * Use webpack to build umd module like upstream + + -- Pirate Praveen Sat, 06 Jan 2018 14:37:32 +0530 + +node-d3-quadtree (1.0.3-1) unstable; urgency=low + + * Initial release (Closes: #877619) + + -- Pirate Praveen Tue, 03 Oct 2017 19:44:15 +0530 diff --git a/clean b/clean new file mode 100644 index 0000000..a261f29 --- /dev/null +++ b/clean @@ -0,0 +1 @@ +dist/* diff --git a/control b/control new file mode 100644 index 0000000..b443d9a --- /dev/null +++ b/control @@ -0,0 +1,33 @@ +Source: node-d3-quadtree +Section: javascript +Priority: optional +Maintainer: Debian Javascript Maintainers +Uploaders: Pirate Praveen +Build-Depends: debhelper-compat (= 12) + , node-d3-array + , node-tape + , pkg-js-tools (>= 0.9.20~) + , rollup + , node-rollup-plugin-terser +Standards-Version: 4.5.1 +Vcs-Browser: https://salsa.debian.org/js-team/node-d3-quadtree +Vcs-Git: https://salsa.debian.org/js-team/node-d3-quadtree.git +Homepage: https://d3js.org/d3-quadtree/ +Testsuite: autopkgtest-pkg-nodejs +Rules-Requires-Root: no + +Package: node-d3-quadtree +Architecture: all +Depends: ${misc:Depends} + , nodejs +Multi-Arch: foreign +Description: Two-dimensional recursive spatial subdivision + A quadtree recursively partitions two-dimensional space into squares, dividing + each square into four equally-sized squares. Each distinct point exists in a + unique leaf node; coincident points are represented by a linked list. + . + Quadtrees can accelerate various spatial operations, such as the Barnes–Hut + approximation for computing many-body forces, collision detection, and + searching for nearby points. + . + Node.js is an event-based server-side JavaScript engine. diff --git a/copyright b/copyright new file mode 100644 index 0000000..9cd63d0 --- /dev/null +++ b/copyright @@ -0,0 +1,37 @@ +Format: https://www.debian.org/doc/packaging-manuals/copyright-format/1.0/ +Upstream-Name: d3-quadtree +Upstream-Contact: https://github.com/d3/d3-quadtree/issues +Source: https://d3js.org/d3-quadtree/ + +Files: * +Copyright: 2010-2016 Mike Bostock (http://bost.ocks.org/mike) +License: BSD-3-Clause + +Files: debian/* +Copyright: 2017 Pirate Praveen +License: BSD-3-Clause + +License: BSD-3-clause + Redistribution and use in source and binary forms, with or without + modification, are permitted provided that the following conditions + are met: + 1. Redistributions of source code must retain the above copyright + notice, this list of conditions and the following disclaimer. + 2. Redistributions in binary form must reproduce the above copyright + notice, this list of conditions and the following disclaimer in the + documentation and/or other materials provided with the distribution. + 3. Neither the name of the University nor the names of its contributors + may be used to endorse or promote products derived from this software + without specific prior written permission. + . + THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE HOLDERS OR + CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, + EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, + PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR + PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF + LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING + NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS + SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. diff --git a/docs b/docs new file mode 100644 index 0000000..b43bf86 --- /dev/null +++ b/docs @@ -0,0 +1 @@ +README.md diff --git a/gbp.conf b/gbp.conf new file mode 100644 index 0000000..b713356 --- /dev/null +++ b/gbp.conf @@ -0,0 +1,5 @@ +[DEFAULT] +pristine-tar = True + +[import-orig] +filter = [ '.gitignore', '.travis.yml', '.git*' ] diff --git a/patches/reproducible_build.diff b/patches/reproducible_build.diff new file mode 100644 index 0000000..2f690be --- /dev/null +++ b/patches/reproducible_build.diff @@ -0,0 +1,15 @@ +Description: Make the build reproducible +Author: Chris Lamb +Last-Update: 2019-06-20 + +--- a/rollup.config.js ++++ b/rollup.config.js +@@ -10,7 +10,7 @@ + format: "umd", + indent: false, + extend: true, +- banner: `// ${meta.homepage} v${meta.version} Copyright ${(new Date).getFullYear()} ${meta.author.name}`, ++ banner: `// ${meta.homepage} v${meta.version} Copyright ${(new Date(process.env.SOURCE_DATE_EPOCH ? (process.env.SOURCE_DATE_EPOCH * 1000) : new Date().getTime())).getFullYear()} ${meta.author.name}`, + globals: Object.assign({}, ...Object.keys(meta.dependencies || {}).filter(key => /^d3-/.test(key)).map(key => ({[key]: "d3"}))) + }, + plugins: [] diff --git a/patches/series b/patches/series new file mode 100644 index 0000000..774a9a2 --- /dev/null +++ b/patches/series @@ -0,0 +1 @@ +reproducible_build.diff diff --git a/rules b/rules new file mode 100755 index 0000000..65b73e2 --- /dev/null +++ b/rules @@ -0,0 +1,8 @@ +#!/usr/bin/make -f +# -*- makefile -*- + +%: + dh $@ --with nodejs + +override_dh_auto_build: + rollup -c diff --git a/source/format b/source/format new file mode 100644 index 0000000..163aaf8 --- /dev/null +++ b/source/format @@ -0,0 +1 @@ +3.0 (quilt) diff --git a/tests/pkg-js/test b/tests/pkg-js/test new file mode 100644 index 0000000..305491f --- /dev/null +++ b/tests/pkg-js/test @@ -0,0 +1 @@ +tape 'test/**/*-test.js' diff --git a/upstream/metadata b/upstream/metadata new file mode 100644 index 0000000..a001f9f --- /dev/null +++ b/upstream/metadata @@ -0,0 +1,4 @@ +Bug-Database: https://github.com/d3/d3-quadtree/issues +Bug-Submit: https://github.com/d3/d3-quadtree/issues/new +Repository: https://github.com/d3/d3-quadtree.git +Repository-Browse: https://github.com/d3/d3-quadtree diff --git a/watch b/watch new file mode 100644 index 0000000..08168ea --- /dev/null +++ b/watch @@ -0,0 +1,5 @@ +version=3 +opts=\ +dversionmangle=s/\+(debian|dfsg|ds|deb)(\.\d+)?$//,\ +filenamemangle=s/.*\/v?([\d\.-]+)\.tar\.gz/node-d3-quadtree-$1.tar.gz/ \ + https://github.com/d3/d3-quadtree/tags .*/archive/v?([\d\.]+).tar.gz -- cgit v1.2.3 From d5dd3ed6420a12d6c58e30fedfac53f12c989757 Mon Sep 17 00:00:00 2001 From: Chris Lamb Date: Wed, 16 Dec 2020 09:53:46 +0100 Subject: Make the build reproducible Last-Update: 2019-06-20 Gbp-Pq: Name reproducible_build.diff --- rollup.config.js | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/rollup.config.js b/rollup.config.js index 804bba8..e751e8d 100644 --- a/rollup.config.js +++ b/rollup.config.js @@ -10,7 +10,7 @@ const config = { format: "umd", indent: false, extend: true, - banner: `// ${meta.homepage} v${meta.version} Copyright ${(new Date).getFullYear()} ${meta.author.name}`, + banner: `// ${meta.homepage} v${meta.version} Copyright ${(new Date(process.env.SOURCE_DATE_EPOCH ? (process.env.SOURCE_DATE_EPOCH * 1000) : new Date().getTime())).getFullYear()} ${meta.author.name}`, globals: Object.assign({}, ...Object.keys(meta.dependencies || {}).filter(key => /^d3-/.test(key)).map(key => ({[key]: "d3"}))) }, plugins: [] -- cgit v1.2.3