qlobber - npm Package Compare versions

Comparing version 0.1.1 to 0.2.0

lib/qlobber.js

@@ -30,2 +30,3 @@ /**
 ```javascript
+matcher = new Qlobber({ remove_duplicates: true });
 matcher.add('*.orange.*', 'Q1');
@@ -42,3 +43,6 @@ matcher.add('*.*.rabbit', 'Q2');
                   'quick.orange.male.rabbit',
-                  'lazy.orange.male.rabbit'].map(matcher.match),
+                  'lazy.orange.male.rabbit'].map(function (topic)
+                  {
+                      return matcher.match(topic).sort();
+                  }),
                  [['Q1', 'Q2'],
@@ -81,2 +85,29 @@ ['Q1', 'Q2'],
 
+// Polyfill Set if we don't have it. In the future when V8 implements Set fully,
+// consider using it as the container in the trie instead of arrays.
+
+var PSet;
+
+if (typeof Set === 'undefined')
+{
+    PSet = function ()
+    {
+        var values = [];
+
+        this.add = function (v)
+        {
+            values.push(v);
+        };
+
+        this.has = function (v)
+        {
+            return values.indexOf(v) >= 0;
+        };
+    };
+}
+else
+{
+    PSet = Set;
+}
+
 /**
@@ -86,3 +117,3 @@ Creates a new qlobber.
 @constructor
-@param {Object} [options] Configures the globber. Use the following properties:
+@param {Object} [options] Configures the qlobber. Use the following properties:
 
@@ -95,3 +126,3 @@ - `{String} separator` The character to use for separating words in topics. Defaults to '.'. MQTT uses '/' as the separator, for example.
 
-- `{String | false} compare` The function to use for sorting matches in order to remove duplicates. Defaults to lexicographical string compare. Specify `false` to turn off duplicate removal. If you store values other than strings in qlobber, pass in your own compare function.
+- `{Boolean} remove_duplicates` qlobber's matching algorithm means values may be returned twice. Specify `true` to have qlobber remove duplicates from its results. Note this will incur a performance penalty. Defaults to `false`.
 */
@@ -102,146 +133,155 @@ function Qlobber (options)
 
