//! A set based on splay tree.
use crate::iter;
use crate::tree_core;
use crate::vec_like;
use std::borrow::Borrow;
use std::cmp;
use std::iter::Peekable;
use std::ops;

/// A set based on splay tree.
///
/// A splay tree based set is a self-adjusting data structure.
/// It performs insertion, removal and look-up in `O(log n)` amortized time.
///
/// It is a logic error for a key to be modified in such a way that
/// the key's ordering relative to any other key,
/// as determined by the `Ord` trait, changes while it is in the map.
/// This is normally only possible through `Cell`, `RefCell`, global state, I/O, or unsafe code.
///
/// # Examples
/// ```
/// use splay_tree::SplaySet;
///
/// let mut set = SplaySet::new();
///
/// set.insert("foo");
/// set.insert("bar");
/// set.insert("baz");
/// assert_eq!(set.len(), 3);
///
/// assert!(set.contains("bar"));
/// assert!(set.remove("bar"));
/// assert!(!set.contains("bar"));
///
/// assert_eq!(vec!["baz", "foo"], set.into_iter().collect::<Vec<_>>());
/// ```
#[derive(Debug, Clone, Hash, PartialEq, Eq, PartialOrd, Ord)]
#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
pub struct SplaySet<T> {
    tree: tree_core::Tree<T, ()>,
}
impl<T> SplaySet<T>
where
    T: Ord,
{
    /// Makes a new SplaySet
    ///
    /// # Examples
    /// ```
    /// use splay_tree::SplaySet;
    ///
    /// let set: SplaySet<()> = SplaySet::new();
    /// assert!(set.is_empty());
    /// ```
    pub fn new() -> Self {
        SplaySet {
            tree: tree_core::Tree::new(),
        }
    }

    /// Clears the set, removing all values.
    ///
    /// # Examples
    /// ```
    /// use splay_tree::SplaySet;
    ///
    /// let mut set = SplaySet::new();
    /// set.insert("foo");
    /// set.clear();
    /// assert!(set.is_empty());
    /// ```
    pub fn clear(&mut self) {
        self.tree = tree_core::Tree::new();
    }

    /// Returns true if the set contains a value.
    ///
    /// The value may be any borrowed form of the set's value type,
    /// but the ordering on the borrowed form _must_ match the ordering on the value type.
    ///
    /// Because `SplaySet` is a self-adjusting amortized data structure,
    /// this function requires the `mut` qualifier for `self`.
    ///
    /// # Examples
    /// ```
    /// use splay_tree::SplaySet;
    ///
    /// let mut set = SplaySet::new();
    /// set.insert("foo");
    /// assert!(set.contains("foo"));
    /// assert!(!set.contains("bar"));
    /// ```
    pub fn contains<Q: ?Sized>(&mut self, value: &Q) -> bool
    where
        T: Borrow<Q>,
        Q: Ord,
    {
        self.tree.contains_key(value)
    }

    /// Immutable version of [`SplaySet::contains()`].
    ///
    /// Note that this method could be less efficient than the mutable version.
    ///
    /// # Examples
    /// ```
    /// use splay_tree::SplaySet;
    ///
    /// let mut set = SplaySet::new();
    /// set.insert("foo");
    /// assert!(set.contains_immut("foo"));
    /// assert!(!set.contains_immut("bar"));
    /// ```
    pub fn contains_immut<Q: ?Sized>(&self, value: &Q) -> bool
    where
        T: Borrow<Q>,
        Q: Ord,
    {
        self.tree.contains_key_immut(value)
    }

    /// Returns a reference to the value in the set, if any, that is equal to the given value.
    ///
    /// The value may be any borrowed form of the set's value type,
    /// but the ordering on the borrowed form _must_ match the ordering on the value type.
    ///
    /// Because `SplaySet` is a self-adjusting amortized data structure,
    /// this function requires the `mut` qualifier for `self`.
    ///
    /// # Examples
    /// ```
    /// use splay_tree::SplaySet;
    ///
    /// let mut set = SplaySet::new();
    /// set.insert("foo");
    /// assert_eq!(set.get("foo"), Some(&"foo"));
    /// assert_eq!(set.get("bar"), None);
    /// ```
    pub fn get<Q: ?Sized>(&mut self, value: &Q) -> Option<&T>
    where
        T: Borrow<Q>,
        Q: Ord,
    {
        if self.tree.get(value).is_some() {
            Some(&self.tree.root_ref().key)
        } else {
            None
        }
    }

    /// Immutable version of [`SplaySet::get()`].
    ///
    /// Note that this method could be less efficient than the mutable version.
    ///
    /// # Examples
    /// ```
    /// use splay_tree::SplaySet;
    ///
    /// let mut set = SplaySet::new();
    /// set.insert("foo");
    /// assert_eq!(set.get_immut("foo"), Some(&"foo"));
    /// assert_eq!(set.get_immut("bar"), None);
    /// ```
    pub fn get_immut<Q: ?Sized>(&self, value: &Q) -> Option<&T>
    where
        T: Borrow<Q>,
        Q: Ord,
    {
        self.tree.get_immut(value).map(|x| x.0)
    }

    /// Finds a minimum element which
    /// satisfies "greater than or equal to `value`" condition in the set.
    ///
    /// The value may be any borrowed form of the set's value type,
    /// but the ordering on the borrowed form _must_ match the ordering on the value type.
    ///
    /// # Examples
    /// ```
    /// use splay_tree::SplaySet;
    ///
    /// let mut set = SplaySet::new();
    /// set.insert(1);
    /// set.insert(3);
    ///
    /// assert_eq!(set.find_lower_bound(&0), Some(&1));
    /// assert_eq!(set.find_lower_bound(&1), Some(&1));
    /// assert_eq!(set.find_lower_bound(&4), None);
    /// ```
    pub fn find_lower_bound<Q: ?Sized>(&mut self, value: &Q) -> Option<&T>
    where
        T: Borrow<Q>,
        Q: Ord,
    {
        self.tree.find_lower_bound(value)
    }

    /// Immutable version of [`SplaySet::find_lower_bound()`].
    ///
    /// Note that this method could be less efficient than the mutable version.
    ///
    /// # Examples
    /// ```
    /// use splay_tree::SplaySet;
    ///
    /// let mut set = SplaySet::new();
    /// set.insert(1);
    /// set.insert(3);
    ///
    /// assert_eq!(set.find_lower_bound_immut(&0), Some(&1));
    /// assert_eq!(set.find_lower_bound_immut(&1), Some(&1));
    /// assert_eq!(set.find_lower_bound_immut(&4), None);
    /// ```
    pub fn find_lower_bound_immut<Q: ?Sized>(&self, value: &Q) -> Option<&T>
    where
        T: Borrow<Q>,
        Q: Ord,
    {
        self.tree.find_lower_bound_immut(value)
    }

    /// Finds a minimum element which satisfies "greater than `value`" condition in the set.
    ///
    /// The value may be any borrowed form of the set's value type,
    /// but the ordering on the borrowed form _must_ match the ordering on the value type.
    ///
    /// # Examples
    /// ```
    /// use splay_tree::SplaySet;
    ///
    /// let mut set = SplaySet::new();
    /// set.insert(1);
    /// set.insert(3);
    ///
    /// assert_eq!(set.find_upper_bound(&0), Some(&1));
    /// assert_eq!(set.find_upper_bound(&1), Some(&3));
    /// assert_eq!(set.find_upper_bound(&4), None);
    /// ```
    pub fn find_upper_bound<Q: ?Sized>(&mut self, value: &Q) -> Option<&T>
    where
        T: Borrow<Q>,
        Q: Ord,
    {
        self.tree.find_upper_bound(value)
    }

    /// Immutable version of [`SplaySet::find_upper_bound()`].
    ///
    /// Note that this method could be less efficient than the mutable version.
    ///
    /// # Examples
    /// ```
    /// use splay_tree::SplaySet;
    ///
    /// let mut set = SplaySet::new();
    /// set.insert(1);
    /// set.insert(3);
    ///
    /// assert_eq!(set.find_upper_bound_immut(&0), Some(&1));
    /// assert_eq!(set.find_upper_bound_immut(&1), Some(&3));
    /// assert_eq!(set.find_upper_bound_immut(&4), None);
    /// ```
    pub fn find_upper_bound_immut<Q: ?Sized>(&self, value: &Q) -> Option<&T>
    where
        T: Borrow<Q>,
        Q: Ord,
    {
        self.tree.find_upper_bound_immut(value)
    }

    /// Gets the minimum value in the map.
    ///
    /// # Examples
    /// ```
    /// use splay_tree::SplaySet;
    ///
    /// let mut set = SplaySet::new();
    /// set.insert(1);
    /// set.insert(3);
    ///
    /// assert_eq!(set.smallest(), Some(&1));
    /// ```
    pub fn smallest(&mut self) -> Option<&T> {
        self.tree.get_lftmost().map(|(v, _)| v)
    }

    /// Immutable version of [`SplaySet::smallest()`].
    ///
    /// Note that this method could be less efficient than the mutable version.
    ///
    /// # Examples
    /// ```
    /// use splay_tree::SplaySet;
    ///
    /// let mut set = SplaySet::new();
    /// set.insert(1);
    /// set.insert(3);
    ///
    /// assert_eq!(set.smallest_immut(), Some(&1));
    /// ```
    pub fn smallest_immut(&self) -> Option<&T> {
        self.tree.get_lftmost_immut().map(|(v, _)| v)
    }

    /// Takes the minimum value in the map.
    ///
    /// # Examples
    /// ```
    /// use splay_tree::SplaySet;
    ///
    /// let mut set = SplaySet::new();
    /// set.insert(1);
    /// set.insert(3);
    ///
    /// assert_eq!(set.take_smallest(), Some(1));
    /// assert_eq!(set.take_smallest(), Some(3));
    /// assert_eq!(set.take_smallest(), None);
    /// ```
    pub fn take_smallest(&mut self) -> Option<T> {
        self.tree.take_lftmost().map(|(v, _)| v)
    }

    /// Gets the maximum value in the map.
    ///
    /// # Examples
    /// ```
    /// use splay_tree::SplaySet;
    ///
    /// let mut set = SplaySet::new();
    /// set.insert(1);
    /// set.insert(3);
    ///
    /// assert_eq!(set.largest(), Some(&3));
    /// ```
    pub fn largest(&mut self) -> Option<&T> {
        self.tree.get_rgtmost().map(|(v, _)| v)
    }

    /// Immutable version of [`SplaySet::largest()`].
    ///
    /// Note that this method could be less efficient than the mutable version.
    ///
    /// # Examples
    /// ```
    /// use splay_tree::SplaySet;
    ///
    /// let mut set = SplaySet::new();
    /// set.insert(1);
    /// set.insert(3);
    ///
    /// assert_eq!(set.largest_immut(), Some(&3));
    /// ```
    pub fn largest_immut(&self) -> Option<&T> {
        self.tree.get_rgtmost_immut().map(|(v, _)| v)
    }

    /// Takes the maximum value in the map.
    ///
    /// # Examples
    /// ```
    /// use splay_tree::SplaySet;
    ///
    /// let mut set = SplaySet::new();
    /// set.insert(1);
    /// set.insert(3);
    ///
    /// assert_eq!(set.take_largest(), Some(3));
    /// assert_eq!(set.take_largest(), Some(1));
    /// assert_eq!(set.take_largest(), None);
    /// ```
    pub fn take_largest(&mut self) -> Option<T> {
        self.tree.take_rgtmost().map(|(v, _)| v)
    }

    /// Adds a value to the set.
    ///
    /// If the set did not have this value present, `true` is returned.
    ///
    /// If the set did have this value present, `false` is returned,
    /// and the entry is not updated.
    ///
    /// # Examples
    /// ```
    /// use splay_tree::SplaySet;
    ///
    /// let mut set = SplaySet::new();
    /// assert!(set.insert("foo"));
    /// assert!(!set.insert("foo"));
    /// assert_eq!(set.len(), 1);
    /// ```
    pub fn insert(&mut self, value: T) -> bool {
        self.tree.insert(value, ()).is_none()
    }

    /// Adds a value to the set, replacing the existing value, if any,
    /// that is equal to the given one.
    /// Returns the replaced value.
    ///
    /// # Examples
    /// ```
    /// use splay_tree::SplaySet;
    ///
    /// let mut set = SplaySet::new();
    /// assert_eq!(set.replace("foo"), None);
    /// assert_eq!(set.replace("foo"), Some("foo"));
    /// ```
    pub fn replace(&mut self, value: T) -> Option<T> {
        let old = self.take(&value);
        self.insert(value);
        old
    }

    /// Removes a value from the set. Returns `true` is the value was present in the set.
    ///
    /// The value may be any borrowed form of the set's value type,
    /// but the ordering on the borrowed form _must_ match the ordering on the value type.
    ///
    /// # Examples
    /// ```
    /// use splay_tree::SplaySet;
    ///
    /// let mut set = SplaySet::new();
    /// set.insert("foo");
    /// assert_eq!(set.remove("foo"), true);
    /// assert_eq!(set.remove("foo"), false);
    /// ```
    pub fn remove<Q: ?Sized>(&mut self, value: &Q) -> bool
    where
        T: Borrow<Q>,
        Q: Ord,
    {
        self.tree.remove(value).is_some()
    }

    /// Removes and returns the value in the set, if any, that is equal to the given one.
    ///
    /// The value may be any borrowed form of the set's value type,
    /// but the ordering on the borrowed form _must_ match the ordering on the value type.
    ///
    /// # Examples
    /// ```
    /// use splay_tree::SplaySet;
    ///
    /// let mut set = SplaySet::new();
    /// set.insert("foo");
    /// assert_eq!(set.take("foo"), Some("foo"));
    /// assert_eq!(set.take("foo"), None);
    /// ```
    pub fn take<Q: ?Sized>(&mut self, value: &Q) -> Option<T>
    where
        T: Borrow<Q>,
        Q: Ord,
    {
        if self.contains(value) {
            self.tree.pop_root().map(|(e, _)| e)
        } else {
            None
        }
    }

    /// Visits the values representing the difference, in ascending order.
    ///
    /// # Examples
    /// ```
    /// use splay_tree::SplaySet;
    ///
    /// let a: SplaySet<_> = vec![1, 2, 3].into_iter().collect();
    /// let b: SplaySet<_> = vec![2, 3, 4].into_iter().collect();
    ///
    /// assert_eq!(a.difference(&b).cloned().collect::<Vec<_>>(),
    ///            [1]);
    /// ```
    pub fn difference<'a>(&'a self, other: &'a Self) -> Difference<'a, T> {
        Difference(self.iter().peekable(), other.iter().peekable())
    }

    /// Visits the values representing the symmetric difference, in ascending order.
    ///
    /// # Examples
    /// ```
    /// use splay_tree::SplaySet;
    ///
    /// let a: SplaySet<_> = vec![1, 2, 3].into_iter().collect();
    /// let b: SplaySet<_> = vec![2, 3, 4].into_iter().collect();
    ///
    /// assert_eq!(a.symmetric_difference(&b).cloned().collect::<Vec<_>>(),
    ///            [1, 4]);
    /// ```
    pub fn symmetric_difference<'a>(&'a self, other: &'a Self) -> SymmetricDifference<'a, T> {
        SymmetricDifference(self.iter().peekable(), other.iter().peekable())
    }

    /// Visits the values representing the intersection, in ascending order.
    ///
    /// # Examples
    /// ```
    /// use splay_tree::SplaySet;
    ///
    /// let a: SplaySet<_> = vec![1, 2, 3].into_iter().collect();
    /// let b: SplaySet<_> = vec![2, 3, 4].into_iter().collect();
    ///
    /// assert_eq!(a.intersection(&b).cloned().collect::<Vec<_>>(),
    ///            [2, 3]);
    /// ```
    pub fn intersection<'a>(&'a self, other: &'a Self) -> Intersection<'a, T> {
        Intersection(self.iter().peekable(), other.iter().peekable())
    }

    /// Visits the values representing the union, in ascending order.
    ///
    /// # Examples
    /// ```
    /// use splay_tree::SplaySet;
    ///
    /// let a: SplaySet<_> = vec![1, 2, 3].into_iter().collect();
    /// let b: SplaySet<_> = vec![2, 3, 4].into_iter().collect();
    ///
    /// assert_eq!(a.union(&b).cloned().collect::<Vec<_>>(),
    ///            [1, 2, 3, 4]);
    /// ```
    pub fn union<'a>(&'a self, other: &'a Self) -> Union<'a, T> {
        Union(self.iter().peekable(), other.iter().peekable())
    }

    /// Returns `true` if the set has no elements in common with `other`.
    /// This is equivalent to checking for an empty intersection.
    ///
    /// # Examples
    /// ```
    /// use splay_tree::SplaySet;
    ///
    /// let a: SplaySet<_> = vec![1, 2, 3].into_iter().collect();
    /// let b: SplaySet<_> = vec![2, 3, 4].into_iter().collect();
    /// let c: SplaySet<_> = vec![4, 5, 6].into_iter().collect();
    ///
    /// assert!(!a.is_disjoint(&b));
    /// assert!(!b.is_disjoint(&c));
    /// assert!(a.is_disjoint(&c));
    /// assert!(c.is_disjoint(&a));
    /// ```
    pub fn is_disjoint(&self, other: &Self) -> bool {
        self.intersection(other).count() == 0
    }

    /// Returns `true` if the set is a subset of another.
    ///
    /// # Examples
    /// ```
    /// use splay_tree::SplaySet;
    ///
    /// let a: SplaySet<_> = vec![1, 2, 3].into_iter().collect();
    /// let b: SplaySet<_> = vec![2, 3, 4].into_iter().collect();
    /// let c: SplaySet<_> = vec![1, 2, 3, 4].into_iter().collect();
    ///
    /// assert!(!a.is_subset(&b));
    /// assert!(!b.is_subset(&a));
    /// assert!(!c.is_subset(&a));
    /// assert!(a.is_subset(&c));
    /// assert!(b.is_subset(&c));
    /// assert!(c.is_subset(&c));
    /// ```
    pub fn is_subset(&self, other: &Self) -> bool {
        self.difference(other).count() == 0
    }

    /// Returns `true` if the set is a superset of another.
    ///
    /// # Examples
    /// ```
    /// use splay_tree::SplaySet;
    ///
    /// let a: SplaySet<_> = vec![1, 2, 3].into_iter().collect();
    /// let b: SplaySet<_> = vec![2, 3, 4].into_iter().collect();
    /// let c: SplaySet<_> = vec![1, 2, 3, 4].into_iter().collect();
    ///
    /// assert!(!a.is_superset(&b));
    /// assert!(!b.is_superset(&a));
    /// assert!(!a.is_superset(&c));
    /// assert!(c.is_superset(&a));
    /// assert!(c.is_superset(&b));
    /// assert!(c.is_superset(&c));
    /// ```
    pub fn is_superset(&self, other: &Self) -> bool {
        other.is_subset(self)
    }

    /// Returns a vector like mutable view of the set.
    ///
    /// # Examples
    /// ```
    /// use splay_tree::SplaySet;
    ///
    /// let mut set = SplaySet::new();
    /// set.insert("foo");
    /// set.insert("bar");
    /// {
    ///     let mut vec = set.as_vec_like_mut();
    ///     vec.push("baz");
    ///
    ///     assert_eq!(vec.get(0), Some(&"foo"));
    ///     assert_eq!(vec.get(2), Some(&"baz"));
    ///
    ///     assert_eq!(vec.find_index(&"bar"), Some(1));
    ///
    ///     assert_eq!(vec.iter().cloned().collect::<Vec<_>>(),
    ///                ["foo", "bar", "baz"]);
    /// }
    /// assert_eq!(set.iter().cloned().collect::<Vec<_>>(),
    ///            ["bar", "baz", "foo"]);
    /// ```
    pub fn as_vec_like_mut(&mut self) -> VecLikeMut<T> {
        VecLikeMut::new(&mut self.tree)
    }
}
impl<T> SplaySet<T> {
    /// Returns the number of elements in the set.
    ///
    /// # Examples
    /// ```
    /// use splay_tree::SplaySet;
    ///
    /// let mut set = SplaySet::new();
    /// set.insert("foo");
    /// set.insert("bar");
    /// assert_eq!(set.len(), 2);
    /// ```
    pub fn len(&self) -> usize {
        self.tree.len()
    }

