Home About Contact
Kotlin , Tree Data Structure

木構造のノード出現順（深さ優先順）に番号を振る話 EPUB playOrder

EPUB の toc.ncx ファイルで naviPoint の playOrder 属性を指定する必要がある。 プログラム的にこれを設定する方法を実装したので、覚え書きとして書き残します。

この辺の話です。 ちなみに、EPUB3 では toc.ncx はもはや不要だとか。

テスト環境:

$ kotlin -version
Kotlin version 1.8.10-release-430 (JRE 17.0.10+7-Ubuntu-122.04.1)

EPUBの目次情報を簡略化して擬似的に表現したコードはこんな感じ:

data class TreeNode(val name: String, val children: List<TreeNode>)

val children1 = listOf(
    TreeNode("1-1", listOf()),
    TreeNode("1-2", listOf()),
    TreeNode("1-3", listOf()))

val children = listOf(
    TreeNode("1", children1),
    TreeNode("2", listOf()),
    TreeNode("3", listOf()))

val rootTreeNode = TreeNode("root", children)

これを show する関数がこれ:

val showTreeNode: (TreeNode)->Unit = { treeNode->
    val indent: (Int)->String = { l-> 0.until(l).map { "  " }.joinToString("") }

    fun recur(acc: List<String>, tn: TreeNode, l: Int): List<String> {
        val newAcc = acc + listOf( "${indent(l)}- ${tn.name}" )

        val leaf = ( tn.children.size<1 )
        return if( leaf ){
            newAcc
        } else {
            tn.children.fold(newAcc, { acc0, childTreeNode->
                recur(acc0, childTreeNode, l+1) 
            })
        }
    }

    val initialValue = listOf<String>()
    val initialIndentValue = 0
    val list = recur(initialValue, treeNode, initialIndentValue)
    println( list.joinToString(System.getProperty("line.separator")) )
}

実行する:

$ kotlin main.kts
- root
  - 1
    - 1-1
    - 1-2
    - 1-3
  - 2
  - 3

playOrder の値は次のように割り当てたい。

$ kotlin main.kts
- root (1)
  - 1 (2)
    - 1-1 (3)
    - 1-2 (4)
    - 1-3 (5)
  - 2 (6)
  - 3 (7)

どうするか。

まず、 TreeNode にそっくりだが、各ノードに playOrder 値を保持できる XTeeeNode クラスを用意します。

data class XTreeNode(
    val name: String,
    val playOrder: Int,
    val children: List<XTreeNode>)

次に TreeNode を XTreeNode に変換する関数を書きます。 シグニチャーはこれ:

typealias TreeConverter = (TreeNode)->XTreeNode

説明上わかりやすくするために typealias しました。

実装はこれ:

val convertTreeNodeToXTreeNode: TreeConverter = { treeNode->
    fun toXTreeNode(playOrder: Int, tn: TreeNode): Pair<Int,XTreeNode> {
        val myPlayOrder = playOrder+1

        val list: List<Pair<Int,XTreeNode>> = tn.children.fold(listOf<Pair<Int,XTreeNode>>(),  { acc, childTreeNode->
            val currentPlayOrder = if( acc.size<1 ){ myPlayOrder } else { acc.last().first }

            val (playOrder0, xTreeNode) = toXTreeNode(currentPlayOrder, childTreeNode)
            if( xTreeNode!=null ){
                acc + listOf(Pair(playOrder0, xTreeNode))
            } else {
                acc
            }
        })

        val children: List<XTreeNode> = list.map { it.second }
        val xTreeNode = XTreeNode(tn.name, myPlayOrder, children)
        val newPlayOrder = if( list.size<1 ){ myPlayOrder } else { list.last().first }
        return Pair(newPlayOrder, xTreeNode)
    }

    val (_, xTreeNode) = toXTreeNode(0, treeNode)
    xTreeNode
}

fold を使って TreeNode を playOrder をつけたい順番に巡回しつつ（何優先なのか？深さ優先 depth-first search ？）、 playOrder 値を引き継ぎつつ、ノードごとにカウントアップしていく感じです。

最後に、意図通り playOrder 値をセットできたか確認するための showXTreeNode 関数を書きます。

val showXTreeNode: (XTreeNode)->Unit = { xTreeNode->
    val indent: (Int)->String = { l-> 0.until(l).map { "  " }.joinToString("") }

    fun recur(acc: List<String>, tn: XTreeNode, l: Int): List<String> {
        val newAcc = acc + listOf( "${indent(l)}- ${tn.name} (${tn.playOrder})" )

        val leaf = ( tn.children.size<1 )
        return if( leaf ){
            newAcc
        } else {
            tn.children.fold(newAcc, { acc0, childTreeNode->
                recur(acc0, childTreeNode, l+1) 
            })
        }
    }

    val initialValue = listOf<String>()
    val initialIndentValue = 0
    val list = recur(initialValue, xTreeNode, initialIndentValue)
    println( list.joinToString(System.getProperty("line.separator")) )
}

showTreeNode 関数とほぼ同じです。単に ノード情報を出力するときに playOrder 値を追記して出力している。

