File Explorer

1/*2 * Copyright Amazon.com, Inc. or its affiliates. All Rights Reserved.3 * SPDX-License-Identifier: Apache-2.0.4 */5 6/** @internal */7export class Node<T> {8    constructor(9        public key?: string,10        public value?: T,11        public children: Map<string, Node<T>> = new Map<string, Node<T>>()) {12    }13}14 15/** @internal */16export type KeySplitter = (key: string) => string[];17/** @internal */18export enum TrieOp {19    Insert,20    Delete,21    Find,22};23 24/** @internal */25export class Trie<T> {26    protected root = new Node<T>();27    protected split_key: KeySplitter;28 29    constructor(split: KeySplitter | string) {30        if (typeof (split) === 'string') {31            const delimeter = split;32            split = (key: string) => {33                return key.split(delimeter);34            }35        }36        this.split_key = split;37    }38 39    protected find_node(key: string, op: TrieOp) {40        const parts = this.split_key(key);41        let current = this.root;42        let parent = undefined;43        for (const part of parts) {44            let child = current.children.get(part);45            if (!child) {46                if (op == TrieOp.Insert) {47                    current.children.set(part, child = new Node(part));48                }49                else {50                    return undefined;51                }52            }53            parent = current;54            current = child;55        }56        if (parent && op == TrieOp.Delete) {57            parent.children.delete(current.key!);58        }59        return current;60    }61 62    insert(key: string, value: T) {63        let node = this.find_node(key, TrieOp.Insert);64        node!.value = value;65    }66 67    remove(key: string) {68        this.find_node(key, TrieOp.Delete);69    }70 71    find(key: string) {72        const node = this.find_node(key, TrieOp.Find);73        return node ? node.value : undefined;74    }75}76