    /// Returns true if the set contains no elements.
    ///
    /// # Examples
    /// ```
    /// use splay_tree::SplaySet;
    ///
    /// let mut set = SplaySet::new();
    /// assert!(set.is_empty());
    ///
    /// set.insert("foo");
    /// assert!(!set.is_empty());
    ///
    /// set.clear();
    /// assert!(set.is_empty());
    /// ```
    pub fn is_empty(&self) -> bool {
        self.len() == 0
    }

    /// Gets an iterator over the SplaySet's contents, in sorted order.
    ///
    /// # Examples
    /// ```
    /// use splay_tree::SplaySet;
    ///
    /// let mut set = SplaySet::new();
    /// set.insert("foo");
    /// set.insert("bar");
    /// set.insert("baz");
    ///
    /// assert_eq!(set.iter().collect::<Vec<_>>(), [&"bar", &"baz", &"foo"]);
    /// ```
    pub fn iter(&self) -> Iter<T> {
        Iter::new(self)
    }

    /// Returns a vector like view of the set.
    ///
    /// # Examples
    /// ```
    /// use splay_tree::SplaySet;
    ///
    /// let mut set = SplaySet::new();
    /// set.insert("foo");
    /// set.insert("bar");
    /// {
    ///     let mut vec = set.as_vec_like();
    ///     assert_eq!(vec.get(0), Some(&"foo"));
    ///     assert_eq!(vec.get(1), Some(&"bar"));
    ///
    ///     assert_eq!(vec.iter().cloned().collect::<Vec<_>>(),
    ///                ["foo", "bar"]);
    /// }
    /// assert_eq!(set.iter().cloned().collect::<Vec<_>>(),
    ///            ["bar", "foo"]);
    /// ```
    pub fn as_vec_like(&self) -> VecLike<T> {
        VecLike::new(&self.tree)
    }
}
impl<T> Default for SplaySet<T>
where
    T: Ord,
{
    fn default() -> Self {
        SplaySet::new()
    }
}
impl<T> std::iter::FromIterator<T> for SplaySet<T>
where
    T: Ord,
{
    fn from_iter<I>(iter: I) -> Self
    where
        I: IntoIterator<Item = T>,
    {
        let mut set = SplaySet::new();
        for x in iter {
            set.insert(x);
        }
        set
    }
}
impl<T> IntoIterator for SplaySet<T> {
    type Item = T;
    type IntoIter = IntoIter<T>;
    fn into_iter(self) -> Self::IntoIter {
        IntoIter(self.tree.into_iter())
    }
}
impl<'a, T> IntoIterator for &'a SplaySet<T> {
    type Item = &'a T;
    type IntoIter = Iter<'a, T>;
    fn into_iter(self) -> Self::IntoIter {
        Iter::new(self)
    }
}
impl<T> Extend<T> for SplaySet<T>
where
    T: Ord,
{
    fn extend<I>(&mut self, iter: I)
    where
        I: IntoIterator<Item = T>,
    {
        for x in iter {
            self.insert(x);
        }
    }
}
impl<'a, T> Extend<&'a T> for SplaySet<T>
where
    T: Copy + 'a + Ord,
{
    fn extend<I>(&mut self, iter: I)
    where
        I: IntoIterator<Item = &'a T>,
    {
        for x in iter {
            self.insert(*x);
        }
    }
}
impl<'a, 'b, T> ops::Sub<&'b SplaySet<T>> for &'a SplaySet<T>
where
    T: Ord + Clone,
{
    type Output = SplaySet<T>;

    /// Returns the difference of `self` and `rhs` as a new `SplaySet<T>`.
    ///
    /// # Examples
    /// ```
    /// use splay_tree::SplaySet;
    ///
    /// let a: SplaySet<_> = vec![1, 2, 3].into_iter().collect();
    /// let b: SplaySet<_> = vec![3, 4, 5].into_iter().collect();
    ///
    /// assert_eq!((&a - &b).into_iter().collect::<Vec<_>>(),
    ///            [1, 2]);
    /// ```
    fn sub(self, rhs: &SplaySet<T>) -> SplaySet<T> {
        self.difference(rhs).cloned().collect()
    }
}
impl<'a, 'b, T> ops::BitXor<&'b SplaySet<T>> for &'a SplaySet<T>
where
    T: Ord + Clone,
{
    type Output = SplaySet<T>;

    /// Returns the symmetric difference of `self` and `rhs` as a new `SplaySet<T>`.
    ///
    /// # Examples
    /// ```
    /// use splay_tree::SplaySet;
    ///
    /// let a: SplaySet<_> = vec![1, 2, 3].into_iter().collect();
    /// let b: SplaySet<_> = vec![3, 4, 5].into_iter().collect();
    ///
    /// assert_eq!((&a ^ &b).into_iter().collect::<Vec<_>>(),
    ///            [1, 2, 4, 5]);
    /// ```
    fn bitxor(self, rhs: &SplaySet<T>) -> SplaySet<T> {
        self.symmetric_difference(rhs).cloned().collect()
    }
}
impl<'a, 'b, T> ops::BitAnd<&'b SplaySet<T>> for &'a SplaySet<T>
where
    T: Ord + Clone,
{
    type Output = SplaySet<T>;

    /// Returns the intersection of `self` and `rhs` as a new `SplaySet<T>`.
    ///
    /// # Examples
    /// ```
    /// use splay_tree::SplaySet;
    ///
    /// let a: SplaySet<_> = vec![1, 2, 3].into_iter().collect();
    /// let b: SplaySet<_> = vec![3, 4, 5].into_iter().collect();
    ///
    /// assert_eq!((&a & &b).into_iter().collect::<Vec<_>>(),
    ///            [3]);
    /// ```
    fn bitand(self, rhs: &SplaySet<T>) -> SplaySet<T> {
        self.intersection(rhs).cloned().collect()
    }
}
impl<'a, 'b, T> ops::BitOr<&'b SplaySet<T>> for &'a SplaySet<T>
where
    T: Ord + Clone,
{
    type Output = SplaySet<T>;

    /// Returns the union of `self` and `rhs` as a new `SplaySet<T>`.
    ///
    /// # Examples
    /// ```
    /// use splay_tree::SplaySet;
    ///
    /// let a: SplaySet<_> = vec![1, 2, 3].into_iter().collect();
    /// let b: SplaySet<_> = vec![3, 4, 5].into_iter().collect();
    ///
    /// assert_eq!((&a | &b).into_iter().collect::<Vec<_>>(),
    ///            [1, 2, 3, 4, 5]);
    /// ```
    fn bitor(self, rhs: &SplaySet<T>) -> SplaySet<T> {
        self.union(rhs).cloned().collect()
    }
}

