Debian Codegraph @

tests/inputs/RedBlackTree.res

raw
1 // a portion of https://github.com/github/linguist/raw/master/samples/ReScript/RedBlackTree.res
2
3 /*
4 Credit to Wikipedia's article on [Red-black
5 tree](http://en.wikipedia.org/wiki/Red–black_tree)
6
7 **Note:** doesn't handle duplicate entries. This is by design.
8
9 ## Overview example:
10
11 ```
12 var rbt = new RedBlackTree([7, 5, 1, 8])
13 rbt.add(2) // => 2
14 rbt.add(10) // => 10
15 rbt.has(5) // => true
16 rbt.remove(8) // => 8
17 ```
18
19 ## Properties:
20
21 - size: The total number of items.
22 */
23
24 type nodeColor =
25 | Red
26 | Black
27
28 /*
29 Property of a red-black tree, taken from Wikipedia:
30 1. A node is either red or black.
31 2. Root is black.
32 3. Leaves are all null and considered black.
33 4. Both children of a red node are black.
34 5. Every path from a node to any of its descendent leaves contains the same
35 number of black nodes.
36 */
37
38 type rec node<'value> = {
39 mutable left: option<node<'value>>,
40 mutable right: option<node<'value>>,
41 mutable parent: option<node<'value>>,
42 mutable sum: float,
43 mutable color : nodeColor,
44 mutable height: float,
45 mutable value: 'value,
46 }
47
48 type t<'value> = {
49 mutable size: int,
50 mutable root: option<node<'value>>,
51 compare: (. 'value, 'value) => int,
52 }
53
54 let createNode = (~color, ~value, ~height) =>
55 {left:None, right:None, parent:None, sum:0., height, value, color}
56
57 external castNotOption: option<'a> => 'a = "%identity"
58
59 let updateSum = (node) => {
60 let leftSum = switch node.left {
61 | None => 0.
62 | Some(left) => left.sum
63 }
64 let rightSum = switch node.right {
65 | None => 0.
66 | Some(right) => right.sum
67 }
68 node.sum = leftSum +. rightSum +. node.height
69 }
70
71 /* Update the sum for the node and parents recursively. */
72 let rec updateSumRecursive = (rbt, node) => {
73 updateSum(node)
74 switch node.parent {
75 | None => ()
76 | Some(parent) =>
77 rbt->updateSumRecursive(parent)
78 }
79 }
80
81 let grandParentOf = node => {
82 switch node.parent {
83 | None => None
84 | Some(ref_) => ref_.parent
85 }
86 }
87
88 let isLeft = node => {
89 switch node.parent {
90 | None => false
91 | Some(parent) => Some(node) === parent.left
92 }
93 }
94
95 let leftOrRightSet = (~node, x, value) => {
96 isLeft(node) ? x.left=value : x.right=value
97 }
98
99 let siblingOf = node => {
100 if isLeft(node) {
101 castNotOption(node.parent).right
102 } else {
103 castNotOption(node.parent).left
104 }
105 }
106
107 let uncleOf = node => {
108 switch grandParentOf(node) {
109 | None => None
110 | Some(grandParentOfNode) =>
111 if isLeft(castNotOption(node.parent)) {
112 grandParentOfNode.right
113 } else {
114 grandParentOfNode.left
115 }
116 }
117 }
118
119 let rec findNode = (rbt, node, value) => {
120 switch node {
121 | None => None
122 | Some(node) =>
123 let cmp = rbt.compare(. value, node.value)
124 if cmp === 0 {
125 Some(node)
126 } else if cmp < 0 {
127 findNode(rbt, node.left, value)
128 } else {
129 findNode(rbt, node.right, value)
130 }
131 }
132 }
133
134 let has = (rbt, value) => findNode(rbt, rbt.root, value) !== None
135
136 let rec peekMinNode = node => switch node {
137 | None => None
138 | Some(node) =>
139 node.left === None ? Some(node) : node.left->peekMinNode
140 }
141
142 let rec peekMaxNode = node => switch node {
143 | None => None
144 | Some(node) =>
145 node.right === None ? Some(node) : node.right->peekMaxNode
146 }
147
148 let rotateLeft = (rbt, node) => {
149 let parent = node.parent
150 let right = node.right
151 switch parent {
152 | Some(parent) =>
153 parent->leftOrRightSet(~node, right)
154 | None =>
155 rbt.root = right
156 }
157 node.parent = right
158 let right = right->castNotOption // precondition
159 let rightLeft = right.left
160 node.right = rightLeft
161 switch rightLeft {
162 | Some(rightLeft) =>
163 rightLeft.parent = Some(node)
164 | None =>
165 ()
166 }
167 right.parent = parent
168 right.left = Some(node)
169 updateSum(node)
170 updateSum(right)
171 }
172
173 // After adding the node, we need to operate on it to preserve the tree's
174 // properties by filtering it through a series of cases. It'd be easier if
175 // there's tail recursion in JavaScript, as some cases fix the node but
176 // restart the cases on the node's ancestor. We'll have to use loops for now.
177
178 let rec _addLoop = (rbt, currentNode) => {
179 // Case 1: node is root. Violates 1. Paint it black.
180 if Some(currentNode) === rbt.root {
181 currentNode.color = Black
182 }
183
184 // Case 2: parent black. No properties violated. After that, parent is sure
185 // to be red.
186 else if (currentNode.parent->castNotOption).color === Black {
187 ()
188 }
189
190 // Case 3: if node's parent and uncle are red, they are painted black.
191 // Their parent (node's grandparent) should be painted red, and the
192 // grandparent red. Note that node certainly has a grandparent, since at
193 // this point, its parent's red, which can't be the root.
194
195 // After the painting, the grandparent might violate 2 or 4.
196 else if({
197 let uncle = uncleOf(currentNode)
198 uncle !== None && (uncle->castNotOption).color === Red
199 }) {
200 (currentNode.parent->castNotOption).color = Black
201 (uncleOf(currentNode)->castNotOption).color = Black
202 (grandParentOf(currentNode)->castNotOption).color = Red
203 _addLoop(rbt, grandParentOf(currentNode)->castNotOption)
204 }
205 else {
206 // At this point, uncle is either black or doesn't exist.
207
208 // Case 4: parent red, uncle black, node is right child, parent is left
209 // child. Do a left rotation. Then, former parent passes through case 5.
210 let currentNode =
211 if !isLeft(currentNode) && isLeft(currentNode.parent->castNotOption) {
212 rotateLeft(rbt, currentNode.parent->castNotOption)
213 currentNode.left->castNotOption
214 } else if isLeft(currentNode) && !isLeft(currentNode.parent->castNotOption) {
215 rotateRight(rbt, currentNode.parent->castNotOption)
216 currentNode.right->castNotOption
217 } else {
218 currentNode
219 }
220
221 // Case 5: parent red, uncle black, node is left child, parent is left
222 // child. Right rotation. Switch parent and grandparent's color.
223 (currentNode.parent->castNotOption).color = Black
224 (grandParentOf(currentNode)->castNotOption).color = Red
225 if isLeft(currentNode) {
226 rotateRight(rbt, grandParentOf(currentNode)->castNotOption)
227 } else {
228 rotateLeft(rbt, grandParentOf(currentNode)->castNotOption)
229 }
230 }
231 }