trie-typed

What

Brief

This is a standalone Trie data structure from the data-structure-typed collection. If you wish to access more data structures or advanced features, you can transition to directly installing the complete data-structure-typed package

How

install

npm

npm i trie-typed --save

yarn

yarn add trie-typed

snippet

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']

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']

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')); // []

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

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

API docs & Examples

API Docs

Live Examples

Examples Repository

Data Structures

Data Structure	Unit Test	Performance Test	API Docs
Trie			Trie

Standard library data structure comparison

Data Structure Typed	C++ STL	java.util	Python collections
Trie	-	-	-

Benchmark

trie

test name	time taken (ms)	executions per sec	sample deviation
100,000 push	45.97	21.76	0.00
100,000 getWords	66.20	15.11	0.00

Built-in classic algorithms

Algorithm	Function Description	Iteration Type

Software Engineering Design Standards

Principle	Description
Practicality	Follows ES6 and ESNext standards, offering unified and considerate optional parameters, and simplifies method names.
Extensibility	Adheres to OOP (Object-Oriented Programming) principles, allowing inheritance for all data structures.
Modularization	Includes data structure modularization and independent NPM packages.
Efficiency	All methods provide time and space complexity, comparable to native JS performance.
Maintainability	Follows open-source community development standards, complete documentation, continuous integration, and adheres to TDD (Test-Driven Development) patterns.
Testability	Automated and customized unit testing, performance testing, and integration testing.
Portability	Plans for porting to Java, Python, and C++, currently achieved to 80%.
Reusability	Fully decoupled, minimized side effects, and adheres to OOP.
Security	Carefully designed security for member variables and methods. Read-write separation. Data structure software does not need to consider other security aspects.
Scalability	Data structure software does not involve load issues.