Auto-Completer

A C++ command-line auto-completion tool using trie data structures and the GNU Readline library.

Overview

This project implements an interactive command-line interface with intelligent auto-completion capabilities. It uses a trie (prefix tree) data structure to efficiently store and retrieve completions, providing fast prefix-based suggestions similar to shell completion.

Features

• Trie-based Auto-completion: Fast prefix matching using an optimized trie data structure
• System Command Loading: Automatically loads all available system commands from PATH
• Custom Word Lists: Support for loading custom completion dictionaries from files
• Interactive Interface: Real-time completion using GNU Readline
• Tree Visualization: Generate Graphviz DOT format output to visualize the trie structure
• Memory Safe: Proper memory management with RAII and smart destruction

Architecture

Core Components

• Node Class: Represents individual trie nodes with character data and child pointers
• Completer Class: Main trie implementation with insertion, search, and completion methods
• Utility Functions: File loading, command discovery, and tree visualization

Key Files

• completer.hpp - Header definitions for Node and Completer classes
• completer.cpp - Core trie implementation and readline integration
• utils.cpp - Utility functions for loading data and tree visualization
• Makefile - Build configuration

Building

Prerequisites

• C++14 compatible compiler (g++/clang++)
• GNU Readline library development headers
• Make

Compilation

make

This creates an executable named completer with the following compilation flags:

• -Wall -Wextra for comprehensive warnings
• -std=c++14 for C++14 standard
• -fsanitize=address for memory debugging
• -lreadline for readline library linking

Cleaning

make clean

Usage

Basic Usage

Run without arguments to load system commands:

./completer

Custom Word Lists

Load completions from custom files:

./completer wordlist1.txt wordlist2.txt

Interactive Commands

Once running, the tool provides an interactive prompt:

• Tab completion: Press Tab to see available completions
• Type tree: Generate DOT format visualization of the trie structure
• Ctrl+C or Ctrl+D: Exit the program

Example Session

complete : git<TAB>
git       gitk      git-upload-pack
complete : git
prefix -> git

complete : tree
digraph {
    Node0[label="~"]
    Node1[label="g"]
    Node0 -> Node1[weight=9]
    ...
}

Implementation Details

Trie Structure

The trie is implemented with:

• Root node containing sentinel value (-1)
• Character-based branching for efficient prefix matching
• Null terminator ('\0') marking word boundaries
• Dynamic memory allocation with proper cleanup

Completion Algorithm

1. Prefix Search: Traverse trie following input characters
2. Subtree Collection: Gather all complete words from matching subtree
3. Result Formatting: Convert to readline-compatible string array

System Integration

• PATH Scanning: Automatically discovers executable commands
• File Loading: Reads custom dictionaries line by line
• Readline Integration: Seamless tab completion interface

File Format

Custom word list files should contain one word per line:

word1
word2
word3

Memory Management

The implementation uses RAII principles:

• Automatic cleanup via destructors
• Exception-safe resource management
• Address sanitizer integration for debugging

Visualization

The tree command generates Graphviz DOT format output for visualizing the trie structure. Save the output to a .dot file and render with:

./completer > output.dot
# Type 'tree' when prompted
dot -Tpng output.dot -o trie.png

Contributing

When modifying the code:

1. Maintain C++14 compatibility
2. Follow existing code style and naming conventions
3. Ensure proper memory management
4. Test with address sanitizer enabled

License

This project is provided as-is for educational and development purposes.