radix-router - npm Package Compare versions

Comparing version 0.0.1 to 0.1.0

index.js

@@ -0,21 +1,68 @@
+'use strict';
 /**
- * JS Radix tree implementation 
+ * JS Radix Router implementation
  */
 
+// node types
+var NORMAL_NODE = 0;
+var WILDCARD_NODE = 1;
+var PLACEHOLDER_NODE = 2;
+
 /**
+ * Returns all children that match the prefix
+ *
+ * @param {Node} - the node to check children for
+ * @param {prefix} - the prefix to match
+ */
+function _getAllPrefixChildren(node, str) {
+    var nodes = [];
+    var children = node.children;
+    for (var i = 0; i < children.length; i++) {
+        // only need to check for first char
+        if (children[i].path[0] === str[0]) {
+            nodes.push(children[i]);
+        }
+    }
+    return nodes;
+}
+
+/**
+ * Returns the child matching the prefix
+ *
+ * @param {Node} - the node to check children for
+ * @param {prefix} - the prefix to match
+ */
+function _getChildNode(node, prefix) {
+    var children = node.children;
+    for (var i = 0; i < children.length; i++) {
+        if (children[i].path === prefix) {
+            return children[i];
+        }
+    }
+    return null;
+}
+
+/**
  * Retrieves the largest prefix of all children
+ *
+ * @param {object <string, Node>} children - a dictionary of childNodes
+ * @param {string} str - the string used to find the largest prefix with
  */
