Constructor
new TrieNode(letter, next, isWordEnding, starterDepth, isFirstChild)
- Source:
Parameters:
| Name | Type | Description |
|---|---|---|
letter |
string | codepoint |
next |
TrieNode | next node pointer |
isWordEnding |
boolean | true if this is an end-of-word node |
starterDepth |
number | The maximum depth below this node before the end-of-word is reached, for the first word added |
isFirstChild |
boolean | is the first child of the parent node |
Members
child :TrieNode
- Description:
Pointer to the first next letter if this letter is matched
- Source:
Pointer to the first next letter if this letter is matched
Type:
id :number
- Description:
Unique ID for this node, purely used for debugging
- Source:
Unique ID for this node, purely used for debugging
Type:
- number
index :number
- Description:
Index of the node in the encoded DAWG, assigned when the encoding is generated
- Source:
Index of the node in the encoded DAWG, assigned when the encoding is generated
Type:
- number
isEndOfWord :boolean
- Description:
Marker for a valid end-of-word node
- Source:
Marker for a valid end-of-word node
Type:
- boolean
isFirstChild :boolean
- Description:
Marker for the first child under a parent node. This is used when the node is arrived at other than through the parent
- Source:
Marker for the first child under a parent node. This is used when the node is arrived at other than through the parent
Type:
- boolean
isPruned :boolean
- Description:
Will be set if the node is to be pruned after DAWG generation
- Source:
Will be set if the node is to be pruned after DAWG generation
Type:
- boolean
letter :string
- Description:
The letter at this node
- Source:
The letter at this node
Type:
- string
maxChildDepth :number
- Description:
Maximum number of nodes under this node (iei remaining length of the longest word this node partiipates in)
- Source:
Maximum number of nodes under this node (iei remaining length of the longest word this node partiipates in)
Type:
- number
next :TrieNode
- Description:
Pointer to the next alternative to this letter
- Source:
Pointer to the next alternative to this letter
Type:
numberOfChildren :number
- Description:
Number of child nodes under this node - used for optimisation
- Source:
Number of child nodes under this node - used for optimisation
Type:
- number
Methods
encode() → {Array.<number>}
- Description:
Encode the node in a pair of integers. Requires node indices to have been established.
- Source:
Returns:
array with the 2-integer encoding
- Type
- Array.<number>
findChild(thisLetter) → {TrieNode}
- Description:
Search along this's child next chain for a node with the given letter.
- Source:
Parameters:
| Name | Type | Description |
|---|---|---|
thisLetter |
string | letter to look for |
Returns:
the node found, or null
- Type
- TrieNode
insertChild(thisLetter, wordEnder, startDepth)
- Description:
Insert a letter in the child list of this node. The child list is sorted on letter
- Source:
Parameters:
| Name | Type | Description |
|---|---|---|
thisLetter |
string | letter to add |
wordEnder |
boolean | true if this is the end of a word |
startDepth |
number | depth of shallowest node |
prune() → {number}
- Description:
Mark a node as pruned, and recursively mark every node under and after it as well
- Source:
Returns:
the total number of nodes pruned as a result
- Type
- number
replaceRedundantNodes(red) → {number}
- Description:
Recursively replaces all redundant nodes in a trie with their first equivalent.
- Source:
Parameters:
| Name | Type | Description |
|---|---|---|
red |
Array.<Array.<TrieNode>> | reduction structure |
Returns:
no of nodes replaced
- Type
- number
sameSubtrie(other) → {boolean}
- Description:
Determine if this and other are the parent nodes of equal Trie branches.
- Source:
Parameters:
| Name | Type | Description |
|---|---|---|
other |
TrieNode | other tree to compare |
Returns:
if the are the same
- Type
- boolean
toString(deeply)
- Description:
Debug
- Source:
Parameters:
| Name | Type | Description |
|---|---|---|
deeply |
boolean | true to expand child nodes |
Type Definitions
wordCallback(nodes)
- Source:
Parameters:
| Name | Type | Description |
|---|---|---|
nodes |
TrieNode | list of nodes on the path from the root to the end of the word |