-    var QlobberObject = this,
-        separator = options.separator || '.',
-        wildcard_one = options.wildcard_one || '*',
-        wildcard_some = options.wildcard_some || '#',
-        trie = {},
+    this._separator = options.separator || '.';
+    this._wildcard_one = options.wildcard_one || '*';
+    this._wildcard_some = options.wildcard_some || '#';
+    this._remove_duplicates = options.remove_duplicates;
+    this._trie = {};
+}
+
+Qlobber.prototype._add = function (val, i, words, sub_trie)
+{
+    var st, word;
+
+    if (i === words.length)
+    {
+        st = sub_trie[this._separator];
         
-    add = function (val, i, words, sub_trie)
-    {
-        var st, word;
-
-        if (i === words.length)
+        if (st)
         {
-            st = sub_trie[separator] = (sub_trie[separator] || []);
             st.push(val);
-            return;
         }
+        else
+        {
+            sub_trie[this._separator] = [val];
+        }
+        
+        return;
+    }
 
-        word = words[i];
-        st = sub_trie[word] = (sub_trie[word] || {});
+    word = words[i];
+    st = sub_trie[word]
+    
+    if (!st)
+    {
+        st = sub_trie[word] = {};
+    }
+    
+    this._add(val, i + 1, words, st);
+};
 
-        add(val, i + 1, words, st);
-    },
+Qlobber.prototype._remove = function (val, i, words, sub_trie)
+{
+    var st, index, word, w;
 
-    remove = function (val, i, words, sub_trie)
+    if (i === words.length)
     {
-        var st, index, word, w;
+        st = sub_trie[this._separator];
 
-        if (i === words.length)
+        if (st)
         {
-            st = sub_trie[separator];
-
-            if (st)
+            if (val === undefined)
             {
-                if (val === undefined)
-                {
-                    st = [];
-                }
-                else
-                {
-                    index = st.lastIndexOf(val);
+                st = [];
+            }
+            else
+            {
+                index = st.lastIndexOf(val);
 
-                    if (index >= 0)
-                    {
-                        st.splice(index, 1);
-                    }
-                }
-
-                if (st.length === 0)
+                if (index >= 0)
                 {
-                    delete sub_trie[separator];
+                    st.splice(index, 1);
                 }
             }
 
-            return;
+            if (st.length === 0)
+            {
+                delete sub_trie[this._separator];
+            }
         }
-        
-        word = words[i];
-        st = sub_trie[word];
 
-        if (!st)
-        {
-            return;
-        }
+        return;
+    }
+    
+    word = words[i];
+    st = sub_trie[word];
 
-        remove(val, i + 1, words, st);
+    if (!st)
+    {
+        return;
+    }
 
+    this._remove(val, i + 1, words, st);
+
+    for (w in st)
+    {
+        return;
+    }
+
+    delete sub_trie[word];
+};
+
+Qlobber.prototype._match = function (v, i, words, sub_trie)
+{
+    var word, st, w, j;
+
+    st = sub_trie[this._wildcard_some];
+
+    if (st)
+    {
+        // common case: no more levels
+
+        /*jslint forin: true */
         for (w in st)
         {
-            if (st.hasOwnProperty(w))
+            if (w !== this._separator)
             {
-                return;
+                for (j = i; j < words.length; j += 1)
+                {
+                    v = this._match(v, j, words, st);
+                }
+
+                break;
             }
         }
+        /*jslint forin: false */
 
-        delete sub_trie[word];
-    },
-    
-    match = function (i, words, sub_trie)
+        v = this._match(v, words.length, words, st);
+    }
+
+    if (i === words.length)
     {
-        var word, st, sts = [], w, j, iv = [];
+        st = sub_trie[this._separator];
 
-        st = sub_trie[wildcard_some];
-
         if (st)
         {
-            // common case: no more levels
-
-            /*jslint forin: true */
-            for (w in st)
-            {
-                if (w !== separator)
-                {
-                    for (j = i; j < words.length; j += 1)
-                    {
-                        sts.push({ i: j, st: st });
-                    }
-
-                    break;
-                }
-            }
-            /*jslint forin: false */
-
-            sts.push({ i: words.length, st: st });
+            v = v.concat(st);
         }
+    }
+    else
+    {
+        word = words[i];
 
-        if (i === words.length)
+        if ((word !== this._wildcard_one) && (word !== this._wildcard_some))
         {
-            st = sub_trie[separator];
+            st = sub_trie[word];
 
             if (st)
             {
-                iv = st;
+                v = this._match(v, i + 1, words, st);
             }
         }
-        else
+
+        if (word)
         {
-            word = words[i];
+            st = sub_trie[this._wildcard_one];
 
-            if ((word !== wildcard_one) && (word !== wildcard_some))
+            if (st)
             {
-                st = sub_trie[word];
-
-                if (st)
-                {
-                    sts.push({ i: i + 1, st: st });
-                }
+                v = this._match(v, i + 1, words, st);
             }
-
-            if (word)
-            {
-                st = sub_trie[wildcard_one];
-
-                if (st)
-                {
-                    sts.push({ i: i + 1, st: st });
-                }
-            }
         }
+    }
 
-        return sts.reduce(function(v, st)
-        {
-            return v.concat(match(st.i, words, st.st));
-        }, iv);
-    };
+    return v;
+};
 
@@ -256,6 +296,6 @@ /**
 */
-    QlobberObject.add = function (topic, val)
-    {
-        add(val, 0, topic.split(separator), trie);
-    };
+Qlobber.prototype.add = function (topic, val)
+{
+    this._add(val, 0, topic.split(this._separator), this._trie);
+};
 
@@ -268,14 +308,12 @@ /**
 */
-    QlobberObject.remove = function (topic, val)
+Qlobber.prototype.remove = function (topic, val)
+{
+    if (arguments.length === 1)
     {
-        if (arguments.length === 1)
-        {
-            remove(undefined, 0, topic.split(separator), trie);
-        }
-        else
-        {
-            remove(val, 0, topic.split(separator), trie);
-        }
-    };
+        val = undefined;
+    }
 
+    this._remove(val, 0, topic.split(this._separator), this._trie);
+};
+
 /**
@@ -285,26 +323,29 @@ Match a topic.
 @param {String} topic The topic to match against.
-@return {Array} List of values that matched the topic. This will be sorted and have duplicates removed unless you configured [Qlobber](#qlobberoptions) otherwise.
+@return {Array} List of values that matched the topic. This may contain duplicates unless you configured [Qlobber](#qlobberoptions) otherwise.
 */
