blob: 0b69ce61db8bce50df00a65b1a6a7089747a426b (
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
|
package firrtlTests.graph
import firrtl.graph._
import firrtlTests._
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) }
}
}
|
