Revision control
Copy as Markdown
Other Tools
//! Type definitions for an ordered set.
use crate::collections::IndexMap;
use core::{borrow::Borrow, hash::Hash, iter::FusedIterator, ops::Index};
/// A default set of values.
///
/// Provides an API compatible with both [`IndexSet`] and a custom implementation based on [`BTreeMap`].
///
/// [`IndexSet`]: indexmap::IndexSet
/// [`BTreeMap`]: alloc::collections::BTreeMap
#[derive(Debug, Clone)]
pub struct IndexSet<T> {
inner: IndexMap<T, ()>,
}
impl<T> Default for IndexSet<T> {
#[inline]
fn default() -> Self {
Self {
inner: IndexMap::default(),
}
}
}
impl<T> IndexSet<T> {
/// Clears the [`IndexSet`], removing all elements.
#[inline]
pub fn clear(&mut self) {
self.inner.clear()
}
/// Returns the number of elements in the [`IndexSet`].
#[inline]
pub fn len(&self) -> usize {
self.inner.len()
}
/// Returns `true` if the [`IndexSet`] contains no elements.
#[inline]
pub fn is_empty(&self) -> bool {
self.inner.is_empty()
}
/// Returns an iterator that yields the items in the [`IndexSet`].
#[inline]
pub fn iter(&self) -> Iter<'_, T> {
Iter {
inner: self.inner.iter(),
}
}
}
impl<T> IndexSet<T>
where
T: Eq + Hash + Ord + Clone,
{
/// Reserves capacity for at least `additional` more elements to be inserted in the [`IndexSet`].
#[inline]
pub fn reserve(&mut self, additional: usize) {
self.inner.reserve(additional);
}
/// Returns true if the [`IndexSet`] contains an element equal to the `value`.
#[inline]
pub fn contains<Q: ?Sized>(&self, value: &Q) -> bool
where
T: Borrow<Q>,
Q: Hash + Eq + Ord,
{
self.inner.contains_key(value)
}
/// Returns a reference to the element in the [`IndexSet`], if any, that is equal to the `value`.
#[inline]
pub fn get<Q: ?Sized>(&self, value: &Q) -> Option<&T>
where
T: Borrow<Q>,
Q: Hash + Eq + Ord,
{
self.inner.get_key_value(value).map(|(x, &())| x)
}
/// Return the index of the item provided, if it exists.
pub fn get_index_of<Q>(&self, value: &Q) -> Option<usize>
where
T: Borrow<Q>,
Q: Hash + Eq + Ord + ?Sized,
{
let (index, _, _) = self.inner.get_full(value)?;
Some(index)
}
/// Adds `value` to the [`IndexSet`].
///
/// Returns whether the value was newly inserted:
///
/// - Returns `true` if the set did not previously contain an equal value.
/// - Returns `false` otherwise and the entry is not updated.
#[inline]
pub fn insert(&mut self, value: T) -> bool {
self.inner.insert(value, ()).is_none()
}
/// Remove the value from the [`IndexSet`], and return `true` if it was present.
///
/// Like [`Vec::swap_remove`], the value is removed by swapping it with the
/// last element of the set and popping it off. **This perturbs
/// the position of what used to be the last element!**
///
/// Return `false` if `value` was not in the set.
///
/// Computes in **O(1)** time (average).
///
/// [`Vec::swap_remove`]: alloc::vec::Vec::swap_remove
#[inline]
pub fn swap_remove<Q: ?Sized>(&mut self, value: &Q) -> bool
where
T: Borrow<Q>,
Q: Hash + Eq + Ord,
{
self.inner.swap_remove(value).is_some()
}
/// Adds a value to the [`IndexSet`], replacing the existing value, if any, that is equal to the given
/// one. Returns the replaced value.
pub fn replace(&mut self, value: T) -> Option<T> {
let removed = self.inner.swap_remove_entry(&value);
self.inner.insert(value, ());
removed.map(|(key, _value)| key)
}
/// Returns `true` if `self` has no elements in common with `other`.
/// This is equivalent to checking for an empty intersection.
pub fn is_disjoint(&self, other: &Self) -> bool {
if self.len() <= other.len() {
self.iter().all(move |value| !other.contains(value))
} else {
other.iter().all(move |value| !self.contains(value))
}
}
/// Returns `true` if the [`IndexSet`] is a subset of another,
/// i.e., `other` contains at least all the values in `self`.
pub fn is_subset(&self, other: &Self) -> bool {
self.len() <= other.len() && self.iter().all(move |value| other.contains(value))
}
/// Returns `true` if the [`IndexSet`] is a superset of another,
/// i.e., `self` contains at least all the values in `other`.
#[inline]
pub fn is_superset(&self, other: &Self) -> bool {
other.is_subset(self)
}
}
impl<T> Index<usize> for IndexSet<T>
where
T: Hash + Eq + Ord,
{
type Output = T;
#[inline]
fn index(&self, index: usize) -> &T {
let Some((value, _)) = self.inner.get_index(index) else {
panic!("out of bounds index: {index}");
};
value
}
}
impl<T> FromIterator<T> for IndexSet<T>
where
T: Hash + Eq + Ord + Clone,
{
fn from_iter<I>(iter: I) -> Self
where
I: IntoIterator<Item = T>,
{
Self {
inner: <IndexMap<T, ()>>::from_iter(iter.into_iter().map(|value| (value, ()))),
}
}
}
impl<'a, T> IntoIterator for &'a IndexSet<T> {
type Item = &'a T;
type IntoIter = Iter<'a, T>;
#[inline]
fn into_iter(self) -> Self::IntoIter {
self.iter()
}
}
impl<T> Extend<T> for IndexSet<T>
where
T: Hash + Eq + Ord + Clone,
{
fn extend<Iter: IntoIterator<Item = T>>(&mut self, iter: Iter) {
self.inner.extend(iter.into_iter().map(|value| (value, ())))
}
}
/// An iterator over the items of a [`IndexSet`].
#[derive(Debug, Clone)]
pub struct Iter<'a, T> {
inner: <&'a IndexMap<T, ()> as IntoIterator>::IntoIter,
}
impl<'a, T> Iterator for Iter<'a, T> {
type Item = &'a T;
#[inline]
fn size_hint(&self) -> (usize, Option<usize>) {
self.inner.size_hint()
}
#[inline]
fn next(&mut self) -> Option<Self::Item> {
self.inner.next().map(|(key, _value)| key)
}
}
impl<'a, T> ExactSizeIterator for Iter<'a, T> {
#[inline]
fn len(&self) -> usize {
self.inner.len()
}
}
impl<'a, T> FusedIterator for Iter<'a, T> {}
impl<T> IntoIterator for IndexSet<T> {
type Item = T;
type IntoIter = IntoIter<T>;
#[inline]
fn into_iter(self) -> Self::IntoIter {
IntoIter {
inner: self.inner.into_iter(),
}
}
}
/// An iterator over the owned items of an [`IndexSet`].
#[derive(Debug)]
pub struct IntoIter<T> {
inner: <IndexMap<T, ()> as IntoIterator>::IntoIter,
}
impl<T> Iterator for IntoIter<T> {
type Item = T;
#[inline]
fn size_hint(&self) -> (usize, Option<usize>) {
self.inner.size_hint()
}
#[inline]
fn next(&mut self) -> Option<Self::Item> {
self.inner.next().map(|(key, _value)| key)
}
}
impl<T> ExactSizeIterator for IntoIter<T> {
#[inline]
fn len(&self) -> usize {
self.inner.len()
}
}
impl<T> FusedIterator for IntoIter<T> {}
#[cfg(feature = "serde")]
impl<T> serde::Serialize for IndexSet<T>
where
T: serde::Serialize + Eq + Hash + Ord,
{
fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
where
S: serde::ser::Serializer,
{
serde::Serialize::serialize(&self.inner, serializer)
}
}
#[cfg(feature = "serde")]
impl<'a, T> serde::Deserialize<'a> for IndexSet<T>
where
T: serde::Deserialize<'a> + Eq + Hash + Ord + Clone,
{
fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
where
D: serde::de::Deserializer<'a>,
{
Ok(IndexSet {
inner: serde::Deserialize::deserialize(deserializer)?,
})
}
}
impl<T> PartialEq for IndexSet<T>
where
T: PartialEq + Hash + Ord,
{
fn eq(&self, other: &Self) -> bool {
self.inner == other.inner
}
fn ne(&self, other: &Self) -> bool {
self.inner != other.inner
}
}
impl<T> Eq for IndexSet<T> where T: Eq + Hash + Ord {}