digital-tree - npm Package Compare versions

Comparing version 1.0.2 to 2.0.0

index.js

@@ -1,136 +0,286 @@
-var debug = require('debug')('digital-tree')
+const { isString, isFunction } = require('util')
+const debug = require('./lib/debug')('Trie')
+const _DFS = Symbol('dfs')
+const _BFS = Symbol('bfs')
+const HashMapNode = require('./lib/HashMapNode')
+const TrieIterator = require('./lib/TrieIterator')
+const NoopIterator = require('./lib/NoopIterator')
 
-module.exports = Trie
+const noopIterator = new NoopIterator()
 
-function Trie() {
-	this._data = {}
-}
+class Trie {
 
-/**
- *	put something in the tree.
- *
- *	@param {Array} key - each member in the array is a level in the tree
- *	@param {variant} value - the value to store
- *
- */
-Trie.prototype.put = function (key, value) {
-	debug('put( {%s}, {%s} )', key, value)
-	var current = this._data
+	static get DFS() { return _DFS }
+	static get BFS() { return _BFS }
 
-	for (var i = 0; i < key.length; i++) {
-		var node = key[i]
+	/**
+	 *    Create a new Trie
+	 *    
+	 *    @param  {variant} [options.rootValue]	The root value of the trie, normally you will not use this.
+	 *    @param  {Symbol} [options.iterationOrder=Trie.DFS] The trie is `iterable`, setting this will change the default iteration order.
+	 *    iteration order can be either `Trie.BFS` or `Trie.DFS`. You can still use an explicit iteration order by calling `trie.bfsIterator()` or `trie.dfsIterator()`
+	 *    @param  {HashMapNode} [options.NodeClass=HashMapNode] 
+	 *    
+	 *    @return {Trie}
+	 */
+	static create({
+		iterationOrder = _DFS,
+		NodeClass = HashMapNode
+	} = {}) {
 
-		if (current[node] === undefined)
-			current[node] = {}
+		if (iterationOrder !== _DFS && iterationOrder !== _BFS) {
+			throw new Error('invalid iteration order, try Trie.BFS or Trie.DFS')
+		}
 
-		current = current[node]
+		return new Trie({ NodeClass, iterationOrder })
 	}
 
-	current.$ = value
-}
+	constructor({ NodeClass, iterationOrder }) {
+		this._nodeClass = NodeClass
+		this._root = this._newNode()
+		this._iterationOrder = iterationOrder
+	}
 
-/**
- *	remove something from the tree
- *
- *	@param {Array} key
- *
- *	@return {Object} subtree that was removed
- */
-Trie.prototype.remove = function (key) {
-	debug('remove( {%s} )', key)
+	/**
+	 *	put something in the tree.
+	 *
+	 *	@param {Iterable} key - each member in the array is a level in the tree
+	 *	@param {variant} [value=true] - the value to store
+	 *
+	 */
+	put(key, value = true) {
+		debug('put( {%s}, {%s} )', key, value)
 
-	var current = this._data
-	var parent
+		if (!this._isValidKey(key)) {
+			throw new Error('invalid key')
+		}
 
-	// find the path, return nothing if its not there
-	for (var i = 0; i < key.length; i++) {
-		var node = key[i]
+		let current = this._root
+		let count = 0
 
-		if (current[node] === undefined)
-			return
+		for (let part of key) {
+			let node = current.getChild(part)
 
-		parent = current
-		current = current[node]
+			if (node === undefined) {
+				node = this._newNode()
+				current.addChild(part, node)
+			}
+
+			count++
+			current = node
+		}
+
+		// prevent "losing" a value in root 
+		// if iterable was "empty"
+		// empty interables doesn't make sense anyways
+		if (count === 0) {
+			throw new Error('invalid key')
+		}
+
+		current.value = value
 	}
 
-	var last = key[key.length - 1]
-	var subtree = parent[last]
-	
-	if (parent) {
-		delete parent[last]
+	putAll(iterable) {
+		for (let key of iterable) {
+			this.put(key, true)
+		}
 	}
 
-	return subtree
-}
+	/**
+	 *	get something from the tree.
+	 *
+	 *	@param {Iterable} [key] - a path in the tree.
+	 *
+	 *	@return {variant} the value that was placed under that key
+	 */
+	get(key) {
+		debug('get( {%s} )', key)
+		const current = this._getNode(key)
+		if (current === undefined) return
+		return current.value
+	}
 
-/**
- *	get something from the tree
- *
- *	@param {Array} key
- *
- *	@return {variant} the value that was placed under that key
- */
-Trie.prototype.get = function(key) {
-	debug('get( {%s} )', key)
-	var current = this._data
+	/**
+	 *    get a Trie view of the tree under "key"
+	 *    
+	 *    @param {Iterable}  key 
+	 *    @param {boolean} [shallow] defaults to false
+	 *    
+	 *    @return {Trie} 
+	 */
+	getSubTrie(key, shallow = false) {
+		debug('getSubTrie( {%s} }', key)
 
-	for (var i = 0; i < key.length; i++) {
-		var node = key[i]
+		const current = this._getNode(key)
+		return this._newTrieLikeThis(current, shallow)
+	}
 
-		if (current[node] === undefined)
-			return undefined
+	/**
+	 *    clone this trie.
+	 *
+	 *    - Object keys will not be cloned
+	 *    
+	 *    @return {Trie}
+	 */
+	clone() {
+		return this._newTrieLikeThis(this._root)
+	}
 
-		current = current[node]
+	/**
+	 *	remove something from the tree
+	 *
+	 *	@param {Iterable} key
+	 *
+	 *	@return {Trie} subtree that was removed
+	 */
+	remove(key) {
+		// this whole thing can go away if HashMapNode will have a 
+		// parent reference... then removeChild() will not have
+		// to accept keyPart
+		const { current, parent, keyPart } = this._getNodeAndParent(key)
+
+		if (current === undefined) return
+
+		parent.removeChild(keyPart)
+
+		return this._newTrieLikeThis(current)
 	}
 
-	return current.$
-}
+	/**
+	 *    search for all values that are associated with keys that have the specified prefix
+	 *    values will be ordered based on the default ordering of the trie (dfs/bfs)
+	 *     
+	 *    @param  {Iterable} prefix 
+	 *    @param  {boolean} [options.includeKeys=false] if set to true result will include keys as values.
+	 *    @return {Iterable}
+	 */
+	search(prefix, { includeKeys = false } = {}) {
+		if (!this._isValidKey(prefix)) {
+			throw new Error('invalid key')
+		}
 
-/**
- *	Search for something in the tree
- *
- *	@param key an array of tokens
- *	@param excludeKeys if true result will only include the leaves and not the whole path
- *
- *	@return {Array} an array of arrays, each sub array contains the key and the value
- */
-Trie.prototype.searchByPrefix = function(key, excludeKeys) {
-	debug('search( {%s} )', key)
+		const node = this._getNode(prefix)
 
-	var results = []
+		if (node === undefined) {
+			return noopIterator
+		}
 
-	var current = this._data
+		return this._newTrieIterator(node, { includeKeys, iterationOrder: this._iterationOrder, prefix })
+	}
 
-	for (var i = 0; i < key.length; i++) {
-		var node = key[i]
+	[Symbol.iterator]() {
+		return this._newTrieIterator(this._root)
+	}
 
-		if (current[node] === undefined)
-			return results
+	/**
+	 *    return a DFS iterator for this trie
+	 *    
+	 *    @param  {boolean} [includeKeys=false] if set to true result will include keys as values.
+	 *    @return {Iterator}
+	 */
+	dfsIterator(includeKeys = false) {
+		return this._newTrieIterator(this._root, { includeKeys, iterationOrder: Trie.DFS })
+	}
 
-		current = current[node]
+	/**
+	 *    return a BFS iterator for this trie
+	 *    
+	 *    @param  {boolean} [includeKeys=false] if set to true result will include keys as values.
+	 *    @return {Iterator}
+	 */
+	bfsIterator(includeKeys = false) {
+		return this._newTrieIterator(this._root, { includeKeys, iterationOrder: Trie.BFS })
 	}
 
-	this._searchByPrefixCollect(key, current, results, excludeKeys)
+	_getNode(key) {
+		if (!this._isValidKey(key)) {
+			throw new Error('invalid key')
+		}
 
-	return results
-}
+		let current = this._root
+		let count = 0
+		
+		for (let part of key) {
+			let node = current.getChild(part)
+			if (node === undefined) {
+				return
+			}
 
-Trie.prototype._searchByPrefixCollect = function(path, parent, results, excludeKeys) {
-	if (!parent) return;
+			count++
+			current = node
+		}
 
-	for (var k in parent) {
-		if (k === '$') {
+		// prevent obtaining access to root
+		// if iterable is empty
+		if (count === 0) {
+			throw new Error('invalid key')
+		}
 
-			if (excludeKeys)
-				results.push(parent.$)
-			else
-				results.push([path.concat([]), parent.$])
+		return current
+	}
 
-			continue
+	_getNodeAndParent(key) {
+
+		if (!this._isValidKey(key)) {
+			throw new Error('invalid key')
 		}
 
-		var current = parent[k]
+		let keyPart = undefined
+		let parent = undefined
+		let current = this._root
+		let count = 0
+		for (keyPart of key) {
+			let node = current.getChild(keyPart)
+			if (node === undefined) {
+				return {}
+			}
 
-		this._searchByPrefixCollect(path.concat([k]), current, results, excludeKeys)
+			count++
+			parent = current
+			current = node
+		}
+
+		// prevent getting access to root
+		// if iterable is empty
+		if (count > 0) {
+			return { current, parent, keyPart }
+		}
+
+		throw new Error('invalid key')
 	}
-}
+
+	_newNode(value) {
+		return new this._nodeClass(value)
+	}
+
+	_isValidKey(key) {
+		// const rightType = Array.isArray(key) || isString(key)
+		// return rightType && key.length > 0
+		return isFunction(key[Symbol.iterator])
+	}
+
+	_newTrieLikeThis(root, shallow = false) {
+		const trie = new Trie({
+			NodeClass: this._nodeClass,
+			iterationOrder: this._iterationOrder
+		})
+
+		trie._root = shallow ? root : root.clone()
+
+		return trie
+	}
+
+	_newTrieIterator(rootNode, { includeKeys = false, iterationOrder = this._iterationOrder, prefix } = {}) {
+		if (iterationOrder === _DFS) {
+			return new TrieIterator(rootNode, { memory: TrieIterator.Stack, includeKeys, prefix })
+		}
+
+		if (iterationOrder === _BFS) {
+			return new TrieIterator(rootNode, { memory: TrieIterator.Queue, includeKeys, prefix })
+		}
+
+		throw new Error('invalid iteration order, try Trie.BFS or Trie.DFS')
+	}
+}
+
+module.exports = Trie

package.json

 {
   "name": "digital-tree",
-  "version": "1.0.2",
+  "version": "2.0.0",
   "description": "trie data structure",
   "main": "index.js",
   "scripts": {
-    "test": "mocha -R spec"
+    "test": "npx ava",
+    "bench": "node benchmark.js"
   },
@@ -24,4 +25,11 @@ "repository": {
   "dependencies": {
-    "debug": "^4.1.1"
+    "benchmark": "^2.1.4",
+    "debug": "^4.1.1",
+    "json-stringify-safe": "^5.0.1"
+  },
+  "devDependencies": {
+    "ava": "^2.1.0",
+    "benchmarkify": "^2.1.1",
+    "trie-d": "^1.0.6"
   }
 }

README.md

 # digital tree
 
-Trie data structure implementation
+A trie data structure implementation. 
 
+- thorough testing
+- utility: clonable and serializable (to/from json)
+- search values by prefix
+
 ## Install
-```
-npm install --save digital-tree
-```
 
+    npm install --save digital-tree
+
+***version 2.0.0 is almost a complete rewrite and mostly not backwards compatible***
+
 ## API
 
+### create() / Ctor
+
+using `create()`` is the recommended way to construct new digital trees:
+
 ```javascript
-    var Trie = require('digital-tree')
-
-    var trie = new Trie()
+    const Trie = require('digital-tree')
+    const trie = Trie.create()
 ```
 
 ### put(key, value)
+
 Put something in the tree
+
 ```javascript
     trie.put(['a', 'path', 'to'], 'something')
+    trie.put(['another', 'thing']) // equivalent to trie.put(['another', 'thing'], true)
+    trie.put('strings also', 'work') // equivalent to trie.put('strings also'.split(''), 'work')
+    
+    // ** this only work with the exact key (reference) **
+    const objectKey = [{ foo: 'bar' }, { bar: 'foo'}]
+    trie.put(objectKey, { some: 'thing'})
 ```
 
-### remove(key)
-Remove something from the tree
+### get(key)
 
-given:
-```json
-{ "a": {
-        "path": {
-            "to": {
-                "$": "value"
-            }
-        }
-    }
-}
-```
+Get something from the tree
 
 ```javascript
-    var subtree = trie.remove(['a', 'path'])
-```
+    const trie = Trie.create()
+    trie.put(['a', 'path', 'to'], 'v1')
+    trie.put('also strings', 'v2')
 
-subtree will be:
-```json
-{ "to": { "$": "value" } }
+    console.log(trie.get([])) // prints 'foo'
+    console.log(trie.get(Trie.root)) // prints 'foo'
+    console.log(trie.get(['a', 'path', 'to'])) // prints 'v1'
+    console.log(trie.get('also strings')) // prints 'v2'
 ```
 
-Trie underlying data will look like this after the removal:
-```json
-{ "a": {}}
+### Iteration
+
+A trie is iterable. Iteration order is either [DFS](https://en.wikipedia.org/wiki/Depth-first_search) or [BFS](https://en.wikipedia.org/wiki/Breadth-first_search)
+
+```javascript
+    const Trie = require('digital-tree')
+    const trie = Trie.create()
+    trie.put('abc', 1)
+    trie.put('abd', 2)
+    trie.put('abe', 3)
+
+    for (let [key, value] of trie) {
+
+    }
 ```
 
-### get(key)
-Get something from the tree
+### search(prefix)
+
+Search and return all the values in the tree that are nested until the provided `prefix`.
+
+The results will be an Iterator over the matching values. The order of iteration is defined based on the default ordering of the trie (BFS/DFS)
+
 ```javascript
-    var value = trie.get(['a', 'path', 'to'])
+    const trie = Trie.create()
+    trie.put('abc', 1)
+    trie.put('abd', 2)
+    trie.put('abe', 3)
+
+    console.log(Array.from(trie.search('ab'))) // prints [ 3, 2, 1 ]
+    console.log(Array.from(trie.search('ab', { includeKeys: true }))) // prints [ [['a','b','e'], 3 ], [['a','b','d'], 2], [['a','b','c'], 1] ]
 ```
-value will be the string "something"
 
-### searchByPrefix(key, excludeEmptyKeys)
-Search for all the entries under key
+### getSubTrie(key, [shallow=false])
 
+Obtain an either cloned or shallow copy of a subtree.
+
 ```javascript
-    var result = trie.searchByPrefix(['a', 'path'])
+trie.put('abc', 1)
+trie.put('abd', 2)
+
+const subTrie = trie.getSubTrie('ab')
+
+console.log(subTrie.get('c')) // prints 1
+console.log(subTrie.get('d')) // prints 2
+console.log(subTrie.get('ab')) // prints undefined
 ```
+*setting `shallow` to `true` will create a view rather than cloning the sub trie*
 
-result will be:
-```json
-[ [ [ "a", "path", "to" ], "something" ] ]
+### remove(key)
+
+Remove something from the tree. This will remove the entire subtree that exists under this specified key and return it
+as a new trie.
+
+```javascript
+    trie.put(['a', 'b'], 'ab')
+    trie.put(['a', 'b', 'c'], 'abc')
+    trie.put(['a', 'b', 'c', 1], 'abc1')
+    trie.put(['a', 'b', 'c', 2], 'abc2')
+
+    const removed = trie.remove(['a', 'b', 'c'])
+    
+    console.log(removed.get([1])) // prints 'abc1'
+    console.log(removed.get([2])) // prints 'abc2'
+
+    console.log(trie.get(['a', 'b', 'c', 1])) // prints 'undefined'
+    console.log(trie.get(['a', 'b'])) // prints 'ab'
 ```
-
-TODO
-- add benchmarks of other similar modules

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

41555

increased by182.3%

Number of package files

15

increased by150%

Lines of code

1080

increased by483.78%

Number of lines in readme file

122

increased by64.86%

Worsened metrics

Dependency count

3

increased by200%

Dev dependency count

3

increased byInfinity%

Number of medium supply chain risk alerts

1

increased byInfinity%

Dependency changes

• + Addedbenchmark@^2.1.4

• + Addedjson-stringify-safe@^5.0.1

• + Addedbenchmark@2.1.4(transitive)

• + Addedjson-stringify-safe@5.0.1(transitive)

• + Addedlodash@4.17.21(transitive)

• + Addedplatform@1.3.6(transitive)