matching_word_tree.go

package main

import (
	"fmt"
	"strings"
)

func main() {
	input := []string{"ass", "fuck", "car", "cat", "cucumber"}

	fmt.Printf("input : %v\n\n", input)

	m := NewMatcher(input)

	Test(m, "car", true)
	Test(m, "cat", true)
	Test(m, "can", false)
	Test(m, "c**", true)
	Test(m, "c**a", false)
	Test(m, "ass", true)
	Test(m, "kek", false)
}

type Matcher struct {
	input          []string
	syntaxTreeHead *LetterNode
}

func NewMatcher(input []string) *Matcher {
	head := LetterNode{
		Head:          true,
		ChildrenNodes: make([]*LetterNode, 0, len(input)),
	}

	for _, word := range input {
		currentNode := &head

		// fmt.Printf("\n\nNow on word %s\n\n", word)

	OUTER:
		for _, letter := range strings.Split(word, "") {
			// fmt.Printf("\nNow on letter %s\n -- current node %s\n\n", letter, currentNode)

			for _, n := range currentNode.ChildrenNodes {
				if n.Letter == letter {
					// currentNode.ChildrenNodes = append(currentNode.ChildrenNodes, n)
					currentNode = n

					continue OUTER
				}
			}

			node := LetterNode{Letter: letter}

			currentNode.ChildrenNodes = append(currentNode.ChildrenNodes, &node)
			currentNode = &node
		}
	}

	return &Matcher{input, &head}
}

func (m *Matcher) IsIncluded(key string) bool {
	return m.syntaxTreeHead.FindWord(key)
}

type LetterNode struct {
	Head          bool
	Letter        string
	ChildrenNodes []*LetterNode
}

func (m *LetterNode) FindWord(word string) bool {
	splittedWord := strings.Split(word, "")

	return m.findWord(splittedWord)
}

func (m *LetterNode) findWord(word []string) bool {
	// fmt.Printf("\n\nfindWord with %s len %d cap %d in current node %s\n\n", word, len(word), cap(word), m)

	if m.Head {
		for i := range m.ChildrenNodes {
			if m.ChildrenNodes[i].findWord(word) {
				return true
			}
		}
	}

	currentLetter := word[0]

	if m.Letter != currentLetter && currentLetter != "*" {
		return false
	}

	// if its the last letter of the word
	if len(word) == 1 && len(m.ChildrenNodes) == 0 {
		return true
	}

	for i := range m.ChildrenNodes {
		restOfTheWord := word[1:]

		if m.ChildrenNodes[i].findWord(restOfTheWord) {
			return true
		}
	}

	return false
}

func (m *LetterNode) String() string {
	children := make([]string, 0, len(m.ChildrenNodes))

	for i := range m.ChildrenNodes {
		children = append(children, m.ChildrenNodes[i].Letter)
	}

	return fmt.Sprintf("< Head?: %t, Letter: %s, Children Letters: [%s] >", m.Head, m.Letter, strings.Join(children, ", "))
}

func Test(m *Matcher, key string, expected bool) {
	result := m.IsIncluded(key)
	var testStatus string

	if result == expected {
		testStatus = "PASSED"
	} else {
		testStatus = "FAILED"
	}

	fmt.Printf("Called with: \"%s\" / expected: %t / result: %t --> %s\n\n", key, expected, result, testStatus)
}