Class Trie<R>

Prefix tree (Trie) for fast prefix queries and word storage.

Remarks

Time O(1), Space O(1)

Example

// Autocomplete: Prefix validation and checking
    const autocomplete = new Trie<string>(['gmail.com', 'gmail.co.nz', 'gmail.co.jp', 'yahoo.com', 'outlook.com']);

    // Get all completions for a prefix
    const gmailCompletions = autocomplete.getWords('gmail');
    console.log(gmailCompletions); // ['gmail.com', 'gmail.co.nz', 'gmail.co.jp']

Example

// File System Path Operations
    const fileSystem = new Trie<string>([
      '/home/user/documents/file1.txt',
      '/home/user/documents/file2.txt',
      '/home/user/pictures/photo.jpg',
      '/home/user/pictures/vacation/',
      '/home/user/downloads'
    ]);

    // Find common directory prefix
    console.log(fileSystem.getLongestCommonPrefix()); // '/home/user/'

    // List all files in a directory
    const documentsFiles = fileSystem.getWords('/home/user/documents/');
    console.log(documentsFiles); // ['/home/user/documents/file1.txt', '/home/user/documents/file2.txt']

Example

// Autocomplete: Basic word suggestions
    // Create a trie for autocomplete
    const autocomplete = new Trie<string>([
      'function',
      'functional',
      'functions',
      'class',
      'classes',
      'classical',
      'closure',
      'const',
      'constructor'
    ]);

    // Test autocomplete with different prefixes
    console.log(autocomplete.getWords('fun')); // ['functional', 'functions', 'function']
    console.log(autocomplete.getWords('cla')); // ['classes', 'classical', 'class']
    console.log(autocomplete.getWords('con')); // ['constructor', 'const']

    // Test with non-matching prefix
    console.log(autocomplete.getWords('xyz')); // []

Example

// Dictionary: Case-insensitive word lookup
    // Create a case-insensitive dictionary
    const dictionary = new Trie<string>([], { caseSensitive: false });

    // Add words with mixed casing
    dictionary.add('Hello');
    dictionary.add('WORLD');
    dictionary.add('JavaScript');

    // Test lookups with different casings
    console.log(dictionary.has('hello')); // true
    console.log(dictionary.has('HELLO')); // true
    console.log(dictionary.has('Hello')); // true
    console.log(dictionary.has('javascript')); // true
    console.log(dictionary.has('JAVASCRIPT')); // true

Example

// IP Address Routing Table
    // Add IP address prefixes and their corresponding routes
    const routes = {
      '192.168.1': 'LAN_SUBNET_1',
      '192.168.2': 'LAN_SUBNET_2',
      '10.0.0': 'PRIVATE_NETWORK_1',
      '10.0.1': 'PRIVATE_NETWORK_2'
    };

    const ipRoutingTable = new Trie<string>(Object.keys(routes));

    // Check IP address prefix matching
    console.log(ipRoutingTable.hasPrefix('192.168.1')); // true
    console.log(ipRoutingTable.hasPrefix('192.168.2')); // true

    // Validate IP address belongs to subnet
    const ip = '192.168.1.100';
    const subnet = ip.split('.').slice(0, 3).join('.');
    console.log(ipRoutingTable.hasPrefix(subnet)); // true

Type Parameters

  • R = any
    1. Node Structure: Each node in a Trie represents a string (or a part of a string). The root node typically represents an empty string.
    2. Child Node Relationship: Each node's children represent the strings that can be formed by adding one character to the string at the current node. For example, if a node represents the string 'ca', one of its children might represent 'cat'.
    3. Fast Retrieval: Trie allows retrieval in O(m) time complexity, where m is the length of the string to be searched.
    4. Space Efficiency: Trie can store a large number of strings very space-efficiently, especially when these strings share common prefixes.
    5. Autocomplete and Prediction: Trie can be used for implementing autocomplete and word prediction features, as it can quickly find all strings with a common prefix.
    6. Sorting: Trie can be used to sort a set of strings in alphabetical order.
    7. String Retrieval: For example, searching for a specific string in a large set of strings.
    8. Autocomplete: Providing recommended words or phrases as a user types.
    9. Spell Check: Checking the spelling of words.
    10. IP Routing: Used in certain types of IP routing algorithms.
    11. Text Word Frequency Count: Counting and storing the frequency of words in a large amount of text data.

Hierarchy (view full)

Constructors

constructor

Properties

_toElementFn?

Accessors

_total caseSensitive root size toElementFn

Methods

_caseProcess _createInstance _createLike _getIterator _spawnLike [iterator] add addMany clear clone delete every filter find forEach getHeight getLongestCommonPrefix getWords has hasCommonPrefix hasPrefix hasPurePrefix isEmpty map mapSame print reduce some toArray toVisual values

Constructors

constructor

  • new Trie<R>(words?, options?): Trie<R>

  • Create a Trie and optionally bulk-insert words.

    Type Parameters

    • R = any

    Parameters

    • Optionalwords: Iterable<string, any, any> | Iterable<R, any, any> = []

      Iterable of strings (or raw records if toElementFn is provided).

    • Optionaloptions: TrieOptions<R>

      Options such as toElementFn and caseSensitive.

    Returns Trie<R>

    New Trie instance.

    Remarks

    Time O(totalChars), Space O(totalChars)

