-
Notifications
You must be signed in to change notification settings - Fork 22
/
insert.go
80 lines (72 loc) · 1.68 KB
/
insert.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
package fast
import (
. "github.com/kocircuit/kocircuit/lang/go/eval/symbol"
)
func Insert(node *Node, value Symbol, less *VarietySymbol) *Node {
if node == nil {
return &Node{Value: value, Color: Red}
} else {
return insertInto(node, value, less)
}
}
func insertInto(node *Node, value Symbol, less *VarietySymbol) *Node {
if IsRedRed(node) {
node = Flip(node)
}
node = placeValue(node, value, less)
if IsBlackRed(node) {
node = RotateLeft(node)
}
if IsLeftRedRed(node) {
node = RotateRight(node)
}
return node
}
func IsRedRed(node *Node) bool {
return node.Left != nil && node.Left.Color == Red &&
node.Right != nil && node.Right.Color == Red
}
func IsBlackRed(node *Node) bool {
return node.Left != nil && node.Left.Color == Black &&
node.Right != nil && node.Right.Color == Red
}
func IsLeftRedRed(node *Node) bool {
return node.Left != nil && node.Left.Left != nil &&
node.Left.Color == Red && node.Left.Left.Color == Red
}
func placeValue(node *Node, value Symbol, less *VarietySymbol) *Node {
smaller := evokeLess(value, node.Value, less)
bigger := evokeLess(node.Value, value, less)
switch {
case smaller:
return &Node{
Value: node.Value,
Color: node.Color,
Left: Insert(node.Left, value, less),
Right: node.Right,
}
case bigger:
return &Node{
Value: node.Value,
Color: node.Color,
Left: node.Left,
Right: Insert(node.Right, value, less),
}
default:
return &Node{
Value: value,
Color: node.Color,
Left: node.Left,
Right: node.Right,
}
}
}
func evokeLess(u, v Symbol, less *VarietySymbol) bool {
return AsBool(
Evoke(
less,
EvokeArg{Name: "left", Value: u},
EvokeArg{Name: "right", Value: v},
),
)
}