Class RedBlackTree < Object

# File benchmark/gc/redblack.rb, line 69
def initialize
  self.root = NilNode.instance
  self.size = 0
end

# File benchmark/gc/redblack.rb, line 74
def add(key)
  insert(Node.new(key))
end

# File benchmark/gc/redblack.rb, line 216
def black_height(x = root)
  height = 0
  while !x.nil?
    x = x.left
    height +=1 if x.nil? || x.black?
  end
  return height
end

# File benchmark/gc/redblack.rb, line 122
def delete(z)
  y = (z.left.nil? || z.right.nil?) ? z : successor(z)
  x = y.left.nil? ? y.right : y.left
  x.parent = y.parent

  if y.parent.nil?
    self.root = x
  else
    if y == y.parent.left
      y.parent.left = x
    else
      y.parent.right = x
    end
  end

  z.key = y.key if y != z

  if y.color == Node::BLACK
    delete_fixup(x)
  end

  self.size -= 1
  return y
end

# File benchmark/gc/redblack.rb, line 212
def empty?
  return self.root.nil?
end

# File benchmark/gc/redblack.rb, line 185
def inorder_walk(x = root)
  x = self.minimum
  while !x.nil?
    yield x.key
    x = successor(x)
  end
end

# File benchmark/gc/redblack.rb, line 78
def insert(x)
  insert_helper(x)

  x.color = Node::RED
  while x != root && x.parent.color == Node::RED
    if x.parent == x.parent.parent.left
      y = x.parent.parent.right
      if !y.nil? && y.color == Node::RED
        x.parent.color = Node::BLACK
        y.color = Node::BLACK
        x.parent.parent.color = Node::RED
        x = x.parent.parent
      else
        if x == x.parent.right
          x = x.parent
          left_rotate(x)
        end
        x.parent.color = Node::BLACK
        x.parent.parent.color = Node::RED
        right_rotate(x.parent.parent)
      end
    else
      y = x.parent.parent.left
      if !y.nil? && y.color == Node::RED
        x.parent.color = Node::BLACK
        y.color = Node::BLACK
        x.parent.parent.color = Node::RED
        x = x.parent.parent
      else
        if x == x.parent.left
          x = x.parent
          right_rotate(x)
        end
        x.parent.color = Node::BLACK
        x.parent.parent.color = Node::RED
        left_rotate(x.parent.parent)
      end
    end
  end
  root.color = Node::BLACK
end

# File benchmark/gc/redblack.rb, line 154
def maximum(x = root)
  while !x.right.nil?
    x = x.right
  end
  return x
end

# File benchmark/gc/redblack.rb, line 147
def minimum(x = root)
  while !x.left.nil?
    x = x.left
  end
  return x
end

# File benchmark/gc/redblack.rb, line 173
def predecessor(x)
  if !x.left.nil?
    return maximum(x.left)
  end
  y = x.parent
  while !y.nil? && x == y.left
    x = y
    y = y.parent
  end
  return y
end

# File benchmark/gc/redblack.rb, line 195
def reverse_inorder_walk(x = root)
  x = self.maximum
  while !x.nil?
    yield x.key
    x = predecessor(x)
  end
end

# File benchmark/gc/redblack.rb, line 205
def search(key, x = root)
  while !x.nil? && x.key != key
    key < x.key ? x = x.left : x = x.right
  end
  return x
end

# File benchmark/gc/redblack.rb, line 161
def successor(x)
  if !x.right.nil?
    return minimum(x.right)
  end
  y = x.parent
  while !y.nil? && x == y.right
    x = y
    y = y.parent
  end
  return y
end