Properties

Protected Optional_toElementFn

_toElementFn?: ((rawElement: R) => string)

The converter used to transform a raw element (R) into a public element (E).

Remarks

Time O(1), Space O(1).

Accessors

Protected_total

  • get _total(): number

  • (Protected) Get total count for base class iteration.

    Returns number

    Total number of elements.

    Remarks

    Time O(1), Space O(1)

caseSensitive

  • get caseSensitive(): boolean

  • Get whether comparisons are case-sensitive.

    Returns boolean

    True if case-sensitive.

    Remarks

    Time O(1), Space O(1)

root

size

toElementFn

  • get toElementFn(): undefined | ((rawElement: R) => E)

  • Exposes the current toElementFn, if configured.

    Returns undefined | ((rawElement: R) => E)

    The converter function or undefined when not set.

    Remarks

    Time O(1), Space O(1).

Methods

Protected_caseProcess

  • _caseProcess(str): string

  • (Protected) Normalize a string according to case sensitivity.

    Parameters

    • str: string

      Input string to normalize.

    Returns string

    Normalized string based on caseSensitive.

    Remarks

    Time O(L), Space O(L)

Protected_createInstance

  • _createInstance(options?): this

  • (Protected) Create an empty instance of the same concrete class.

    Parameters

    • Optionaloptions: TrieOptions<R>

      Options forwarded to the constructor.

    Returns this

    An empty like-kind trie instance.

    Remarks

    Time O(1), Space O(1)

Protected_createLike

  • _createLike<RM>(elements?, options?): Trie<RM>

  • (Protected) Create a like-kind trie and seed it from an iterable.

    Type Parameters

    • RM

    Parameters

    • Optionalelements: Iterable<string, any, any> | Iterable<RM, any, any> = []

      Iterable used to seed the new trie.

    • Optionaloptions: TrieOptions<RM>

      Options forwarded to the constructor.

    Returns Trie<RM>

    A like-kind Trie instance.

    Remarks

    Time O(ΣL), Space O(ΣL)

Protected_getIterator

Protected_spawnLike

  • _spawnLike<RM>(options?): Trie<RM>

  • (Protected) Spawn an empty like-kind trie instance.

    Type Parameters

    • RM

    Parameters

    • Optionaloptions: TrieOptions<RM>

      Options forwarded to the constructor.

    Returns Trie<RM>

    An empty like-kind Trie instance.

    Remarks

    Time O(1), Space O(1)

[iterator]

  • [iterator](...args): IterableIterator<string, any, any>

  • Returns an iterator over the structure's elements.

    Parameters

    • Rest...args: unknown[]

      Optional iterator arguments forwarded to the internal iterator.

    Returns IterableIterator<string, any, any>

    An IterableIterator<E> that yields the elements in traversal order.

    Remarks

    Producing the iterator is O(1); consuming the entire iterator is Time O(n) with O(1) extra space.

add

  • add(word): boolean

  • Insert one word into the trie.

    Parameters

    • word: string

      Word to insert.

    Returns boolean

    True if the word was newly added.

    Remarks

    Time O(L), Space O(L)

addMany

  • addMany(words): boolean[]

  • Insert many words from an iterable.

    Parameters

    • words: Iterable<string, any, any> | Iterable<R, any, any>

      Iterable of strings (or raw records if toElementFn is provided).

    Returns boolean[]

    Array of per-word 'added' flags.

    Remarks

    Time O(ΣL), Space O(ΣL)

clear

clone

delete

  • delete(word): boolean

  • Delete one word if present.

    Parameters

    • word: string

      Word to delete.

    Returns boolean

    True if a word was removed.

    Remarks

    Time O(L), Space O(1)

every

  • every(predicate, thisArg?): boolean

  • Tests whether all elements satisfy the predicate.

    Parameters

    • predicate: ElementCallback<string, R, boolean>

      Function invoked for each element with signature (value, index, self).

    • OptionalthisArg: unknown

      Optional this binding for the predicate.

    Returns boolean

    true if every element passes; otherwise false.

    Remarks

    Time O(n) in the worst case; may exit early when the first failure is found. Space O(1).

filter

  • filter(predicate, thisArg?): this

  • Filter words into a new trie of the same class.

    Parameters

    • predicate: ElementCallback<string, R, boolean>

      Predicate (word, index, trie) → boolean to keep word.

    • OptionalthisArg: any

      Value for this inside the predicate.

    Returns this

    A new trie containing words that satisfy the predicate.

    Remarks

    Time O(ΣL), Space O(ΣL)

