Created
February 22, 2013 19:58
-
-
Save docent666/5016135 to your computer and use it in GitHub Desktop.
Union find exercise - scala dojo 21st of Feb 2013
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package com.bulba.unionfind | |
trait CityMap { | |
def isConnected(from: Point, to: Point): Boolean | |
} | |
case class Point(name: String) { | |
def - (to: Point) = (this, to) | |
} | |
case class London(routes: Map[Point, Set[Point]]) extends CityMap { | |
def isConnected(from: Point, to: Point): Boolean = { | |
routes.getOrElse(from, Set()) contains to | |
} | |
} | |
object London { | |
def apply(routes: (Point, Point)) = { | |
new London(Map(routes._1, Set(routes._2))) | |
} | |
def apply(routes: List[(Point, Point)]) = { | |
// val m: Map[Point, Set[(Point,Point)]] = routes.groupBy(_._1) | |
// routes.foldLeft(Map[Point,Set[(Point, Point)]]())((map, (from, to)) => ) | |
// val m2: Map[Point, List[Point]] = for (p <- m) p -> p._2.map(_._2) | |
new London(routeMap) | |
} | |
} | |
object CityMapImplicits { | |
implicit def stringToPoint(s: String): Point = Point(s) | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package com.bulba.unionfind | |
import org.specs2.mutable.Specification | |
import com.bulba.unionfind.CityMapImplicits._ | |
class DisjointSetSpec extends Specification { | |
"Disjoint set spec" should { | |
"read a-b into a graph" in { | |
London("a" - "b").isConnected("a","b") must beTrue | |
} | |
"for a-b b is not connected to a" in { | |
London("a" - "b").isConnected("b","a") must beFalse | |
} | |
"for a-b,b-c a is connected to b and b is connected to c" in { | |
val london: Any = London(List("a" - "b", "b" - "c")) | |
london.isConnected("a","c") must beTrue | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Exercise was stopped at the stage of parsing the input data - as the last test states, London should allow a list of connections and rule that with so defined connections a and c would be connected. The apply methods in object London are broken - can you fix them?