/**
 * data-structure-typed
 *
 * @author Pablo Zeng
 * @copyright Copyright (c) 2022 Pablo Zeng <zrwusa@gmail.com>
 * @license MIT License
 */
import type { ElementCallback, TrieOptions } from '../../types';
import { IterableElementBase } from '../base';
/**
 * Node used by Trie to store one character and its children.
 * @remarks Time O(1), Space O(1)
 */
export declare class TrieNode {
    /**
     * Create a Trie node with a character key.
     * @remarks Time O(1), Space O(1)
     * @returns New TrieNode instance.
     */
    constructor(key: string);
    protected _key: string;
    /**
     * Get the character key of this node.
     * @remarks Time O(1), Space O(1)
     * @returns Character key string.
     */
    get key(): string;
    /**
     * Set the character key of this node.
     * @remarks Time O(1), Space O(1)
     * @param value - New character key.
     * @returns void
     */
    set key(value: string);
    protected _children: Map<string, TrieNode>;
    /**
     * Get the child map of this node.
     * @remarks Time O(1), Space O(1)
     * @returns Map from character to child node.
     */
    get children(): Map<string, TrieNode>;
    /**
     * Replace the child map of this node.
     * @remarks Time O(1), Space O(1)
     * @param value - New map of character → node.
     * @returns void
     */
    set children(value: Map<string, TrieNode>);
    protected _isEnd: boolean;
    /**
     * Check whether this node marks the end of a word.
     * @remarks Time O(1), Space O(1)
     * @returns True if this node ends a word.
     */
    get isEnd(): boolean;
    /**
     * Mark this node as the end of a word or not.
     * @remarks Time O(1), Space O(1)
     * @param value - Whether this node ends a word.
     * @returns void
     */
    set isEnd(value: boolean);
}
/**
 * Prefix tree (Trie) for fast prefix queries and word storage.
 * @remarks Time O(1), Space O(1)
 * @template R
 * 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.
 * @example
 * // Trie isPrefix and isAbsolutePrefix checks
 *  const trie = new Trie(['tree', 'trial', 'trick', 'trip', 'trie']);
 *
 *     // Check if string is a prefix of any word
 *     console.log(trie.hasPrefix('tri')); // true;
 *     console.log(trie.hasPrefix('tr')); // true;
 *     console.log(trie.hasPrefix('xyz')); // false;
 *
 *     // Check if string is an absolute prefix (not a complete word)
 *     console.log(trie.hasPurePrefix('tri')); // true;
 *     console.log(trie.hasPurePrefix('tree')); // false; // 'tree' is a complete word
 *
 *     // Verify size
 *     console.log(trie.size); // 5;
 * @example
 * // Trie for autocomplete search index
 *  // Trie is perfect for autocomplete: O(m + k) where m is prefix length, k is results
 *     const searchIndex = new Trie(['typescript', 'javascript', 'python', 'java', 'rust', 'ruby', 'golang', 'kotlin']);
 *
 *     // User types 'j' - get all suggestions
 *     const jResults = searchIndex.getWords('j');
 *     console.log(jResults); // contains 'javascript';
 *     console.log(jResults); // contains 'java';
 *     console.log(jResults.length); // 2;
 *
 *     // User types 'ja' - get more specific suggestions
 *     const jaResults = searchIndex.getWords('ja');
 *     console.log(jaResults); // contains 'javascript';
 *     console.log(jaResults); // contains 'java';
 *     console.log(jaResults.length); // 2;
 *
 *     // User types 'jav' - even more specific
 *     const javResults = searchIndex.getWords('jav');
 *     console.log(javResults); // contains 'javascript';
 *     console.log(javResults); // contains 'java';
 *     console.log(javResults.length); // 2;
 *
 *     // Check for common prefix
 *
 *     console.log(searchIndex.hasCommonPrefix('ja')); // false; // Not all words start with 'ja'
 *
 *     // Total words in index
 *     console.log(searchIndex.size); // 8;
 *
 *     // Get height (depth of tree)
 *     const height = searchIndex.getHeight();
 *     console.log(typeof height); // 'number';
 * @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
 * // 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
 * // 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;
 */
