Ruby AVL tree: lambda abuse

gistfile1.rb

def node(l, x, r, h)
  -> f { f.call(l, x, r, h) }
end

def match(tree, nodef, nilf)
  if tree != nil then
    tree.call(-> l, x, r, h { nodef.call(l, x, r, h) })
  else
    nilf.call()
  end
end

def ensureNonNil(tree, f)
  match(tree,
    -> l, x, r, h { f.call(l, x, r, h) },
    -> { raise "Empty tree"} )
end

def height(tree)
  match(tree,
    -> l, x, r, h { h },
    -> { 0 })
end

def make(l, x, r)
  node(l, x, r, 1 + [height(l), height(r)].max)
end

 #         5                            3
 #       /   \    Root                /   \
 #      3     D   Right rotation     2     5
 #    /  \            ----->        / \   / \
 #   2    C                        A   B C   D
 #  / \
 # A   B
def rotRight(tree)
  match(tree,
    -> l, x, r, h {
          match(l,
          -> ll, lx, lr, lh { make(ll, lx, make(lr, x, r)) },
          -> { tree })},
    -> { tree } )
end

 #    3                                 5
 #  /   \         Root                /   \
 # A     5        Left rotation      3     7
 #      / \           ----->        / \   / \
 #     B   7                       A   B C   D
 #        / \
 #       C   D
def rotLeft(tree)
  match(tree,
    -> l, x, r, h {
          match(r,
            -> rl, rx, rr, rh { make(make(l, x, rl), rx, rr) },
            -> { tree }) },
    -> { tree })
end

 #       5                              5                                 4
 #     /   \      Left child          /   \        Root                 /   \
 #   3      D     Left rotation      4     D       Right rotation      3     5
 #  / \                ----->       / \               ----->          / \   / \
 # A   4                           3   C                             A   B C   D
 #    / \                         / \
 #   B   C                       A   B
def doubleRotRight(tree)
  match(tree,
    -> l, x, r, h { rotRight(make(rotLeft(l), x, r)) },
    -> { tree } )
end

 #    3                               3                                 4
 #  /   \        Right child        /   \        Root                 /   \
 # A      5      Right rotation    A     4       Left rotation       3     5
 #       / \         ----->             / \         ----->          / \   / \
 #      4   D                          B   5                       A   B C   D
 #     / \                                / \
 #    B   C                              C   D
def doubleRotLeft(tree)
  match(tree,
    ->  l, x, r, h { rotLeft(make(l, x, rotRight(r))) },
    -> { tree })
end

def balanceFactor(tree)
  match(tree,
    -> l, x, r, h { height(l) - height(r) },
    -> { 0 })
end

def balance(l, x, r)
  node = make(l, x, r)
  if balanceFactor(node) >= 2 then
    #heavy left node
    if balanceFactor(l) >= 1 then
      #heavy left left node
      node = rotRight node
    else
      #heavy left right node
      node = doubleRotRight node
    end
  elsif balanceFactor(node) <= -2 then
    #heavy right node
    if balanceFactor(r) <= -1 then
      #heavy right right node
      node = rotLeft node
    else
      #heavy right left node
      node = doubleRotLeft node
    end
  end
  node
end

def insert(tree, v)
  match(tree,
    -> l, x, r, h {
          if v < x then balance(insert(l, v), x, r)
          elsif v > x then balance(l, x, insert(r, v))
          else tree
          end },
    -> { make(nil, v, nil) })
end

def contains(tree, v)
  match(tree,
    -> l, x, r, h {
          if v < x then contains(l, v)
          elsif v > x then contains(r, v)
          else true
          end },
    -> { false } )
end

def fold(tree, seed, f)
  match(tree,
    -> l, x, r, h { fold(r, f.call(fold(l, seed, f), x), f) },
    -> { seed })
end

def iter(tree, &f)
  match(tree,
    -> l, x, r, h {
        iter(l, &f)
        f.call(x)
        iter(r, &f)},
    -> { })
end

treeRand =
  (0..1000)
  .sort_by { |_| Random.rand }
  .inject(nil) { |tree, x| insert(tree, x) }
puts "height(treeRand): #{height(treeRand)}"
puts "contains(treeRand, 500): #{contains(treeRand, 500)}"
puts "contains(treeRand, -1): #{contains(treeRand, -1)}"
puts "contains(treeRand, 1001): #{contains(treeRand, 1001)}"
puts "Elements: "
iter(treeRand) { |x| print x, " " }