json_api/value/collections/map.rs
1//! A hash map implementation with consistent ordering.
2//!
3//! The types in this module are commonly used as the underlying data structure
4//! of arbitrary objects found in JSON API data.
5
6use std::fmt::{self, Debug, Formatter};
7use std::hash::Hash;
8use std::iter::FromIterator;
9use std::ops::RangeFull;
10
11use ordermap::{self, OrderMap};
12use serde::de::{Deserialize, Deserializer};
13use serde::ser::{Serialize, Serializer};
14
15use value::{Key, Value};
16use value::collections::Equivalent;
17
18/// A hash map implementation with consistent ordering.
19#[derive(Clone, Eq, PartialEq)]
20pub struct Map<K = Key, V = Value>
21where
22 K: Eq + Hash,
23{
24 inner: OrderMap<K, V>,
25}
26
27impl<K, V> Map<K, V>
28where
29 K: Eq + Hash,
30{
31 /// Creates an empty `Map`.
32 ///
33 /// # Example
34 ///
35 /// ```
36 /// # extern crate json_api;
37 /// #
38 /// # fn main() {
39 /// use json_api::value::{Key, Map, Value};
40 /// let mut map = Map::<Key, Value>::new();
41 /// # }
42 /// ```
43 pub fn new() -> Self {
44 Default::default()
45 }
46
47 /// Creates a new empty `Map`, with specified capacity.
48 ///
49 /// # Example
50 ///
51 /// ```
52 /// # extern crate json_api;
53 /// #
54 /// # use json_api::Error;
55 /// # use json_api::value::Map;
56 /// #
57 /// # fn example() -> Result<(), Error> {
58 /// let mut map = Map::with_capacity(2);
59 ///
60 /// map.insert("x", 1);
61 /// map.insert("y", 2);
62 ///
63 /// // The next insert will likely require reallocation...
64 /// map.insert("z", 3);
65 /// #
66 /// # Ok(())
67 /// # }
68 /// #
69 /// # fn main() {
70 /// # example().unwrap();
71 /// # }
72 /// ```
73 pub fn with_capacity(capacity: usize) -> Self {
74 let inner = OrderMap::with_capacity(capacity);
75 Map { inner }
76 }
77
78 /// Returns the number of key-value pairs the map can hold without
79 /// reallocating.
80 ///
81 /// # Example
82 ///
83 /// ```
84 /// # extern crate json_api;
85 /// #
86 /// # use json_api::value::{Key, Map, Value};
87 /// #
88 /// # fn main() {
89 /// let map = Map::<Key, Value>::with_capacity(2);
90 /// assert!(map.capacity() >= 2);
91 /// # }
92 /// ```
93 pub fn capacity(&self) -> usize {
94 self.inner.capacity()
95 }
96
97 /// Clears the map, removing all key-value pairs. Keeps the allocated memory
98 /// for reuse.
99 ///
100 /// # Example
101 ///
102 /// ```
103 /// # extern crate json_api;
104 /// #
105 /// # use json_api::value::Map;
106 /// #
107 /// # fn main() {
108 /// let mut map = Map::new();
109 ///
110 /// map.insert("x", 1);
111 /// map.clear();
112 /// assert!(map.is_empty());
113 /// # }
114 /// ```
115 pub fn clear(&mut self) {
116 self.inner.clear();
117 }
118
119 /// Returns true if the map contains a value for the specified key.
120 ///
121 /// # Example
122 ///
123 /// ```
124 /// # extern crate json_api;
125 /// #
126 /// # use json_api::value::Map;
127 /// #
128 /// # fn main() {
129 /// let mut map = Map::new();
130 ///
131 /// map.insert(1, "a");
132 /// assert_eq!(map.contains_key(&1), true);
133 /// assert_eq!(map.contains_key(&2), false);
134 /// # }
135 /// ```
136 pub fn contains_key<Q: ?Sized>(&self, key: &Q) -> bool
137 where
138 Q: Equivalent<K> + Hash,
139 {
140 self.inner.contains_key(key)
141 }
142
143 /// Clears the map, returning all key-value pairs as an iterator. Keeps the
144 /// allocated memory for reuse.
145 ///
146 /// # Example
147 ///
148 /// ```
149 /// # extern crate json_api;
150 /// #
151 /// # use json_api::value::Map;
152 /// #
153 /// # fn main() {
154 /// let mut map = Map::new();
155 ///
156 /// map.insert("x", 1);
157 /// map.insert("y", 2);
158 ///
159 /// for (key, value) in map.drain(..) {
160 /// assert!(key == "x" || key == "y");
161 /// assert!(value == 1 || value == 2);
162 /// }
163 ///
164 /// assert!(map.is_empty());
165 /// # }
166 /// ```
167 pub fn drain(&mut self, range: RangeFull) -> Drain<K, V> {
168 let iter = self.inner.drain(range);
169 Drain { iter }
170 }
171
172 /// Returns a reference to the value corresponding to the key.
173 ///
174 /// # Example
175 ///
176 /// ```
177 /// # extern crate json_api;
178 /// #
179 /// # use json_api::value::Map;
180 /// #
181 /// # fn main() {
182 /// let mut map = Map::new();
183 ///
184 /// map.insert("x", 1);
185 ///
186 /// assert_eq!(map.get("x"), Some(&1));
187 /// assert_eq!(map.get("y"), None);
188 /// # }
189 /// ```
190 pub fn get<Q: ?Sized>(&self, key: &Q) -> Option<&V>
191 where
192 Q: Equivalent<K> + Hash,
193 {
194 self.inner.get(key)
195 }
196
197 /// Inserts a key-value pair into the map.
198 ///
199 /// If a value already existed for key, that old value is returned in
200 /// `Some`; otherwise, `None` is returned.
201 ///
202 /// # Example
203 ///
204 /// ```
205 /// # extern crate json_api;
206 /// #
207 /// # use json_api::value::Map;
208 /// #
209 /// # fn main() {
210 /// let mut map = Map::new();
211 ///
212 /// assert_eq!(map.insert("x", 1), None);
213 /// assert_eq!(map.insert("x", 2), Some(1));
214 /// # }
215 /// ```
216 pub fn insert(&mut self, key: K, value: V) -> Option<V> {
217 self.inner.insert(key, value)
218 }
219
220 /// Return an iterator visiting all the key-value pairs of the map in the
221 /// order in which they were inserted.
222 ///
223 /// # Example
224 ///
225 /// ```
226 /// # extern crate json_api;
227 /// #
228 /// # use json_api::value::Map;
229 /// #
230 /// # fn main() {
231 /// let mut map = Map::new();
232 ///
233 /// map.insert("a", 1);
234 /// map.insert("b", 2);
235 /// map.insert("c", 3);
236 ///
237 /// for (key, value) in map.iter() {
238 /// println!("key: {} value: {}", key, value);
239 /// }
240 /// # }
241 /// ```
242 pub fn iter(&self) -> Iter<K, V> {
243 let iter = self.inner.iter();
244 Iter { iter }
245 }
246
247 /// Return an iterator visiting all the key-value pairs of the map in the
248 /// order in which they were inserted, with mutable references to the
249 /// values.
250 ///
251 /// # Example
252 ///
253 /// ```
254 /// # extern crate json_api;
255 /// #
256 /// # use json_api::value::Map;
257 /// #
258 /// # fn main() {
259 /// let mut map = Map::new();
260 ///
261 /// map.insert("a", 1);
262 /// map.insert("b", 2);
263 /// map.insert("c", 3);
264 ///
265 /// for (_, value) in map.iter_mut() {
266 /// *value += 1;
267 /// }
268 ///
269 /// for (key, value) in &map {
270 /// println!("key: {} value: {}", key, value);
271 /// }
272 /// # }
273 /// ```
274 pub fn iter_mut(&mut self) -> IterMut<K, V> {
275 let iter = self.inner.iter_mut();
276 IterMut { iter }
277 }
278
279 /// Return an iterator visiting all keys in the order in which they were
280 /// inserted.
281 ///
282 /// # Example
283 ///
284 /// ```
285 /// # extern crate json_api;
286 /// #
287 /// # use json_api::value::Map;
288 /// #
289 /// # fn main() {
290 /// let mut map = Map::new();
291 ///
292 /// map.insert("a", 1);
293 /// map.insert("b", 2);
294 /// map.insert("c", 3);
295 ///
296 /// for key in map.keys() {
297 /// println!("{}", key);
298 /// }
299 /// # }
300 /// ```
301 pub fn keys(&self) -> Keys<K, V> {
302 let iter = self.inner.keys();
303 Keys { iter }
304 }
305
306 /// Return the number of key-value pairs in the map.
307 ///
308 /// # Example
309 ///
310 /// ```
311 /// # extern crate json_api;
312 /// #
313 /// # use json_api::value::Map;
314 /// #
315 /// # fn main() {
316 /// let mut map = Map::new();
317 /// assert_eq!(map.len(), 0);
318 ///
319 /// map.insert("x", 1);
320 /// assert_eq!(map.len(), 1);
321 /// # }
322 /// ```
323 pub fn len(&self) -> usize {
324 self.inner.len()
325 }
326
327 /// Returns true if the map contains no elements.
328 ///
329 /// # Example
330 ///
331 /// ```
332 /// # extern crate json_api;
333 /// #
334 /// # use json_api::value::Map;
335 /// #
336 /// # fn main() {
337 /// let mut map = Map::new();
338 /// assert!(map.is_empty());
339 ///
340 /// map.insert("x", 1);
341 /// assert!(!map.is_empty());
342 /// # }
343 /// ```
344 pub fn is_empty(&self) -> bool {
345 self.len() == 0
346 }
347
348 /// Removes a key from the map, returning the value at the key if the key
349 /// was previously in the map.
350 ///
351 /// # Example
352 ///
353 /// ```
354 /// # extern crate json_api;
355 /// #
356 /// # use json_api::value::Map;
357 /// #
358 /// # fn main() {
359 /// let mut map = Map::new();
360 ///
361 /// map.insert("x", 1);
362 ///
363 /// assert_eq!(map.remove("x"), Some(1));
364 /// assert_eq!(map.remove("x"), None);
365 /// # }
366 /// ```
367 pub fn remove<Q: ?Sized>(&mut self, key: &Q) -> Option<V>
368 where
369 Q: Equivalent<K> + Hash,
370 {
371 self.inner.remove(key)
372 }
373
374
375 /// Reserves capacity for at least additional more elements to be inserted
376 /// in the `Map`. The collection may reserve more space to avoid frequent
377 /// reallocations.
378 ///
379 /// # Note
380 ///
381 /// This method has yet to be fully implemented in the [`ordermap`] crate.
382 ///
383 /// # Example
384 ///
385 /// ```
386 /// # extern crate json_api;
387 /// #
388 /// # use json_api::value::{Key, Map, Value};
389 /// #
390 /// # fn main() {
391 /// let mut map = Map::<Key, Value>::new();
392 /// map.reserve(10);
393 /// # }
394 /// ```
395 ///
396 /// [`ordermap`]: https://docs.rs/ordermap
397 pub fn reserve(&mut self, additional: usize) {
398 self.inner.reserve(additional);
399 }
400
401 /// Return an iterator visiting all values in the order in which they were
402 /// inserted.
403 ///
404 /// # Example
405 ///
406 /// ```
407 /// # extern crate json_api;
408 /// #
409 /// # use json_api::value::Map;
410 /// #
411 /// # fn main() {
412 /// let mut map = Map::new();
413 ///
414 /// map.insert("a", 1);
415 /// map.insert("b", 2);
416 /// map.insert("c", 3);
417 ///
418 /// for value in map.values() {
419 /// println!("{}", value);
420 /// }
421 /// # }
422 /// ```
423 pub fn values(&self) -> Values<K, V> {
424 let iter = self.inner.values();
425 Values { iter }
426 }
427
428 /// Return an iterator visiting all values mutably in the order in which
429 /// they were inserted.
430 ///
431 /// # Example
432 ///
433 /// ```
434 /// # extern crate json_api;
435 /// #
436 /// # use json_api::value::Map;
437 /// #
438 /// # fn main() {
439 /// let mut map = Map::new();
440 ///
441 /// map.insert("a", 1);
442 /// map.insert("b", 2);
443 /// map.insert("c", 3);
444 ///
445 /// for value in map.values_mut() {
446 /// *value += 1;
447 /// }
448 ///
449 /// for value in map.values() {
450 /// println!("{}", value);
451 /// }
452 /// # }
453 pub fn values_mut(&mut self) -> ValuesMut<K, V> {
454 let iter = self.inner.values_mut();
455 ValuesMut { iter }
456 }
457}
458
459impl<K, V> Debug for Map<K, V>
460where
461 K: Debug + Eq + Hash,
462 V: Debug,
463{
464 fn fmt(&self, f: &mut Formatter) -> fmt::Result {
465 f.debug_map().entries(self).finish()
466 }
467}
468
469impl<K, V> Default for Map<K, V>
470where
471 K: Eq + Hash,
472{
473 fn default() -> Self {
474 let inner = Default::default();
475 Map { inner }
476 }
477}
478
479impl<K, V> Extend<(K, V)> for Map<K, V>
480where
481 K: Eq + Hash,
482{
483 fn extend<I>(&mut self, iter: I)
484 where
485 I: IntoIterator<Item = (K, V)>,
486 {
487 self.inner.extend(iter);
488 }
489}
490
491impl<K, V> FromIterator<(K, V)> for Map<K, V>
492where
493 K: Eq + Hash,
494{
495 fn from_iter<I>(iter: I) -> Self
496 where
497 I: IntoIterator<Item = (K, V)>,
498 {
499 let inner = OrderMap::from_iter(iter);
500 Map { inner }
501 }
502}
503
504impl<K, V> IntoIterator for Map<K, V>
505where
506 K: Eq + Hash,
507{
508 type Item = (K, V);
509 type IntoIter = IntoIter<K, V>;
510
511 fn into_iter(self) -> Self::IntoIter {
512 let iter = self.inner.into_iter();
513 IntoIter { iter }
514 }
515}
516
517impl<'a, K, V> IntoIterator for &'a Map<K, V>
518where
519 K: Eq + Hash,
520{
521 type Item = (&'a K, &'a V);
522 type IntoIter = Iter<'a, K, V>;
523
524 fn into_iter(self) -> Self::IntoIter {
525 self.iter()
526 }
527}
528
529impl<'a, K, V> IntoIterator for &'a mut Map<K, V>
530where
531 K: Eq + Hash,
532{
533 type Item = (&'a K, &'a mut V);
534 type IntoIter = IterMut<'a, K, V>;
535
536 fn into_iter(self) -> Self::IntoIter {
537 self.iter_mut()
538 }
539}
540
541impl<'de, K, V> Deserialize<'de> for Map<K, V>
542where
543 K: Deserialize<'de> + Eq + Hash,
544 V: Deserialize<'de>,
545{
546 fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
547 where
548 D: Deserializer<'de>,
549 {
550 OrderMap::deserialize(deserializer).map(|inner| Map { inner })
551 }
552}
553
554impl<K, V> Serialize for Map<K, V>
555where
556 K: Eq + Hash + Serialize,
557 V: Serialize,
558{
559 fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
560 where
561 S: Serializer,
562 {
563 self.inner.serialize(serializer)
564 }
565}
566
567/// A draining iterator over the entries of a `Map`.
568pub struct Drain<'a, K: 'a, V: 'a> {
569 iter: ordermap::Drain<'a, K, V>,
570}
571
572impl<'a, K, V> Iterator for Drain<'a, K, V> {
573 type Item = (K, V);
574
575 fn next(&mut self) -> Option<Self::Item> {
576 self.iter.next()
577 }
578
579 fn size_hint(&self) -> (usize, Option<usize>) {
580 self.iter.size_hint()
581 }
582}
583
584/// An iterator over the entries of a `Map`.
585pub struct Iter<'a, K: 'a, V: 'a> {
586 iter: ordermap::Iter<'a, K, V>,
587}
588
589impl<'a, K, V> Iterator for Iter<'a, K, V> {
590 type Item = (&'a K, &'a V);
591
592 fn next(&mut self) -> Option<Self::Item> {
593 self.iter.next()
594 }
595
596 fn count(self) -> usize {
597 self.iter.len()
598 }
599
600 fn last(mut self) -> Option<Self::Item> {
601 self.next_back()
602 }
603
604 fn nth(&mut self, n: usize) -> Option<Self::Item> {
605 self.iter.nth(n)
606 }
607
608 fn size_hint(&self) -> (usize, Option<usize>) {
609 self.iter.size_hint()
610 }
611}
612
613impl<'a, K, V> DoubleEndedIterator for Iter<'a, K, V> {
614 fn next_back(&mut self) -> Option<Self::Item> {
615 self.iter.next_back()
616 }
617}
618
619impl<'a, K, V> ExactSizeIterator for Iter<'a, K, V> {
620 fn len(&self) -> usize {
621 self.iter.len()
622 }
623}
624
625/// An mutable iterator over the entries of a `Map`.
626pub struct IterMut<'a, K: 'a, V: 'a> {
627 iter: ordermap::IterMut<'a, K, V>,
628}
629
630impl<'a, K, V> Iterator for IterMut<'a, K, V> {
631 type Item = (&'a K, &'a mut V);
632
633 fn next(&mut self) -> Option<Self::Item> {
634 self.iter.next()
635 }
636
637 fn count(self) -> usize {
638 self.iter.len()
639 }
640
641 fn last(mut self) -> Option<Self::Item> {
642 self.next_back()
643 }
644
645 fn nth(&mut self, n: usize) -> Option<Self::Item> {
646 self.iter.nth(n)
647 }
648
649 fn size_hint(&self) -> (usize, Option<usize>) {
650 self.iter.size_hint()
651 }
652}
653
654impl<'a, K, V> DoubleEndedIterator for IterMut<'a, K, V> {
655 fn next_back(&mut self) -> Option<Self::Item> {
656 self.iter.next_back()
657 }
658}
659
660impl<'a, K, V> ExactSizeIterator for IterMut<'a, K, V> {
661 fn len(&self) -> usize {
662 self.iter.len()
663 }
664}
665
666/// An owning iterator over the entries of a `Map`.
667pub struct IntoIter<K, V> {
668 iter: ordermap::IntoIter<K, V>,
669}
670
671impl<K, V> Iterator for IntoIter<K, V> {
672 type Item = (K, V);
673
674 fn next(&mut self) -> Option<Self::Item> {
675 self.iter.next()
676 }
677
678 fn count(self) -> usize {
679 self.iter.len()
680 }
681
682 fn last(mut self) -> Option<Self::Item> {
683 self.next_back()
684 }
685
686 fn nth(&mut self, n: usize) -> Option<Self::Item> {
687 self.iter.nth(n)
688 }
689
690 fn size_hint(&self) -> (usize, Option<usize>) {
691 self.iter.size_hint()
692 }
693}
694
695impl<K, V> DoubleEndedIterator for IntoIter<K, V> {
696 fn next_back(&mut self) -> Option<Self::Item> {
697 self.iter.next_back()
698 }
699}
700
701impl<K, V> ExactSizeIterator for IntoIter<K, V> {
702 fn len(&self) -> usize {
703 self.iter.len()
704 }
705}
706
707/// An iterator over the keys of a `Map`.
708pub struct Keys<'a, K: 'a, V: 'a> {
709 iter: ordermap::Keys<'a, K, V>,
710}
711
712impl<'a, K, V> Iterator for Keys<'a, K, V> {
713 type Item = &'a K;
714
715 fn next(&mut self) -> Option<Self::Item> {
716 self.iter.next()
717 }
718
719 fn count(self) -> usize {
720 self.iter.len()
721 }
722
723 fn last(mut self) -> Option<Self::Item> {
724 self.next_back()
725 }
726
727 fn nth(&mut self, n: usize) -> Option<Self::Item> {
728 self.iter.nth(n)
729 }
730
731 fn size_hint(&self) -> (usize, Option<usize>) {
732 self.iter.size_hint()
733 }
734}
735
736impl<'a, K, V> DoubleEndedIterator for Keys<'a, K, V> {
737 fn next_back(&mut self) -> Option<Self::Item> {
738 self.iter.next_back()
739 }
740}
741
742impl<'a, K, V> ExactSizeIterator for Keys<'a, K, V> {
743 fn len(&self) -> usize {
744 self.iter.len()
745 }
746}
747
748/// An iterator over the values of a `Map`.
749pub struct Values<'a, K: 'a, V: 'a> {
750 iter: ordermap::Values<'a, K, V>,
751}
752
753impl<'a, K, V> Iterator for Values<'a, K, V> {
754 type Item = &'a V;
755
756 fn next(&mut self) -> Option<Self::Item> {
757 self.iter.next()
758 }
759
760 fn count(self) -> usize {
761 self.iter.len()
762 }
763
764 fn last(mut self) -> Option<Self::Item> {
765 self.next_back()
766 }
767
768 fn nth(&mut self, n: usize) -> Option<Self::Item> {
769 self.iter.nth(n)
770 }
771
772 fn size_hint(&self) -> (usize, Option<usize>) {
773 self.iter.size_hint()
774 }
775}
776
777impl<'a, K, V> DoubleEndedIterator for Values<'a, K, V> {
778 fn next_back(&mut self) -> Option<Self::Item> {
779 self.iter.next_back()
780 }
781}
782
783impl<'a, K, V> ExactSizeIterator for Values<'a, K, V> {
784 fn len(&self) -> usize {
785 self.iter.len()
786 }
787}
788
789/// A mutable iterator over the values of a `Map`.
790pub struct ValuesMut<'a, K: 'a, V: 'a> {
791 iter: ordermap::ValuesMut<'a, K, V>,
792}
793
794impl<'a, K, V> Iterator for ValuesMut<'a, K, V> {
795 type Item = &'a mut V;
796
797 fn next(&mut self) -> Option<Self::Item> {
798 self.iter.next()
799 }
800
801 fn count(self) -> usize {
802 self.iter.len()
803 }
804
805 fn last(mut self) -> Option<Self::Item> {
806 self.next_back()
807 }
808
809 fn nth(&mut self, n: usize) -> Option<Self::Item> {
810 self.iter.nth(n)
811 }
812
813 fn size_hint(&self) -> (usize, Option<usize>) {
814 self.iter.size_hint()
815 }
816}
817
818impl<'a, K, V> DoubleEndedIterator for ValuesMut<'a, K, V> {
819 fn next_back(&mut self) -> Option<Self::Item> {
820 self.iter.next_back()
821 }
822}
823
824impl<'a, K, V> ExactSizeIterator for ValuesMut<'a, K, V> {
825 fn len(&self) -> usize {
826 self.iter.len()
827 }
828}