hierarchy-closure - npm Package Compare versions

Comparing version 1.1.0 to 1.2.0

hierarchy-closure.js

 var HierarchyClosure = (function () {
-  /**
-   * @@ should be its own package
+  /** create a hierarchy object
+   * This object keeps track of direct children and parents as well as transitive children and parents.
    */
@@ -12,4 +12,5 @@ function makeHierarchy () {
       add: function (parent, child) {
-        if (parent in children && children[parent].indexOf(child) !== -1) {
-          // already seen
+        if (parent === child || // skip add(A, A)
+            // test if this is a novel entry.
+            (parent in children && children[parent].indexOf(child) !== -1)) {
           return
@@ -23,5 +24,3 @@ }
         target[child] = value
-        if (child in roots) {
-          delete roots[child]
-        }
+        delete roots[child]
 
@@ -38,5 +37,9 @@ // // maintain hierarchy (direct and confusing)
         function updateClosure (container, members, near, far) {
-          container[far] = container[far].concat(near, container[near])
+          container[far] = container[far].filter(
+            e => /* e !== near && */ container[near].indexOf(e) === -1
+          ).concat(container[near].indexOf(near) === -1 ? [near] : [], container[near])
           container[near].forEach(
-            n => (members[n] = members[n].concat(far, members[far]))
+            n => (members[n] = members[n].filter(
+              e => e !== far && members[far].indexOf(e) === -1
+            ).concat(members[far].indexOf(far) === -1 ? [far] : [], members[far]))
           )
@@ -60,6 +63,6 @@ }
 
-  function walkHierarchy (n, f, p) {
+  function depthFirst (n, f, p) {
     return Object.keys(n).reduce((ret, k) => {
       return ret.concat(
-        walkHierarchy(n[k], f, k),
+        depthFirst(n[k], f, k),
         p ? f(k, p) : []) // outer invocation can have null parent
@@ -69,7 +72,8 @@ }, [])
 
-  return { create: makeHierarchy, walk: walkHierarchy }
+  return { create: makeHierarchy, depthFirst }
 })()
 
+/* istanbul ignore next */
 if (typeof require !== 'undefined' && typeof exports !== 'undefined') {
   module.exports = HierarchyClosure
 }

package.json

 {
   "name": "hierarchy-closure",
-  "version": "1.1.0",
+  "version": "1.2.0",
   "description": "keep closure of parents and children in hierarchy",
@@ -9,3 +9,3 @@ "main": "hierarchy-closure.js",
     "coverage:report": "cat ./coverage/lcov.info | coveralls",
-    "test": "standard && jest --coverage",
+    "test": "standard hierarchy-closure.js && jest --coverage",
     "travis-deploy-once": "travis-deploy-once",
@@ -26,8 +26,8 @@ "semantic-release": "semantic-release"
   "devDependencies": {
-    "coveralls": "^3.0.2",
-    "install": "^0.12.1",
-    "jest": "^23.4.1",
-    "semantic-release": "^15.8.1",
-    "standard": "^11.0.1",
-    "travis-deploy-once": "^5.0.1"
+    "coveralls": "^3.0.4",
+    "install": "^0.12.2",
+    "jest": "^24.8.0",
+    "semantic-release": "^15.13.18",
+    "standard": "^12.0.1",
+    "travis-deploy-once": "^5.0.11"
   },
@@ -34,0 +34,0 @@ "standard": {

README.md

@@ -15,31 +15,48 @@ [![NPM Version](https://badge.fury.io/js/hierarchy-closure.png)](https://npmjs.org/package/hierarchy-closure)
 
-## use
+## create ()
 
+This constructs a hierarchy.
+
 ``` javascript
 // create hierarchy
-t = Hierarchy.create()
+myHierarchy = Hierarchy.create()
+```
+
+## add (parent, child)
+
+Adding parent/child pairs builds a structure called `myHierarchy.roots` with the trees of added parent/child pairs.
+It also creates two closures:
+- *parents*: a mapping from child to its list of parents.
+- *children*: a mapping from parent to its list of children.
+
+### No order dependence
+
+You can fill in your tree in any order and get the same closures:
+
+``` javascript
+// populating myHierarchy created above...
 // add single entry B->C
-t.add('B', 'C')
+myHierarchy.add('B', 'C')
 // add single entry B->C
-t.add('B', 'C')
+myHierarchy.add('B', 'C')
 // add child C->D
-t.add('C', 'D')
+myHierarchy.add('C', 'D')
 // add disconnected entry F->G
-t.add('F', 'G')
+myHierarchy.add('F', 'G')
 // add parent E->F
-t.add('E', 'F')
+myHierarchy.add('E', 'F')
 // add middle D->E
-t.add('D', 'E')
+myHierarchy.add('D', 'E')
 // add top A->B
-t.add('A', 'B')
+myHierarchy.add('A', 'B')
 // add bottom G->H
-t.add('G', 'H')
+myHierarchy.add('G', 'H')
 // add redundant entry (no effect)
-t.add('A', 'B')
+myHierarchy.add('A', 'B')
 ```
 
-## results
+### add Exanple Results
 
 ``` javascript
-{ add: t.add,
+{ add: myHierarchy.add,
   roots: {A: {B: {C: {D: {E: {F: {G: {H: {}}}}}}}}},
@@ -68,1 +85,37 @@ parents: {
 ```
+
+## depthFirst (root, (parent, child) => { ... })
+
+This calls you callback function with parent/child pairs starting with any children:
+
+``` javascript
+// create hierarchy
+h2 = Hierarchy.create()
+h2.add('A', 'AB1')
+h2.add('AB1', 'AB1C1')
+h2.add('AB1C1', 'AB1C1D1')
+h2.add('AB1C1', 'AB1C1D2')
+h2.add('AB1', 'AB1C2')
+h2.add('AB1C2', 'AB1C2D1')
+h2.add('A', 'AB2')
+h2.add('AB2', 'AB2C1')
+h2.add('AB2C1', 'AB2C1D1')
+const seen = []
+Hierarchy.depthFirst(t.roots, (l, r) => seen.push([l, r]))
+```
+
+### depthFirst Example Results
+
+``` JSON
+[
+  [ 'AB1C1D1', 'AB1C1' ],
+  [ 'AB1C1D2', 'AB1C1' ],
+  [ 'AB1C1', 'AB1' ],
+  [ 'AB1C2D1', 'AB1C2' ],
+  [ 'AB1C2', 'AB1' ],
+  [ 'AB1', 'A' ],
+  [ 'AB2C1D1', 'AB2C1' ],
+  [ 'AB2C1', 'AB2' ],
+  [ 'AB2', 'A' ]
+]
+```

test/hierarchy-test.js

 const Hierarchy = require('../hierarchy-closure')
 
-describe('hierarchy-closure', function () {
+describe('linear series', function () {
   let t// = Hierarchy.create()
@@ -75,1 +75,86 @@ it('create hierarchy', function () {
 })
+
+describe('multiple children', function () {
+  let t = Hierarchy.create()
+  expect(t).toEqual(
+    { add: t.add,
+      roots: {},
+      parents: {},
+      children: {}})
+  it('add doube entry A->{B,C}', function () {
+    t.add('A', 'B')
+    t.add('A', 'C')
+    expect(t).toEqual(
+      { add: t.add,
+        roots: {A: {B: {}, C: {}}},
+        parents: {A: [], B: ['A'], C: ['A']},
+        children: {A: ['B', 'C'], B: [], C: []}})
+  })
+})
+
+describe('repeated insertions', function () {
+  let t = Hierarchy.create()
+  expect(t).toEqual(
+    { add: t.add,
+      roots: {},
+      parents: {},
+      children: {}})
+  it('add doube entry B->C', function () {
+    t.add('B', 'C')
+    t.add('B', 'C')
+    expect(t).toEqual(
+      { add: t.add,
+        roots: {B: {C: {}}},
+        parents: {B: [], C: ['B']},
+        children: {B: ['C'], C: []}})
+  })
+  it('add indirect doube entry C->D, B->D', function () {
+    t.add('C', 'D')
+    t.add('B', 'D')
+    expect(t).toEqual(
+      { add: t.add,
+        roots: {B: {C: {D: {}}}},
+        parents: {B: [], C: ['B'], D: ['C', 'B']},
+        children: {B: ['C', 'D'], C: ['D'], D: []}})
+  })
+  it('add indirect doube entry C->D, B->D', function () {
+    t.add('A', 'D')
+    t.add('A', 'B')
+    expect(t).toEqual(
+      { add: t.add,
+        roots: {A: {B: {C: {D: {}}}, D: {}}},
+        parents: {A: [], B: ['A'], C: ['B', 'A'], D: ['C', 'B', 'A']},
+        children: {A: ['B', 'C', 'D'], B: ['C', 'D'], C: ['D'], D: []}})
+  })
+})
+
+describe('hierarchy walker', function () {
+  let t = Hierarchy.create()
+  // t.add('A', 'AB1')
+  t.add('A', 'AB1')
+  t.add('AB1', 'AB1C1')
+  t.add('AB1C1', 'AB1C1D1')
+  t.add('AB1C1', 'AB1C1D2')
+  t.add('AB1', 'AB1C2')
+  t.add('AB1C2', 'AB1C2D1')
+  t.add('A', 'AB2')
+  t.add('AB2', 'AB2C1')
+  t.add('AB2C1', 'AB2C1D1')
+  it('should visit nodes in order', function () {
+    const seen = []
+    Hierarchy.depthFirst(t.roots, (l, r) => seen.push([l, r]))
+    expect(seen).toEqual(
+      [
+        [ 'AB1C1D1', 'AB1C1' ],
+        [ 'AB1C1D2', 'AB1C1' ],
+        [ 'AB1C1', 'AB1' ],
+        [ 'AB1C2D1', 'AB1C2' ],
+        [ 'AB1C2', 'AB1' ],
+        [ 'AB1', 'A' ],
+        [ 'AB2C1D1', 'AB2C1' ],
+        [ 'AB2C1', 'AB2' ],
+        [ 'AB2', 'A' ]
+      ]
+    )
+  })
+})

No alert changes

Improved metrics

Total package byte prevSize

13316

increased by43.06%

Lines of code

227

increased by60.99%

Number of lines in readme file

120

increased by79.1%

No dependency changes