blob: 30f7b8033a6f646a095f49a84b33805016890c51 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
|
// SPDX-License-Identifier: Apache-2.0
package firrtlTests.graph
import firrtl.graph._
import firrtl.testutils._
class EulerTourTests extends FirrtlFlatSpec {
val top = "top"
val first_layer = Set("1a", "1b", "1c")
val second_layer = Set("2a", "2b", "2c")
val third_layer = Set("3a", "3b", "3c")
val last_null = Set.empty[String]
val m = Map(top -> first_layer) ++ first_layer.map {
case x => Map(x -> second_layer)
}.flatten.toMap ++ second_layer.map {
case x => Map(x -> third_layer)
}.flatten.toMap ++ third_layer.map {
case x => Map(x -> last_null)
}.flatten.toMap
val graph = DiGraph(m)
val instances = graph.pathsInDAG(top).values.flatten
val tour = EulerTour(graph, top)
it should "show equivalency of Berkman--Vishkin and naive RMQs" in {
instances.toSeq.combinations(2).toList.map {
case Seq(a, b) =>
tour.rmqNaive(a, b) should be(tour.rmqBV(a, b))
}
}
it should "determine naive RMQs of itself correctly" in {
instances.toSeq.map { case a => tour.rmqNaive(a, a) should be(a) }
}
it should "determine Berkman--Vishkin RMQs of itself correctly" in {
instances.toSeq.map { case a => tour.rmqNaive(a, a) should be(a) }
}
}
|
