#![feature(test)]
extern crate test;
use std::iter::FromIterator;
#[derive(Clone)]
pub struct VecMap<K: PartialEq, V> {
inner: Vec<(K, V)>,
}
impl<K: PartialEq + std::fmt::Debug, V: std::fmt::Debug> std::fmt::Debug for VecMap<K, V> {
fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
f.debug_map()
.entries(self.inner.iter().map(|e| (&e.0, &e.1)))
.finish()
}
}
impl<K: PartialEq, V> Default for VecMap<K, V> {
fn default() -> Self {
VecMap { inner: Vec::new() }
}
}
impl<K: PartialEq, V: PartialEq> PartialEq for VecMap<K, V> {
fn eq(&self, rhs: &Self) -> bool {
if self.inner.len() != rhs.inner.len() {
return false;
}
if self
.inner
.iter()
.zip(rhs.inner.iter())
.all(|(lhs, rhs)| lhs == rhs)
{
return true;
}
self.inner.iter().all(|left| {
if let Some(right) = rhs.get(&left.0) {
right == &left.1
} else {
false
}
})
}
}
impl<K: PartialEq, V> From<Vec<(K, V)>> for VecMap<K, V> {
fn from(inner: Vec<(K, V)>) -> Self {
VecMap { inner }
}
}
impl<K: PartialEq, V> Into<Vec<(K, V)>> for VecMap<K, V> {
fn into(self) -> Vec<(K, V)> {
self.inner
}
}
impl<K: PartialEq, V> VecMap<K, V> {
pub fn new() -> Self {
Self::default()
}
pub fn with_capacity(capacity: usize) -> Self {
VecMap {
inner: Vec::with_capacity(capacity),
}
}
pub fn inner(&self) -> &Vec<(K, V)> {
&self.inner
}
pub unsafe fn inner_mut(&mut self) -> &mut Vec<(K, V)> {
&mut self.inner
}
pub unsafe fn push_insert(&mut self, key: K, value: V) {
self.inner.push((key, value))
}
pub fn insert(&mut self, key: K, mut value: V) -> Option<V> {
if let Some(slot) = self.get_mut(&key) {
std::mem::swap(&mut value, slot);
Some(value)
} else {
self.inner.push((key, value));
None
}
}
pub fn get_pair<Lookup: PartialEq<K>>(&self, key: &Lookup) -> Option<(&K, &V)> {
self.inner
.iter()
.find(|e| key == &e.0)
.map(|e| (&e.0, &e.1))
}
pub fn get_pair_mut<Lookup: PartialEq<K>>(&mut self, key: &Lookup) -> Option<(&K, &mut V)> {
self.inner
.iter_mut()
.find(|e| key == &e.0)
.map(|e| (&e.0, &mut e.1))
}
pub fn get<Lookup: PartialEq<K>>(&self, key: &Lookup) -> Option<&V> {
self.inner.iter().find(|e| key == &e.0).map(|e| &e.1)
}
pub fn get_mut<Lookup: PartialEq<K>>(&mut self, key: &Lookup) -> Option<&mut V> {
self.inner
.iter_mut()
.find(|e| key == &e.0)
.map(|e| &mut e.1)
}
pub fn get_mut_init<'l>(&'l mut self, key: K) -> &'l mut V where V: Default{
if let Some(position) = self.inner.iter().position(|el| key == el.0) {
&mut self.inner[position].1
} else {
self.inner.push((key, Default::default()));
if let Some(last) = self.inner.last_mut() {
&mut last.1
} else {
unsafe {std::hint::unreachable_unchecked()};
}
}
}
pub fn remove(&mut self, key: &K) -> Option<V> {
self.inner
.iter()
.position(|e| &e.0 == key)
.map(|position| self.inner.swap_remove(position).1)
}
pub fn keys<'l>(&'l self) -> Box<dyn Iterator<Item = &'l K> + 'l> {
Box::new(self.inner.iter().map(|e| &e.0))
}
pub fn iter<'l>(&'l self) -> Box<dyn Iterator<Item = (&'l K, &'l V)> + 'l> {
Box::new(self.inner.iter().map(|e| (&e.0, &e.1)))
}
pub fn iter_mut<'l>(&'l mut self) -> Box<dyn Iterator<Item = (&'l K, &'l mut V)> + 'l> {
Box::new(self.inner.iter_mut().map(|e| (&e.0, &mut e.1)))
}
}
impl<K: PartialEq, V> IntoIterator for VecMap<K, V> {
type Item = (K, V);
type IntoIter = std::vec::IntoIter<(K, V)>;
fn into_iter(self) -> Self::IntoIter {
self.inner.into_iter()
}
}
impl<'l, K: PartialEq, V> IntoIterator for &'l VecMap<K, V> {
type Item = (&'l K, &'l V);
type IntoIter = Box<dyn Iterator<Item = (&'l K, &'l V)> + 'l>;
fn into_iter(self) -> Self::IntoIter {
self.iter()
}
}
impl<'l, K: PartialEq, V> IntoIterator for &'l mut VecMap<K, V> {
type Item = (&'l K, &'l mut V);
type IntoIter = Box<dyn Iterator<Item = (&'l K, &'l mut V)> + 'l>;
fn into_iter(self) -> Self::IntoIter {
self.iter_mut()
}
}
impl<K: PartialEq, V> FromIterator<(K, V)> for VecMap<K, V> {
fn from_iter<T: IntoIterator<Item = (K, V)>>(iter: T) -> Self {
let mut this = Self::new();
for (key, value) in iter {
this.insert(key, value);
}
this
}
}
#[cfg(test)]
mod bench {
mod hash_map {
use crate::test::Bencher;
type Map<K, V> = std::collections::HashMap<K, V>;
fn insertion(b: &mut Bencher, size: usize) {
b.iter(|| {
let mut map = Map::new();
for (key, value) in (0..size).map(|x| (x, x + 2)) {
map.insert(key, value);
}
});
}
fn colliding_insertion(b: &mut Bencher, size: usize) {
b.iter(|| {
let mut map = Map::new();
for (key, value) in (0..size).map(|x| (x % (size / 4), x + 2)) {
map.insert(key, value);
}
});
}
fn iteration(b: &mut Bencher, size: usize) {
use std::iter::FromIterator;
let map = Map::from_iter((0..size).map(|x| (x, x + 2)));
b.iter(|| map.iter().for_each(|_| ()))
}
#[bench]
fn insertion_16(b: &mut Bencher) {
insertion(b, 16)
}
#[bench]
fn insertion_128(b: &mut Bencher) {
insertion(b, 128)
}
#[bench]
fn insertion_256(b: &mut Bencher) {
insertion(b, 256)
}
#[bench]
fn insertion_1024(b: &mut Bencher) {
insertion(b, 1024)
}
#[bench]
fn colliding_insertion_16(b: &mut Bencher) {
colliding_insertion(b, 16)
}
#[bench]
fn colliding_insertion_128(b: &mut Bencher) {
colliding_insertion(b, 128)
}
#[bench]
fn colliding_insertion_1024(b: &mut Bencher) {
colliding_insertion(b, 1024)
}
#[bench]
fn colliding_insertion_16000(b: &mut Bencher) {
colliding_insertion(b, 16000)
}
#[bench]
fn iteration_16(b: &mut Bencher) {
iteration(b, 16)
}
#[bench]
fn iteration_128(b: &mut Bencher) {
iteration(b, 128)
}
#[bench]
fn iteration_16000(b: &mut Bencher) {
iteration(b, 16000)
}
}
mod vec_map {
use crate::test::Bencher;
type Map<K, V> = crate::VecMap<K, V>;
fn insertion(b: &mut Bencher, size: usize) {
b.iter(|| {
let mut map = Map::new();
for (key, value) in (0..size).map(|x| (x, x + 2)) {
map.insert(key, value);
}
});
}
fn colliding_insertion(b: &mut Bencher, size: usize) {
b.iter(|| {
let mut map = Map::new();
for (key, value) in (0..size).map(|x| (x % (size / 4), x + 2)) {
map.insert(key, value);
}
});
}
fn iteration(b: &mut Bencher, size: usize) {
use std::iter::FromIterator;
let map = Map::from_iter((0..size).map(|x| (x, x + 2)));
b.iter(|| map.iter().for_each(|_| ()))
}
#[bench]
fn insertion_16(b: &mut Bencher) {
insertion(b, 16)
}
#[bench]
fn insertion_128(b: &mut Bencher) {
insertion(b, 128)
}
#[bench]
fn insertion_256(b: &mut Bencher) {
insertion(b, 256)
}
#[bench]
fn insertion_1024(b: &mut Bencher) {
insertion(b, 1024)
}
#[bench]
fn colliding_insertion_16(b: &mut Bencher) {
colliding_insertion(b, 16)
}
#[bench]
fn colliding_insertion_128(b: &mut Bencher) {
colliding_insertion(b, 128)
}
#[bench]
fn colliding_insertion_1024(b: &mut Bencher) {
colliding_insertion(b, 1024)
}
#[bench]
fn colliding_insertion_16000(b: &mut Bencher) {
colliding_insertion(b, 16000)
}
#[bench]
fn iteration_16(b: &mut Bencher) {
iteration(b, 16)
}
#[bench]
fn iteration_128(b: &mut Bencher) {
iteration(b, 128)
}
#[bench]
fn iteration_16000(b: &mut Bencher) {
iteration(b, 16000)
}
}
}