pcp/propagation/
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
15//! Represents the *constraint store* which is a conjunction of constraints, it also comes with an algorithm checking the consistency of the store. It is not a complete method for solving a constraint problem because the output can be `Unknown`. A complete solver is obtained using a search algorithm on top of the consistency algorithm.
16
17use kernel::*;
18use trilean::SKleene;
19use trilean::SKleene::*;
20use model::*;
21use propagation::Reactor;
22use propagation::Scheduler;
23use propagation::concept::*;
24use propagation::ops::*;
25use variable::ops::*;
26use gcollections::kind::*;
27use gcollections::ops::*;
28use std::ops::{Index, IndexMut};
29use bit_set::BitSet;
30
31#[derive(Debug)]
32pub struct Store<VStore, Event, Reactor, Scheduler>
33{
34  propagators: Vec<Box<dyn PropagatorConcept<VStore, Event> + 'static>>,
35  active: BitSet,
36  reactor: Reactor,
37  scheduler: Scheduler
38}
39
40impl<VStore, Event, R, S> Empty for Store<VStore, Event, R, S> where
41 Event: EventIndex,
42 R: Reactor,
43 S: Scheduler
44{
45  fn empty() -> Store<VStore, Event, R, S> {
46    Store {
47      propagators: vec![],
48      active: BitSet::new(),
49      reactor: Reactor::new(0,0),
50      scheduler: Scheduler::new(0)
51    }
52  }
53}
54
55impl<VStore, Event, R, S> Collection for Store<VStore, Event, R, S>
56{
57  type Item = Box<dyn PropagatorConcept<VStore, Event>>;
58}
59
60impl<VStore, Event, R, S> AssociativeCollection for Store<VStore, Event, R, S>
61{
62  type Location = usize;
63}
64
65impl<VStore, Event, R, S>  Cardinality for Store<VStore, Event, R, S>
66{
67  type Size = usize;
68
69  fn size(&self) -> usize {
70    self.propagators.len()
71  }
72}
73
74impl<VStore, Event, R, S> Store<VStore, Event, R, S>
75{
76  fn display_constraints(&self, model: &Model, indexes: Vec<usize>, header: &str) {
77    let header_width = 15;
78    print!("{:>width$} ", header, width=header_width);
79    let mut idx = 0;
80    while idx < indexes.len() {
81      self.propagators[indexes[idx]].display(model);
82      if idx < indexes.len() - 1 {
83        print!(" /\\ \n{:>width$} ", "", width=header_width);
84      }
85      idx += 1;
86    }
87    println!();
88  }
89}
90
91impl<VStore, Event, R, S> DisplayStateful<(Model, VStore)> for Store<VStore, Event, R, S>
92{
93  fn display(&self, &(ref model, ref vstore): &(Model, VStore)) {
94    let mut subsumed = vec![];
95    let mut unknown = vec![];
96    let mut unsatisfiable = vec![];
97    for (i, p) in self.propagators.iter().enumerate() {
98      match p.is_subsumed(&vstore) {
99        False => unsatisfiable.push(i),
100        True => subsumed.push(i),
101        Unknown => unknown.push(i)
102      };
103    }
104    self.display_constraints(&model, unsatisfiable, "unsatisfiable:");
105    self.display_constraints(&model, subsumed, "subsumed:");
106    self.display_constraints(&model, unknown, "unknown:");
107  }
108}
109
110impl<VStore, Event, R, S> DisplayStateful<Model> for Store<VStore, Event, R, S>
111{
112  fn display(&self, model: &Model) {
113    let mut i = 0;
114    while i < self.propagators.len() {
115      self.propagators[i].display(model);
116      if i < self.propagators.len() - 1 {
117        print!(" /\\ ");
118      }
119      i += 1;
120    }
121  }
122}
123
124impl<VStore, Event, R, S> Store<VStore, Event, R, S> where
125 VStore: Cardinality<Size=usize> + DrainDelta<Event>,
126 Event: EventIndex,
127 R: Reactor + Cardinality<Size=usize>,
128 S: Scheduler
129{
130  fn prepare(&mut self, vstore: &VStore) {
131    self.init_reactor(vstore);
132    self.init_scheduler();
133  }
134
135  fn init_reactor(&mut self, vstore: &VStore) {
136    self.reactor = Reactor::new(vstore.size(), Event::size());
137    for p_idx in self.active.iter() {
138      let p_deps = self[p_idx].dependencies();
139      for (v, ev) in p_deps {
140        debug_assert!(v < vstore.size(),
141          "The propagator {:?} has a dependency to the variable {} which is not in the vstore (of size {}).\n\
142          Hint: you should not manually create `Identity` struct, if you do make sure they contain relevant index to the variable vstore.",
143          self[p_idx], v, vstore.size());
144        self.reactor.subscribe(v, ev, p_idx);
145      }
146    }
147  }
148
149  fn init_scheduler(&mut self) {
150    self.scheduler = Scheduler::new(self.propagators.len());
151    for p_idx in self.active.iter() {
152      self.scheduler.schedule(p_idx);
153    }
154  }
155
156  fn propagation_loop(&mut self, vstore: &mut VStore) -> bool {
157    let mut consistent = true;
158    while !self.scheduler.is_empty() && consistent {
159      while let Some(p_idx) = self.scheduler.pop() {
160        if !self.propagate_one(p_idx, vstore) {
161          consistent = false;
162          break;
163        }
164        self.react(vstore);
165      }
166      // self.react(vstore); // For bulk reaction.
167    }
168    consistent
169  }
170
171  fn propagate_one(&mut self, p_idx: usize, vstore: &mut VStore) -> bool {
172    vstore.reset_changed();
173    let subsumed = self.propagator_consistency(p_idx, vstore);
174    match subsumed {
175      False => return false,
176      True => self.unlink_prop(p_idx),
177      Unknown => self.reschedule_prop(p_idx, vstore)
178    };
179    true
180  }
181
182  fn propagator_consistency(&mut self, p_idx: usize, vstore: &mut VStore) -> SKleene {
183    if self[p_idx].propagate(vstore) {
184      self[p_idx].is_subsumed(vstore)
185    } else {
186      False
187    }
188  }
189
190  fn reschedule_prop(&mut self, p_idx: usize, vstore: &mut VStore) {
191    if vstore.has_changed() {
192      self.scheduler.schedule(p_idx);
193    }
194  }
195
196  fn react(&mut self, vstore: &mut VStore) {
197    for (v, ev) in vstore.drain_delta() {
198      let reactions = self.reactor.react(v, ev);
199      for p in reactions.into_iter() {
200        self.scheduler.schedule(p);
201      }
202    }
203  }
204
205  fn unlink_prop(&mut self, p_idx: usize) {
206    self.active.remove(p_idx);
207    self.scheduler.unschedule(p_idx);
208    let deps = self[p_idx].dependencies();
209    for &(var, ev) in deps.iter() {
210      self.reactor.unsubscribe(var, ev, p_idx)
211    }
212  }
213}
214
215impl<VStore, Event, R, S> Index<usize> for Store<VStore, Event, R, S>
216{
217  type Output = Box<dyn PropagatorConcept<VStore, Event> + 'static>;
218  fn index<'a>(&'a self, index: usize) -> &'a Self::Output {
219    &self.propagators[index]
220  }
221}
222
223impl<VStore, Event, R, S> IndexMut<usize> for Store<VStore, Event, R, S>
224{
225  fn index_mut<'a>(&'a mut self, index: usize) -> &'a mut Self::Output {
226    &mut self.propagators[index]
227  }
228}
229
230impl<VStore, Event, R, S> Alloc for Store<VStore, Event, R, S>
231{
232  fn alloc(&mut self, p: Self::Item) -> usize {
233    let idx = self.propagators.len();
234    self.propagators.push(p);
235    self.active.insert(idx);
236    idx
237  }
238}
239
240impl<VStore, Event, R, S> Subsumption<VStore> for Store<VStore, Event, R, S>
241{
242  fn is_subsumed(&self, vstore: &VStore) -> SKleene {
243    self.propagators.iter()
244    .fold(True, |x,p| x.and(p.is_subsumed(vstore)))
245  }
246}
247
248impl<VStore, Event, R, S> Consistency<VStore> for Store<VStore, Event, R, S> where
249 VStore: Cardinality<Size=usize> + DrainDelta<Event>,
250 Event: EventIndex,
251 R: Reactor + Cardinality<Size=usize>,
252 S: Scheduler
253{
254  fn consistency(&mut self, vstore: &mut VStore) -> SKleene {
255    self.prepare(vstore);
256    let consistent = self.propagation_loop(vstore);
257    if !consistent { False }
258    else if self.reactor.is_empty() { True }
259    else { Unknown }
260  }
261}
262
263impl<VStore, Event, R, S> Clone for Store<VStore, Event, R, S> where
264 Event: EventIndex,
265 R: Reactor,
266 S: Scheduler
267{
268  fn clone(&self) -> Self {
269    let mut cstore = Store::empty();
270    cstore.propagators = self.propagators.iter()
271      .map(|p| p.bclone())
272      .collect();
273    cstore.active = self.active.clone();
274    cstore
275  }
276}
277
278impl<VStore, Event, R, S> Freeze for Store<VStore, Event, R, S> where
279 Event: EventIndex,
280 R: Reactor + Clone,
281 S: Scheduler
282{
283  type FrozenState = FrozenStore<VStore, Event, R, S>;
284  fn freeze(self) -> Self::FrozenState
285  {
286    FrozenStore::new(self)
287  }
288}
289
290pub struct FrozenStore<VStore, Event, R, S> where
291 Event: EventIndex,
292 R: Reactor + Clone,
293 S: Scheduler
294{
295  cstore: Store<VStore, Event, R, S>
296}
297
298impl<VStore, Event, R, S> FrozenStore<VStore, Event, R, S> where
299 Event: EventIndex,
300 R: Reactor + Clone,
301 S: Scheduler
302{
303  fn new(cstore: Store<VStore, Event, R, S>) -> Self {
304    FrozenStore {
305      cstore: cstore
306    }
307  }
308}
309
310impl<VStore, Event, R, S> Snapshot for FrozenStore<VStore, Event, R, S> where
311 Event: EventIndex,
312 R: Reactor + Clone,
313 S: Scheduler
314{
315  type Label = (usize, BitSet);
316  type State = Store<VStore, Event, R, S>;
317
318  fn label(&mut self) -> Self::Label {
319    (self.cstore.propagators.len(), self.cstore.active.clone())
320  }
321
322  fn restore(mut self, label: Self::Label) -> Self::State {
323    self.cstore.propagators.truncate(label.0);
324    self.cstore.active = label.1;
325    self.cstore
326  }
327}
328
329// #[cfg(test)]
330// mod test {
331//   use kernel::*;
332//   use trilean::SKleene::*;
333//   use variable::VStoreFD;
334//   use propagation::*;
335//   use propagators::cmp::*;
336//   use propagators::distinct::*;
337//   use term::addition::Addition;
338//   use interval::interval::*;
339//   use interval::ops::*;
340//   use gcollections::ops::*;
341
342//   type VStore = VStoreFD;
343//   type CStore = CStoreFD<VStore>;
344
345//   #[test]
346//   fn basic_test() {
347//     let variables: &mut VStore = &mut VStore::empty();
348//     let mut constraints: CStore = CStore::empty();
349
350//     assert_eq!(constraints.consistency(variables), True);
351
352//     let var1 = variables.alloc(Interval::new(1,4));
353//     let var2 = variables.alloc(Interval::new(1,4));
354//     let var3 = variables.alloc(Interval::new(1,1));
355
356//     assert_eq!(constraints.consistency(variables), True);
357
358//     constraints.alloc(Box::new(XLessY::new(var1.clone(), var2)));
359//     assert_eq!(constraints.consistency(variables), Unknown);
360
361//     constraints.alloc(Box::new(XEqY::new(var1, var3)));
362//     assert_eq!(constraints.consistency(variables), True);
363//   }
364
365//   fn chained_lt(n: usize, expect: SKleene) {
366//     // X1 < X2 < X3 < ... < XN, all in dom [1, 10]
367//     let variables: &mut VStore = &mut VStore::empty();
368//     let mut constraints: CStore = CStore::empty();
369//     let mut vars = vec![];
370//     for _ in 0..n {
371//       vars.push(variables.alloc(Interval::new(1,10)));
372//     }
373//     for i in 0..n-1 {
374//       constraints.alloc(Box::new(XLessY::new(vars[i].clone(), vars[i+1].clone())));
375//     }
376//     assert_eq!(constraints.consistency(variables), expect);
377//   }
378
379//   #[test]
380//   fn chained_lt_tests() {
381//     chained_lt(1, True);
382//     chained_lt(2, Unknown);
383//     chained_lt(5, Unknown);
384//     chained_lt(9, Unknown);
385//     chained_lt(10, True);
386//     chained_lt(11, False);
387//   }
388
389//   #[test]
390//   fn example_nqueens() {
391//     nqueens(1, True);
392//     nqueens(2, Unknown);
393//     nqueens(3, Unknown);
394//     nqueens(4, Unknown);
395//   }
396
397//   fn nqueens(n: usize, expect: SKleene) {
398//     let variables: &mut VStore = &mut VStore::empty();
399//     let mut constraints: CStore = CStore::empty();
400//     let mut queens = vec![];
401//     // 2 queens can't share the same line.
402//     for _ in 0..n {
403//       queens.push(variables.alloc((1, n as i32).to_interval()));
404//     }
405//     for i in 0..n-1 {
406//       for j in i + 1..n {
407//         // 2 queens can't share the same diagonal.
408//         let q1 = (i + 1) as i32;
409//         let q2 = (j + 1) as i32;
410//         // Xi + i != Xj + j
411//         constraints.alloc(Box::new(XNeqY::new(Addition::new(queens[i], q1), Addition::new(queens[j], q2))));
412//         // constraints.alloc(XNeqY::new(queens[i].clone(), Addition::new(queens[j].clone(), q2 - q1)));
413//         // Xi - i != Xj - j
414//         constraints.alloc(Box::new(XNeqY::new(queens[i].clone(), Addition::new(queens[j].clone(), -q2 + q1))));
415//       }
416//     }
417//     // 2 queens can't share the same column.
418//     constraints.alloc(Box::new(Distinct::new(queens)));
419//     assert_eq!(constraints.consistency(variables), expect);
420//   }
421// }
pcp/propagation/store.rs

pcp/propagation/
store.rs
