AdvancedTrieAutoComplete.java

/**
 * Advanced Trie Data Structure with Auto-Complete Implementation
 * 
 * This program demonstrates advanced concepts including:
 * - Trie (Prefix Tree) data structure implementation
 * - Auto-complete functionality with prefix matching
 * - Fuzzy search with Levenshtein distance algorithm
 * - Frequency-based word suggestions and ranking
 * - Memory-efficient storage with compressed nodes
 * - Advanced search algorithms and optimization
 * - Real-time suggestion generation
 * - Dictionary management with batch operations
 * 
 * Features:
 * 1. Fast prefix-based auto-complete (O(m) where m is prefix length)
 * 2. Fuzzy search for typo tolerance
 * 3. Frequency-based word ranking
 * 4. Memory-optimized storage
 * 5. Batch insert/delete operations
 * 6. Advanced search with filters
 * 7. Export/Import functionality
 * 8. Performance monitoring and statistics
 * 
 * @author Contributing to Hacktoberfest 2025
 * @version 2.0
 */

import java.util.*;
import java.util.concurrent.*;
import java.util.stream.Collectors;
import java.io.*;
import java.nio.file.*;

/**
 * Represents a node in the Trie structure
 */
class TrieNode {
    private final Map<Character, TrieNode> children;
    private boolean isEndOfWord;
    private int frequency;
    private String word; // Store complete word for efficiency
    private long lastAccessed;
    private Set<String> metadata; // Additional word information (synonyms, categories, etc.)
    
    public TrieNode() {
        this.children = new ConcurrentHashMap<>(); // Thread-safe for concurrent operations
        this.isEndOfWord = false;
        this.frequency = 0;
        this.lastAccessed = System.currentTimeMillis();
        this.metadata = new HashSet<>();
    }
    
    // Getters and setters
    public Map<Character, TrieNode> getChildren() { return children; }
    public boolean isEndOfWord() { return isEndOfWord; }
    public void setEndOfWord(boolean endOfWord) { 
        this.isEndOfWord = endOfWord;
        this.lastAccessed = System.currentTimeMillis();
    }
    public int getFrequency() { return frequency; }
    public void incrementFrequency() { 
        this.frequency++;
        this.lastAccessed = System.currentTimeMillis();
    }
    public void setFrequency(int frequency) { this.frequency = frequency; }
    public String getWord() { return word; }
    public void setWord(String word) { this.word = word; }
    public long getLastAccessed() { return lastAccessed; }
    public Set<String> getMetadata() { return metadata; }
    public void addMetadata(String meta) { metadata.add(meta); }
}

/**
 * Represents a search result with ranking information
 */
class SearchResult implements Comparable<SearchResult> {
    private final String word;
    private final int frequency;
    private final int editDistance;
    private final double relevanceScore;
    private final Set<String> metadata;
    private final long lastAccessed;
    
    public SearchResult(String word, int frequency, int editDistance, Set<String> metadata, long lastAccessed) {
        this.word = word;
        this.frequency = frequency;
        this.editDistance = editDistance;
        this.metadata = new HashSet<>(metadata);
        this.lastAccessed = lastAccessed;
        
        // Calculate relevance score based on multiple factors
        double frequencyScore = Math.log(frequency + 1) * 10; // Logarithmic frequency scoring
        double distanceScore = Math.max(0, 50 - (editDistance * 10)); // Penalty for edit distance
        double recencyScore = (System.currentTimeMillis() - lastAccessed) < 86400000 ? 5 : 0; // Recent access bonus
        
        this.relevanceScore = frequencyScore + distanceScore + recencyScore;
    }
    
    @Override
    public int compareTo(SearchResult other) {
        // Primary sort by relevance score (higher is better)
        int scoreComparison = Double.compare(other.relevanceScore, this.relevanceScore);
        if (scoreComparison != 0) return scoreComparison;
        
        // Secondary sort by frequency (higher is better)
        int frequencyComparison = Integer.compare(other.frequency, this.frequency);
        if (frequencyComparison != 0) return frequencyComparison;
        
        // Tertiary sort by edit distance (lower is better)
        int distanceComparison = Integer.compare(this.editDistance, other.editDistance);
        if (distanceComparison != 0) return distanceComparison;
        
        // Final sort by lexicographical order
        return this.word.compareTo(other.word);
    }
    
