leveled_hash_map/lib.rs
1#![allow(clippy::type_complexity)]
2
3use std::collections::{HashMap, HashSet};
4use std::error::Error;
5use std::fmt::{self, Debug, Display, Formatter};
6use std::hash::Hash;
7use std::sync::Arc;
8
9/// A structure to separate values into different levels with keys. Every key-value entry which is not at the top level has a parent key at the superior level. Keys at the same level are unique, no matter what parent keys they have.
10#[derive(Debug)]
11pub struct LeveledHashMap<K: Eq + Hash, V> {
12 pool: Vec<HashMap<Arc<K>, (Option<Arc<K>>, V)>>,
13 sub: Vec<HashMap<Arc<K>, HashSet<Arc<K>>>>,
14}
15
16/// Possible errors come from `LeveledHashMap`.
17pub enum LeveledHashMapError<K> {
18 /// The length of a key chain is over the max level of a `LeveledHashMap`.
19 /// ```
20 /// use std::sync::Arc;
21 ///
22 /// use leveled_hash_map::{LeveledHashMap, LeveledHashMapError};
23 ///
24 /// let mut map = LeveledHashMap::new();
25 ///
26 /// map.insert(&[Arc::new("food")], 100).unwrap();
27 ///
28 /// // now the map has "Level 0", "Level 0" is available to be got, "Level 0" and "Level 1" are available to be inserted
29 ///
30 /// assert_eq!(&100, map.get_advanced(&[Arc::new("food")], 0).unwrap());
31 ///
32 /// // try to get value at "Level 1"
33 ///
34 /// match map.get_professional(&[Arc::new("food"), Arc::new("dessert")], 0) {
35 /// Ok(_) => unreachable!(),
36 /// Err(err) => match err {
37 /// LeveledHashMapError::KeyTooMany => (),
38 /// _ => unreachable!()
39 /// }
40 /// }
41 ///
42 /// // try to insert value to "Level 2"
43 ///
44 /// match map.insert(&[Arc::new("food"), Arc::new("dessert"), Arc::new("cake")], 10) {
45 /// Ok(_) => unreachable!(),
46 /// Err(err) => match err {
47 /// LeveledHashMapError::KeyTooMany => (),
48 /// _ => unreachable!()
49 /// }
50 /// }
51 ///
52 /// // try to insert value to "Level 1"
53 ///
54 /// match map.insert(&[Arc::new("food"), Arc::new("dessert")], 10) {
55 /// Ok(_) => (),
56 /// Err(err) => unreachable!()
57 /// }
58 /// ```
59 KeyTooMany,
60 /// The key chain is correct, but the last key in the key chain does not exist.
61 /// ```
62 /// use std::sync::Arc;
63 ///
64 /// use leveled_hash_map::{LeveledHashMap, LeveledHashMapError};
65 ///
66 /// let mut map = LeveledHashMap::new();
67 ///
68 /// map.insert(&[Arc::new("food")], 100).unwrap();
69 ///
70 /// map.insert(&[Arc::new("food"), Arc::new("dessert")], 100).unwrap();
71 ///
72 /// map.insert(&[Arc::new("food"), Arc::new("dessert"), Arc::new("cake")], 100).unwrap();
73 ///
74 /// // try to get "food/dessert/chocolate"
75 ///
76 /// match map.get_professional(&[Arc::new("food"), Arc::new("dessert"), Arc::new("chocolate")], 0) {
77 /// Ok(_) => unreachable!(),
78 /// Err(err) => {
79 /// match err {
80 /// LeveledHashMapError::KeyNotExist {
81 /// level,
82 /// key,
83 /// } => {
84 /// assert_eq!(2, level);
85 /// assert_eq!(Arc::new("chocolate"), key);
86 /// }
87 /// _ => unreachable!(),
88 /// }
89 /// }
90 /// }
91 /// ```
92 KeyNotExist {
93 level: usize,
94 key: Arc<K>,
95 },
96 /// The key chain is empty.
97 /// ```
98 /// use std::sync::Arc;
99 ///
100 /// use leveled_hash_map::{LeveledHashMap, LeveledHashMapError};
101 ///
102 /// let mut map = LeveledHashMap::new();
103 ///
104 /// map.insert(&[Arc::new("food")], 100).unwrap();
105 ///
106 /// // try to get ""
107 ///
108 /// match map.get_professional(&[], 0) {
109 /// Ok(_) => unreachable!(),
110 /// Err(err) => {
111 /// match err {
112 /// LeveledHashMapError::KeyChainEmpty => (),
113 /// _ => unreachable!(),
114 /// }
115 /// }
116 /// }
117 /// ```
118 KeyChainEmpty,
119 /// The key chain is incorrect.
120 /// ```
121 /// use std::sync::Arc;
122 ///
123 /// use leveled_hash_map::{LeveledHashMap, LeveledHashMapError};
124 ///
125 /// let mut map = LeveledHashMap::new();
126 ///
127 /// map.insert(&[Arc::new("food")], 100).unwrap();
128 ///
129 /// map.insert(&[Arc::new("food"), Arc::new("meat")], 200).unwrap();
130 ///
131 /// map.insert(&[Arc::new("food"), Arc::new("dessert")], 100).unwrap();
132 ///
133 /// map.insert(&[Arc::new("food"), Arc::new("dessert"), Arc::new("cake")], 100).unwrap();
134 ///
135 /// // try to get "food/meat/chocolate", here "food/meat" exists
136 ///
137 /// match map.get_professional(&[Arc::new("food"), Arc::new("meat"), Arc::new("cake")], 0) {
138 /// Ok(_) => unreachable!(),
139 /// Err(err) => {
140 /// match err {
141 /// LeveledHashMapError::KeyChainIncorrect {
142 /// level,
143 /// key,
144 /// last_key,
145 /// } => {
146 /// assert_eq!(2, level);
147 /// assert_eq!(Arc::new("cake"), key);
148 /// assert_eq!(Some(Arc::new("dessert")), last_key);
149 /// }
150 /// _ => unreachable!(),
151 /// }
152 /// }
153 /// }
154 /// ```
155 KeyChainIncorrect {
156 level: usize,
157 key: Arc<K>,
158 last_key: Option<Arc<K>>,
159 },
160}
161
162impl<K> Debug for LeveledHashMapError<K> {
163 #[inline]
164 fn fmt(&self, f: &mut Formatter) -> Result<(), fmt::Error> {
165 match self {
166 LeveledHashMapError::KeyTooMany => f.write_str("KeyTooMany"),
167 LeveledHashMapError::KeyNotExist {
168 level,
169 ..
170 } => {
171 let mut s = f.debug_struct("KeyNotExist");
172 s.field("Level", level);
173 s.finish()
174 }
175 LeveledHashMapError::KeyChainEmpty => f.write_str("KeyChainEmpty"),
176 LeveledHashMapError::KeyChainIncorrect {
177 level,
178 ..
179 } => {
180 let mut s = f.debug_struct("KeyChainIncorrect");
181 s.field("Level", level);
182 s.finish()
183 }
184 }
185 }
186}
187
188impl<K> Display for LeveledHashMapError<K> {
189 #[inline]
190 fn fmt(&self, f: &mut Formatter) -> Result<(), fmt::Error> {
191 match self {
192 LeveledHashMapError::KeyTooMany => {
193 f.write_str("The length of a key chain is over the max level of a `LeveledHashMap`.")
194 }
195 LeveledHashMapError::KeyNotExist {
196 level,
197 ..
198 } => {
199 f.write_fmt(format_args!("The key chain is correct, but the last key at level {} in the key chain does not exist.", level))
200 }
201 LeveledHashMapError::KeyChainEmpty => {
202 f.write_str("The key chain is empty.")
203 }
204 LeveledHashMapError::KeyChainIncorrect {
205 level,
206 ..
207 } => {
208 f.write_fmt(format_args!("The key chain is incorrect at level {}.", level))
209 }
210 }
211 }
212}
213
214impl<K> Error for LeveledHashMapError<K> {}
215
216impl<K: Eq + Hash, V> LeveledHashMap<K, V> {
217 /// Create a new `LeveledHashMap` instance. The key needs to be implemented `Eq` and `Hash` traits.
218 /// ```
219 /// use leveled_hash_map::LeveledHashMap;
220 ///
221 /// let _map: LeveledHashMap<&'static str, String> = LeveledHashMap::new();
222 /// ```
223 #[inline]
224 pub fn new() -> LeveledHashMap<K, V> {
225 LeveledHashMap {
226 pool: Vec::new(),
227 sub: Vec::new(),
228 }
229 }
230
231 /// Get a value by a key chain. The key chain starts at Level 0.
232 /// ```
233 /// use std::sync::Arc;
234 ///
235 /// use leveled_hash_map::LeveledHashMap;
236 ///
237 /// let map: LeveledHashMap<&'static str, String> = LeveledHashMap::new();
238 ///
239 /// let _result = map.get(&[Arc::new("first_key")]);
240 /// ```
241 #[inline]
242 pub fn get(&self, key_chain: &[Arc<K>]) -> Option<&V> {
243 self.get_advanced(key_chain, 0)
244 }
245
246 /// Get a value by a key chain. The key chain starts at Level 0.
247 /// ```
248 /// use std::sync::Arc;
249 ///
250 /// use leveled_hash_map::LeveledHashMap;
251 ///
252 /// let mut map: LeveledHashMap<&'static str, String> = LeveledHashMap::new();
253 ///
254 /// let _result = map.get_mut(&[Arc::new("first_key")]);
255 /// ```
256 #[inline]
257 pub fn get_mut(&mut self, key_chain: &[Arc<K>]) -> Option<&mut V> {
258 self.get_advanced_mut(key_chain, 0)
259 }
260
261 /// Get a value by a key chain and a level which the key chain starts with.
262 /// ```
263 /// use std::sync::Arc;
264 ///
265 /// use leveled_hash_map::LeveledHashMap;
266 ///
267 /// let map: LeveledHashMap<&'static str, String> = LeveledHashMap::new();
268 ///
269 /// let _result = map.get_advanced(&[Arc::new("second_key")], 1);
270 /// ```
271 #[inline]
272 pub fn get_advanced(&self, key_chain: &[Arc<K>], start_level: usize) -> Option<&V> {
273 self.get_professional(key_chain, start_level).ok().map(|v| v.1)
274 }
275
276 /// Get a value by a key chain and a level which the key chain starts with.
277 /// ```
278 /// use std::sync::Arc;
279 ///
280 /// use leveled_hash_map::LeveledHashMap;
281 ///
282 /// let mut map: LeveledHashMap<&'static str, String> = LeveledHashMap::new();
283 ///
284 /// let _result = map.get_advanced_mut(&[Arc::new("second_key")], 1);
285 /// ```
286 #[inline]
287 pub fn get_advanced_mut(&mut self, key_chain: &[Arc<K>], start_level: usize) -> Option<&mut V> {
288 self.get_professional_mut(key_chain, start_level).ok().map(|v| v.1)
289 }
290
291 /// Get a value and its parent key by a key chain and a level which the key chain starts with. It returns a `Err(LeveledHashMapError)` instance to describe the reason of the getting failure.
292 /// ```
293 /// use std::sync::Arc;
294 ///
295 /// use leveled_hash_map::LeveledHashMap;
296 ///
297 /// let mut map: LeveledHashMap<&'static str, String> = LeveledHashMap::new();
298 ///
299 /// map.insert(&[Arc::new("food")], "食物".to_string()).unwrap();
300 ///
301 /// map.insert(&[Arc::new("food"), Arc::new("dessert")], "甜點".to_string()).unwrap();
302 ///
303 /// let result_1 = map.get_professional(&[Arc::new("food")], 0).unwrap();
304 ///
305 /// let result_2 = map.get_professional(&[Arc::new("food"), Arc::new("dessert")], 0).unwrap();
306 ///
307 /// assert_eq!(None, result_1.0);
308 /// assert_eq!("食物", result_1.1);
309 ///
310 /// assert_eq!(Some(Arc::new("food")), result_2.0);
311 /// assert_eq!("甜點", result_2.1);
312 /// ```
313 pub fn get_professional(
314 &self,
315 key_chain: &[Arc<K>],
316 start_level: usize,
317 ) -> Result<(Option<Arc<K>>, &V), LeveledHashMapError<K>> {
318 let key_chain_len = key_chain.len();
319
320 if key_chain_len == 0 {
321 return Err(LeveledHashMapError::KeyChainEmpty);
322 } else if key_chain_len + start_level > self.pool.len() {
323 return Err(LeveledHashMapError::KeyTooMany);
324 }
325
326 let key_chain_len_dec = key_chain_len - 1;
327
328 let mut i = 0;
329
330 let mut last_key = None;
331
332 while i < key_chain_len_dec {
333 let ii = i + start_level;
334 let ck = &key_chain[i];
335 match self.pool[ii].get(ck) {
336 Some((pk, _)) => {
337 if ii > start_level && last_key.ne(&pk.as_ref()) {
338 return Err(LeveledHashMapError::KeyChainIncorrect {
339 level: ii,
340 key: Arc::clone(ck),
341 last_key: pk.as_ref().map(Arc::clone),
342 });
343 }
344 last_key = Some(ck);
345 }
346 None => {
347 return Err(LeveledHashMapError::KeyNotExist {
348 level: ii,
349 key: Arc::clone(ck),
350 })
351 }
352 }
353
354 i += 1;
355 }
356
357 let ck = &key_chain[key_chain_len_dec];
358
359 let ii = key_chain_len_dec + start_level;
360
361 match self.pool[ii].get(ck) {
362 Some((pk, v)) => {
363 if ii > start_level && last_key.ne(&pk.as_ref()) {
364 return Err(LeveledHashMapError::KeyChainIncorrect {
365 level: ii,
366 key: Arc::clone(ck),
367 last_key: pk.as_ref().map(Arc::clone),
368 });
369 }
370 let pk = pk.as_ref().map(Arc::clone);
371 Ok((pk, v))
372 }
373 None => {
374 Err(LeveledHashMapError::KeyNotExist {
375 level: ii,
376 key: Arc::clone(ck),
377 })
378 }
379 }
380 }
381
382 /// Get a value and its parent key by a key chain and a level which the key chain starts with. It returns a `Err(LeveledHashMapError)` instance to describe the reason of the getting failure.
383 /// ```
384 /// use std::sync::Arc;
385 ///
386 /// use leveled_hash_map::LeveledHashMap;
387 ///
388 /// let mut map: LeveledHashMap<&'static str, String> = LeveledHashMap::new();
389 ///
390 /// map.insert(&[Arc::new("food")], "食物".to_string()).unwrap();
391 ///
392 /// map.insert(&[Arc::new("food"), Arc::new("dessert")], "甜點".to_string()).unwrap();
393 ///
394 /// let result = map.get_professional_mut(&[Arc::new("food")], 0).unwrap();
395 ///
396 /// result.1.push_str("/食品");
397 ///
398 /// assert_eq!(None, result.0);
399 /// assert_eq!("食物/食品", result.1);
400 /// ```
401 pub fn get_professional_mut(
402 &mut self,
403 key_chain: &[Arc<K>],
404 start_level: usize,
405 ) -> Result<(Option<Arc<K>>, &mut V), LeveledHashMapError<K>> {
406 let key_chain_len = key_chain.len();
407
408 if key_chain_len == 0 {
409 return Err(LeveledHashMapError::KeyChainEmpty);
410 } else if key_chain_len + start_level > self.pool.len() {
411 return Err(LeveledHashMapError::KeyTooMany);
412 }
413
414 let key_chain_len_dec = key_chain_len - 1;
415
416 let mut i = 0;
417
418 let mut last_key = None;
419
420 while i < key_chain_len_dec {
421 let ii = i + start_level;
422 let ck = &key_chain[i];
423 match self.pool[ii].get(ck) {
424 Some((pk, _)) => {
425 if ii > start_level && last_key.ne(&pk.as_ref()) {
426 return Err(LeveledHashMapError::KeyChainIncorrect {
427 level: ii,
428 key: Arc::clone(ck),
429 last_key: pk.as_ref().map(Arc::clone),
430 });
431 }
432 last_key = Some(ck);
433 }
434 None => {
435 return Err(LeveledHashMapError::KeyNotExist {
436 level: ii,
437 key: Arc::clone(ck),
438 })
439 }
440 }
441
442 i += 1;
443 }
444
445 let ck = &key_chain[key_chain_len_dec];
446
447 let ii = key_chain_len_dec + start_level;
448
449 match self.pool[ii].get_mut(ck) {
450 Some((pk, v)) => {
451 if ii > start_level && last_key.ne(&pk.as_ref()) {
452 return Err(LeveledHashMapError::KeyChainIncorrect {
453 level: ii,
454 key: Arc::clone(ck),
455 last_key: pk.as_ref().map(Arc::clone),
456 });
457 }
458 let pk = pk.as_ref().map(Arc::clone);
459 Ok((pk, v))
460 }
461 None => {
462 Err(LeveledHashMapError::KeyNotExist {
463 level: ii,
464 key: Arc::clone(ck),
465 })
466 }
467 }
468 }
469
470 /// Remove a value by a key chain. The key chain starts at Level 0.
471 /// ```
472 /// use std::sync::Arc;
473 ///
474 /// use leveled_hash_map::LeveledHashMap;
475 ///
476 /// let mut map: LeveledHashMap<&'static str, String> = LeveledHashMap::new();
477 ///
478 /// map.insert(&[Arc::new("food")], "食物".to_string()).unwrap();
479 ///
480 /// map.insert(&[Arc::new("food"), Arc::new("dessert")], "甜點".to_string()).unwrap();
481 ///
482 /// map.insert(&[Arc::new("food"), Arc::new("meat")], "肉類".to_string()).unwrap();
483 ///
484 /// let result = map.remove(&[Arc::new("food"), Arc::new("dessert")]).unwrap();
485 ///
486 /// assert_eq!("甜點", result.0);
487 /// assert_eq!(0, result.1.len());
488 ///
489 /// let result = map.remove(&[Arc::new("food")]).unwrap();
490 ///
491 /// assert_eq!("食物", result.0);
492 /// assert_eq!(1, result.1.len());
493 /// assert_eq!(
494 /// &(Some(Arc::new("food")), "肉類".to_string()),
495 /// result.1[0].get(&Arc::new("meat")).unwrap()
496 /// );
497 /// ```
498 #[inline]
499 pub fn remove(
500 &mut self,
501 key_chain: &[Arc<K>],
502 ) -> Option<(V, Vec<HashMap<Arc<K>, (Option<Arc<K>>, V)>>)> {
503 self.remove_advanced(key_chain, 0)
504 }
505
506 /// Remove a value by a key chain and a level which the key chain starts with.
507 /// ```
508 /// use std::sync::Arc;
509 ///
510 /// use leveled_hash_map::LeveledHashMap;
511 ///
512 /// let mut map: LeveledHashMap<&'static str, String> = LeveledHashMap::new();
513 ///
514 /// map.insert(&[Arc::new("food")], "食物".to_string()).unwrap();
515 ///
516 /// map.insert(&[Arc::new("food"), Arc::new("dessert")], "甜點".to_string()).unwrap();
517 ///
518 /// map.insert(&[Arc::new("food"), Arc::new("meat")], "肉類".to_string()).unwrap();
519 ///
520 /// let result = map.remove_advanced(&[Arc::new("dessert")], 1).unwrap();
521 ///
522 /// assert_eq!("甜點", result.0);
523 /// assert_eq!(0, result.1.len());
524 ///
525 /// let result = map.remove_advanced(&[Arc::new("food")], 0).unwrap();
526 ///
527 /// assert_eq!("食物", result.0);
528 /// assert_eq!(1, result.1.len());
529 /// assert_eq!(
530 /// &(Some(Arc::new("food")), "肉類".to_string()),
531 /// result.1[0].get(&Arc::new("meat")).unwrap()
532 /// );
533 /// ```
534 #[inline]
535 pub fn remove_advanced(
536 &mut self,
537 key_chain: &[Arc<K>],
538 start_level: usize,
539 ) -> Option<(V, Vec<HashMap<Arc<K>, (Option<Arc<K>>, V)>>)> {
540 self.remove_professional(key_chain, start_level).ok().map(|v| (v.1, v.2))
541 }
542
543 /// Remove a value by a key chain and a level which the key chain starts with. It returns a `Err(LeveledHashMapError)` instance to describe the reason of the getting failure.
544 /// ```
545 /// use std::sync::Arc;
546 ///
547 /// use leveled_hash_map::LeveledHashMap;
548 ///
549 /// let mut map: LeveledHashMap<&'static str, String> = LeveledHashMap::new();
550 ///
551 /// map.insert(&[Arc::new("food")], "食物".to_string()).unwrap();
552 ///
553 /// map.insert(&[Arc::new("food"), Arc::new("dessert")], "甜點".to_string()).unwrap();
554 ///
555 /// map.insert(&[Arc::new("food"), Arc::new("meat")], "肉類".to_string()).unwrap();
556 ///
557 /// let result = map.remove_professional(&[Arc::new("dessert")], 1).unwrap();
558 ///
559 /// assert_eq!(Some(Arc::new("food")), result.0);
560 /// assert_eq!("甜點", result.1);
561 /// assert_eq!(0, result.2.len());
562 ///
563 /// let result = map.remove_professional(&[Arc::new("food")], 0).unwrap();
564 ///
565 /// assert_eq!(None, result.0);
566 /// assert_eq!("食物", result.1);
567 /// assert_eq!(1, result.2.len());
568 /// assert_eq!(
569 /// &(Some(Arc::new("food")), "肉類".to_string()),
570 /// result.2[0].get(&Arc::new("meat")).unwrap()
571 /// );
572 /// ```
573 pub fn remove_professional(
574 &mut self,
575 key_chain: &[Arc<K>],
576 start_level: usize,
577 ) -> Result<
578 (Option<Arc<K>>, V, Vec<HashMap<Arc<K>, (Option<Arc<K>>, V)>>),
579 LeveledHashMapError<K>,
580 > {
581 let last_key = self.get_professional(key_chain, start_level)?.0;
582
583 let key_chain_len = key_chain.len();
584
585 let key_chain_len_dec = key_chain_len - 1;
586
587 let level = key_chain_len_dec + start_level;
588
589 let (pk, v) = self.pool[level].remove(&key_chain[key_chain_len_dec]).unwrap();
590
591 if level > 0 {
592 if let Some(v) = self.sub[level - 1].get_mut(&last_key.unwrap()) {
593 v.remove(&key_chain[key_chain_len_dec]);
594 }
595 }
596
597 let sub = self.sub[level].remove(&key_chain[key_chain_len_dec]).unwrap();
598
599 if sub.is_empty() {
600 return Ok((pk, v, Vec::new()));
601 }
602
603 let mut sub_values: Vec<HashMap<Arc<K>, (Option<Arc<K>>, V)>> = Vec::new();
604 let mut my_sub_values = HashMap::new();
605
606 for s in sub {
607 let (a, b, mut c) = self.remove_professional(&[Arc::clone(&s)], level + 1).unwrap();
608
609 let len = c.len();
610
611 sub_values.reserve(len);
612
613 c.reverse();
614
615 for i in (0..len).rev() {
616 if let Some(h) = sub_values.get_mut(i) {
617 for (k, v) in c.remove(i) {
618 h.insert(k, v);
619 }
620 continue;
621 }
622 sub_values.push(c.remove(i));
623 }
624
625 my_sub_values.insert(s, (a, b));
626 }
627
628 sub_values.insert(0, my_sub_values);
629
630 Ok((pk, v, sub_values))
631 }
632
633 /// Insert a value by a key chain. It returns a `Err(LeveledHashMapError)` instance to describe the reason of the getting failure.
634 /// ```
635 /// use std::sync::Arc;
636 ///
637 /// use leveled_hash_map::LeveledHashMap;
638 ///
639 /// let mut map: LeveledHashMap<&'static str, String> = LeveledHashMap::new();
640 ///
641 /// map.insert(&[Arc::new("food")], "食物".to_string()).unwrap();
642 ///
643 /// {
644 /// let result = map.get(&[Arc::new("food")]).unwrap();
645 ///
646 /// assert_eq!("食物", result);
647 /// }
648 ///
649 /// let result = map.insert(&[Arc::new("food")], "食品".to_string()).unwrap();
650 ///
651 /// assert_eq!(Some("食物".to_string()), result);
652 ///
653 /// let result = map.get(&[Arc::new("food")]).unwrap();
654 ///
655 /// assert_eq!("食品", result);
656 /// ```
657 pub fn insert(
658 &mut self,
659 key_chain: &[Arc<K>],
660 value: V,
661 ) -> Result<Option<V>, LeveledHashMapError<K>> {
662 let key_chain_len = key_chain.len();
663
664 if key_chain_len == 0 {
665 return Err(LeveledHashMapError::KeyChainEmpty);
666 }
667
668 let key_chain_len_dec = key_chain_len - 1;
669
670 if key_chain_len_dec > self.pool.len() {
671 return Err(LeveledHashMapError::KeyTooMany);
672 }
673
674 match self.get_professional(key_chain, 0) {
675 Ok(_) => {
676 if key_chain_len_dec > 0 {
677 Ok(self.pool[key_chain_len_dec]
678 .insert(
679 Arc::clone(&key_chain[key_chain_len_dec]),
680 (Some(Arc::clone(&key_chain[key_chain_len_dec - 1])), value),
681 )
682 .map(|v| v.1))
683 } else {
684 Ok(self.pool[0].insert(Arc::clone(&key_chain[0]), (None, value)).map(|v| v.1))
685 }
686 }
687 Err(err) => {
688 match err {
689 LeveledHashMapError::KeyChainEmpty => Err(LeveledHashMapError::KeyChainEmpty),
690 LeveledHashMapError::KeyTooMany => {
691 let mut map = HashMap::new();
692
693 if self.pool.is_empty() {
694 map.insert(Arc::clone(&key_chain[0]), (None, value));
695
696 self.pool.push(map);
697
698 let mut map = HashMap::new();
699
700 map.insert(Arc::clone(&key_chain[0]), HashSet::new());
701
702 self.sub.push(map);
703
704 Ok(None)
705 } else {
706 map.insert(
707 Arc::clone(&key_chain[key_chain_len_dec]),
708 (Some(Arc::clone(&key_chain[key_chain_len_dec - 1])), value),
709 );
710
711 self.pool.push(map);
712
713 let mut map = HashMap::new();
714
715 map.insert(Arc::clone(&key_chain[key_chain_len_dec]), HashSet::new());
716
717 self.sub.push(map);
718
719 let map = self.sub[key_chain_len_dec - 1]
720 .get_mut(&key_chain[key_chain_len_dec - 1])
721 .unwrap();
722
723 map.insert(Arc::clone(&key_chain[key_chain_len_dec]));
724
725 Ok(None)
726 }
727 }
728 LeveledHashMapError::KeyChainIncorrect {
729 level,
730 key,
731 last_key,
732 } => {
733 Err(LeveledHashMapError::KeyChainIncorrect {
734 level,
735 key,
736 last_key,
737 })
738 }
739 LeveledHashMapError::KeyNotExist {
740 level,
741 key,
742 } => {
743 self.sub[level]
744 .insert(Arc::clone(&key_chain[key_chain_len_dec]), HashSet::new());
745 if level > 0 {
746 self.pool[level].insert(
747 key,
748 (Some(Arc::clone(&key_chain[key_chain_len_dec - 1])), value),
749 );
750 self.sub[level - 1]
751 .get_mut(&key_chain[key_chain_len_dec - 1])
752 .unwrap()
753 .insert(Arc::clone(&key_chain[key_chain_len_dec]));
754 } else {
755 self.pool[level].insert(key, (None, value));
756 }
757 Ok(None)
758 }
759 }
760 }
761 }
762 }
763
764 /// Insert values by a key chain and a `HashMap` instance and a level which the key chain starts with. It returns a `Err(LeveledHashMapError)` instance to describe the reason of the getting failure.
765 /// ```
766 /// use std::collections::HashMap;
767 /// use std::sync::Arc;
768 ///
769 /// use leveled_hash_map::LeveledHashMap;
770 ///
771 /// let mut map: LeveledHashMap<&'static str, String> = LeveledHashMap::new();
772 ///
773 /// map.insert(&[Arc::new("food")], "食物".to_string()).unwrap();
774 ///
775 /// let mut insert_map = HashMap::new();
776 ///
777 /// insert_map.insert("dessert", "甜點".to_string());
778 /// insert_map.insert("meat", "肉類".to_string());
779 ///
780 /// map.insert_many(&[Arc::new("food")], insert_map, 0).unwrap();
781 ///
782 /// let result = map.get(&[Arc::new("food"), Arc::new("dessert")]).unwrap();
783 ///
784 /// assert_eq!("甜點", result);
785 ///
786 /// let result = map.get(&[Arc::new("food"), Arc::new("meat")]).unwrap();
787 ///
788 /// assert_eq!("肉類", result);
789 /// ```
790 pub fn insert_many(
791 &mut self,
792 key_chain: &[Arc<K>],
793 value: HashMap<K, V>,
794 start_level: usize,
795 ) -> Result<HashMap<Arc<K>, V>, LeveledHashMapError<K>> {
796 let key_chain_len = key_chain.len();
797
798 if key_chain_len > self.pool.len() + 1 {
799 return Err(LeveledHashMapError::KeyTooMany);
800 }
801
802 match self.get_professional(key_chain, start_level) {
803 Ok(_) => {
804 let key_chain_len_dec = key_chain_len - 1;
805
806 let mut previous = HashMap::new();
807
808 let level = key_chain_len + start_level;
809
810 if level >= self.pool.len() {
811 self.pool.push(HashMap::new());
812 self.sub.push(HashMap::new());
813 }
814
815 let last_key = &key_chain[key_chain_len_dec];
816
817 let mut temp = HashMap::new();
818
819 for (k, v) in value {
820 let k = Arc::new(k);
821
822 if let Some((pk, _)) = self.pool[level].get(&Arc::clone(&k)) {
823 if last_key.ne(pk.as_ref().unwrap()) {
824 return Err(LeveledHashMapError::KeyChainIncorrect {
825 level,
826 key: Arc::clone(&k),
827 last_key: pk.as_ref().map(Arc::clone),
828 });
829 }
830 }
831
832 temp.insert(k, v);
833 }
834
835 for (k, v) in temp {
836 match self.pool[level].insert(Arc::clone(&k), (Some(Arc::clone(last_key)), v)) {
837 Some((_, v)) => {
838 previous.insert(k, v);
839 }
840 None => {
841 self.sub[level].insert(Arc::clone(&k), HashSet::new());
842 self.sub[level - 1].get_mut(last_key).unwrap().insert(Arc::clone(&k));
843 }
844 }
845 }
846
847 Ok(previous)
848 }
849 Err(err) => {
850 match err {
851 LeveledHashMapError::KeyChainIncorrect {
852 level,
853 key,
854 last_key,
855 } => {
856 Err(LeveledHashMapError::KeyChainIncorrect {
857 level,
858 key,
859 last_key,
860 })
861 }
862 LeveledHashMapError::KeyNotExist {
863 level,
864 key,
865 } => {
866 Err(LeveledHashMapError::KeyNotExist {
867 level,
868 key,
869 })
870 }
871 LeveledHashMapError::KeyTooMany => Err(LeveledHashMapError::KeyTooMany),
872 LeveledHashMapError::KeyChainEmpty => {
873 if start_level > 0 {
874 return Err(LeveledHashMapError::KeyChainEmpty);
875 }
876
877 if self.pool.is_empty() {
878 self.pool.push(HashMap::new());
879 self.sub.push(HashMap::new());
880 }
881
882 let mut previous = HashMap::new();
883
884 for (k, v) in value {
885 let k = Arc::new(k);
886 match self.pool[0].insert(Arc::clone(&k), (None, v)) {
887 Some((_, v)) => {
888 previous.insert(k, v);
889 }
890 None => {
891 self.sub[0].insert(Arc::clone(&k), HashSet::new());
892 }
893 }
894 }
895
896 Ok(previous)
897 }
898 }
899 }
900 }
901 }
902
903 /// Get the keys at a specific level.
904 /// ```
905 /// use std::collections::HashMap;
906 /// use std::sync::Arc;
907 ///
908 /// use leveled_hash_map::LeveledHashMap;
909 ///
910 /// let mut map: LeveledHashMap<&'static str, String> = LeveledHashMap::new();
911 ///
912 /// map.insert(&[Arc::new("food")], "食物".to_string()).unwrap();
913 ///
914 /// let mut insert_map = HashMap::new();
915 ///
916 /// insert_map.insert("dessert", "甜點".to_string());
917 /// insert_map.insert("meat", "肉類".to_string());
918 ///
919 /// map.insert_many(&[Arc::new("food")], insert_map, 0).unwrap();
920 ///
921 /// let result = map.keys(0).unwrap();
922 ///
923 /// assert_eq!(1, result.len());
924 ///
925 /// let result = map.keys(1).unwrap();
926 ///
927 /// assert_eq!(2, result.len());
928 /// ```
929 #[inline]
930 pub fn keys(&self, level: usize) -> Option<&HashMap<Arc<K>, HashSet<Arc<K>>>> {
931 self.sub.get(level)
932 }
933}
934
935impl<K: Eq + Hash, V> Default for LeveledHashMap<K, V> {
936 #[inline]
937 fn default() -> Self {
938 LeveledHashMap::new()
939 }
940}