cairo_lang_utils/
collection_arithmetics.rs

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
#[cfg(test)]
#[path = "collection_arithmetics_test.rs"]
mod test;

use core::hash::{BuildHasher, Hash};
use core::ops::{Add, Sub};

use crate::ordered_hash_map::{Entry, OrderedHashMap};

/// A trait for types which have a zero value.
///
/// Functions may assume the following:
/// * `x = x + zero() = zero() + x`
pub trait HasZero {
    /// Returns the zero value for the type.
    fn zero() -> Self;
}
impl HasZero for i32 {
    fn zero() -> Self {
        0
    }
}
impl HasZero for i64 {
    fn zero() -> Self {
        0
    }
}

/// Returns a map which contains the sum of the values from the given two maps, for each key.
///
/// If the key is missing from one of them, it is treated as zero.
pub fn add_maps<
    Key: Hash + Eq,
    Value: HasZero + Add<Output = Value> + Clone + Eq,
    Rhs: IntoIterator<Item = (Key, Value)>,
    BH: BuildHasher,
>(
    lhs: OrderedHashMap<Key, Value, BH>,
    rhs: Rhs,
) -> OrderedHashMap<Key, Value, BH> {
    merge_maps(lhs, rhs, |a, b| a + b)
}

/// Returns a map which contains the difference of the values from the given two maps, for each key.
///
/// If the key is missing from one of them, it is treated as zero.
pub fn sub_maps<
    Key: Hash + Eq,
    Value: HasZero + Sub<Output = Value> + Clone + Eq,
    Rhs: IntoIterator<Item = (Key, Value)>,
    BH: BuildHasher,
>(
    lhs: OrderedHashMap<Key, Value, BH>,
    rhs: Rhs,
) -> OrderedHashMap<Key, Value, BH> {
    merge_maps(lhs, rhs, |a, b| a - b)
}

/// Returns a map which contains the combination by using `action` of the values from the given two
/// maps, for each key.
///
/// If the key is missing from one of them, it is treated as zero.
fn merge_maps<
    Key: Hash + Eq,
    Value: HasZero + Clone + Eq,
    Rhs: IntoIterator<Item = (Key, Value)>,
    Action: Fn(Value, Value) -> Value,
    BH: BuildHasher,
>(
    lhs: OrderedHashMap<Key, Value, BH>,
    rhs: Rhs,
    action: Action,
) -> OrderedHashMap<Key, Value, BH> {
    let mut res = lhs;
    for (key, rhs_val) in rhs {
        match res.entry(key) {
            Entry::Occupied(mut e) => {
                let new_val = action(e.get().clone(), rhs_val);
                if new_val == Value::zero() {
                    e.swap_remove();
                } else {
                    e.insert(new_val);
                }
            }
            Entry::Vacant(e) => {
                if rhs_val != Value::zero() {
                    e.insert(action(Value::zero(), rhs_val));
                }
            }
        }
    }
    res
}