Typeahead / Search Autocomplete

interface TrieNode {
  char: string;
  children: Map<string, TrieNode>;
  isEndOfWord: boolean;
  frequency: number;                // global search count
  topK: Array<{ term: string; score: number }>;  // pre-computed, k=10
}

{
  "prefix": "ap",
  "topK": [
    { "term": "apple",   "score": 9800000 },
    { "term": "app",     "score": 7200000 },
    { "term": "apply",   "score": 3100000 },
    { "term": "apple tv","score": 2100000 },
    { "term": "apnews",  "score": 1900000 }
  ],
  "updatedAt": 1719500000
}

interface QueryLog {
  _id: ObjectId;
  query: string;        // normalized (lowercase, trimmed)
  userId?: string;      // null for anonymous
  sessionId: string;
  timestamp: Date;
  resultCount: number;  // for future relevance tuning
}

{
  "prefix": "ap",
  "suggestions": [
    { "term": "apple",  "score": 9800000 },
    { "term": "app",    "score": 7200000 }
  ],
  "source": "cache"
}

class SuggestionService {
  async getSuggestions(prefix: string, k: number): Promise<Term[]>
  async logQuery(query: string, userId?: string, sessionId: string): Promise<void>
  async getPersonalized(prefix: string, userId: string): Promise<Term[]>
}

class TrieBuilder {
  async rebuildTrie(windowDays: number): Promise<void>
  async aggregateFrequencies(since: Date): Promise<Map<string, number>>
  async pushToCache(trie: TrieNode): Promise<void>
}

// --- Trie Data Structure ---

class TrieNode {
  char: string;
  children: Map<string, TrieNode> = new Map();
  isEndOfWord = false;
  frequency = 0;
  topK: Array<{ term: string; score: number }> = [];

  constructor(char: string) {
    this.char = char;
  }
}

class Trie {
  private root: TrieNode = new TrieNode('');

  insert(term: string, frequency: number): void {
    let node = this.root;
    for (const char of term.toLowerCase()) {
      if (!node.children.has(char)) {
        node.children.set(char, new TrieNode(char));
      }
      node = node.children.get(char)!;
    }
    node.isEndOfWord = true;
    node.frequency = frequency;
  }

  /** O(p) prefix lookup — returns pre-computed topK at the prefix node */
  search(prefix: string): Array<{ term: string; score: number }> {
    let node = this.root;
    for (const char of prefix.toLowerCase()) {
      if (!node.children.has(char)) return [];
      node = node.children.get(char)!;
    }
    return node.topK;
  }

  /** Called after all insertions — compute top-k at each node bottom-up */
  computeTopK(k = 10): void {
    this._computeTopKDFS(this.root, '', k);
  }

  private _computeTopKDFS(node: TrieNode, prefix: string, k: number): Array<{ term: string; score: number }> {
    let candidates: Array<{ term: string; score: number }> = [];
    if (node.isEndOfWord) {
      candidates.push({ term: prefix, score: node.frequency });
    }
    for (const [char, child] of node.children) {
      candidates.push(...this._computeTopKDFS(child, prefix + char, k));
    }
    candidates.sort((a, b) => b.score - a.score);
    node.topK = candidates.slice(0, k);
    return node.topK;
  }
}

// --- Service Layer ---

class SuggestionService {
  constructor(
    private readonly prefixCache: PrefixCache,
    private readonly queryLogRepo: QueryLogRepository,
    private readonly trie: Trie,   // in-memory fallback
  ) {}

  async getSuggestions(prefix: string, k = 5): Promise<Array<{ term: string; score: number }>> {
    const normalized = prefix.toLowerCase().trim();
    if (!normalized) return [];

    // 1. Try Redis cache (O(1))
    const cached = await this.prefixCache.get(normalized);
    if (cached) return cached.topK.slice(0, k);

    // 2. Fallback to in-memory trie
    return this.trie.search(normalized).slice(0, k);
  }

  async logQuery(query: string, userId?: string, sessionId?: string): Promise<void> {
    // Fire-and-forget — do not await in hot path
    this.queryLogRepo.insert({
      query: query.toLowerCase().trim(),
      userId,
      sessionId,
      timestamp: new Date(),
    }).catch(err => logger.error('logQuery failed', { err }));
  }
}

// --- Cache Adapter ---

class PrefixCache {
  constructor(private readonly redis: RedisClient) {}

  async get(prefix: string): Promise<{ topK: Array<{ term: string; score: number }> } | null> {
    const raw = await this.redis.get(`suggest:${prefix}`);
    return raw ? JSON.parse(raw) : null;
  }

  async set(prefix: string, data: { topK: Array<{ term: string; score: number }> }, ttlSec = 7200): Promise<void> {
    await this.redis.set(`suggest:${prefix}`, JSON.stringify(data), 'EX', ttlSec);
  }
}