microcad_lang_base/
ord_map.rs

1// Copyright © 2024-2026 The µcad authors <info@microcad.xyz>
2// SPDX-License-Identifier: AGPL-3.0-or-later
3
4//! Ordered Map
5
6use std::ops::Index;
7
8use microcad_core::hash::HashMap;
9
10/// Trait a value in an `OrdMap` must implement.
11/// # Types
12/// `K`: key type
13pub trait OrdMapValue<K>
14where
15    K: std::cmp::Eq + std::hash::Hash + Clone,
16{
17    /// return some unique key of this value or `None`
18    fn key(&self) -> Option<K>;
19}
20
21/// Map whose values can be accessed via index in original insert order.
22#[derive(Clone, PartialEq)]
23pub struct OrdMap<K, V>
24where
25    V: OrdMapValue<K>,
26    K: std::cmp::Eq + std::hash::Hash + Clone,
27{
28    /// vec to store values
29    vec: Vec<V>,
30    /// map to store key -> index of value in vec
31    map: HashMap<K, usize>,
32}
33
34impl<K, V> Default for OrdMap<K, V>
35where
36    V: OrdMapValue<K>,
37    K: std::cmp::Eq + std::hash::Hash + Clone,
38{
39    fn default() -> Self {
40        Self {
41            vec: Default::default(),
42            map: Default::default(),
43        }
44    }
45}
46
47impl<K, V> std::fmt::Debug for OrdMap<K, V>
48where
49    V: OrdMapValue<K> + std::fmt::Debug,
50    K: std::cmp::Eq + std::hash::Hash + Clone,
51{
52    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
53        f.debug_struct("OrdMap").field("vec", &self.vec).finish()
54    }
55}
56
57impl<K, V> From<Vec<V>> for OrdMap<K, V>
58where
59    V: OrdMapValue<K>,
60    K: std::cmp::Eq + std::hash::Hash + Clone,
61{
62    fn from(vec: Vec<V>) -> Self {
63        Self {
64            map: vec
65                .iter()
66                .enumerate()
67                .filter_map(|(i, item)| item.key().map(|key| (key, i)))
68                .collect(),
69            vec,
70        }
71    }
72}
73
74impl<K, V> OrdMap<K, V>
75where
76    V: OrdMapValue<K>,
77    K: std::cmp::Eq + std::hash::Hash + Clone,
78{
79    /// get iterator over values in original order
80    pub fn iter(&self) -> std::slice::Iter<'_, V> {
81        self.vec.iter()
82    }
83
84    /// return number of stored values
85    pub fn len(&self) -> usize {
86        self.vec.len()
87    }
88
89    /// `true` no values are stored`
90    pub fn is_empty(&self) -> bool {
91        self.vec.is_empty()
92    }
93
94    /// add new value
95    ///
96    /// On duplicated named entries, it returns the existing key and the new, duplicate key
97    pub fn try_push(&mut self, item: V) -> Result<(), (K, K)> {
98        if let Some(key) = item.key() {
99            match self.map.entry(key) {
100                std::collections::hash_map::Entry::Vacant(entry) => entry.insert(self.vec.len()),
101                std::collections::hash_map::Entry::Occupied(entry) => {
102                    return Err((entry.key().clone(), item.key().expect("ord_map error")));
103                }
104            };
105        }
106        self.vec.push(item);
107        Ok(())
108    }
109
110    /// get value by key
111    pub fn get(&self, key: &K) -> Option<&V> {
112        self.map.get(key).map(|index| &self.vec[*index])
113    }
114
115    /// get list of all keys
116    pub fn keys(&self) -> std::collections::hash_map::Keys<'_, K, usize> {
117        self.map.keys()
118    }
119
120    /// get first element
121    pub fn first(&self) -> Option<&V> {
122        self.vec.first()
123    }
124}
125
126impl<K, V> Index<usize> for OrdMap<K, V>
127where
128    V: OrdMapValue<K>,
129    K: std::cmp::Eq + std::hash::Hash + Clone,
130{
131    type Output = V;
132
133    fn index(&self, index: usize) -> &Self::Output {
134        &self.vec[index]
135    }
136}
137
138impl<K, V> Index<&K> for OrdMap<K, V>
139where
140    V: OrdMapValue<K>,
141    K: std::cmp::Eq + std::hash::Hash + Clone,
142{
143    type Output = V;
144
145    fn index(&self, key: &K) -> &Self::Output {
146        &self.vec[*self.map.get(key).expect("key not found")]
147    }
148}
microcad_lang_base/ord_map.rs

microcad_lang_base/
ord_map.rs