/// An Iterator over a SplaySet items.
pub struct Iter<'a, T: 'a>(iter::Iter<'a, T, ()>);
impl<'a, T: 'a> Iter<'a, T> {
    fn new(set: &'a SplaySet<T>) -> Self {
        Iter(set.tree.iter())
    }
}
impl<'a, T: 'a> Iterator for Iter<'a, T> {
    type Item = &'a T;
    fn next(&mut self) -> Option<Self::Item> {
        self.0.next().map(|(e, _)| e)
    }
}

/// An owning iterator over a SplaySet's items.
pub struct IntoIter<T>(iter::IntoIter<T, ()>);
impl<T> Iterator for IntoIter<T> {
    type Item = T;
    fn next(&mut self) -> Option<Self::Item> {
        self.0.next().map(|(e, _)| e)
    }
}

fn item_cmp<T>(a: Option<&T>, b: Option<&T>) -> Option<cmp::Ordering>
where
    T: Ord,
{
    match (a, b) {
        (None, None) => None,
        (Some(_), None) => Some(cmp::Ordering::Less),
        (None, Some(_)) => Some(cmp::Ordering::Greater),
        (Some(a), Some(b)) => Some(a.cmp(b)),
    }
}

/// A lazy iterator producing elements in the set difference (in-order).
pub struct Difference<'a, T: 'a>(Peekable<Iter<'a, T>>, Peekable<Iter<'a, T>>);
impl<'a, T: 'a> Iterator for Difference<'a, T>
where
    T: Ord,
{
    type Item = &'a T;
    fn next(&mut self) -> Option<Self::Item> {
        loop {
            match item_cmp(self.0.peek(), self.1.peek()) {
                None => return None,
                Some(cmp::Ordering::Less) => return self.0.next(),
                Some(cmp::Ordering::Greater) => {
                    self.1.next();
                }
                Some(cmp::Ordering::Equal) => {
                    self.0.next();
                    self.1.next();
                }
            }
        }
    }
}

