#![allow(unused_assignments, unused_variables, dead_code)]
#![feature(fn_traits, unboxed_closures)]

use std::{
    cmp::Ordering,
    marker::PhantomData,
};

struct BinaryHeap<T, C>
where
    C: FnMut(&T, &T) -> Ordering,
{
    data: Vec<T>,
    cmp: C,
}

struct Max<T: Ord>(PhantomData<fn(&T, &T) -> Ordering>);

impl<T: Ord> Max<T> {
    pub fn new() -> Max<T> {
        Max(PhantomData)
    }
}

impl<'a, 'b, T: Ord> FnOnce<(&'a T, &'b T)> for Max<T> {
    type Output = Ordering;
    extern "rust-call" fn call_once(self, args: (&'a T, &'b T)) -> Ordering {
        T::cmp(args.0, args.1)
    }
}

impl<'a, 'b, T: Ord> FnMut<(&'a T, &'b T)> for Max<T> {
    extern "rust-call" fn call_mut(&mut self, args: (&'a T, &'b T)) -> Ordering {
        T::cmp(args.0, args.1)
    }
}

impl<'a, 'b, T: Ord> Fn<(&'a T, &'b T)> for Max<T> {
    extern "rust-call" fn call(&self, args: (&'a T, &'b T)) -> Ordering {
        T::cmp(args.0, args.1)
    }
}

struct Min<T: Ord>(PhantomData<fn(&T, &T) -> Ordering>);

impl<T: Ord> Min<T> {
    pub fn new() -> Min<T> {
        Min(PhantomData)
    }
}

impl<'a, 'b, T: Ord> FnOnce<(&'a T, &'b T)> for Min<T> {
    type Output = Ordering;
    extern "rust-call" fn call_once(self, args: (&'a T, &'b T)) -> Ordering {
        T::cmp(args.1, args.0)
    }
}

impl<'a, 'b, T: Ord> FnMut<(&'a T, &'b T)> for Min<T> {
    extern "rust-call" fn call_mut(&mut self, args: (&'a T, &'b T)) -> Ordering {
        T::cmp(args.1, args.0)
    }
}

impl<'a, 'b, T: Ord> Fn<(&'a T, &'b T)> for Min<T> {
    extern "rust-call" fn call(&self, args: (&'a T, &'b T)) -> Ordering {
        T::cmp(args.1, args.0)
    }
}

impl<T> BinaryHeap<T, fn(&T, &T) -> Ordering> {
    pub fn new() -> BinaryHeap<T, Max<T>>
    where
        T: Ord,
    {
        BinaryHeap {
            data: Vec::new(),
            cmp: Max(PhantomData),
        }
    }

    pub fn new_by<C>(cmp: C) -> BinaryHeap<T, C>
    where
        C: FnMut(&T, &T) -> Ordering,
    {
        BinaryHeap {
            data: Vec::new(),
            cmp,
        }
    }

    pub fn new_by_key<K, F>(mut f: F) -> BinaryHeap<T, impl FnMut(&T, &T) -> Ordering>
    where
        K: Ord,
        F: FnMut(&T) -> K,
    {
        BinaryHeap {
            data: Vec::new(),
            cmp: move |x, y| K::cmp(&f(x), &f(y)),
        }
    }

    pub fn with_capacity(capacity: usize) -> BinaryHeap<T, Max<T>>
    where
        T: Ord,
    {
        BinaryHeap {
            data: Vec::with_capacity(capacity),
            cmp: Max(PhantomData),
        }
    }

    pub fn with_capacity_by<C>(capacity: usize, cmp: C) -> BinaryHeap<T, C>
    where
        C: FnMut(&T, &T) -> Ordering,
    {
        BinaryHeap {
            data: Vec::with_capacity(capacity),
            cmp,
        }
    }

    pub fn with_capacity_by_key<K, F>(capacity: usize, mut f: F) -> BinaryHeap<T, impl FnMut(&T, &T) -> Ordering>
    where
        K: Ord,
        F: FnMut(&T) -> K,
    {
        BinaryHeap {
            data: Vec::with_capacity(capacity),
            cmp: move |x, y| K::cmp(&f(x), &f(y)),
        }
    }

    pub fn from(vec: Vec<T>) -> BinaryHeap<T, Max<T>>
    where
        T: Ord,
    {
        // TODO heapify data.
        BinaryHeap {
            data: vec,
            cmp: Max(PhantomData),
        }
    }

    pub fn from_by<C>(vec: Vec<T>, cmp: C) -> BinaryHeap<T, C>
    where
        C: FnMut(&T, &T) -> Ordering,
    {
        // TODO heapify data.
        BinaryHeap {
            data: vec,
            cmp,
        }
    }

    pub fn from_by_key<K, F>(vec: Vec<T>, mut f: F) -> BinaryHeap<T, impl FnMut(&T, &T) -> Ordering>
    where
        K: Ord,
        F: FnMut(&T) -> K,
    {
        // TODO heapify data.
        BinaryHeap {
            data: vec,
            cmp: move |x, y| K::cmp(&f(x), &f(y)),
        }
    }
}

impl<T, F> BinaryHeap<T, F>
where
    F: FnMut(&T, &T) -> Ordering,
{
    pub fn change_compare(&mut self, cmp: F) {
        // TODO heapify data.
        self.cmp = cmp;
    }

    pub fn peek(&self) -> Option<&T> {
        if self.data.len() > 0 {
            Some(&self.data[0])
        } else {
            None
        }
    }
}

fn main() {
    let heap = BinaryHeap::new();
    let value: Option<&usize> = heap.peek();

    let heap = BinaryHeap::new_by(Min::new());
    let value: Option<&usize> = heap.peek();

    let heap = BinaryHeap::new_by_key(|value| !0 - *value);
    let value: Option<&usize> = heap.peek();
}