LetterNode

LetterNode

Letter node in a Dictionary. Each node has multiple links and helpers that trade off space for performance during word searches. Each LetterNode participates in two linked lists; the next pointer points to the next alternative to this letter when composing a word, while the child pointer points to the first in a chain of possible child nodes. For example, in a dictionary where we have the two words NO, SO and SAD:

  N -next-> S -next->
  |         |
child     child
  |         |
  `-> O(e)  `-> A -next-> O(e)
                |
              child
                |
                D(e)

where (e) indicates a node that is a valid end-of-word. The example is a tree; however the DAWG compressor will collapse letter sequences that are common to several words, to create a more optimal DAG.

Once a Dictionary has been created and fully populated, it can be processed using buildLists to generate lists that support rapid navigation through the DAG without needing to traverse the node chains.

Constructor

new LetterNode()

Source:

Members

CHILD_INDEX_BIT_MASK :number

Description:

  • Mask for child index, exclusing above bit masks

Source:

Mask for child index, exclusing above bit masks

Type:
  • number

CHILD_INDEX_SHIFT :number

Description:

  • Shift to create space for masks

Source:

Shift to create space for masks

Type:
  • number

END_OF_LIST_BIT_MASK :number

Description:

  • Bit mask for end-of-list marker

Source:

Bit mask for end-of-list marker

Type:
  • number

END_OF_WORD_BIT_MASK :number

Description:

  • Bit mask for end-of-word marker

Source:

Bit mask for end-of-word marker

Type:
  • number

(nullable) child :LetterNode

Description:

  • Pointer to the head of the child chain

Source:

Pointer to the head of the child chain

Type:

isEndOfWord :boolean

Description:

  • Is this the end of a valid word?

Source:

Is this the end of a valid word?

Type:
  • boolean

letter :string

Description:

  • The letter at this node

Source:

The letter at this node

Type:
  • string

(nullable) next :number|LetterNode

Description:

  • Pointer to the next (alternative) node in this peer chain. During loading this will be a number that will be converted to a pointer.

Source:

Pointer to the next (alternative) node in this peer chain. During loading this will be a number that will be converted to a pointer.

Type:

(nullable) postLetters :Array.<LetterNode>

Description:

  • List of letters that are in the nodes listed in postNode. Set up by buildLists.

Source:

List of letters that are in the nodes listed in postNode. Set up by buildLists.

Type:

(nullable) postNodes :Array.<LetterNode>

Description:

  • List of nodes that are linked to from this node. Set up by buildLists.

Source:

List of nodes that are linked to from this node. Set up by buildLists.

Type:

(nullable) preLetters :Array.<string>

Description:

  • List of letters that are in the nodes listed in preNodes. Set up by buildLiss.

Source:

List of letters that are in the nodes listed in preNodes. Set up by buildLiss.

Type:
  • Array.<string>

(nullable) preNodes :Array.<LetterNode>

Description:

  • List of nodes that link forward to this node. Set up by buildLists.

Source:

List of nodes that link forward to this node. Set up by buildLists.

Type:

Methods

add(word) → {boolean}

Description:

  • Add a letter sequence to this node. This is used to add whitelist nodes to a DAG.

Source:
Parameters:
Name Type Description
word string

word being added
Returns:

true if the word was added, false if it was already there

Type
boolean

buildLists()

Description:

  • Build forward and backward lists to allow us to navigate in both directions - forward through words, and backwards too. This has to be done from the root of the DAG, and has to be re-done if the DAG is modified..

Source:

decode(i, numb) → {LetterNode}

Description:

  • Decode node information encoded in an integer in a serialised Dictionary.

Source:
Parameters:
Name Type Description
i number

index of node in node list
numb number

encoded node
Returns:

this

Type
LetterNode

eachLongWord(s, cb)

Description:

  • Enumerate each LONG word in the dictionary. A long word is one that has no child nodes i.e. cannot be extended by adding more letters to create a new word. Calls cb on each word. Caution this is NOT the same as dawg/TrieNode.eachWord.

Source:
Parameters:
Name Type Description
s string

the word constructed so far
cb wordCallback

the callback

eachNode(cb)

Description:

  • Enumerate each node in the dictionary. Calls cb on each node, stops if cb returns false.

Source:
Parameters:
Name Type Description
cb LetterNode~nodeCallback

the callback

eachWord(s, cb)

Description:

  • Enumerate each word in the dictionary. Calls cb on each word.

Source:
Parameters:
Name Type Description
s string

the word constructed so far
cb LetterNode~wordCallback

the callback

findWordsThatUse(chars, realWord, blankedWord, foundWords)

Description:

  • Find words that can be made from a sorted set of letters.

Source:
Parameters:
Name Type Description
chars Array.<string>

the available set of characters
realWord string

the string built so far in this recursion
blankedWord string

the string built using spaces for blanks if they are used
foundWords Array.<string>

list of words found

hangmen(chars, index, word, list)

Description:

  • Find all words below this node that match the character sequence passed from a given point in the sequence. " " acts as a wildcard.

Source:
Parameters:
Name Type Description
chars string

the character sequence to match
index number

index into chars
word string

word asembled so far
list Array.<string>

list of words found

match(chars, index) → {LetterNode}

Description:

  • Find the letter node at the end of the subtree that matches the last character in chars, even if it"s not isEndOfWord

Source:
Parameters:
Name Type Description
chars string

a string of characters that may be the root of a word
index number

index into chars
Returns:

node found, or undefined

Type
LetterNode

Type Definitions

nodeCallback(node) → {boolean}

Source:
Parameters:
Name Type Description
node LetterNode

node
Returns:

true to continue the iteration, false to stop it.

Type
boolean

wordCallback(word, node)

Source:
Parameters:
Name Type Description
word string

found
node LetterNode

node where word was terminated