use std::cmp;
use std::collections::{BTreeSet, HashMap, HashSet};

type Float = f64;

#[derive(Debug, Clone, Copy)]
struct Probability(Float);

#[derive(Debug, PartialEq, Eq)]
enum ProbabilityError {
    Malformed,
    OutOfRange,
}

impl Probability {
    fn try_new(inner: Float) -> Result<Self, ProbabilityError> {
        use ProbabilityError::*;

        if inner.is_nan() || inner.is_infinite() {
            return Err(Malformed);
        }

        if inner < 0.0 || inner > 1.0 {
            return Err(OutOfRange);
        }

        Ok(Probability(inner))
    }
}

impl cmp::PartialEq for Probability {
    fn eq(&self, other: &Self) -> bool {
        self.0 == other.0
    }
}

impl cmp::Eq for Probability {}

impl cmp::Ord for Probability {
    fn cmp(&self, other: &Self) -> cmp::Ordering {
        self.0.partial_cmp(&other.0).unwrap()
    }
}

impl cmp::PartialOrd for Probability {
    fn partial_cmp(&self, other: &Self) -> Option<cmp::Ordering> {
        Some(self.cmp(&other))
    }
}

impl std::ops::Mul for Probability {
    type Output = Self;
    fn mul(self, rhs: Self) -> Self {
        Probability(self.0 * rhs.0)
    }
}

type Idx = usize;

fn min_max((a, b): (Idx, Idx)) -> (Idx, Idx) {
    if a < b {
        (a, b)
    } else {
        (b, a)
    }
}

#[derive(Default, Debug)]
struct ProbGraph {
    edges: HashMap<(Idx, Idx), Probability>,
    neighbors_set: HashMap<Idx, HashSet<Idx>>,
}

impl ProbGraph {
    fn insert_edge(&mut self, edge: (Idx, Idx, Probability)) {
        let no_neighbors = || HashSet::new();

        let (idx1, idx2, prob) = edge;
        let idx_pair = min_max((idx1, idx2));

        self.edges.insert(idx_pair, prob);
        self.neighbors_set
            .entry(idx1)
            .or_insert_with(no_neighbors)
            .insert(idx2);
        self.neighbors_set
            .entry(idx2)
            .or_insert_with(no_neighbors)
            .insert(idx1);
    }

    fn get_probability(&self, edge: (Idx, Idx)) -> Option<Probability> {
        self.edges.get(&min_max(edge)).cloned()
    }

    fn get_neighbors(&self, vertex: Idx) -> Option<&HashSet<Idx>> {
        self.neighbors_set.get(&vertex)
    }

    fn visit(&mut self, vertex: Idx) {
        if let Some(neighbors) = self.neighbors_set.remove(&vertex) {
            for neighbor in neighbors {
                self.neighbors_set.entry(neighbor).and_modify(|set| {set.remove(&vertex);});
            }
        }
    }
}

#[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Clone)]
struct ProbabilityTo(Probability, Idx);

type ProbabilityHeap = BTreeSet<ProbabilityTo>;

trait FetchMax {
    type Item;
    fn get_max(&self) -> Option<&Self::Item>;
    fn fetch_max(&mut self) -> Option<Self::Item>;
}

impl FetchMax for ProbabilityHeap {
    type Item = ProbabilityTo;

    fn get_max(&self) -> Option<&Self::Item> {
        self.range(..).rev().next()
    }

    fn fetch_max(&mut self) -> Option<Self::Item> {
        self.get_max().cloned().map(|max| {
            self.remove(&max);
            max
        })
    }
}

fn max_survivability(edges: &[(Idx, Idx, Float)]) -> Probability {
    if edges.is_empty() {
        panic!("max_survivability: input is empty");
    }

    let never = Probability::try_new(0.0).unwrap();
    let always = Probability::try_new(1.0).unwrap();

    let mut start = Idx::max_value();
    let mut end = Idx::min_value();
    let mut graph = ProbGraph::default();
    let mut candidates = ProbabilityHeap::new();
    let mut probabilities = HashMap::new();

    for (i, &(from, to, float)) in edges.iter().enumerate() {
        if from == to {
            panic!("max_survivability: found loop at {}: both indices are {}",
            i,
            from);
        }

        let prob = Probability::try_new(float)
            .unwrap_or_else(|err| {
                panic!("max_survivability: failed to convert {} at {} into probability: {:?}",
                float,
                i,
                err)
        });

        graph.insert_edge((from, to, prob));
        candidates.insert(ProbabilityTo(never, from));
        candidates.insert(ProbabilityTo(never, to));

        start = start.min(from);
        end = end.max(to);

        probabilities.insert(from, never);
        probabilities.insert(to,   never);
    }

    probabilities.insert(start, always);
    candidates.remove(&ProbabilityTo(never, start));
    candidates.insert(ProbabilityTo(always, start));

    while let Some(ProbabilityTo(prob, idx)) = candidates.fetch_max() {
        for &neighbor in graph.get_neighbors(idx).unwrap() {
            let new = graph.get_probability((idx, neighbor)).unwrap() * prob;
            let old = probabilities[&neighbor];
            if new > old {
                candidates.remove(&ProbabilityTo(old, neighbor));
                candidates.insert(ProbabilityTo(new, neighbor));
                *probabilities.get_mut(&neighbor).unwrap() = new;
            }
        }

        graph.visit(idx);
        println!();
    }

    probabilities[&end]
}

fn main() {
    println!("{}", max_survivability(&[(0, 1, 0.5), (1, 2, 0.5)]).0); //0.25
    println!("{}", max_survivability(&[(0, 1, 0.5), (1, 2, 0.5), (0, 2, 0.7)]).0); //0.7
}