pcp/variable/
store.rs

1// Copyright 2015 Pierre Talbot (IRCAM)
2
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6
7//     http://www.apache.org/licenses/LICENSE-2.0
8
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15use kernel::*;
16use variable::ops::*;
17use variable::concept::*;
18use term::identity::*;
19use gcollections::kind::*;
20use gcollections::ops::*;
21use model::*;
22use vec_map::{Drain, VecMap};
23use std::slice;
24use std::marker::PhantomData;
25use std::fmt::{Display, Debug};
26use std::ops::Index;
27
28#[derive(Clone, Debug, PartialEq, Eq)]
29pub struct Store<Memory, Event>
30{
31  memory: Memory,
32  delta: VecMap<Event>,
33  has_changed: bool
34}
35
36impl<Memory, Event> Collection for Store<Memory, Event> where
37  Memory: MemoryConcept
38{
39  type Item = <Memory as Collection>::Item;
40}
41
42impl<Memory, Event> AssociativeCollection for Store<Memory, Event> where
43  Memory: MemoryConcept
44{
45  type Location = Identity<<Memory as Collection>::Item>;
46}
47
48impl<Memory, Event, Domain> ImmutableMemoryConcept for Store<Memory, Event> where
49 Memory: MemoryConcept<Item=Domain>,
50 Event: Debug
51{}
52
53impl<Memory, Domain, Bound, Event> VStoreConcept for Store<Memory, Event> where
54 Memory: MemoryConcept<Item=Domain>,
55 Domain: Subset + Cardinality + Bounded<Item=Bound> + Display,
56 Event: EventConcept<Domain>
57{
58}
59
60impl<Memory, Event> Store<Memory, Event> where
61 Memory: MemoryConcept
62{
63  fn from_memory(memory: Memory) -> Self {
64    Store {
65      memory: memory,
66      delta: VecMap::new(),
67      has_changed: false
68    }
69  }
70}
71
72impl<Memory, Event> Empty for Store<Memory, Event> where
73 Memory: MemoryConcept
74{
75  fn empty() -> Store<Memory, Event> {
76    Store::from_memory(Memory::empty())
77  }
78}
79
80impl<Memory, Domain, Event> Store<Memory, Event> where
81 Memory: MemoryConcept,
82 Memory: Collection<Item=Domain>,
83 Domain: Subset + Cardinality + Bounded,
84 Event: EventConcept<Domain>
85{
86  // FIXME: Need a rustc fix on borrowing rule, `updated` not needed.
87  fn update_delta(&mut self, key: usize, old_dom: &Domain) {
88    if let Some(delta) = Event::new(&self[key], old_dom) {
89      self.has_changed = true;
90      let mut updated = false;
91      if let Some(old_delta) = self.delta.get_mut(key) {
92        *old_delta = Merge::merge(old_delta.clone(), delta.clone());
93        updated = true;
94      }
95      if !updated {
96        self.delta.insert(key, delta);
97      }
98    }
99  }
100}
101
102impl<Memory, Event> Cardinality for Store<Memory, Event> where
103 Memory: MemoryConcept
104{
105  type Size = usize;
106
107  fn size(&self) -> usize {
108    self.memory.size()
109  }
110}
111
112impl<Memory, Event> Iterable for Store<Memory, Event> where
113 Memory: MemoryConcept
114{
115  fn iter<'a>(&'a self) -> slice::Iter<'a, Self::Item> {
116    self.memory.iter()
117  }
118}
119
120impl<Memory, Domain, Event> Alloc for Store<Memory, Event> where
121 Memory: MemoryConcept,
122 Memory: Collection<Item=Domain>,
123 Domain: Cardinality + IsEmpty
124{
125  fn alloc(&mut self, dom: Self::Item) -> Self::Location {
126    assert!(!dom.is_empty());
127    let var_idx = self.memory.size();
128    self.memory.push(dom);
129    Identity::new(var_idx)
130  }
131}
132
133impl<Memory, Domain, Event> MonotonicUpdate for Store<Memory, Event> where
134 Memory: MemoryConcept,
135 Memory: Collection<Item=Domain>,
136 Domain: Subset + Cardinality + Bounded,
137 Event: EventConcept<Domain>
138{
139  // We update the domain located at `loc` if `dom` is not empty and is a strictly smaller than the current value.
140  fn update(&mut self, loc: &Identity<Domain>, dom: Self::Item) -> bool {
141    let idx = loc.index();
142    assert!(dom.is_subset(&self.memory[idx]),
143      "Domain update must be monotonic.");
144    if dom.is_empty() {
145      false
146    }
147    else {
148      if dom.size() < self[idx].size() {
149        let old_dom = self.memory.replace(idx, dom);
150        self.update_delta(idx, &old_dom);
151      }
152      true
153    }
154  }
155}
156
157impl<Memory, Event> Index<usize> for Store<Memory, Event> where
158 Memory: MemoryConcept
159{
160  type Output = <Memory as Collection>::Item;
161
162  fn index<'a>(&'a self, index: usize) -> &'a Self::Output {
163    assert!(index < self.memory.size(),
164      "Variable not registered in the store. Variable index must be obtained with `alloc`.");
165    &self.memory[index]
166  }
167}
168
169impl<Memory, Event, Domain> Store<Memory, Event> where
170 Memory: MemoryConcept<Item=Domain>,
171 Domain: Display + IsSingleton
172{
173  fn display_var_matrix(&self, model: &Model,
174    var_idx: Vec<usize>, header: &str)
175  {
176    let header_width = 15;
177    let var_width = 20;
178    let num_columns = 8;
179    print!("{:>width$} ", header, width=header_width);
180    for (i,idx) in var_idx.into_iter().enumerate() {
181      if (i+1) % (num_columns+1) == 0 {
182        print!("\n{:>width$} ", "", width=header_width);
183      }
184      let var_str = format!("{:<6} = {}", model.var_name(idx), self[idx]);
185      print!("{:<width$}", var_str, width=var_width);
186    }
187    println!();
188  }
189}
190
191impl<Memory, Event, Domain> DisplayStateful<Model> for Store<Memory, Event> where
192 Memory: MemoryConcept<Item=Domain>,
193 Domain: Display + IsSingleton
194{
195  fn display(&self, model: &Model) {
196    let mut idx_assigned = vec![];
197    let mut idx_others = vec![];
198    for (i,dom) in self.memory.iter().enumerate() {
199      if dom.is_singleton() {
200        idx_assigned.push(i);
201      }
202      else {
203        idx_others.push(i);
204      }
205    }
206    self.display_var_matrix(model, idx_assigned, "assigned:");
207    self.display_var_matrix(model, idx_others, "not assigned:");
208  }
209}
210
211impl<Memory, Event> DrainDelta<Event> for Store<Memory, Event>
212{
213  fn drain_delta<'a>(&'a mut self) -> Drain<'a, Event> {
214    self.delta.drain()
215  }
216
217  fn has_changed(&self) -> bool {
218    self.has_changed
219  }
220
221  fn reset_changed(&mut self) {
222    self.has_changed = false;
223  }
224}
225
226impl<Memory, Event> Freeze for Store<Memory, Event> where
227 Memory: MemoryConcept
228{
229  type FrozenState = FrozenStore<Memory, Event>;
230  fn freeze(self) -> Self::FrozenState
231  {
232    FrozenStore::new(self)
233  }
234}
235
236pub struct FrozenStore<Memory, Event> where
237 Memory: MemoryConcept
238{
239  frozen_memory: Memory::FrozenState,
240  phantom_event: PhantomData<Event>
241}
242
243impl<Memory, Event> FrozenStore<Memory, Event> where
244 Memory: MemoryConcept
245{
246  fn new(store: Store<Memory, Event>) -> Self {
247    FrozenStore {
248      frozen_memory: store.memory.freeze(),
249      phantom_event: PhantomData
250    }
251  }
252}
253
254impl<Memory, Event> Snapshot for FrozenStore<Memory, Event> where
255 Memory: MemoryConcept
256{
257  type Label = <Memory::FrozenState as Snapshot>::Label;
258  type State = Store<Memory, Event>;
259
260  fn label(&mut self) -> Self::Label {
261    self.frozen_memory.label()
262  }
263
264  fn restore(self, label: Self::Label) -> Self::State {
265    Store::from_memory(self.frozen_memory.restore(label))
266  }
267}
268
269#[cfg(test)]
270pub mod test {
271  use variable::VStoreFD;
272  use variable::ops::*;
273  use term::ops::*;
274  use term::identity::*;
275  use propagation::events::*;
276  use propagation::events::FDEvent::*;
277  use interval::interval::*;
278  use gcollections::ops::*;
279
280  pub type Domain = Interval<i32>;
281  pub type VStore = VStoreFD;
282
283  pub fn consume_delta(store: &mut VStore, delta_expected: Vec<(usize, FDEvent)>) {
284    let res: Vec<(usize, FDEvent)> = store.drain_delta().collect();
285    assert_eq!(res, delta_expected);
286    assert!(store.drain_delta().next().is_none());
287  }
288
289  #[test]
290  fn ordered_assign_10_vars() {
291    let dom0_10 = (0, 10).to_interval();
292    let mut store = VStore::empty();
293
294    for i in 0..10 {
295      assert_eq!(store.alloc(dom0_10), Identity::new(i));
296    }
297  }
298
299  #[test]
300  fn valid_read_update() {
301    let dom0_10 = (0, 10).to_interval();
302    let dom5_5 = (5, 5).to_interval();
303    let mut store = VStore::empty();
304
305    let vars: Vec<_> = (0..10).map(|_| store.alloc(dom0_10)).collect();
306    for mut var in vars {
307      assert_eq!(var.read(&store), dom0_10);
308      assert_eq!(var.update(&mut store, dom5_5), true);
309      assert_eq!(var.read(&store), dom5_5);
310    }
311  }
312
313  #[test]
314  fn empty_update() {
315    let mut store = VStore::empty();
316    let dom5_5 = (5, 5).to_interval();
317
318    let mut var = store.alloc(dom5_5);
319    assert_eq!(var.update(&mut store, Interval::empty()), false);
320  }
321
322  #[test]
323  #[should_panic]
324  fn empty_assign() {
325    let mut store = VStore::empty();
326    store.alloc(Interval::<i32>::empty());
327  }
328
329  #[test]
330  #[should_panic]
331  fn non_monotonic_update_singleton() {
332    let dom0_10 = (0,10).to_interval();
333    let dom11_11 = 11.to_interval();
334
335    let mut store = VStore::empty();
336    let mut var = store.alloc(dom0_10);
337    var.update(&mut store, dom11_11);
338  }
339
340  #[test]
341  #[should_panic]
342  fn non_monotonic_update_widen() {
343    let dom0_10 = (0,10).to_interval();
344    let domm5_15 = (-5, 15).to_interval();
345
346    let mut store = VStore::empty();
347    let mut var = store.alloc(dom0_10);
348    var.update(&mut store, domm5_15);
349  }
350
351  fn test_op<Op>(test_num: u32, source: Domain, target: Domain, delta_expected: Vec<FDEvent>, update_success: bool, op: Op) where
352    Op: FnOnce(&VStore, Identity<Domain>) -> Domain
353  {
354    println!("Test number {}", test_num);
355    let mut store = VStore::empty();
356    let mut var = store.alloc(source);
357
358    let new = op(&store, var);
359    assert_eq!(var.update(&mut store, new), update_success);
360    assert_eq!(new, target);
361
362    if update_success {
363      let delta_expected = delta_expected.into_iter().map(|d| (var.index(), d)).collect();
364      consume_delta(&mut store, delta_expected);
365      assert_eq!(var.read(&store), target);
366    }
367  }
368
369  fn test_binary_op<Op>(source1: Domain, source2: Domain, target: Domain, delta_expected: Vec<(usize, FDEvent)>, update_success: bool, op: Op) where
370    Op: FnOnce(&VStore, Identity<Domain>, Identity<Domain>) -> Domain
371  {
372    let mut store = VStore::empty();
373    let mut var1 = store.alloc(source1);
374    let mut var2 = store.alloc(source2);
375
376    let new = op(&store, var1, var2);
377    assert_eq!(var1.update(&mut store, new), update_success);
378    assert_eq!(var2.update(&mut store, new), update_success);
379    assert_eq!(new, target);
380
381    if update_success {
382      consume_delta(&mut store, delta_expected);
383      assert_eq!(var1.read(&store), target);
384      assert_eq!(var2.read(&store), target);
385    }
386  }
387
388  #[test]
389  fn var_update_test() {
390    let dom0_10 = (0,10).to_interval();
391    let dom0_9 = (0,5).to_interval();
392    let dom1_10 = (5,10).to_interval();
393    let dom1_9 = (1,9).to_interval();
394    let dom0_0 = (0,0).to_interval();
395    let empty = Interval::empty();
396
397    var_update_test_one(1, dom0_10, dom0_10, vec![], true);
398    var_update_test_one(2, dom0_10, empty, vec![], false);
399    var_update_test_one(3, dom0_10, dom0_0, vec![Assignment], true);
400    var_update_test_one(4, dom0_10, dom1_10, vec![Bound], true);
401    var_update_test_one(5, dom0_10, dom0_9, vec![Bound], true);
402    var_update_test_one(6, dom0_10, dom1_9, vec![Bound], true);
403  }
404
405  fn var_update_test_one(test_num: u32, source: Domain, target: Domain, delta_expected: Vec<FDEvent>, update_success: bool) {
406    test_op(test_num, source, target, delta_expected, update_success, |_,_| target);
407  }
408
409  #[test]
410  fn var_shrink_bound() {
411    let dom0_10 = (0,10).to_interval();
412
413    var_shrink_lb_test_one(1, dom0_10, 0, vec![], true);
414    var_shrink_lb_test_one(2, dom0_10, 10, vec![Assignment], true);
415    var_shrink_lb_test_one(3, dom0_10, 1, vec![Bound], true);
416    var_shrink_lb_test_one(4, dom0_10, 11, vec![], false);
417
418    var_shrink_ub_test_one(5, dom0_10, 10, vec![], true);
419    var_shrink_ub_test_one(6, dom0_10, 0, vec![Assignment], true);
420    var_shrink_ub_test_one(7, dom0_10, 1, vec![Bound], true);
421    var_shrink_ub_test_one(8, dom0_10, -1, vec![], false);
422  }
423
424  fn var_shrink_lb_test_one(test_num: u32, source: Domain, target_lb: i32, delta_expected: Vec<FDEvent>, update_success: bool) {
425    let expected_dom = (target_lb, source.upper()).to_interval();
426
427    test_op(test_num, source, expected_dom, delta_expected, update_success,
428      |store, var| var.read(store).shrink_left(target_lb));
429  }
430
431  fn var_shrink_ub_test_one(test_num: u32, source: Domain, target_ub: i32, delta_expected: Vec<FDEvent>, update_success: bool) {
432    let expected_dom = (source.lower(), target_ub).to_interval();
433
434    test_op(test_num, source, expected_dom, delta_expected, update_success,
435      |store, var| var.read(store).shrink_right(target_ub));
436  }
437
438  #[test]
439  fn var_intersection_test() {
440    let dom0_10 = (0,10).to_interval();
441    let dom10_20 = (10,20).to_interval();
442    let dom10_10 = (10,10).to_interval();
443    let dom11_20 = (11,20).to_interval();
444    let dom1_9 = (1,9).to_interval();
445
446    var_intersection_test_one(dom0_10, dom10_20, dom10_10, vec![(0, Assignment), (1, Assignment)], true);
447    var_intersection_test_one(dom0_10, dom1_9, dom1_9, vec![(0, Bound)], true);
448    var_intersection_test_one(dom1_9, dom0_10, dom1_9, vec![(1, Bound)], true);
449    var_intersection_test_one(dom0_10, dom11_20, Interval::empty(), vec![], false);
450  }
451
452  fn var_intersection_test_one(source1: Domain, source2: Domain, target: Domain, delta_expected: Vec<(usize, FDEvent)>, update_success: bool) {
453    test_binary_op(source1, source2, target, delta_expected, update_success,
454      |store, v1, v2| v1.read(store).intersection(&v2.read(store)));
455  }
456}
pcp/variable/store.rs

pcp/variable/
store.rs
