Как создать отношения родитель-ребенок в неизменных классах Kotlin

Question

У меня есть неизменяемые классы, представляющие дерево, где детям нужна родительская ссылка.

sealed class Node {
    abstract val parent: Parent?
}

class Child(
    override val parent: Parent,
) : Node()

class Parent(
    override val parent: Parent?,
    val children: List<Node>
) : Node()

Существует ли идиоматический способ Kotlin для создания родителя со списком детей, для которого правильно установлена ​​родительская ссылка?

Answer 1

Мы можем заполнить Parent изменяемым списком, который мы заполняем, когда у нас есть ссылка.

sealed class Node {
    abstract val parent: Parent?
}

class Child(
    override val parent: Parent
) : Node()

class Parent(
    override val parent: Parent?,
    val children: List<Node>
) : Node() {
    companion object {
        operator fun invoke(parent: Parent?, childBuilders: List<(Parent) -> Node>): Parent {
            val children = mutableListOf<Node>()
            return Parent(parent, children).apply {
                children.addAll(childBuilders.map { it(this) })
            }
        }
    }
}

Answer 2

Вы можете попробовать использовать параметры корневого узла и компоновщика:

sealed class Node {
    data class Root(
        val createChildren: ParentList.() -> Unit
    ) : Node() {
        val children: List<Node> = ParentList(this).apply(createChildren)
    }

    data class Branch(
        val createChildren: ParentList.() -> Unit,
        val parent: Node
    ) : Node() {
        val children: List<Node> = ParentList(this).apply(createChildren)
    }

    data class Leaf(
        val parent: Node
    ) : Node()
}

class ParentList(
    val parent: Node,
    private val children: MutableList<Node> = mutableListOf()
) : List<Node> by children {

    fun branch(createChildren: ParentList.() -> Unit) {
        children += Node.Branch(createChildren, parent)
    }

    fun leaf() {
        children += Node.Leaf(parent)
    }

}

fun root(createChildren: ParentList.() -> Unit) = Node.Root(createChildren)

Они могут быть построены следующим образом (возможно, потребуется добавить дополнительные детали к любому из узлов):

fun usage() {

    val graph = root {
        branch {
            leaf()
        }
        branch {
            branch {
                leaf()
            }
            leaf()
        }
    }
}

Вы можете разрешить доступ потенциальным детям и / или родителям со свойствами расширения:

val Node.children: List<Node> get() = when(this) {
    is Node.Root -> children
    is Node.Branch -> children
    is Node.Leaf -> emptyList()
}

val Node.parent: Node? get() = when(this) {
    is Node.Root -> null
    is Node.Branch -> parent
    is Node.Leaf -> parent
}

Итак, вы можете перемещаться по потомкам:

fun Node.allChildren(): List<Node> = 
  children + children.flatMap { it.allChildren() }

Или перейти вверх:

fun Node.allParents(): List<Node> = 
  listOfNotNull(parent).flatMap { listOf(it) + allParents() }

Чтобы избежать оценки при выполнении поиска, который может закончиться раньше, вы всегда можете использовать последовательности вместо списков:

fun Node.allChildren(): Sequence<Node> = 
  children.asSequence() + children.asSequence().flatMap { it.allChildren() }

fun Node.allParents(): Sequence<Node> = 
  listOfNotNull(parent).asSequence().flatMap { sequenceOf(it) + it.allParents() }

Примечание: Остерегайтесь Stackoverflows

Answer 3

Вместо того, чтобы настаивать на неизменности, возможно, вы остановитесь только на чтении. Думайте об этом как об аналоге kotlins MutableList / List. Примерно так:

sealed class Node {
    abstract val parent: Container?
}

abstract class Child : Node()

abstract class Container : Node() {
    abstract val children: List<Node>
}

private class MutableChild(override var parent: Container?) : Child()

private class MutableContainer(override var parent: Container?, override var children: List<Node>) : Container()

fun buildTree() : Node {
    val children = mutableListOf<Node>()
    val parent = MutableContainer(null, children)
    MutableChild(parent).also { children.add(it) }
    MutableChild(parent).also { children.add(it) }

    return parent
}

Answer 4

Мы можем лениво оценить список строителей в первый раз, когда нужны дети. Обратите внимание, что это безопасно только в том случае, если остальная часть кодовой базы достаточно прозрачна по ссылкам.

sealed class Node {
    abstract val parent: Parent?
}

class Child(
    override val parent: Parent
) : Node()

class Parent(
    override val parent: Parent?,
    private val childBuilders: List<(Parent) -> Node>
) : Node() {

    val children: List<Node> by lazy {
        childBuilders.map { it(this)}
    }
}

Answer 5

Альтернативный подход может заключаться в том, чтобы сделать parent устанавливаемым изнутри Node и предоставить ему список дочерних элементов, для которых нужно установить родителя.

sealed class Node(
    children: List<Node> = listOf()
) {
    var parent: Container? = null
        private set

    init {
        (this as? Container)?.apply {
            children.forEach { it.parent = this }            
        }
    }
}

data class Child(val type: String) : Node()

data class Container(
    val children: List<Node>
) : Node(children)

Единственным побочным эффектом является то, что parent не будет использоваться классами данных как свойство.