1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96

use hydrate_base::hashing::HashSet;
use std::hash::Hash;

#[derive(Clone, Default)]
pub struct OrderedSet<T: Eq + PartialEq + Hash + Clone> {
    vec: Vec<T>,
    // the set is just a lookup, the vec is the real authority
    set: HashSet<T>,
}

impl<T: Eq + PartialEq + Hash + Clone> PartialEq for OrderedSet<T> {
    fn eq(
        &self,
        other: &Self,
    ) -> bool {
        self.vec == other.vec
    }
}

impl<'a, T: Eq + PartialEq + Hash + Clone> IntoIterator for &'a OrderedSet<T> {
    type Item = &'a T;
    type IntoIter = std::slice::Iter<'a, T>;

    fn into_iter(self) -> Self::IntoIter {
        self.iter()
    }
}

impl<T: std::fmt::Debug + Eq + PartialEq + Hash + Clone> std::fmt::Debug for OrderedSet<T> {
    fn fmt(
        &self,
        f: &mut std::fmt::Formatter<'_>,
    ) -> std::fmt::Result {
        f.debug_struct("OrderedSet")
            .field("vec", &self.vec)
            // Don't include the set because it's redundant
            .finish()
    }
}

impl<T: Eq + PartialEq + Hash + Clone> OrderedSet<T> {
    pub fn iter(&self) -> std::slice::Iter<T> {
        self.vec.iter()
    }

    pub fn contains(
        &self,
        value: &T,
    ) -> bool {
        self.set.contains(value)
    }

    // Returns true if insert is "successful". Otherwise it's false if it already existed
    pub fn try_insert_at_position(
        &mut self,
        index: usize,
        value: T,
    ) -> bool {
        let is_newly_inserted = self.set.insert(value.clone());
        if is_newly_inserted {
            self.vec.insert(index, value);
        }

        is_newly_inserted
    }

    // Returns true if insert is "successful". Otherwise it's false if it already existed
    pub fn try_insert_at_end(
        &mut self,
        value: T,
    ) -> bool {
        let is_newly_inserted = self.set.insert(value.clone());
        if is_newly_inserted {
            self.vec.push(value);
        }

        is_newly_inserted
    }

    pub fn remove(
        &mut self,
        value: &T,
    ) -> bool {
        let removed = self.set.remove(value);
        if removed {
            self.vec
                .remove(self.vec.iter().position(|x| x == value).unwrap());
        }

        removed
    }

    pub fn is_empty(&self) -> bool {
        self.vec.is_empty()
    }
}