Noober

Cargo.toml

[package]
name = "noober"
version = "0.0.1"
authors = ["Jani Rahkola <jani.rahkola@iki.fi>"]

[[bin]]
name = "noober"

[dependencies]
rustc-serialize = "0.1.0"

main.rs

#![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));
}