CodeKataをKotlinでやってみた 〜Transitive Dependencies編〜

今回もCodeKataをKotlinでやっていきたいと思います。
「そもそもCodeKataって何？」と言う方は"CodeKataをKotlinでやってみた 〜Karate Chop編〜"をご参照ください。

トライしてみる

今回の課題は21あるKataのうち18つ目に当たる"Transitive Dependencies"です。

Let’s write some code that calculates how dependencies propagate between things such as classes in a program.
......
One of the insidious things about dependencies is that they are transitive—if A depends on B and B depends on C, then A also depends on C. So, let’s write some code that calculates the full set of dependencies for a group of items. The code takes as input a set of lines where the first token is the name of an item. The remaining tokens are the names of things that this first item depends on. Given the following input, we know that A directly depends on B and C, B depends on C and E, and so on.

  A   B   C
  B   C   E
  C   G
  D   A   F
  E   F
  F   H

The program should use this data to calculate the full set of dependencies. For example, looking at B, we see it directly depends on C and E. C in turn relies on G, E relies on F, and F relies on H. This means that B ultimately relies on C, E, F, G, and H. In fact, the full set of dependencies for the previous example is:

  A   B C E F G H
  B   C E F G H
  C   G
  D   A B C E F G H
  E   F H
  F   H

Let’s express this using unit tests. The following code assumes that our dependency calculator is a class with an add_direct() method to add the direct dependencies for an item, and a dependencies_for() method to return the full list of dependencies for an item. The code uses Ruby’s %w{…} construct, which builds an array of strings from its argument.

def test_basic
  dep = Dependencies.new
  dep.add_direct('A', %w{ B C } )
  dep.add_direct('B', %w{ C E } )
  dep.add_direct('C', %w{ G   } )
  dep.add_direct('D', %w{ A F } )
  dep.add_direct('E', %w{ F   } )
  dep.add_direct('F', %w{ H   } )
>
  assert_equal( %w{ B C E F G H },   dep.dependencies_for('A'))
  assert_equal( %w{ C E F G H },     dep.dependencies_for('B'))
  assert_equal( %w{ G },             dep.dependencies_for('C'))
  assert_equal( %w{ A B C E F G H }, dep.dependencies_for('D'))
  assert_equal( %w{ F H },           dep.dependencies_for('E'))
  assert_equal( %w{ H },             dep.dependencies_for('F'))
end

つまり、あるファイル群が与えられた時、各ファイルが依存している全ファイルを算出するようなプログラムを実装することが今回の課題です。注意しなければいけないのは、例えばファイル"A"が直接依存しているファイルが"B"/"C"の2つであったとしても、ファイル"B"が"C"/"E"に依存しているのであれば"A"は間接的に"E"にも依存しているとして算出を行う必要がある点です。
メソッド呼び出しのインターフェースはブログ記事で提示されているテストケースのものを踏襲しようと思います。

実装

class Dependencies {
    // map storing direct dependencies relationships
    private val directDependencies = mutableMapOf<String, MutableList<String>>()
    // map storing all dependencies including transitive ones
    private val allDependencies = mutableMapOf<String, MutableList<String>>()

    /**
     * add direct dependencies info to "directDependencies"
     */
    fun addDirect(file: String, dependencies: MutableList<String>) {
        directDependencies[file] = dependencies
    }

    /**
     * check all dependencies and return files depended by passed "file"
     */
    fun dependenciesFor(file: String): List<String> {
        checkDependencies()
        return allDependencies.getByKey(file)
    }

    /**
     * by referring "directDependencies", check all dependencies
     * including transitive ones and store them to "allDependencies"
     */
    private fun checkDependencies() {
        val tempMap = mutableMapOf<String, MutableList<String>>()
        // check "directDependencies" and record all dependencies info to "tempMap"
        directDependencies
                .forEach {
                    val list = mutableListOf<String>()
                    executeCheck(it.key, list)
                    tempMap[it.key] = list
                }
        // by referring "tempMap", non-duplicated and sorted dependencies info
        // is recorded to "allDependencies"
        tempMap.recordNonDuplicatedAndSortedInfo(allDependencies)
    }

    /**
     * execute dependencies check process recursively
     */
    private fun executeCheck(file: String, list: MutableList<String>) {
        try {
            directDependencies.getByKey(file).forEach {
                if (list.isCircular(it))
                    throw IllegalStateException("Circular dependencies detected for the file; $file")
                list.add(it)
                executeCheck(it, list)
            }
        } catch (e: IllegalArgumentException) {
            // when "IllegalArgumentException" occur, that means passed "file"
            // doesn't have any dependencies info on "directDependencies",
            // so we do nothing for that case but finishing recursive method call
        } catch (e: IllegalStateException) {
            // when "IllegalStateException" occur, that means passed "file" must have
            // circular dependencies as relationships, so we do nothing for that case
            // but finishing recursive method call
        }
    }

    companion object {
        /**
         * if dependencies relationship is being circular or not
         */
        private fun MutableList<String>.isCircular(file: String): Boolean =
                this.contains(file)

        /**
         * get value by key assuring return type is "List<String>", not "List<String>?"
         */
        private fun MutableMap<String, MutableList<String>>.getByKey(key: String): List<String> {
            return this[key] ?: throw IllegalArgumentException("invalid item passed: $key")
        }

        /**
         * record info of "this" to passed "dependenciesMap" in non-duplicated and sorted form
         */
        private fun MutableMap<String, MutableList<String>>.recordNonDuplicatedAndSortedInfo(
                dependenciesMap: MutableMap<String, MutableList<String>>) {
            this.forEach {
                val values = it.value.toSet().toMutableList()
                values.sort()
                dependenciesMap[it.key] = values
            }
        }
    }
}

