pcp/search/branching/
first_smallest_var.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 search::space::*;
16use search::branching::*;
17use variable::ops::Iterable;
18use gcollections::ops::*;
19use num::traits::Unsigned;
20use num::Integer;
21
22pub struct FirstSmallestVar;
23
24impl<VStore, CStore, R, Domain, Size> VarSelection<Space<VStore, CStore, R>> for FirstSmallestVar where
25  VStore: Iterable<Item=Domain>,
26  Domain: Cardinality<Size=Size>,
27  Size: Ord + Unsigned + Integer
28{
29  fn select(&mut self, space: &Space<VStore, CStore, R>) -> usize {
30    space.vstore.iter().enumerate()
31      .filter(|&(_, v)| v.size() > Size::one())
32      .min_by_key(|&(_, v)| v.size())
33      .expect("Cannot select a variable in a space where all variables are assigned.")
34      .0
35  }
36}
37
38#[cfg(test)]
39pub mod test {
40  use super::*;
41  use search::*;
42  use search::branching::VarSelection;
43  use interval::interval_set::*;
44  use interval::ops::*;
45
46  pub fn test_selector<S>(mut selector: S, vars: Vec<(i32, i32)>, expect: usize) where
47    S: VarSelection<FDSpace>
48  {
49    let mut space = FDSpace::empty();
50
51    for (l,u) in vars {
52      space.vstore.alloc(IntervalSet::new(l,u));
53    }
54
55    assert_eq!(selector.select(&space), expect);
56  }
57
58  #[test]
59  fn smallest_var_selection() {
60    test_selector(FirstSmallestVar, vec![(1,10),(2,4),(1,1)], 1);
61    test_selector(FirstSmallestVar, vec![(1,10),(2,4),(2,4)], 1);
62    test_selector(FirstSmallestVar,
63      vec![(1,1),(1,1),(1,10),(1,1),(2,4),(1,1),(1,1)], 4);
64  }
65
66  #[should_panic]
67  #[test]
68  fn smallest_var_selection_all_assigned() {
69    test_selector(FirstSmallestVar, vec![(0, 0),(2,2),(1,1)], 0);
70  }
71}
pcp/search/branching/first_smallest_var.rs

pcp/search/branching/
first_smallest_var.rs
