use len_trait::{LenZero, CapacityMut};

/// A mutable collection onto which items can be added to an arbitrary location in the collection.
///
/// Pushing an item must never *decrease* the length of a collection, and it usually increases it.
/// Additionally, the push must take amortized O(n) time and space to complete with respect to the
/// length of the pushed value.
pub trait Push<T>: LenZero {
    /// 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>;
}

/// A mutable collection onto which items can be added while retaining a sorting variant.
///
/// Unlike a regular `Push<T>` implementation, sorted pushes must take amortized O(m log n) time and
/// O(1) space, where m is the length of the pushed item and n is the length of the collection.
pub trait PushSorted<T> {
    /// Type of value that gets pushed out, if any.
    type PushedOut;

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

/// A mutable, ordered collection into which items can be inserted at an index.
///
/// Unlike a regular `Push<T>` implementation, insertions must take amortized O(n + m) time and
/// O(n + m) space, where m is the length of the pushed item and n is the length of the collection.
pub trait Insert<T>: PushBack<T> {
    /// Inserts the value at a position in the collection.
    fn insert(&mut self, index: usize, val: T) -> Option<Self::PushedOut>;
}

/// Alternative to `PushOrdered<&T>`.
pub trait InsertRef<T: ?Sized>: PushRefBack<T> {
    /// Inserts the value at a position in the collection.
    fn insert_ref(&mut self, index: usize, val: &T) -> Option<Self::PushedOut>;
}

/// Alternative to `Push<&mut T>`.
pub trait Append<T: ?Sized + CapacityMut>: PushBack<T> {
    /// Moves data out of `val` and into this collection.
    ///
    /// Invoking this method should make `val` empty while retaining its capacity.
    fn append(&mut self, val: &mut 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.
#[derive(Clone, Copy, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
pub struct PushedVal;