Press n or j to go to the next uncovered block, b, p or k for the previous block.
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 | 4x 4x 469x 469x 469x 4x 14x 4x 37x 37x 37x 3x 37x 4x 44x 44x 33x 33x 29x 29x 4x 38x 37x 37x 37x 76x 76x 70x 31x 4x 67x 67x 5x 67x 2x 67x 4x 74x 74x 74x 74x 53x 53x 74x 4x | import { Word, NextNodes, NodeStack, SuggestedPattern, Value } from './types'
import { Suggestion } from './suggestion'
/**
* **NOTE:** a valid [[Match]] with a `remainder` can **only** occur if the partial match
* occurs at a word boundary (i.e., the [[Node | node]] contained in the [[Match| match]]
* has `end === true`). This is due to the fact that the API for defining a [[Pattern | pattern]]
* does not support concatenating a lookup result and char sequences into a single word. E.g.,
* a pattern such as `<some_lookup_context>s` to make a lookup result plural is not supported.
*/
export interface Match {
nodes: NodeStack
remainder: Word[]
}
/**
* <p align="center">
* <img height="80px" src="https://web.archive.org/web/20090806155747/http://www.geocities.com/brerfoxkaleidscope/man_hampster_wheel_lg_wht.gif">
* <img height="80px" src="https://web.archive.org/web/20090806155747/http://www.geocities.com/brerfoxkaleidscope/man_hampster_wheel_lg_wht.gif">
* <img height="80px" src="https://web.archive.org/web/20090806155747/http://www.geocities.com/brerfoxkaleidscope/man_hampster_wheel_lg_wht.gif">
* </p>
*/
export class Node {
end: boolean
next: NextNodes
constructor(readonly value: Value) {
this.end = false
this.next = { char: {}, word: {}, lookup: {} }
}
public isLeaf(): boolean {
return Object.keys(this.next.char).length === 0
&& Object.keys(this.next.word).length === 0
&& Object.keys(this.next.lookup).length === 0
}
/**
* Given an input sequence of words, a starting [[Node | node]], and
* a [[Dictionary | dictionary]], finds all valid matching paths that
* the input satisfies.
*
* #### Simple Example
* If we have a starting node which yields the following
* sub-trie,
* ```
* t - r - i - e
* \
* e - e
* ```
* and input *"tr"*, the returned node will be *"r"*.
*
* #### Advanced Example
* With a more complex starting trie,
* ```
* null - a - b - c - - d (1)
* \
* <X> - - d (2)
*
* <X>: null - a - b - c
* \
* <Y>
*
* <Y>: null - a - b - c - - d (3)
* ```
* given **"abc d"**, it wll return the **"d"** [[Node | nodes]] labeled
* _(1)_, _(2)_, _(3)_
*
* Since patterns can span multiple levels of nested contexts, we need to return
* not only the matched words (partially matched on completed words), but also the
* remainder of the match. This way, we can check for matches in parent contexts in
* case a pattern satisfies a match over an arbitrary number of contextual levels.
*/
public matchPattern(tokens: Word[]): Match[] {
Iif (tokens.length === 0) return []
let matches: Match[] = []
// find matching paths from lookups
for (const [alias, lookup] of Object.entries(this.next.lookup)) {
matches = matches.concat(lookup.matchPattern(tokens))
}
return matches.concat(this.matchWord(tokens))
}
public matchWord(tokens: Word[]): Match[] {
const word = this.next.word[tokens[0][0]]
if (!word) return []
const node = word.matchChars(tokens[0])
if (!node) return []
const match = { nodes: [node], remainder: tokens.slice(1) }
// (1) if there are no remainders keep searching. include match in results if it is a terminal.
// (2) if there are no remainders, return this single match (regardless of if it isa terminal).
return match.remainder.length > 0
? (node.end ? [match] : []).concat(node.matchPattern(match.remainder)) // (1)
: [match] // (2)
}
/**
* Given an word, returns the final node which matches the complete word. null otherwise.
*/
public matchChars(word: Word): Node | null {
if (this.value !== word[0]) return null
let node: Node = this
word = word.substr(1)
while (word) {
node = node.next.char[word[0]]
if (!node) return null
word = word.substr(1)
}
return node
}
public completePattern(tokens: SuggestedPattern): Suggestion[] {
let suggestions: Suggestion[] = []
// complete pattern in all next lookups
for (const [alias, lookup] of Object.entries(this.next.lookup)) {
suggestions = suggestions.concat(lookup.completePattern([...tokens, { [lookup.value as string]: lookup.contexts }]))
}
// complete pattern in all next words
for (const [char, word] of Object.entries(this.next.word)) {
suggestions = suggestions.concat(word.completeWord([...tokens, char]))
}
return suggestions.concat(this.completeWord(tokens))
}
public completeWord(tokens: SuggestedPattern): Suggestion[] {
let suggestions: Suggestion[] = []
// if this is an ending node, add it to suggestions
if (this.end) suggestions.push(new Suggestion([...tokens]))
const lastWord: Word = (tokens.pop() as Word) || ''
// augment the last token with the next characters
for (const char of Object.values(this.next.char)) {
const augmentedTokens = [...tokens, `${lastWord}${char.value}`]
suggestions = suggestions.concat(char.completePattern(augmentedTokens))
}
return suggestions
}
}
|