~pierrec/giox

ref: c164e218831e giox/cmd/iconx/tree.go -rw-r--r-- 1.6 KiB
c164e218Pierre Curto cm/iconx: update the set of icons 6 months ago
                                                                                
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
package main

import (
	"hash/maphash"
	"strings"
)

const TagSep = '/'

type treeNode struct {
	key  string
	next []int
}

type tree struct {
	mhash maphash.Hash
	root  []int
	data  map[int]treeNode
}

func (t *tree) hash(k string) int {
	t.mhash.Reset()
	_, _ = t.mhash.WriteString(k)
	return int(t.mhash.Sum64())
}

func (t *tree) init() {
	if t.data == nil {
		t.data = make(map[int]treeNode)
	}
}

func (t *tree) addRoot(key string) (added bool) {
	t.init()
	k := t.hash(key)
	_, ok := t.data[k]
	if !ok {
		added = true
		t.data[k] = treeNode{key: key}
	}
	t.root = addUniqInt(t.root, k)
	return
}

func (t *tree) addChild(key, next string) {
	t.init()
	k := t.hash(key)
	n, ok := t.data[k]
	if !ok {
		n.key = key
	}
	h := t.hash(next)
	n.next = addUniqInt(n.next, h)
	if _, ok := t.data[h]; !ok {
		t.data[h] = treeNode{key: next}
	}
	t.data[k] = n
}

func (t *tree) Add(key string) bool {
	key = cleanKey(key)
	for {
		i := strings.LastIndexByte(key, TagSep)
		if i < 0 {
			return t.addRoot(key)
		}
		t.addChild(key[:i], key)
		key = key[:i]
	}
}

func (t *tree) Has(key string) bool {
	key = cleanKey(key)
	k := t.hash(key)
	_, ok := t.data[k]
	return ok
}

func (t *tree) Root() []int {
	return t.root
}

func (t *tree) Children(i int) []int {
	return t.data[i].next
}

func (t *tree) Key(i int) string {
	return t.data[i].key
}

// addUniqInt adds i to s if not already in s.
func addUniqInt(s []int, i int) []int {
	for _, j := range s {
		if j == i {
			return s
		}
	}
	return append(s, i)
}

func cleanKey(key string) string {
	if strings.HasPrefix(key, string(TagSep)) {
		return key[1:]
	}
	return key
}