Algebraic data types: Difference between revisions
no edit summary
(→Emacs Lisp: Use rbt- namespace) |
No edit summary |
||
Line 995:
check''
</lang>
=={{header|Julia}}==
Julia's multiple dispatch model is based on the types of a function's arguments, but does not look deeper into the function's array arguments for the types of their contents. Therefore we do multi-dispatch on the balance function but then use an if statement within the multiply dispatched functions to further match based on argument vector contents.
<lang julia>import Base.length
abstract type AbstractColoredNode end
struct RedNode <: AbstractColoredNode end; const R = RedNode()
struct BlackNode <: AbstractColoredNode end; const B = BlackNode()
struct Empty end; const E = Empty()
length(e::Empty) = 1
function balance(b::BlackNode, v::Vector, z, d)
if v[1] == R
if length(v[2]) == 4 && v[2][1] == R
return [R, [B, v[2][2], v[2][3], v[2][4]], v[3], [B, v[4], z, d]]
elseif length(v[4]) == 4 && v[4][1] == R
return [R, [B, v[2], v[3], v[4][2]], v[4][3], [B, v[4][4], z, d]]
end
end
[b, v, z, d]
end
function balance(b::BlackNode, a, x, v::Vector)
if v[1] == R
if length(v[2]) == 4 && v[2][1] == R
return [R, [B, a, x, v[2][2]], v[2][3], [B, v[3], v[4]]]
elseif length(v[4]) == 4 && v[4][1] == R
return [R, [B, a, x, v[2]], v[3], [B, v[4][2], v[4][3], v[4][4]]]
end
end
[b, a, x, v]
end
function balance(b::BlackNode, a::Vector, x, v::Vector)
if v[1] == R
if length(v[2]) == 4 && v[2][1] == R
return [R, [B, a, x, v[2][2]], v[2][3], [B, v[3], v[4]]]
elseif length(v[4]) == 4 && v[4][1] == R
return [R, [B, a, x, v[2]], v[3], [B, v[4][2], v[4][3], v[4][4]]]
end
end
[b, a, x, v]
end
balance(node, l, a, r) = [node, l, a, r]
function ins(v::Vector, x::Number)
if length(v) == 4
if x < v[3]
return balance(v[1], ins(v[2], x), v[3], v[4])
elseif x > v[3]
return balance(v[1], v[2], v[3], ins(v[4], x))
end
end
v
end
ins(t, a) = [R, E, a, E]
insert(v, a) = (t = ins(v, a); t[1] = B; t)
function printRBtree(t)
s = string(t)
s = replace(s, r"lackNode\(\)|edNode\(\)|Any|mpty\(\)" => "")
println(s)
end
function testRB()
t = E
for i in rand(collect(1:20), 10)
t = insert(t, i)
end
printRBtree(t)
end
testRB()
</lang>{{out}}
<pre>
[B, [R, [B, E, 2, E], 3, [B, E, 5, E]], 8, [R, [B, [R, E, 9, [R, E, 11, E]], 13, E], 14, [B, 20, E]]]
</pre>
=={{header|Kotlin}}==
| |||