This is a solid implementation of a Trie. It’s thread-safe, supports metadata storage via interface{}, and includes memory optimization during deletion—all of which make it production-ready for autocomplete services.

Below is a complete, professional README.md tailored for your repository.

---

GoTrie

GoTrie is a high-performance, thread-safe Trie data structure implemented in Go, specifically designed for autocomplete and prefix-search functionality. It supports weighted results (counts), custom metadata storage, and dynamic filtering.

🚀 Features

• Thread-Safe: Safe for concurrent use with sync.RWMutex.
• Weighted Autocomplete: Search results are automatically sorted by frequency (count) and alphabetically.
• Custom Data: Store any data type alongside your keys using interface{}.
• Memory Efficient: Includes a cleanupPath mechanism to remove redundant nodes upon deletion.
• Filtering: Advanced search supports custom filter functions.
• Zero Dependencies: Built entirely with the Go standard library.

📦 Installation

To install the package, run:

go get github.com/masoudkaviani/gotrie

🛠️ Usage

Quick Start

package main

import (
	"fmt"
	"github.com/masoudkaviani/gotrie"
)

func main() {
	// Initialize a new Trie
	tr := gotrie.New()

	// Insert words with weights (counts)
	tr.Insert("apple", 10)
	tr.Insert("application", 15)
	tr.Insert("app", 5)
	tr.Insert("banana", 20)

	// Search for suggestions with a prefix "app"
	// Limits results to top 5
	suggestions := tr.Search("app", 5)

	for _, s := range suggestions {
		fmt.Printf("Tag: %s, Count: %d\n", s.Tag, s.Count)
	}
}

Storing Custom Data

You can attach metadata (like database IDs or structs) to any word:

type User struct {
    ID int
}

tr.InsertWithData("golang", 100, User{ID: 1})

count, data, exists := tr.Get("golang")
if exists {
    user := data.(User)
    fmt.Printf("Found %s with ID %d\n", "golang", user.ID)
}

Advanced Filtering

Filter results dynamically during the search process:

// Only return suggestions with a count higher than 10
suggestions := tr.SearchWithFilter("app", 0, func(s *gotrie.TagSuggestion) bool {
    return s.Count > 10
})

📖 API Reference

Initialization

• New(): Creates a new empty Trie.
• NewWithCapacity(cap): Creates a Trie with pre-allocated capacity for root children.

Modification

• Insert(word, count): Adds or updates a word.
• InsertWithData(word, count, data): Adds or updates a word with custom metadata.
• Update(word, count): Updates an existing word (aliases Insert).
• Delete(word): Removes a word and cleans up unused nodes.
• Clear(): Wipes all data from the Trie.

Retrieval & Search

• Search(prefix, limit): Returns suggestions sorted by count (desc) then alpha.
• SearchWithFilter(prefix, limit, filter): Search with a custom boolean filter.
• Get(word): Returns count, data, and existence for a specific word.
• Exists(word): Returns true if the word is in the Trie.
• PrefixExists(prefix): Returns true if any word starts with the prefix.
• Size(): Returns the total number of words.

---

🧪 Running Tests

To run the test suite, navigate to the project directory and run:

go test -v ./...

The tests cover concurrent access, deletion logic, and result ordering.

📄 License

This project is licensed under the MIT License.