trie.go

package main

import (
	"bufio"
	"fmt"
	"os"
	"unicode"
)

type node struct {
	children map[rune]*node
	final    bool
}

func newNode() *node {
	n := new(node)
	n.children = make(map[rune]*node)
	return n
}

type trie struct {
	root *node
}

func newTrie() *trie {
	t := new(trie)
	t.root = newNode()
	return t
}

func (t *trie) add(word string) {
	curr := t.root
	for _, c := range word {
		if !unicode.IsLetter(c) {
			continue
		}
		if curr.children[c] == nil {
			curr.children[c] = newNode()
		}
		curr = curr.children[c]
	}
	curr.final = true
}

func (t *trie) search(word string) bool {
	curr := t.root
	for _, c := range word {
		if !unicode.IsLetter(c) {
			continue
		}
		if curr.children[c] == nil {
			return false
		}
		curr = curr.children[c]
	}
	return curr.final
}

func main() {
	t := newTrie()

	fmt.Print("indexing dictionary...")
	dict, err := os.Open("/usr/share/dict/words")
	if err != nil {
		panic(err)
	}

	reader := bufio.NewReader(dict)
	for {
		line, _, _ := reader.ReadLine()
		if line == nil {
			break
		}
		t.add(string(line))
	}

	dict.Close()
	fmt.Println("done")

	var tmp string

repl:
	for {
		fmt.Print("> ")
		fmt.Scan(&tmp)

		switch tmp {
		case "add":
			fmt.Scan(&tmp)
			t.add(tmp)
			fmt.Printf("added %q\n", tmp)

		case "search":
			fmt.Scan(&tmp)
			fmt.Println(t.search(tmp))

		case "exit":
			break repl

		default:
			fmt.Fprintln(os.Stdout, "unrecognized command", tmp)
		}
	}
}