/**
 * @module trie
 * @description A Trie data structure implementation that supports wildcard matching
 * @template T The type of values stored in the trie
 */
export type Parts = string[];

/**
 * Trie class for storing and matching hierarchical key-value pairs with wildcard support
 * @template T The type of values stored in the trie
 */
export class Trie<T> {
  #value: Array<T>;
  #children: Map<string, Trie<T>>;
  private separator = "/";
  private wildcardOne = "+";
  private wildcardSubtree = "#";
  private reservedPrefix = "$";
  private looseCompare: boolean;

  /**
   * Creates a new Trie instance
   * @param looseCompare Whether to use loose comparison for object values
   */
  constructor(looseCompare = false) {
    this.#value = [];
    this.#children = new Map();
    this.looseCompare = looseCompare;
  }

  /**
   * Matches a child node with the given key parts
   * @param child The child node key to match
   * @param parts Remaining parts of the key to match
   * @returns Array of matched values
   */
  matchChild(child: string, parts: Parts): Array<T> {
    const childNode = this.#children.get(child);
    return childNode ? childNode._match(parts) : [];
  }

  /**
   * Matches a key against the trie
   * @param key The key to match
   * @returns Array of matched values
   */
  match(key: string): T[] {
    const parts = key.split(this.separator);
    if (parts.length > 0 && parts[0]?.charAt(0) === this.reservedPrefix) {
      return this._matchPrefix(parts);
    }
    return this._match(parts);
  }

  /**
   * Internal method to match reserved prefix keys
   * @param parts Parts of the key to match
   * @returns Array of matched values
   */
  private _matchPrefix(parts: Parts): Array<T> {
    const [first, ...rest] = parts;
    if (first === undefined) return [];

    // Direct lookup on the reserved topic node without evaluating top-level + or #
    return this.matchChild(first, rest);
  }

  /**
   * Internal method to match keys with wildcard support
   * @param parts Parts of the key to match
   * @returns Array of matched values
   */
  private _match(parts: Parts): Array<T> {
    let results: Array<T> = [];

    // 1. Check if there is a multi-level wildcard ('#') at this level.
    // In MQTT, 'a/#' matches 'a', 'a/b', 'a/b/c', etc.
    const subtreeNode = this.#children.get(this.wildcardSubtree);
    if (subtreeNode) {
      results = results.concat(subtreeNode.#value);
    }

    // 2. Base case: we reached the end of the topic parts.
    if (parts.length === 0) {
      return results.concat(this.#value);
    }

    const [first, ...rest] = parts;
    // deno-coverage-ignore
    if (first === undefined) return [];

    // 3. Exact matching child node
    const exact = this.matchChild(first, rest);

    // 4. Single-level wildcard ('+') matching child node
    const single = this.matchChild(this.wildcardOne, rest);

    return results.concat(exact, single);
  }

  /**
   * Adds a value to the trie at the specified key
   * @param key The key to add the value at
   * @param value The value to add
   */
  add(key: string, value: T): void {
    return this._add(key.split(this.separator), value);
  }

  /**
   * Internal method to recursively add a value
   * @param parts Parts of the key to add at
   * @param value The value to add
   */
  private _add(parts: Parts, value: T): void {
    if (parts.length === 0) {
      this.#value = this.#value.concat(value);
      return;
    }
    const [first, ...rest] = parts;
    // deno-coverage-ignore
    if (first === undefined) return;
    const child = this.#children.get(first);
    if (child instanceof Trie) {
      child._add(rest, value);
    } else {
      const node = new Trie<T>(this.looseCompare);
      this.#children.set(first, node);
      node._add(rest, value);
    }
  }

  /**
   * Removes a value from the trie at the specified key
   * @param key The key to remove the value from
   * @param value The value to remove
   */
  /**
   * Removes a value from the trie at the specified key
   * @param key The key to remove the value from
   * @param value The value (or partial object) to remove
   */
  remove(key: string, value: Partial<T> | T): void {
    return this._remove(key.split(this.separator), value);
  }

  /**
   * Internal method to recursively remove a value
   * @param parts Parts of the key to remove from
   * @param value The value to remove
   */
  private _remove(parts: Parts, value: Partial<T> | T): void {
    if (parts.length === 0) {
      const arr = this.#value;
      this.#value = arr.filter(this.filter(value));
      return;
    }
    const [first, ...rest] = parts;
    // deno-coverage-ignore
    if (first === undefined) return;
    const node = this.#children.get(first);
    if (node) {
      node._remove(rest, value);
      if (node.#value.length === 0 && node.#children.size === 0) {
        this.#children.delete(first);
      }
    }
  }

  /**
   * Creates a filter function for removing values
   * Supports partial object matching when looseCompare is enabled or when matching objects.
   * @param value The value (or partial value) to filter against
   * @returns Filter function (returns true to KEEP the item, false to REMOVE it)
   */
  private filter(value: Partial<T> | T): (item: T) => boolean {
    if (typeof value === "object" && value !== null) {
      return (item) => {
        if (typeof item !== "object" || item === null) {
          return true; // Keep if the stored item isn't an object but we are filtering by one
        }

        // Check if every key-value pair in our filter object matches the stored item
        for (const key in value) {
          if (Object.prototype.hasOwnProperty.call(value, key)) {
            // If the stored item has a different value (or doesn't have the key), it's not a match
            if (item[key] !== value[key]) {
              return true; // Keep the item (no match)
            }
          }
        }
        return false; // Remove the item (it matches all criteria in the partial object)
      };
    }

    // Fallback for primitives
    return (item) => item !== value;
  }
}