CODEWITHSUNDEEP
scala
Carcigenicate
Carcigenicate

Reputation: 45742

Implementing a Binary Tree in Scala

I'm having difficulty setting up a Binary Tree in Scala. It will have to be covariant of it's type parameters (to allow a null-tree type), and its type for its key will need to be a sub class of Ordered, to allow for comparisons against other keys. This is what I have so far:

package tutorial

class AbTree[+K <: Ordered[K],+V] {
    def throwTreeException(msg:String) = throw new
            Exception("TreeException: " + msg)

    def replaceL[L >: K, W >: V](nTree:AbTree[L,W]): AbTree[L,W] = this match {
        case ETree => throwTreeException("replaceL called on an ETree")
        case tree:Tree[L,W] => tree.copy(lTree = nTree)
    }

    def replaceR[L >: K, W >: V](nTree:AbTree[L,W]): AbTree[L,W] = this match {
        case ETree          => throwTreeException("replaceR called on an ETree")
        case tree:Tree[L,W] => tree.copy(rTree = nTree)
    }

    def insert[L >: K, W >: V](nK:L,nV:W): AbTree[L,W] = this match {
        case ETree => Tree(nK,nV)                                           //Line 18
        case Tree(k,v,lT,rT) =>
            if (nK < k) replaceL(lT.insert(nK,nV))
            else if (nK > k) replaceR(rT.insert(nK,nV))                     //Line 21
            else Tree(k,v,lT,rT)
    }
}

case class Tree[+K <: Ordered[K],+V]
    (key:K,value:V,lTree:AbTree[K,V] = ETree,rTree:AbTree[K,V] = ETree)
    extends AbTree[K,V]

case object ETree
    extends AbTree[Nothing,Nothing]

which gives me 6 errors across insert:

- Line 18: inferred type arguments [L,W] do not conform to method apply's type parameter bounds [K <: Ordered[K],V] Error occurred in an application involving default arguments.
- Line 18: type mismatch;  found   : L  required: K Error occurred in an application involving default arguments
- Line 18: type mismatch;  found   : tutorial.Tree[K,V]  required: tutorial.AbTree[L,W] Error occurred in an application involving default arguments.
- Line 18: type mismatch;  found   : W  required: V Error occurred in an application involving default arguments.
- Line 20: value < is not a member of type parameter L
- Line 21: value > is not a member of type parameter L

This is only one combination of type bounds that I tried. I've gotten so many errors pushing through this that I don't know which ones are the real problem, and which are caused by other issues; so I don't know where to begin.

I'm guessing there's a huge hole in my understanding somewhere. Can someone please point out what's the primary problem with what I have above?

Upvotes: 1

Views: 1085

Answers (1)

Rado Buransky
Rado Buransky

Reputation: 3294

Take this as an inspiration. Take a look at the implementation of the Map in Scala. Key type is not covariant, value type is. Perhaps it makes more sense to define isEmpty method rather than pattern matching an object.

class AbTree[K, +V](implicit ordering: Ordering[K]) {
  def throwTreeException(msg:String) = throw new
      Exception("TreeException: " + msg)

  def replaceL[W >: V](nTree:AbTree[K, W]): AbTree[K, W] = {
    val empty = AbTree.empty[K, V]
    this match {
      case `empty` => throwTreeException("replaceL called on an ETree")
      case tree:Tree[K, W] => tree.copy(lTree = nTree)
    }
  }

  def replaceR[W >: V](nTree:AbTree[K, W]): AbTree[K, W] = {
    val empty = AbTree.empty[K, V]
    this match {
      case `empty`          => throwTreeException("replaceR called on an ETree")
      case tree:Tree[K, W] => tree.copy(rTree = nTree)
    }
  }

  def insert[W >: V](nK:K,nV:W): AbTree[K,W] = {
    val empty = AbTree.empty[K, V]
    this match {
      case `empty` => Tree(nK, nV) //Line 18
      case Tree(k, v, lT, rT) =>
        if (ordering.compare(nK, k) < 0) replaceL(lT.insert(nK, nV))
        else if (ordering.compare(nK, k) > 0) replaceR(rT.insert(nK, nV)) //Line 21
        else Tree(k, v, lT, rT)
    }
  }

}

object AbTree {
  implicit private object NothingOrdering extends Ordering[Any] {
    override def compare(x: Any, y: Any): Int = 0
  }
  private object ETree extends AbTree[Any, Nothing]

  def empty[K, V]: AbTree[K, V] = ETree.asInstanceOf[AbTree[K, V]]
}

case class Tree[K, +V](key:K,
                       value:V,
                       lTree:AbTree[K,V] = AbTree.empty[K, V],
                       rTree:AbTree[K,V] = AbTree.empty[K, V])
                      (implicit ordering: Ordering[K]) extends AbTree[K,V]

Upvotes: 1

Related Questions