gistfile1.txt

 # We declare an abstract type, that contains the nodes and the leaves of the tree
  abstract TreePart

  type TreeNode{K,V} <: TreePart
      key::  K
      value:: V
      isRed::Bool
      left:: TreePart
      right:: TreePart
  end
  # Nodes are always red so no method that explicitly assings the color is neccessary
  TreeNode{K,V}(key::K,value::V,left::TreePart,right::TreePart) = TreeNode(key,value,true,left,right)
  TreeNode{K,V}(key::K,value::V) = TreeNode(key, value, true, TreeLeaf(), TreeLeaf())

  type TreeLeaf <: TreePart
      isRed::Bool
      # Leaves are always black
      TreeLeaf()=new(false)
  end

  # To be able to have different instances of LLRB trees, we create a tree type
  # that characterizes a tree by its root
  type LLRBTree
      root:: TreePart

      LLRBTree(node::TreePart) = (tree = new(); tree.root=node; tree.root.isRed=false; tree)
  end
  LLRBTree() = LLRBTree(TreeLeaf())
  LLRBTree(key, value) = (tree=LLRBTree(TreeNode(key,value)))
  
    #         |                                                             |
  #       node                              -> rotateleft ->             son
  #       /   \                                                         /  \
  #           son                                                      node
  #          /   \                                                    /  \
  function rotateleft(node::TreeNode)
      son=node.right

      if isa(son, TreeLeaf)
          error("The right part of the given node must be a node")
      end

      node.right=son.left
      son.left=node
      son.isRed=node.isRed
      node.isRed=true
      return son
  end

  #         |                                                              |
  #        node                              -> rotateright ->            son
  #       /   \                                                          /  \
  #     son                                                               node
  #    /   \                                                              /  \
  function rotateright(node::TreeNode)
      son=node.left

      if isa(son, TreeLeaf)
          error("The left part of the given node must be a node")
      end

      node.left=son.right
      son.right=node
      son.isRed=node.isRed
      node.isRed=true
      return son
  end

  function flipcolor!(node::TreeNode)

      node.isRed = !node.isRed
      node.left.isRed = !node.left.isRed
      node.right.isRed = !node.right.isRed
  end
  
  
    # Adds the specified key/value pair below the specified root node.
  # Shouldn't be exported because the tree root would not be updated
  function add_node{K,V}(node::TreePart, key::K, value::V)

      if isa(node, TreeLeaf)
          # Add the node only when a leaf is found
           #("node added")
          return TreeNode(key, value)
      end

      if node.key < key
          node.right = add_node(node.right, key, value)
      elseif node.key > key
          node.left = add_node(node.left, key, value)
      else
          node.value = value
          #return node      #If we uncomment this, there won't be an unneccesary
                            # rotation in the last subtrees, but the conversion to
                            # 2-3 trees won't be as easy
      end

      if node.right.isRed
           #("Rotate left to prevent red node on right")
          node=rotateleft(node)
      end
      if node.left.isRed && node.left.left.isRed
           #("Rotate right to prevent consecutive red nodes")
          node=rotateright(node)
      end
      if node.left.isRed && node.right.isRed
           #("Split node with two red children")
          flipcolor!(node)
           #(node)
      end

      return node
  end
  # For trees and nodes as parameters, different name so the other one doesn't get used
  push!{K,V}(tree::LLRBTree, key::K, value::V) = (tree.root = add_node(tree.root, key, value); tree.root.isRed=false; tree)
  push!{K,V}(tree::LLRBTree, node::TreeNode{K,V}) = (tree.root = add_node(tree.root, node.key, node.value); tree.root.isRed=false; tree)