export declare class Trie<R = any> extends IterableElementBase<string, R> {
    /**
     * Create a Trie and optionally bulk-insert words.
     * @remarks Time O(totalChars), Space O(totalChars)
     * @param [words] - Iterable of strings (or raw records if toElementFn is provided).
     * @param [options] - Options such as toElementFn and caseSensitive.
     * @returns New Trie instance.
     */
    constructor(words?: Iterable<string> | Iterable<R>, options?: TrieOptions<R>);
    protected _size: number;
    /**
     * Get the number of stored words.
     * @remarks Time O(1), Space O(1)
     * @returns Word count.
     */
    get size(): number;
    protected _caseSensitive: boolean;
    /**
     * Get whether comparisons are case-sensitive.
     * @remarks Time O(1), Space O(1)
     * @returns True if case-sensitive.
     */
    get caseSensitive(): boolean;
    protected _root: TrieNode;
    /**
     * Get the root node.
     * @remarks Time O(1), Space O(1)
     * @returns Root TrieNode.
     */
    get root(): TrieNode;
    /**
     * (Protected) Get total count for base class iteration.
     * @remarks Time O(1), Space O(1)
     * @returns Total number of elements.
     */
    protected get _total(): number;
    /**
     * Insert one word into the trie.
     * @remarks Time O(L), Space O(L)
     * @param word - Word to insert.
     * @returns True if the word was newly added.
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
      * @example
   * // basic Trie creation and add words
   *  // Create a simple Trie with initial words
   *     const trie = new Trie(['apple', 'app', 'apply']);
   *
   *     // Verify size
   *     console.log(trie.size); // 3;
   *
   *     // Check if words exist
   *     console.log(trie.has('apple')); // true;
   *     console.log(trie.has('app')); // true;
   *
   *     // Add a new word
   *     trie.add('application');
   *     console.log(trie.size); // 4;
     */
    add(word: string): boolean;
    /**
     * Insert many words from an iterable.
     * @remarks Time O(ΣL), Space O(ΣL)
     * @param words - Iterable of strings (or raw records if toElementFn is provided).
     * @returns Array of per-word 'added' flags.
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
      * @example
   * // Add multiple words
   *  const trie = new Trie();
   *     trie.addMany(['cat', 'car', 'card']);
   *     console.log(trie.has('cat')); // true;
   *     console.log(trie.has('car')); // true;
   *     console.log(trie.size); // 3;
     */
    addMany(words: Iterable<string> | Iterable<R>): boolean[];
    /**
     * Check whether a word exists.
     * @remarks Time O(L), Space O(1)
     * @param word - Word to search for.
     * @returns True if present.
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
      * @example
   * // Check if a word exists
   *  const dict = new Trie(['apple', 'app', 'application']);
   *
   *     console.log(dict.has('app')); // true;
   *     console.log(dict.has('apple')); // true;
   *     console.log(dict.has('ap')); // false;
     */
    has(word: string): boolean;
    /**
     * Check whether the trie is empty.
     * @remarks Time O(1), Space O(1)
     * @returns True if size is 0.
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
      * @example
   * // Check if empty
   *  const trie = new Trie();
   *     console.log(trie.isEmpty()); // true;
   *     trie.add('word');
   *     console.log(trie.isEmpty()); // false;
     */
    isEmpty(): boolean;
    /**
     * Remove all words and reset to a fresh root.
     * @remarks Time O(1), Space O(1)
     * @returns void
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
      * @example
   * // Remove all words
   *  const trie = new Trie(['a', 'b', 'c']);
   *     trie.clear();
   *     console.log(trie.isEmpty()); // true;
     */
    clear(): void;
    /**
     * Delete one word if present.
     * @remarks Time O(L), Space O(1)
     * @param word - Word to delete.
     * @returns True if a word was removed.
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
      * @example
   * // Trie delete and iteration
   *  const trie = new Trie(['car', 'card', 'care', 'careful', 'can', 'cat']);
   *
   *     // Delete a word
   *     trie.delete('card');
   *     console.log(trie.has('card')); // false;
   *
   *     // Word with same prefix still exists
   *     console.log(trie.has('care')); // true;
   *
   *     // Size decreased
   *     console.log(trie.size); // 5;
   *
   *     // Iterate through all words
   *     const allWords = [...trie];
   *     console.log(allWords.length); // 5;
     */
    delete(word: string): boolean;
    /**
     * Compute the height (max depth) of the trie.
     * @remarks Time O(N), Space O(H)
     * @returns Maximum depth from root to a leaf.
     */
    getHeight(): number;
    /**
     * Check whether input is a proper prefix of at least one word.
     * @remarks Time O(L), Space O(1)
     * @param input - String to test as prefix.
     * @returns True if input is a prefix but not a full word.
     */
    hasPurePrefix(input: string): boolean;
    /**
     * Check whether any word starts with input.
     * @remarks Time O(L), Space O(1)
     * @param input - String to test as prefix.
     * @returns True if input matches a path from root.
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
      * @example
   * // Check if a prefix exists
   *  const trie = new Trie(['hello', 'help', 'world']);
   *
   *     console.log(trie.hasPrefix('hel')); // true;
   *     console.log(trie.hasPrefix('wor')); // true;
   *     console.log(trie.hasPrefix('xyz')); // false;
     */
    hasPrefix(input: string): boolean;
    /**
     * Check whether the trie’s longest common prefix equals input.
     * @remarks Time O(min(H,L)), Space O(1)
     * @param input - Candidate longest common prefix.
     * @returns True if input equals the common prefix.
     */
    hasCommonPrefix(input: string): boolean;
    /**
     * Return the longest common prefix among all words.
     * @remarks Time O(H), Space O(1)
     * @returns The longest common prefix string.
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
      * @example
   * // Find shared prefix
   *  const trie = new Trie(['flower', 'flow', 'flight']);
   *
   *     console.log(trie.getLongestCommonPrefix()); // 'fl';
     */
    getLongestCommonPrefix(): string;
    /**
     * Collect words under a prefix up to a maximum count.
     * @remarks Time O(K·L), Space O(K·L)
     * @param [prefix] - Prefix to match; default empty string for root.
     * @param [max] - Maximum number of words to return; default is Number.MAX_SAFE_INTEGER.
     * @param [isAllWhenEmptyPrefix] - When true, collect from root even if prefix is empty.
     * @returns Array of collected words (at most max).
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
      * @example
   * // Trie getWords and prefix search
   *  const trie = new Trie(['apple', 'app', 'apply', 'application', 'apricot']);
   *
   *     // Get all words with prefix 'app'
   *     const appWords = trie.getWords('app');
   *     console.log(appWords); // contains 'app';
   *     console.log(appWords); // contains 'apple';
   *     console.log(appWords); // contains 'apply';
   *     console.log(appWords); // contains 'application';
   *     expect(appWords).not.toContain('apricot');
     */
    getWords(prefix?: string, max?: number, isAllWhenEmptyPrefix?: boolean): string[];
    /**
     * Deep clone this trie by iterating and inserting all words.
     * @remarks Time O(ΣL), Space O(ΣL)
     * @returns A new trie with the same words and options.
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
      * @example
   * // Create independent copy
   *  const trie = new Trie(['hello', 'world']);
   *     const copy = trie.clone();
   *     copy.delete('hello');
   *     console.log(trie.has('hello')); // true;
     */
    clone(): this;
    /**
     * Filter words into a new trie of the same class.
     * @remarks Time O(ΣL), Space O(ΣL)
     * @param predicate - Predicate (word, index, trie) → boolean to keep word.
     * @param [thisArg] - Value for `this` inside the predicate.
     * @returns A new trie containing words that satisfy the predicate.
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
      * @example
   * // Filter words
   *  const trie = new Trie(['cat', 'car', 'dog', 'card']);
   *     const result = trie.filter(w => w.startsWith('ca'));
   *     console.log(result.size); // 3;
     */
    filter(predicate: ElementCallback<string, R, boolean>, thisArg?: unknown): this;
    /**
   * Transform words
  
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
    * @example
 * // Transform words
 *  const trie = new Trie(['hello', 'world']);
 *     const upper = trie.map(w => w.toUpperCase());
 *     console.log(upper.has('HELLO')); // true;
   */
    map<RM>(callback: ElementCallback<string, R, string>, options?: TrieOptions<RM>, thisArg?: unknown): Trie<RM>;
    /**
     * Map words into a new trie (possibly different record type).
     * @remarks Time O(ΣL), Space O(ΣL)
     * @template EM
     * @template RM
     * @param callback - Mapping function (word, index, trie) → newWord (string).
     * @param [options] - Options for the output trie (e.g., toElementFn, caseSensitive).
     * @param [thisArg] - Value for `this` inside the callback.
     * @returns A new Trie constructed from mapped words.
     */
    map<EM, RM>(callback: ElementCallback<string, R, EM>, options?: TrieOptions<RM>, thisArg?: unknown): IterableElementBase<EM, RM>;
    /**
     * Map words into a new trie of the same element type.
     * @remarks Time O(ΣL), Space O(ΣL)
     * @param callback - Mapping function (word, index, trie) → string.
     * @param [thisArg] - Value for `this` inside the callback.
     * @returns A new trie with mapped words.
     */
    mapSame(callback: ElementCallback<string, R, string>, thisArg?: unknown): this;
    /**
     * (Protected) Create an empty instance of the same concrete class.
     * @remarks Time O(1), Space O(1)
     * @param [options] - Options forwarded to the constructor.
     * @returns An empty like-kind trie instance.
     */
    protected _createInstance(options?: TrieOptions<R>): this;
    /**
     * (Protected) Create a like-kind trie and seed it from an iterable.
     * @remarks Time O(ΣL), Space O(ΣL)
     * @template RM
     * @param [elements] - Iterable used to seed the new trie.
     * @param [options] - Options forwarded to the constructor.
     * @returns A like-kind Trie instance.
     */
    protected _createLike<RM>(elements?: Iterable<string> | Iterable<RM>, options?: TrieOptions<RM>): Trie<RM>;
    /**
     * (Protected) Spawn an empty like-kind trie instance.
     * @remarks Time O(1), Space O(1)
     * @template RM
     * @param [options] - Options forwarded to the constructor.
     * @returns An empty like-kind Trie instance.
     */
    protected _spawnLike<RM>(options?: TrieOptions<RM>): Trie<RM>;
    /**
     * (Protected) Iterate all words in lexicographic order of edges.
     * @remarks Time O(ΣL), Space O(H)
     * @returns Iterator of words.
     */
    protected _getIterator(): IterableIterator<string>;
    /**
     * (Protected) Normalize a string according to case sensitivity.
     * @remarks Time O(L), Space O(L)
     * @param str - Input string to normalize.
     * @returns Normalized string based on caseSensitive.
     */
    protected _caseProcess(str: string): string;
}