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 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 | 4x 4x 4x 4x 4x 95x 95x 190x 4x 85x 85x 85x 85x 67x 85x 4x 5x 3x 3x 3x 6x 3x 3x 270x 135x 125x 125x 125x 125x 125x 125x 38x 38x 76x 38x 38x 27x 27x 27x 38x 4x 98x 98x 98x 98x 98x 11x 11x 87x 87x 294x 288x 286x 286x 286x 286x 94x 39x 37x 37x 37x 37x 74x 41x 41x 41x 37x 37x 37x 37x 37x 4x 3x 3x 1x 1x 2x 2x 1x 3x 4x | import {
Pattern,
Word,
Lookup,
} from './types'
import { Dictionary } from './dictionary'
import { Node } from './node'
import { LookupNode } from './lookup'
import { Suggestion } from './suggestion'
import { NormalizePattern } from './util'
import { isWord, isLookup } from './typegaurds'
/**
* <p align="center">
* <img src="https://web.archive.org/web/20091026172159/http://geocities.com/simms_huijnen/Animations/osciloscope.gif">
* <img src="https://web.archive.org/web/20091026172159/http://geocities.com/simms_huijnen/Animations/osciloscope.gif">
* <img src="https://web.archive.org/web/20091026172159/http://geocities.com/simms_huijnen/Animations/osciloscope.gif">
* </p>
*
* A `Scope` is the top-level [[Node|node]] of a Phrase [Trie](https://en.wikipedia.org/wiki/Trie) --
* a trie of (trie)s which allows not only matching next characters, but also next words. This class
* exposes methods for adding, removing, and suggesting patterns.
*
* As a technical note, a `Scope`'s value is `null`, thus all patterns within a scope are
* accessible through the [[NextNodes.word|`Scope.next.word`]] or [[NextNodes.lookup|`Scope.next.lookup`]].
*/
export class Scope extends Node {
/**
* Constructs a `Scope`.
* @param dictionary typically a reference to the dictionary this scope is contained within.
* @param patterns an array of patterns to initially add to this scope.
*/
constructor(readonly dictionary: Dictionary, Ipatterns: Pattern[] = []) {
super(null)
// add provided patterns to our trie.
for (const pattern of patterns) { this.add(pattern) }
}
/**
* Adds a [[Term|term]] or [[Pattern|pattern]] to the scope.
*/
public add(pattern: Word | Lookup | Pattern) {
let words = NormalizePattern(pattern)
Iif (words.length === 0) return
// TODO validate pattern.
// TODO handle empty strings as Words by skipping.
// (gaurantees each word has at least one character)
let node: Node = this
// this ensures that the root node of the Trie does not have any next.chars
// rather, the null root acts as the last char of the previous word in a pattern
// this is a simplifying structure for the algorithm.
if (isWord(words[0])) {
({ node, pattern: words } = this._addFirstCharOfNextWord(this, words))
}
this._add(node, words)
}
/**
* Removes a [[Pattern|pattern]] from the scope.
*/
public remove(pattern: Pattern) { }
/**
* Given a sequence of input tokens, returns an array of [[Suggestion|suggested completions]].
*
* @param input a sequence of input tokens.
* @param lookahead how many tokens to resolve in lookups which occur immediately after input. See [[Dictionary.lookahead|lookahead]].
*/
public suggest(input: Word | Word[], lookahead: number = 0): Suggestion[] {
let suggestions: Suggestion[] = []
// normalize input to be an array (if only given a string)
Eif (!Array.isArray(input)) input = [input]
// find matches with no remainder and extract their lookup-stacks
const stacks = this.matchPattern(input).filter(m => m.remainder.length === 0).map(m => m.nodes)
for (const stack of stacks) {
suggestions = suggestions.concat(this._unwind(stack, input, lookahead))
}
return suggestions
}
private _add(node: Node, pattern: Pattern, EisLastWord: boolean = false) {
if (pattern.length === 0) return
if (pattern.length === 1) isLastWord = true
let nextNodes: Node[] = []
let next: Word | Lookup = pattern[0]
if (isWord(next)) nextNodes = [this._addChars(node, next, isLastWord)]
if (isLookup(next)) nextNodes = this._addLookup(node, next, isLastWord)
if (isLastWord) return
pattern = pattern.slice(1)
next = pattern[0]
for (let nextNode of nextNodes) {
let nextPattern = pattern
if (isWord(next)) {
const result = this._addFirstCharOfNextWord(nextNode, pattern)
nextNode = result.node
nextPattern = result.pattern
}
this._add(nextNode, nextPattern)
}
}
private _addFirstCharOfNextWord(node: Node, pattern: Pattern): { node: Node, pattern: Pattern } {
const word = pattern[0] as Word
const c = word[0]
// check if this node has already been made
if (!(c in node.next.word)) node.next.word[c] = new Node(c)
node = node.next.word[c]
if (word.length === 1 && pattern.length === 1) {
node.end = true
return { node, pattern: [] }
}
pattern = ([word.substr(1)] as Pattern).concat(pattern.slice(1))
return { node, pattern }
}
private _addChars(node: Node, word: Word, isLastWord: boolean = true): Node {
if (word.length === 0) return node
const c: string = word[0]
if (!node.next.char[c]) node.next.char[c] = new Node(c)
if (word.length === 1 && isLastWord) node.next.char[c].end = true
// recurse until all has been consumed.
if (word.length > 1) return this._addChars(node.next.char[c], word.slice(1), isLastWord)
return node.next.char[c]
}
private _addLookup(node: Node, lookup: Lookup, isLastWord: boolean = true): Node[] {
let nodes: Node[] = []
for (let [alias, contexts] of Object.entries(lookup)) {
// normalize contexts to always be an array
if (!Array.isArray(contexts)) contexts = [contexts]
let tries: Scope[] = []
for (const context of contexts) {
const trie = this.dictionary.scopes.get(context)
Iif (!trie) throw new Error(`No such context '${context}'`) // TODO make this a type
tries.push(trie)
}
const lookupNode = new LookupNode(alias, tries)
if (isLastWord) lookupNode.end = true
node.next.lookup[alias] = lookupNode
nodes.push(lookupNode)
}
return nodes
}
private _unwind(stack: Node[], input: Word[], Ilookahead: number = 0): Suggestion[] {
let suggestions: Suggestion[] = stack[0].completePattern([...input])
// essentially reshape the `suggestions` array s.t. each resulting array of
// suggestions from each subsequent node in the lookup-stack is concat'd.
for (const node of stack.slice(1)) {
for (const suggestion of node.completePattern([])) {
let tmp: Suggestion[] = []
for (const suggestion_i of suggestions) {
tmp.push(suggestion_i.concat(suggestion))
}
suggestions = tmp
}
}
// return immediately if we don't require a lookahead.
Eif (lookahead === 0) return suggestions
// for each resulting suggestion, enforce a lookahead from the input offset
let resolvedSuggestions: Suggestion[] = []
for (const suggestion of suggestions) {
resolvedSuggestions = resolvedSuggestions
.concat(suggestion.resolveLookups(input, lookahead))
}
return resolvedSuggestions
}
}
|