-    QlobberObject.match = function (topic)
+Qlobber.prototype.match = function (topic)
+{
+    var r = this._match([], 0, topic.split(this._separator), this._trie);
+
+    if (this._remove_duplicates)
     {
-        var r = match(0, topic.split(separator), trie);
+        var seen = new PSet(), r2 = [], i, v;
 
-        if (options.compare !== false)
+        for (i = 0; i < r.length; i += 1)
         {
-            r = r.sort(options.compare).reduce(function (prev, cur)
+            v = r[i];
+
+            if (!seen.has(v))
             {
-                if (prev[prev.length - 1] !== cur)
-                {
-                    prev.push(cur);
-                }
+                r2.push(v);
+                seen.add(v);
+            }
+        }
 
-                return prev;
-            }, [undefined]);
+        return r2;
+    }
 
-            r.shift();
-        }
+    return r;
+};
 
-        return r;
-    };
-
 /**
@@ -315,16 +356,14 @@ Reset the qlobber.
 */
-    QlobberObject.clear = function ()
-    {
-        trie = {};
-    };
+Qlobber.prototype.clear = function ()
+{
+    this._trie = {};
+};
 
-    // for debugging
+// for debugging
+Qlobber.prototype.get_trie = function ()
+{
+    return this._trie;
+};
 
-    QlobberObject.get_trie = function ()
-    {
-        return trie;
-    };
-}
-
 exports.Qlobber = Qlobber;
 

