bloomrun - npm Package Compare versions

Comparing version 2.3.0 to 3.0.0

bloomrun.js

 'use strict'
 
+var deepSort = require('./lib/deepSort')
+var insertionSort = require('./lib/insertionSort')
 var Bucket = require('./lib/bucket')
 var Iterator = require('./lib/iterator')
 var PatternSet = require('./lib/patternSet')
-var matchingBuckets = require('./lib/matchingBuckets')
 var onlyRegex = require('./lib/onlyRegex')
 
-function BloomRun (opts) {
-  if (!(this instanceof BloomRun)) {
-    return new BloomRun(opts)
+function Bloomrun (opts) {
+  if (!(this instanceof Bloomrun)) {
+    return new Bloomrun(opts)
   }
@@ -16,11 +17,13 @@
   this._buckets = []
-  this._regexBucket = new Bucket(this._isDeep)
+  this._regexBucket = new Bucket(this)
   this._defaultResult = null
+  this._tree = {}
+  this._algo = this._isDeep ? deepSort : insertionSort
 }
 
-BloomRun.prototype.default = function (payload) {
+Bloomrun.prototype.default = function (payload) {
   this._defaultResult = payload
 }
 
-BloomRun.prototype.add = function (pattern, payload) {
+Bloomrun.prototype.add = function (pattern, payload) {
   if (onlyRegex(pattern)) {
@@ -31,15 +34,24 @@ this._regexBucket.add(new PatternSet(pattern, payload, this._isDeep))
 
-  var buckets = matchingBuckets(this._buckets, pattern)
+  var patternSet = new PatternSet(pattern, payload, this._isDeep)
   var bucket
 
-  if (buckets.length > 0) {
-    bucket = buckets[0]
-  } else {
-    bucket = new Bucket(this._isDeep)
-    this._buckets.push(bucket)
+  for (var key in pattern) {
+    if (pattern.hasOwnProperty(key)) {
+      if (typeof pattern[key] !== 'object') {
+        if (!this._tree[key]) {
+          this._tree[key] = {}
+        }
+        bucket = this._tree[key][pattern[key]]
+
+        if (!bucket) {
+          bucket = new Bucket(this)
+          this._buckets.push(bucket)
+          this._tree[key][pattern[key]] = bucket
+        }
+
+        bucket.add(patternSet)
+      }
+    }
   }
 
-  var patternSet = new PatternSet(pattern, payload, this._isDeep)
-  bucket.add(patternSet)
-
   return this
@@ -56,2 +68,3 @@ }
       buckets.splice(i, 1)
+      break
     }
@@ -61,13 +74,20 @@ }
 
-BloomRun.prototype.remove = function (pattern, payload) {
-  var matches = matchingBuckets(this._buckets, pattern)
+Bloomrun.prototype.remove = function (pattern, payload) {
+  var bucket = null
   payload = payload || null
 
-  if (matches.length > 0) {
-    for (var i = 0; i < matches.length; i++) {
-      var bucket = matches[i]
+  for (var key in pattern) {
+    if (pattern.hasOwnProperty(key)) {
+      if (typeof pattern[key] !== 'object') {
+        if (this._tree[key] && this._tree[key][pattern[key]]) {
+          bucket = this._tree[key][pattern[key]]
 
-      if (bucket.remove(pattern, payload)) {
-        removeBucket(this._buckets, bucket)
-        bucket.forEach(addPatternSet, this)
+          if (bucket.remove(pattern, payload)) {
+            removeBucket(this._buckets, bucket)
+            bucket.forEach(addPatternSet, this)
+            if (bucket.data.length === 0) {
+              delete this._tree[key][pattern[key]]
+            }
+          }
+        }
       }
@@ -80,9 +100,29 @@ }
 
-BloomRun.prototype.lookup = function (pattern, opts) {
-  var iterator = new Iterator(this, pattern, opts)
-  return iterator.next() || this._defaultResult || null
+function onlyPatterns (current) {
+  return current.pattern
 }
 
-BloomRun.prototype.list = function (pattern, opts) {
-  var iterator = new Iterator(this, pattern, opts)
+function patternsAndPayloads (current) {
+  return {
+    pattern: current.pattern,
+    payload: current.payload
+  }
+}
+
+Bloomrun.prototype.lookup = function (pattern, opts) {
+  var asMatch = null
+  if (opts && opts.patterns) {
+    asMatch = opts.payloads ? patternsAndPayloads : onlyPatterns
+  }
+
+  var iterator = new Iterator(this, pattern, asMatch)
+  return iterator.one() || this._defaultResult || null
+}
+
+Bloomrun.prototype.list = function (pattern, opts) {
+  var asMatch = null
+  if (opts && opts.patterns) {
+    asMatch = opts.payloads ? patternsAndPayloads : onlyPatterns
+  }
+  var iterator = new Iterator(this, pattern, asMatch)
   var list = []
@@ -109,4 +149,10 @@ var current = null
 
-BloomRun.prototype.iterator = Iterator
+Bloomrun.prototype.iterator = function (obj, opts) {
+  var asMatch = null
+  if (opts && opts.patterns) {
+    asMatch = opts.payloads ? patternsAndPayloads : onlyPatterns
+  }
+  return new Iterator(this, obj, asMatch)
+}
 
-module.exports = BloomRun
+module.exports = Bloomrun

lib/bucket.js

 'use strict'
 
-var BloomFilter = require('bloomfilter').BloomFilter
-var deepSort = require('./deepSort')
-var genKeys = require('./genKeys')
-var deepMatch = require('./deepMatch')
+var sorted = require('sorted-array-functions')
+var match = require('./match')
 
-function Bucket (isDeep) {
-  this.filter = new BloomFilter(
-    32 * 256, // number of bits to allocate.
-    16        // number of hash functions.
-  )
+function Bucket (parent) {
   this.data = []
-  this.isDeep = isDeep
+  this._algo = parent._algo
+  this._isDeep = parent._isDeep
+  this.magic = this._isDeep ? 0 : Number.MAX_SAFE_INTEGER
 }
 
 Bucket.prototype.add = function (set) {
-  genKeys(set.pattern).forEach(addPatterns, this)
-  this.data.push(set)
-  if (this.isDeep) {
-    this.data.sort(deepSort)
+  sorted.add(this.data, set, this._algo)
+  if (this._isDeep) {
+    if (this.magic < set.magic) {
+      this.magic = set.magic
+    }
+  } else {
+    if (this.magic > set.magic) {
+      this.magic = set.magic
+    }
   }
@@ -26,12 +27,7 @@ return this
 
-function addPatterns (toAdd) {
-  this.filter.add(toAdd)
-}
-
 Bucket.prototype.remove = function (pattern, payload) {
   var foundPattern = false
   var data = this.data
-
   for (var i = 0; i < data.length; i++) {
-    if (deepMatch(pattern, data[i].pattern)) {
+    if (match(pattern, data[i].pattern)) {
       if (payload === null || payload === data[i].payload) {
@@ -38,0 +34,0 @@ data.splice(i, 1)

lib/iterator.js

 'use strict'
 
-var matchingBuckets = require('./matchingBuckets')
-var deepMatch = require('./deepMatch')
-var onlyRegex = require('./onlyRegex')
+var sorted = require('sorted-array-functions')
+var match = require('./match')
 
-function Iterator (parent, obj, opts) {
-  if (!(this instanceof Iterator)) {
-    return new Iterator(this, parent, obj)
-  }
-
+function Iterator (parent, obj, asMatch) {
   this.parent = parent
   this.pattern = obj
-  this.onlyPatterns = opts && opts.patterns && !opts.payloads
-  this.patternsAndPayloads = opts && opts.patterns && opts.payloads
-  this.onlyPayloads = (opts && !opts.patterns && opts.payloads) || !opts
-
+  this._asMatch = asMatch
+  this.buckets = []
+  this.visited = this.bucket = null
   if (obj) {
-    if (onlyRegex(obj)) {
-      this.buckets = parent._buckets
-    } else {
-      this.buckets = matchingBuckets(parent._buckets, obj)
-    }
+    loop(obj, parent._tree, this.buckets, parent._algo)
   } else {
     this.buckets = parent._buckets
   }
+  var r = parent._regexBucket
+  this.i = this.k = 0
+  this.regexpBucket = r.data.length > 0 && r
+}
 
-  if (this.parent._regexBucket.data.length > 0) {
-    this.buckets.push(this.parent._regexBucket)
+function loop (obj, tree, keys, algo) {
+  var magic = 0
+  var branch
+
+  for (var key in obj) {
+    branch = tree[key]
+    if (branch && branch[obj[key]]) {
+      magic = branch[obj[key]]
+      sorted.add(keys, magic, algo)
+    }
   }
+}
 
-  this.i = 0
-  this.k = 0
+Iterator.prototype.nextBucket = function () {
+  var bucket = this.bucket
+  var regexpBucket = this.regexpBucket
+
+  if (!bucket) {
+    bucket = this.buckets[this.i++]
+
+    if (!bucket && regexpBucket) {
+      bucket = regexpBucket
+      this.regexpBucket = null
+    }
+
+    this.bucket = bucket
+  }
+
+  return bucket
 }
 
+Iterator.prototype.one = function () {
+  var result = null
+  var bucket = null
+  var pattern = this.pattern
+  var asMatch = this._asMatch
+
+  while (result === null && (bucket = this.nextBucket())) {
+    var current = bucket.data[this.k]
+
+    if (!pattern || match(current.pattern, pattern)) {
+      result = asMatch ? asMatch(current) : current.payload
+    }
+
+    if (++this.k === bucket.data.length) {
+      this.bucket = null
+      this.k = 0
+    }
+  }
+
+  return result
+}
+
 Iterator.prototype.next = function () {
-  var match = null
+  var result = null
+  var bucket = null
+  var current = null
+  var pattern = this.pattern
+  var asMatch = this._asMatch
 
-  if (this.i === this.buckets.length) {
-    return null
+  if (!this.visited) {
+    this.visited = new Set()
   }
 
-  var current = this.buckets[this.i].data[this.k]
+  var visited = this.visited
 
-  if (!this.pattern || deepMatch(current.pattern, this.pattern)) {
-    if (this.onlyPayloads) {
-      match = current.payload
-    } else if (this.onlyPatterns) {
-      match = current.pattern
-    } else if (this.patternsAndPayloads) {
-      match = {
-        pattern: current.pattern,
-        payload: current.payload
-      }
+  while (result === null) {
+    bucket = this.nextBucket()
+
+    if (!bucket) {
+      return null
     }
-  }
 
-  if (++this.k === this.buckets[this.i].data.length) {
-    ++this.i
-    this.k = 0
+    current = bucket.data[this.k]
+
+    if (!visited.has(current) && (!pattern || match(current.pattern, pattern))) {
+      visited.add(current)
+      result = asMatch ? asMatch(current) : current.payload
+    }
+
+    if (++this.k === bucket.data.length) {
+      this.bucket = null
+      this.k = 0
+    }
   }
 
-  if (match) {
-    return match
-  } else {
-    return this.next()
-  }
+  return result
 }
 
 module.exports = Iterator

lib/patternSet.js

 'use strict'
 
+var counter = 1
+
 function PatternSet (pattern, payload, isDeep) {
@@ -9,24 +11,8 @@ this.pattern = pattern
   if (isDeep) {
-    this.magic = calcMagic(pattern)
+    this.magic = Object.keys(pattern).length
+  } else {
+    this.magic = counter++
   }
 }
 
-function calcMagic (pattern) {
-  var keys = Object.keys(pattern)
-  var length = keys.length
-  var result = 0
-  var key
-
-  for (var i = 0; i < length; i++) {
-    key = keys[i]
-    if (typeof pattern[key] === 'object') {
-      result += calcMagic(pattern[key])
-    } else {
-      result++
-    }
-  }
-
-  return result
-}
-
 module.exports = PatternSet

lib/safeEqual.js

 'use strict'
 
 function safeEqual (a, b) {
-  if (typeof b !== 'string' || typeof b !== 'string') {
+  if (typeof a !== 'string' || typeof b !== 'string') {
     return a === b
@@ -6,0 +6,0 @@ }

package.json

 {
   "name": "bloomrun",
-  "version": "2.3.0",
+  "version": "3.0.0",
   "description": "JS object pattern matching, powered by bloom filters",
@@ -10,2 +10,3 @@ "main": "bloomrun.js",
     "test": "tape test.js | faucet",
+    "zuul-local": "zuul --open --local 8081 -- test.js",
     "coverage": "istanbul cover tape test.js > /dev/null; open coverage/lcov-report/index.html",
@@ -25,3 +26,3 @@ "coveralls": "istanbul cover tape test.js; cat coverage/lcov.info | coveralls"
   "dependencies": {
-    "bloomfilter": "0.0.16"
+    "sorted-array-functions": "^1.0.0"
   },
@@ -36,4 +37,5 @@ "devDependencies": {
     "standard": "^7.0.0",
-    "tape": "^4.0.2"
+    "tape": "^4.0.2",
+    "zuul": "^3.11.1"
   }
 }

README.md

@@ -9,4 +9,3 @@ [![logo][logo-url]][npm-url]
 
-A js pattern matcher based on bloom filters, inspired by [patrun](http://npm.im/patrun).
-But different: 3-10x faster, and with results that can be returned in __insertion order__ or __depth order__.
+A js pattern matcher with results that can be returned in __insertion order__ or __depth order__. 2.5KB minified and gzipped, runs in the browser. Inspired by bloom filters.
 
@@ -73,3 +72,3 @@ * [Install](#install)
 
-Creates a new instance of Bloomrun.
+Creates a new instance of __bloomrun__.
 
@@ -89,3 +88,3 @@ Options are:
 
-Adds a pattern to the Bloomrun instance. You can also provide an alternative
+Adds a pattern to the __bloomrun__ instance. You can also provide an alternative
 payload to return instead of the pattern itself. This allows pattern based
@@ -100,3 +99,3 @@ retrieval of objects. If no payload is provided the pattern itself will be
 
-Removes a pattern from the Bloomrun instance. Filters are rebuilt after each
+Removes a pattern from the __bloomrun__ instance. Filters are rebuilt after each
 removal which may mean the same pattern is matched by another filter. In cases
@@ -199,8 +198,4 @@ where two patterns differ only by payload, the supplied payload can be used to
 
-Bloomrun would not be possible without
-[bloomfilter](https://www.npmjs.com/package/bloomfilter).
-
 The bloomrun logo was created, with thanks, by [Dean McDonnell](https:/github.com/mcdonnelldean)
 
-
 ## License
@@ -207,0 +202,0 @@

test.js

@@ -51,26 +51,2 @@ 'use strict'
 
-test('regexp support in the lookup', function (t) {
-  t.plan(1)
-
-  var instance = bloomrun()
-  var pattern = { prefs: 'userId' }
-  var payload = '1234'
-
-  instance.add(pattern, payload)
-
-  t.deepEqual(instance.lookup({ prefs: /user.*/ }), payload)
-})
-
-test('regexp plus props support in the lookup', function (t) {
-  t.plan(1)
-
-  var instance = bloomrun()
-  var pattern = { cmd: 'save', prefs: 'userId' }
-  var payload = '1234'
-
-  instance.add(pattern, payload)
-
-  t.deepEqual(instance.lookup({ cmd: 'save', prefs: /user.*/ }), payload)
-})
-
 test('regexp support in the pattern', function (t) {
@@ -100,20 +76,2 @@ t.plan(1)
 
-test('deep pattern matching', function (t) {
-  t.plan(1)
-
-  var instance = bloomrun()
-  var pattern = { role: 'sum', tnx: { side: 'buy' } }
-  var payload = '1234'
-
-  instance.add(pattern, payload)
-
-  t.deepEqual(instance.lookup({
-    role: 'sum',
-    tnx: {
-      side: 'buy',
-      amount: 100
-    }
-  }), payload)
-})
-
 test('functions are supported as payloads', function (t) {
@@ -413,31 +371,2 @@ t.plan(1)
 
-test('recursive depth support', function (t) {
-  t.plan(1)
-
-  var instance = bloomrun({ indexing: 'depth' })
-  var pattern1 = { group: '123', some: { key: 'value' } }
-  var pattern2 = {
-    group: '123',
-    some: {
-      key: 'value',
-      a: 'b'
-    }
-  }
-
-  function payloadOne () { }
-  function payloadTwo () { }
-
-  instance.add(pattern1, payloadOne)
-  instance.add(pattern2, payloadTwo)
-
-  t.equal(instance.lookup({
-    group: '123',
-    some: {
-      key: 'value',
-      a: 'b',
-      c: 'd'
-    }
-  }), payloadTwo)
-})
-
 test('boolean matching', function (t) {
@@ -484,18 +413,12 @@ t.plan(5)
 
-  // first bucket
   instance.add({ c: 'CCC' }, 1)
-  // second bucket
   instance.add({ b: 'BBB' }, 2)
-  // first bucket
   instance.add({ a: 'AAA', b: 'BBB', c: 'CCC' }, 3)
-  // first bucket
   instance.add({ a: 'AAA' }, 4)
 
   t.deepEqual(instance.list({ a: 'AAA', b: 'BBB', c: 'CCC', d: 'DDD' }), [
-    // first bucket matches
     3,
     1,
-    4,
-    // second bucket matches
-    2
+    2,
+    4
   ])
@@ -508,14 +431,9 @@ })
 
-  // this goes in the 1st bucket
   instance.add({ c: 'CCC' }, 2)
-  // and this one too
   instance.add({ c: 'CCC', d: 'DDD' }, 1)
-  // this goes in the 2nd bucket
   instance.add({ a: 'AAA' }, 3)
 
   t.deepEqual(instance.list({ a: 'AAA', b: 'BBB', c: 'CCC', d: 'DDD' }), [
-    // first bucket matches
     1,
     2,
-    // second bucket
     3
@@ -534,6 +452,4 @@ ])
   t.deepEqual(instance.list({ a: 'AAA', b: 'BBB', c: 'CCC', d: 'DDD' }), [
-    // first bucket matches
     2,
     1,
-    // second bucket matches
     3
@@ -543,20 +459,2 @@ ])
 
-test('recursive depth support, no other keys', function (t) {
-  t.plan(1)
-
-  var instance = bloomrun({ indexing: 'depth' })
-  var pattern1 = { some: { key: 'value' } }
-  var pattern2 = { some: { key: 'value', a: 'b' } }
-
-  function payloadOne () { }
-  function payloadTwo () { }
-
-  instance.add(pattern1, payloadOne)
-  instance.add(pattern2, payloadTwo)
-
-  t.equal(instance.lookup({
-    some: { key: 'value', a: 'b', c: 'd' }
-  }), payloadTwo)
-})
-
 test('patterns and data can be listed while using payloads', function (t) {
@@ -563,0 +461,0 @@ t.plan(1)

No alert changes

Improved metrics

Total package byte prevSize

58250

increased by16.15%

Number of package files

22

increased by10%

Lines of code

975

increased by10.8%

Worsened metrics

Dev dependency count

9

increased by12.5%

Number of lines in readme file

212

decreased by-2.3%

Dependency changes

• + Addedsorted-array-functions@^1.0.0

• + Addedsorted-array-functions@1.3.0(transitive)

• - Removedbloomfilter@0.0.16

• - Removedbloomfilter@0.0.16(transitive)