Реализация двоичного дерева в Scala

Question

У меня возникли трудности с установкой двоичного дерева в Scala. Он должен быть ковариантным по отношению к его параметрам типа (чтобы разрешить нулевой тип дерева), а его тип для его ключа должен быть подклассом Ordered, позволяющим сравнивать с другими ключами. Это то, что я до сих пор:

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] 

, который дает мне 6 ошибок через 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 

Это только одна комбинация границ типа, которые я пробовал. У меня так много ошибок, что я не знаю, какие из них являются реальной проблемой и которые вызваны другими проблемами; поэтому я не знаю с чего начать.

Я предполагаю, что в моем понимании есть какая-то огромная дыра. Может кто-нибудь, пожалуйста, указать, что является основной проблемой с тем, что у меня выше?

Answer 1

Возьмите это как вдохновение. Взгляните на реализацию Карты в Скале. Тип ключа не является ковариантным, тип значения -. Возможно, имеет смысл определить метод isEmpty, а не шаблон, сопоставляющий объект.

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]