find

  • find<S>(predicate, thisArg?): undefined | S

  • Finds the first element that satisfies the predicate and returns it.

    Finds the first element of type S (a subtype of E) that satisfies the predicate and returns it.

    Type Parameters

    • S extends string

    Parameters

    • predicate: ElementCallback<string, R, S>

      Type-guard predicate: (value, index, self) => value is S.

    • OptionalthisArg: unknown

      Optional this binding for the predicate.

    Returns undefined | S

    The matched element typed as S, or undefined if not found.

    Remarks

    Time O(n) in the worst case; may exit early on the first match. Space O(1).

forEach

  • forEach(callbackfn, thisArg?): void

  • Invokes a callback for each element in iteration order.

    Parameters

    • callbackfn: ElementCallback<string, R, void>

      Function invoked per element with signature (value, index, self).

    • OptionalthisArg: unknown

      Optional this binding for the callback.

    Returns void

    void.

    Remarks

    Time O(n), Space O(1).

getHeight

  • getHeight(): number

  • Compute the height (max depth) of the trie.

    Returns number

    Maximum depth from root to a leaf.

    Remarks

    Time O(N), Space O(H)

getLongestCommonPrefix

  • getLongestCommonPrefix(): string

  • Return the longest common prefix among all words.

    Returns string

    The longest common prefix string.

    Remarks

    Time O(H), Space O(1)

getWords

  • getWords(prefix?, max?, isAllWhenEmptyPrefix?): string[]

  • Collect words under a prefix up to a maximum count.

    Parameters

    • Optionalprefix: string = ''

      Prefix to match; default empty string for root.

    • Optionalmax: number = Number.MAX_SAFE_INTEGER

      Maximum number of words to return; default is Number.MAX_SAFE_INTEGER.

    • OptionalisAllWhenEmptyPrefix: boolean = false

      When true, collect from root even if prefix is empty.

    Returns string[]

    Array of collected words (at most max).

    Remarks

    Time O(K·L), Space O(K·L)

has

hasCommonPrefix

  • hasCommonPrefix(input): boolean

  • Check whether the trie’s longest common prefix equals input.

    Parameters

    • input: string

      Candidate longest common prefix.

    Returns boolean

    True if input equals the common prefix.

    Remarks

    Time O(min(H,L)), Space O(1)

hasPrefix

  • hasPrefix(input): boolean

  • Check whether any word starts with input.

    Parameters

    • input: string

      String to test as prefix.

    Returns boolean

    True if input matches a path from root.

    Remarks

    Time O(L), Space O(1)

hasPurePrefix

  • hasPurePrefix(input): boolean

  • Check whether input is a proper prefix of at least one word.

    Parameters

    • input: string

      String to test as prefix.

    Returns boolean

    True if input is a prefix but not a full word.

    Remarks

    Time O(L), Space O(1)

isEmpty

map

  • map<RM>(callback, options?, thisArg?): Trie<RM>

  • Maps each element to a new element and returns a new iterable structure.

    Type Parameters

    • RM

      The mapped raw element type used internally by the target structure.

    Parameters

    • callback: ElementCallback<string, R, string>

      Function with signature (value, index, self) => mapped.

    • Optionaloptions: TrieOptions<RM>

      Optional options for the returned structure, including its toElementFn.

    • OptionalthisArg: any

      Optional this binding for the callback.

    Returns Trie<RM>

    A new IterableElementBase<EM, RM> containing mapped elements.

    Remarks

    Time O(n), Space O(n).

  • map<EM, RM>(callback, options?, thisArg?): IterableElementBase<EM, RM>

  • Map words into a new trie (possibly different record type).

    Type Parameters

    • EM
    • RM

    Parameters

    • callback: ElementCallback<string, R, EM>

      Mapping function (word, index, trie) → newWord (string).

    • Optionaloptions: TrieOptions<RM>

      Options for the output trie (e.g., toElementFn, caseSensitive).

    • OptionalthisArg: any

      Value for this inside the callback.

    Returns IterableElementBase<EM, RM>

    A new Trie constructed from mapped words.

    Remarks

    Time O(ΣL), Space O(ΣL)

mapSame

  • mapSame(callback, thisArg?): this

  • Map words into a new trie of the same element type.

    Parameters

    • callback: ElementCallback<string, R, string>

      Mapping function (word, index, trie) → string.

    • OptionalthisArg: any

      Value for this inside the callback.

    Returns this

    A new trie with mapped words.

    Remarks

    Time O(ΣL), Space O(ΣL)

print

reduce

some

  • some(predicate, thisArg?): boolean

  • Tests whether at least one element satisfies the predicate.

    Parameters

    • predicate: ElementCallback<string, R, boolean>

      Function invoked for each element with signature (value, index, self).

    • OptionalthisArg: unknown

      Optional this binding for the predicate.

    Returns boolean

    true if any element passes; otherwise false.

    Remarks

    Time O(n) in the worst case; may exit early on first success. Space O(1).

toArray

toVisual

values

  • values(): IterableIterator<string, any, any>

  • Returns an iterator over the values (alias of the default iterator).

    Returns IterableIterator<string, any, any>

    An IterableIterator<E> over all elements.

    Remarks

    Creating the iterator is O(1); full iteration is Time O(n), Space O(1).

Settings

Member Visibility

On This Page

Constructors
Properties
Accessors
Methods