<commit_before>###*
@author <NAME> (2011, <EMAIL>)
###
mugs.LLRBNode = (() ->

  ###
    Immutable implementation of Left Leaning Red Black Tree as
    described in this paper: http://www.cs.princeton.edu/~rs/talks/LLRB/LLRB.pdf
  
    Invartiant 1: No red node has a red child
    Invartiant 2: Every leaf path has the same number of black nodes
    Invartiant 3: Only the left child can be red (left leaning)
  ###

  ###
    Public interface
  ###

  F = (key,value,color,left,right) ->
    this.key   = key
    this.value = value
    this.color = if color? then color else RED
    this.left  = if left?  then left  else new mugs.None()
    this.right = if right? then right else new mugs.None()
    this.comparator = standard_comparator
    return this

  F.prototype.copy = (key,value,color,left,right) ->
    new mugs.LLRBNode(
      if key?   && key    != _ then key   else this.key,
      if value? && value  != _ then value else this.value,
      if color? && color  != _ then color else this.color,
      if left?  && left   != _ then left  else this.left,
      if right? && right  != _ then right else this.right)

  F.prototype.insert            = (key,item)  -> insert(new mugs.Some(this),key,item).copy(_,_,BLACK,_,_)
  F.prototype.remove            = (key)       -> remove(new mugs.Some(this),key).get().copy(_,_,BLACK,_,_)
  F.prototype.removeMinKey      = ()          -> removeMin(new mugs.Some(this)).get().copy(_,_,BLACK,_,_)
  F.prototype.minKey            = ()          -> min(new mugs.Some(this)).get().key
  F.prototype.get               = (key)       -> get(new mugs.Some(this),key)
  F.prototype.count             = ()          -> count(new mugs.Some(this))
  F.prototype.containsKey       = (key)       -> containsKey(new mugs.Some(this),key)
  F.prototype.values            = ()          -> values(new mugs.Some(this))
  F.prototype.keys              = ()          -> keys(new mugs.Some(this))
  F.prototype.inorderTraversal  = (f)         -> inorderTraversal(new mugs.Some(this), f)

  ###
    Private : ADT Operations
  ###

  # return the value associated with the given wrapped in an option.
  get = (optionNode, key) ->
    while !optionNode.isEmpty()
      cmp = optionNode.get().comparator(key,optionNode.get().key)
      if      cmp == 0 then return new mugs.Some(optionNode.get().value)
      else if cmp <  0 then optionNode = optionNode.get().left;
      else if cmp >  0 then optionNode = optionNode.get().right;
    return new mugs.None()    

  # checks if 
  containsKey = (optionNode, key) ->
    found = false
    while !optionNode.isEmpty() and !found
      cmp = optionNode.get().comparator(key,optionNode.get().key)
      if      cmp == 0 then return true
      else if cmp <  0 then optionNode = optionNode.get().left;
      else if cmp >  0 then optionNode = optionNode.get().right;
    return false

  # returns the node with the minimum key is tree rooted at optionNode
  min = (optionNode) ->
    if (optionNode.isEmpty())
      return new mugs.None();
    n = optionNode.get() # it's okay. just checked that it wasn't empty
    if n.left.isEmpty()
      return new mugs.Some(n)
    else
      min(n.left)

  # Returns a plain node
  insert = (optionNode,key,item) ->
    if optionNode.isEmpty() then return new mugs.LLRBNode(key,item)

    n   = optionNode.get()
    cmp = n.comparator(key,n.key)

    if (cmp < 0)     then n = n.copy(_,_,_,new mugs.Some(insert(n.left,key,item)),_)
    else if cmp == 0 then n = n.copy(_,item,_,_,_)
    else                  n = n.copy(_,_,_,_,new mugs.Some(insert(n.right,key,item)))

    return fixUp(n)

  # takes option wrapper node and returns an option wrapped node
  removeMin = (optionNode) ->
    if (optionNode.isEmpty() or optionNode.get().left.isEmpty())
      return new mugs.None()

    n = optionNode.get()

    if !isRed(n.left) and !isRed(n.left.get().left)
      n = moveRedLeft(n)

    n = n.copy(_,_,_,removeMin(n.left),_)
    return new mugs.Some(fixUp(n))

  # takes an option wrapped node and returns an option wrapped node
  remove = (optionNode,key) ->

    if optionNode.isEmpty()
      return new mugs.None()

    n = optionNode.get() # it's okay. just checked that it wasn't empty

    if n.comparator(key,n.key) < 0
      if !n.left.isEmpty() and !isRed(n.left) and !isRed(n.left.get().left)
         n = moveRedLeft(n)
      n = n.copy(_,_,_,remove(n.left,key),_)
    else
      if isRed(n.left)
        n = rotateRight(n)
      if !n.right.isEmpty() and !isRed(n.right) and !isRed(n.right.get().left)
        n = moveRedRight(n)
      if n.comparator(key, n.key) == 0
        if n.right.isEmpty()
          return new mugs.None()
        else
          smallest = min(n.right).get()
          n  = n.copy(smallest.key,smallest.val,_,_,removeMin(n.right))
      n = n.copy(_,_,_,_,remove(n.right, key))
    return new mugs.Some(fixUp(n))

  ###
    Methods not directly related to the ADT but very handy 
  ###

  ### 
    Returns the values in the tree in sorted order. 
  ### 
  values = (optionNode) -> 
    arr = []
    inorderTraversal(optionNode, (node) -> arr.push(node.value) )
    new List().buildFromArray(arr)         

  ### 
    Returns the keys in the tree in sorted order. 
  ### 
  keys = (optionNode) -> 
    arr = []
    inorderTraversal(optionNode, (node) -> arr.push(node.key) )
    new List().buildFromArray(arr)         
  
  ###
    This will do an inorderTraversal of the tree applying the function 'f'<commit_msg>fixed more namespace errors<commit_after>###*
@author <NAME> (2011, <EMAIL>)
###
mugs.LLRBNode = (() ->

  ###
    Immutable implementation of Left Leaning Red Black Tree as
    described in this paper: http://www.cs.princeton.edu/~rs/talks/LLRB/LLRB.pdf
  
    Invartiant 1: No red node has a red child
    Invartiant 2: Every leaf path has the same number of black nodes
    Invartiant 3: Only the left child can be red (left leaning)
  ###

  ###
    Public interface
  ###

  F = (key,value,color,left,right) ->
    this.key   = key
    this.value = value
    this.color = if color? then color else RED
    this.left  = if left?  then left  else new mugs.None()
    this.right = if right? then right else new mugs.None()
    this.comparator = standard_comparator
    return this

  F.prototype.copy = (key,value,color,left,right) ->
    new mugs.LLRBNode(
      if key?   && key    != _ then key   else this.key,
      if value? && value  != _ then value else this.value,
      if color? && color  != _ then color else this.color,
      if left?  && left   != _ then left  else this.left,
      if right? && right  != _ then right else this.right)

  F.prototype.insert            = (key,item)  -> insert(new mugs.Some(this),key,item).copy(_,_,BLACK,_,_)
  F.prototype.remove            = (key)       -> remove(new mugs.Some(this),key).get().copy(_,_,BLACK,_,_)
  F.prototype.removeMinKey      = ()          -> removeMin(new mugs.Some(this)).get().copy(_,_,BLACK,_,_)
  F.prototype.minKey            = ()          -> min(new mugs.Some(this)).get().key
  F.prototype.get               = (key)       -> get(new mugs.Some(this),key)
  F.prototype.count             = ()          -> count(new mugs.Some(this))
  F.prototype.containsKey       = (key)       -> containsKey(new mugs.Some(this),key)
  F.prototype.values            = ()          -> values(new mugs.Some(this))
  F.prototype.keys              = ()          -> keys(new mugs.Some(this))
  F.prototype.inorderTraversal  = (f)         -> inorderTraversal(new mugs.Some(this), f)

  ###
    Private : ADT Operations
  ###

  # return the value associated with the given wrapped in an option.
  get = (optionNode, key) ->
    while !optionNode.isEmpty()
      cmp = optionNode.get().comparator(key,optionNode.get().key)
      if      cmp == 0 then return new mugs.Some(optionNode.get().value)
      else if cmp <  0 then optionNode = optionNode.get().left;
      else if cmp >  0 then optionNode = optionNode.get().right;
    return new mugs.None()    

  # checks if 
  containsKey = (optionNode, key) ->
    found = false
    while !optionNode.isEmpty() and !found
      cmp = optionNode.get().comparator(key,optionNode.get().key)
      if      cmp == 0 then return true
      else if cmp <  0 then optionNode = optionNode.get().left;
      else if cmp >  0 then optionNode = optionNode.get().right;
    return false

  # returns the node with the minimum key is tree rooted at optionNode
  min = (optionNode) ->
    if (optionNode.isEmpty())
      return new mugs.None();
    n = optionNode.get() # it's okay. just checked that it wasn't empty
    if n.left.isEmpty()
      return new mugs.Some(n)
    else
      min(n.left)

  # Returns a plain node
  insert = (optionNode,key,item) ->
    if optionNode.isEmpty() then return new mugs.LLRBNode(key,item)

    n   = optionNode.get()
    cmp = n.comparator(key,n.key)

    if (cmp < 0)     then n = n.copy(_,_,_,new mugs.Some(insert(n.left,key,item)),_)
    else if cmp == 0 then n = n.copy(_,item,_,_,_)
    else                  n = n.copy(_,_,_,_,new mugs.Some(insert(n.right,key,item)))

    return fixUp(n)

  # takes option wrapper node and returns an option wrapped node
  removeMin = (optionNode) ->
    if (optionNode.isEmpty() or optionNode.get().left.isEmpty())
      return new mugs.None()

    n = optionNode.get()

    if !isRed(n.left) and !isRed(n.left.get().left)
      n = moveRedLeft(n)

    n = n.copy(_,_,_,removeMin(n.left),_)
    return new mugs.Some(fixUp(n))

  # takes an option wrapped node and returns an option wrapped node
  remove = (optionNode,key) ->

    if optionNode.isEmpty()
      return new mugs.None()

    n = optionNode.get() # it's okay. just checked that it wasn't empty

    if n.comparator(key,n.key) < 0
      if !n.left.isEmpty() and !isRed(n.left) and !isRed(n.left.get().left)
         n = moveRedLeft(n)
      n = n.copy(_,_,_,remove(n.left,key),_)
    else
      if isRed(n.left)
        n = rotateRight(n)
      if !n.right.isEmpty() and !isRed(n.right) and !isRed(n.right.get().left)
        n = moveRedRight(n)
      if n.comparator(key, n.key) == 0
        if n.right.isEmpty()
          return new mugs.None()
        else
          smallest = min(n.right).get()
          n  = n.copy(smallest.key,smallest.val,_,_,removeMin(n.right))
      n = n.copy(_,_,_,_,remove(n.right, key))
    return new mugs.Some(fixUp(n))

  ###
    Methods not directly related to the ADT but very handy 
  ###

  ### 
    Returns the values in the tree in sorted order. 
  ### 
  values = (optionNode) -> 
    arr = []
    inorderTraversal(optionNode, (node) -> arr.push(node.value) )
    new mugs.List().buildFromArray(arr)         

  ### 
    Returns the keys in the tree in sorted order. 
  ### 
  keys = (optionNode) -> 
    arr = []
    inorderTraversal(optionNode, (node) -> arr.push(node.key) )
    new mugs.List().buildFromArray(arr)         
  
  ###
    This will do an inorderTraversal of the tree applying the function 'f'
{'fraction_non_alphanumeric': 0.13896507588224538, 'fraction_numerical': 0.0031084293289449626, 'mean_word_length': 2.4464398235664775, 'pattern_counts': {'":': 0, '<': 15, '<?xml version=': 0, '>': 57, 'https://': 0, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '6406055', 'n_tokens_mistral': 3702, 'n_tokens_neox': 3585, 'n_words': 954}