/// A lazy iterator producing elements in the set symmetric difference (in-order).
pub struct SymmetricDifference<'a, T: 'a>(Peekable<Iter<'a, T>>, Peekable<Iter<'a, T>>);
impl<'a, T: 'a> Iterator for SymmetricDifference<'a, T>
where
    T: Ord,
{
    type Item = &'a T;
    fn next(&mut self) -> Option<Self::Item> {
        loop {
            match item_cmp(self.0.peek(), self.1.peek()) {
                None => return None,
                Some(cmp::Ordering::Less) => return self.0.next(),
                Some(cmp::Ordering::Greater) => return self.1.next(),
                Some(cmp::Ordering::Equal) => {
                    self.0.next();
                    self.1.next();
                }
            }
        }
    }
}

/// A lazy iterator producing elements in the set intersection (in-order).
pub struct Intersection<'a, T: 'a>(Peekable<Iter<'a, T>>, Peekable<Iter<'a, T>>);
impl<'a, T: 'a> Iterator for Intersection<'a, T>
where
    T: Ord,
{
    type Item = &'a T;
    fn next(&mut self) -> Option<Self::Item> {
        loop {
            match item_cmp(self.0.peek(), self.1.peek()) {
                None => return None,
                Some(cmp::Ordering::Less) => {
                    self.0.next();
                }
                Some(cmp::Ordering::Greater) => {
                    self.1.next();
                }
                Some(cmp::Ordering::Equal) => {
                    self.0.next();
                    return self.1.next();
                }
            }
        }
    }
}

