Socket
Socket
Sign inDemoInstall

@datastructures-js/trie

Package Overview
Dependencies
0
Maintainers
1
Versions
16
Alerts
File Explorer

Advanced tools

npm Scripts

Install Socket

Detect and block malicious and high-risk dependencies

Install

Comparing version 2.0.0 to 3.0.0

8

CHANGELOG.md

@@ -9,4 +9,12 @@ # Changelog

## [3.0.0] - 2020-04-09
### Changed
- renamed `.getWordsCount()` & `.getNodesCount()` to `.wordsCount()` & `.nodesCount()`.
### Fixed
- README
- jsdoc
## [2.0.0] - 2020-03-24
### Changed
- new implementation and interface

2

package.json
{
"name": "@datastructures-js/trie",
"version": "2.0.0",
"version": "3.0.0",
"description": "trie implementation in javascript",

@@ -5,0 +5,0 @@ "main": "index.js",

273

README.md

@@ -9,3 +9,7 @@ # @datastructures-js/trie

<img width="500" alt="Trie" src="https://user-images.githubusercontent.com/6517308/42425010-dc9f20ca-82db-11e8-8f78-1efe6959df5f.png">
<table>
<tr><th>Trie</th></tr>
<tr><td><img width="500" alt="Trie" src="https://user-images.githubusercontent.com/6517308/42425010-dc9f20ca-82db-11e8-8f78-1efe6959df5f.png">
</td></tr>
</table>

@@ -17,3 +21,3 @@ # Table of Contents

* [import](#import)
* [Creating a Trie](#create-a-trie)
* [Construction](#construction)
* [.insert(word)](#insertword)

@@ -25,5 +29,6 @@ * [.has(word)](#hasword)

* [.toArray()](#toarray)
* [.getWordsCount()](#getwordscount)
* [.getNodesCount()](#getnodescount)
* [.wordsCount()](#wordsCount)
* [.nodesCount()](#nodesCount)
* [.clear()](#clear)
* [TrieNode](#trienode)
* [Build](#build)

@@ -52,3 +57,3 @@ * [License](#license)

### Create a Trie
### Construction

@@ -64,24 +69,19 @@ ```js

<table>
<tr>
<th>runtime</th>
<th>params</th>
<th>return</th>
</tr>
<tr>
<td>O(k) : k is the length of word</td>
<td>
word: {string}
</td>
<td><b>{TrieNode}</b>
<br /><br/>
<b>.getChar()</b>: {string} returns the node's char.<br/>
<b>.getParent()</b>: {TrieNode} returns the parent node.<br/>
<b>.isEndOfWord()</b> {boolean} check if a node donates an end of a word.<br/>
<b>.getChild(char)</b>: {TrieNode} returns the child node of a char<br/>
<b>.hasChild(char)</b>: {boolean} check the node has a child char.<br/>
<b>.childrenCount()</b>: {number} returns the number of children nodes.<br/>
</td>
</tr>
<tr><th align="center" colspan="2">params</th></tr>
<tr><td><b>name</b></td><td><b>type</b></td></tr>
<tr><td>word</td><td>string</td></tr>
</table>
<table>
<tr><th>return</th></tr>
<tr><td><a href="#trienode">TrieNode</a></td></tr>
</table>
<table>
<tr><th>runtime</th></tr>
<tr><td>O(k) : k = length of the word</td></tr>
</table>
#### Example
```js

@@ -102,17 +102,19 @@ englishLang.insert('hi');

<table>
<tr>
<th>runtime</th>
<th>params</th>
<th>return</th>
</tr>
<tr>
<td>O(k) : k is the length of word</td>
<td>
word: {string}
</td>
<td>{boolean}
</td>
</tr>
<tr><th align="center" colspan="2">params</th></tr>
<tr><td><b>name</b></td><td><b>type</b></td></tr>
<tr><td>word</td><td>string</td></tr>
</table>
<table>
<tr><th>return</th></tr>
<tr><td>boolean</td></tr>
</table>
<table>
<tr><th>runtime</th></tr>
<tr><td>O(k) : k = length of the word</td></tr>
</table>
#### Example
```js

@@ -127,17 +129,19 @@ englishLang.has('hi'); // true

<table>
<tr>
<th>runtime</th>
<th>params</th>
<th>return</th>
</tr>
<tr>
<td>O(k) : k is the length of word</td>
<td>
word: {string}
</td>
<td>{TrieNode}
</td>
</tr>
<tr><th align="center" colspan="2">params</th></tr>
<tr><td><b>name</b></td><td><b>type</b></td></tr>
<tr><td>word</td><td>string</td></tr>
</table>
<table>
<tr><th>return</th></tr>
<tr><td><a href="#trienode">TrieNode</a></td></tr>
</table>
<table>
<tr><th>runtime</th></tr>
<tr><td>O(k) : k = length of the word</td></tr>
</table>
#### Example
```js

@@ -158,17 +162,19 @@ const hi = englishLang.find('hi');

<table>
<tr>
<th>runtime</th>
<th>params</th>
<th>return</th>
</tr>
<tr>
<td>O(k) : k is the length of word</td>
<td>
word: {string}
</td>
<td>{boolean}
</td>
</tr>
<tr><th align="center" colspan="2">params</th></tr>
<tr><td><b>name</b></td><td><b>type</b></td></tr>
<tr><td>word</td><td>string</td></tr>
</table>
<table>
<tr><th>return</th></tr>
<tr><td>boolean</td></tr>
</table>
<table>
<tr><th>runtime</th></tr>
<tr><td>O(k) : k = length of the word</td></tr>
</table>
#### Example
```js

@@ -183,14 +189,12 @@ englishLang.remove('hi'); // true - hi removed

<table>
<tr>
<th>runtime</th>
<th>params</th>
</tr>
<tr>
<td>O(n) : n is the number of nodes in the trie</td>
<td>
cb: {function(word)}
</td>
</tr>
<tr><th align="center" colspan="2">params</th></tr>
<tr><td><b>name</b></td><td><b>type</b></td><td><b>description</b></td></tr>
<tr><td>cb</td><td>function</td><td>called with each word in the trie</td></tr>
</table>
<table>
<tr><th>runtime</th></tr>
<tr><td>O(n) : n = number of nodes in the trie</td></tr>
</table>
```js

@@ -214,14 +218,13 @@ englishLang.forEach((word) => console.log(word));

<table>
<tr>
<th>runtime</th>
<th>return</th>
</tr>
<tr>
<td>O(n) : n is the number of nodes in the trie</td>
<td>
{array}
</td>
</tr>
<tr><th>return</th><th>description</th></tr>
<tr><td>array</td><td>a list of all the words in the trie</td></tr>
</table>
<table>
<tr><th>runtime</th></tr>
<tr><td>O(n) : n = number of nodes in the trie</td></tr>
</table>
#### Example
```js

@@ -233,40 +236,38 @@ console.log(englishLang.toArray());

### .getWordsCount()
### .wordsCount()
gets the count of words in the trie.
<table>
<tr>
<th>runtime</th>
<th>return</th>
</tr>
<tr>
<td>O(1)</td>
<td>
{number}
</td>
</tr>
<tr><th>return</th></tr>
<tr><td>number</td></tr>
</table>
<table>
<tr><th>runtime</th></tr>
<tr><td>O(1)</td></tr>
</table>
#### Example
```js
console.log(englishLang.getWordsCount()); // 7
console.log(englishLang.wordsCount()); // 7
```
### .getNodesCount()
### .nodesCount()
gets the count of nodes in the trie.
<table>
<tr>
<th>runtime</th>
<th>return</th>
</tr>
<tr>
<td>O(1)</td>
<td>
{number}
</td>
</tr>
<tr><th>return</th></tr>
<tr><td>number</td></tr>
</table>
<table>
<tr><th>runtime</th></tr>
<tr><td>O(1)</td></tr>
</table>
#### Example
```js
console.log(englishLang.getNodesCount()); // 23
console.log(englishLang.nodesCount()); // 23
```

@@ -286,8 +287,60 @@

#### Example
```js
englishLang.clear();
console.log(englishLang.getWordsCount()); // 0
console.log(englishLang.getNodesCount()); // 1
console.log(englishLang.wordsCount()); // 0
console.log(englishLang.nodesCount()); // 1
```
### TrieNode
#### .getChar()
returns the node's char.
<table>
<tr><th>return</th></tr>
<tr><td>string</td></tr>
</table>
#### .getParent()
returns the parent node.
<table>
<tr><th>return</th></tr>
<tr><td>TrieNode</td></tr>
</table>
#### .isEndOfWord()
check if a node is an end of a word.
<table>
<tr><th>return</th></tr>
<tr><td>boolean</td></tr>
</table>
#### .getChild(char)
returns the child node of a char.
<table>
<tr><th>return</th></tr>
<tr><td>TrieNode</td></tr>
</table>
#### .hasChild(char)
check the node has a child char.
<table>
<tr><th>return</th></tr>
<tr><td>boolean</td></tr>
</table>
#### .childrenCount()
returns the number of children nodes.
<table>
<tr><th>return</th></tr>
<tr><td>number</td></tr>
</table>
## Build

@@ -294,0 +347,0 @@ ```

77

src/trie.js
/**
* datastructures-js/trie
* @datastructures-js/trie
* @copyright 2020 Eyas Ranjous <eyas.ranjous@gmail.com>

@@ -14,5 +14,5 @@ * @license MIT

constructor() {
this.root = new TrieNode('');
this.wordsCount = 0;
this.nodesCount = 1; // root node
this._root = new TrieNode('');
this._wordsCount = 0;
this._nodesCount = 1; // root node
}

@@ -23,7 +23,8 @@

* inserts a word into the trie and returns its last char node
*
* @param {string} word
* @return {TrieNode}
* @param {TrieNode} node
* @param {number} i
* @returns {TrieNode}
*/
insert(word, node = this.root, i = 0) {
insert(word, node = this._root, i = 0) {
if (typeof word !== 'string') {

@@ -36,3 +37,3 @@ throw new Error('Trie.insert expects a string word');

node.setEndOfWord(true);
this.wordsCount += 1;
this._wordsCount += 1;
}

@@ -44,3 +45,3 @@ return node;

node.addChild(word[i]);
this.nodesCount += 1;
this._nodesCount += 1;
}

@@ -54,7 +55,8 @@

* checks if a word exists in the trie
*
* @param {string} word
* @return {boolean}
* @param {TrieNode} node
* @param {number} i
* @returns {boolean}
*/
has(word, node = this.root, i = 0) {
has(word, node = this._root, i = 0) {
if (typeof word !== 'string') return false;

@@ -74,7 +76,8 @@

* finds a word in the trie and returns its last char node
*
* @param {string} word
* @return {TrieNode}
* @param {TrieNode} word
* @param {string} word
* @returns {TrieNode}
*/
find(word, node = this.root, i = 0) {
find(word, node = this._root, i = 0) {
if (typeof word !== 'string') return null;

@@ -94,5 +97,4 @@

* removes a word from the trie
*
* @param {string} word
* @return {boolean}
* @returns {boolean}
*/

@@ -106,3 +108,3 @@ remove(word) {

lastCharNode.setEndOfWord(false);
this.wordsCount -= 1;
this._wordsCount -= 1;
return true;

@@ -115,3 +117,3 @@ }

current.getParent().removeChild(current.getChar());
this.nodesCount -= 1;
this._nodesCount -= 1;
}

@@ -121,3 +123,3 @@ current = current.getParent();

this.wordsCount -= 1;
this._wordsCount -= 1;
return true;

@@ -127,7 +129,9 @@ }

/**
* @public
* traverse the words in the trie
*
* @param {function} cb
* @param {TrieNode} node
* @param {string} w
*/
forEach(cb, node = this.root, w = '') {
forEach(cb, node = this._root, w = '') {
if (typeof cb !== 'function') {

@@ -142,5 +146,5 @@ throw new Error('Trie.forEach expects a callback');

node.getChildren().forEach((childNode) => {
word += childNode.getChar();
this.forEach(cb, childNode, word); // depth-first search
node.children().forEach((child) => {
word += child.getChar();
this.forEach(cb, child, word); // depth-first search
word = word.substr(0, word.length - 1); // backward tracking

@@ -151,5 +155,5 @@ });

/**
* @public
* converts the trie into an array of words
*
* @return {array}
* @returns {array}
*/

@@ -164,6 +168,6 @@ toArray() {

* @public
* @return {number}
* @returns {number}
*/
getNodesCount() {
return this.nodesCount;
nodesCount() {
return this._nodesCount;
}

@@ -173,15 +177,16 @@

* @public
* @return {number}
* @returns {number}
*/
getWordsCount() {
return this.wordsCount;
wordsCount() {
return this._wordsCount;
}
/**
* @public
* clears the trie
*/
clear() {
this.root = new TrieNode('');
this.nodesCount = 1;
this.wordsCount = 0;
this._root = new TrieNode('');
this._nodesCount = 1;
this._wordsCount = 0;
}

@@ -188,0 +193,0 @@ }

38

src/trieNode.js
/**
* datastructures-js/trie
* @datastructures-js/trie
* @copyright 2020 Eyas Ranjous <eyas.ranjous@gmail.com>

@@ -12,6 +12,6 @@ * @license MIT

constructor(char) {
this.char = char;
this.endOfWord = false;
this.parentNode = null;
this.children = new Map();
this._char = char;
this._isEndOfWord = false;
this._parent = null;
this._children = new Map();
}

@@ -24,3 +24,3 @@

getChar() {
return this.char;
return this._char;
}

@@ -33,3 +33,3 @@

setParent(parentNode) {
this.parentNode = parentNode;
this._parent = parentNode;
}

@@ -42,3 +42,3 @@

getParent() {
return this.parentNode;
return this._parent;
}

@@ -50,4 +50,4 @@

*/
setEndOfWord(endOfWord) {
this.endOfWord = endOfWord;
setEndOfWord(isEndOfWord) {
this._isEndOfWord = isEndOfWord;
}

@@ -60,3 +60,3 @@

isEndOfWord() {
return this.endOfWord;
return this._isEndOfWord;
}

@@ -71,3 +71,3 @@

childNode.setParent(this);
this.children.set(char, childNode);
this._children.set(char, childNode);
}

@@ -81,3 +81,3 @@

removeChild(char) {
return this.children.delete(char);
return this._children.delete(char);
}

@@ -91,7 +91,7 @@

getChild(char) {
return this.children.get(char) || null;
return this._children.get(char) || null;
}
/**
* @internal
* @public
* @param {string} char

@@ -101,3 +101,3 @@ * @return {boolean}

hasChild(char) {
return this.children.has(char);
return this._children.has(char);
}

@@ -109,4 +109,4 @@

*/
getChildren() {
return this.children;
children() {
return this._children;
}

@@ -119,3 +119,3 @@

childrenCount() {
return this.children.size;
return this._children.size;
}

@@ -122,0 +122,0 @@ }

.eslintrc
test/trie.test.js
SocketSocket SOC 2 Logo

Product

  • Package Alerts
  • Integrations
  • Docs
  • Pricing
  • FAQ
  • Roadmap

About

Packages

Stay in touch

Get open source security insights delivered straight into your inbox.

  • Terms
  • Privacy
  • Security

Made with ⚡️ by Socket Inc