1use crate::lang::data::{Map, OrderedMap, SortedMap};
4use crate::lang::hash::JavaHash;
5use crate::lang::protocol::{
6 HashType, IAssoc, IColl, IConj, ICount, IDisplay, IDissoc, IEmpty, IEquality, IFind, IHash,
7 ILookup, IMetadata, IObjType, IPeekFirst, IPeekLast, IPersistent, IPopFirst, IPopLast,
8 MetaType, ObjType,
9};
10use std::hash::Hash;
11use std::rc::Rc;
12
13#[derive(Debug, Clone)]
14pub struct Standard<K, V> {
15 metadata: Option<Rc<crate::lang::data::Metadata>>,
16 priorities: Map<K, V>,
17 buckets: SortedMap<V, OrderedMap<K, ()>>,
18}
19impl<K: Clone + Eq + Hash, V: Clone + Ord> Default for Standard<K, V> {
20 fn default() -> Self {
21 Self {
22 metadata: None,
23 priorities: Map::new(),
24 buckets: SortedMap::new(),
25 }
26 }
27}
28impl<K: Clone + Eq + Hash, V: Clone + Ord> Standard<K, V> {
29 pub fn new() -> Self {
30 Self::default()
31 }
32 pub fn len(&self) -> usize {
33 self.priorities.len()
34 }
35 pub fn is_empty(&self) -> bool {
36 self.priorities.is_empty()
37 }
38 pub fn get(&self, key: &K) -> Option<&V> {
39 self.priorities.get(key)
40 }
41 pub fn iter(&self) -> std::vec::IntoIter<(K, V)> {
42 let mut out = Vec::with_capacity(self.len());
43 for (priority, bucket) in self.buckets.iter() {
44 for (key, _) in bucket.iter() {
45 out.push((key.clone(), priority.clone()));
46 }
47 }
48 out.into_iter()
49 }
50 pub fn assoc_value(&self, key: K, priority: V) -> Self {
51 if self.get(&key) == Some(&priority) {
52 return self.clone();
53 }
54 let mut buckets = self.buckets.clone();
55 if let Some(old) = self.get(&key) {
56 if let Some(bucket) = buckets.get(old) {
57 let next = bucket.dissoc_value(&key);
58 buckets = if next.is_empty() {
59 buckets.dissoc_value(old)
60 } else {
61 buckets.assoc_value(old.clone(), next)
62 };
63 }
64 }
65 let bucket = buckets
66 .get(&priority)
67 .cloned()
68 .unwrap_or_else(OrderedMap::new)
69 .assoc_value(key.clone(), ());
70 Self {
71 metadata: self.metadata.clone(),
72 priorities: self.priorities.assoc_value(key, priority.clone()),
73 buckets: buckets.assoc_value(priority, bucket),
74 }
75 }
76 pub fn dissoc_value(&self, key: &K) -> Self {
77 let Some(priority) = self.get(key) else {
78 return self.clone();
79 };
80 let mut buckets = self.buckets.clone();
81 if let Some(bucket) = buckets.get(priority) {
82 let next = bucket.dissoc_value(key);
83 buckets = if next.is_empty() {
84 buckets.dissoc_value(priority)
85 } else {
86 buckets.assoc_value(priority.clone(), next)
87 };
88 }
89 Self {
90 metadata: self.metadata.clone(),
91 priorities: self.priorities.dissoc_value(key),
92 buckets,
93 }
94 }
95 pub fn peek_first_entry(&self) -> Option<(K, V)> {
96 self.iter().next()
97 }
98 pub fn peek_last_entry(&self) -> Option<(K, V)> {
99 self.iter().last()
100 }
101 pub fn pop_first_value(&self) -> Self {
102 self.peek_first_entry()
103 .map(|(k, _)| self.dissoc_value(&k))
104 .unwrap_or_else(|| self.clone())
105 }
106 pub fn pop_last_value(&self) -> Self {
107 self.peek_last_entry()
108 .map(|(k, _)| self.dissoc_value(&k))
109 .unwrap_or_else(|| self.clone())
110 }
111}
112impl<K: Clone + Eq + Hash, V: Clone + Ord> FromIterator<(K, V)> for Standard<K, V> {
113 fn from_iter<T: IntoIterator<Item = (K, V)>>(it: T) -> Self {
114 it.into_iter()
115 .fold(Self::new(), |m, (k, v)| m.assoc_value(k, v))
116 }
117}
118impl<K: Clone + Eq + Hash, V: Clone + Ord> IntoIterator for Standard<K, V> {
119 type Item = (K, V);
120 type IntoIter = std::vec::IntoIter<(K, V)>;
121 fn into_iter(self) -> Self::IntoIter {
122 self.iter()
123 }
124}
125impl<K: Clone + Eq + Hash, V: Clone + Ord> ICount for Standard<K, V> {
126 fn count(&self) -> usize {
127 self.len()
128 }
129}
130impl<K: Clone + Eq + Hash, V: Clone + Ord> IFind<K> for Standard<K, V> {
131 type Output = (K, V);
132 fn find(&self, key: &K) -> Option<Self::Output> {
133 self.priorities
134 .find_entry(key)
135 .map(|(k, v)| (k.clone(), v.clone()))
136 }
137}
138impl<K: Clone + Eq + Hash, V: Clone + Ord> ILookup<K, V> for Standard<K, V> {
139 type Keys = std::vec::IntoIter<K>;
140 type Values = std::vec::IntoIter<V>;
141 fn keys(&self) -> Self::Keys {
142 self.iter().map(|(k, _)| k).collect::<Vec<_>>().into_iter()
143 }
144 fn vals(&self) -> Self::Values {
145 self.iter().map(|(_, v)| v).collect::<Vec<_>>().into_iter()
146 }
147}
148impl<K: Clone + Eq + Hash, V: Clone + Ord> IAssoc<K, V> for Standard<K, V> {
149 type Output = Self;
150 fn assoc(&self, k: K, v: V) -> Self {
151 self.assoc_value(k, v)
152 }
153}
154impl<K: Clone + Eq + Hash, V: Clone + Ord> IDissoc<K> for Standard<K, V> {
155 type Output = Self;
156 fn dissoc(&self, k: &K) -> Self {
157 self.dissoc_value(k)
158 }
159}
160impl<K: Clone + Eq + Hash, V: Clone + Ord> IConj<(K, V)> for Standard<K, V> {
161 type Output = Self;
162 fn conj(&self, (k, v): (K, V)) -> Self {
163 self.assoc_value(k, v)
164 }
165}
166impl<K: Clone + Eq + Hash, V: Clone + Ord> IPeekFirst<(K, V)> for Standard<K, V> {
167 fn peek_first(&self) -> Option<(K, V)> {
168 self.peek_first_entry()
169 }
170}
171impl<K: Clone + Eq + Hash, V: Clone + Ord> IPeekLast<(K, V)> for Standard<K, V> {
172 fn peek_last(&self) -> Option<(K, V)> {
173 self.peek_last_entry()
174 }
175}
176impl<K: Clone + Eq + Hash, V: Clone + Ord> IPopFirst for Standard<K, V> {
177 type Output = Self;
178 fn pop_first(&self) -> Self {
179 self.pop_first_value()
180 }
181}
182impl<K: Clone + Eq + Hash, V: Clone + Ord> IPopLast for Standard<K, V> {
183 type Output = Self;
184 fn pop_last(&self) -> Self {
185 self.pop_last_value()
186 }
187}
188impl<K: Clone + Eq + Hash, V: Clone + Ord> IEmpty for Standard<K, V> {
189 type Output = Self;
190 fn empty(&self) -> Self {
191 Self::new().with_meta(self.metadata.clone())
192 }
193}
194impl<K: Clone + Eq + Hash, V: Clone + Ord> IMetadata for Standard<K, V> {
195 type Metadata = Rc<crate::lang::data::Metadata>;
196 fn meta(&self) -> Option<&Self::Metadata> {
197 self.metadata.as_ref()
198 }
199 fn with_meta(&self, metadata: Option<Self::Metadata>) -> Self {
200 Self {
201 metadata,
202 ..self.clone()
203 }
204 }
205 fn metatype(&self) -> MetaType {
206 MetaType::Map
207 }
208}
209impl<K: Clone + Eq + Hash, V: Clone + Ord> IPersistent for Standard<K, V> {}
210impl<K: Clone + Eq + Hash, V: Clone + Ord + PartialEq> IEquality for Standard<K, V> {
211 fn equality(&self, other: &Self) -> bool {
212 self.len() == other.len() && self.priorities.iter().all(|(k, v)| other.get(k) == Some(v))
213 }
214}
215impl<K: Clone + Eq + Hash + std::fmt::Debug, V: Clone + Ord + std::fmt::Debug> IDisplay
216 for Standard<K, V>
217{
218 fn display(&self) -> String {
219 format!(
220 "{{{}}}",
221 self.iter()
222 .map(|(k, v)| format!("{k:?} {v:?}"))
223 .collect::<Vec<_>>()
224 .join(" ")
225 )
226 }
227}
228impl<K: Clone + Eq + Hash + JavaHash, V: Clone + Ord + Hash + JavaHash> IHash for Standard<K, V> {
229 fn hash_calc(&self, t: HashType) -> u64 {
230 crate::lang::hash::compose_unordered(
231 "MAP",
232 self.priorities
233 .iter()
234 .map(|(k, v)| crate::lang::hash::compose_entry(k.java_hash(t), v.java_hash(t))),
235 ) as u64
236 }
237}
238impl<K: Clone + Eq + Hash + std::fmt::Debug, V: Clone + Ord + std::fmt::Debug> IObjType
239 for Standard<K, V>
240{
241 fn obj_type(&self) -> ObjType {
242 ObjType::Map
243 }
244}
245impl<K, V> IColl<(K, V)> for Standard<K, V>
246where
247 K: Clone + Eq + Hash + JavaHash + std::fmt::Debug,
248 V: Clone + Ord + PartialEq + Hash + JavaHash + std::fmt::Debug,
249{
250 fn start_string(&self) -> &'static str {
251 "{"
252 }
253 fn end_string(&self) -> &'static str {
254 "}"
255 }
256}
257
258#[cfg(test)]
259mod tests {
260 use super::Standard;
261 #[test]
262 fn stable_ties_and_priority_updates() {
263 let map = Standard::new()
264 .assoc_value("a", 2)
265 .assoc_value("b", 1)
266 .assoc_value("c", 1);
267 assert_eq!(
268 map.iter().collect::<Vec<_>>(),
269 vec![("b", 1), ("c", 1), ("a", 2)]
270 );
271 let moved = map.assoc_value("b", 2);
272 assert_eq!(
273 moved.iter().collect::<Vec<_>>(),
274 vec![("c", 1), ("a", 2), ("b", 2)]
275 );
276 assert_eq!(map.get(&"b"), Some(&1));
277 assert_eq!(moved.peek_last_entry(), Some(("b", 2)));
278 }
279}