directDependenciesにaddDirectを通して引き渡された直接依存の関係をMapとして記録します。あるファイルについて全依存関係を取得するにはdependenciesForを呼び出すことになりますが、このメソッド内でcheckDependenciesを呼び出して実際の依存関係算出処理を行うことにします。算出された各ファイルのついての全依存関係はMapであるallDependenciesに記録され、引数として渡されるfileをkeyとすることで対象ファイルの全依存関係を取得することができます。

依存関係算出処理はcheckDependenciesとそこで呼び出されるexecuteCheckで行われています。checkDependenciesで直接依存を記録しているdirectDependenciesの各要素に対してexecuteCheckを呼び出しています。executeCheckは再帰的に実装をしていて、起点となるファイルに対する全ての依存関係を引数で渡されるlistに記録します。

executeCheckでは例外ハンドリングを2箇所記述しています。

• IllegalArgumentException
• 再帰的に呼び出されたexecuteCheckが依存関係を見にいった際に対象となるファイルが存在しなかった場合をハンドル
• IllegalStateException
• 依存関係が循環してしまっている場合をハンドル

想定されている例外であることも踏まえて、両ケースの例外が発生した場合には再帰処理の終了のみ行うようにしてます。

そのようにして算出された全依存関係を一旦tempMapに記録し、依存先ファイルの重複記述を排除・アルファベット順でのソートを適応したものをallDependenciesにMapとして記録します。

テスト

それではテストケースを整備してアルゴリズムが意図通り動作しているか確認してみます。テストケースは2つ用意していて、1つ目はブログ内で提示されていたテストケース、2つ目はブログ終盤で紹介されている循環依存を伴うケースです。

class DependenciesTest {
    @Test
    fun testDependencies() {
        val dep = Dependencies()
        dep.addDirect("A", mutableListOf("B", "C"))
        dep.addDirect("B", mutableListOf("C", "E"))
        dep.addDirect("C", mutableListOf("G"))
        dep.addDirect("D", mutableListOf("A", "F") )
        dep.addDirect("E", mutableListOf("F"))
        dep.addDirect("F", mutableListOf("H"))

        assertEquals(mutableListOf("B", "C", "E", "F", "G", "H"), dep.dependenciesFor("A"))
        assertEquals(mutableListOf("C", "E", "F", "G", "H"), dep.dependenciesFor("B"))
        assertEquals(mutableListOf("G"), dep.dependenciesFor("C"))
        assertEquals(mutableListOf("A", "B", "C", "E", "F", "G", "H"), dep.dependenciesFor("D"))
        assertEquals(mutableListOf("F", "H"), dep.dependenciesFor("E"))
        assertEquals(mutableListOf("H"), dep.dependenciesFor("F"))
    }

    @Test
    fun testCircularDependencies() {
        val dep = Dependencies()
        dep.addDirect("A", mutableListOf("B"))
        dep.addDirect("B", mutableListOf("C"))
        dep.addDirect("C", mutableListOf("A"))

        assertEquals(mutableListOf("A", "B", "C"), dep.dependenciesFor("A"))
        assertEquals(mutableListOf("A", "B", "C"), dep.dependenciesFor("B"))
        assertEquals(mutableListOf("A", "B", "C"), dep.dependenciesFor("C"))
    }
}

無事全てのケースを通過し、意図通りにプログラムが動いていることを確認できました！

まとめ

今回の課題も楽しんで実装することができました。実際の記述に関して、「この部分をこう書けばもっと可読性・保守性・拡張性を担保できるよ」といったご指摘がございましたら是非是非コメントにて宜しくお願いいたします。

お読みいただきまして、ありがとうございました！

関連記事一覧

• CodeKataをKotlinでやってみた 〜Karate Chop編〜
• CodeKataをKotlinでやってみた 〜Data Munging編〜
• [CodeKataをKotlinでやってみた 〜Bloom Filters編〜]
  (https://qiita.com/Takuyaaaa/items/eaa3848bce3bccdd946f)
• [CodeKataをKotlinでやってみた 〜Anagrams編〜]
  (https://qiita.com/Takuyaaaa/items/df06e24e6f2c7f8ced35)
• [CodeKataをKotlinでやってみた 〜Checkout編〜]
  (https://qiita.com/Takuyaaaa/items/0a4b82e30c977444c0bc)
• [CodeKataをKotlinでやってみた 〜Sorting it Out編〜]
  (https://qiita.com/Takuyaaaa/items/b5210c53bff3ff5f0512)
• [CodeKataをKotlinでやってみた 〜Counting Code Lines編〜]
  (https://qiita.com/Takuyaaaa/items/cb9143fbcb9e0b2a7822)
• [CodeKataをKotlinでやってみた 〜Tom Swift Under the Milkwood編〜]
  (https://qiita.com/Takuyaaaa/items/feccf69d2b9d95196a72)
• [CodeKataをKotlinでやってみた 〜Transitive Dependencies編〜]
  (https://qiita.com/Takuyaaaa/items/9b43473b8feffe1ce9f7)
• [CodeKataをKotlinでやってみた 〜Word Chains編〜]
  (https://qiita.com/Takuyaaaa/items/2539338252ad7e19ba18)
• [CodeKataをKotlinでやってみた 〜Simple Lists編〜]
  (https://qiita.com/Takuyaaaa/items/36ef73522bfe8d054448)