JS Simple Trie Implementation
Tags: javascript, structure, trie
Published: 2021-12-25 14:10:05

## Introduction
As you know, Trie performs quite well on string operations such as searching and extracting a substring, especially when you have many substrings to search and simply performing normal search operations will It takes a lot of time and so in this article, I will show you a simple implementation of Trie data structure in JS language. 😃 You can use this implementation to understand how Trie works and use some of the available functions I provide. 😃 Note that this version is still quite simple and therefore may in some cases not be good for performance. 😅

## Implementation
The first thing you need is function(s) that lists the characters from a given string. I named these functions `forwardChars` and `backwardChars` respectively (they are generators). The Trie structure that I implement can allow you to search for a substring ending in a certain position, and that will be more convenient for you when performing tasks that involve replacing strings in `textarea` elements of html. And the code should be straight forward as following:

```javascript
function* forwardChars(str, index) {
    index |= 0;

    if (index < 0)
        index = 0;

    for (let i = index; i < str.length; i++)
        yield str.charCodeAt(i);
}

function* backwardChars(str, index) {
    if (index >= str.length || !Number.isSafeInteger(index)) {
        index = str.length;
        index--;
    }

    for (let i = index; i >= 0; i--)
        yield str.charCodeAt(i);
}
```

In this version, I will use character codes instead of plain characters.

Next, I implemented the `TrieNode` structure in Trie. The structure is pretty simple, it's an object that holds a `codes` mapping that maps from the next character code to the next `TrieNode`. In `TrieNode`, I provide only one method which is `next` to get the next node based on the given character code. `ensure` parameter to ensure a new node will be created instead of `null` being returned. And so, our source code will be

```javascript
class TrieNode {
    constructor() {
        this.codes = new Map();
    }

    next(code, ensure) {
        if (!this.codes.has(code)) {
            let next = null;

            if (ensure) {
                next = new TrieNode();
                this.codes.set(code, next);
            }

            return next;
        }

        return this.codes.get(code);
    }
}
```

Next, we will have the `Trie` class, which is the main class in the entire source code. In `Trie` we will have
* The constructor which is used to create a root node which is a `TrieNode`. Here, we will have the `forward` parameter to choose between forward or backward mode
* The `add(str)` function will add a substring `str` to `Trie`
* The `match(str, index)` function will match the substring `str` at position `index` and return the matched substring presented in `Trie`

And so our source code will be
```javascript
class Trie {
    constructor(forward = true) {
        this.root = new TrieNode();
        this.listChars = forward ? forwardChars : backwardChars;
    }

    add(str) {
        let current = this.root;

        for (let code of this.listChars(str))
            current = current.next(code, true);

        current.terminated = true;
    }

    match(str, index) {
        let forward = this.listChars == forwardChars;
        let current = this.root;
        let count = 0;
        let length = 0;

        index |= 0;

        for (let code of this.listChars(str, index)) {
            count++;
            current = current.next(code, false);

            if (!current)
                break;

            if (current.terminated)
                length = count;
        }

        return str.substr(forward ? index : ++index - length, length);
    }
}
```

Combine them all and the full source code is
```javascript
function* forwardChars(str, index) {
    index |= 0;

    if (index < 0)
        index = 0;

    for (let i = index; i < str.length; i++)
        yield str.charCodeAt(i);
}

function* backwardChars(str, index) {
    if (index >= str.length || !Number.isSafeInteger(index)) {
        index = str.length;
        index--;
    }

    for (let i = index; i >= 0; i--)
        yield str.charCodeAt(i);
}

class TrieNode {
    constructor() {
        this.codes = new Map();
    }

    next(code, ensure) {
        if (!this.codes.has(code)) {
            let next = null;

            if (ensure) {
                next = new TrieNode();
                this.codes.set(code, next);
            }

            return next;
        }

        return this.codes.get(code);
    }
}

class Trie {
    constructor(forward = true) {
        this.root = new TrieNode();
        this.listChars = forward ? forwardChars : backwardChars;
    }

    add(str) {
        let current = this.root;

        for (let code of this.listChars(str))
            current = current.next(code, true);

        current.terminated = true;
    }

    match(str, index) {
        let forward = this.listChars == forwardChars;
        let current = this.root;
        let count = 0;
        let length = 0;

        index |= 0;

        for (let code of this.listChars(str, index)) {
            count++;
            current = current.next(code, false);

            if (!current)
                break;

            if (current.terminated)
                length = count;
        }

        return str.substr(forward ? index : ++index - length, length);
    }
}
```
## Using the class
The thing you should focus here is the `Trie` class. Using the class is simple: initialize one, add substrings to it using `add` method and the call `match` on the string you want to extract at `index` position. So the code

```javascript
let ft = new Trie(); // this is forward trie

ft.add('abc');
ft.add('abcdef');
ft.add('xyz');

ft.match('abc', 0); // return 'abc'
ft.match('abc', 1); // return ''
ft.match('ab', 0); // return ''
ft.match('abcdef', 0); // return 'abcdef'
ft.match('abcdef', 1); // return ''
ft.match('xabcdef', 0); // return ''
ft.match('xabcdef', 1); // return 'abcdef'
ft.match('xyz', 0); // return 'xyz'
ft.match('xyz', 1); // return ''
ft.match('qxyz', 0); // return ''

let bt = new Trie(false); // this is backward trie

bt.add('abc');
bt.add('abcdef');
bt.add('xyz');

bt.match('abc', 2); // return 'abc'
bt.match('abc', 1); // return ''
bt.match('xabc', 3); // return 'abc'
bt.match('xyz', 2); // return 'xyz'
```

I hoped the implementation helped you see how to implement such a simple Trie in JS and hoped it can help you with search operations on strings. 😃 Have a nice day then. 😊