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

microcad_lang/
ord_map.rs