    // Getters
    public String getWord() { return word; }
    public int getFrequency() { return frequency; }
    public int getEditDistance() { return editDistance; }
    public double getRelevanceScore() { return relevanceScore; }
    public Set<String> getMetadata() { return metadata; }
    public long getLastAccessed() { return lastAccessed; }
    
    @Override
    public String toString() {
        return String.format("%s (freq: %d, dist: %d, score: %.1f)", 
                           word, frequency, editDistance, relevanceScore);
    }
}

/**
 * Statistics and monitoring for the Trie
 */
class TrieStatistics {
    private int totalWords = 0;
    private int totalNodes = 0;
    private long totalSearches = 0;
    private long totalInsertions = 0;
    private final Map<String, Integer> searchPatterns = new ConcurrentHashMap<>();
    private final Map<Integer, Integer> prefixLengthDistribution = new ConcurrentHashMap<>();
    
    public void recordSearch(String prefix) {
        totalSearches++;
        searchPatterns.merge(prefix, 1, Integer::sum);
        prefixLengthDistribution.merge(prefix.length(), 1, Integer::sum);
    }
    
    public void recordInsertion() { totalInsertions++; }
    public void setTotalWords(int totalWords) { this.totalWords = totalWords; }
    public void setTotalNodes(int totalNodes) { this.totalNodes = totalNodes; }
    
    public void printStatistics() {
        System.out.println("\n=== Advanced Trie Statistics ===");
        System.out.println("Total Words: " + totalWords);
        System.out.println("Total Nodes: " + totalNodes);
        System.out.println("Memory Efficiency: " + (totalWords > 0 ? (totalWords * 100.0 / totalNodes) : 0) + "%");
        System.out.println("Total Searches: " + totalSearches);
        System.out.println("Total Insertions: " + totalInsertions);
        System.out.println("Average Searches per Word: " + (totalWords > 0 ? (totalSearches * 1.0 / totalWords) : 0));
        
        if (!searchPatterns.isEmpty()) {
            System.out.println("\nMost Popular Search Prefixes:");
            searchPatterns.entrySet().stream()
                .sorted(Map.Entry.<String, Integer>comparingByValue().reversed())
                .limit(5)
                .forEach(entry -> System.out.printf("  '%s': %d searches%n", entry.getKey(), entry.getValue()));
        }
        
        if (!prefixLengthDistribution.isEmpty()) {
            System.out.println("\nPrefix Length Distribution:");
            prefixLengthDistribution.entrySet().stream()
                .sorted(Map.Entry.comparingByKey())
                .forEach(entry -> System.out.printf("  Length %d: %d searches%n", entry.getKey(), entry.getValue()));
        }
    }
}

/**
 * Main Advanced Trie Auto-Complete Implementation
 */
public class AdvancedTrieAutoComplete {
    private final TrieNode root;
    private final TrieStatistics statistics;
    private final int maxSuggestions;
    private final int maxEditDistance;
    
    public AdvancedTrieAutoComplete() {
        this(10, 2);
    }
    
    public AdvancedTrieAutoComplete(int maxSuggestions, int maxEditDistance) {
        this.root = new TrieNode();
        this.statistics = new TrieStatistics();
        this.maxSuggestions = maxSuggestions;
        this.maxEditDistance = maxEditDistance;
    }
    
    /**
     * Insert a word into the Trie with optional metadata
     */
    public void insert(String word, String... metadata) {
        if (word == null || word.trim().isEmpty()) return;
        
        word = word.toLowerCase().trim();
        TrieNode current = root;
        
        for (char c : word.toCharArray()) {
            current = current.getChildren().computeIfAbsent(c, k -> new TrieNode());
        }
        
        current.setEndOfWord(true);
        current.incrementFrequency();
        current.setWord(word);
        
        // Add metadata if provided
        for (String meta : metadata) {
            if (meta != null && !meta.trim().isEmpty()) {
                current.addMetadata(meta.trim().toLowerCase());
            }
        }
        
        statistics.recordInsertion();
    }
    
