persistent-hash-trie - npm Package Compare versions

Comparing version 0.2.4 to 0.3.0

benchmark/assoc.js

@@ -5,8 +5,12 @@ 'use strict'
 var gen = require('./gen-data')
+var versions = require('./versions')
 
-var makeSuite = function(quantity) {
+var makeSuite = function(quantity){
 	var suite = new require('benchmark').Suite('assoc property with Trie of ' + quantity)
 	var data = gen(quantity, Math.random())
 
-	var test = function(name, p){
+	var test = function(o){
+		var name = o.name
+		var p = o.module
+
 		var trie = _.reduce(data, function(trie, val, key){
@@ -21,6 +25,3 @@ return p.assoc(trie, key, val)
 
-	test('current', require('..'))
-	test('v0.2.1', require('./previous-versions/0.2.1/'))
-	test('v0.2.2', require('./previous-versions/0.2.2/'))
-	test('v0.2.3', require('./previous-versions/0.2.3/'))
+	_.each(versions, test)
 
@@ -27,0 +28,0 @@ return suite

benchmark/benchmarks.js

@@ -10,5 +10,5 @@ 'use strict'
 var get = require('./get')
-var transient = require('./transient')
+var mutable = require('./mutable')
+var keys = require('./keys')
 
-
 var suites = [
@@ -36,8 +36,13 @@ assoc(1),
 
-	transient(1),
-	transient(10),
-	transient(100),
-	transient(1000)
+	mutable(1),
+	mutable(10),
+	mutable(100),
+	mutable(1000),
+
+	keys(1),
+	keys(10),
+	keys(100),
+	keys(1000)
 ]
 
 _.each(suites, run)

benchmark/dissoc.js

@@ -5,2 +5,3 @@ 'use strict'
 var gen = require('./gen-data')
+var versions = require('./versions')
 
@@ -11,3 +12,6 @@ var makeSuite = function(quantity){
 
-	var test = function(name, p){
+	var test = function(o){
+		var name = o.name
+		var p = o.module
+
 		var trie = _.reduce(data, function(trie, val, key){
@@ -23,6 +27,3 @@ return p.assoc(trie, key, val)
 
-	test('current', require('..'))
-	test('v0.2.1', require('./previous-versions/0.2.1/'))
-	test('v0.2.2', require('./previous-versions/0.2.2/'))
-	test('v0.2.3', require('./previous-versions/0.2.3/'))
+	_.each(versions, test)
 
@@ -29,0 +30,0 @@ return suite

benchmark/get.js

@@ -5,2 +5,3 @@ 'use strict'
 var gen = require('./gen-data')
+var versions = require('./versions')
 
@@ -11,3 +12,6 @@ var makeSuite = function(quantity){
 
-	var test = function(name, p){
+	var test = function(o){
+		var name = o.name
+		var p = o.module
+
 		var trie = _.reduce(data, function(trie, val, key){
@@ -23,7 +27,3 @@ return p.assoc(trie, key, val)
 
-	test('current', require('..'))
-	test('v0.2.1', require('./previous-versions/0.2.1/'))
-	test('v0.2.2', require('./previous-versions/0.2.2/'))
-	test('v0.2.3', require('./previous-versions/0.2.3/'))
-
+	_.each(versions, test)
 	return suite
@@ -30,0 +30,0 @@ }

benchmark/has.js

@@ -5,2 +5,3 @@ 'use strict'
 var gen = require('./gen-data')
+var versions = require('./versions')
 
@@ -11,3 +12,6 @@ var makeSuite = function(quantity){
 
-	var test = function(name, p){
+	var test = function(o){
+		var name = o.name
+		var p = o.module
+
 		var trie = _.reduce(data, function(trie, val, key){
@@ -23,6 +27,3 @@ return p.assoc(trie, key, val)
 
-	test('current', require('..'))
-	test('v0.2.1', require('./previous-versions/0.2.1/'))
-	test('v0.2.2', require('./previous-versions/0.2.2/'))
-	test('v0.2.3', require('./previous-versions/0.2.3/'))
+	_.each(versions, test)
 
@@ -29,0 +30,0 @@ return suite

benchmark/transient.js

@@ -5,8 +5,13 @@ 'use strict'
 var gen = require('./gen-data')
+var versions = require('./versions')
 
 var makeSuite = function(quantity){
-	var suite = new require('benchmark').Suite('transient property with Trie of ' + quantity)
+	var suite = new require('benchmark').Suite('mutable with Trie of ' + quantity)
 	var data = gen(quantity, Math.random())
 
-	var test = function(name, p){
+	var test = function(o){
+		var name = o.name
+		var p = o.module
+
+
 		var trie = _.reduce(data, function(trie, val, key){
@@ -16,11 +21,11 @@ return p.assoc(trie, key, val)
 
+		// legacy implementations called this 'transient'
+		var methodName = p.transient ? 'transient' : 'mutable'
+
 		suite.add(name, function(){
-			p.transient(trie)
+			p[methodName](trie)
 		})
 	}
 
-	test('current', require('..'))
-	test('v0.2.1', require('./previous-versions/0.2.1/'))
-	test('v0.2.2', require('./previous-versions/0.2.2/'))
-	test('v0.2.3', require('./previous-versions/0.2.3/'))
+	_.each(versions, test)
 
@@ -27,0 +32,0 @@ return suite

package.json

@@ -5,3 +5,3 @@
   "description": "Pure string:val storage, using structural sharing",
-  "version": "0.2.4",
+  "version": "0.3.0",
   "main": "src/persistent-hash-trie.js",
@@ -18,3 +18,4 @@ "scripts": {
     "microtime": "0.3.3",
-    "better-stack-traces": "0.0.4"
+    "better-stack-traces": "0.0.4",
+    "string-hash": "1.1.0"
   },
@@ -21,0 +22,0 @@ "repository": {

src/persistent-hash-trie.js

@@ -65,7 +65,8 @@ 'use strict'
 // hash-table-like behaviour, as the hash-trie has), they can be passed in
-// as opts to the CRUD functions.  The default ones covers the 80% use-case
+// as opts to assoc/dissoc/get/has.
+
+// These defaults cover the ~80% use case of unordered string:val pairs.
 var defaultOpts = {
-    eq  : function(a, b){ return a === b },
-
-    hash: hash
+    eq   : function(a, b){ return a === b },
+    hash : hash
 }
@@ -199,4 +200,4 @@
     value: function(node, key, val, opts, depth){
-        var origPath = hashMask(node.key, depth, opts.hash)
-        var path     = hashMask(key, depth, opts.hash)
+        var nodePath = hashMask(node.key, depth, opts.hash)
+        var keyPath  = hashMask(key, depth, opts.hash)
 
@@ -212,4 +213,4 @@ var makeHashmap = function(){
             var children = {}
-            children[origPath] = node
-            children[path]     = Value(key, val)
+            children[nodePath] = node
+            children[keyPath]  = Value(key, val)
 
@@ -221,3 +222,3 @@ return Trie(children)
             var children = {}
-            children[path] = assoc(node, key, val, opts, depth + 1)
+            children[keyPath] = assoc(node, key, val, opts, depth + 1)
             return Trie(children)
@@ -227,4 +228,4 @@ }
         var makeTrie = function(){
-            if ( origPath !== path ) return resolveShallowConflict()
-            else                     return resolveDeepConflict()
+            if ( nodePath !== keyPath ) return resolveShallowConflict()
+            else                        return resolveDeepConflict()
         }
@@ -252,11 +253,3 @@
 
-// Object -> [String]
 
-// get the keys of an object
-var keys = Object.keys || function(o){
-    var a = []
-    for ( var key in o ) a.push(key)
-    return a
-}
-
 // Node, String, (Int) -> Trie
@@ -287,28 +280,37 @@
         var child = node.children[path]
-        var trie
 
-        // handle the 'missing key' case, returning the Trie
-        if ( child === undefined ) trie = node
-
         // handle the 'present key' cases.  If it's a Value, remove it.  If it's a sub-Trie or Hashmap
         // recurse to prevent other values from being lost
-        else if ( child.type === 'value' && opts.eq(child.key, key) )
-            trie = Trie(copyDissoc(node.children, path))
-        else
-           trie = Trie(copyDissoc(node.children, path, dissoc(child, key, opts, depth + 1)))
+        var dissocKey = function(){
+            if ( child.type === 'value' && opts.eq(child.key, key) )
+                return Trie(copyDissoc(node.children, path))
+            else
+                return Trie(copyDissoc(node.children, path, dissoc(child, key, opts, depth + 1)))
+        }
 
         // if there's only a single value in a Trie node left, then it can be replaced by its value,
         // allowing us to make the Trie more shallow, and therefore more effecient.
-        var names = keys(trie.children)
-        var child = trie.children[names[0]]
+        var collapseTrie = function(trie){
+            var names = util.keys(trie.children)
+            var child = trie.children[names[0]]
 
-        if ( names.length === 1 && child && child.type === 'value' )
-            return Value(child.key, child.value)
-        else
-            return trie
+            // don't collapse an empty root trie
+            if ( depth === 0 )                                       return trie
+            else if ( child === undefined )                          return trie
+            else if ( names.length === 1 && child.type === 'value' ) return Value(child.key, child.value)
+            else                                                     return trie
+        }
+
+        var handleTrie = function(){
+            return collapseTrie(dissocKey(node))
+        }
+
+        // if there's no child, return the node
+        if ( child === undefined )  return node;
+        else                        return handleTrie();
     },
     value: function(){},
-    hashmap: function(map, key, opts, depth){
-        var ret = copyDissoc(map.values, hashMask(key, depth, opts.hash))
-        var names = keys(ret)
+    hashmap: function(node, key, opts, depth){
+        var ret = copyDissoc(node.values, key)
+        var names = util.keys(ret)
         var child = ret[names[0]]
@@ -324,3 +326,3 @@
 
-// transient returns a mutable version of a Trie.
+// mutable returns a mutable version of a Trie.
 
@@ -334,11 +336,11 @@ // It achieves this by recursing down the Trie, finding all the Value nodes
 
-var transient = function(node, curr){
+var mutable = function(node, curr){
     curr = curr || {}
-    transientFns[node.type](node, curr)
+    mutableFns[node.type](node, curr)
     return curr
 }
 
-var transientFns = {
+var mutableFns = {
     trie: function(node, curr){
-        for ( var key in node.children ) transient(node.children[key], curr)
+        for ( var key in node.children ) mutable(node.children[key], curr)
     },
@@ -349,15 +351,38 @@ value: function(node, curr){
     hashmap: function(node, curr){
-        for ( var key in node.values ) transient(node.values[key], curr)
+        for ( var key in node.values ) mutable(node.values[key], curr)
     }
 }
 
+// Node -> [String]
+
+// keys returns the keys stored in the array, like Object.keys
+// implemented similarly to `mutable`
+var keys = function(node, arr){
+    arr = arr || []
+    keysFns[node.type](node, arr)
+    return arr
+}
+
+var keysFns = {
+    trie: function(node, arr){
+        for ( var key in node.children ) keys(node.children[key], arr)
+    },
+    value: function(node, arr){
+        arr.push(node.key)
+    },
+    hashmap: function(node, arr){
+        for ( var key in node.values ) keys(node.values[key], arr)
+    }
+}
+
 module.exports = {
-    Trie      : Trie,
-    Value     : Value,
-    Hashmap   : Hashmap,
-    has       : has,
-    get       : get,
-    assoc     : assoc,
-    dissoc    : dissoc,
-    transient : transient
+    Trie    : Trie,
+    Value   : Value,
+    Hashmap : Hashmap,
+    has     : has,
+    get     : get,
+    assoc   : assoc,
+    dissoc  : dissoc,
+    mutable : mutable,
+    keys    : keys
 }

src/util.js

@@ -36,2 +36,12 @@ 'use strict'
 
+// Object -> [String]
+
+// get the keys of an object
+var keys = Object.keys || function(o){
+    var a = []
+    for ( var key in o ) a.push(key)
+    return a
+}
+
+
 module.exports = {
@@ -44,3 +54,4 @@ extend    : extend,
     map       : map,
-    reduce    : reduce
+    reduce    : reduce,
+    keys      : keys
 }

test/random-data-test.js

@@ -50,21 +50,8 @@ 'use strict'
 
-describe('using random data', function(){
+var testWithData = function(data){
 
-    var seed = Math.random()
-    var data = gen(10000, seed)
+    var keys = _.keys(data)
 
-    // get the first 10 keys of the randomly genned data
-    var first10 = (function(){
-        var a = []
-        for ( var p in data ) {
-            a.push(p)
-            if ( a.length === 10 ) return a
-        }
-    })()
+    describe('assoc/dissoc/has/get on trie w/ ' + keys.length + ' items', function(){
 
-    log('TESTING SEED: ' + seed)
-
-    describe('assoc/dissoc/has/get on trie w/ 10000 items', function(){
-
-        // create a trie of 10000 items
         var trie =  _.reduce(data, function(trie, val, key){
@@ -74,4 +61,4 @@ return p.assoc(trie, key, val)
 
-        it('should return not undefined for gets from first 10 keys', function(){
-            _.each(first10, function(prop){
+        it('should return not undefined for get', function(){
+            _.each(keys, function(prop){
                 a.notEqual(p.get(trie, prop), undefined)
@@ -81,5 +68,5 @@ })
 
-        it('should return true for has from first 10 keys', function(){
+        it('should return true for has', function(){
 
-            _.each(first10, function(prop){
+            _.each(keys, function(prop){
                 a.equal(p.has(trie, prop), true)
@@ -89,11 +76,11 @@ })
 
-        it('should allow us to assoc over first 10 keys', function(){
+        it('should allow us to assoc', function(){
 
             var testVal = {}
 
-            var t = _.reduce(first10, function(trie, key){
+            var t = _.reduce(keys, function(trie, key){
                 return p.assoc(trie, key, testVal)
             }, trie)
 
-            _.each(first10, function(prop){
+            _.each(keys, function(prop){
                 a.equal(p.get(t, prop), testVal)
@@ -103,9 +90,8 @@ })
 
-        it('should allow us to dissoc first 10 keys', function(){
-
-            var t = _.reduce(first10, function(trie, key){
+        it('should allow us to dissoc', function(){
+            var t = _.reduce(keys, function(trie, key){
                 return p.dissoc(trie, key)
             }, trie)
 
-            _.each(first10, function(prop){
+            _.each(keys, function(prop){
                 a.ok(!p.has(t, prop))
@@ -115,54 +101,28 @@ })
 
-        describe('transient', function(){
+        describe('mutable', function(){
             it('should return the same object that\'s put in to the trie', function(){
-                a.equal(Object.keys(p.transient(trie)).length, Object.keys(data).length)
-                a.deepEqual(p.transient(trie), data)
+                a.deepEqual(p.mutable(trie), data)
             })
         })
-    })
 
-    describe('assoc/dissoc/has/get on trie w/ 10000 items from depth 4', function(){
-
-        // create a trie of 10000 items
-        var trie =  _.reduce(data, function(trie, val, key){
-            return p.assoc(trie, key, val, null, 4)
-        }, p.Trie())
-
-        it('should return not undefined for gets from first 10 keys', function(){
-            _.each(first10, function(prop){
-                a.notEqual(p.get(trie, prop, null, 4), undefined)
+        describe('keys', function(){
+            it('should return an array of keys stored in the trie', function(){
+                a.deepEqual(p.keys(trie).sort(), _.keys(data).sort())
             })
         })
+    })
+}
 
-        it('should return true for has from first 10 keys', function(){
 
-            _.each(first10, function(prop){
-                a.equal(p.has(trie, prop, null, 4), true)
-            })
-        })
+describe('using random data', function(){
+    var seed = Math.random()
+    var data = gen(100, seed)
+    log('TESTING SEED: ' + seed)
 
-        it('should allow us to assoc over first 10 keys', function(){
+    testWithData(gen(1, seed))
+    testWithData(gen(100, seed))
+    testWithData(gen(1000, seed))
+    testWithData(gen(10000, seed))
+})
 
-            var testVal = {}
 
-            var t = _.reduce(first10, function(trie, key){
-                return p.assoc(trie, key, testVal, null, 4)
-            }, trie)
-
-            _.each(first10, function(prop){
-                a.equal(p.get(t, prop, null, 4), testVal)
-            })
-        })
-
-        it('should allow us to dissoc first 10 keys', function(){
-
-            var t = _.reduce(first10, function(trie, key){
-                return p.dissoc(trie, key, null, 4)
-            }, trie)
-
-            _.each(first10, function(prop){
-                a.ok(!p.has(t, prop, null, 4))
-            })
-        })
-    })
-})

New alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Major refactor

Supply chain risk

Package has recently undergone a major refactor. It may be unstable or indicate significant internal changes. Use caution when updating to versions that include significant changes.

Found 1 instance in 1 package

Fixed alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Improved metrics

Total package byte prevSize

385078

increased by196.71%

Number of package files

254

increased by229.87%

Lines of code

8497

increased by237.45%

Number of lines in readme file

101

increased by9.78%

Worsened metrics

Dev dependency count

6

increased by20%

Number of low supply chain risk alerts

68

increased by240%

Number of medium supply chain risk alerts

1

increased byInfinity%

No dependency changes