Grcov report - antichain.rs

1

use std::collections::HashMap;

2

use std::fmt;

3

use std::hash::Hash;

4

5

use merc_collections::VecSet;

6

7

/// An antichain is a data structure that stores pairs of (s, T) \subset S x 2^S, where `S` is a set of elements that have a total order <.

8

/// The antichain maintains the invariant that for any two pairs (s1, T1) and (s2, T2) in the antichain, neither s1 < s2 nor s2 < s1 holds, i.e.,

9

/// it is dual to a chain.

10

pub struct Antichain<K, V> {

11

    storage: HashMap<K, VecSet<VecSet<V>>>,

12

13

    /// The largest size of the antichain.

14

    max_antichain: usize,

15

    /// Number of times a pair was inserted into the antichain.

16

    antichain_misses: usize,

17

    /// Number of times antichain_insert was called.

18

    antichain_inserts: usize,

19

20

21

impl<K: Eq + Hash, V: Clone + Ord> Antichain<K, V> {

22

    /// Creates a new empty antichain.

23

201

    pub fn new() -> Self {

24

201

        Antichain {

25

201

            storage: HashMap::new(),

26

201

            max_antichain: 0,

27

201

            antichain_misses: 0,

28

201

            antichain_inserts: 0,

29

201

30

201

31

32

    /// Inserts the given (s, T) pair into the antichain and returns true iff it was

33

    /// not already present.

34

158714

    pub fn insert(&mut self, key: K, value: VecSet<V>) -> bool {

35

158714

        let mut inserted = false;

36

158714

        self.storage

37

158714

            .entry(key)

38

158714

            .and_modify(|entry| {

39

144519

                let mut contains = false;

40

216628

                entry.retain(|inner_value| {

41

216628

                    if inner_value.is_subset(&value) {

42

                        // The new value is a superset of an existing entry

43

128250

                        contains = true;

44

128250

                        true

45

88378

                    } else if value.is_subset(inner_value) {

46

                        // Remove any entry that is a superset of the new value

47

10478

                        false

48

                    } else {

49

                        // Leave incomparable entries unchanged

50

77900

                        true

51

52

216628

});

53

54

144519

                if !contains {

55

16798

                    self.antichain_misses += 1; // Was not present

56

16798

                    entry.insert(value.clone());

57

16798

                    inserted = true;

58

127721

59

144519

})

60

158714

            .or_insert_with(|| {

61

14195

                self.antichain_misses += 1; // Was not present

62

14195

                inserted = true;

63

14195

                VecSet::singleton(value)

64

14195

});

65

66

158714

        self.antichain_inserts += 1;

67

158714

        self.max_antichain = self.max_antichain.max(self.storage.len());

68

69

158714

        inserted

70

158714

71

72

73

impl<K: Eq + Hash, V: Clone + Ord> Default for Antichain<K, V> {

74

    fn default() -> Self {

75

        Self::new()

76

77

78

79

impl<K, V: fmt::Debug + Ord> Antichain<K, V> {

80

    /// Checks the internal consistency of the antichain invariant.

81

    #[cfg(test)]

82

100

    fn check_consistency(&self) {

83

992

        for (_key, values) in &self.storage {

84

4293

            for i in values.iter() {

85

21359

                for j in values.iter() {

86

21359

                    if i == j {

87

                        // Ignore identical entries

88

4293

                        continue;

89

17066

90

91

17066

                    assert!(

92

17066

                        !i.is_subset(j) && !j.is_subset(i),

93

                        "Antichain invariant violated: {:?} and {:?} are comparable.",

94

i,

95

96

);

97

98

99

100

101

102

103

impl<T: fmt::Debug, U: fmt::Debug> fmt::Debug for Antichain<T, U> {

104

1

    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {

105

1

        writeln!(f, "Antichain {{")?;

106

1

        for (key, values) in &self.storage {

107

1

            writeln!(f, "  {:?}: {:?}", key, values)?;

108

109

1

        writeln!(f, "}}")

110

1

111

112

113

#[cfg(test)]

114

mod tests {

115

    use merc_collections::vecset;

116

    use merc_utilities::random_test;

117

    use rand::Rng;

118

119

    use crate::Antichain;

120

121

    #[test]

122

1

    fn test_antichain() {

123

1

        let mut antichain: Antichain<u32, u32> = Antichain::new();

124

125

1

        let inserted = antichain.insert(1, vecset![2, 3]);

126

1

        assert!(inserted);

127

128

1

        println!("{:?}", antichain);

129

130

1

        let inserted = antichain.insert(1, vecset![2, 3, 6]);

131

1

        assert!(

132

1

            !inserted,

133

            "The pair (1, {{2,3,6}}) should not be inserted in {:?}.",

134

            antichain

135

);

136

137

1

        let inserted = antichain.insert(1, vecset![2]);

138

1

        assert!(

139

1

            inserted,

140

            "The pair (1, {{2}}) should overwrite (1, {{2, 3}}) in {:?}.",

141

            antichain

142

);

143

144

1

        let inserted = antichain.insert(1, vecset![5, 6]);

145

1

        assert!(

146

1

            inserted,

147

            "The pair (1, {{5, 6}}) should be inserted since it is incomparable to existing pairs in {:?}.",

148

            antichain

149

);

150

1

151

152

    #[test]

153

1

    fn test_random_antichain() {

154

100

        random_test(100, |rng| {

155

100

            let mut antichain: Antichain<u32, u32> = Antichain::new();

156

157

            // Insert random pairs into the antichain.

158

100

            for _ in 0..50 {

159

5000

                let key = rng.random_range(0..10);

160

5000

                let set_size = rng.random_range(1..5);

161

5000

                let mut value = vecset![];

162

163

12532

                for _ in 0..set_size {

164

12532

                    value.insert(rng.random_range(0..20));

165

12532

166

167

5000

                antichain.insert(key, value);

168

169

170

100

            antichain.check_consistency();

171

100

})

172

1

173