/// A lazy iterator producing elements in the set union (in-order).
pub struct Union<'a, T: 'a>(Peekable<Iter<'a, T>>, Peekable<Iter<'a, T>>);
impl<'a, T: 'a> Iterator for Union<'a, T>
where
    T: Ord,
{
    type Item = &'a T;
    fn next(&mut self) -> Option<Self::Item> {
        match item_cmp(self.0.peek(), self.1.peek()) {
            None => None,
            Some(cmp::Ordering::Less) => self.0.next(),
            Some(cmp::Ordering::Greater) => self.1.next(),
            Some(cmp::Ordering::Equal) => {
                self.0.next();
                self.1.next()
            }
        }
    }
}

/// A vector like view of a set.
#[derive(Debug, Clone)]
pub struct VecLike<'a, T: 'a> {
    inner: vec_like::VecLike<'a, T, ()>,
}
impl<'a, T: 'a> VecLike<'a, T> {
    fn new(tree: &'a tree_core::Tree<T, ()>) -> Self {
        VecLike {
            inner: vec_like::VecLike::new(tree),
        }
    }

    /// Returns the element of the vector at the given index,
    /// or `None` if the index is out of bounds.
    ///
    /// # Examples
    /// ```
    /// use splay_tree::SplaySet;
    ///
    /// let mut set = SplaySet::new();
    /// set.insert("foo");
    /// set.insert("bar");
    /// set.insert("baz");
    ///
    /// let vec = set.as_vec_like();
    /// assert_eq!(vec.get(0), Some(&"foo"));
    /// assert_eq!(vec.get(1), Some(&"bar"));
    /// assert_eq!(vec.get(2), Some(&"baz"));
    /// assert_eq!(vec.get(3), None);
    /// ```
    pub fn get(&self, index: usize) -> Option<&'a T> {
        self.inner.get(index).map(|(v, _)| v)
    }

    /// Returns the first element of the vector, or `None` if it is empty.
    ///
    /// # Examples
    /// ```
    /// use splay_tree::SplaySet;
    ///
    /// let mut set = SplaySet::new();
    /// set.insert("foo");
    /// set.insert("bar");
    /// set.insert("baz");
    ///
    /// let vec = set.as_vec_like();
    /// assert_eq!(vec.first(), Some(&"foo"));
    /// ```
    pub fn first(&self) -> Option<&'a T> {
        self.inner.first().map(|(v, _)| v)
    }

    /// Returns the last element of the vector, or `None` if it is empty.
    ///
    /// # Examples
    /// ```
    /// use splay_tree::SplaySet;
    ///
    /// let mut set = SplaySet::new();
    /// set.insert("foo");
    /// set.insert("bar");
    /// set.insert("baz");
    ///
    /// let vec = set.as_vec_like();
    /// assert_eq!(vec.last(), Some(&"baz"));
    /// ```
    pub fn last(&self) -> Option<&'a T> {
        self.inner.last().map(|(v, _)| v)
    }

    /// Gets an iterator over the vector's elements, in positional order (low to high).
    ///
    /// # Examples
    /// ```
    /// use splay_tree::SplaySet;
    ///
    /// let mut set = SplaySet::new();
    /// set.insert("foo");
    /// set.insert("bar");
    /// set.insert("baz");
    ///
    /// assert_eq!(set.iter().cloned().collect::<Vec<_>>(), ["bar", "baz", "foo"]);
    ///
    /// let vec = set.as_vec_like();
    /// assert_eq!(vec.iter().cloned().collect::<Vec<_>>(), ["foo", "bar", "baz"]);
    /// ```
    pub fn iter(&self) -> VecLikeIter<'a, T> {
        VecLikeIter(self.inner.iter())
    }

    /// Returns the number of elements in the vector like set.
    ///
    /// # Examples
    /// ```
    /// use splay_tree::SplaySet;
    ///
    /// let mut set = SplaySet::new();
    /// set.insert("foo");
    /// {
    ///     let vec = set.as_vec_like();
    ///     assert_eq!(vec.len(), 1);
    /// }
    /// ```
    pub fn len(&self) -> usize {
        self.inner.len()
    }

    /// Returns `true` if the vector like set contains no elements.
    ///
    /// # Examples
    /// ```
    /// use splay_tree::SplaySet;
    ///
    /// let set = SplaySet::<usize>::new();
    /// let vec = set.as_vec_like();
    /// assert!(vec.is_empty());
    /// ```
    pub fn is_empty(&self) -> bool {
        self.len() == 0
    }
}

