Изменить узел в дереве классов дел Scala - PullRequest
Новая
       40

Изменить узел в дереве классов дел Scala

5 голосов
/ 03 февраля 2012

Предположим, у меня есть какая-то сборка дерева, использующая классы дел, что-то вроде этого: 

abstract class Tree
case class Branch(b1:Tree,b2:Tree, value:Int) extends Tree
case class Leaf(value:Int) extends Tree
var tree = Branch(Branch(Leaf(1),Leaf(2),3),Branch(Leaf(4), Leaf(5),6))

А теперь я хочу построить метод для изменения узла с некоторым идентификатором на другой узел.Этот узел легко найти, но я не знаю, как его изменить.Есть ли простой способ сделать это?

Ответы [ 3 ]

3 голосов
/ 03 февраля 2012

Это очень интересный вопрос! Как уже отмечали другие, вы должны изменить весь путь от корня до узла, который вы хотите изменить. Неизменяемые карты очень похожи, и вы можете узнать что-то , глядя на PersistentHashMap Clojure .

Мои рекомендации:

  • Измените Tree на Node. Вы даже называете это узлом в своем вопросе, так что это, вероятно, лучшее имя.
  • Потяните value до базового класса. Еще раз, вы говорите об этом в своем вопросе, так что это, вероятно, правильное место для этого.
  • В вашем методе замены убедитесь, что если ни Node, ни его дочерние элементы не изменились, не создавайте новый Node.

Комментарии в коде ниже: 

// Changed Tree to Node, b/c that seems more accurate
// Since Branch and Leaf both have value, pull that up to base class
sealed abstract class Node(val value: Int) {
  /** Replaces this node or its children according to the given function */
  def replace(fn: Node => Node): Node

  /** Helper to replace nodes that have a given value */
  def replace(value: Int, node: Node): Node =
    replace(n => if (n.value == value) node else n)
}

// putting value first makes class structure match tree structure
case class Branch(override val value: Int, left: Node, right: Node)
     extends Node(value) {
  def replace(fn: Node => Node): Node = {
    val newSelf = fn(this)

    if (this eq newSelf) {
      // this node's value didn't change, check the children
      val newLeft = left.replace(fn)
      val newRight = right.replace(fn)

      if ((left eq newLeft) && (right eq newRight)) {
        // neither this node nor children changed
        this
      } else {
        // change the children of this node
        copy(left = newLeft, right = newRight)
      }
    } else {
      // change this node
      newSelf
    }
  }
}
2 голосов
/ 03 февраля 2012

Поскольку ваша древовидная структура является неизменной, вы должны изменить весь путь от узла до корня. когда вы посещаете свое дерево, сохраняйте список посещенных узлов, затем обновите все узлы вплоть до корня, используя метод копирования , как предложено pr10001 .

1 голос
/ 03 февраля 2012

Метод copy: 

val tree1 = Branch(Branch(Leaf(1),Leaf(2),3),Branch(Leaf(4), Leaf(5),6))
val tree2 = tree1.copy(b2 = tree1.b2.copy(b1 = Leaf(5))
// -> Branch(Branch(Leaf(1),Leaf(2),3),Branch(Leaf(5), Leaf(5),6))
...