use std::collections::HashMap;
use std::fmt;
const INDEX_THRESHOLD: usize = 16;
#[derive(Clone)]
pub struct OrderedMap<V> {
keys: Keys,
values: Vec<V>,
}
#[derive(Clone, Default)]
pub(crate) struct Keys {
pub(crate) names: Vec<String>,
index: Option<HashMap<String, usize>>,
}
impl Keys {
pub(crate) fn position(&self, key: &str) -> Option<usize> {
match &self.index {
Some(index) => index.get(key).copied(),
None => self.names.iter().position(|k| k == key),
}
}
pub(crate) fn insert(&mut self, at: usize, key: String) {
if let Some(index) = &mut self.index {
if at < self.names.len() {
for i in index.values_mut().filter(|i| **i >= at) {
*i += 1;
}
}
index.insert(key.clone(), at);
}
self.names.insert(at, key);
if self.index.is_none() && self.names.len() > INDEX_THRESHOLD {
self.index = Some(
self.names
.iter()
.enumerate()
.map(|(i, k)| (k.clone(), i))
.collect(),
);
}
}
pub(crate) fn remove(&mut self, at: usize) {
let key = self.names.remove(at);
if let Some(index) = &mut self.index {
index.remove(&key);
for i in index.values_mut().filter(|i| **i > at) {
*i -= 1;
}
}
}
}
impl<V> Default for OrderedMap<V> {
fn default() -> Self {
OrderedMap {
keys: Keys::default(),
values: Vec::new(),
}
}
}
impl<V> OrderedMap<V> {
pub fn new() -> Self {
Self::default()
}
pub fn with_capacity(capacity: usize) -> Self {
OrderedMap {
keys: Keys {
names: Vec::with_capacity(capacity),
index: None,
},
values: Vec::with_capacity(capacity),
}
}
pub fn len(&self) -> usize {
self.values.len()
}
pub fn is_empty(&self) -> bool {
self.values.is_empty()
}
pub fn position(&self, key: &str) -> Option<usize> {
self.keys.position(key)
}
pub fn get(&self, key: &str) -> Option<&V> {
self.position(key).map(|i| &self.values[i])
}
pub fn get_mut(&mut self, key: &str) -> Option<&mut V> {
self.position(key).map(|i| &mut self.values[i])
}
pub fn contains_key(&self, key: &str) -> bool {
self.position(key).is_some()
}
pub fn get_index(&self, index: usize) -> Option<(&String, &V)> {
Some((self.keys.names.get(index)?, &self.values[index]))
}
pub fn insert(&mut self, key: impl Into<String>, value: V) -> Option<V> {
let key = key.into();
if let Some(i) = self.position(&key) {
return Some(std::mem::replace(&mut self.values[i], value));
}
let at = self.values.len();
self.insert_new(at, key, value);
None
}
pub fn insert_at(&mut self, at: usize, key: impl Into<String>, value: V) {
let key = key.into();
assert!(
!self.contains_key(&key),
"OrderedMap::insert_at: key present"
);
self.insert_new(at, key, value);
}
fn insert_new(&mut self, at: usize, key: String, value: V) {
self.keys.insert(at, key);
self.values.insert(at, value);
}
pub fn remove_full(&mut self, key: &str) -> Option<(usize, V)> {
let at = self.position(key)?;
self.keys.remove(at);
Some((at, self.values.remove(at)))
}
pub fn remove(&mut self, key: &str) -> Option<V> {
self.remove_full(key).map(|(_, v)| v)
}
pub fn iter(&self) -> Iter<'_, V> {
Iter::new(&self.keys.names, &self.values)
}
pub fn iter_mut(&mut self) -> impl ExactSizeIterator<Item = (&String, &mut V)> {
self.keys.names.iter().zip(self.values.iter_mut())
}
pub fn keys(&self) -> impl DoubleEndedIterator<Item = &String> + ExactSizeIterator + Clone {
self.keys.names.iter()
}
pub fn values(&self) -> impl DoubleEndedIterator<Item = &V> + ExactSizeIterator + Clone {
self.values.iter()
}
pub fn values_mut(&mut self) -> impl ExactSizeIterator<Item = &mut V> {
self.values.iter_mut()
}
}
impl<V: PartialEq> PartialEq for OrderedMap<V> {
fn eq(&self, other: &Self) -> bool {
self.len() == other.len() && self.iter().all(|(k, v)| other.get(k) == Some(v))
}
}
impl<V: fmt::Debug> fmt::Debug for OrderedMap<V> {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_map().entries(self.iter()).finish()
}
}
impl<K: Into<String>, V> FromIterator<(K, V)> for OrderedMap<V> {
fn from_iter<I: IntoIterator<Item = (K, V)>>(iter: I) -> Self {
let iter = iter.into_iter();
let mut map = OrderedMap::with_capacity(iter.size_hint().0);
for (k, v) in iter {
map.insert(k, v);
}
map
}
}
#[derive(Clone)]
pub struct Iter<'a, V>(std::iter::Zip<std::slice::Iter<'a, String>, std::slice::Iter<'a, V>>);
impl<'a, V> Iter<'a, V> {
pub(crate) fn new(keys: &'a [String], values: &'a [V]) -> Self {
Iter(keys.iter().zip(values))
}
}
impl<'a, V> Iterator for Iter<'a, V> {
type Item = (&'a String, &'a V);
fn next(&mut self) -> Option<Self::Item> {
self.0.next()
}
fn size_hint(&self) -> (usize, Option<usize>) {
self.0.size_hint()
}
}
impl<V> DoubleEndedIterator for Iter<'_, V> {
fn next_back(&mut self) -> Option<Self::Item> {
self.0.next_back()
}
}
impl<V> ExactSizeIterator for Iter<'_, V> {}
pub struct IntoIter<V>(std::iter::Zip<std::vec::IntoIter<String>, std::vec::IntoIter<V>>);
impl<V> IntoIter<V> {
pub(crate) fn new(keys: Vec<String>, values: Vec<V>) -> Self {
IntoIter(keys.into_iter().zip(values))
}
}
impl<V> Iterator for IntoIter<V> {
type Item = (String, V);
fn next(&mut self) -> Option<Self::Item> {
self.0.next()
}
fn size_hint(&self) -> (usize, Option<usize>) {
self.0.size_hint()
}
}
impl<V> DoubleEndedIterator for IntoIter<V> {
fn next_back(&mut self) -> Option<Self::Item> {
self.0.next_back()
}
}
impl<V> ExactSizeIterator for IntoIter<V> {}
impl<'a, V> IntoIterator for &'a OrderedMap<V> {
type Item = (&'a String, &'a V);
type IntoIter = Iter<'a, V>;
fn into_iter(self) -> Iter<'a, V> {
self.iter()
}
}
impl<V> IntoIterator for OrderedMap<V> {
type Item = (String, V);
type IntoIter = IntoIter<V>;
fn into_iter(self) -> IntoIter<V> {
IntoIter::new(self.keys.names, self.values)
}
}
#[cfg(test)]
mod tests {
use super::*;
fn check(map: &OrderedMap<usize>) {
for (i, (k, v)) in map.iter().enumerate() {
assert_eq!(map.position(k), Some(i), "{k}");
assert_eq!(map.get(k), Some(v));
}
assert_eq!(map.get("missing"), None);
}
#[test]
fn keeps_order_and_positions_through_inserts_and_removes() {
let mut map = OrderedMap::new();
for i in 0..20 {
map.insert(format!("k{i}"), i);
check(&map);
}
assert_eq!(map.insert("k3", 30), Some(3));
map.insert_at(0, "first", 100);
map.insert_at(5, "middle", 101);
check(&map);
assert_eq!(map.remove_full("k0"), Some((1, 0)));
assert_eq!(map.remove("middle"), Some(101));
check(&map);
for i in 1..20 {
map.remove(&format!("k{i}"));
check(&map);
}
assert_eq!(map.keys().collect::<Vec<_>>(), ["first"]);
map.insert("again", 1);
check(&map);
}
#[test]
fn equality_ignores_order() {
let a: OrderedMap<i32> = [("x", 1), ("y", 2)].into_iter().collect();
let b: OrderedMap<i32> = [("y", 2), ("x", 1)].into_iter().collect();
let c: OrderedMap<i32> = [("y", 2), ("x", 3)].into_iter().collect();
assert_eq!(a, b);
assert_ne!(a, c);
}
}