これを使って、意図通りできたか確認します。

//showTreeNode(rootTreeNode)
showXTreeNode(convertTreeNodeToXTreeNode(rootTreeNode))

実行。

$ kotlin main.kts
- root (1)
  - 1 (2)
    - 1-1 (3)
    - 1-2 (4)
    - 1-3 (5)
  - 2 (6)
  - 3 (7)

うまくいきました。

本当に意図通り作動するのか？木構造の階層をさらに追加して実験してみます。

val children11 = listOf(
    TreeNode("1-1-1", listOf()),
    TreeNode("1-1-2", listOf()),
    TreeNode("1-1-3", listOf()))

val children1 = listOf(
    TreeNode("1-1", children11),
    TreeNode("1-2", listOf()),
    TreeNode("1-3", listOf()))

実行。

$ kotlin main.kts
- root (1)
  - 1 (2)
    - 1-1 (3)
      - 1-1-1 (4)
      - 1-1-2 (5)
      - 1-1-3 (6)
    - 1-2 (7)
    - 1-3 (8)
  - 2 (9)
  - 3 (10)

どうやら意図通り作動しそうです。

まとめ

コード全体を掲載します。

typealias TreeConverter = (TreeNode)->XTreeNode

val convertTreeNodeToXTreeNode: TreeConverter = { treeNode->
    fun toXTreeNode(playOrder: Int, tn: TreeNode): Pair<Int,XTreeNode> {
        val myPlayOrder = playOrder+1

        val list: List<Pair<Int,XTreeNode>> = tn.children.fold(listOf<Pair<Int,XTreeNode>>(),  { acc, childTreeNode->
            val currentPlayOrder = if( acc.size<1 ){ myPlayOrder } else { acc.last().first }

            val (playOrder0, xTreeNode) = toXTreeNode(currentPlayOrder, childTreeNode)
            if( xTreeNode!=null ){
                acc + listOf(Pair(playOrder0, xTreeNode))
            } else {
                acc
            }
        })

        val children: List<XTreeNode> = list.map { it.second }
        val xTreeNode = XTreeNode(tn.name, myPlayOrder, children)
        val newPlayOrder = if( list.size<1 ){ myPlayOrder } else { list.last().first }
        return Pair(newPlayOrder, xTreeNode)
    }

    val (_, xTreeNode) = toXTreeNode(0, treeNode)
    xTreeNode
}

val showTreeNode: (TreeNode)->Unit = { treeNode->
    val indent: (Int)->String = { l-> 0.until(l).map { "  " }.joinToString("") }

    fun recur(acc: List<String>, tn: TreeNode, l: Int): List<String> {
        val newAcc = acc + listOf( "${indent(l)}- ${tn.name}" )

        val leaf = ( tn.children.size<1 )
        return if( leaf ){
            newAcc
        } else {
            tn.children.fold(newAcc, { acc0, childTreeNode->
                recur(acc0, childTreeNode, l+1) 
            })
        }
    }

    val initialValue = listOf<String>()
    val initialIndentValue = 0
    val list = recur(initialValue, treeNode, initialIndentValue)
    println( list.joinToString(System.getProperty("line.separator")) )
}

val showXTreeNode: (XTreeNode)->Unit = { xTreeNode->
    val indent: (Int)->String = { l-> 0.until(l).map { "  " }.joinToString("") }

    fun recur(acc: List<String>, tn: XTreeNode, l: Int): List<String> {
        val newAcc = acc + listOf( "${indent(l)}- ${tn.name} (${tn.playOrder})" )

        val leaf = ( tn.children.size<1 )
        return if( leaf ){
            newAcc
        } else {
            tn.children.fold(newAcc, { acc0, childTreeNode->
                recur(acc0, childTreeNode, l+1) 
            })
        }
    }

    val initialValue = listOf<String>()
    val initialIndentValue = 0
    val list = recur(initialValue, xTreeNode, initialIndentValue)
    println( list.joinToString(System.getProperty("line.separator")) )
}


data class TreeNode(val name: String, val children: List<TreeNode>)

data class XTreeNode(
    val name: String,
    val playOrder: Int,
    val children: List<XTreeNode>)

val children11 = listOf(
    TreeNode("1-1-1", listOf()),
    TreeNode("1-1-2", listOf()),
    TreeNode("1-1-3", listOf()))

val children1 = listOf(
    TreeNode("1-1", children11),
    TreeNode("1-2", listOf()),
    TreeNode("1-3", listOf()))

val children = listOf(
    TreeNode("1", children1),
    TreeNode("2", listOf()),
    TreeNode("3", listOf()))

/*
val children1 = listOf(
    TreeNode("1-1", listOf()),
    TreeNode("1-2", listOf()),
    TreeNode("1-3", listOf()))

val children = listOf(
    TreeNode("1", children1),
    TreeNode("2", listOf()),
    TreeNode("3", listOf()))
*/

val rootTreeNode = TreeNode("root", children)

//showTreeNode(rootTreeNode)
showXTreeNode(convertTreeNodeToXTreeNode(rootTreeNode))

以上です。