package main

import (
    "fmt"
    "sort"
    "strings"
)

func main() {
    t := New()
    type kv struct {
        k string
        v string
    }
    kvs := []kv{
        {"/content/a.md", "aaa"},
        {"/content/a.md", "ddd"},
        {"/content/b.md", "bbb"},
        {"/content/c.md", "ccc"},
        {"/", "root"},
    }
    for _, kv := range kvs {
        t.Insert(kv.k, kv.v)
    }
    t.Print()

    v, _ := t.Get("/")
    fmt.Println("=--=")
    fmt.Println(v)
}

type edge struct {
    name  string
    start *node
    end   *node
}

type edges []*edge

type node struct {
    val      any
    prefix   *edge
    suffixes edges
}

type Tree struct {
    root *node
}

func New() *Tree {
    return &Tree{root: &node{
        val:      "TreeRoot",
        prefix:   nil,
        suffixes: edges{},
    }}
}

func (t *Tree) Get(k string) (interface{}, bool) {
    n := t.root
    path := k
    for {
        if len(path) == 0 {
            return n.val, true
            break
        }

        e := n.getEdge(path)
        if e == nil {
            break
        } else if e.name == "" {
            break
        }

        if strings.HasPrefix(path, e.name) {
            path = path[len(e.name):]
            n = e.end
        } else {
            break
        }
    }
    return nil, false
}

func (t *Tree) Insert(k string, v interface{}) bool {
    var parent *node
    n := t.root
    path := k

    if len(path) == 0 {
        panic("empty key not supported yet.")
    }

    for {
        if len(path) == 0 {
            n.val = v
            return true
        }

        parent = n
        e := n.getEdge(path)

        if e == nil {
            e := newNodeEdge()
            e.name = path
            e.start = parent
            e.end.val = v

            parent.addEdge(e)
            return true
        }

        commonPrefix := longestPrefix(path, e.name)

        if commonPrefix == len(e.name) {
            path = path[commonPrefix:]
            n = e.end
            continue
        }

        commonEdge := newNodeEdge()
        commonEdge.name = path[:commonPrefix]
        commonEdge.start = e.start

        e.start.addEdge(commonEdge)
        e.start.delEdge(e)
        commonEdge.end.addEdge(e)

        e.name = e.name[commonPrefix:]

        freshEdgeName := path[commonPrefix:]
        if len(freshEdgeName) == 0 {
            commonEdge.end.val = v
        } else {
            freshEdge := newNodeEdge()
            freshEdge.name = freshEdgeName
            freshEdge.start = commonEdge.end
            freshEdge.end.val = v

            commonEdge.end.addEdge(freshEdge)
        }
        return true
    }

    return false
}

func newNodeEdge() *edge {
    e := &edge{
        name:  "",
        start: nil,
        end: &node{
            val:      nil,
            prefix:   nil,
            suffixes: edges{},
        },
    }
    e.end.prefix = e
    return e
}

func (n *node) getEdge(path string) *edge {
    return findEdgeWithSamePrefix(
        getFirstByte(path), n.suffixes)
}

func (n *node) addEdge(e *edge) {
    e.start = n
    n.suffixes = append(n.suffixes, e)
    sortAscending(n.suffixes)
}

func (n *node) delEdge(e *edge) {
    if e.start == n {
        var pos int
        for i, item := range n.suffixes {
            if item == e {
                pos = i
                break
            }
        }
        n.suffixes = append(n.suffixes[:pos],
            n.suffixes[pos+1:]...)
    }
}

func sortAscending(es edges) {
    sort.Slice(es, func(i, j int) bool {
        return getFirstByte(
            es[i].name) < getFirstByte(es[j].name)
    })
}

func getFirstByte(v string) byte {
    return v[0]
}

func findEdgeWithSamePrefix(
    firstByte byte, es edges) *edge {
    for _, e := range es {
        if getFirstByte(e.name) == firstByte {
            return e
        }
    }
    return nil
}

func longestPrefix(k1, k2 string) int {
    max := len(k1)
    if l := len(k2); l < max {
        max = l
    }
    var i int
    for i = 0; i < max; i++ {
        if k1[i] != k2[i] {
            break
        }
    }
    return i
}

func (t *Tree) Print() {
    recursivePrint(t.root)
}

func recursivePrint(n *node) {
    printNode(n)
    for _, e := range n.suffixes {
        recursivePrint(e.end)
    }
}

node: prefix , value TreeRoot
node: prefix /, value root
node: prefix /content/, value %!s(<nil>)
node: prefix a.md, value aaa
node: prefix b.md, value bbb
node: prefix c.md, value ccc
=--=
root