Changeset View
Changeset View
Standalone View
Standalone View
swh/web/tests/resources/contents/code/extensions/TrieNode.js
- This file was added.
import HashTable from '../hash-table/HashTable'; | |||||
export default class TrieNode { | |||||
/** | |||||
* @param {string} character | |||||
* @param {boolean} isCompleteWord | |||||
*/ | |||||
constructor(character, isCompleteWord = false) { | |||||
this.character = character; | |||||
this.isCompleteWord = isCompleteWord; | |||||
this.children = new HashTable(); | |||||
} | |||||
/** | |||||
* @param {string} character | |||||
* @return {TrieNode} | |||||
*/ | |||||
getChild(character) { | |||||
return this.children.get(character); | |||||
} | |||||
/** | |||||
* @param {string} character | |||||
* @param {boolean} isCompleteWord | |||||
* @return {TrieNode} | |||||
*/ | |||||
addChild(character, isCompleteWord = false) { | |||||
if (!this.children.has(character)) { | |||||
this.children.set(character, new TrieNode(character, isCompleteWord)); | |||||
} | |||||
const childNode = this.children.get(character); | |||||
// In cases similar to adding "car" after "carpet" we need to mark "r" character as complete. | |||||
childNode.isCompleteWord = childNode.isCompleteWord || isCompleteWord; | |||||
return childNode; | |||||
} | |||||
/** | |||||
* @param {string} character | |||||
* @return {TrieNode} | |||||
*/ | |||||
removeChild(character) { | |||||
const childNode = this.getChild(character); | |||||
// Delete childNode only if: | |||||
// - childNode has NO children, | |||||
// - childNode.isCompleteWord === false. | |||||
if ( | |||||
childNode | |||||
&& !childNode.isCompleteWord | |||||
&& !childNode.hasChildren() | |||||
) { | |||||
this.children.delete(character); | |||||
} | |||||
return this; | |||||
} | |||||
/** | |||||
* @param {string} character | |||||
* @return {boolean} | |||||
*/ | |||||
hasChild(character) { | |||||
return this.children.has(character); | |||||
} | |||||
/** | |||||
* Check whether current TrieNode has children or not. | |||||
* @return {boolean} | |||||
*/ | |||||
hasChildren() { | |||||
return this.children.getKeys().length !== 0; | |||||
} | |||||
/** | |||||
* @return {string[]} | |||||
*/ | |||||
suggestChildren() { | |||||
return [...this.children.getKeys()]; | |||||
} | |||||
/** | |||||
* @return {string} | |||||
*/ | |||||
toString() { | |||||
let childrenAsString = this.suggestChildren().toString(); | |||||
childrenAsString = childrenAsString ? `:${childrenAsString}` : ''; | |||||
const isCompleteString = this.isCompleteWord ? '*' : ''; | |||||
return `${this.character}${isCompleteString}${childrenAsString}`; | |||||
} | |||||
} |