ref black tree proposed structure

gistfile1.txt

  final class Tree[A, +B](
          private var _key: A,
          private var _value: AnyRef,
          private var _left: Tree[A, _],
          private var _right: Tree[A, _],
          private var _count: Int)
  {
    final def count = _count & 0x7FFFFFFF
    final def key = _key
    final def value = _value.asInstanceOf[B]
    final def left = _left.asInstanceOf[Tree[A, B]]
    final def right = _right.asInstanceOf[Tree[A, B]]

    @inline private def mutable = (_count & 0x80000000) == 0
    def makeImmutable: Tree[A, B] = {
      var size = 1
      if (_left ne null) {_left.makeImmutable; size +=_left.count}
      if (_right ne null) {_right.makeImmutable; size +=_left.count}
      if (isBlack) _count = -size else _count = size
      this
    }
    @inline def isBlack = _count < 0
    @inline def isRed = _count >= 0
    @inline private def initialBlackCount = Int.MinValue
    @inline private def initialRedCount = 0
    @inline private def initialCount = if (isBlack) initialBlackCount else initialRedCount

    def black: Tree[A, B] = {
      if (isBlack) this
      else if (mutable) {
        _count = Int.MinValue;
        this
      }
      else new Tree(_key, _value, _left, _right, initialBlackCount)
    }
    def red: Tree[A, B] = {
      if (isRed) this
      else if (mutable) {
        _count = 0;
        this
      }
      else new Tree(_key, _value, _left, _right, initialRedCount)
    }
    def withkV[B1 >: B](key: A, value: B1): Tree[A, B1] = {
      if (mutable) {
        _key = key
        _value = value.asInstanceOf[AnyRef]
        this
      } else new Tree(key, value.asInstanceOf[AnyRef], _left, _right, _count)
    }
    def withLeft[B1 >: B](newLeft: Tree[A, B1]): Tree[A, B1] = {
      if (mutable) {
        _left = newLeft
        this
      } else new Tree(_key, _value, newLeft, _right, initialCount)
    }
    def withRight[B1 >: B](newRight: Tree[A, B1]): Tree[A, B1] = {
      if (mutable) {
        _right = newRight
        this
      } else new Tree(_key, _value, _left, newRight, initialCount)
    }
  }