-
Notifications
You must be signed in to change notification settings - Fork 10
/
RedBlackTree.elm
157 lines (128 loc) · 3.75 KB
/
RedBlackTree.elm
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
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
module Main exposing (..)
import Svg exposing (Svg, svg, circle, line, polygon, rect, g, text_, text)
import Svg.Attributes exposing (..)
import TreeDiagram exposing (node, Tree, defaultTreeLayout)
import TreeDiagram.Svg exposing (draw)
type Color
= Red
| Black
-- Tree to draw
redBlackTree =
node
(Just ( 13, Black ))
[ node
(Just ( 8, Red ))
[ node
(Just ( 1, Black ))
[ node Nothing []
, node
(Just ( 6, Red ))
[ node Nothing []
, node Nothing []
]
]
, node
(Just ( 11, Black ))
[ node Nothing []
, node Nothing []
]
]
, node
(Just ( 17, Red ))
[ node
(Just ( 15, Black ))
[ node Nothing []
, node Nothing []
]
, node
(Just ( 25, Black ))
[ node
(Just ( 22, Red ))
[ node Nothing []
, node Nothing []
]
, node
(Just ( 27, Red ))
[ node Nothing []
, node Nothing []
]
]
]
]
(=>) prop value =
prop (toString value)
{-| Represent edges as arrows from parent to child
-}
drawEdge : ( Float, Float ) -> Svg msg
drawEdge ( x, y ) =
let
arrowOffset =
42
theta =
atan (y / x)
rot_ =
if x > 0 then
theta
else
pi + theta
rot =
(rot_ / (2 * pi)) * 360
dist =
sqrt (x ^ 2 + y ^ 2)
scale =
(dist - arrowOffset) / dist
( xTo, yTo ) =
( scale * x, scale * y )
in
g
[]
[ line
[ x1 => 0, y1 => 0, x2 => xTo, y2 => yTo, stroke "black", strokeWidth "2" ]
[]
, g
[ transform <|
"translate("
++ (toString xTo)
++ " "
++ (toString yTo)
++ ") "
++ "rotate("
++ (toString rot)
++ ")"
]
[ arrow ]
]
{-| Represent nodes as colored circles with the node value inside.
-}
drawNode : Maybe ( Int, Color ) -> Svg msg
drawNode n =
case n of
Just ( n, c ) ->
let
color =
case c of
Red ->
"#CC0000"
Black ->
"black"
in
g
[]
[ circle [ r "27", stroke "black", strokeWidth "2", fill color, cx "0", cy "0" ] []
, text_ [ textAnchor "middle", fill "white", fontSize "30", fontFamily "\"Times New Roman\",serif", transform "translate(0,11)" ] [ text <| toString n ]
]
Nothing ->
g
[]
[ rect [ width "50", height "35", stroke "black", transform "translate(-25,-22)" ] []
, text_ [ textAnchor "middle", fill "white", fontSize "20", transform "translate(0,4)", fontFamily "sans-serif" ] [ text "Nil" ]
]
-- Arrow to go on the ends of edges
arrow =
polygon [ points "-10,10 10,0, -10,-10 -5,0" ] []
main =
draw
{ defaultTreeLayout | padding = 60, siblingDistance = 80 }
drawNode
drawEdge
redBlackTree