-
Notifications
You must be signed in to change notification settings - Fork 0
/
stringify.go
142 lines (116 loc) · 3.4 KB
/
stringify.go
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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
package cidrtree
import (
"fmt"
"io"
"strings"
)
// String returns a hierarchical tree diagram of the ordered CIDRs as string, just a wrapper for [Tree.Fprint].
func (t Table[V]) String() string {
w := new(strings.Builder)
_ = t.Fprint(w)
return w.String()
}
// Fprint writes an ordered CIDR tree diagram to w. If w is nil, Fprint panics.
//
// The order from top to bottom is in ascending order of the start address
// and the subtree structure is determined by the CIDRs coverage.
func (t Table[V]) Fprint(w io.Writer) error {
if err := t.root4.fprint(w); err != nil {
return err
}
if err := t.root6.fprint(w); err != nil {
return err
}
return nil
}
func (n *node[V]) fprint(w io.Writer) error {
if n == nil {
return nil
}
// pcm = parent-child-mapping
var pcm parentChildsMap[V]
// init map
pcm.pcMap = make(map[*node[V]][]*node[V])
pcm = n.buildParentChildsMap(pcm)
if len(pcm.pcMap) == 0 {
return nil
}
// start symbol
if _, err := fmt.Fprint(w, "▼\n"); err != nil {
return err
}
// start recursion with root and empty padding
var root *node[V]
return root.walkAndStringify(w, pcm, "")
}
func (n *node[V]) walkAndStringify(w io.Writer, pcm parentChildsMap[V], pad string) error {
// the prefix (pad + glyphe) is already printed on the line on upper level
if n != nil {
if _, err := fmt.Fprintf(w, "%v (%v)\n", n.cidr, n.value); err != nil {
return err
}
}
glyphe := "├─ "
spacer := "│ "
// dereference child-slice for clearer code
childs := pcm.pcMap[n]
// for all childs do, but ...
for i, child := range childs {
// ... treat last child special
if i == len(childs)-1 {
glyphe = "└─ "
spacer = " "
}
// print prefix for next cidr
if _, err := fmt.Fprint(w, pad+glyphe); err != nil {
return err
}
// recdescent down
if err := child.walkAndStringify(w, pcm, pad+spacer); err != nil {
return err
}
}
return nil
}
// parentChildsMap, needed for hierarchical tree printing, this is not BST printing!
//
// CIDR tree, parent->childs relation printed. A parent CIDR covers a child CIDR.
type parentChildsMap[T any] struct {
pcMap map[*node[T]][]*node[T] // parent -> []child map
stack []*node[T] // just needed for the algo
}
// buildParentChildsMap, in-order traversal
func (n *node[V]) buildParentChildsMap(pcm parentChildsMap[V]) parentChildsMap[V] {
if n == nil {
return pcm
}
// in-order traversal, left tree
pcm = n.left.buildParentChildsMap(pcm)
// detect parent-child-mapping for this node
pcm = n.pcmForNode(pcm)
// in-order traversal, right tree
return n.right.buildParentChildsMap(pcm)
}
// pcmForNode, find parent in stack, remove cidrs from stack, put this cidr on stack.
func (n *node[V]) pcmForNode(pcm parentChildsMap[V]) parentChildsMap[V] {
// if this cidr is covered by a prev cidr on stack
for j := len(pcm.stack) - 1; j >= 0; j-- {
that := pcm.stack[j]
if that.cidr.Contains(n.cidr.Addr()) {
// cidr in node j is parent to cidr
pcm.pcMap[that] = append(pcm.pcMap[that], n)
break
}
// Remember: sort order of CIDRs is lower-left, superset to the left:
// if this cidr wasn't covered by j, remove node at j from stack
pcm.stack = pcm.stack[:j]
}
// stack is emptied, no cidr on stack covers current cidr
if len(pcm.stack) == 0 {
// parent is root
pcm.pcMap[nil] = append(pcm.pcMap[nil], n)
}
// put current node on stack for next node
pcm.stack = append(pcm.stack, n)
return pcm
}