package.json

 {
   "name": "qlobber",
   "description": "Node.js globbing for amqp-like topics",
-  "version": "0.1.1",
+  "version": "0.2.0",
   "homepage": "https://github.com/davedoesdev/qlobber",
@@ -6,0 +6,0 @@ "author": {

README.md

@@ -29,2 +29,3 @@ # qlobber   [![Build Status](https://travis-ci.org/davedoesdev/qlobber.png)](https://travis-ci.org/davedoesdev/qlobber)
 ```javascript
+matcher = new Qlobber({ remove_duplicates: true });
 matcher.add('*.orange.*', 'Q1');
@@ -41,3 +42,6 @@ matcher.add('*.*.rabbit', 'Q2');
                   'quick.orange.male.rabbit',
-                  'lazy.orange.male.rabbit'].map(matcher.match),
+                  'lazy.orange.male.rabbit'].map(function (topic)
+                  {
+                      return matcher.match(topic).sort();
+                  }),
                  [['Q1', 'Q2'],
@@ -81,6 +85,6 @@ ['Q1', 'Q2'],
 - <a name="toc_qlobberoptions"></a>[Qlobber](#qlobberoptions)
-- <a name="toc_qlobberobjectaddtopic-val"></a><a name="toc_qlobberobject"></a>[QlobberObject.add](#qlobberobjectaddtopic-val)
-- <a name="toc_qlobberobjectremovetopic-val"></a>[QlobberObject.remove](#qlobberobjectremovetopic-val)
-- <a name="toc_qlobberobjectmatchtopic"></a>[QlobberObject.match](#qlobberobjectmatchtopic)
-- <a name="toc_qlobberobjectclear"></a>[QlobberObject.clear](#qlobberobjectclear)
+- <a name="toc_qlobberprototypeaddtopic-val"></a><a name="toc_qlobberprototype"></a>[Qlobber.prototype.add](#qlobberprototypeaddtopic-val)
+- <a name="toc_qlobberprototyperemovetopic-val"></a>[Qlobber.prototype.remove](#qlobberprototyperemovetopic-val)
+- <a name="toc_qlobberprototypematchtopic"></a>[Qlobber.prototype.match](#qlobberprototypematchtopic)
+- <a name="toc_qlobberprototypeclear"></a>[Qlobber.prototype.clear](#qlobberprototypeclear)
 
@@ -93,3 +97,3 @@ # Qlobber([options])
 
-- `{Object} [options]` Configures the globber. Use the following properties:
+- `{Object} [options]` Configures the qlobber. Use the following properties:
 
@@ -103,9 +107,9 @@
 
-  - `{String | false} compare` The function to use for sorting matches in order to remove duplicates. Defaults to lexicographical string compare. Specify `false` to turn off duplicate removal. If you store values other than strings in qlobber, pass in your own compare function.
+  - `{Boolean} remove_duplicates` qlobber's matching algorithm means values may be returned twice. Specify `true` to have qlobber remove duplicates from its results. Note this will incur a performance penalty. Defaults to `false`.
 
 <sub>Go: [TOC](#tableofcontents)</sub>
 
-<a name="qlobberobject"></a>
+<a name="qlobberprototype"></a>
 
-# QlobberObject.add(topic, val)
+# Qlobber.prototype.add(topic, val)
 
@@ -121,5 +125,5 @@ > Add a topic matcher to the qlobber.
 
-<sub>Go: [TOC](#tableofcontents) | [QlobberObject](#toc_qlobberobject)</sub>
+<sub>Go: [TOC](#tableofcontents) | [Qlobber.prototype](#toc_qlobberprototype)</sub>
 
-# QlobberObject.remove(topic, [val])
+# Qlobber.prototype.remove(topic, [val])
 
@@ -133,5 +137,5 @@ > Remove a topic matcher from the qlobber.
 
-<sub>Go: [TOC](#tableofcontents) | [QlobberObject](#toc_qlobberobject)</sub>
+<sub>Go: [TOC](#tableofcontents) | [Qlobber.prototype](#toc_qlobberprototype)</sub>
 
-# QlobberObject.match(topic)
+# Qlobber.prototype.match(topic)
 
@@ -146,7 +150,7 @@ > Match a topic.
 
-`{Array}` List of values that matched the topic. This will be sorted and have duplicates removed unless you configured [Qlobber](#qlobberoptions) otherwise.
+`{Array}` List of values that matched the topic. This may contain duplicates unless you configured [Qlobber](#qlobberoptions) otherwise.
 
-<sub>Go: [TOC](#tableofcontents) | [QlobberObject](#toc_qlobberobject)</sub>
+<sub>Go: [TOC](#tableofcontents) | [Qlobber.prototype](#toc_qlobberprototype)</sub>
 
-# QlobberObject.clear()
+# Qlobber.prototype.clear()
 
@@ -157,4 +161,4 @@ > Reset the qlobber.
 
-<sub>Go: [TOC](#tableofcontents) | [QlobberObject](#toc_qlobberobject)</sub>
+<sub>Go: [TOC](#tableofcontents) | [Qlobber.prototype](#toc_qlobberprototype)</sub>
 
 _&mdash;generated by [apidox](https://github.com/codeactual/apidox)&mdash;_

test/topic_spec.js

@@ -22,3 +22,3 @@ /*globals rabbitmq_test_bindings : false,
     {
-        matcher = new qlobber.Qlobber();
+        matcher = new qlobber.Qlobber({ remove_duplicates: true });
         done();
@@ -50,3 +50,3 @@ });
         {
-            expect(matcher.match(test[0]), test[0]).to.eql(test[1].sort());
+            expect(matcher.match(test[0]).sort(), test[0]).to.eql(test[1].sort());
         });
@@ -69,3 +69,3 @@ });
         {
-            expect(matcher.match(test[0]), test[0]).to.eql(test[1].sort());
+            expect(matcher.match(test[0]).sort(), test[0]).to.eql(test[1].sort());
         });
@@ -89,3 +89,3 @@
         {
-            expect(matcher.match(test[0]), test[0]).to.eql(test[1].sort());
+            expect(matcher.match(test[0]).sort(), test[0]).to.eql(test[1].sort());
         });
@@ -102,3 +102,3 @@ });
         {
-            expect(matcher.match(test[0]), test[0]).to.eql(test[1].sort());
+            expect(matcher.match(test[0]).sort(), test[0]).to.eql(test[1].sort());
         });
@@ -120,3 +120,3 @@ });
         {
-            expect(matcher.match(test[0]), test[0]).to.eql(test[1].sort());
+            expect(matcher.match(test[0]).sort(), test[0]).to.eql(test[1].sort());
         });
@@ -127,20 +127,8 @@ });
     {
-        matcher = new qlobber.Qlobber(
-        {
-            compare: function (f1, f2)
-            {
-                return f1.topic < f2.topic ? -1 : f1.topic > f2.topic ? 1 : 0;
-            }
-        });
-
         add_bindings(rabbitmq_test_bindings, function (topic)
         {
-            var f = function ()
+            return function ()
             {
                 return topic;
             };
-
-            f.topic = topic;
-
-            return f;
         });
@@ -153,3 +141,3 @@
                 return f();
-            })).to.eql(test[1].sort());
+            }).sort()).to.eql(test[1].sort());
         });
@@ -177,3 +165,6 @@ });
                 'quick.orange.male.rabbit',
-                'lazy.orange.male.rabbit'].map(matcher.match)).to.eql(
+                'lazy.orange.male.rabbit'].map(function (topic)
+                {
+                    return matcher.match(topic).sort();
+                })).to.eql(
                [['Q1', 'Q2'],
@@ -180,0 +171,0 @@ ['Q1', 'Q2'],

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

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

26495

increased by0.83%

Lines of code

550

increased by4.56%

Number of lines in readme file

156

increased by2.63%

No dependency changes