use std::mem;
#[derive(Clone, Debug, Default, PartialEq, Eq)]
pub struct SmallStringMap<T> {
entries: Vec<(String, T)>,
}
impl<T> SmallStringMap<T> {
#[must_use]
#[inline(always)]
pub const fn new() -> Self {
Self {
entries: Vec::new(),
}
}
#[must_use]
#[inline(always)]
pub fn with_capacity(capacity: usize) -> Self {
Self {
entries: Vec::with_capacity(capacity),
}
}
#[must_use]
#[inline(always)]
pub fn from_vec(entries: Vec<(String, T)>) -> Self {
Self { entries }
}
#[must_use]
#[inline(always)]
pub fn into_vec(self) -> Vec<(String, T)> {
self.entries
}
#[must_use]
#[inline(always)]
pub fn as_slice(&self) -> &[(String, T)] {
&self.entries
}
#[must_use]
#[inline(always)]
pub fn len(&self) -> usize {
self.entries.len()
}
#[must_use]
#[inline(always)]
pub fn is_empty(&self) -> bool {
self.entries.is_empty()
}
#[must_use]
#[inline(always)]
pub fn capacity(&self) -> usize {
self.entries.capacity()
}
#[inline(always)]
pub fn clear(&mut self) {
self.entries.clear();
}
#[must_use]
#[inline]
fn position(&self, key: &str) -> Option<usize> {
self.entries.iter().position(|(k, _)| k == key)
}
#[must_use]
#[inline]
pub fn contains_key(&self, key: &str) -> bool {
self.position(key).is_some()
}
#[must_use]
#[inline]
pub fn get(&self, key: &str) -> Option<&T> {
self.entries.iter().find(|(k, _)| k == key).map(|(_, v)| v)
}
#[must_use]
#[inline]
pub fn get_mut(&mut self, key: &str) -> Option<&mut T> {
self.entries
.iter_mut()
.find(|(k, _)| k == key)
.map(|(_, v)| v)
}
#[must_use]
#[inline]
pub fn get_key_value(&self, key: &str) -> Option<(&str, &T)> {
self.entries
.iter()
.find(|(k, _)| k == key)
.map(|(k, v)| (k.as_str(), v))
}
#[inline]
pub fn insert(&mut self, key: impl Into<String>, value: T) -> Option<T> {
let key = key.into();
match self.position(&key) {
Some(i) => Some(mem::replace(&mut self.entries[i].1, value)),
None => {
self.entries.push((key, value));
None
}
}
}
#[inline]
pub fn remove(&mut self, key: &str) -> Option<T> {
let i = self.position(key)?;
Some(self.entries.remove(i).1)
}
#[inline]
pub fn swap_remove(&mut self, key: &str) -> Option<T> {
let i = self.position(key)?;
Some(self.entries.swap_remove(i).1)
}
#[inline]
pub fn iter(&self) -> impl Iterator<Item = (&str, &T)> {
self.entries.iter().map(|(k, v)| (k.as_str(), v))
}
#[inline]
pub fn iter_mut(&mut self) -> impl Iterator<Item = (&str, &mut T)> {
self.entries.iter_mut().map(|(k, v)| (k.as_str(), v))
}
#[inline]
pub fn keys(&self) -> impl Iterator<Item = &str> {
self.entries.iter().map(|(k, _)| k.as_str())
}
#[inline]
pub fn values(&self) -> impl Iterator<Item = &T> {
self.entries.iter().map(|(_, v)| v)
}
#[inline]
pub fn values_mut(&mut self) -> impl Iterator<Item = &mut T> {
self.entries.iter_mut().map(|(_, v)| v)
}
#[must_use]
#[inline]
pub fn entry(&mut self, key: impl Into<String>) -> Entry<'_, T> {
let key = key.into();
match self.position(&key) {
Some(index) => Entry::Occupied(OccupiedEntry { map: self, index }),
None => Entry::Vacant(VacantEntry { map: self, key }),
}
}
}
impl<T> std::ops::Index<&str> for SmallStringMap<T> {
type Output = T;
#[inline(always)]
fn index(&self, key: &str) -> &T {
self.get(key).expect("no entry found for key")
}
}
impl<T> FromIterator<(String, T)> for SmallStringMap<T> {
#[inline]
fn from_iter<I: IntoIterator<Item = (String, T)>>(iter: I) -> Self {
let mut map = Self::new();
for (k, v) in iter {
map.insert(k, v);
}
map
}
}
impl<T> Extend<(String, T)> for SmallStringMap<T> {
#[inline]
fn extend<I: IntoIterator<Item = (String, T)>>(&mut self, iter: I) {
for (k, v) in iter {
self.insert(k, v);
}
}
}
impl<T> IntoIterator for SmallStringMap<T> {
type Item = (String, T);
type IntoIter = std::vec::IntoIter<(String, T)>;
#[inline(always)]
fn into_iter(self) -> Self::IntoIter {
self.entries.into_iter()
}
}
impl<T> From<Vec<(String, T)>> for SmallStringMap<T> {
#[inline(always)]
fn from(entries: Vec<(String, T)>) -> Self {
Self::from_vec(entries)
}
}
pub enum Entry<'a, T> {
Occupied(OccupiedEntry<'a, T>),
Vacant(VacantEntry<'a, T>),
}
pub struct OccupiedEntry<'a, T> {
map: &'a mut SmallStringMap<T>,
index: usize,
}
pub struct VacantEntry<'a, T> {
map: &'a mut SmallStringMap<T>,
key: String,
}
impl<'a, T> Entry<'a, T> {
#[inline]
pub fn or_insert(self, default: T) -> &'a mut T {
match self {
Entry::Occupied(e) => e.into_mut(),
Entry::Vacant(e) => e.insert(default),
}
}
#[inline]
pub fn or_insert_with<F: FnOnce() -> T>(self, default: F) -> &'a mut T {
match self {
Entry::Occupied(e) => e.into_mut(),
Entry::Vacant(e) => e.insert(default()),
}
}
#[inline]
pub fn or_insert_with_key<F: FnOnce(&str) -> T>(self, default: F) -> &'a mut T {
match self {
Entry::Occupied(e) => e.into_mut(),
Entry::Vacant(e) => {
let value = default(&e.key);
e.insert(value)
}
}
}
#[inline]
pub fn or_default(self) -> &'a mut T
where
T: Default,
{
self.or_insert_with(T::default)
}
#[inline]
pub fn and_modify<F: FnOnce(&mut T)>(mut self, f: F) -> Self {
if let Entry::Occupied(e) = &mut self {
f(e.get_mut());
}
self
}
#[must_use]
#[inline(always)]
pub fn key(&self) -> &str {
match self {
Entry::Occupied(e) => e.key(),
Entry::Vacant(e) => e.key(),
}
}
}
impl<'a, T> OccupiedEntry<'a, T> {
#[must_use]
#[inline(always)]
pub fn key(&self) -> &str {
&self.map.entries[self.index].0
}
#[must_use]
#[inline(always)]
pub fn get(&self) -> &T {
&self.map.entries[self.index].1
}
#[must_use]
#[inline(always)]
pub fn get_mut(&mut self) -> &mut T {
&mut self.map.entries[self.index].1
}
#[must_use]
#[inline(always)]
pub fn into_mut(self) -> &'a mut T {
&mut self.map.entries[self.index].1
}
#[inline]
pub fn insert(&mut self, value: T) -> T {
mem::replace(self.get_mut(), value)
}
#[inline]
pub fn remove(self) -> T {
self.map.entries.remove(self.index).1
}
}
impl<'a, T> VacantEntry<'a, T> {
#[must_use]
#[inline(always)]
pub fn key(&self) -> &str {
&self.key
}
#[must_use]
#[inline(always)]
pub fn into_key(self) -> String {
self.key
}
#[inline]
pub fn insert(self, value: T) -> &'a mut T {
self.map.entries.push((self.key, value));
&mut self.map.entries.last_mut().unwrap().1
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn insert_get_and_overwrite() {
let mut m: SmallStringMap<i32> = SmallStringMap::new();
assert!(m.is_empty());
assert_eq!(m.insert("a", 1), None);
assert_eq!(m.insert("b", 2), None);
assert_eq!(m.insert("a", 10), Some(1)); assert_eq!(m.get("a"), Some(&10));
assert_eq!(m.get("missing"), None);
assert_eq!(m.len(), 2);
assert!(m.contains_key("b"));
assert_eq!(m.keys().collect::<Vec<_>>(), ["a", "b"]);
}
#[test]
fn entry_or_insert_and_modify() {
let mut counts: SmallStringMap<i32> = SmallStringMap::new();
for word in ["x", "y", "x", "x", "y"] {
*counts.entry(word).or_insert(0) += 1;
}
assert_eq!(counts.get("x"), Some(&3));
assert_eq!(counts.get("y"), Some(&2));
counts.entry("x").and_modify(|c| *c += 100).or_insert(1);
counts.entry("z").and_modify(|c| *c += 100).or_insert(1);
assert_eq!(counts.get("x"), Some(&103));
assert_eq!(counts.get("z"), Some(&1));
assert_eq!(*counts.entry("w").or_default(), 0);
let v = counts.entry("keyed").or_insert_with_key(|k| k.len() as i32);
assert_eq!(*v, 5);
}
#[test]
fn remove_preserves_order() {
let mut m: SmallStringMap<&str> = [
("a".to_string(), "1"),
("b".to_string(), "2"),
("c".to_string(), "3"),
]
.into_iter()
.collect();
assert_eq!(m.remove("b"), Some("2"));
assert_eq!(m.remove("b"), None);
assert_eq!(m.keys().collect::<Vec<_>>(), ["a", "c"]);
}
#[test]
fn index_and_iteration() {
let mut m: SmallStringMap<i32> = SmallStringMap::new();
m.insert("one", 1);
m.insert("two", 2);
assert_eq!(m["two"], 2);
for v in m.values_mut() {
*v *= 10;
}
assert_eq!(m.iter().collect::<Vec<_>>(), [("one", &10), ("two", &20)]);
assert_eq!(
m.into_iter().collect::<Vec<_>>(),
[("one".to_string(), 10), ("two".to_string(), 20)]
);
}
}