// codesnip-guard: VecMap
#[cfg_attr(any(),rustfmt::skip)]pub use self::vec_map::VecMap;#[cfg_attr(any(),rustfmt::skip)]mod vec_map{use super::{Container,ContainerEntry};use std::{fmt::{self,Debug},iter::{FilterMap,Flatten,Map,repeat_with},mem::replace,slice};#[doc=" Stores keys at distinct indices supplied by `key_to_index`."]#[derive(Clone,PartialEq,Eq,PartialOrd,Ord,Hash)]pub struct VecMap<const FIXED:bool,K,V,F>{pub data:Vec<Option<(K,V)>>,key_to_index:F}impl<const FIXED:bool,K,V,F>Debug for VecMap<FIXED,K,V,F>where K:Debug,V:Debug{fn fmt(&self,f:&mut fmt::Formatter<'_>)->fmt::Result{f.debug_map().entries(self.data.iter().flatten().map(|(k,v):&(K,V)|(k,v))).finish()}}#[derive(Debug)]pub struct Entry<'a,K,V>{key:K,entry:&'a mut Option<(K,V)>}impl<K,V,F>VecMap<false,K,V,F>{pub fn new(key_to_index:F)->Self where F:Fn(&K)->usize{Self::with_capacity(0,key_to_index)}pub fn with_capacity(capacity:usize,key_to_index:F)->Self where F:Fn(&K)->usize{Self{data:Vec::with_capacity(capacity),key_to_index}}}impl<K,V,F>VecMap<true,K,V,F>{#[doc=" Fixed storage: every key's index must be in `0..len`."]pub fn with_len(len:usize,key_to_index:F)->Self where F:Fn(&K)->usize{Self{data:repeat_with(| |None).take(len).collect(),key_to_index}}}impl<const FIXED:bool,K,V,F>Container for VecMap<FIXED,K,V,F>where F:Fn(&K)->usize{type Key=K;type Value=V;type Entry<'a>=Entry<'a,K,V>where Self:'a,Self::Key:'a,Self::Value:'a;type Iter<'a>=Map<Flatten<slice::Iter<'a,Option<(K,V)>>>,fn(&(K,V))->(&K,&V)>where Self:'a,Self::Key:'a,Self::Value:'a;type Drain<'a>=FilterMap<slice::IterMut<'a,Option<(K,V)>>,fn(&mut Option<(K,V)>)->Option<(K,V)>>where Self:'a,Self::Key:'a,Self::Value:'a;fn get(&self,key:&Self::Key)->Option<&Self::Value>{let index=(self.key_to_index)(key);self.data.get(index).and_then(|x|x.as_ref()).map(|x|&x.1)}fn get_mut(&mut self,key:&Self::Key)->Option<&mut Self::Value>{let index=(self.key_to_index)(key);self.data.get_mut(index).and_then(|x|x.as_mut()).map(|x|&mut x.1)}fn insert(&mut self,key:Self::Key,value:Self::Value)->Option<Self::Value>{let index=(self.key_to_index)(&key);let entry=if FIXED{self.data.get_mut(index).unwrap()}else{if index>=self.data.len(){self.data.resize_with(index+1,Default::default);}unsafe{self.data.get_unchecked_mut(index)}};match entry{Some((_,v))=>Some(replace(v,value)),entry=>{*entry=Some((key,value));None}}}fn remove(&mut self,key:&Self::Key)->Option<Self::Value>{let index=(self.key_to_index)(key);self.data.get_mut(index).and_then(|x|x.take()).map(|x|x.1)}fn entry(&mut self,key:Self::Key)->Self::Entry<'_>{let index=(self.key_to_index)(&key);let entry=if FIXED{self.data.get_mut(index).unwrap()}else{if index>=self.data.len(){self.data.resize_with(index+1,Default::default);}unsafe{self.data.get_unchecked_mut(index)}};Entry{key,entry}}fn iter(&self)->Self::Iter<'_>{self.data.iter().flatten().map(|(k,v)|(k,v))}fn drain(&mut self)->Self::Drain<'_>{self.data.iter_mut().filter_map(Option::take)}}impl<'a,K,V>ContainerEntry<'a>for Entry<'a,K,V>{type Key=K;type Value=V;fn or_default(self)->&'a mut Self::Value where Self::Value:Default{match self.entry{Some((_,value))=>value,entry=>{*entry=Some((self.key,Default::default()));unsafe{&mut entry.as_mut().unwrap_unchecked().1}}}}fn or_insert(self,default:Self::Value)->&'a mut Self::Value{match self.entry{Some((_,value))=>value,entry=>{*entry=Some((self.key,default));unsafe{&mut entry.as_mut().unwrap_unchecked().1}}}}fn or_insert_with<F>(self,default:F)->&'a mut Self::Value where F:FnOnce()->Self::Value{match self.entry{Some((_,value))=>value,entry=>{*entry=Some((self.key,default()));unsafe{&mut entry.as_mut().unwrap_unchecked().1}}}}fn or_insert_with_key<F>(self,default:F)->&'a mut Self::Value where F:FnOnce(&Self::Key)->Self::Value{match self.entry{Some((_,value))=>value,entry=>{let default=default(&self.key);*entry=Some((self.key,default));unsafe{&mut entry.as_mut().unwrap_unchecked().1}}}}fn key(&self)->&Self::Key{&self.key}fn and_modify<F>(self,f:F)->Self where F:FnOnce(&mut Self::Value){if let Some((_,value))=self.entry{f(value);}self}}}
// codesnip-guard: container
#[cfg_attr(any(),rustfmt::skip)]pub use self::container::{Container,ContainerEntry};#[cfg_attr(any(),rustfmt::skip)]mod container{use std::{cmp::Ord,collections::{BTreeMap,HashMap,btree_map,hash_map},hash::{BuildHasher,Hash},iter::FusedIterator};pub trait Container{type Key;type Value;type Entry<'a>:ContainerEntry<'a,Key=Self::Key,Value=Self::Value>where Self:'a,Self::Key:'a,Self::Value:'a;type Iter<'a>:Iterator<Item=(&'a Self::Key,&'a Self::Value)>where Self:'a,Self::Key:'a,Self::Value:'a;type Drain<'a>:Iterator<Item=(Self::Key,Self::Value)>where Self:'a,Self::Key:'a,Self::Value:'a;fn get(&self,key:&Self::Key)->Option<&Self::Value>;fn get_mut(&mut self,key:&Self::Key)->Option<&mut Self::Value>;fn insert(&mut self,key:Self::Key,value:Self::Value)->Option<Self::Value>;fn remove(&mut self,key:&Self::Key)->Option<Self::Value>;fn entry(&mut self,key:Self::Key)->Self::Entry<'_>;fn iter(&self)->Self::Iter<'_>;fn drain(&mut self)->Self::Drain<'_>;}pub trait ContainerEntry<'a>{type Key:'a;type Value:'a;fn or_default(self)->&'a mut Self::Value where Self::Value:Default;fn or_insert(self,default:Self::Value)->&'a mut Self::Value;fn or_insert_with<F>(self,default:F)->&'a mut Self::Value where F:FnOnce()->Self::Value;fn or_insert_with_key<F>(self,default:F)->&'a mut Self::Value where F:FnOnce(&Self::Key)->Self::Value;fn key(&self)->&Self::Key;fn and_modify<F>(self,f:F)->Self where F:FnOnce(&mut Self::Value);}#[derive(Debug)]pub struct BTreeMapDrain<'a,K,V>{inner:&'a mut BTreeMap<K,V>}impl<K,V>Container for BTreeMap<K,V>where K:Ord{type Key=K;type Value=V;type Entry<'a>=btree_map::Entry<'a,K,V>where K:'a,V:'a;type Iter<'a>=btree_map::Iter<'a,K,V>where K:'a,V:'a;type Drain<'a>=BTreeMapDrain<'a,K,V>where K:'a,V:'a;fn get(&self,key:&Self::Key)->Option<&Self::Value>{self.get(key)}fn get_mut(&mut self,key:&Self::Key)->Option<&mut Self::Value>{self.get_mut(key)}fn insert(&mut self,key:Self::Key,value:Self::Value)->Option<Self::Value>{self.insert(key,value)}fn remove(&mut self,key:&Self::Key)->Option<Self::Value>{self.remove(key)}fn entry(&mut self,key:Self::Key)->Self::Entry<'_>{self.entry(key)}fn iter(&self)->Self::Iter<'_>{self.iter()}fn drain(&mut self)->Self::Drain<'_>{BTreeMapDrain{inner:self}}}impl<K,V>Iterator for BTreeMapDrain<'_,K,V>where K:Ord{type Item=(K,V);fn next(&mut self)->Option<Self::Item>{self.inner.pop_first()}}impl<K,V>DoubleEndedIterator for BTreeMapDrain<'_,K,V>where K:Ord{fn next_back(&mut self)->Option<Self::Item>{self.inner.pop_last()}}impl<K,V>ExactSizeIterator for BTreeMapDrain<'_,K,V>where K:Ord{fn len(&self)->usize{self.inner.len()}}impl<K,V>FusedIterator for BTreeMapDrain<'_,K,V>where K:Ord{}impl<'a,K,V>ContainerEntry<'a>for btree_map::Entry<'a,K,V>where K:'a+Ord,V:'a{type Key=K;type Value=V;fn or_default(self)->&'a mut Self::Value where Self::Value:Default{self.or_default()}fn or_insert(self,default:Self::Value)->&'a mut Self::Value{self.or_insert(default)}fn or_insert_with<F>(self,default:F)->&'a mut Self::Value where F:FnOnce()->Self::Value{self.or_insert_with(default)}fn or_insert_with_key<F>(self,default:F)->&'a mut Self::Value where F:FnOnce(&Self::Key)->Self::Value{self.or_insert_with_key(default)}fn key(&self)->&Self::Key{self.key()}fn and_modify<F>(self,f:F)->Self where F:FnOnce(&mut Self::Value){self.and_modify(f)}}impl<K,V,S>Container for HashMap<K,V,S>where K:Eq+Hash,S:BuildHasher{type Key=K;type Value=V;type Entry<'a>=hash_map::Entry<'a,K,V>where S:'a,K:'a,V:'a;type Iter<'a>=hash_map::Iter<'a,K,V>where S:'a,K:'a,V:'a;type Drain<'a>=hash_map::Drain<'a,K,V>where S:'a,K:'a,V:'a;fn get(&self,key:&Self::Key)->Option<&Self::Value>{self.get(key)}fn get_mut(&mut self,key:&Self::Key)->Option<&mut Self::Value>{self.get_mut(key)}fn insert(&mut self,key:Self::Key,value:Self::Value)->Option<Self::Value>{self.insert(key,value)}fn remove(&mut self,key:&Self::Key)->Option<Self::Value>{self.remove(key)}fn entry(&mut self,key:Self::Key)->Self::Entry<'_>{self.entry(key)}fn iter(&self)->Self::Iter<'_>{self.iter()}fn drain(&mut self)->Self::Drain<'_>{self.drain()}}impl<'a,K,V>ContainerEntry<'a>for hash_map::Entry<'a,K,V>where K:'a+Eq+Hash,V:'a{type Key=K;type Value=V;fn or_default(self)->&'a mut Self::Value where Self::Value:Default{self.or_default()}fn or_insert(self,default:Self::Value)->&'a mut Self::Value{self.or_insert(default)}fn or_insert_with<F>(self,default:F)->&'a mut Self::Value where F:FnOnce()->Self::Value{self.or_insert_with(default)}fn or_insert_with_key<F>(self,default:F)->&'a mut Self::Value where F:FnOnce(&Self::Key)->Self::Value{self.or_insert_with_key(default)}fn key(&self)->&Self::Key{self.key()}fn and_modify<F>(self,f:F)->Self where F:FnOnce(&mut Self::Value){self.and_modify(f)}}}