Trees & Hierarchical Structures

/**
 * Prefix tree for string operations
 * @param Token Optional token constructor for custom tokenization
 */
function Trie<T>(Token?: new () => T): Trie<T>;

interface Trie<T> {
  readonly size: number;
  
  /** Add string/sequence to trie */
  add(sequence: Iterable<T>): this;
  
  /** Remove string/sequence from trie */
  delete(sequence: Iterable<T>): boolean;
  
  /** Check if exact sequence exists */
  has(sequence: Iterable<T>): boolean;
  
  /** Find node for given prefix */
  find(prefix: Iterable<T>): TrieNode<T> | null;
  
  /** Get all sequences with given prefix */
  prefixes(prefix: Iterable<T>): Array<Array<T>>;
  
  /** Remove all sequences */
  clear(): void;
  
  values(): IterableIterator<Array<T>>;
  [Symbol.iterator](): IterableIterator<Array<T>>;
  
  inspect(): any;
}

interface TrieNode<T> {
  /** Check if this node represents end of a sequence */
  readonly final: boolean;
  
  /** Get child node for token */
  get(token: T): TrieNode<T> | undefined;
  
  /** Check if child exists for token */
  has(token: T): boolean;
  
  /** Iterate over all sequences from this node */
  suffixes(): Array<Array<T>>;
}

/**
 * Prefix tree with key-value associations
 * @param Token Optional token constructor for custom tokenization
 */
function TrieMap<T, V>(Token?: new () => T): TrieMap<T, V>;

interface TrieMap<T, V> {
  readonly size: number;
  
  /** Store key-value pair */
  set(key: Iterable<T>, value: V): this;
  
  /** Get value for exact key */
  get(key: Iterable<T>): V | undefined;
  
  /** Check if exact key exists */
  has(key: Iterable<T>): boolean;
  
  /** Remove key-value pair */
  delete(key: Iterable<T>): boolean;
  
  /** Find node for given prefix */
  find(prefix: Iterable<T>): TrieMapNode<T, V> | null;
  
  /** Get all key-value pairs with given prefix */
  prefixes(prefix: Iterable<T>): Array<[Array<T>, V]>;
  
  clear(): void;
  
  values(): IterableIterator<V>;
  keys(): IterableIterator<Array<T>>;
  entries(): IterableIterator<[Array<T>, V]>;
  [Symbol.iterator](): IterableIterator<[Array<T>, V]>;
  
  inspect(): any;
}

/**
 * BK-Tree for fuzzy string matching
 * @param distance Distance function (e.g., Levenshtein distance)
 */
function BKTree(distance: DistanceFunction): BKTree;

interface BKTree {
  readonly size: number;
  
  /** Add item to tree */
  add(item: string): this;
  
  /** Search for items within tolerance */
  search(query: string, tolerance: number): Array<string>;
  
  /** Remove all items */
  clear(): void;
  
  values(): IterableIterator<string>;
  [Symbol.iterator](): IterableIterator<string>;
  
  inspect(): any;
}

type DistanceFunction = (a: string, b: string) => number;

/**
 * k-dimensional tree for spatial data
 * @param dimensions Number of dimensions
 * @param distance Optional distance function
 * @param axisAccessor Optional function to access axis values
 */
function KDTree(
  dimensions: number,
  distance?: DistanceFunction,
  axisAccessor?: AxisAccessor
): KDTree;

interface KDTree {
  readonly dimensions: number;
  readonly size: number;
  
  /** Add point to tree */
  add(point: Point): this;
  
  /** Find k nearest neighbors */
  nearestNeighbor(query: Point, k?: number): Array<Point>;
  
  /** Find all points within range */
  range(bounds: Bounds): Array<Point>;
  
  clear(): void;
  
  values(): IterableIterator<Point>;
  [Symbol.iterator](): IterableIterator<Point>;
  
  inspect(): any;
}

type Point = Array<number> | {[key: string]: number};
type Bounds = Array<[number, number]>; // Min-max pairs for each dimension
type AxisAccessor = (point: Point, axis: number) => number;

/**
 * Vantage-point tree for metric space queries
 * @param distance Distance function for items
 * @param items Optional initial items to build tree
 */
function VPTree(distance: DistanceFunction, items?: Array<any>): VPTree;

