상속 된 PrefixMap 맵은 무엇이 업데이트됩니까?

Question

스칼라 컬렉션의 아키텍처 스칼라 프로그래밍, 제 3 판 프로그래밍에서 PrefixMap 예제를 실행하면 업데이트를 호출 할 때 상속 된 PrefixMap 맵을 업데이트하는 것이 이해가 안됩니다.

import collection._ 

class PrefixMap[T] 
    extends mutable.Map[String, T] 
    with mutable.MapLike[String, T, PrefixMap[T]] { 

    val id: Long = PrefixMap.nextId 
    var suffixes: immutable.Map[Char, PrefixMap[T]] = Map.empty 
    var value: Option[T] = None 

    def get(s: String): Option[T] = 
    if (s.isEmpty) value 
    else suffixes get s(0) flatMap (_.get(s substring 1)) 

    def withPrefix(s: String): PrefixMap[T] = 
    if (s.isEmpty) this 
    else { 
     val leading = s(0) 
     suffixes get leading match { 
     case None => 
      suffixes = suffixes + (leading -> empty) 
     case _ => 
     } 
     val ret = suffixes(leading) withPrefix (s substring 1) 
     println("withPrefix: ends with: id="+this.id+", size="+this.size+", this="+this) 
     ret 
    } 

    override def update(s: String, elem: T) = { 
    println("update: this before withPrefix: id="+this.id+", size="+this.size+", return="+this) 
    val pm = withPrefix(s) 
    println("update: withPrefix returned to update: id="+pm.id+", size="+pm.size+", return="+pm) 
    println("===> update: this after withPrefix and before assignment to pm.value : id="+this.id+", size="+this.size+", return="+this) 
    pm.value = Some(elem) 
    println("===> update: this after assinment to pm.value: id="+this.id+", size="+this.size+", return="+this) 
    } 

    override def remove(s: String): Option[T] = 
    if (s.isEmpty) { val prev = value; value = None; prev } 
    else suffixes get s(0) flatMap (_.remove(s substring 1)) 

    def iterator: Iterator[(String, T)] = 
    (for (v <- value.iterator) yield ("", v)) ++ 
     (for ((chr, m) <- suffixes.iterator; 
      (s, v) <- m.iterator) yield (chr +: s, v)) 

    def += (kv: (String, T)): this.type = { update(kv._1, kv._2); this } 

    def -= (s: String): this.type = { remove(s); this } 

    override def empty = new PrefixMap[T] 
} 

object PrefixMap { 
    var ids: Long = 0 
    def nextId: Long = { PrefixMap.ids+=1; ids } 
} 

object MyApp extends App { 
    val pm = new PrefixMap[Int] 
    pm.update("a", 0) 
    println(pm) 

} 

출력은 :

업데이트이 withPrefix 전 : 여기서 는 코드 ID = 1, 크기 = 0, = 복귀 맵()

withPrefix : ID : 끝나는 = 1, 크기 = 0이 맵()

업데이트 = withPrefix 업데이트 반환 이드 = 2, 사이즈 = 0을 반환 = 맵()

===> 업데이트이 withPrefix 후 과제 t 전에 id = 1, size = 1, return = Map (a - pm.value : id = 1, size = 0, return = Map()

업데이트 : > 0)

지도 (A -> 0)

그래서 질문은 :이 업데이트 방법 "pm.value = 일부 (ELEM)"와 라인의 상속지도 발생 가능성이 방법 PrefixMap을 (a -> 0)으로 업데이트 하시겠습니까?

Answer 1

그것은 당신이 무슨 뜻인지 분명하지 않다 "는 PrefixMap의지도를 상속". Map은 trait입니다. Java 월드에서 온 경우 interface과 유사합니다. 즉, Map은 자체적으로 아무런 가치도 가지지 않으며 계약을 지정하고 "핵심"방법 (PrefixMap에서 구현하는 방법)을 통해 다양한 편의 방법의 기본 구현을 제공합니다.

이 전체 데이터 구조가 어떻게 작동하는지에 대해서는 PrefixMap 구현을 "tree"으로 상상해야합니다. 논리적으로 각 모서리는 단일 문자 (접두사 시퀀스에서)를 가지며 각 노드는 잠재적으로 루트에서 현재 노드로가는 도중에 모든 문자가 누적되어 생성되는 문자열에 해당합니다. 당신이 나무에 "ac" -> 123를 추가하는 경우, 그것은

될 것

를 실행 한 다음, 당신은 "ab" -> 12 키 - 값을 가진지도가있는 경우

그래서 나무는 다음과 같을 것

마지막으로 "a" -> 1을 트리에 추가하면 다음과 같이됩니다.

"a"노드를 루트로 사용하면 남은 것은 유효한 접두사 트리이며 모든 문자열은 접두사 "a"로 축약됩니다.

물리적 레이아웃은 약간 다릅니다

1. 는 루트 외부에서 Map[String,T]입니다 PrefixMap[T]입니다 노드 및 빈 문자열 키에 대한 노드가 있습니다. value + suffixes 즉 옵션 값이며,
2. 내부 노드는 구현이 효과적으로 withPrefix 호출하고 뭔가를 찾을 수있다 update 볼 수 있습니다으로 어린이의 목록이 Map[Char, PrefixMap[T]]

으로 가장자리에 해당 문자로 노드 합병 그것을 가치 부여. 그래서 withPrefix 메서드는 무엇을합니까? 재귀 적으로 구현되지만 반복적 인 방식으로 생각하는 것이 더 쉬울 수도 있습니다. 이러한 관점에서, 그것은 하나에 의해 주어진 String 하나의 문자로 반복없는 노드가

case None => 
     suffixes = suffixes + (leading -> empty) 

을보고 마지막으로 케이스에 전체 String (즉, this에 해당하는 노드를 반환 만드는 트리를 탐색 깊은 재귀 s.isEmpty)

방법 get 구현은 실제로 withPrefix와 매우 유사하다 : 그것은 재귀 적으로 반복 주어진 문자열 이상과 트리를 탐색하지만 누락 된 노드를 만들 필요가 없기 때문에 간단합니다. 자식 노드는 실제로 Map에 저장되기 때문에 get 메서드는 Option을 반환합니다. PrefixMap은 Option과 같은 방식으로 반환됩니다. 따라서 flatMap을 사용할 수 있으며 특정 수준에 그러한 자식 노드가 없으면 정상적으로 작동합니다.

마지막 iterator는 value.iterator

모든 iterator (스칼라 다행히도 Option이 값의 유무를 그냥 1 0 소자 따라 반환 iterator를 구현)

1. 의 조합으로 반복자를 작성 키의 접두사로서 자신의 문자를 추가하는 것만으로 모든 자식 노드를 처리 할 수 ​​있습니다.

그래서 당신은

val pm = new PrefixMap[Int] 
pm.update("a", 0) 
println(pm) 

update이 트리의 노드 (들)을 생성하는과 값을 저장 할 때. pm.toString은 실제로 iterate을 사용하여 문자열 표현을 만듭니다. 따라서 트리 컬렉션을 통해 모든 노드의 비어 있지 않은 모든 값 (valueOption)을 반복합니다.