#[cfg(test)]
#[macro_use]
extern crate quickcheck;
#[cfg(feature = "serde")]
extern crate serde;
#[cfg(feature = "serde")]
use serde::{Deserialize, Deserializer, Serialize, Serializer};
pub mod bitfield;
mod bucket;
mod builder;
mod iterator;
use bitfield::{BitField, DefaultBitField};
use bucket::Bucket;
pub use builder::BiMapBuilder;
pub use iterator::{IntoIter, Iter};
use std::borrow::Borrow;
use std::collections::hash_map::RandomState;
use std::fmt::{self, Debug};
use std::hash::{BuildHasher, Hash, Hasher};
use std::iter::{self, Extend, FromIterator};
use std::mem;
pub(crate) const DEFAULT_HASH_MAP_SIZE: usize = 32;
const RESIZE_GROWTH_FACTOR: usize = 2;
pub(crate) const MAX_LOAD_FACTOR: f32 = 1.1;
pub struct BiMap<L, R, LH = RandomState, RH = RandomState, B = DefaultBitField> {
len: usize,
left_data: Box<[Bucket<L, usize, B>]>,
right_data: Box<[Bucket<R, usize, B>]>,
left_hasher: LH,
right_hasher: RH,
}
impl<L, R> Default for BiMap<L, R> {
fn default() -> Self {
BiMapBuilder::new().finish()
}
}
impl<L, R> BiMap<L, R> {
pub fn new() -> Self {
Default::default()
}
}
impl<L, R, LH, RH, B> BiMap<L, R, LH, RH, B> {
pub fn capacity(&self) -> usize {
(self.left_data.len() as f32 / MAX_LOAD_FACTOR).floor() as usize
}
pub fn len(&self) -> usize {
self.len
}
pub fn is_empty(&self) -> bool {
self.len == 0
}
pub fn iter(&self) -> Iter<L, R, B> {
self.into_iter()
}
}
impl<L, R, LH, RH, B> BiMap<L, R, LH, RH, B>
where
L: Hash + Eq,
R: Hash + Eq,
LH: BuildHasher,
RH: BuildHasher,
B: BitField,
{
fn find_ideal_index<K: Hash, H: BuildHasher>(key: &K, hasher: &H, len: usize) -> usize {
let mut hasher = hasher.build_hasher();
key.hash(&mut hasher);
hasher.finish() as usize % len
}
fn mark_as_full<K>(ideal_index: usize, actual_index: usize, data: &mut [Bucket<K, usize, B>]) {
let offset = (data.len() + actual_index - ideal_index) % data.len();
data[ideal_index].neighbourhood = data[ideal_index].neighbourhood | B::one_at(offset);
}
fn mark_as_empty<K>(ideal_index: usize, actual_index: usize, data: &mut [Bucket<K, usize, B>]) {
let offset = (data.len() + actual_index - ideal_index) % data.len();
data[ideal_index].neighbourhood = data[ideal_index].neighbourhood & B::zero_at(offset);
}
fn insert_one_sided<K: Hash, V, H: BuildHasher>(
key: K,
key_data: &mut [Bucket<K, usize, B>],
value_data: &mut [Bucket<V, usize, B>],
hasher: &H,
) -> Result<usize, K> {
let len = key_data.len();
let ideal_index = Self::find_ideal_index(&key, hasher, len);
if key_data[ideal_index].neighbourhood.full() {
return Err(key);
}
let nearest = key_data[ideal_index..]
.iter()
.chain(key_data[..ideal_index].iter())
.enumerate()
.find(|&(_, bucket)| bucket.data.is_none())
.map(|(offset, _)| offset);
if let Some(offset) = nearest {
if offset < B::size() {
let index = (offset + ideal_index) % len;
Self::mark_as_full(ideal_index, index, key_data);
key_data[index].data = Some((key, usize::max_value(), ideal_index));
Ok(index)
} else {
let max_offset = (ideal_index + B::size()) % len;
let nearest = (0..)
.map(|i| (len + max_offset - i) % len)
.take(B::size() - 1)
.skip(1)
.find(|&i| {
let &(_, _, ideal) = key_data[i].data.as_ref().unwrap();
if ideal > ideal_index {
ideal - ideal_index < B::size()
} else if ideal < ideal_index {
ideal < max_offset && max_offset < ideal
} else {
false
}
});
if let Some(index) = nearest {
let (new_key, new_value, new_ideal) = key_data[index].data.take().unwrap();
Self::mark_as_empty(new_ideal, index, key_data);
key_data[index].data = Some((key, usize::max_value(), ideal_index));
Self::mark_as_full(ideal_index, index, key_data);
match Self::insert_one_sided(new_key, key_data, value_data, hasher) {
Ok(new_key_index) => {
{
let &mut (_, ref mut paired_key_index, _) =
value_data[new_value].data.as_mut().unwrap();
*paired_key_index = new_key_index;
let &mut (_, ref mut paired_value_index, _) =
key_data[new_key_index].data.as_mut().unwrap();
*paired_value_index = new_value;
}
Self::mark_as_full(new_ideal, new_key_index, key_data);
Ok(index)
}
Err(new_key) => {
Self::mark_as_full(new_ideal, index, key_data);
Self::mark_as_empty(ideal_index, index, key_data);
let (key, _, _) = key_data[index].data.take().unwrap();
key_data[index].data = Some((new_key, new_value, new_ideal));
Err(key)
}
}
} else {
Err(key)
}
}
} else {
Err(key)
}
}
pub fn insert(&mut self, left: L, right: R) -> (Option<R>, Option<L>) {
let output = {
let &mut BiMap {
ref mut len,
ref mut left_data,
ref mut right_data,
ref left_hasher,
ref right_hasher,
} = self;
match Self::remove(&left, left_data, right_data, left_hasher, right_hasher, len) {
Some((old_left, old_right)) => {
if old_right == right {
(Some(old_right), Some(old_left))
} else {
(
Some(old_right),
Self::remove(
&right,
right_data,
left_data,
right_hasher,
left_hasher,
len,
)
.map(|(_key, value)| value),
)
}
}
None => (
None,
Self::remove(
&right,
right_data,
left_data,
right_hasher,
left_hasher,
len,
)
.map(|(_key, value)| value),
),
}
};
let failure: Option<(L, R)> = if MAX_LOAD_FACTOR * self.len as f32
>= self.left_data.len() as f32
{
Some((left, right))
} else {
let &mut BiMap {
ref mut left_data,
ref mut right_data,
ref left_hasher,
ref right_hasher,
..
} = self;
match Self::insert_one_sided(left, left_data, right_data, left_hasher) {
Ok(left_index) => {
match Self::insert_one_sided(right, right_data, left_data, right_hasher) {
Ok(right_index) => {
let &mut (_, ref mut paired_right_index, _) =
left_data[left_index].data.as_mut().unwrap();
*paired_right_index = right_index;
let &mut (_, ref mut paired_left_index, _) =
right_data[right_index].data.as_mut().unwrap();
*paired_left_index = left_index;
None
}
Err(right) => {
let (left, _, left_ideal) = left_data[left_index].data.take().unwrap();
Self::mark_as_empty(left_ideal, left_index, left_data);
Some((left, right))
}
}
}
Err(left) => Some((left, right)),
}
};
if failure.is_none() {
self.len += 1;
}
if let Some((left, right)) = failure {
self.len = 0;
let capacity = self.left_data.len() * RESIZE_GROWTH_FACTOR;
let old_left_data = mem::replace(&mut self.left_data, Bucket::empty_vec(capacity));
let old_right_data = mem::replace(&mut self.right_data, Bucket::empty_vec(capacity));
iter::once((left, right))
.chain(IntoIter::new(old_left_data, old_right_data))
.for_each(|(left, right)| {
self.insert(left, right);
});
}
output
}
fn get<'a, Q: ?Sized, K, V, KH>(
key: &Q,
key_data: &[Bucket<K, usize, B>],
value_data: &'a [Bucket<V, usize, B>],
key_hasher: &KH,
) -> Option<&'a V>
where
Q: Hash + Eq,
K: Hash + Eq + Borrow<Q>,
KH: BuildHasher,
{
let len = key_data.len();
let ideal = Self::find_ideal_index(&key, key_hasher, len);
let neighbourhood = key_data[ideal].neighbourhood;
neighbourhood
.iter()
.filter_map(|offset| key_data[(ideal + offset) % len].data.as_ref())
.filter(|&&(ref candidate_key, ..)| candidate_key.borrow() == key)
.filter_map(|&(_, pair_index, _)| value_data[pair_index].data.as_ref())
.map(|&(ref value, ..)| value)
.next()
}
fn remove<Q: ?Sized, K, V, KH, VH>(
key: &Q,
key_data: &mut [Bucket<K, usize, B>],
value_data: &mut [Bucket<V, usize, B>],
key_hasher: &KH,
value_hasher: &VH,
map_len: &mut usize,
) -> Option<(K, V)>
where
Q: Hash + Eq,
K: Hash + Eq + Borrow<Q>,
V: Hash,
KH: BuildHasher,
VH: BuildHasher,
{
let len = key_data.len();
let index = Self::find_ideal_index(&key, key_hasher, len);
let neighbourhood = key_data[index].neighbourhood;
if let Some(offset) =
neighbourhood
.iter()
.find(|offset| match key_data[(index + offset) % len].data {
Some((ref candidate_key, ..)) => candidate_key.borrow() == key,
_ => false,
})
{
key_data[index].neighbourhood = neighbourhood & B::zero_at(offset);
let (key, value_index, _) = key_data[(index + offset) % len].data.take().unwrap();
let (value, ..) = value_data[value_index].data.take().unwrap();
let ideal_value_index = Self::find_ideal_index(&value, value_hasher, len);
let value_offset = (value_index + len - ideal_value_index) % len;
value_data[ideal_value_index].neighbourhood =
value_data[ideal_value_index].neighbourhood & B::zero_at(value_offset);
*map_len -= 1;
Some((key, value))
} else {
None
}
}
pub fn get_left<'a, Q: ?Sized>(&'a self, left: &Q) -> Option<&'a R>
where
L: Borrow<Q>,
Q: Hash + Eq,
{
let &BiMap {
ref left_data,
ref right_data,
ref left_hasher,
..
} = self;
Self::get(left, left_data, right_data, left_hasher)
}
pub fn get_right<'a, Q: ?Sized>(&'a self, right: &Q) -> Option<&'a L>
where
R: Borrow<Q>,
Q: Hash + Eq,
{
let &BiMap {
ref right_data,
ref left_data,
ref right_hasher,
..
} = self;
Self::get(right, right_data, left_data, right_hasher)
}
pub fn remove_left<Q: ?Sized>(&mut self, left: &Q) -> Option<R>
where
L: Borrow<Q>,
Q: Hash + Eq,
{
let &mut BiMap {
ref mut len,
ref mut left_data,
ref mut right_data,
ref left_hasher,
ref right_hasher,
} = self;
Self::remove(left, left_data, right_data, left_hasher, right_hasher, len)
.map(|(_key, value)| value)
}
pub fn remove_right<Q: ?Sized>(&mut self, right: &Q) -> Option<L>
where
R: Borrow<Q>,
Q: Hash + Eq,
{
let &mut BiMap {
ref mut len,
ref mut left_data,
ref mut right_data,
ref left_hasher,
ref right_hasher,
} = self;
Self::remove(right, right_data, left_data, right_hasher, left_hasher, len)
.map(|(_key, value)| value)
}
}
impl<L, R, LH, RH, B> PartialEq for BiMap<L, R, LH, RH, B>
where
L: Hash + Eq,
R: Hash + Eq,
LH: BuildHasher,
RH: BuildHasher,
B: BitField,
{
fn eq(&self, other: &Self) -> bool {
self.len() == other.len()
&& self.iter().all(|(left, right)| {
other.get_left(left).map_or(false, |r| *right == *r)
&& other.get_right(right).map_or(false, |l| *left == *l)
})
}
}
impl<L, R, LH, RH, B> Eq for BiMap<L, R, LH, RH, B>
where
L: Hash + Eq,
R: Hash + Eq,
LH: BuildHasher,
RH: BuildHasher,
B: BitField,
{
}
impl<L, R, LH, RH, B> Debug for BiMap<L, R, LH, RH, B>
where
L: Debug,
R: Debug,
{
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
f.debug_map().entries(self.iter()).finish()
}
}
impl<'a, L, R, LH, RH, B> IntoIterator for &'a BiMap<L, R, LH, RH, B> {
type Item = (&'a L, &'a R);
type IntoIter = Iter<'a, L, R, B>;
fn into_iter(self) -> Self::IntoIter {
let &BiMap {
ref left_data,
ref right_data,
..
} = self;
Iter::new(left_data.iter(), right_data)
}
}
impl<L, R, LH, RH, B> IntoIterator for BiMap<L, R, LH, RH, B> {
type Item = (L, R);
type IntoIter = IntoIter<L, R, B>;
fn into_iter(self) -> Self::IntoIter {
let BiMap {
left_data,
right_data,
..
} = self;
IntoIter::new(left_data, right_data)
}
}
impl<L, R, LH, RH, B> FromIterator<(L, R)> for BiMap<L, R, LH, RH, B>
where
L: Hash + Eq,
R: Hash + Eq,
LH: BuildHasher + Default,
RH: BuildHasher + Default,
B: BitField,
{
fn from_iter<T: IntoIterator<Item = (L, R)>>(iter: T) -> Self {
let mut output = BiMapBuilder::new()
.left_hasher(Default::default())
.right_hasher(Default::default())
.bitfield::<B>()
.finish();
output.extend(iter);
output
}
}
impl<L, R, LH, RH, B> Extend<(L, R)> for BiMap<L, R, LH, RH, B>
where
L: Hash + Eq,
R: Hash + Eq,
LH: BuildHasher,
RH: BuildHasher,
B: BitField,
{
fn extend<T: IntoIterator<Item = (L, R)>>(&mut self, iter: T) {
for (left, right) in iter {
self.insert(left, right);
}
}
}
#[cfg(feature = "serde")]
impl<L, R, LH, RH, B> Serialize for BiMap<L, R, LH, RH, B>
where
L: Serialize,
R: Serialize,
{
fn serialize<S: Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
use serde::ser::SerializeSeq;
let mut seq = serializer.serialize_seq(Some(self.len))?;
for (ref left, ref right) in self.iter() {
seq.serialize_element(&(left, right))?;
}
seq.end()
}
}
#[cfg(feature = "serde")]
impl<'de, L, R, LH, RH, B> Deserialize<'de> for BiMap<L, R, LH, RH, B>
where
L: Hash + Eq + Deserialize<'de>,
R: Hash + Eq + Deserialize<'de>,
LH: BuildHasher + Default,
RH: BuildHasher + Default,
B: BitField,
{
fn deserialize<D: Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error> {
use std::fmt;
use std::marker::PhantomData;
use serde::de::{MapAccess, Visitor};
struct MapVisitor<L, R, LH, RH, B> {
marker: PhantomData<BiMap<L, R, LH, RH, B>>,
}
impl<'de, L, R, LH, RH, B> Visitor<'de> for MapVisitor<L, R, LH, RH, B>
where
L: Hash + Eq + Deserialize<'de>,
R: Hash + Eq + Deserialize<'de>,
LH: BuildHasher + Default,
RH: BuildHasher + Default,
B: BitField,
{
type Value = BiMap<L, R, LH, RH, B>;
fn expecting(&self, formatter: &mut fmt::Formatter) -> fmt::Result {
formatter.write_str("a map")
}
fn visit_map<A: MapAccess<'de>>(self, mut map: A) -> Result<Self::Value, A::Error> {
let builder = BiMapBuilder::new()
.left_hasher(Default::default())
.right_hasher(Default::default())
.bitfield::<B>();
let mut output = if let Some(size) = map.size_hint() {
builder.capacity(size).finish()
} else {
builder.finish()
};
while let Some((left, right)) = map.next_entry()? {
output.insert(left, right);
}
Ok(output)
}
}
let visitor = MapVisitor {
marker: PhantomData,
};
deserializer.deserialize_map(visitor)
}
}
#[cfg(test)]
mod test {
use crate::BiMap;
#[test]
fn test_iteration_empty() {
let map: BiMap<(), ()> = BiMap::new();
assert_eq!((&map).into_iter().next(), None);
assert_eq!(map.into_iter().next(), None);
}
}