microcad_lang/
ord_map.rs

1// Copyright © 2024-2025 The µcad authors <info@ucad.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    pub fn try_push(&mut self, item: V) -> Result<(), K> {
95        if let Some(key) = item.key().clone() {
96            if self.map.contains_key(&key) {
97                return Err(key);
98            }
99            self.map.insert(key, self.vec.len());
100        }
101        self.vec.push(item);
102        Ok(())
103    }
104
105    /// get value by key
106    pub fn get(&self, key: &K) -> Option<&V> {
107        self.map.get(key).map(|index| &self.vec[*index])
108    }
109
110    /// get list of all keys
111    pub fn keys(&self) -> std::collections::hash_map::Keys<'_, K, usize> {
112        self.map.keys()
113    }
114
115    /// get first element
116    pub fn first(&self) -> Option<&V> {
117        self.vec.first()
118    }
119}
120
121impl<K, V> Index<usize> for OrdMap<K, V>
122where
123    V: OrdMapValue<K>,
124    K: std::cmp::Eq + std::hash::Hash + Clone,
125{
126    type Output = V;
127
128    fn index(&self, index: usize) -> &Self::Output {
129        &self.vec[index]
130    }
131}
132
133impl<K, V> Index<&K> for OrdMap<K, V>
134where
135    V: OrdMapValue<K>,
136    K: std::cmp::Eq + std::hash::Hash + Clone,
137{
138    type Output = V;
139
140    fn index(&self, key: &K) -> &Self::Output {
141        &self.vec[*self.map.get(key).expect("key not found")]
142    }
143}
microcad_lang/ord_map.rs

microcad_lang/
ord_map.rs