-function getLargestPrefix(children, str) {
-    let length = 0;
-
-    Object.keys(children).forEach(function(key) {
-        for (var i = 0; i < key.length; i++) {
-            if (str[i] !== key[i] || i > length) {
+function _getLargestPrefix(children, str) {
+    var index = 0;
+    for (let i = 0; i < children.length; i++) {
+        var path = children[i].path;
+        var totalIterations = Math.min(str.length, path.length);
+        for (; index < totalIterations; index++) {
+            if (str[index] !== path[index]) {
                 break;
             }
-            length = i + 1;
         }
-    });
+        if (index > 0) {
+            break;
+        }
+    }
 
-    return str.substring(0, length);
+    // largest prefix
+    return str.slice(0, index);
 }
@@ -25,36 +72,159 @@
  * Traverses the tree to find the node that the input string matches.
+ *
+ * @param {Node} node - the node to attempt to traverse
+ * @param {string} str - the string used as the basis for traversal
+ * @param {function} onExactMatch - the handler for exact matches
+ * @param {function} onPartialMatch - the handler for partial matches
+ * @param {function} onNoMatch - the handler for when no match is found
  */
-function lookup(node, str, options) {
+function _traverse(options) {
+    var node = options.node;
+    var str = options.str;
+    var onExactMatch = options.onExactMatch;
+    var onPartialMatch = options.onPartialMatch;
+    var onNoMatch = options.onNoMatch;
+    var onPlaceholder = options.onPlaceholder;
+    var data = options.data;
+
     var children = node.children;
-    var prefix = getLargestPrefix(children, str);
+    var childNode;
 
+    // check if a child is possibly a placeholder or a wildcard
+    // if wildcard is found, use it as a backup if no result is found,
+    // if placeholder is found, grab the data and traverse
+    var wildcardNode = null;
+    for (var i = 0; i < children.length; i++) {
+        childNode = children[i];
+        if (children[i].type === WILDCARD_NODE) {
+            wildcardNode = childNode;
+            break;
+        } else if (children[i].type === PLACEHOLDER_NODE) {
+            var key = childNode.path.slice(1);
+            var slashIndex = str.indexOf('/');
+            var param;
+            if (slashIndex !== -1) {
+                param = str.slice(0, slashIndex);
+            } else {
+                param = str;
+            }
+            options.node = children[i];
+            options.str = str.slice(param.length);
+
+            onPlaceholder(key, param, data);
+            // return the child node if there is nowhere else to go
+            // otherwise, traverse to the child
+            if (options.str.length === 0) {
+                return children[i];
+            }
+            return _traverse(options);
+        }
+    }
+
+    var prefix = _getLargestPrefix(children, str);
+
     // no matches, return null
     if (prefix.length === 0) {
-        return null;
-    } 
+        return onNoMatch(node, str, data) || wildcardNode;
+    }
 
+    // exact match with input string was found
+    if (prefix.length === str.length) {
+        return onExactMatch(node, prefix, str, data) || wildcardNode;
+    }
+
     // get child
-    let child = node.children[prefix];
-
-    // nowhere to go from here.
-    if (prefix.length === str.length) {
-        // delete node if node is passed,
-        // otherwise return the match
-        if (child && options && options.deleteNode) {
-            if (Object.keys(child.children).length ===  0) {
-                delete node.children[prefix];
-            } else {
-                delete child.data;
-            }
+    childNode = _getChildNode(node, prefix);
+    // child exists, continue traversing
+    if (childNode) {
+        options.node = childNode;
+        options.str = str.slice(prefix.length);
+        let result = _traverse(options);
+        // if no result, return the wildcard node
+        if (!result && wildcardNode) {
+            return wildcardNode;
+        } else {
+            return result;
         }
+    }
 
-        return child;
+    // partial match was found
+    return onPartialMatch(node, prefix, str, data) || wildcardNode;
+}
+
+/**
+ * Traverses all child nodes places the full resulting path into a map
+ *
+ * @param {Node} node - the node to attempt to traverse
+ * @param {string} str - the string that is the base of the key
+ * @param {object} map - the map to traverse the cobrowse event with
+ */
+function _traverseDepths(node, str, map) {
+    if (node.data) {
+        map[str] = node.data;
     }
 
-    // child exists, continue traversing
-    if (child) {
-        return lookup(child, str.substring(prefix.length), options);
+    node.children.forEach(function(child) {
+        _traverseDepths(child, str + child.path, map);
+    });
+}
+
+/**
+ * Helper function for creating a node based the path and data it is given
+ */
+function _createNode(path, data) {
+    let node;
+    if (path[0] === ':') {
+        node = new Node(path, data, PLACEHOLDER_NODE);
+    } else if (path === '**') {
+        node = new Node(path, data, WILDCARD_NODE);
+    } else {
+        // normal string to match
+        node = new Node(path, data);
     }
+    return node;
+}
 
-    return null;
+function _buildNodeChain(str, data) {
+    let parentNode;
+    let currentNode;
+    let startingPoint = 0;
+    let sections = str.split('/');
+    // first section is a special case, if it has real content, create a node
+    // otherwise, create an empty node
+    if (sections[startingPoint].length > 0) {
+        parentNode = currentNode = _createNode(sections[startingPoint]);
+    } else {
+        parentNode = currentNode = new Node('');
+    }
+    startingPoint++;
+
+    for (var i = startingPoint; i < sections.length; i++) {
+        let parseRemaining = true;
+        let newNode;
+
+        // add slash to last node if the last section was empty
+        if (i > 0 && sections[i - 1].length === 0){
+            currentNode.path += '/';
+        } else if (sections[i].length === 0) {
+            newNode = new Node('/');
+            parseRemaining = false;
+        } else {
+            var node = new Node('/');
+            currentNode.children.push(node);
+            node.parent = currentNode;
+            currentNode = node;
+        }
+
+        if (parseRemaining) {
+            let path = sections[i];
+            newNode = _createNode(path);
+        }
+
+        currentNode.children.push(newNode);
+        newNode.parent = currentNode;
+        currentNode = newNode;
+    }
+    currentNode.data = data;
+
+    return parentNode;
 }
@@ -65,11 +235,17 @@
  * parent node and the two resulting nodes from the split
+ *
+ * @param {Node} node - the node to split
+ * @param {string} prefix - the largest prefix found
+ * @param {string} str - the leftover parts of the input string
+ * @param {object} data - the data to store in the new node
  */
-function splitNode(node, prefix, str, data) {
-    var length = 0;
-    var closestMatch;
+function _splitNode(node, prefix, str, data) {
+    var originalNode;
+    var oldIndex;
 
-    var keys = Object.keys(node.children);
-    for (var i = 0; i < keys.length; i++) {
-        if (keys[i].startsWith(prefix)) {
-            closestMatch = keys[i];
+    var children = node.children;
+    for (var i = 0; i < children.length; i++) {
+        if (children[i].path.startsWith(prefix)) {
+            originalNode = children[i];
+            oldIndex = i;
             break;
@@ -80,50 +256,123 @@ }
     var newLink = str.substring(prefix.length);
-    var oldLink = closestMatch.substring(prefix.length);
+    var oldLink = originalNode.path.substring(prefix.length);
 
-    var originalNode = node.children[closestMatch];
-    var newNode = new Node(data);
-    var intermediateNode = new Node();
+    // set new path
+    originalNode.path = oldLink;
+    var newNode = _buildNodeChain(newLink, data);
+    var intermediateNode = new Node(prefix);
 
     originalNode.parent = intermediateNode;
     newNode.parent = intermediateNode;
+    intermediateNode.parent = node;
 
-    intermediateNode.children[oldLink] = originalNode;
-    intermediateNode.children[newLink] = newNode;
+    intermediateNode.children.push(originalNode);
+    intermediateNode.children.push(newNode);
 
-    node.children[prefix] = intermediateNode;
+    node.children.push(intermediateNode);
 
-    delete node.children[closestMatch];
+    // remove old node the list of children
+    node.children.splice(oldIndex, 1);
+    return newNode;
 }
 
-/**
- * Inserts node with the given data into the tree
- */
-function put(node, str, data) {
-    var children = node.children;
-    var prefix = getLargestPrefix(children, str);
+// handle exact matches
+var EXACT_MATCH_HANDLERS = {
+    'insert': function(node, prefix, str, data) {
+        var childNode = _getChildNode(node, prefix);
+        childNode.data = data;
+        return node;
+    },
+    'delete': function(parentNode, prefix) {
+        var childNode = _getChildNode(parentNode, prefix);
+        if (childNode.children.length ===  0) {
+            // delete node from parent
+            for (var i = 0; i < parentNode.children.length; i++) {
+                if (parentNode.children[i].path === prefix) {
+                    break;
+                }
+            }
+            parentNode.children.splice(i, 1);
+        } else {
+            delete childNode.data;
+        }
+        return childNode;
+    },
+    'lookup': function(node, prefix) {
+        var discoveredNode = _getChildNode(node, prefix);
+        return discoveredNode;
+    },
+    'startsWith': function(node, prefix, str) {
+        var childNode = _getChildNode(node, prefix);
+        if (childNode) {
+            return childNode;
+        }
+        return _getAllPrefixChildren(node, prefix);
+    }
+};
 
-    // no prefix match
-    if (prefix.length === 0) {
-        // drop in the node
-        var newNode = node.children[str] = new Node(data);
-        newNode.parent = node;
-        return;
-    } 
+// handle situations where there is a partial match
+var PARTIAL_MATCH_HANDLERS = {
+    'insert': function(node, prefix, str, data) {
+        var newNode = _splitNode(node, prefix, str, data);
+        return newNode;
+    },
+    'delete': function() {
+        return null;
+    },
+    'lookup': function(node) {
+        return null;
+    },
+    'startsWith': function(node, prefix) {
+        return _getAllPrefixChildren(node, prefix);
+    }
+};
 
-    if (prefix.length === str.length) {
-        // exact match found, set data in node
-        node.children[prefix].data = data;
-        return;
+// handle situtations where there is no match
+var NO_MATCH_HANDLERS = {
+    'insert': function(parentNode, str, data) {
+        var newNode = _buildNodeChain(str, data);
+        parentNode.children.push(newNode);
+        newNode.parent = parentNode;
+        return newNode;
+    },
+    'delete': function() {
+        return null;
+    },
+    'lookup': function() {
+        return null;
+    },
+    'startsWith': function() {
+        return null;
     }
+};
 
-    // if match found, continue traversing, else
-    // partial match was found, split the node
-    var child = node.children[prefix];
-    if (child) {
-        put(child, str.substring(prefix.length), data);
-    } else {
-        splitNode(node, prefix, str, data);
-    }
+// handle situations where a place holder was found
+var PLACEHOLDER_HANDLERS = {
+    'lookup': function(key, param, data) {
+        if (!data.params) {
+            data.params = {};
+        }
+        data.params[key] = param;
+    },
+    // no ops, (maybe
+    'delete': function() {},
+    'insert': function() {},
+    'startsWith': function() {}
+};
+
+/**
+ * Helper method for retrieving all needed action handlers
+ *
+ * @param {string} action - the action to perform
+ */
+function _getHandlers(action) {
+    return {
+        onExactMatch: EXACT_MATCH_HANDLERS[action],
+        onPartialMatch: PARTIAL_MATCH_HANDLERS[action],
+        onNoMatch: NO_MATCH_HANDLERS[action],
+        onPlaceholder: PLACEHOLDER_HANDLERS[action]
+    };
 }
 
+
 function _validateInput(str) {
@@ -135,9 +384,40 @@ if (typeof str !== 'string') {
 
-function Node(data) {
+/**
+ * Kicks off the traversal
+ *
+ * @param {Node} rootNode - the node to start from
+ * @param {string} action - the action to perform, this will be used to get handlers
+ * @param {string} input - the string to use for traversal
+ * @param {object} data - the object to store in the Radix Tree
+ */
+function _startTraversal(rootNode, action, input, data) {
+    var handlers = _getHandlers(action);
+    return _traverse({
+        node: rootNode,
+        str: input,
+        onExactMatch: handlers.onExactMatch,
+        onPartialMatch: handlers.onPartialMatch,
+        onNoMatch: handlers.onNoMatch,
+        onPlaceholder: handlers.onPlaceholder,
+        data: data
+    });
+}
+
+/**
+ * Node of the Radix Tree
+ * @constructor
+ */
+function Node(path, data, type) {
+    this.type = type || NORMAL_NODE;
+    this.path = path;
     this.parent = undefined;
-    this.children = {};
-    this.data = data;
+    this.children = [];
+    this.data = data || null;
 }
 
-function RadixTree(options) {
+/**
+ * The Radix Router
+ * @constructor
+ */
+function RadixRouter(options) {
     this._rootNode = new Node();
@@ -148,23 +428,41 @@ // TODO: handle routes passed in via options
 
-RadixTree.prototype = {
+RadixRouter.prototype = {
     lookup: function(input) {
-        let node = lookup(this._rootNode, input);
-        return node && node.data;
+        _validateInput(input);
+        var result = {
+            data: null
+        };
+        var node = _startTraversal(this._rootNode, 'lookup', input, result);
+        result.data = node ? node.data : null;
+        return result;
     },
 
     startsWith: function(prefix) {
-        // TODO: complete this
+        _validateInput(prefix);
+        var result = _startTraversal(this._rootNode, 'startsWith', prefix);
+
+        var map = {};
+        if (result instanceof Node) {
+            _traverseDepths(result, prefix, map);
+        } else {
+            result.forEach(function(child) {
+                _traverseDepths(child,
+                    prefix.substring(0, prefix.indexOf(child.path[0])) + child.path,
+                    map);
+            });
+        }
+        return map;
     },
 
     insert: function(input, data) {
-        put(this._rootNode, input, data);
+        _validateInput(input);
+        return _startTraversal(this._rootNode, 'insert', input, data);
     },
 
     delete: function(input) {
-        lookup(this._rootNode, input, {
-            deleteNode: true
-        });
+        _validateInput(input);
+        return _startTraversal(this._rootNode, 'delete', input);
     }
 };
 
-module.exports = RadixTree;
+module.exports = RadixRouter;

package.json

 {
   "devDependencies": {
+    "benchmark": "^2.1.2",
     "chai": "^3.5.0",
-    "mocha": "^3.1.2"
+    "git-hooks": "^1.1.6",
+    "jscs": "^3.0.7",
+    "jshint": "^2.9.4",
+    "mocha": "^3.1.2",
+    "path-based-router": "^1.1.3",
+    "radix-tree": "^0.3.4"
   },
   "name": "radix-router",
-  "version": "0.0.1",
+  "version": "0.1.0",
   "description": "Radix tree based router",
@@ -9,0 +15,0 @@ "main": "index.js",

README.md

@@ -1,5 +0,10 @@
-# Radix Tree
+# Radix Router
 
-A simple radix tree (compact prefix tree) implementation.
+(Not complete yet!)
 
-(Not complete yet)
+A simple router implemented using a [Radix Tree](https://en.wikipedia.com/wiki/Radix_tree) (aka compact [Prefix Tree](https://en.wikipedia.com/wiki/Trie)).
+
+Todo: 
+- Allow routes to be specified in constructor
+- Add support for wild card matching (`/path/**`)
+- Allow for placeholders to be matched (`/path/:match`)

tests/radix-tree-test.js

@@ -1,6 +0,9 @@
-let {expect} = require('chai');
+const {expect} = require('chai');
+const util = require('util');
+
 let RadixTree = require('../index');
 
 describe('Radix Tree', () => {
-    it('should be able to insert nodes correctly into the tree', () => {
+    // TODO: Redo this portion to show valid structure
+    it.skip('should be able to insert nodes correctly into the tree', () => {
         let tree = new RadixTree();
@@ -14,3 +17,2 @@ tree.insert('hello');
         tree.insert('choot');
-
         /**
@@ -40,2 +42,3 @@ * Expected structure:
         expect(h2_node.children['oot']).to.not.equal(undefined);
+        
     });
@@ -48,14 +51,50 @@
         tree.insert('hi', 3);
-        tree.insert('helium', 4);
+        tree.insert('heli//u/m', 4);
         tree.insert('coooool', 5);
         tree.insert('chrome', 6);
         tree.insert('choot', 7);
+        tree.insert('chrome/coooo/il/li/iloool', 9)
+        tree.insert('//chrome//coooo/il/li/iloool', 10)
+        tree.insert('/chrome//coooo/il/li/iloool', 11)
+        tree.insert('chrome/**', 12);
+        tree.insert('chrome/*/coooo/il/li/iloool', 13);
+        tree.insert('carbon/:element', 14);
+        tree.insert('carbon/:element/test/:testing', 15);
+        tree.insert('this/:route/has/:cool/stuff/**', 16);
         
-        expect(tree.lookup('hello')).to.equal(1);
-        expect(tree.lookup('cool')).to.equal(2);
-        expect(tree.lookup('hi')).to.equal(3);
-        expect(tree.lookup('helium')).to.equal(4);
-        expect(tree.lookup('coooool')).to.equal(5);
-        expect(tree.lookup('chrome')).to.equal(6);
-        expect(tree.lookup('choot')).to.equal(7);
+        expect(tree.lookup('hello')).to.deep.equal({data: 1});
+        expect(tree.lookup('cool')).to.deep.equal({data: 2});
+        expect(tree.lookup('hi')).to.deep.equal({data: 3});
+        expect(tree.lookup('heli//u/m')).to.deep.equal({data: 4});
+        expect(tree.lookup('coooool')).to.deep.equal({data: 5});
+        expect(tree.lookup('chrome')).to.deep.equal({data: 6});
+        expect(tree.lookup('choot')).to.deep.equal({data: 7});
+        expect(tree.lookup('chrome/coooo/il/li/iloool')).to.deep.equal({data: 9});
+        expect(tree.lookup('chrome/*/coooo/il/li/iloool')).to.deep.equal({data: 13});
+        expect(tree.lookup('carbon/test1')).to.deep.equal({
+            data: 14, 
+            params: {
+                'element': 'test1'
+            }
+        });
+        expect(tree.lookup('carbon/test2/test/test23')).to.deep.equal({
+            data: 15,
+            params: {
+                'element': 'test2',
+                'testing': 'test23'
+            }
+        });
+        expect(tree.lookup('this/test/has/more/stuff/seflijsfelisjef')).to.deep.equal({
+            data: 16,
+            params: {
+                route: 'test',
+                cool: 'more'
+            }
+        });
+        expect(tree.lookup('this/is')).to.deep.equal({
+            data: null,
+            params: {
+                route: 'is'
+            }
+        });
     });
@@ -74,6 +113,8 @@
         tree.delete('choot');
-        expect(tree.lookup('choot')).to.equal(null);
+        expect(tree.lookup('choot')).to.deep.equal({
+            data: null
+        });
     });
 
-    it('should be able retrieve data via prefix', () => {
+    it('should be able retrieve all results via prefix', () => {
         let tree = new RadixTree();
@@ -87,5 +128,13 @@ tree.insert('hello', 1);
         tree.insert('choot', 7);
-        // TODO: complete
-        
+        tree.insert('chromium', 8);
+
+        let setA = tree.startsWith('h');
+        expect(setA.hasOwnProperty('hello')).to.equal(true);
+        expect(setA.hasOwnProperty('hi')).to.equal(true);
+        expect(setA.hasOwnProperty('helium')).to.equal(true);
+
+        let setB = tree.startsWith('chro');
+        expect(setB.hasOwnProperty('chrome')).to.equal(true);
+        expect(setB.hasOwnProperty('chromium')).to.equal(true);
     });
 });

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

47363

increased by222.07%

Number of package files

14

increased by100%

Lines of code

538

increased by156.19%

Number of lines in readme file

11

increased by83.33%

Worsened metrics

Dev dependency count

8

increased by300%

Number of medium supply chain risk alerts

1

increased byInfinity%

No dependency changes