use len_trait::LenZero;

/// A mutable collection from which items can be removed from an arbitrary location in the collection.
///
/// Popping an item cannot *increase* the length of a collection if `Some` value is returned, and
/// must not change the length if `None` is returned. Additionally, the pop must take amortized O(1)
/// time and space to complete.
///
/// Returning `None` from the collection does not necessarily mean that no value was popped, just
/// that the desired type could not be popped off. One should inspect the `Len` of the type to check
/// if the container is truly empty.
pub trait Pop<T>: LenZero {
    /// Removes the value from the collection, if any exist.
    fn pop(&mut self) -> Option<T>;
}

/// A mutable collection from which items can be removed "at the beginning," retaining ordering.
pub trait PopFront<T>: Pop<T> {
    /// Removes the value from the front of the collection, if any exist.
    fn pop_front(&mut self) -> Option<T>;
}

/// A mutable collection from which items can be removed "at the end," retaining ordering
pub trait PopBack<T>: Pop<T> {
    /// Removes the value from the back of the collection, if any exist.
    fn pop_back(&mut self) -> Option<T>;
}

/// A mutable collection from which the largest-value item can be removed.
///
/// Unlike `Pop<T>` implementations, `PopLargest<T>` implementations may take amortized O(log n)
/// time and O(1) space with respect to the length of the collection.
pub trait PopLargest<T> {
    /// Removes the largest value from the collection, if any exist.
    fn pop_largest(&mut self) -> Option<T>;
}

/// A mutable collection from which the smallest-value item can be removed.
///
/// Unlike `Pop<T>` implementations, `PopSmallest<T>` implementations may take amortized O(log n)
/// time and O(1) space with respect to the length of the collection.
pub trait PopSmallest<T> {
    /// Removes the smallest value from the collection, if any exist.
    fn pop_smallest(&mut self) -> Option<T>;
}