#![feature(trusted_len, drain_filter)]
#[cfg(feature="serde")]
extern crate serde;
#[cfg(feature = "petgraph")]
extern crate petgraph;
extern crate fixedbitset;
use std::marker::PhantomData;
use std::iter::{self, FromIterator};
use std::borrow::Borrow;
use std::ops::{Index, IndexMut};
use std::fmt::{self, Debug, Formatter};
pub mod set;
pub mod table;
#[cfg(feature="serde")]
mod serialization;
#[cfg(feature="petgraph")]
mod graph;
mod utils;
mod integer_id;
pub use set::IdSet;
pub use integer_id::IntegerId;
use table::{
EntryTable, EntryIterable, DenseEntryTable,
SafeEntries, SafeEntriesMut, DirectEntryTable
};
pub type DirectIdMap<K, V> = IdMap<K, V, DirectEntryTable<K, V>>;
pub type OrderedIdMap<K, V> = IdMap<K, V, DenseEntryTable<K, V>>;
pub struct IdMap<K: IntegerId, V, T: EntryTable<K, V> = DenseEntryTable<K, V>> {
entries: T,
marker: PhantomData<DirectEntryTable<K, V>>
}
impl<K: IntegerId, V> IdMap<K, V, DirectEntryTable<K, V>> {
#[inline]
pub fn new_direct() -> Self {
IdMap::new_other()
}
#[inline]
pub fn with_capacity_direct(capacity: usize) -> Self {
IdMap::with_capacity_other(capacity)
}
}
impl<K: IntegerId, V> IdMap<K, V> {
#[inline]
pub fn new() -> Self {
IdMap {
entries: DenseEntryTable::new(),
marker: PhantomData
}
}
#[inline]
pub fn with_capacity(capacity: usize) -> Self {
IdMap {
entries: DenseEntryTable::with_capacity(capacity),
marker: PhantomData
}
}
}
impl<K: IntegerId, V, T: EntryTable<K, V>> IdMap<K, V, T> {
#[inline]
pub fn new_other() -> Self {
IdMap {
entries: T::new(),
marker: PhantomData
}
}
#[inline]
pub fn with_capacity_other(capacity: usize) -> Self {
IdMap {
entries: T::with_capacity(capacity),
marker: PhantomData
}
}
#[inline]
pub fn is_empty(&self) -> bool {
self.entries.is_empty()
}
#[inline]
pub fn len(&self) -> usize {
self.entries.len()
}
pub fn max_id(&self) -> Option<u64> {
self.entries.max_id()
}
#[inline]
pub fn contains_key<Q: Borrow<K>>(&self, key: Q) -> bool {
self.get(key).is_some()
}
#[inline]
pub fn get<Q: Borrow<K>>(&self, key: Q) -> Option<&V> {
let key = key.borrow();
self.entries.get(key)
}
#[inline]
pub fn get_mut<Q: Borrow<K>>(&mut self, key: Q) -> Option<&mut V> {
let key = key.borrow();
self.entries.get_mut(key)
}
#[inline]
pub fn insert(&mut self, key: K, value: V) -> Option<V> {
self.entries.insert(key, value)
}
#[inline]
pub fn remove<Q: Borrow<K>>(&mut self, key: Q) -> Option<V> {
let key = key.borrow();
self.entries.swap_remove(key)
}
#[inline]
pub fn entry(&mut self, key: K) -> Entry<K, V, T> {
if self.entries.get(&key).is_some() {
Entry::Occupied(OccupiedEntry {
map: self, key
})
} else {
Entry::Vacant(VacantEntry { key, map: self })
}
}
#[inline]
pub fn iter(&self) -> Iter<K, V, T> {
Iter(SafeEntries::new(&self.entries))
}
#[inline]
pub fn iter_mut(&mut self) -> IterMut<K, V, T> {
IterMut(SafeEntriesMut::new(&mut self.entries))
}
#[inline]
pub fn keys(&self) -> Keys<K, V, T> {
Keys(SafeEntries::new(&self.entries))
}
#[inline]
pub fn values(&self) -> Values<K, V, T> {
Values(SafeEntries::new(&self.entries))
}
#[inline]
pub fn values_mut(&mut self) -> ValuesMut<K, V, T> {
ValuesMut(SafeEntriesMut::new(&mut self.entries))
}
#[inline]
pub fn clear(&mut self) {
self.entries.clear();
}
#[inline]
pub fn retain<F>(&mut self, func: F) where F: FnMut(&K, &mut V) -> bool {
self.entries.retain(func);
}
#[inline]
pub fn reserve(&mut self, amount: usize) {
self.entries.reserve(amount);
}
#[inline]
pub fn raw_debug(&self) -> RawDebug<K, V, T> where K: Debug, V: Debug {
RawDebug(self)
}
}
impl<K, V, T> Clone for IdMap<K, V, T> where K: IntegerId + Clone, V: Clone, T: EntryTable<K, V> {
#[inline]
fn clone(&self) -> Self {
IdMap {
entries: self.entries.cloned(),
marker: PhantomData
}
}
}
pub struct RawDebug<'a, K: IntegerId + 'a, V: 'a, T: 'a + EntryTable<K, V>>(&'a IdMap<K, V, T>);
impl<'a, K, V, T> Debug for RawDebug<'a, K, V, T>
where K: IntegerId + Debug, V: Debug, T: EntryTable<K, V>, K: 'a, V: 'a, T: 'a {
fn fmt(&self, f: &mut Formatter) -> fmt::Result {
f.debug_struct("IdMap")
.field("entries", self.0.entries.raw_debug())
.finish()
}
}
impl<K, V1, T1, V2, T2> PartialEq<IdMap<K, V2, T2>> for IdMap<K, V1, T1>
where K: IntegerId, V1: PartialEq<V2>,
T1: EntryTable<K, V1>, T2: EntryTable<K, V2>, {
fn eq(&self, other: &IdMap<K, V2, T2>) -> bool {
if self.entries.len() != other.entries.len() {
return false;
}
self.iter().all(|(key, value)| {
other.get(key).map_or(false, |other_value| value == other_value)
})
}
}
#[macro_export]
macro_rules! idmap {
($($key:expr => $value:expr),*) => {
{
let entries = vec![$(($key, $value)),*];
let mut result = $crate::IdMap::with_capacity(entries.len());
result.extend(entries);
result
}
};
($($key:expr => $value:expr,)*) => (idmap!($($key => $value),*));
}
#[macro_export]
macro_rules! direct_idmap {
($($key:expr => $value:expr),*) => {
{
let entries = vec![$(($key, $value)),*];
let mut result = $crate::IdMap::with_capacity_direct(entries.len());
result.extend(entries);
result
}
};
($($key:expr => $value:expr,)*) => (direct_idmap!($($key => $value),*));
}
#[macro_export]
macro_rules! idset {
($($element:expr),*) => {
{
let entries = vec![$($element),*];
let mut result = $crate::IdSet::with_capacity(entries.len());
result.extend(entries);
result
}
};
}
impl<K: IntegerId, V, T: EntryTable<K, V>> Default for IdMap<K, V, T> {
#[inline]
fn default() -> Self {
IdMap::new_other()
}
}
impl<K: IntegerId, V, T: EntryTable<K, V>> Index<K> for IdMap<K, V, T> {
type Output = V;
#[inline]
fn index(&self, key: K) -> &V {
&self[&key]
}
}
impl<K: IntegerId, V, T: EntryTable<K, V>> IndexMut<K> for IdMap<K, V, T> {
#[inline]
fn index_mut(&mut self, key: K) -> &mut V {
&mut self[&key]
}
}
impl<'a, K: IntegerId, V, T: EntryTable<K, V>> Index<&'a K> for IdMap<K, V, T> {
type Output = V;
#[inline]
fn index(&self, key: &'a K) -> &V {
if let Some(value) = self.get(key) {
value
} else {
panic!("Missing entry for {:?}", key)
}
}
}
impl<'a, K: IntegerId, V, T: EntryTable<K, V>> IndexMut<&'a K> for IdMap<K, V, T> {
#[inline]
fn index_mut(&mut self, key: &'a K) -> &mut V {
if let Some(value) = self.get_mut(key) {
value
} else {
panic!("Missing entry for {:?}", key)
}
}
}
impl<K: IntegerId, V: Debug, T: EntryTable<K, V>> Debug for IdMap<K, V, T> {
fn fmt(&self, f: &mut Formatter) -> fmt::Result {
let mut d = f.debug_map();
for (key, value) in self.iter() {
d.entry(key, value);
}
d.finish()
}
}
pub enum Entry<'a, K: IntegerId + 'a, V: 'a, T: 'a + EntryTable<K, V>> {
Occupied(OccupiedEntry<'a, K, V, T>),
Vacant(VacantEntry<'a, K, V, T>)
}
impl<'a, K: IntegerId + 'a, V: 'a, T: EntryTable<K, V>> Entry<'a, K, V, T> {
#[inline]
pub fn or_insert(self, value: V) -> &'a mut V {
self.or_insert_with(|| value)
}
#[inline]
pub fn or_insert_with<F>(self, func: F) -> &'a mut V where F: FnOnce() -> V {
match self {
Entry::Occupied(entry) => entry.value(),
Entry::Vacant(entry) => entry.or_insert_with(func)
}
}
}
pub struct OccupiedEntry<'a, K: IntegerId + 'a, V: 'a, T: 'a + EntryTable<K, V>> {
map: &'a mut IdMap<K, V, T>,
key: K,
}
impl<'a, K: IntegerId + 'a, V: 'a, T: EntryTable<K, V>> OccupiedEntry<'a, K, V, T> {
#[inline]
pub fn key(&self) -> &K {
&self.key
}
#[inline]
pub fn value(self) -> &'a mut V {
self.map.entries.get_mut(&self.key).unwrap()
}
#[inline]
pub fn get(&self) -> &V {
self.map.entries.get(&self.key).unwrap()
}
#[inline]
pub fn get_mut(&mut self) -> &mut V {
self.map.entries.get_mut(&self.key).unwrap()
}
#[inline]
pub fn insert(self, value: V) -> V {
self.map.entries.insert(self.key, value).unwrap()
}
#[inline]
pub fn remove(self) -> V {
self.map.entries.swap_remove(&self.key).unwrap()
}
}
pub struct VacantEntry<'a, K: IntegerId + 'a, V: 'a, T: EntryTable<K, V> + 'a> {
map: &'a mut IdMap<K, V, T>,
key: K,
}
impl<'a, K: IntegerId + 'a, V: 'a, T: EntryTable<K, V> + 'a> VacantEntry<'a, K, V, T> {
#[inline]
pub fn insert(self, value: V) -> &'a mut V {
self.map.entries.insert_vacant(self.key, value)
}
#[inline]
pub fn or_insert_with<F>(self, func: F) -> &'a mut V where F: FnOnce() -> V {
self.insert(func())
}
}
impl<K: IntegerId, V, T: EntryTable<K, V>> IntoIterator for IdMap<K, V, T> {
type Item = (K, V);
type IntoIter = <T as IntoIterator>::IntoIter;
#[inline]
fn into_iter(self) -> Self::IntoIter {
self.entries.into_iter()
}
}
impl<'a, K: IntegerId + 'a, V: 'a, T: 'a> IntoIterator for &'a IdMap<K, V, T>
where T: EntryTable<K, V> {
type Item = (&'a K, &'a V);
type IntoIter = Iter<'a, K, V, T>;
#[inline]
fn into_iter(self) -> Self::IntoIter {
self.iter()
}
}
impl<'a, K, V, T> IntoIterator for &'a mut IdMap<K, V, T>
where T: EntryTable<K, V>, K: IntegerId + 'a, V: 'a, T: 'a {
type Item = (&'a K, &'a mut V);
type IntoIter = IterMut<'a, K, V, T>;
#[inline]
fn into_iter(self) -> Self::IntoIter {
self.iter_mut()
}
}
impl<K: IntegerId, V, T: EntryTable<K, V>> Extend<(K, V)> for IdMap<K, V, T> {
fn extend<I: IntoIterator<Item=(K, V)>>(&mut self, iter: I) {
let iter = iter.into_iter();
if let Some(size) = iter.size_hint().1 {
self.reserve(size);
}
for (key, value) in iter {
self.insert(key, value);
}
}
}
impl<K: IntegerId, V, T: EntryTable<K, V>> FromIterator<(K, V)> for IdMap<K, V, T> {
#[inline]
fn from_iter<I>(iterable: I) -> Self where I: IntoIterator<Item=(K, V)> {
let mut result = Self::new_other();
result.extend(iterable);
result
}
}
impl<'a, K, V, T> FromIterator<(&'a K, &'a V)> for IdMap<K, V, T>
where K: IntegerId + Clone + 'a, V: Clone + 'a, T: EntryTable<K, V> {
#[inline]
fn from_iter<I>(iterable: I) -> Self where I: IntoIterator<Item=(&'a K, &'a V)> {
let mut result = Self::new_other();
result.extend(iterable);
result
}
}
impl<'a, K, V, T> Extend<(&'a K, &'a V)> for IdMap<K, V, T>
where K: IntegerId + Clone + 'a, V: Clone + 'a, T: EntryTable<K, V> {
#[inline]
fn extend<I: IntoIterator<Item=(&'a K, &'a V)>>(&mut self, iter: I) {
self.extend(iter.into_iter().map(|(key, value)| (key.clone(), value.clone())))
}
}
pub struct Iter<'a, K, V, I>(SafeEntries<'a, K, V, I>)
where K: IntegerId + 'a, V: 'a, I: 'a + EntryIterable<K, V>;
impl <'a, K, V, I> Iterator for Iter<'a, K, V, I>
where K: IntegerId + 'a, V: 'a, I: 'a + EntryIterable<K, V> {
type Item = (&'a K, &'a V);
#[inline]
fn size_hint(&self) -> (usize, Option<usize>) {
self.0.size_hint()
}
#[inline]
fn next(&mut self) -> Option<(&'a K, &'a V)> {
self.0.next().map(|(_, key, value)| (key, value))
}
}
impl <'a, K, V, I> iter::FusedIterator for Iter<'a, K, V, I>
where K: IntegerId + 'a, V: 'a, I: 'a + EntryIterable<K, V>, I: iter::FusedIterator {}
impl <'a, K, V, I> iter::ExactSizeIterator for Iter<'a, K, V, I>
where K: IntegerId + 'a, V: 'a, I: 'a + EntryIterable<K, V>, I: iter::ExactSizeIterator {}
unsafe impl <'a, K, V, I> iter::TrustedLen for Iter<'a, K, V, I>
where K: IntegerId + 'a, V: 'a, I: 'a + EntryIterable<K, V>, I: iter::TrustedLen {}
impl<'a, K, V, I> Clone for Iter<'a, K, V, I>
where K: IntegerId + 'a, V: 'a, I: 'a + EntryIterable<K, V> {
#[inline]
fn clone(&self) -> Self {
Iter(self.0.clone())
}
}
impl<'a, K, V, I> Debug for Iter<'a, K, V, I>
where K: IntegerId + Debug + 'a, V: Debug + 'a, I: 'a + EntryIterable<K, V> {
fn fmt(&self, f: &mut Formatter) -> fmt::Result {
f.debug_tuple("Iter")
.field(&self.0)
.finish()
}
}
pub struct Keys<'a, K, V, I>(SafeEntries<'a, K, V, I>)
where K: IntegerId + 'a, V: 'a, I: 'a + EntryIterable<K, V>;
impl <'a, K, V, I> Iterator for Keys<'a, K, V, I>
where K: IntegerId + 'a, V: 'a, I: 'a + EntryIterable<K, V> {
type Item = &'a K;
#[inline]
fn size_hint(&self) -> (usize, Option<usize>) {
self.0.size_hint()
}
#[inline]
fn next(&mut self) -> Option<&'a K> {
self.0.next().map(|(_, key, _)| key)
}
}
impl <'a, K, V, I> iter::FusedIterator for Keys<'a, K, V, I>
where K: IntegerId + 'a, V: 'a, I: 'a + EntryIterable<K, V>, I: iter::FusedIterator {}
impl <'a, K, V, I> iter::ExactSizeIterator for Keys<'a, K, V, I>
where K: IntegerId + 'a, V: 'a, I: 'a + EntryIterable<K, V>, I: iter::ExactSizeIterator {}
unsafe impl <'a, K, V, I> iter::TrustedLen for Keys<'a, K, V, I>
where K: IntegerId + 'a, V: 'a, I: 'a + EntryIterable<K, V>, I: iter::TrustedLen {}
impl<'a, K, V, I> Clone for Keys<'a, K, V, I>
where K: IntegerId + 'a, V: 'a, I: 'a + EntryIterable<K, V> {
#[inline]
fn clone(&self) -> Self {
Keys(self.0.clone())
}
}
impl<'a, K, V, I> Debug for Keys<'a, K, V, I>
where K: IntegerId + Debug + 'a, V: Debug + 'a, I: 'a + EntryIterable<K, V>{
fn fmt(&self, f: &mut Formatter) -> fmt::Result {
f.debug_tuple("Keys")
.field(&self.0)
.finish()
}
}
pub struct Values<'a, K, V, I>(SafeEntries<'a, K, V, I>)
where K: IntegerId + 'a, V: 'a, I: 'a + EntryIterable<K, V>;
impl <'a, K, V, I> Iterator for Values<'a, K, V, I>
where K: IntegerId + 'a, V: 'a, I: 'a + EntryIterable<K, V> {
type Item = &'a V;
#[inline]
fn size_hint(&self) -> (usize, Option<usize>) {
self.0.size_hint()
}
#[inline]
fn next(&mut self) -> Option<&'a V> {
self.0.next().map(|(_, _, value)| value)
}
}
impl <'a, K, V, I> iter::FusedIterator for Values<'a, K, V, I>
where K: IntegerId + 'a, V: 'a, I: 'a + EntryIterable<K, V>, I: iter::FusedIterator {}
impl <'a, K, V, I> iter::ExactSizeIterator for Values<'a, K, V, I>
where K: IntegerId + 'a, V: 'a, I: 'a + EntryIterable<K, V>, I: iter::ExactSizeIterator {}
unsafe impl <'a, K, V, I> iter::TrustedLen for Values<'a, K, V, I>
where K: IntegerId + 'a, V: 'a, I: 'a + EntryIterable<K, V>, I: iter::TrustedLen {}
impl<'a, K, V, I> Clone for Values<'a, K, V, I>
where K: IntegerId + 'a, V: 'a, I: 'a + EntryIterable<K, V> {
#[inline]
fn clone(&self) -> Self {
Values(self.0.clone())
}
}
impl<'a, K, V, I> Debug for Values<'a, K, V, I>
where K: IntegerId + Debug + 'a, V: Debug + 'a, I: 'a + EntryIterable<K, V> {
fn fmt(&self, f: &mut Formatter) -> fmt::Result {
f.debug_tuple("Values")
.field(&self.0)
.finish()
}
}
pub struct ValuesMut<'a, K, V, I>(SafeEntriesMut<'a, K, V, I>)
where K: IntegerId + 'a, V: 'a, I: 'a + EntryIterable<K, V>;
impl <'a, K, V, I> Iterator for ValuesMut<'a, K, V, I>
where K: IntegerId + 'a, V: 'a, I: 'a + EntryIterable<K, V> {
type Item = &'a mut V;
#[inline]
fn size_hint(&self) -> (usize, Option<usize>) {
self.0.size_hint()
}
#[inline]
fn next(&mut self) -> Option<&'a mut V> {
self.0.next().map(|(_, _, value)| value)
}
}
impl <'a, K, V, I> iter::FusedIterator for ValuesMut<'a, K, V, I>
where K: IntegerId + 'a, V: 'a, I: 'a + EntryIterable<K, V>, I: iter::FusedIterator {}
impl <'a, K, V, I> iter::ExactSizeIterator for ValuesMut<'a, K, V, I>
where K: IntegerId + 'a, V: 'a, I: 'a + EntryIterable<K, V>, I: iter::ExactSizeIterator {}
unsafe impl <'a, K, V, I> iter::TrustedLen for ValuesMut<'a, K, V, I>
where K: IntegerId + 'a, V: 'a, I: 'a + EntryIterable<K, V>, I: iter::TrustedLen {}
pub struct IterMut<'a, K, V, I>(SafeEntriesMut<'a, K, V, I>)
where K: IntegerId + 'a, V: 'a, I: 'a + EntryIterable<K, V>;
impl <'a, K, V, I> Iterator for IterMut<'a, K, V, I>
where K: IntegerId + 'a, V: 'a, I: 'a + EntryIterable<K, V> {
type Item = (&'a K, &'a mut V);
#[inline]
fn size_hint(&self) -> (usize, Option<usize>) {
self.0.size_hint()
}
#[inline]
fn next(&mut self) -> Option<(&'a K, &'a mut V)> {
self.0.next().map(|(_, key, value)| (key, value))
}
}
impl <'a, K, V, I> iter::FusedIterator for IterMut<'a, K, V, I>
where K: IntegerId + 'a, V: 'a, I: 'a + EntryIterable<K, V>, I: iter::FusedIterator {}
impl <'a, K, V, I> iter::ExactSizeIterator for IterMut<'a, K, V, I>
where K: IntegerId + 'a, V: 'a, I: 'a + EntryIterable<K, V>, I: iter::ExactSizeIterator {}
unsafe impl <'a, K, V, I> iter::TrustedLen for IterMut<'a, K, V, I>
where K: IntegerId + 'a, V: 'a, I: 'a + EntryIterable<K, V>, I: iter::TrustedLen {}
#[doc(hidden)]
#[cold] #[inline(never)]
pub fn _invalid_id(id: u64) -> ! {
panic!("ID is invalid: {}", id);
}