Sign Up for Free

RunKit +

Try any Node.js package right in your browser

This is a playground to test code. It runs a full Node.js environment and already has all of npm’s 400,000 packages pre-installed, including ancestor-of with all npm packages installed. Try it out:

var ancestorOf = require("ancestor-of")

This service is provided by RunKit and is not affiliated with npm, Inc or the package authors.

ancestor-of v1.0.0

Test if a node is an ancestor of another node in a tree

ancestor-of

Preprocess a tree (encoded as a JSON object) so that given any two nodes in the tree it is possible to determine whether one is the ancestor of the other. Ancestor queries take O(1) time, and the data structure requres O(n) space and preprocessing time.

Example

var preprocess = require("ancestor-of")

//Construct some tree
var tree = {
  a: {
    x: {},
    y: {}
  },
  b: [ [], [[]] ]
}

//Construct ancestorOf data structure
var ancestorOf = preprocess(tree)

//Now we can check ancestor relations on elements of tree:
var assert = require("assert")

assert.ok(ancestorOf(tree.a, tree.a.x))
assert.ok(!ancestorOf(tree.a.ax, tree.a))
assert.ok(!ancestorOf(tree.b, tree.a))
assert.ok(ancestorOf(tree.b, tree.b[1][0]))

Install

npm install ancestor-of

API

var ancestorOf = require("ancestor-of")(tree[,childrenOf(node)])

Preprocesses tree to answer ancestor queries.

  • tree is the root of a JSON object tree

  • childrenOf(node) is an optional function which returns an array of children of node

    • node is the subtree node

    childrenOf should return an array of all possible children of node

Returns A query which answers ancestor queries

ancestorOf(a,b)

Determine if b is an ancestor of a

  • a is the first node
  • b is the node which is tested to be ancestor of a

Returns true if b is an ancestor of a, otherwise false

ancestorOf.rebuild()

Rebuild the data structure if some of the children of tree have changed.

Credits

(c) 2014 Mikola Lysenko. MIT License

RunKit is a free, in-browser JavaScript dev environment for prototyping Node.js code, with every npm package installed. Sign up to share your code.
Sign Up for Free