Skip to content

Instantly share code, notes, and snippets.

@rahcola rahcola/Cargo.toml
Last active Aug 29, 2015

Embed
What would you like to do?
Noober
[package]
name = "noober"
version = "0.0.1"
authors = ["Jani Rahkola <jani.rahkola@iki.fi>"]
[[bin]]
name = "noober"
[dependencies]
rustc-serialize = "0.1.0"
#![feature(slicing_syntax)]
extern crate rustc;
extern crate "rustc-serialize" as rustc_serialize;
use rustc::middle::graph::{Graph, NodeIndex};
use rustc_serialize::{json, Encodable, Encoder};
use std::collections::{BinaryHeap, VecMap};
use std::num::{Int, UnsignedInt};
use std::io;
#[deriving(RustcDecodable, Show)]
struct Journey {
from: uint,
to: uint,
route: Option<Vec<uint>>,
}
impl<S: Encoder<E>, E> Encodable<S, E> for Journey {
fn encode(&self, s: &mut S) -> Result<(), E> {
s.emit_struct("Journey", 0, |s| {
try!(s.emit_struct_field("from", 0, |s| { s.emit_uint(self.from) }));
try!(s.emit_struct_field("to", 1, |s| { s.emit_uint(self.to) }));
match self {
&Journey{route: Some(ref v), ..}
=> s.emit_struct_field("route", 2, |s| { v.encode(s) }),
_ => Ok(()),
}
})
}
}
fn dijkstra<N, E: UnsignedInt>(graph: &Graph<N, E>,
from: NodeIndex,
to: NodeIndex) -> Option<Vec<NodeIndex>> {
#[deriving(PartialEq)]
struct State<T>((NodeIndex, T));
impl<T: UnsignedInt> Eq for State<T> {}
impl<T: UnsignedInt> Ord for State<T> {
fn cmp(&self, &State(ref other): &State<T>) -> Ordering {
let &State(ref me) = self;
other.1.cmp(&me.1)
}
}
impl<T: UnsignedInt> PartialOrd for State<T> {
fn partial_cmp(&self, other: &State<T>) -> Option<Ordering> {
Some(self.cmp(other))
}
}
let mut distance: VecMap<E> = VecMap::new();
let mut path: VecMap<NodeIndex> = VecMap::new();
let mut unvisited: BinaryHeap<State<E>> = BinaryHeap::new();
distance.insert(from.node_id(), Int::zero());
path.insert(from.node_id(), from);
unvisited.push(State((from, Int::zero())));
while let Some(State((node, d))) = unvisited.pop() {
if node == to {
let mut route = Vec::new();
let mut next = node;
while next != from {
route.push(next);
next = path[next.node_id()];
}
route.push(from);
route.reverse();
return Some(route);
}
graph.each_outgoing_edge(node, |_, e| {
let to = e.target();
let alt_distance = d + e.data;
match distance.remove(&to.node_id()) {
Some(ref old_distance) if *old_distance <= alt_distance => {
distance.insert(to.node_id(), *old_distance);
},
_ => {
distance.insert(to.node_id(), alt_distance);
path.insert(to.node_id(), node);
unvisited.push(State((to, alt_distance)));
},
}
true
});
}
None
}
fn plan(graph: &Graph<uint, uint>,
index: &VecMap<NodeIndex>,
journey: &Journey) -> Option<Journey> {
match journey {
&Journey{from, to, route: None}
=> dijkstra(graph, index[from], index[to])
.map(|v| v.map_in_place(|i| *graph.node_data(i)))
.and_then(|v| Some(Journey{from: from, to: to, route: Some(v)})),
_ => None,
}
}
fn read_graph(s: &str) -> Result<(Graph<uint, uint>, VecMap<NodeIndex>), json::DecoderError> {
#[deriving(RustcDecodable)]
struct Edge {
from: uint,
to: uint,
weight: uint,
}
let mut graph = Graph::new();
let mut index = VecMap::new();
let edges = try!(json::decode::<Vec<Edge>>(s));
for &Edge{from, to, weight} in edges.iter() {
if !index.contains_key(&from) {
index.insert(from, graph.add_node(from));
}
if !index.contains_key(&to) {
index.insert(to, graph.add_node(to));
}
graph.add_edge(index[from], index[to], weight);
}
Ok((graph, index))
}
fn read_journeys(s: &str) -> Result<Vec<Journey>, json::DecoderError> {
Ok(try!(json::decode(s)))
}
fn file_as_string(path: &str) -> Result<String, io::IoError> {
Ok(try!(io::File::open(&Path::new(path)).read_to_string()))
}
fn main() {
let (g, i) = read_graph(file_as_string("graph.json").unwrap()[]).unwrap();
let js = read_journeys(file_as_string("journeys.json").unwrap()[]).unwrap();
let r: Vec<Journey> = js.into_iter().map(|journey| {
match plan(&g, &i, &journey) {
Some(p) => p,
None => journey,
}
}).collect();
println!("{}", json::encode(&r));
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.