@datastructures-js/trie
Advanced tools
Comparing version 4.1.1 to 4.2.0
@@ -8,2 +8,14 @@ # Changelog | ||
## [Unreleased] | ||
## [4.2.0] - 2021-12-01 | ||
### Added | ||
- `isLeaf()` to TrieNode: leaf is a node that has no children. | ||
### Fixed | ||
- `remove(word)` two edge cases that were not covered: | ||
1. the case when removing a word that does not exist, count should not change. | ||
2. the case when another word overlaps with the word being deleted, it was removing all the word chars regardless if one char is an end of another word. | ||
**Credit:** 王悠悠 https://github.com/anson09 | ||
## [4.1.1] - 2021-06-20 | ||
@@ -10,0 +22,0 @@ |
{ | ||
"name": "@datastructures-js/trie", | ||
"version": "4.1.1", | ||
"version": "4.2.0", | ||
"description": "trie implementation in javascript", | ||
@@ -29,3 +29,3 @@ "main": "index.js", | ||
"eslint-plugin-import": "^2.19.1", | ||
"grunt": "^1.0.4", | ||
"grunt": "^1.4.1", | ||
"grunt-eslint": "^22.0.0", | ||
@@ -32,0 +32,0 @@ "grunt-mocha-istanbul": "^5.0.2", |
@@ -124,2 +124,6 @@ /** | ||
if (!currentNode.isEndOfWord()) { | ||
return null; | ||
} | ||
if (currentNode.childrenCount() > 0 || word === '') { | ||
@@ -131,9 +135,11 @@ currentNode.setEndOfWord(false); | ||
while (!currentNode.isRoot()) { | ||
if (currentNode.childrenCount() === 0) { | ||
currentNode.getParent().removeChild(currentNode.getChar()); | ||
this._nodesCount -= 1; | ||
} | ||
do { | ||
currentNode.getParent().removeChild(currentNode.getChar()); | ||
this._nodesCount -= 1; | ||
currentNode = currentNode.getParent(); | ||
} | ||
} while ( | ||
currentNode.isLeaf() | ||
&& !currentNode.isEndOfWord() | ||
&& !currentNode.isRoot() | ||
); | ||
@@ -140,0 +146,0 @@ this._wordsCount -= 1; |
@@ -16,2 +16,6 @@ /** | ||
/** | ||
* @public | ||
* @return {boolean} | ||
*/ | ||
isRoot() { | ||
@@ -23,2 +27,10 @@ return this._char === ''; | ||
* @public | ||
* @return {boolean} | ||
*/ | ||
isLeaf() { | ||
return this._children.size === 0; | ||
} | ||
/** | ||
* @public | ||
* @returns {string} | ||
@@ -25,0 +37,0 @@ */ |
18156
340