{"_id":"paul","_rev":"344571","name":"paul","description":"tree traversal and transform functions","dist-tags":{"latest":"0.0.3"},"maintainers":[{"name":"andrejewski","email":"christopher.andrejewski@gmail.com"}],"time":{"modified":"2021-06-20T02:32:19.000Z","created":"2015-05-21T00:09:13.647Z","0.0.3":"2015-06-07T03:30:50.388Z","0.0.2":"2015-05-25T14:32:04.006Z","0.0.1":"2015-05-21T00:09:13.647Z"},"users":{},"author":{"name":"Chris Andrejewski","email":"christopher.andrejewski@gmail.com"},"repository":{"type":"git","url":"https://github.com/andrejewski/paul.git"},"versions":{"0.0.3":{"name":"paul","version":"0.0.3","description":"tree traversal and transform functions","main":"index.js","directories":{"test":"test"},"scripts":{"test":"mocha"},"repository":{"type":"git","url":"https://github.com/andrejewski/paul.git"},"keywords":["tree","node","ast","walk","traversal"],"author":{"name":"Chris Andrejewski","email":"christopher.andrejewski@gmail.com"},"license":"ISC","bugs":{"url":"https://github.com/andrejewski/paul/issues"},"homepage":"https://github.com/andrejewski/paul","devDependencies":{"mocha":"^2.2.5"},"gitHead":"b4e039543ba9d1c1db77ac8b48922b31c2c28ac6","_id":"paul@0.0.3","_shasum":"7fbef33df6936c050cb7e9c00c22cbd110b7bb4f","_from":".","_npmVersion":"1.4.28","_npmUser":{"name":"andrejewski","email":"chrisishereladies@gmail.com"},"maintainers":[{"name":"andrejewski","email":"christopher.andrejewski@gmail.com"}],"dist":{"shasum":"7fbef33df6936c050cb7e9c00c22cbd110b7bb4f","size":8881,"noattachment":false,"key":"/paul/-/paul-0.0.3.tgz","tarball":"http://registry.cnpm.dingdandao.com/paul/download/paul-0.0.3.tgz"},"publish_time":1433647850388,"_cnpm_publish_time":1433647850388,"_hasShrinkwrap":false},"0.0.2":{"name":"paul","version":"0.0.2","description":"tree traversal and transform functions","main":"index.js","directories":{"test":"test"},"scripts":{"test":"mocha"},"repository":{"type":"git","url":"https://github.com/andrejewski/paul.git"},"keywords":["tree","node","ast","walk","traversal"],"author":{"name":"Chris Andrejewski","email":"christopher.andrejewski@gmail.com"},"license":"ISC","bugs":{"url":"https://github.com/andrejewski/paul/issues"},"homepage":"https://github.com/andrejewski/paul","devDependencies":{"mocha":"^2.2.5"},"gitHead":"82dbeed420b331185ec52e61d3fb821675d9fd46","_id":"paul@0.0.2","_shasum":"157d39ecb93a5413ac35ccefd75b1518a1b96223","_from":".","_npmVersion":"1.4.28","_npmUser":{"name":"andrejewski","email":"chrisishereladies@gmail.com"},"maintainers":[{"name":"andrejewski","email":"christopher.andrejewski@gmail.com"}],"dist":{"shasum":"157d39ecb93a5413ac35ccefd75b1518a1b96223","size":8526,"noattachment":false,"key":"/paul/-/paul-0.0.2.tgz","tarball":"http://registry.cnpm.dingdandao.com/paul/download/paul-0.0.2.tgz"},"publish_time":1432564324006,"_cnpm_publish_time":1432564324006,"_hasShrinkwrap":false},"0.0.1":{"name":"paul","version":"0.0.1","description":"tree traversal and transform functions","main":"index.js","directories":{"test":"test"},"scripts":{"test":"mocha"},"repository":{"type":"git","url":"https://github.com/andrejewski/paul.git"},"keywords":["tree","node","ast","walk","traversal"],"author":{"name":"Chris Andrejewski","email":"christopher.andrejewski@gmail.com"},"license":"ISC","bugs":{"url":"https://github.com/andrejewski/paul/issues"},"homepage":"https://github.com/andrejewski/paul","devDependencies":{"mocha":"^2.2.5"},"gitHead":"e500386ede3ba3d7824ffc89b042c3ed8cee8c11","_id":"paul@0.0.1","_shasum":"2e5eac21b18cf8537fd8731f78176557b8b93714","_from":".","_npmVersion":"1.4.28","_npmUser":{"name":"andrejewski","email":"chrisishereladies@gmail.com"},"maintainers":[{"name":"andrejewski","email":"christopher.andrejewski@gmail.com"}],"dist":{"shasum":"2e5eac21b18cf8537fd8731f78176557b8b93714","size":7429,"noattachment":false,"key":"/paul/-/paul-0.0.1.tgz","tarball":"http://registry.cnpm.dingdandao.com/paul/download/paul-0.0.1.tgz"},"publish_time":1432166953647,"_cnpm_publish_time":1432166953647,"_hasShrinkwrap":false}},"readme":"# Paul\n\nPaul is a library of functions for working with tree data structures such as abstract syntax trees, binary trees, and other nested data structures.\n\n```bash\nnpm install paul # hey, that rhymes\n```\n\n## Usage\n\n```js\nvar Paul = require('paul');\nvar Walker = new Paul(['children']);\n\nvar tree = {\n\tvalue: 10,\n\tchildren: [{\n\t\tvalue: 6\n\t}, {\n\t\tvalue: 4\n\t}]\n};\n\nvar sum = Walker.depthReduce(tree, function(num, node) {\n\treturn num + node.value;\n}, 0);\n\nrequire('assert').equal(20, sum);\n```\n\n## Documentation\n\n- [`Paul(walkFn)`](https://github.com/andrejewski/paul#paulwalkfn)\n\t- [`walker(walkFn) func`](https://github.com/andrejewski/paul#walkerwalkfn-func)\n\t- [`walk(tree, walkFn)`](https://github.com/andrejewski/paul#walktree-walkfn)\n\t- `prototype`\n\t\t- [`map(tree, transform) tree`](https://github.com/andrejewski/paul#maptree-transform-tree)\n\t\t- [`filter(tree, predicate) tree`](https://github.com/andrejewski/paul#filtertree-predicate-tree)\n\t\t- [`where(tree, properties) tree`](https://github.com/andrejewski/paul#wheretree-properties-tree)\n\t\t- [`iterator(tree) Iterator`](https://github.com/andrejewski/paul#iteratortree-iterator)\n\t\t- [`forEach(tree, iteratee)`](https://github.com/andrejewski/paul#foreachtree-iteratee)\n\t\t- [`find(tree, predicate) node`](https://github.com/andrejewski/paul#findtree-predicate-node)\n\t\t- [`findWhere(tree, properties) node`](https://github.com/andrejewski/paul#findwheretree-properties-node)\n\t\t- [`reduce(tree, iteratee, [memo]) memo`](https://github.com/andrejewski/paul#reducetree-iteratee-memo-memo)\n\t\t- [`parent(tree, node) parentNode`](https://github.com/andrejewski/paul#parenttree-node-parentnode)\n\t\t- [`siblings(tree, node) {left, right}`](https://github.com/andrejewski/paul#siblingstree-node-left-right)\n\n**Note:** Methods `iterator()` through `siblings()` are not actual methods and instead there are two methods that differ solely on traversal method. For instance, `find()` must be called as either `depthFind()` or `breadthFind()`. An [explanation](http://stackoverflow.com/a/687752/1444710) of the difference between these traversals may be helpful.\n\nAssume all code examples are preceded by the following:\n\n```js\nvar Paul = require('paul');\nvar assert = require('assert');\n```\n\n===\n\n### Paul(walkFn)\n\nAn instance of Paul will have all of the prototype functions listed above. See `walker(walkFn)` for a description of a valid walking function.\n\n*Note:* the `new` keyword is optional but recommended.\n\n===\n\n### walker(walkFn) func\n\nThe function `walker` takes a walking function and returns a function to be used on a node to return its children.\n\nWhat makes Paul useful is this function. Supply `walker` a walking function with the signature `function(node, walk)`, which decides how a node's children are walked or ignored.\n\nSay you have an AST where you could have one or more child nodes on the properties `left`, `right`, and/or `children` for any given node. The appropriate walk function would be:\n\n```js\nfunction walkFn(node, walk) {\n\tif(node.left) walk('left');\n\tif(node.right) walk('right');\n\tif(node.children) walk('children');\n}\nvar walker1 = Paul.walker(walkFn);\n```\n\nPaul walks through the given tree node-by-node with your walk function until no more child nodes are found and the walking ends.\n\nIf an AST has a lot of properties that could have child nodes values, `walker` also accepts an array of property keys.\n\n```js\nvar walker2 = Paul.walker(['left', 'right', 'children']);\n// walker 2 does the same as walker 1.\n```\n\n===\n\n### walk(tree, walkFn)\n\nTakes a `tree` and a function that accepts a `node` and `walk(node)` callback.\n\nThis function is not a method of an instance of Paul for the simple reason that you walk the nodes yourself.\n\nAll this function does is pass the given function `walkFn` the `node` to be processed and the function `walk` and return the value computed by the `walkFn`. \n\nConfused? An example will help us both honestly.\n\n```js\nvar tree = {\n\top: '+',\n\tleft: {value: 8},\n\tright: {\n\t\top: '/',\n\t\tleft: {value: 20},\n\t\tright: {value: 4}\n\t}\n};\n\nvar math = Paul.walk(tree, function(node, walk) {\n\tif(node.op) {\n\t\treturn '(' + walk(node.left) + node.op + walk(node.right) + ')';\n\t}\n\treturn node.value;\n});\n\nassert.equal(math, '(8+(20/4))');\n```\n\nIf only the `walkFn` is provided, the function will return a generic function to call on any `tree`.\n\n===\n\n### map(tree, transform) tree\n\nProduces a new tree of nodes by mapping each node in **tree** through a transformation function **transform**. The function is passed one argument `node`.\n\n```js\nvar pine = {id: \"A\", kids: [{id: \"B\"}, {id: \"C\"}]};\nvar paul = new Paul(['kids']);\n\nvar palm = paul.map(pine, function(node) {\n\tnode.id += node.id;\n\treturn node;\n});\n\nvar tree = {id: \"AA\", kids: [{id: \"BB\"}, {id: \"CC\"}]};\nassert.deepEqual(palm, tree);\n```\n\n===\n\n### filter(tree, predicate) tree\n\nLooks through each node in the **tree**, returning a tree of all the nodes that pass a truth test **predicate**. Any nodes that fail the truth test and their sub-nodes will be removed. Sub-nodes will not be tested if the parent node fails.\n\n```js\nvar pine = {id: \"A\", kids: [{id: \"B\"}, {id: \"C\"}]};\nvar paul = new Paul(['kids']);\n\nvar palm = paul.filter(pine, function(node) {\n\treturn node.id === \"A\";\n});\n\nvar tree = {id: \"A\", kids: []};\nassert.deepEqual(palm, tree);\n```\n\n===\n\n### where(tree, properties) tree\n\nLooks through each node in the **tree**, returning a tree of all the nodes that contain all of the key-value pairs listed in **properties**. Any nodes that fail the truth test and their sub-nodes will be removed. Sub-nodes will not be tested if the parent node fails.\n\n```js\nvar pine = {id: \"A\", kids: [{id: \"B\"}, {id: \"C\"}]};\nvar paul = new Paul(['kids']);\n\nvar palm = paul.where(pine, {id: \"A\"});\n\nvar tree = {id: \"A\", kids: []};\nassert.deepEqual(palm, tree);\n```\n\n===\n\n### iterator(tree) Iterator\n\nReturns an iterator that returns each node in the tree in the specified traversal order. \n\n- `depthIterator(tree) Iterator`: depth-first\n- `breadthIterator(tree) Iterator`: breadth-first\n\nAn [explanation](http://stackoverflow.com/a/687752/1444710) of the difference between these traversals may be helpful.\n\nEach `next()` call on the returned iterator returns an object containing a boolean `done` which is true when there are no more nodes to iterator over and `value` which is the node. This conforms to the ES6 [Iterator protocol](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Iteration_protocols).\n\n```js\nvar tree = {id: \"A\", kids: [{id: \"B\"}, {id: \"C\"}]};\nvar paul = new Paul(['kids']);\n\nvar text = \"\";\nvar iter = paul.depthIterator(tree);\n\nwhile(true) {\n\tvar res = iter.next();\n\tif(res.done) break;\n\ttext += node.id;\n}\n\nassert.equal(text, \"ABC\");\n```\n\n===\n\n### forEach(tree, iteratee)\n\nIterates over a **tree**, yielding each node in turn to an **iteratee** function. Each invocation of iteratee is called with one argument `node`. Iteration order is decided by which method is used.\n\n- `depthForEach(tree, iteratee)`: depth-first\n- `breadthForEach(tree, iteratee)`: breadth-first\n\n```js\nvar tree = {id: \"A\", kids: [{id: \"B\"}, {id: \"C\"}]};\nvar paul = new Paul(['kids']);\n\nvar text = \"\";\npaul.depthForEach(tree, function(node) {\n\ttext += node.id;\n});\n\nassert.equal(text, \"ABC\");\n```\n\n===\n\n### find(tree, predicate) node\n\nLooks through each node in the **tree**, returning the first one that passes a truth test **predicate**, or `undefined` if no node passes the test. The function returns as soon as it finds an acceptable node, and doesn't traverse the entire tree.\n\n- `depthFind(tree, predicate)`: depth-first\n- `breadthFind(tree, predicate)`: breadth-first\n\n```js\nvar tree = {id: \"A\", kids: [{id: \"B\"}, {id: \"C\"}]};\nvar paul = new Paul(['kids']);\n\nvar node = paul.depthFind(tree, function(node) {\n\treturn node.id === \"B\";\n});\n\nassert.deepEqual(node, {id: \"B\"});\n```\n\n===\n\n### findWhere(tree, properties) node\n\nLooks through each node in the **tree**, returning the first node that contains all of the key-value pairs listed in **properties**, or `undefined` if no node passes the test. The function returns as soon as it finds an acceptable node, and doesn't traverse the entire tree.\n\n- `depthFindWhere(tree, properties)`: depth-first\n- `breadthFindWhere(tree, properties)`: breadth-first\n\n```js\nvar tree = {id: \"A\", kids: [{id: \"B\"}, {id: \"C\"}]};\nvar paul = new Paul(['kids']);\n\nvar node = paul.depthFindWhere(tree, {id: \"B\"}});\n\nassert.deepEqual(node, {id: \"B\"});\n```\n\n===\n\n### reduce(tree, iteratee, [memo]) memo\n\nAlso known as inject and foldl, reduce boils down a **tree** of nodes into a single value. **Memo** is the initial state of the reduction, and each successive step of it should be returned by **iteratee**. The iteratee is passed two arguments: the memo, then the node.\n\nIf no memo is passed to the initial invocation of reduce, the iteratee is not invoked on the root node of the tree. The root node is instead passed as the memo in the invocation of the iteratee on the next node in the tree.\n\n- `depthReduce(tree, iteratee, [memo])`: depth-first\n- `breadthReduce(tree, iteratee, [memo])`: breadth-first\n\n```js\nvar tree = {id: \"A\", kids: [{id: \"B\"}, {id: \"C\"}]};\nvar paul = new Paul(['kids']);\n\nvar text = paul.depthReduce(tree, function(str, node) {\n\treturn str + node.id;\n}, \"\");\n\nassert.equal(text, \"ABC\");\n```\n\n===\n\n### parent(tree, node) parentNode\n\nReturns the parent node of the given **node**. If the node is not found in the **tree** or the node has no parent (meaning the node is the tree), `undefined` is returned. \n\n- `depthParent(tree, node) parentNode`: depth-first\n- `breadthParent(tree, node) parentNode`: breadth-first\n\n```js\nvar tree = {id: \"A\", kids: [{id: \"B\"}, {id: \"C\"}]};\nvar paul = new Paul(['kids']);\n\nvar nodeB = tree.kids[0];\nvar parentOfB = paul.depthParent(tree, nodeB);\n\nassert.equal(tree, parentOfB);\n```\n\n===\n\n### siblings(tree, node) {left, right}\n\nReturns the sibling nodes of the given **node**. If the node is not found in the **tree** or the node has no parent (meaning the node is the tree), `undefined` is returned. Also if the node is not in an Array member (i.e `{child: node}`), the node cannot have any siblings and thus `undefined` is returned.\n\nSiblings of a node are returned in an object containing two properties `left` and `right`. Siblings that come before the given node are placed in the `left` property. Siblings that come after the given node are placed in the `right` property.\n\n- `depthSiblings(tree, node) {left, right}`: depth-first\n- `breadthSiblings(tree, node) {left, right}`: breadth-first\n\n```js\nvar tree = {id: \"A\", kids: [{id: \"B\"}, {id: \"C\"}, {id: \"D\"}]};\nvar paul = new Paul(['kids']);\n\nvar nodeC = tree.kids[1];\nvar siblings = paul.depthSiblings(tree, nodeC);\n\nassert.deepEqual(siblings, {\n\tleft: [{id: \"B\"}],\n\tright: [{id: \"D\"}]\n});\n```\n\n## Why \"Paul\"?\n\nI have a history of naming awesome libraries after awesome people I know with [four](https://github.com/andrejewski/reem) [letter](https://github.com/andrejewski/matt) [names](https://github.com/andrejewski/seth). I need this library for further work with my HTML parser project [Himalaya](https://github.com/andrejewski/himalaya). Also, have you ever seen [The Fast and the Furious](http://en.wikipedia.org/wiki/The_Fast_and_the_Furious)? \n\nYes, this project is dedicated to [Paul Walker](http://en.wikipedia.org/wiki/Paul_Walker).\n\n## Contributing\n\nWe can always have more tests: if you find a bug, create an issue or be **fabulous** and fix the problem and write the tests up yourself in a coherent pull request. Same goes for documentation: typo fixes and clearer function descriptions are appreciated.\n\nRun tests with the `npm test` command.\n\nFollow me on [Twitter](https://twitter.com/compooter) for updates or just for the lolz and please check out my other [repositories](https://github.com/andrejewski) if I have earned it. I thank you for reading.\n\n","_attachments":{},"homepage":"https://github.com/andrejewski/paul","bugs":{"url":"https://github.com/andrejewski/paul/issues"},"license":"ISC"}