boa/builtins/set/
ordered_set.rs

1use crate::gc::{custom_trace, Finalize, Trace};
2use indexmap::{
3    set::{IntoIter, Iter},
4    IndexSet,
5};
6use std::{
7    collections::hash_map::RandomState,
8    fmt::Debug,
9    hash::{BuildHasher, Hash},
10};
11
12/// A newtype wrapping indexmap::IndexSet
13#[derive(Clone)]
14pub struct OrderedSet<V, S = RandomState>(IndexSet<V, S>)
15where
16    V: Hash + Eq;
17
18impl<V: Eq + Hash + Trace, S: BuildHasher> Finalize for OrderedSet<V, S> {}
19unsafe impl<V: Eq + Hash + Trace, S: BuildHasher> Trace for OrderedSet<V, S> {
20    custom_trace!(this, {
21        for v in this.0.iter() {
22            mark(v);
23        }
24    });
25}
26
27impl<V: Hash + Eq + Debug> Debug for OrderedSet<V> {
28    fn fmt(&self, formatter: &mut std::fmt::Formatter<'_>) -> Result<(), std::fmt::Error> {
29        self.0.fmt(formatter)
30    }
31}
32
33impl<V: Hash + Eq> Default for OrderedSet<V> {
34    fn default() -> Self {
35        Self::new()
36    }
37}
38
39impl<V> OrderedSet<V>
40where
41    V: Hash + Eq,
42{
43    pub fn new() -> Self {
44        OrderedSet(IndexSet::new())
45    }
46
47    pub fn with_capacity(capacity: usize) -> Self {
48        OrderedSet(IndexSet::with_capacity(capacity))
49    }
50
51    /// Return the number of key-value pairs in the map.
52    ///
53    /// Computes in **O(1)** time.
54    pub fn size(&self) -> usize {
55        self.0.len()
56    }
57
58    /// Returns true if the map contains no elements.
59    ///
60    /// Computes in **O(1)** time.
61    pub fn is_empty(&self) -> bool {
62        self.0.len() == 0
63    }
64
65    /// Insert a value pair in the set.
66    ///
67    /// If an equivalent value already exists in the set: ???
68    ///
69    /// If no equivalent value existed in the set: the new value is
70    /// inserted, last in order, and false
71    ///
72    /// Computes in **O(1)** time (amortized average).
73    pub fn add(&mut self, value: V) -> bool {
74        self.0.insert(value)
75    }
76
77    /// Delete the `value` from the set and return true if successful
78    ///
79    /// Return `false` if `value` is not in map.
80    ///
81    /// Computes in **O(n)** time (average).
82    pub fn delete(&mut self, value: &V) -> bool {
83        self.0.shift_remove(value)
84    }
85
86    /// Checks if a given value is present in the set
87    ///
88    /// Return `true` if `value` is present in set, false otherwise.
89    ///
90    /// Computes in **O(n)** time (average).
91    pub fn contains(&self, value: &V) -> bool {
92        self.0.contains(value)
93    }
94
95    /// Get a key-value pair by index
96    /// Valid indices are 0 <= index < self.len()
97    /// Computes in O(1) time.
98    pub fn get_index(&self, index: usize) -> Option<&V> {
99        self.0.get_index(index)
100    }
101
102    /// Return an iterator over the values of the set, in their order
103    pub fn iter(&self) -> Iter<'_, V> {
104        self.0.iter()
105    }
106}
107
108impl<'a, V, S> IntoIterator for &'a OrderedSet<V, S>
109where
110    V: Hash + Eq,
111    S: BuildHasher,
112{
113    type Item = &'a V;
114    type IntoIter = Iter<'a, V>;
115    fn into_iter(self) -> Self::IntoIter {
116        self.0.iter()
117    }
118}
119
120impl<V, S> IntoIterator for OrderedSet<V, S>
121where
122    V: Hash + Eq,
123    S: BuildHasher,
124{
125    type Item = V;
126    type IntoIter = IntoIter<V>;
127    fn into_iter(self) -> IntoIter<V> {
128        self.0.into_iter()
129    }
130}
boa/builtins/set/ordered_set.rs

boa/builtins/set/
ordered_set.rs
