ddo/implementation/dominance/
simple.rs

1// Copyright 2020 Xavier Gillard
2//
3// Permission is hereby granted, free of charge, to any person obtaining a copy of
4// this software and associated documentation files (the "Software"), to deal in
5// the Software without restriction, including without limitation the rights to
6// use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of
7// the Software, and to permit persons to whom the Software is furnished to do so,
8// subject to the following conditions:
9//
10// The above copyright notice and this permission notice shall be included in all
11// copies or substantial portions of the Software.
12//
13// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
14// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS
15// FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR
16// COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER
17// IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
18// CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
19
20use std::{hash::Hash, cmp::Ordering, sync::Arc, fmt::Debug};
21use dashmap::{DashMap, mapref::entry::Entry};
22
23use crate::{Dominance, DominanceChecker, DominanceCmpResult, DominanceCheckResult};
24
25/// Simple implementation of a dominance checker that stores a vector of non-dominated
26/// states for each distinct key.
27
28#[derive(Debug)]
29struct DominanceEntry<T> {
30    state: Arc<T>,
31    value: isize,
32}
33
34type DominanceMap<K, S> = DashMap<K, Vec<DominanceEntry<S>>, fxhash::FxBuildHasher>;
35
36#[derive(Debug)]
37pub struct SimpleDominanceChecker<D>
38where
39    D: Dominance,
40    D::Key: Eq + PartialEq + Hash,
41{
42    dominance: D,
43    data: Vec<DominanceMap<D::Key, D::State>>,
44}
45
46impl<D> SimpleDominanceChecker<D> 
47where
48    D: Dominance,
49    D::Key: Eq + PartialEq + Hash,
50{
51    pub fn new(dominance: D, nb_variables: usize) -> Self {
52        let mut data = vec![];
53        for _ in 0..=nb_variables {
54            data.push(Default::default());
55        }
56        Self { dominance, data }
57    }
58}
59
60impl<D> DominanceChecker for SimpleDominanceChecker<D> 
61where
62    D: Dominance,
63    D::Key: Eq + PartialEq + Hash,
64{
65    type State = D::State;
66
67    fn clear_layer(&self, depth: usize) {
68        self.data[depth].clear();
69    }
70
71    fn is_dominated_or_insert(&self, state: Arc<Self::State>, depth: usize, value: isize) -> DominanceCheckResult {
72        if let Some(key) = self.dominance.get_key(state.clone()) {
73            match self.data[depth].entry(key) {
74                Entry::Occupied(mut e) => {
75                    let mut dominated = false;
76                    let mut threshold = Some(isize::MAX);
77                    e.get_mut().retain(|other| {
78                        match self.dominance.partial_cmp(state.as_ref(), value, other.state.as_ref(), other.value) {
79                            Some(cmp) => match cmp {
80                                DominanceCmpResult { ordering: Ordering::Less, only_val_diff} => {
81                                    dominated = true;
82                                    if self.dominance.use_value() {
83                                        if only_val_diff {
84                                            threshold = threshold.min(Some(other.value.saturating_sub(1)));
85                                        } else {
86                                            threshold = threshold.min(Some(other.value));
87                                        }
88                                    }
89                                    true
90                                },
91                                DominanceCmpResult { ordering: Ordering::Equal, only_val_diff: _ } => false,
92                                DominanceCmpResult { ordering: Ordering::Greater, only_val_diff: _ } => false,
93                            },
94                            None => true,
95                        }
96                    });
97                    if !dominated {
98                        threshold = None;
99                        e.get_mut().push(DominanceEntry { state, value });
100                    }
101                    DominanceCheckResult { dominated, threshold }
102                },
103                Entry::Vacant(e) => {
104                    e.insert(vec![DominanceEntry { state, value }]);
105                    DominanceCheckResult { dominated: false, threshold: None }
106                },
107            }
108        } else {
109            DominanceCheckResult { dominated: false, threshold: None }
110        }
111    }
112
113    fn cmp(&self, a: &Self::State, val_a: isize, b: &Self::State, val_b: isize) -> Ordering {
114        self.dominance.cmp(a, val_a, b, val_b)
115    }
116}
117
118#[cfg(test)]
119mod tests {
120    use std::sync::Arc;
121
122    use crate::{Dominance, SimpleDominanceChecker, DominanceChecker, DominanceCheckResult};
123
124    #[test]
125    fn not_dominated_when_keys_are_different() {
126        let dominance = SimpleDominanceChecker::new(DummyDominanceWithValue, 0);
127
128        assert_eq!(DominanceCheckResult{ dominated: false, threshold: None }, dominance.is_dominated_or_insert(Arc::new(vec![3, 0]), 0, 3));
129        assert_eq!(DominanceCheckResult{ dominated: false, threshold: None }, dominance.is_dominated_or_insert(Arc::new(vec![2, 0]), 0, 2));
130        assert_eq!(DominanceCheckResult{ dominated: false, threshold: None }, dominance.is_dominated_or_insert(Arc::new(vec![1, 0]), 0, 1));
131        assert_eq!(DominanceCheckResult{ dominated: false, threshold: None }, dominance.is_dominated_or_insert(Arc::new(vec![0, 0]), 0, 0));
132    }
133
134    #[test]
135    fn dominated_when_keys_are_equal() {
136        let dominance = SimpleDominanceChecker::new(DummyDominance, 0);
137
138        assert_eq!(DominanceCheckResult{ dominated: false, threshold: None }, dominance.is_dominated_or_insert(Arc::new(vec![0, 3]), 0, 0));
139
140        let res = dominance.is_dominated_or_insert(Arc::new(vec![0, 2]), 0, 2);
141        assert!(res.dominated);
142
143        let res = dominance.is_dominated_or_insert(Arc::new(vec![0, 1]), 0, 1);
144        assert!(res.dominated);
145
146        let res = dominance.is_dominated_or_insert(Arc::new(vec![0, 0]), 0, 0);
147        assert!(res.dominated);
148
149        let dominance = SimpleDominanceChecker::new(DummyDominanceWithValue, 0);
150
151        assert_eq!(DominanceCheckResult{ dominated: false, threshold: None }, dominance.is_dominated_or_insert(Arc::new(vec![0, 0]), 0, 3));
152
153        let res = dominance.is_dominated_or_insert(Arc::new(vec![0, 0]), 0, 2);
154        assert!(res.dominated);
155
156        let res = dominance.is_dominated_or_insert(Arc::new(vec![0, 0]), 0, 1);
157        assert!(res.dominated);
158
159        let res = dominance.is_dominated_or_insert(Arc::new(vec![0, 0]), 0, 0);
160        assert!(res.dominated);
161
162        let res = dominance.is_dominated_or_insert(Arc::new(vec![0, -1]), 0, 3);
163        assert!(res.dominated);
164    }
165
166    #[test]
167    fn not_dominated_when_keys_are_equal() {
168        let dominance = SimpleDominanceChecker::new(DummyDominance, 0);
169
170        assert_eq!(DominanceCheckResult{ dominated: false, threshold: None }, dominance.is_dominated_or_insert(Arc::new(vec![0, 0, 3]), 0, 3));
171        assert_eq!(DominanceCheckResult{ dominated: false, threshold: None }, dominance.is_dominated_or_insert(Arc::new(vec![0, 0, 3]), 0, 1));
172        assert_eq!(DominanceCheckResult{ dominated: false, threshold: None }, dominance.is_dominated_or_insert(Arc::new(vec![0, 1, 1]), 0, 5));
173        assert_eq!(DominanceCheckResult{ dominated: false, threshold: None }, dominance.is_dominated_or_insert(Arc::new(vec![0, 0, 4]), 0, 3));
174
175        let dominance = SimpleDominanceChecker::new(DummyDominanceWithValue, 0);
176
177        assert_eq!(DominanceCheckResult{ dominated: false, threshold: None }, dominance.is_dominated_or_insert(Arc::new(vec![0, 0]), 0, 3));
178        assert_eq!(DominanceCheckResult{ dominated: false, threshold: None }, dominance.is_dominated_or_insert(Arc::new(vec![0, 3]), 0, 0));
179        assert_eq!(DominanceCheckResult{ dominated: false, threshold: None }, dominance.is_dominated_or_insert(Arc::new(vec![0, 1]), 0, 1));
180        assert_eq!(DominanceCheckResult{ dominated: false, threshold: None }, dominance.is_dominated_or_insert(Arc::new(vec![0, 0]), 0, 5));
181    }
182
183    #[test]
184    fn pruning_threshold_when_value_is_used() {
185        let dominance = SimpleDominanceChecker::new(DummyDominanceWithValue, 0);
186
187        assert_eq!(DominanceCheckResult{ dominated: false, threshold: None }, dominance.is_dominated_or_insert(Arc::new(vec![0, 0]), 0, 3));
188        assert_eq!(DominanceCheckResult{ dominated: true, threshold: Some(2) }, dominance.is_dominated_or_insert(Arc::new(vec![0, 0]), 0, 2));
189        assert_eq!(DominanceCheckResult{ dominated: true, threshold: Some(2) }, dominance.is_dominated_or_insert(Arc::new(vec![0, 0]), 0, 1));
190        assert_eq!(DominanceCheckResult{ dominated: true, threshold: Some(3) }, dominance.is_dominated_or_insert(Arc::new(vec![0, -1]), 0, 0));
191    }
192
193    #[test]
194    fn entry_is_added_only_when_dominant() {
195        let dominance = SimpleDominanceChecker::new(DummyDominanceWithValue, 0);
196
197        assert_eq!(DominanceCheckResult{ dominated: false, threshold: None }, dominance.is_dominated_or_insert(Arc::new(vec![0, 0]), 0, 3));
198        assert!(dominance.data[0].get(&0).is_some());
199        assert_eq!(1, dominance.data[0].get(&0).unwrap().len());
200
201        assert_eq!(DominanceCheckResult{ dominated: true, threshold: Some(2) }, dominance.is_dominated_or_insert(Arc::new(vec![0, 0]), 0, 1));
202        assert_eq!(1, dominance.data[0].get(&0).unwrap().len());
203
204        assert_eq!(DominanceCheckResult{ dominated: false, threshold: None }, dominance.is_dominated_or_insert(Arc::new(vec![0, 1]), 0, 1));
205        assert_eq!(2, dominance.data[0].get(&0).unwrap().len());
206
207        assert_eq!(DominanceCheckResult{ dominated: false, threshold: None }, dominance.is_dominated_or_insert(Arc::new(vec![0, -1]), 0, 5));
208        assert_eq!(3, dominance.data[0].get(&0).unwrap().len());
209    }
210
211    #[test]
212    fn entry_is_removed_when_dominated() {
213        let dominance = SimpleDominanceChecker::new(DummyDominanceWithValue, 0);
214
215        assert_eq!(DominanceCheckResult{ dominated: false, threshold: None }, dominance.is_dominated_or_insert(Arc::new(vec![0, 0]), 0, 3));
216        assert!(dominance.data[0].get(&0).is_some());
217        assert_eq!(1, dominance.data[0].get(&0).unwrap().len());
218
219        assert_eq!(DominanceCheckResult{ dominated: false, threshold: None }, dominance.is_dominated_or_insert(Arc::new(vec![0, 1]), 0, 5));
220        assert_eq!(1, dominance.data[0].get(&0).unwrap().len());
221
222        assert_eq!(DominanceCheckResult{ dominated: false, threshold: None }, dominance.is_dominated_or_insert(Arc::new(vec![0, 2]), 0, 7));
223        assert_eq!(1, dominance.data[0].get(&0).unwrap().len());
224    }
225
226    struct DummyDominance;
227    impl Dominance for DummyDominance {
228        type State = Vec<isize>;
229        type Key = isize;
230
231        fn get_key(&self, state: Arc<Self::State>) -> Option<Self::Key> {
232            Some(state[0])
233        }
234
235        fn nb_dimensions(&self, state: &Self::State) -> usize {
236            state.len()
237        }
238
239        fn get_coordinate(&self, state: &Self::State, i: usize) -> isize {
240            state[i]
241        }
242    }
243
244    struct DummyDominanceWithValue;
245    impl Dominance for DummyDominanceWithValue {
246        type State = Vec<isize>;
247        type Key = isize;
248
249        fn get_key(&self, state: Arc<Self::State>) -> Option<Self::Key> {
250            Some(state[0])
251        }
252
253        fn nb_dimensions(&self, state: &Self::State) -> usize {
254            state.len()
255        }
256
257        fn get_coordinate(&self, state: &Self::State, i: usize) -> isize {
258            state[i]
259        }
260
261        fn use_value(&self) -> bool {
262            true
263        }
264    }
265}
ddo/implementation/dominance/simple.rs

ddo/implementation/dominance/
simple.rs
