🌳

Kotlinで木構造を宣言的に扱うOSS kotlin-treeを公開しました

2023/01/04に公開

Kotlin

OSS

tech

はじめに

明けましておめでとうございます！
年末年始でKotlinで木構造を宣言的に扱うためのkotlin-treeというOSSを公開しました！

KotlinのCollection APIのように木構造を処理することができます。楽！

val treeNode: TreeNode<Int> = nodeOf(
    1,
    mutableListOf(
        nodeOf(
            11,
            mutableList(
                leafOf(111),
                leafOf(112)
            )
        ),
        leafOf(12)
    )
)
// 1
// ├── 11
// │   ├── 111
// │   └── 112
// └── 12

treeNode.map { ele -> ele * 2 }
// 2
// ├── 22
// │   ├── 222
// │   └── 224
// └── 24

以下作ったモチベーションをつらつら書きます。

Kotlinで汎用的な木構造のAPIを提供したい
隣接モデルなどの他モデルへの変換を楽にしたい

Kotlinで汎用的な木構造のAPIを提供したい

このライブラリを作った一つ目の理由はKotlinやJavaには標準で木構造を処理するAPIが存在しないためです。
Kotlinの標準のCollection APIはmapやfilterなど便利で直感的なAPIを提供しているものの、木構造になると自分でデータ構造を定義するところから始めなくてはいけません。
また、木構造を処理するとなるとほぼ必ず再起処理を使わないといけません（whileループでもいいが使いたい人はいるかはわからない）。

class TreeNode(
    val value: Int,
    val children: List<TreeNode>
) {
    fun double(): TreeNode {
        return TreeNode(
            value * 2,
            children.map { node -> node.double() }
        )
    }
}

上記のような単純な例なら問題ないですが、実装が複雑になればなるほど再起処理の扱いは面倒になっていきます。
そして多分木の再起処理は末尾最適化ができず、上記のような実装は木構造の階層が深いケースにおいてスタックオーバーフローを起こします。

このような課題に対してkotlin-treeでは使用者が再起処理を意識せずとも値の変換やフィルタリング処理ができるようなAPIを提供しています。
詳細は以下のREADMEのExamplesの章をご確認ください。

また、内部実装はスタック + whileループの深さ優先探索で実装されていて、スタックオーバーフローを起こさないようにしています（=再起処理を使って実装していない）。

こちらについても実装は200行とないのでお時間ある方はぜひお読みください！

隣接モデルなどの他モデルへの変換を楽にしたい

木構造を扱う上での二つ目の問題は、木構造はRDBMSなどのデータベースにそのまま保存することが難しいという点です。

以下のようなデータがあったとき、よくRDBMSでは隣接モデルや経路列挙モデルのようなモデルに変換してデータを保存します。

// 1
// ├── 11
// │   ├── 111
// │   └── 112
// └── 12

隣接モデル

parent_node_id	self_node_id
null	1
1	11
11	111
11	112
1	12

経路列挙モデル

path	node_id
1	1
1/11	11
1/11/111	111
1/11/112	112
1/12	12

この辺の木構造におけるスキーマ戦略は以下の本に詳しく書いてありますのでリンクをつけておきます。

意外に難しい変換処理

試してみるとわかるのですが、これらのモデルとの変換処理は意外に難しいです。
少なくとも普段のWeb開発に求められるアルゴリズムの能力の少し上をいった複雑な実装が必要になります。

しかしご安心を！ kotlin-treeでは上記の二つ、隣接モデルや経路列挙モデルに対しての変換処理を提供しています。

// 経路列挙モデル（AdjacencyModel）
val adjacencyList = AdjacencyList.of(
    getSelfNodeId = { it },
    list = listOf(
        null to 1,
        1 to 11,
        11 to 111,
        1 to 12,
        null to 2,
        2 to 21,
        3 to 31 // the parentNodeId is not found
    )
)
val (treeNodes, parentNodeNotFoundList) = adjacencyList.toTreeNode()
// treeNodes
// 1
// ├── 11
// │   ├── 111
// │   └── 112
// └── 12
// 2
// └── 21
// parentNodeNotFoundList
// (parentNodeId: 3, selfNodeId: 31)

通常の変換処理に加えて、親ノードが見つからないなどの不整合なノードを見つけることもできます。
もちろん逆方向の変換もすることが可能です。
こちらも詳しくはREADMEをお読みください。

ぜひ使ってみた感想をお願いします！

自分としては他企業のプロダクションコードにガチ導入されるレベルのものにしていくつもりです！
使ってみて良さそうならぜひスターをつけていただいたり、感想をツイートしていただけると幸いです！
Issueもお待ちしています！