    /**
     * Batch insert multiple words for better performance
     */
    public void batchInsert(Collection<String> words) {
        words.parallelStream().forEach(this::insert);
        updateStatistics();
    }
    
    /**
     * Search for exact word match
     */
    public boolean search(String word) {
        if (word == null || word.trim().isEmpty()) return false;
        
        TrieNode node = findNode(word.toLowerCase().trim());
        if (node != null && node.isEndOfWord()) {
            node.incrementFrequency(); // Update frequency on access
            return true;
        }
        return false;
    }
    
    /**
     * Get auto-complete suggestions for a prefix
     */
    public List<SearchResult> getAutoCompleteSuggestions(String prefix) {
        return getAutoCompleteSuggestions(prefix, maxSuggestions);
    }
    
    public List<SearchResult> getAutoCompleteSuggestions(String prefix, int limit) {
        if (prefix == null || prefix.trim().isEmpty()) {
            return new ArrayList<>();
        }
        
        prefix = prefix.toLowerCase().trim();
        statistics.recordSearch(prefix);
        
        TrieNode prefixNode = findNode(prefix);
        if (prefixNode == null) {
            // If exact prefix not found, try fuzzy search
            return getFuzzySearchSuggestions(prefix, limit);
        }
        
        Set<SearchResult> results = new HashSet<>();
        collectWords(prefixNode, prefix, results, 0);
        
        return results.stream()
            .sorted()
            .limit(limit)
            .collect(Collectors.toList());
    }
    
    /**
     * Fuzzy search with edit distance tolerance
     */
    public List<SearchResult> getFuzzySearchSuggestions(String query, int limit) {
        if (query == null || query.trim().isEmpty()) {
            return new ArrayList<>();
        }
        
        query = query.toLowerCase().trim();
        Set<SearchResult> results = new HashSet<>();
        
        collectFuzzyMatches(root, "", query, 0, results);
        
        return results.stream()
            .filter(result -> result.getEditDistance() <= maxEditDistance)
            .sorted()
            .limit(limit)
            .collect(Collectors.toList());
    }
    
    /**
     * Advanced search with filters
     */
    public List<SearchResult> advancedSearch(String query, Set<String> requiredMetadata, 
                                           int minFrequency, long maxAge) {
        List<SearchResult> baseSuggestions = getAutoCompleteSuggestions(query, maxSuggestions * 2);
        
        return baseSuggestions.stream()
            .filter(result -> result.getFrequency() >= minFrequency)
            .filter(result -> (System.currentTimeMillis() - result.getLastAccessed()) <= maxAge)
            .filter(result -> requiredMetadata == null || requiredMetadata.isEmpty() || 
                   result.getMetadata().containsAll(requiredMetadata))
            .limit(maxSuggestions)
            .collect(Collectors.toList());
    }
    
    /**
     * Find node for a given prefix
     */
    private TrieNode findNode(String prefix) {
        TrieNode current = root;
        for (char c : prefix.toCharArray()) {
            TrieNode next = current.getChildren().get(c);
            if (next == null) return null;
            current = next;
        }
        return current;
    }
    
    /**
     * Collect all words from a subtree
     */
    private void collectWords(TrieNode node, String prefix, Set<SearchResult> results, int editDistance) {
        if (node.isEndOfWord()) {
            results.add(new SearchResult(
                prefix, 
                node.getFrequency(), 
                editDistance, 
                node.getMetadata(),
                node.getLastAccessed()
            ));
        }
        
        if (results.size() >= maxSuggestions * 3) return; // Prevent excessive collection
        
        for (Map.Entry<Character, TrieNode> entry : node.getChildren().entrySet()) {
            collectWords(entry.getValue(), prefix + entry.getKey(), results, editDistance);
        }
    }
    
