use crate::map::red_black_tree_map;
use crate::RedBlackTreeMap;
use archery::{ArcK, RcK, SharedPointerKind};
use std::borrow::Borrow;
use std::cmp::Ordering;
use std::fmt::Display;
use std::iter::FromIterator;
use std::ops::RangeBounds;
pub type Iter<'a, T, P> = red_black_tree_map::IterKeys<'a, T, (), P>;
pub type RangeIter<'a, T, RB, Q, P> =
std::iter::Map<red_black_tree_map::RangeIter<'a, T, (), RB, Q, P>, fn((&'a T, &())) -> &'a T>;
#[macro_export]
macro_rules! rbt_set {
($($e:expr),*) => {
{
#[allow(unused_mut)]
let mut s = $crate::RedBlackTreeSet::new();
$(
s.insert_mut($e);
)*
s
}
};
}
#[macro_export]
macro_rules! rbt_set_sync {
($($e:expr),*) => {
{
#[allow(unused_mut)]
let mut s = $crate::RedBlackTreeSet::new_sync();
$(
s.insert_mut($e);
)*
s
}
};
}
#[derive(Debug)]
pub struct RedBlackTreeSet<T, P = RcK>
where
T: Ord,
P: SharedPointerKind,
{
map: RedBlackTreeMap<T, (), P>,
}
pub type RedBlackTreeSetSync<T> = RedBlackTreeSet<T, ArcK>;
impl<T> RedBlackTreeSetSync<T>
where
T: Ord,
{
#[must_use]
pub fn new_sync() -> RedBlackTreeSetSync<T> {
RedBlackTreeSet::new_with_ptr_kind()
}
}
impl<T> RedBlackTreeSet<T>
where
T: Ord,
{
#[must_use]
pub fn new() -> RedBlackTreeSet<T> {
RedBlackTreeSet { map: RedBlackTreeMap::new_with_ptr_kind() }
}
}
impl<T, P> RedBlackTreeSet<T, P>
where
T: Ord,
P: SharedPointerKind,
{
#[must_use]
pub fn new_with_ptr_kind() -> RedBlackTreeSet<T, P> {
RedBlackTreeSet { map: RedBlackTreeMap::new_with_ptr_kind() }
}
#[must_use]
pub fn insert(&self, v: T) -> RedBlackTreeSet<T, P> {
RedBlackTreeSet { map: self.map.insert(v, ()) }
}
pub fn insert_mut(&mut self, v: T) {
self.map.insert_mut(v, ());
}
#[must_use]
pub fn remove<V: ?Sized>(&self, v: &V) -> RedBlackTreeSet<T, P>
where
T: Borrow<V>,
V: Ord,
{
RedBlackTreeSet { map: self.map.remove(v) }
}
pub fn remove_mut<V: ?Sized>(&mut self, v: &V) -> bool
where
T: Borrow<V>,
V: Ord,
{
self.map.remove_mut(v)
}
#[must_use]
pub fn contains<V: ?Sized>(&self, v: &V) -> bool
where
T: Borrow<V>,
V: Ord,
{
self.map.contains_key(v)
}
#[must_use]
pub fn first(&self) -> Option<&T> {
self.map.first().map(|(k, _)| k)
}
#[must_use]
pub fn last(&self) -> Option<&T> {
self.map.last().map(|(k, _)| k)
}
#[must_use]
pub fn is_disjoint<PO>(&self, other: &RedBlackTreeSet<T, PO>) -> bool
where
PO: SharedPointerKind,
{
let mut self_it = self.iter();
let mut other_it = other.iter();
let mut v_opt = self_it.next();
let mut u_opt = other_it.next();
while let (Some(v), Some(u)) = (v_opt, u_opt) {
match v.cmp(u) {
Ordering::Less => v_opt = self_it.next(),
Ordering::Equal => return false,
Ordering::Greater => u_opt = other_it.next(),
}
}
true
}
#[must_use]
pub fn is_subset<PO>(&self, other: &RedBlackTreeSet<T, PO>) -> bool
where
PO: SharedPointerKind,
{
let mut other_it = other.iter();
for v in self.iter() {
loop {
match other_it.next() {
Some(u) => match u.cmp(v) {
Ordering::Less => (),
Ordering::Equal => break,
Ordering::Greater => return false,
},
None => return false,
}
}
}
true
}
#[must_use]
pub fn is_superset<PO>(&self, other: &RedBlackTreeSet<T, PO>) -> bool
where
PO: SharedPointerKind,
{
other.is_subset(self)
}
#[must_use]
#[inline]
pub fn size(&self) -> usize {
self.map.size()
}
#[must_use]
#[inline]
pub fn is_empty(&self) -> bool {
self.size() == 0
}
#[must_use]
pub fn iter(&self) -> Iter<'_, T, P> {
self.map.keys()
}
#[must_use]
pub fn range<Q, RB>(&self, range: RB) -> RangeIter<'_, T, RB, Q, P>
where
T: Borrow<Q>,
Q: Ord + ?Sized,
RB: RangeBounds<Q>,
{
self.map.range(range).map(|(k, _)| k)
}
}
impl<T, P> Clone for RedBlackTreeSet<T, P>
where
T: Ord,
P: SharedPointerKind,
{
fn clone(&self) -> RedBlackTreeSet<T, P> {
RedBlackTreeSet { map: self.map.clone() }
}
}
impl<T, P> Default for RedBlackTreeSet<T, P>
where
T: Ord,
P: SharedPointerKind,
{
fn default() -> RedBlackTreeSet<T, P> {
RedBlackTreeSet::new_with_ptr_kind()
}
}
impl<T, P, PO> PartialEq<RedBlackTreeSet<T, PO>> for RedBlackTreeSet<T, P>
where
T: Ord,
P: SharedPointerKind,
PO: SharedPointerKind,
{
fn eq(&self, other: &RedBlackTreeSet<T, PO>) -> bool {
self.map.eq(&other.map)
}
}
impl<T, P> Eq for RedBlackTreeSet<T, P>
where
T: Ord,
P: SharedPointerKind,
{
}
impl<T: Ord, P, PO> PartialOrd<RedBlackTreeSet<T, PO>> for RedBlackTreeSet<T, P>
where
P: SharedPointerKind,
PO: SharedPointerKind,
{
fn partial_cmp(&self, other: &RedBlackTreeSet<T, PO>) -> Option<Ordering> {
self.iter().partial_cmp(other.iter())
}
}
impl<T: Ord, P> Ord for RedBlackTreeSet<T, P>
where
P: SharedPointerKind,
{
fn cmp(&self, other: &RedBlackTreeSet<T, P>) -> Ordering {
self.iter().cmp(other.iter())
}
}
impl<T, P> Display for RedBlackTreeSet<T, P>
where
T: Ord + Display,
P: SharedPointerKind,
{
fn fmt(&self, fmt: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
let mut first = true;
fmt.write_str("{")?;
for v in self.iter() {
if !first {
fmt.write_str(", ")?;
}
v.fmt(fmt)?;
first = false;
}
fmt.write_str("}")
}
}
impl<'a, T, P> IntoIterator for &'a RedBlackTreeSet<T, P>
where
T: Ord,
P: SharedPointerKind,
{
type Item = &'a T;
type IntoIter = Iter<'a, T, P>;
fn into_iter(self) -> Iter<'a, T, P> {
self.iter()
}
}
impl<T, P> FromIterator<T> for RedBlackTreeSet<T, P>
where
T: Ord,
P: SharedPointerKind,
{
fn from_iter<I: IntoIterator<Item = T>>(into_iter: I) -> RedBlackTreeSet<T, P> {
let mut set = RedBlackTreeSet::new_with_ptr_kind();
for v in into_iter {
set.insert_mut(v);
}
set
}
}
#[cfg(feature = "serde")]
pub mod serde {
use super::*;
use ::serde::de::{Deserialize, Deserializer, SeqAccess, Visitor};
use ::serde::ser::{Serialize, Serializer};
use std::fmt;
use std::marker::PhantomData;
impl<T, P> Serialize for RedBlackTreeSet<T, P>
where
T: Ord + Serialize,
P: SharedPointerKind,
{
fn serialize<S: Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
serializer.collect_seq(self)
}
}
impl<'de, T, P> Deserialize<'de> for RedBlackTreeSet<T, P>
where
T: Ord + Deserialize<'de>,
P: SharedPointerKind,
{
fn deserialize<D: Deserializer<'de>>(
deserializer: D,
) -> Result<RedBlackTreeSet<T, P>, D::Error> {
deserializer.deserialize_seq(RedBlackTreeSetVisitor {
_phantom_t: PhantomData,
_phantom_p: PhantomData,
})
}
}
struct RedBlackTreeSetVisitor<T, P> {
_phantom_t: PhantomData<T>,
_phantom_p: PhantomData<P>,
}
impl<'de, T, P> Visitor<'de> for RedBlackTreeSetVisitor<T, P>
where
T: Ord + Deserialize<'de>,
P: SharedPointerKind,
{
type Value = RedBlackTreeSet<T, P>;
fn expecting(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
formatter.write_str("a sequence")
}
fn visit_seq<A>(self, mut seq: A) -> Result<RedBlackTreeSet<T, P>, A::Error>
where
A: SeqAccess<'de>,
{
let mut set = RedBlackTreeSet::new_with_ptr_kind();
while let Some(value) = seq.next_element()? {
set.insert_mut(value);
}
Ok(set)
}
}
}
#[cfg(test)]
mod test;