extern crate smallvec;
use std::fmt;
use std::iter::{FromIterator, IntoIterator};
use smallvec::{Array, SmallVec};
use std::collections::HashSet;
use std::hash::Hash;
pub struct SmolSet<A: Array>
where
A::Item: PartialEq + Eq,
{
inner: InnerSmolSet<A>,
}
impl<A: Array> Default for SmolSet<A>
where
A::Item: PartialEq + Eq + Hash,
{
fn default() -> Self {
SmolSet::new()
}
}
pub enum InnerSmolSet<A: Array>
where
A::Item: PartialEq + Eq,
{
Stack(SmallVec<A>),
Heap(std::collections::HashSet<A::Item>),
}
impl<A: Array> Default for InnerSmolSet<A>
where
A::Item: PartialEq + Eq,
{
fn default() -> Self {
InnerSmolSet::Stack(SmallVec::new())
}
}
impl<A: Array> Clone for InnerSmolSet<A>
where
A::Item: PartialEq + Eq + Clone,
{
fn clone(&self) -> Self {
match &self {
InnerSmolSet::Stack(elements) => InnerSmolSet::Stack(elements.clone()),
InnerSmolSet::Heap(elements) => InnerSmolSet::Heap(elements.clone()),
}
}
}
impl<A: Array> PartialEq for SmolSet<A>
where
A::Item: Eq + PartialEq + Hash,
{
fn eq(&self, other: &Self) -> bool {
fn set_same<A: Array>(stack: &SmallVec<A>, heap: &HashSet<A::Item>) -> bool
where
A::Item: Eq + PartialEq,
{
stack.len() == heap.len() && heap.iter().all(|x| stack.contains(x))
}
match (&self.inner, &other.inner) {
(InnerSmolSet::Stack(lhs), InnerSmolSet::Stack(rhs)) => lhs.eq(rhs),
(InnerSmolSet::Heap(lhs), InnerSmolSet::Heap(rhs)) => lhs.eq(rhs),
(InnerSmolSet::Stack(stack), InnerSmolSet::Heap(heap)) => set_same(stack, heap),
(InnerSmolSet::Heap(heap), InnerSmolSet::Stack(stack)) => set_same(stack, heap),
}
}
}
#[derive(PartialEq, Debug)]
pub enum SetMode {
Stack,
Heap,
}
impl<A: Array> SmolSet<A>
where
A::Item: PartialEq + Eq + Hash,
{
pub fn new() -> SmolSet<A> {
SmolSet {
inner: InnerSmolSet::Stack(SmallVec::new()),
}
}
pub fn mode(&self) -> SetMode {
match self.inner {
InnerSmolSet::Stack(_) => SetMode::Stack,
InnerSmolSet::Heap(_) => SetMode::Heap,
}
}
pub fn is_empty(&self) -> bool {
self.len() == 0
}
pub fn insert(&mut self, elem: A::Item) -> bool {
match &mut self.inner {
InnerSmolSet::Stack(ref mut elements) => {
if elements.contains(&elem) {
false
} else {
if elements.len() + 1 <= A::size() {
elements.push(elem);
} else {
let mut ee = HashSet::<A::Item>::with_capacity(elements.len() + 1);
while !elements.is_empty() {
ee.insert(elements.remove(0));
}
ee.insert(elem);
self.inner = InnerSmolSet::Heap(ee);
}
true
}
}
InnerSmolSet::Heap(ref mut elements) => elements.insert(elem),
}
}
pub fn remove(&mut self, elem: &A::Item) -> bool {
match &mut self.inner {
InnerSmolSet::Stack(ref mut elements) => {
if let Some(pos) = elements.iter().position(|e| *e == *elem) {
elements.remove(pos);
true
} else {
false
}
}
InnerSmolSet::Heap(ref mut elements) => elements.remove(elem),
}
}
pub fn contains(&self, elem: &A::Item) -> bool {
match &self.inner {
InnerSmolSet::Stack(ref elements) => elements.iter().any(|e| *e == *elem),
InnerSmolSet::Heap(ref elements) => elements.contains(elem),
}
}
pub fn iter(&self) -> SmolSetIter<A> {
match &self.inner {
InnerSmolSet::Stack(element) => SmolSetIter {
inner: InnerSmolSetIter::Stack(element.iter()),
},
InnerSmolSet::Heap(element) => SmolSetIter {
inner: InnerSmolSetIter::Heap(element.iter()),
},
}
}
pub fn len(&self) -> usize {
match &self.inner {
InnerSmolSet::Stack(elements) => elements.len(),
InnerSmolSet::Heap(elements) => elements.len(),
}
}
pub fn clear(&mut self) {
match &mut self.inner {
InnerSmolSet::Stack(ref mut elements) => elements.clear(),
InnerSmolSet::Heap(ref mut elements) => {
elements.clear();
self.inner = Default::default();
}
}
}
pub fn get(&self, elem: &A::Item) -> Option<&A::Item> {
match &self.inner {
InnerSmolSet::Stack(elements) => elements.iter().find(|x| (elem).eq(&x)),
InnerSmolSet::Heap(elements) => elements.iter().find(|x| (elem).eq(&x)),
}
}
pub fn take(&mut self, value: &A::Item) -> Option<A::Item> {
match &mut self.inner {
InnerSmolSet::Stack(ref mut elements) => {
if let Some(pos) = elements.iter().position(|e| *e == *value) {
let result = elements.remove(pos);
Some(result)
} else {
None
}
}
InnerSmolSet::Heap(ref mut elements) => elements.take(value),
}
}
pub fn replace(&mut self, value: A::Item) -> Option<A::Item> {
match &mut self.inner {
InnerSmolSet::Stack(ref mut elements) => {
if let Some(pos) = elements.iter().position(|e| *e == value) {
let result = elements.remove(pos);
elements.insert(pos, value);
Some(result)
} else {
None
}
}
InnerSmolSet::Heap(ref mut elements) => elements.replace(value),
}
}
pub fn drain(&mut self) -> SmallDrain<A::Item> {
match &mut self.inner {
InnerSmolSet::Stack(ref mut elements) => {
let mut ee = Vec::<A::Item>::with_capacity(elements.len() + 1);
while !elements.is_empty() {
ee.push(elements.remove(0));
}
SmallDrain { data: ee, index: 0 }
}
InnerSmolSet::Heap(ref mut elements) => {
let drain = elements.drain().collect::<Vec<A::Item>>();
SmallDrain {
data: drain,
index: 0,
}
}
}
}
pub fn retain<F>(&mut self, f: F)
where
F: FnMut(&mut A::Item) -> bool + for<'r> FnMut(&'r <A as smallvec::Array>::Item) -> bool,
{
match &mut self.inner {
InnerSmolSet::Stack(ref mut elements) => elements.retain(f),
InnerSmolSet::Heap(ref mut elements) => elements.retain(f),
}
}
pub fn intersection<'a>(&'a self, other: &'a Self) -> SmallIntersection<'a, A::Item> {
match &self.inner {
InnerSmolSet::Stack(ref elements) => {
let result = elements
.iter()
.filter(|x| other.contains(x))
.collect::<Vec<&'a A::Item>>();
SmallIntersection {
data: result,
index: 0,
}
}
InnerSmolSet::Heap(ref elements) => {
let result = elements
.iter()
.filter(|x| other.contains(x))
.collect::<Vec<&'a A::Item>>();
SmallIntersection {
data: result,
index: 0,
}
}
}
}
pub fn union<'a>(&'a self, other: &'a Self) -> SmallUnion<'a, A::Item> {
match &self.inner {
InnerSmolSet::Stack(ref elements) => {
let mut lhs = elements.iter().collect::<Vec<&'a A::Item>>();
let mut rhs = other
.iter()
.filter(|x| !lhs.contains(x))
.collect::<Vec<&'a A::Item>>();
lhs.append(&mut rhs);
SmallUnion {
data: lhs,
index: 0,
}
}
InnerSmolSet::Heap(ref elements) => {
let mut lhs = elements.iter().collect::<Vec<&'a A::Item>>();
let mut rhs = other
.iter()
.filter(|x| !lhs.contains(x))
.collect::<Vec<&'a A::Item>>();
lhs.append(&mut rhs);
SmallUnion {
data: rhs,
index: 0,
}
}
}
}
pub fn difference<'a>(&'a self, other: &'a Self) -> SmallDifference<'a, A::Item> {
match &self.inner {
InnerSmolSet::Stack(ref elements) => {
let lhs = elements
.iter()
.filter(|x| !other.contains(x))
.collect::<Vec<&'a A::Item>>();
SmallDifference {
data: lhs,
index: 0,
}
}
InnerSmolSet::Heap(ref elements) => {
let lhs = elements
.iter()
.filter(|x| !other.contains(x))
.collect::<Vec<&'a A::Item>>();
SmallDifference {
data: lhs,
index: 0,
}
}
}
}
pub fn symmetric_difference<'a>(
&'a self,
other: &'a Self,
) -> SmallSymmetricDifference<'a, A::Item> {
match &self.inner {
InnerSmolSet::Stack(ref elements) => {
let mut lhs = elements
.iter()
.filter(|x| !other.contains(x))
.collect::<Vec<&'a A::Item>>();
let mut rhs = other
.iter()
.filter(|x| !elements.contains(x))
.collect::<Vec<&'a A::Item>>();
lhs.append(&mut rhs);
SmallSymmetricDifference {
data: lhs,
index: 0,
}
}
InnerSmolSet::Heap(ref elements) => {
let mut lhs = elements
.iter()
.filter(|x| other.contains(x))
.collect::<Vec<&'a A::Item>>();
let mut rhs = other
.iter()
.filter(|x| elements.contains(x))
.collect::<Vec<&'a A::Item>>();
lhs.append(&mut rhs);
SmallSymmetricDifference {
data: lhs,
index: 0,
}
}
}
}
}
pub struct SmallDrain<T> {
data: Vec<T>,
index: usize,
}
impl<T> Iterator for SmallDrain<T> {
type Item = T;
fn next(&mut self) -> Option<Self::Item> {
if self.index == self.data.len() {
None
} else {
let ptr = self.data.as_ptr();
self.index += 1;
unsafe { Some(std::ptr::read(ptr.add(self.index - 1))) }
}
}
}
pub struct SmallIntersection<'a, T> {
data: Vec<&'a T>,
index: usize,
}
impl<'a, T> Iterator for SmallIntersection<'a, T> {
type Item = &'a T;
fn next(&mut self) -> Option<Self::Item> {
if self.index == self.data.len() {
None
} else {
let ptr = self.data.as_ptr();
self.index += 1;
unsafe { Some(std::ptr::read(ptr.add(self.index - 1))) }
}
}
}
pub struct SmallUnion<'a, T> {
data: Vec<&'a T>,
index: usize,
}
impl<'a, T> Iterator for SmallUnion<'a, T> {
type Item = &'a T;
fn next(&mut self) -> Option<Self::Item> {
if self.index == self.data.len() {
None
} else {
let ptr = self.data.as_ptr();
self.index += 1;
unsafe { Some(std::ptr::read(ptr.add(self.index - 1))) }
}
}
}
pub struct SmallDifference<'a, T> {
data: Vec<&'a T>,
index: usize,
}
impl<'a, T> Iterator for SmallDifference<'a, T> {
type Item = &'a T;
fn next(&mut self) -> Option<Self::Item> {
if self.index == self.data.len() {
None
} else {
let ptr = self.data.as_ptr();
self.index += 1;
unsafe { Some(std::ptr::read(ptr.add(self.index - 1))) }
}
}
}
pub struct SmallSymmetricDifference<'a, T> {
data: Vec<&'a T>,
index: usize,
}
impl<'a, T> Iterator for SmallSymmetricDifference<'a, T> {
type Item = &'a T;
fn next(&mut self) -> Option<Self::Item> {
if self.index == self.data.len() {
None
} else {
let ptr = self.data.as_ptr();
self.index += 1;
unsafe { Some(std::ptr::read(ptr.add(self.index - 1))) }
}
}
}
impl<A: Array> Clone for SmolSet<A>
where
A::Item: PartialEq + Eq + Clone,
{
fn clone(&self) -> SmolSet<A> {
SmolSet {
inner: self.inner.clone(),
}
}
}
impl<A: Array> fmt::Debug for SmolSet<A>
where
A::Item: PartialEq + Eq + fmt::Debug,
{
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
match &self.inner {
InnerSmolSet::Stack(elements) => write!(f, "{:?}", elements.as_slice()),
InnerSmolSet::Heap(elements) => write!(f, "{:?}", elements),
}
}
}
impl<A: Array> FromIterator<A::Item> for SmolSet<A>
where
A::Item: PartialEq + Eq + Hash,
{
fn from_iter<T>(iter: T) -> Self
where
T: IntoIterator<Item = A::Item>,
{
iter.into_iter().fold(SmolSet::new(), |mut acc, x| {
acc.insert(x);
acc
})
}
}
pub struct SmolSetIter<'a, A: Array>
where
A::Item: PartialEq + Eq + Hash + 'a,
{
inner: InnerSmolSetIter<'a, A>,
}
pub enum InnerSmolSetIter<'a, A: Array>
where
A::Item: PartialEq + Eq + Hash + 'a,
{
Stack(std::slice::Iter<'a, A::Item>),
Heap(std::collections::hash_set::Iter<'a, A::Item>),
}
impl<'a, A: Array> Iterator for SmolSetIter<'a, A>
where
A::Item: PartialEq + Eq + Hash + 'a,
{
type Item = &'a A::Item;
fn next(&mut self) -> Option<Self::Item> {
match &mut self.inner {
InnerSmolSetIter::Stack(ref mut iter) => iter.next(),
InnerSmolSetIter::Heap(ref mut iter) => iter.next(),
}
}
}