    /**
     * Collect fuzzy matches using dynamic programming
     */
    private void collectFuzzyMatches(TrieNode node, String currentWord, String query, 
                                   int depth, Set<SearchResult> results) {
        if (depth > query.length() + maxEditDistance) return;
        if (results.size() >= maxSuggestions * 2) return;
        
        if (node.isEndOfWord()) {
            int editDistance = calculateEditDistance(currentWord, query);
            if (editDistance <= maxEditDistance) {
                results.add(new SearchResult(
                    currentWord,
                    node.getFrequency(),
                    editDistance,
                    node.getMetadata(),
                    node.getLastAccessed()
                ));
            }
        }
        
        for (Map.Entry<Character, TrieNode> entry : node.getChildren().entrySet()) {
            collectFuzzyMatches(
                entry.getValue(), 
                currentWord + entry.getKey(), 
                query, 
                depth + 1, 
                results
            );
        }
    }
    
    /**
     * Calculate Levenshtein distance between two strings
     */
    private int calculateEditDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();
        
        int[][] dp = new int[m + 1][n + 1];
        
        // Initialize base cases
        for (int i = 0; i <= m; i++) dp[i][0] = i;
        for (int j = 0; j <= n; j++) dp[0][j] = j;
        
        // Fill the dp table
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = 1 + Math.min(
                        Math.min(dp[i - 1][j], dp[i][j - 1]),
                        dp[i - 1][j - 1]
                    );
                }
            }
        }
        
        return dp[m][n];
    }
    
    /**
     * Update internal statistics
     */
    private void updateStatistics() {
        int[] nodeCount = {0};
        int[] wordCount = {0};
        countNodes(root, nodeCount, wordCount);
        
        statistics.setTotalNodes(nodeCount[0]);
        statistics.setTotalWords(wordCount[0]);
    }
    
    /**
     * Recursively count nodes and words
     */
    private void countNodes(TrieNode node, int[] nodeCount, int[] wordCount) {
        nodeCount[0]++;
        if (node.isEndOfWord()) wordCount[0]++;
        
        for (TrieNode child : node.getChildren().values()) {
            countNodes(child, nodeCount, wordCount);
        }
    }
    
    /**
     * Export dictionary to file
     */
    public void exportDictionary(String filename) throws IOException {
        List<String> words = new ArrayList<>();
        collectAllWords(root, "", words);
        
        Files.write(
            Paths.get(filename), 
            words, 
            StandardOpenOption.CREATE, 
            StandardOpenOption.TRUNCATE_EXISTING
        );
        
        System.out.println("Dictionary exported to " + filename + " (" + words.size() + " words)");
    }
    
    /**
     * Import dictionary from file
     */
    public void importDictionary(String filename) throws IOException {
        List<String> words = Files.readAllLines(Paths.get(filename));
        batchInsert(words);
        System.out.println("Dictionary imported from " + filename + " (" + words.size() + " words)");
    }
    
    /**
     * Collect all words in the Trie
     */
    private void collectAllWords(TrieNode node, String prefix, List<String> words) {
        if (node.isEndOfWord()) {
            words.add(prefix);
        }
        
        for (Map.Entry<Character, TrieNode> entry : node.getChildren().entrySet()) {
            collectAllWords(entry.getValue(), prefix + entry.getKey(), words);
        }
    }
    
    /**
     * Get statistics
     */
    public TrieStatistics getStatistics() {
        updateStatistics();
        return statistics;
    }
    
    /**
     * Demo method showing various features
     */
    public static void main(String[] args) throws IOException {
        System.out.println("=== Advanced Trie Auto-Complete Demo ===\n");
        
        AdvancedTrieAutoComplete trie = new AdvancedTrieAutoComplete(8, 2);
        
        // Sample dictionary with metadata
        String[] programmingWords = {
            "java", "javascript", "python", "programming", "algorithm", "data", "structure",
            "computer", "science", "software", "development", "coding", "debugging",
            "object", "oriented", "functional", "recursive", "iterative", "complexity",
            "optimization", "performance", "scalability", "architecture", "design",
            "pattern", "framework", "library", "api", "database", "query", "index"
        };
        
        System.out.println("Building dictionary...");
        for (String word : programmingWords) {
            // Add metadata categories
            if (word.contains("java") || word.equals("python")) {
                trie.insert(word, "language", "popular");
            } else if (word.equals("algorithm") || word.equals("complexity") || word.equals("optimization")) {
                trie.insert(word, "algorithm", "theory");
            } else if (word.equals("database") || word.equals("query") || word.equals("index")) {
                trie.insert(word, "database", "storage");
            } else {
                trie.insert(word, "programming", "general");
            }
        }
        
        // Simulate some popular searches to build frequency data
        String[] popularSearches = {"java", "javascript", "programming", "algorithm", "data"};
        for (String search : popularSearches) {
            for (int i = 0; i < 5; i++) { // Simulate multiple searches
                trie.search(search);
            }
        }
        
        System.out.println("Dictionary built with " + programmingWords.length + " words.\n");
        
        // Demo 1: Basic Auto-Complete
        System.out.println("=== Demo 1: Auto-Complete Suggestions ===");
        String[] prefixes = {"pro", "alg", "dat", "ja"};
        
        for (String prefix : prefixes) {
            System.out.println("\\nSuggestions for '" + prefix + "':");
            List<SearchResult> suggestions = trie.getAutoCompleteSuggestions(prefix);
            for (int i = 0; i < suggestions.size() && i < 5; i++) {
                System.out.println("  " + (i + 1) + ". " + suggestions.get(i));
            }
        }
        
        // Demo 2: Fuzzy Search
        System.out.println("\\n\\n=== Demo 2: Fuzzy Search (Typo Tolerance) ===");
        String[] typos = {"javs", "progamming", "algrithm", "databse"};
        
        for (String typo : typos) {
            System.out.println("\\nFuzzy search for '" + typo + "' (with typos):");
            List<SearchResult> fuzzyResults = trie.getFuzzySearchSuggestions(typo, 5);
            for (int i = 0; i < fuzzyResults.size(); i++) {
                System.out.println("  " + (i + 1) + ". " + fuzzyResults.get(i));
            }
        }
        
        // Demo 3: Advanced Search with Filters
        System.out.println("\\n\\n=== Demo 3: Advanced Search with Metadata Filter ===");
        Set<String> languageFilter = new HashSet<>(Arrays.asList("language"));
        List<SearchResult> languageResults = trie.advancedSearch("", languageFilter, 1, Long.MAX_VALUE);
        System.out.println("\\nWords tagged as 'language':");
        languageResults.forEach(result -> System.out.println("  - " + result.getWord() + " " + result.getMetadata()));
        
        // Demo 4: Performance Test
        System.out.println("\\n\\n=== Demo 4: Performance Test ===");
        long startTime = System.currentTimeMillis();
        
        for (int i = 0; i < 1000; i++) {
            trie.getAutoCompleteSuggestions("pro");
        }
        
        long endTime = System.currentTimeMillis();
        System.out.println("Performed 1000 auto-complete operations in " + (endTime - startTime) + "ms");
        System.out.println("Average time per operation: " + ((endTime - startTime) / 1000.0) + "ms");
        
        // Demo 5: Export/Import
        System.out.println("\\n\\n=== Demo 5: Export/Import Dictionary ===");
        try {
            trie.exportDictionary("programming_dictionary.txt");
            
            AdvancedTrieAutoComplete newTrie = new AdvancedTrieAutoComplete();
            newTrie.importDictionary("programming_dictionary.txt");
            
            System.out.println("Verification - Suggestions in new Trie for 'pro':");
            newTrie.getAutoCompleteSuggestions("pro").forEach(result -> 
                System.out.println("  - " + result.getWord()));
            
        } catch (IOException e) {
            System.err.println("Error with file operations: " + e.getMessage());
        }
        
        // Display final statistics
        System.out.println("\\n=== Final Performance Statistics ===");
        trie.getStatistics().printStatistics();
        
        System.out.println("\\n=== Demo Completed Successfully! ===");
    }
}