/// A vector like mutable view of a set.
#[derive(Debug)]
pub struct VecLikeMut<'a, T: 'a> {
    inner: vec_like::VecLikeMut<'a, T, ()>,
}
impl<'a, T: 'a> VecLikeMut<'a, T>
where
    T: Ord,
{
    /// Appends a new element to the back of the vector like set.
    ///
    /// If the set did not have this value present, `true` is returnd.
    ///
    /// If the set did have this value present, `false` is returnd,
    /// and the entry is not appended.
    ///
    /// This is a synonym of the `SplaySet::insert` function.
    ///
    /// # Examples
    /// ```
    /// use splay_tree::SplaySet;
    ///
    /// let mut set = SplaySet::new();
    /// let mut vec = set.as_vec_like_mut();
    ///
    /// assert_eq!(vec.push("foo"), true);
    /// assert_eq!(vec.len(), 1);
    ///
    /// assert_eq!(vec.push("foo"), false);
    /// assert_eq!(vec.len(), 1);
    ///
    /// assert_eq!(vec.push("bar"), true);
    /// assert_eq!(vec.len(), 2);
    ///
    /// assert_eq!(vec.find_index("foo"), Some(0));
    /// assert_eq!(vec.get(0), Some(&"foo"));
    /// ```
    pub fn push(&mut self, value: T) -> bool {
        self.inner.push(value, ())
    }

    /// Removes the last element from the vector like set and returns it, or `None` if it is empty.
    ///
    /// # Examples
    /// ```
    /// use splay_tree::SplaySet;
    ///
    /// let mut set = SplaySet::new();
    /// set.insert("foo");
    /// set.insert("bar");
    /// {
    ///     let mut vec = set.as_vec_like_mut();
    ///     assert_eq!(vec.pop(), Some("bar"));
    ///     assert_eq!(vec.pop(), Some("foo"));
    ///     assert_eq!(vec.pop(), None);
    /// }
    /// assert!(set.is_empty());
    /// ```
    pub fn pop(&mut self) -> Option<T> {
        self.inner.pop().map(|(v, _)| v)
    }

    /// Returns the index of the element that is equal to the given value,
    /// or `None` if the collection does not have no such element.
    ///
    /// Because underlying `SplaySet` is a self-adjusting amortized data structure,
    /// this function requires the `mut` qualifier for `self`.
    ///
    /// # Examples
    /// ```
    /// use splay_tree::SplaySet;
    ///
    /// let mut set = SplaySet::new();
    /// set.insert("foo");
    /// set.insert("bar");
    /// set.insert("baz");
    ///
    /// let mut vec = set.as_vec_like_mut();
    /// assert_eq!(vec.find_index("foo"), Some(0));
    /// assert_eq!(vec.find_index("baz"), Some(2));
    /// assert_eq!(vec.find_index("qux"), None);
    /// ```
    pub fn find_index<Q: ?Sized>(&mut self, value: &Q) -> Option<usize>
    where
        T: Borrow<Q>,
        Q: Ord,
    {
        self.inner.find_index(value)
    }
}
impl<'a, T: 'a> VecLikeMut<'a, T> {
    fn new(tree: &'a mut tree_core::Tree<T, ()>) -> Self {
        VecLikeMut {
            inner: vec_like::VecLikeMut::new(tree),
        }
    }

    /// Returns the element of the vector at the given index,
    /// or `None` if the index is out of bounds.
    ///
    /// # Examples
    /// ```
    /// use splay_tree::SplaySet;
    ///
    /// let mut set = SplaySet::new();
    /// set.insert("foo");
    /// set.insert("bar");
    /// set.insert("baz");
    ///
    /// let vec = set.as_vec_like_mut();
    /// assert_eq!(vec.get(0), Some(&"foo"));
    /// assert_eq!(vec.get(1), Some(&"bar"));
    /// assert_eq!(vec.get(2), Some(&"baz"));
    /// assert_eq!(vec.get(3), None);
    /// ```
    pub fn get(&self, index: usize) -> Option<&T> {
        self.inner.get(index).map(|(v, _)| v)
    }

    /// Returns the first element of the vector, or `None` if it is empty.
    ///
    /// # Examples
    /// ```
    /// use splay_tree::SplaySet;
    ///
    /// let mut set = SplaySet::new();
    /// set.insert("foo");
    /// set.insert("bar");
    /// set.insert("baz");
    ///
    /// let vec = set.as_vec_like_mut();
    /// assert_eq!(vec.first(), Some(&"foo"));
    /// ```
    pub fn first(&self) -> Option<&T> {
        self.inner.first().map(|(v, _)| v)
    }

    /// Returns the last element of the vector, or `None` if it is empty.
    ///
    /// # Examples
    /// ```
    /// use splay_tree::SplaySet;
    ///
    /// let mut set = SplaySet::new();
    /// set.insert("foo");
    /// set.insert("bar");
    /// set.insert("baz");
    ///
    /// let vec = set.as_vec_like_mut();
    /// assert_eq!(vec.last(), Some(&"baz"));
    /// ```
    pub fn last(&self) -> Option<&T> {
        self.inner.last().map(|(v, _)| v)
    }

    /// Gets an iterator over the vector's elements, in positional order (low to high).
    ///
    /// # Examples
    /// ```
    /// use splay_tree::SplaySet;
    ///
    /// let mut set = SplaySet::new();
    /// set.insert("foo");
    /// set.insert("bar");
    /// set.insert("baz");
    ///
    /// assert_eq!(set.iter().cloned().collect::<Vec<_>>(), ["bar", "baz", "foo"]);
    ///
    /// let vec = set.as_vec_like_mut();
    /// assert_eq!(vec.iter().cloned().collect::<Vec<_>>(), ["foo", "bar", "baz"]);
    /// ```
    pub fn iter(&self) -> VecLikeIter<T> {
        VecLikeIter(self.inner.iter())
    }

    /// Returns the number of elements in the vector like set.
    ///
    /// # Examples
    /// ```
    /// use splay_tree::SplaySet;
    ///
    /// let mut set = SplaySet::new();
    /// set.insert("foo");
    /// {
    ///     let mut vec = set.as_vec_like_mut();
    ///     vec.push("bar");
    ///     assert_eq!(vec.len(), 2);
    /// }
    /// assert_eq!(set.len(), 2);
    /// ```
    pub fn len(&self) -> usize {
        self.inner.len()
    }

    /// Returns `true` if the vector like set contains no elements.
    ///
    /// # Examples
    /// ```
    /// use splay_tree::SplaySet;
    ///
    /// let mut set = SplaySet::new();
    ///
    /// let mut vec = set.as_vec_like_mut();
    /// assert!(vec.is_empty());
    ///
    /// vec.push(0);
    /// assert!(!vec.is_empty());
    /// ```
    pub fn is_empty(&self) -> bool {
        self.len() == 0
    }
}

/// An iterator over a VecLike's elements
pub struct VecLikeIter<'a, T: 'a>(vec_like::Iter<'a, T, ()>);
impl<'a, T: 'a> Iterator for VecLikeIter<'a, T> {
    type Item = &'a T;
    fn next(&mut self) -> Option<Self::Item> {
        self.0.next().map(|(v, _)| v)
    }
}