		@@ -12,515 +12,98 @@ 'use strict'

		/**
		* 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
		}
		function _validateInput (path, strictPaths) {
		assert(path, '"path" must be provided')
		assert(typeof path === 'string', '"path" must be that of a string')

		/**
		* 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]
		}
		// allow for trailing slashes to match by removing it
		if (!strictPaths && path.length > 1 && path[path.length - 1] === '/') {
		path = path.slice(0, path.length - 1)
		}
		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) {
		var index = 0
		for (var i = 0; i < children.length; i++) {
		var path = children[i].path
		var totalIterations = Math.min(str.length, path.length)
		while (index < totalIterations) {
		if (str[index] !== path[index]) {
		break
		}
		index++
		}
		if (index > 0) {
		break
		}
		}

		// largest prefix
		return str.slice(0, index)
		return path
		}

		/**
		* 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
		* Node of the Radix Tree
		* @constructor
		*/
		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
		function Node (options) {
		options = options \|\| {}
		this.type = options.type \|\| NORMAL_NODE

		var children = node.children
		var childNode
		// if placeholder node
		this.paramName = options.paramName \|\| null

		// 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
		if (onPlaceholder) {
		for (var i = 0; i < children.length; i++) {
		childNode = children[i]
		if (children[i].type === WILDCARD_NODE) {
		wildcardNode = childNode
		} else if (children[i].type === PLACEHOLDER_NODE) {
		var key = childNode.path.slice(1)
		var slashIndex = str.indexOf('/')
		this.parent = options.parent \|\| null
		this.children = {}
		this.data = options.data \|\| null

		var param
		if (slashIndex !== -1) {
		param = str.slice(0, slashIndex)
		} else {
		param = str
		}

		options.node = children[i]
		options.str = str.slice(param.length)

		return onPlaceholder({
		key: key,
		param: param,
		options: options,
		childNode: childNode
		})
		}
		}
		}

		var prefix = _getLargestPrefix(children, str)

		// no matches, return null
		if (prefix.length === 0) {
		return onNoMatch(options) \|\| wildcardNode
		}

		// exact match with input string was found
		if (prefix.length === str.length) {
		return onExactMatch({
		node: node,
		prefix: prefix,
		str: str,
		data: data
		}) \|\| wildcardNode
		}

		// get child
		childNode = _getChildNode(node, prefix)

		// child exists, continue traversing
		if (childNode) {
		options.node = childNode
		options.str = str.slice(prefix.length)
		var result = _traverse(options)
		// if no result, return the wildcard node
		if (!result && wildcardNode) {
		return wildcardNode
		} else {
		return result
		}
		}

		// partial match was found
		return onPartialMatch({
		node: node,
		prefix: prefix,
		str: str,
		data: data
		}) \|\| wildcardNode
		// keep track of special child nodes
		this.wildcardChildNode = null
		this.placeholderChildNode = null
		}

		/**
		* 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, array) {
		if (node.data) {
		array.push(node.data)
		}
		function _getNodeType (str) {
		var type

		node.children.forEach(function (child) {
		_traverseDepths(child, str + child.path, array)
		})
		}

		/**
		* Helper function for creating a node based the path and data it is given
		*/
		function _createNode (path, data) {
		var node
		if (path[0] === ':') {
		node = new Node(path, data, PLACEHOLDER_NODE)
		} else if (path === '**') {
		node = new Node(path, data, WILDCARD_NODE)
		if (str[0] === ':') {
		type = PLACEHOLDER_NODE
		} else if (str === '**') {
		type = WILDCARD_NODE
		} else {
		// normal string to match
		node = new Node(path, data)
		type = NORMAL_NODE
		}
		return node
		}

		function _buildNodeChain (str, data) {
		var parentNode
		var currentNode
		var startingPoint = 0

		// if the string is just a single slash, return the node
		// otherwise just slash the node
		if (str.length === 0 \|\| str === '/') {
		return new Node('/', data)
		}

		var 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++) {
		var parseRemaining = true
		var 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) {
		var path = sections[i]
		newNode = _createNode(path)
		}

		currentNode.children.push(newNode)
		newNode.parent = currentNode
		currentNode = newNode
		}

		// if the last node's path is empty, remove it.
		if (currentNode.path === '') {
		currentNode.parent.children = []
		currentNode.parent.data = data
		} else {
		currentNode.data = data
		}

		return parentNode
		return type
		}

		/**
		* Splits a node in half, placing an intermediary node between the
		* 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 originalNode
		var oldIndex
		function _findNode (path, rootNode) {
		var sections = path.split('/')

		var children = node.children
		for (var i = 0; i < children.length; i++) {
		if (children[i].path.startsWith(prefix)) {
		originalNode = children[i]
		oldIndex = i
		break
		}
		}
		// optimization: pushing to an array is much faster than setting
		// a value in an object, so store params as array
		var params = []
		var wildcardNode = null
		var node = rootNode

		var newLink = str.substring(prefix.length)
		var oldLink = originalNode.path.substring(prefix.length)
		for (var i = 0; i < sections.length; i++) {
		var section = sections[i]

		// 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.push(originalNode)
		intermediateNode.children.push(newNode)

		node.children.push(intermediateNode)

		// remove old node the list of children
		node.children.splice(oldIndex, 1)
		return newNode
		}

		// handle exact matches
		var EXACT_MATCH_HANDLERS = {
		'insert': function (options) {
		var node = options.node
		var prefix = options.prefix
		var data = options.data
		var childNode = _getChildNode(node, prefix)
		childNode.data = data
		return node
		},
		'remove': function (options) {
		var parentNode = options.node
		var prefix = options.prefix
		var result = options.data

		var childNode = _getChildNode(parentNode, prefix)

		if (childNode.data) {
		result.success = true
		if (node.wildcardChildNode !== null) {
		wildcardNode = node.wildcardChildNode
		}

		if (childNode.children.length === 0) {
		// remove node from parent
		for (var i = 0; i < parentNode.children.length; i++) {
		if (parentNode.children[i].path === prefix) {
		break
		}
		// exact matches take precedence over placeholders
		var nextNode = node.children[section]
		if (nextNode !== undefined) {
		node = nextNode
		} else {
		node = node.placeholderChildNode
		if (node !== null) {
		params.push(section)
		} else {
		break
		}
		parentNode.children.splice(i, 1)

		if (parentNode.children.length === 1) {
		var lastChildNode = parentNode.children[0]
		if (parentNode.data && Object.keys(parentNode.data).length === 1) {
		// no real data is associated with the parent
		if (parentNode.type === NORMAL_NODE && parentNode.path !== '/' &&
		lastChildNode.type === NORMAL_NODE && lastChildNode.path !== '/') {
		// child node just a regular node, merge them together
		parentNode.children = []
		parentNode.path += lastChildNode.path
		parentNode.data = lastChildNode.data
		parentNode.data.path = parentNode.path
		}
		}
		}
		} else {
		childNode.data = null
		}

		return childNode
		},
		'lookup': function (options) {
		var node = options.node
		var prefix = options.prefix
		var discoveredNode = _getChildNode(node, prefix)
		return discoveredNode
		},
		'startsWith': function (options) {
		var node = options.node
		var prefix = options.prefix
		var childNode = _getChildNode(node, prefix)
		if (childNode) {
		return childNode
		}
		return _getAllPrefixChildren(node, prefix)
		}
		}

		// handle situations where there is a partial match
		var PARTIAL_MATCH_HANDLERS = {
		'insert': function (options) {
		var node = options.node
		var prefix = options.prefix
		var str = options.str
		var data = options.data
		var newNode = _splitNode(node, prefix, str, data)
		return newNode
		},
		'remove': function () {
		return null
		},
		'lookup': function () {
		return null
		},
		'startsWith': function (options) {
		var node = options.node
		var prefix = options.prefix
		return _getAllPrefixChildren(node, prefix)
		if ((node === null \|\| node.data === null) && wildcardNode !== null) {
		node = wildcardNode
		}
		}

		// handle situtations where there is no match
		var NO_MATCH_HANDLERS = {
		'insert': function (options) {
		var parentNode = options.node
		var str = options.str
		var data = options.data
		var newNode = _buildNodeChain(str, data)
		parentNode.children.push(newNode)
		newNode.parent = parentNode
		return newNode
		},
		'remove': function () {
		return null
		},
		'lookup': function () {
		return null
		},
		'startsWith': function () {
		return []
		}
		}

		function _onPlaceholder (placeholderOptions) {
		var options = placeholderOptions.options
		var childNode = options.node
		var parentNode = options.node.parent
		var str = options.str
		var data = options.data

		// return the child node if there is nowhere else to go
		// otherwise, traverse to the child
		if (options.str.length === 0) {
		return options.onExactMatch({
		node: parentNode,
		prefix: childNode.path,
		str: str,
		data: data
		})
		}
		return _traverse(options)
		}

		// handle situations where a place holder was found
		var PLACEHOLDER_HANDLERS = {
		// lookup handles placeholders differently
		'lookup': function (placeholderOptions) {
		var key = placeholderOptions.key
		var param = placeholderOptions.param
		var options = placeholderOptions.options
		var data = options.data

		if (!data.params) {
		data.params = {}
		}
		data.params[key] = param

		if (options.str.length === 0) {
		return options.node
		}

		return _traverse(options)
		},

		// inserts shouldn't care about placeholders at all
		'insert': null,
		'remove': _onPlaceholder,
		'startsWith': _onPlaceholder
		}

		/**
		* 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]
		node: node,
		params: params
		}
		}

		function _validateInput (input, strictPaths) {
		var path = input
		assert(path, '"path" must be provided')
		assert(typeof path === 'string', '"path" must be that of a string')
		function _getAllNodesWithData (node, resultArray) {
		var keys = Object.keys(node.children)

		// allow for trailing slashes to match by removing it
		if (!strictPaths && path.length > 1 && path[path.length - 1] === '/') {
		path = path.slice(0, path.length - 1)
		for (var i = 0; i < keys.length; i++) {
		var nextNode = node.children[keys[i]]
		_getAllNodesWithData(nextNode, resultArray)
		}

		return path
		}

		/**
		* 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 \|\| null
		}

		/**
		* The Radix Router
		@@ -533,2 +116,3 @@ * @constructor
		self._strictMode = options && options.strict
		self._staticRoutesMap = {}

		@@ -554,13 +138,21 @@ // handle insertion of routes passed into constructor
		path = _validateInput(path, self._strictMode)
		var data = {}

		// find the node
		var node = _startTraversal(self._rootNode, 'lookup', path, data)
		var result = node && node.data
		// optimization, if a route is static and does not have any
		// variable sections, retrieve from a static routes map
		var staticPathNode
		if ((staticPathNode = self._staticRoutesMap[path])) {
		return staticPathNode.data
		}

		if (result && data.params) {
		result.params = data.params
		var result = _findNode(path, self._rootNode)
		var node = result.node
		var params = result.params

		var data = (node !== null && node.data) \|\| null

		if (data !== null && params.length > 0) {
		data.params = params
		}

		return result
		return data
		},
		@@ -577,15 +169,37 @@
		var self = this
		_validateInput(prefix, self._strictMode)
		var result = _startTraversal(self._rootNode, 'startsWith', prefix)
		prefix = _validateInput(prefix, self._strictMode)

		var sections = prefix.split('/')
		var node = self._rootNode
		var resultArray = []
		if (result instanceof Node) {
		_traverseDepths(result, prefix, resultArray)
		} else {
		result.forEach(function (child) {
		_traverseDepths(child,
		prefix.substring(0, prefix.indexOf(child.path[0])) + child.path,
		resultArray)
		})

		for (var i = 0; i < sections.length; i++) {
		var section = sections[i]

		if (node.data) {
		resultArray.push(node.data)
		}

		var nextNode = node.children[section]

		if (nextNode !== undefined) {
		node = nextNode
		} else if (i === sections.length - 1) {
		var keys = Object.keys(node.children)

		for (var j = 0; j < keys.length; j++) {
		var key = keys[j]

		if (key.startsWith(section)) {
		nextNode = node.children[key]

		if (nextNode.data) {
		resultArray.push(nextNode.data)
		}
		_getAllNodesWithData(nextNode, resultArray)
		}
		}
		}
		}

		return resultArray
		@@ -604,5 +218,54 @@ },
		var path = data.path
		var isStaticRoute = true

		path = _validateInput(path, self._strictMode)
		_startTraversal(self._rootNode, 'insert', path, data)

		var sections = path.split('/')

		var node = self._rootNode

		for (var i = 0; i < sections.length; i++) {
		var section = sections[i]

		var children = node.children
		var childNode

		if ((childNode = children[section])) {
		node = childNode
		} else {
		var type = _getNodeType(section)

		// create new node to represent the next
		// part of the path
		childNode = new Node({
		type: type,
		parent: node
		})

		node.children[section] = childNode

		if (type === PLACEHOLDER_NODE) {
		childNode.paramName = section.slice(1)
		node.placeholderChildNode = childNode
		isStaticRoute = false
		} else if (type === WILDCARD_NODE) {
		node.wildcardChildNode = childNode
		isStaticRoute = false
		}

		node = childNode
		}
		}

		// store whatever data was provided into the node
		node.data = data

		// optimization, if a route is static and does not have any
		// variable sections, we can store it into a map for faster
		// retrievals
		if (isStaticRoute === true) {
		self._staticRoutesMap[path] = node
		}

		return node
		},
		@@ -620,5 +283,28 @@
		path = _validateInput(path, self._strictMode)
		var result = { success: false }
		_startTraversal(self._rootNode, 'remove', path, result)
		return result.success

		var success = false
		var sections = path.split('/')
		var node = self._rootNode

		for (var i = 0; i < sections.length; i++) {
		var section = sections[i]
		node = node.children[section]
		if (!node) {
		break
		}
		}

		if (node && node.data) {
		var lastSection = sections[sections.length - 1]
		node.data = null
		if (Object.keys(node.children).length === 0) {
		var parentNode = node.parent
		delete parentNode[lastSection]
		parentNode.wildcardChildNode = null
		parentNode.placeholderChildNode = null
		}
		success = true
		}

		return success
		}
		@@ -625,0 +311,0 @@ }

package.json

		@@ -19,3 +19,3 @@ {
		"name": "radix-router",
		"version": "1.0.0",
		"version": "2.0.0",
		"description": "Radix tree based router",
		@@ -22,0 +22,0 @@ "main": "index.js",

README.md

		@@ -6,4 +6,4 @@ # Radix Router

		A router implemented using a [Radix Tree](https://en.wikipedia.com/wiki/Radix_tree) (aka compact [Prefix Tree](https://en.wikipedia.com/wiki/Trie)).
		This router has support for placeholders and wildcards.
		A fast, simple path router that is optimized for consistently fast lookups. This router
		has support for placeholders and wildcards.

		@@ -24,3 +24,4 @@ ### Installation
		- `routes` - The routes to insert into the router.
		- `strict` - Setting this option to `true` will force lookups to match exact paths (trailing slashes will not be ignored). Defaults to `false`.
		- `strict` - Setting this option to `true` will force lookups to match exact paths
		(trailing slashes will not be ignored). Defaults to `false`.

		@@ -150,4 +151,8 @@ ```js
		content fills the position of the placeholder will be added to the lookup result
		under the `params` attribute.
		under the `params` attribute. The results within `params` is sorted by its occurrence
		in the route.

		Note: Route placeholder params are placed into an array as an optimization. Your route handlers
		should be aware of the order placeholders are defined in the routes.

		Example:
		@@ -160,2 +165,7 @@
		})

		router.insert(
		path: '/api/v3/:organizations/directory/:groupId',
		very: 'placeholder'
		})
		```
		@@ -168,6 +178,13 @@
		very: 'placeholder',
		params: {
		myPlaceholder: 'application'
		}
		params: [ 'application' ]
		}
		```

		Output of `router.lookup('/api/v3/test-org/directory/test-group-id')`:
		```js
		{
		path: '/api/v3/:organizations/directory/:groupId',
		very: 'placeholder',
		params: [ 'test-org', 'test-group-id' ]
		}
		```

tests/lookup-test.js

		@@ -42,28 +42,24 @@ var expect = require('chai').expect
		data: 14,
		params: {
		'element': 'test1'
		}
		params: [ 'test1' ]
		})

		expect(router.lookup('carbon')).to.deep.equal(null)
		expect(router.lookup('carbon/')).to.deep.equal(null)

		expect(router.lookup('carbon/test1')).to.deep.equal({
		path: 'carbon/:element',
		data: 14,
		params: {
		'element': 'test1'
		}
		params: [ 'test1' ]
		})

		expect(router.lookup('carbon/test2/test/test23')).to.deep.equal({
		path: 'carbon/:element/test/:testing',
		data: 15,
		params: {
		'element': 'test2',
		'testing': 'test23'
		}
		params: [ 'test2', 'test23' ]
		})

		expect(router.lookup('this/test/has/more/stuff')).to.deep.equal({
		path: 'this/:route/has/:cool/stuff',
		data: 16,
		params: {
		route: 'test',
		cool: 'more'
		}
		params: [ 'test', 'more' ]
		})
		@@ -70,0 +66,0 @@ })

tests/remove-test.js

+@@ -39,5 +39,3 @@ var expect = require('chai').expect
+      path: 'placeholder/:choo',
+      params: {
+        choo: 'route'
+      },
+      params: [ 'route' ],
+      data: 8
+@@ -51,6 +49,3 @@ })
+      path: 'placeholder/:choo/:choo2',
+      params: {
+        choo: 'route',
+        choo2: 'route2'
+      },
+      params: [ 'route', 'route2' ],
+      data: 8
+@@ -57,0 +52,0 @@ })

tests/structure-test.js

radix-router - npm Package Compare versions

New alerts

Fixed alerts

Improved metrics

Worsened metrics