diff options
author | Li Haoyi <haoyi.sg@gmail.com> | 2018-02-09 00:14:47 -0800 |
---|---|---|
committer | Li Haoyi <haoyi.sg@gmail.com> | 2018-02-09 08:17:47 -0800 |
commit | 8ddd2fa054bc8639c28db2e95b7903e2954fdb7d (patch) | |
tree | aa985f1e715f07eb279e6facad61de8a187e316c /main/test/src/mill/eval/TarjanTests.scala | |
parent | 90d0a3388d280554eaa51371f666d2f7a965a8af (diff) | |
download | mill-8ddd2fa054bc8639c28db2e95b7903e2954fdb7d.tar.gz mill-8ddd2fa054bc8639c28db2e95b7903e2954fdb7d.tar.bz2 mill-8ddd2fa054bc8639c28db2e95b7903e2954fdb7d.zip |
.
Diffstat (limited to 'main/test/src/mill/eval/TarjanTests.scala')
-rw-r--r-- | main/test/src/mill/eval/TarjanTests.scala | 91 |
1 files changed, 91 insertions, 0 deletions
diff --git a/main/test/src/mill/eval/TarjanTests.scala b/main/test/src/mill/eval/TarjanTests.scala new file mode 100644 index 00000000..2f9d0a4d --- /dev/null +++ b/main/test/src/mill/eval/TarjanTests.scala @@ -0,0 +1,91 @@ +package mill.eval + +import utest._ + +object TarjanTests extends TestSuite{ + def check(input: Seq[Seq[Int]], expected: Seq[Seq[Int]]) = { + val result = Tarjans(input).map(_.sorted) + val sortedExpected = expected.map(_.sorted) + assert(result == sortedExpected) + } + val tests = Tests{ + // + 'empty - check(Seq(), Seq()) + + // (0) + 'singleton - check(Seq(Seq()), Seq(Seq(0))) + + + // (0)-. + // ^._/ + 'selfCycle - check(Seq(Seq(0)), Seq(Seq(0))) + + // (0) <-> (1) + 'simpleCycle- check(Seq(Seq(1), Seq(0)), Seq(Seq(1, 0))) + + // (0) (1) (2) + 'multipleSingletons - check( + Seq(Seq(), Seq(), Seq()), + Seq(Seq(0), Seq(1), Seq(2)) + ) + + // (0) -> (1) -> (2) + 'straightLineNoCycles- check( + Seq(Seq(1), Seq(2), Seq()), + Seq(Seq(2), Seq(1), Seq(0)) + ) + + // (0) <- (1) <- (2) + 'straightLineNoCyclesReversed- check( + Seq(Seq(), Seq(0), Seq(1)), + Seq(Seq(0), Seq(1), Seq(2)) + ) + + // (0) <-> (1) (2) -> (3) -> (4) + // ^.____________/ + 'independentSimpleCycles - check( + Seq(Seq(1), Seq(0), Seq(3), Seq(4), Seq(2)), + Seq(Seq(1, 0), Seq(4, 3, 2)) + ) + + // ___________________ + // v \ + // (0) <-> (1) (2) -> (3) -> (4) + // ^.____________/ + 'independentLinkedCycles - check( + Seq(Seq(1), Seq(0), Seq(3), Seq(4), Seq(2, 1)), + Seq(Seq(1, 0), Seq(4, 3, 2)) + ) + // _____________ + // / v + // (0) <-> (1) (2) -> (3) -> (4) + // ^.____________/ + 'independentLinkedCycles2 - check( + Seq(Seq(1, 2), Seq(0), Seq(3), Seq(4), Seq(2)), + Seq(Seq(4, 3, 2), Seq(1, 0)) + ) + + // _____________ + // / v + // (0) <-> (1) (2) -> (3) -> (4) + // ^. ^.____________/ + // \________________/ + 'combinedCycles - check( + Seq(Seq(1, 2), Seq(0), Seq(3), Seq(4), Seq(2, 1)), + Seq(Seq(4, 3, 2, 1, 0)) + ) + // + // (0) <-> (1) <- (2) <- (3) <-> (4) <- (5) + // ^.____________/ / / + // / / + // (6) <- (7) <-/ (8) <-' + // / / + // v / + // (9) <--------' + 'combinedCycles - check( + Seq(Seq(1), Seq(0), Seq(0, 1), Seq(2, 4, 7, 9), Seq(3), Seq(4, 8), Seq(9), Seq(6), Seq(), Seq()), + Seq(Seq(0, 1), Seq(2), Seq(9), Seq(6), Seq(7), Seq(3, 4), Seq(8), Seq(5)) + ) + + } +}
\ No newline at end of file |