interface VPTree {
  readonly size: number;
  
  /** Find k nearest neighbors */
  nearestNeighbors(query: any, k: number): Array<any>;
  
  /** Find all items within radius */
  neighbors(query: any, radius: number): Array<any>;
  
  values(): IterableIterator<any>;
  [Symbol.iterator](): IterableIterator<any>;
  
  inspect(): any;
}

/**
 * Static interval tree for range queries
 * @param intervals Array of intervals to build tree from
 */
function StaticIntervalTree(intervals: Array<Interval>): StaticIntervalTree;

interface StaticIntervalTree {
  readonly size: number;
  
  /** Find all intervals overlapping with query interval */
  search(interval: Interval): Array<Interval>;
  
  values(): IterableIterator<Interval>;
  [Symbol.iterator](): IterableIterator<Interval>;
  
  inspect(): any;
}

type Interval = [number, number]; // [start, end]

import {Trie} from "mnemonist";

// String trie for autocomplete
const dictionary = new Trie();
dictionary.add("apple");
dictionary.add("application");
dictionary.add("apply");
dictionary.add("banana");

console.log(dictionary.has("app")); // false (not complete word)
console.log(dictionary.has("apple")); // true

// Get all words with prefix
const suggestions = dictionary.prefixes("app");
console.log(suggestions); // [["apple"], ["application"], ["apply"]]

// Navigate trie structure
const appNode = dictionary.find("app");
if (appNode) {
  console.log(appNode.suffixes()); // All suffixes from "app"
}

import {TrieMap} from "mnemonist";

// Prefix-based configuration
const config = new TrieMap();
config.set("server.port", 8080);
config.set("server.host", "localhost");
config.set("database.url", "mongodb://localhost");

console.log(config.get("server.port")); // 8080

// Get all configs with prefix
const serverConfigs = config.prefixes("server");
// [[["server", "port"], 8080], [["server", "host"], "localhost"]]

import {BKTree} from "mnemonist";

// Levenshtein distance function
function levenshtein(a: string, b: string): number {
  // Implementation of edit distance
  const matrix = [];
  for (let i = 0; i <= b.length; i++) {
    matrix[i] = [i];
  }
  for (let j = 0; j <= a.length; j++) {
    matrix[0][j] = j;
  }
  for (let i = 1; i <= b.length; i++) {
    for (let j = 1; j <= a.length; j++) {
      if (b.charAt(i - 1) === a.charAt(j - 1)) {
        matrix[i][j] = matrix[i - 1][j - 1];
      } else {
        matrix[i][j] = Math.min(
          matrix[i - 1][j - 1] + 1,
          matrix[i][j - 1] + 1,
          matrix[i - 1][j] + 1
        );
      }
    }
  }
  return matrix[b.length][a.length];
}

// Spell checker
const spellChecker = new BKTree(levenshtein);
spellChecker.add("javascript");
spellChecker.add("python");
spellChecker.add("typescript");

// Find similar words
const suggestions = spellChecker.search("javascrip", 2);
console.log(suggestions); // ["javascript"] (distance 1)

import {KDTree} from "mnemonist";

// 2D spatial index
const spatialIndex = new KDTree(2);
spatialIndex.add([1, 2]);
spatialIndex.add([3, 4]);
spatialIndex.add([5, 1]);
spatialIndex.add([2, 8]);

// Find nearest neighbors
const nearest = spatialIndex.nearestNeighbor([2, 3], 2);
console.log(nearest); // Closest 2 points to [2, 3]

// Range query
const inRange = spatialIndex.range([[0, 4], [0, 5]]);
console.log(inRange); // Points in rectangle (0,0) to (4,5)

import {VPTree} from "mnemonist";

// Text similarity search
function cosineSimilarity(a: string, b: string): number {
  // Implementation of cosine similarity
  return /* calculated similarity */;
}

const documents = [
  "machine learning algorithms",
  "deep learning neural networks", 
  "artificial intelligence systems",
  "natural language processing"
];

const similarityIndex = new VPTree(cosineSimilarity, documents);

// Find similar documents
const query = "neural network learning";
const similar = similarityIndex.nearestNeighbors(query, 2);
console.log(similar); // Most similar documents