use serde::{de, ser};
use std::borrow::Borrow;
use std::fmt::{self, Debug};
use std::hash::Hash;
use std::iter::FromIterator;
use std::marker::PhantomData;
use std::ops;
#[cfg(not(feature = "preserve_order"))]
use std::collections::{btree_map, BTreeMap};
#[cfg(feature = "preserve_order")]
use indexmap::{self, IndexMap};
#[derive(Clone, PartialEq)]
pub struct Map<K: Ord + Hash, V> {
map: MapImpl<K, V>,
}
#[cfg(not(feature = "preserve_order"))]
type MapImpl<K, V> = BTreeMap<K, V>;
#[cfg(feature = "preserve_order")]
type MapImpl<K, V> = IndexMap<K, V>;
impl<K: Ord + Hash, V> Map<K, V> {
#[inline]
pub fn new() -> Self {
Map {
map: MapImpl::new(),
}
}
#[cfg(not(feature = "preserve_order"))]
#[inline]
pub fn with_capacity(capacity: usize) -> Self {
let _ = capacity;
Map {
map: BTreeMap::new(),
}
}
#[cfg(feature = "preserve_order")]
#[inline]
pub fn with_capacity(capacity: usize) -> Self {
Map {
map: IndexMap::with_capacity(capacity),
}
}
#[inline]
pub fn clear(&mut self) {
self.map.clear()
}
#[inline]
pub fn get<Q: ?Sized>(&self, key: &Q) -> Option<&V>
where
K: Borrow<Q>,
Q: Ord + Eq + Hash,
{
self.map.get(key)
}
#[inline]
pub fn contains_key<Q: ?Sized>(&self, key: &Q) -> bool
where
K: Borrow<Q>,
Q: Ord + Eq + Hash,
{
self.map.contains_key(key)
}
#[inline]
pub fn get_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<&mut V>
where
K: Borrow<Q>,
Q: Ord + Eq + Hash,
{
self.map.get_mut(key)
}
#[inline]
pub fn insert(&mut self, k: K, v: V) -> Option<V> {
self.map.insert(k, v)
}
#[inline]
pub fn remove<Q: ?Sized>(&mut self, key: &Q) -> Option<V>
where
K: Borrow<Q>,
Q: Ord + Eq + Hash,
{
self.map.remove(key)
}
pub fn entry<S>(&mut self, key: S) -> Entry<'_, K, V>
where
S: Into<K>,
{
#[cfg(feature = "preserve_order")]
use indexmap::map::Entry as EntryImpl;
#[cfg(not(feature = "preserve_order"))]
use std::collections::btree_map::Entry as EntryImpl;
match self.map.entry(key.into()) {
EntryImpl::Vacant(vacant) => Entry::Vacant(VacantEntry { vacant }),
EntryImpl::Occupied(occupied) => Entry::Occupied(OccupiedEntry { occupied }),
}
}
#[inline]
pub fn len(&self) -> usize {
self.map.len()
}
#[inline]
pub fn is_empty(&self) -> bool {
self.map.is_empty()
}
#[inline]
pub fn iter(&self) -> Iter<'_, K, V> {
Iter {
iter: self.map.iter(),
}
}
#[inline]
pub fn iter_mut(&mut self) -> IterMut<'_, K, V> {
IterMut {
iter: self.map.iter_mut(),
}
}
#[inline]
pub fn keys(&self) -> Keys<'_, K, V> {
Keys {
iter: self.map.keys(),
}
}
#[inline]
pub fn values(&self) -> Values<'_, K, V> {
Values {
iter: self.map.values(),
}
}
}
impl<K: Ord + Hash, V> Default for Map<K, V> {
#[inline]
fn default() -> Self {
Map {
map: MapImpl::new(),
}
}
}
impl<'a, K, V, Q: ?Sized> ops::Index<&'a Q> for Map<K, V>
where
K: Ord + Hash + Borrow<Q>,
Q: Ord + Eq + Hash,
{
type Output = V;
fn index(&self, index: &Q) -> &V {
self.map.index(index)
}
}
impl<'a, K, V, Q: ?Sized> ops::IndexMut<&'a Q> for Map<K, V>
where
K: Ord + Hash + Borrow<Q>,
Q: Ord + Eq + Hash,
{
fn index_mut(&mut self, index: &Q) -> &mut V {
self.map.get_mut(index).expect("no entry found for key")
}
}
impl<K: Ord + Hash + Debug, V: Debug> Debug for Map<K, V> {
#[inline]
fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> Result<(), fmt::Error> {
self.map.fmt(formatter)
}
}
impl<K: Ord + Hash + ser::Serialize, V: ser::Serialize> ser::Serialize for Map<K, V> {
#[inline]
fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
where
S: ser::Serializer,
{
use serde::ser::SerializeMap;
let mut map = serializer.serialize_map(Some(self.len()))?;
for (k, v) in self {
map.serialize_key(k)?;
map.serialize_value(v)?;
}
map.end()
}
}
impl<'de, K, V> de::Deserialize<'de> for Map<K, V>
where
K: Ord + Hash + de::Deserialize<'de>,
V: de::Deserialize<'de>,
{
#[inline]
fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
where
D: de::Deserializer<'de>,
{
struct Visitor<VK, VV>(PhantomData<(VK, VV)>);
impl<'de, VK, VV> de::Visitor<'de> for Visitor<VK, VV>
where
VK: Hash + Ord + de::Deserialize<'de>,
VV: de::Deserialize<'de>,
{
type Value = Map<VK, VV>;
fn expecting(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
formatter.write_str("a map")
}
#[inline]
fn visit_unit<E>(self) -> Result<Self::Value, E>
where
E: de::Error,
{
Ok(Map::new())
}
#[inline]
fn visit_map<V>(self, mut visitor: V) -> Result<Self::Value, V::Error>
where
V: de::MapAccess<'de>,
{
let mut values = Map::new();
while let Some((key, value)) = visitor.next_entry()? {
values.insert(key, value);
}
Ok(values)
}
}
deserializer.deserialize_map(Visitor(PhantomData::<(K, V)>))
}
}
impl<K: Ord + Hash, V> FromIterator<(K, V)> for Map<K, V> {
fn from_iter<T>(iter: T) -> Self
where
T: IntoIterator<Item = (K, V)>,
{
Map {
map: FromIterator::from_iter(iter),
}
}
}
impl<K: Ord + Hash, V> Extend<(K, V)> for Map<K, V> {
fn extend<T>(&mut self, iter: T)
where
T: IntoIterator<Item = (K, V)>,
{
self.map.extend(iter);
}
}
macro_rules! delegate_iterator {
(($name:ident [$($generics_decl:tt)*], $($generics:tt)*) => $item:ty) => {
impl <$($generics_decl)*> Iterator for $name $($generics)* {
type Item = $item;
#[inline]
fn next(&mut self) -> Option<Self::Item> {
self.iter.next()
}
#[inline]
fn size_hint(&self) -> (usize, Option<usize>) {
self.iter.size_hint()
}
}
impl <$($generics_decl)*> DoubleEndedIterator for $name $($generics)* {
#[inline]
fn next_back(&mut self) -> Option<Self::Item> {
self.iter.next_back()
}
}
impl <$($generics_decl)*> ExactSizeIterator for $name $($generics)* {
#[inline]
fn len(&self) -> usize {
self.iter.len()
}
}
}
}
pub enum Entry<'a, K: Ord + Hash, V> {
Vacant(VacantEntry<'a, K, V>),
Occupied(OccupiedEntry<'a, K, V>),
}
pub struct VacantEntry<'a, K: Ord + Hash, V> {
vacant: VacantEntryImpl<'a, K, V>,
}
pub struct OccupiedEntry<'a, K: Ord + Hash, V> {
occupied: OccupiedEntryImpl<'a, K, V>,
}
#[cfg(not(feature = "preserve_order"))]
type VacantEntryImpl<'a, K, V> = btree_map::VacantEntry<'a, K, V>;
#[cfg(feature = "preserve_order")]
type VacantEntryImpl<'a, K, V> = indexmap::map::VacantEntry<'a, K, V>;
#[cfg(not(feature = "preserve_order"))]
type OccupiedEntryImpl<'a, K, V> = btree_map::OccupiedEntry<'a, K, V>;
#[cfg(feature = "preserve_order")]
type OccupiedEntryImpl<'a, K, V> = indexmap::map::OccupiedEntry<'a, K, V>;
impl<'a, K: Ord + Hash, V> Entry<'a, K, V> {
pub fn key(&self) -> &K {
match *self {
Entry::Vacant(ref e) => e.key(),
Entry::Occupied(ref e) => e.key(),
}
}
pub fn or_insert(self, default: V) -> &'a mut V {
match self {
Entry::Vacant(entry) => entry.insert(default),
Entry::Occupied(entry) => entry.into_mut(),
}
}
pub fn or_insert_with<F>(self, default: F) -> &'a mut V
where
F: FnOnce() -> V,
{
match self {
Entry::Vacant(entry) => entry.insert(default()),
Entry::Occupied(entry) => entry.into_mut(),
}
}
}
impl<'a, K: Ord + Hash, V> VacantEntry<'a, K, V> {
#[inline]
pub fn key(&self) -> &K {
self.vacant.key()
}
#[inline]
pub fn insert(self, value: V) -> &'a mut V {
self.vacant.insert(value)
}
}
impl<'a, K: Ord + Hash, V> OccupiedEntry<'a, K, V> {
#[inline]
pub fn key(&self) -> &K {
self.occupied.key()
}
#[inline]
pub fn get(&self) -> &V {
self.occupied.get()
}
#[inline]
pub fn get_mut(&mut self) -> &mut V {
self.occupied.get_mut()
}
#[inline]
pub fn into_mut(self) -> &'a mut V {
self.occupied.into_mut()
}
#[inline]
pub fn insert(&mut self, value: V) -> V {
self.occupied.insert(value)
}
#[inline]
pub fn remove(self) -> V {
self.occupied.remove()
}
}
impl<'a, K: Ord + Hash, V> IntoIterator for &'a Map<K, V> {
type Item = (&'a K, &'a V);
type IntoIter = Iter<'a, K, V>;
#[inline]
fn into_iter(self) -> Self::IntoIter {
Iter {
iter: self.map.iter(),
}
}
}
pub struct Iter<'a, K: Ord + Hash, V> {
iter: IterImpl<'a, K, V>,
}
#[cfg(not(feature = "preserve_order"))]
type IterImpl<'a, K, V> = btree_map::Iter<'a, K, V>;
#[cfg(feature = "preserve_order")]
type IterImpl<'a, K, V> = indexmap::map::Iter<'a, K, V>;
delegate_iterator!((Iter['a, K: Ord + Hash, V], <'a, K, V>) => (&'a K, &'a V));
impl<'a, K: Ord + Hash, V> IntoIterator for &'a mut Map<K, V> {
type Item = (&'a K, &'a mut V);
type IntoIter = IterMut<'a, K, V>;
#[inline]
fn into_iter(self) -> Self::IntoIter {
IterMut {
iter: self.map.iter_mut(),
}
}
}
pub struct IterMut<'a, K: Ord + Hash, V> {
iter: IterMutImpl<'a, K, V>,
}
#[cfg(not(feature = "preserve_order"))]
type IterMutImpl<'a, K, V> = btree_map::IterMut<'a, K, V>;
#[cfg(feature = "preserve_order")]
type IterMutImpl<'a, K, V> = indexmap::map::IterMut<'a, K, V>;
delegate_iterator!((IterMut['a, K: Ord + Hash, V], <'a, K, V>) => (&'a K, &'a mut V));
impl<K: Ord + Hash, V> IntoIterator for Map<K, V> {
type Item = (K, V);
type IntoIter = IntoIter<K, V>;
#[inline]
fn into_iter(self) -> Self::IntoIter {
IntoIter {
iter: self.map.into_iter(),
}
}
}
pub struct IntoIter<K: Ord + Hash, V> {
iter: IntoIterImpl<K, V>,
}
#[cfg(not(feature = "preserve_order"))]
type IntoIterImpl<K, V> = btree_map::IntoIter<K, V>;
#[cfg(feature = "preserve_order")]
type IntoIterImpl<K, V> = indexmap::map::IntoIter<K, V>;
delegate_iterator!((IntoIter[K: Ord + Hash, V], <K, V>) => (K, V));
pub struct Keys<'a, K: Ord + Hash, V> {
iter: KeysImpl<'a, K, V>,
}
#[cfg(not(feature = "preserve_order"))]
type KeysImpl<'a, K, V> = btree_map::Keys<'a, K, V>;
#[cfg(feature = "preserve_order")]
type KeysImpl<'a, K, V> = indexmap::map::Keys<'a, K, V>;
delegate_iterator!((Keys['a, K: Ord + Hash, V], <'a, K, V>) => &'a K);
pub struct Values<'a, K: Ord + Hash, V> {
iter: ValuesImpl<'a, K, V>,
}
#[cfg(not(feature = "preserve_order"))]
type ValuesImpl<'a, K, V> = btree_map::Values<'a, K, V>;
#[cfg(feature = "preserve_order")]
type ValuesImpl<'a, K, V> = indexmap::map::Values<'a, K, V>;
delegate_iterator!((Values['a, K: Ord + Hash, V], <'a, K, V>) => &'a V);