#![cfg_attr(test, feature(plugin))]
#![cfg_attr(test, plugin(clippy))]
#![cfg_attr(feature = "nightly", feature(never_type))]

#[cfg(feature = "nightly")]
type Nothing = !;

/// Represents that no value is ever pushed out on a push.
///
/// Currently, the `!` type is only available on nightly. As a result, when the `nightly` feature
/// isn't enabled, this enum is used in place of `!` to represent that no object can ever be pushed
/// out when a push happens.
#[cfg(not(feature = "nightly"))]
pub enum Nothing {}

use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, LinkedList, VecDeque};
use std::hash::Hash;

/// A mutable collection onto which items can be added to an arbitrary location in the collection.
pub trait Push<T> {
    /// Type of value that gets pushed out, if any.
    ///
    /// For some collections, a value may be "pushed out" after a value is pushed.
    type PushedOut;

    /// Adds the value to the collection.
    fn push(&mut self, val: T) -> Option<Self::PushedOut>;
}

/// A mutable collection onto which items can be added "at the beginning."
///
/// "At the beginning" is defined in a way such that truncating the collection to the item's length
/// after a push will retain the item.
pub trait PushFront<T>: Push<T> {
    /// Adds the value to the front of the collection.
    fn push_front(&mut self, val: T) -> Option<Self::PushedOut>;
}

/// A mutable collection onto which items can be added "at the end."
///
/// "At the end" is defined in a way such that truncating the collection down by the item's length
/// after a push will remove the item.
pub trait PushBack<T>: Push<T> {
    /// Adds the value to the back of the collection.
    fn push_back(&mut self, val: T) -> Option<Self::PushedOut>;
}

/// Alternative to `Push<&T>`.
pub trait PushRef<T: ?Sized> {
    /// Type of value that gets pushed out, if any.
    type PushedOut;

    /// Adds the value to the collection.
    fn push_ref(&mut self, val: &T) -> Option<Self::PushedOut>;
}

/// Alternative to `PushFront<&T>`.
pub trait PushRefFront<T: ?Sized>: PushRef<T> {
    /// Adds the value to the front of the collection.
    fn push_ref_front(&mut self, val: &T) -> Option<Self::PushedOut>;
}

/// Alternative to `PushBack<&T>`.
pub trait PushRefBack<T: ?Sized>: PushRef<T> {
    /// Adds the value to the back of the collection.
    fn push_ref_back(&mut self, val: &T) -> Option<Self::PushedOut>;
}

/// Represents a pushed value that has been dropped.
///
/// Some collections do not actually push a value if another value exists in this place. These
/// collections will return `Some(PushedVal)` to represent that, even though the pushed value was
/// dropped, it was "pushed out" instead of being pushed.
pub struct PushedVal;

impl<K: Ord, V> Push<(K, V)> for BTreeMap<K, V> {
    type PushedOut = V;
    fn push(&mut self, (key, val): (K, V)) -> Option<V> {
        BTreeMap::insert(self, key, val)
    }
}

impl<T: Ord> Push<T> for BTreeSet<T> {
    type PushedOut = PushedVal;
    fn push(&mut self, val: T) -> Option<PushedVal> {
        if BTreeSet::insert(self, val) {
            None
        } else {
            Some(PushedVal)
        }
    }
}

impl<T: Ord> Push<T> for BinaryHeap<T> {
    type PushedOut = Nothing;
    fn push(&mut self, val: T) -> Option<Nothing> {
        BinaryHeap::push(self, val);
        None
    }
}

impl<K: Hash + Eq, V> Push<(K, V)> for HashMap<K, V> {
    type PushedOut = V;
    fn push(&mut self, (key, val): (K, V)) -> Option<V> {
        HashMap::insert(self, key, val)
    }
}

impl<T: Hash + Eq> Push<T> for HashSet<T> {
    type PushedOut = PushedVal;
    fn push(&mut self, val: T) -> Option<PushedVal> {
        if HashSet::insert(self, val) {
            None
        } else {
            Some(PushedVal)
        }
    }
}

impl<T> Push<T> for LinkedList<T> {
    type PushedOut = Nothing;
    fn push(&mut self, val: T) -> Option<Nothing> {
        LinkedList::push_back(self, val);
        None
    }
}

impl<T> Push<LinkedList<T>> for LinkedList<T> {
    type PushedOut = Nothing;
    fn push(&mut self, mut val: LinkedList<T>) -> Option<Nothing> {
        LinkedList::append(self, &mut val);
        None
    }
}

impl Push<char> for String {
    type PushedOut = Nothing;
    fn push(&mut self, val: char) -> Option<Nothing> {
        String::push(self, val);
        None
    }
}

impl PushRef<str> for String {
    type PushedOut = Nothing;
    fn push_ref(&mut self, val: &str) -> Option<Nothing> {
        String::push_str(self, val);
        None
    }
}

impl<T> Push<T> for Vec<T> {
    type PushedOut = Nothing;
    fn push(&mut self, val: T) -> Option<Nothing> {
        Vec::push(self, val);
        None
    }
}

impl<T: Clone> PushRef<[T]> for Vec<T> {
    type PushedOut = Nothing;
    fn push_ref(&mut self, val: &[T]) -> Option<Nothing> {
        Vec::extend_from_slice(self, val);
        None
    }
}

impl<T> Push<T> for VecDeque<T> {
    type PushedOut = Nothing;
    fn push(&mut self, val: T) -> Option<Nothing> {
        VecDeque::push_back(self, val);
        None
    }
}

impl<T> PushFront<T> for LinkedList<T> {
    fn push_front(&mut self, val: T) -> Option<Nothing> {
        LinkedList::push_front(self, val);
        None
    }
}

impl<T> PushBack<T> for LinkedList<T> {
    fn push_back(&mut self, val: T) -> Option<Nothing> {
        LinkedList::push_back(self, val);
        None
    }
}

impl<T> PushFront<LinkedList<T>> for LinkedList<T> {
    fn push_front(&mut self, mut val: LinkedList<T>) -> Option<Nothing> {
        LinkedList::append(&mut val, self);
        *self = val;
        None
    }
}

impl<T> PushBack<LinkedList<T>> for LinkedList<T> {
    fn push_back(&mut self, mut val: LinkedList<T>) -> Option<Nothing> {
        LinkedList::append(self, &mut val);
        None
    }
}

impl PushBack<char> for String {
    fn push_back(&mut self, val: char) -> Option<Nothing> {
        String::push(self, val);
        None
    }
}

impl PushRefBack<str> for String {
    fn push_ref_back(&mut self, val: &str) -> Option<Nothing> {
        String::push_str(self, val);
        None
    }
}

impl<T> PushBack<T> for Vec<T> {
    fn push_back(&mut self, val: T) -> Option<Nothing> {
        Vec::push(self, val);
        None
    }
}

impl<T: Clone> PushRefBack<[T]> for Vec<T> {
    fn push_ref_back(&mut self, val: &[T]) -> Option<Nothing> {
        Vec::extend_from_slice(self, val);
        None
    }
}

impl<T> PushFront<T> for VecDeque<T> {
    fn push_front(&mut self, val: T) -> Option<Nothing> {
        VecDeque::push_front(self, val);
        None
    }
}

impl<T> PushBack<T> for VecDeque<T> {
    fn push_back(&mut self, val: T) -> Option<Nothing> {
        VecDeque::push_back(self, val);
        None
    }
}