pcp/search/branching/
binary_split.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 search::branching::*;
17use search::branching::branch::*;
18use search::space::*;
19use term::*;
20use propagators::cmp::*;
21use concept::*;
22
23pub struct BinarySplit;
24
25impl<VStore, CStore, R, Domain, Bound> Distributor<Space<VStore, CStore, R>, Bound> for BinarySplit where
26  VStore: VStoreConcept<Item=Domain, Location=Identity<Domain>, Output=Domain> + 'static,
27  CStore: IntCStore<VStore>,
28  Domain: IntDomain<Item=Bound> + 'static,
29  Bound: IntBound + Copy + 'static,
30  R: FreezeSpace<VStore, CStore> + Snapshot<State=Space<VStore, CStore, R>>
31{
32  fn distribute(&mut self, space: Space<VStore, CStore, R>, var_idx: usize, val: Bound) ->
33    (<Space<VStore, CStore, R> as Freeze>::FrozenState, Vec<Branch<Space<VStore, CStore, R>>>)
34  {
35    // See notes in Enumerate::distribute.
36    Branch::distribute(space,
37      vec![
38        Box::new(move |space: &mut Space<VStore, CStore, R>| {
39          let x = Box::new(Identity::<Domain>::new(var_idx)) as Var<VStore>;
40          let v = Box::new(Constant::new(val)) as Var<VStore>;
41          let x_less_v = x_leq_y::<_,_,Bound>(x.bclone(), v.bclone());
42          space.cstore.alloc(Box::new(x_less_v));
43        }),
44        Box::new(move |space: &mut Space<VStore, CStore, R>| {
45          let x = Box::new(Identity::<Domain>::new(var_idx)) as Var<VStore>;
46          let v = Box::new(Constant::new(val)) as Var<VStore>;
47          let x_geq_v = x_greater_y(x, v);
48          space.cstore.alloc(Box::new(x_geq_v));
49        })
50      ]
51    )
52  }
53}
54
55#[cfg(test)]
56pub mod test {
57  use super::*;
58  use search::branching::Distributor;
59  use search::branching::MiddleVal;
60  use term::ops::*;
61  use trilean::SKleene::*;
62  use search::*;
63  use interval::interval_set::*;
64  use interval::ops::Range;
65  use gcollections::ops::*;
66
67  type Domain = IntervalSet<i32>;
68
69  pub fn test_distributor<D, Val>(mut distributor: D, mut val_selection: Val, distribution_index: usize,
70    root: Vec<(i32, i32)>, children: Vec<(i32, i32)>) where
71   Val: ValSelection<Domain>,
72   D: Distributor<FDSpace, i32>
73  {
74    let mut space = FDSpace::empty();
75
76    for (l,u) in root {
77      space.vstore.alloc(IntervalSet::new(l,u));
78    }
79
80    let x = Identity::<Domain>::new(distribution_index);
81    let d = x.read(&space.vstore);
82    let b = val_selection.select(d);
83
84    let (mut immutable_state, branches) = distributor.distribute(space, distribution_index, b);
85
86    assert_eq!(branches.len(), children.len());
87
88    for (branch, (l,u)) in branches.into_iter().zip(children.into_iter()) {
89      space = branch.commit(immutable_state);
90      assert_eq!(space.consistency(), True);
91      let split_dom = x.read(&space.vstore);
92      assert_eq!(split_dom, IntervalSet::new(l,u));
93      immutable_state = space.freeze();
94    }
95  }
96
97  #[test]
98  fn binary_split_distribution() {
99    let vars = vec![(1,10),(2,4),(1,2)];
100    test_distributor(BinarySplit, MiddleVal, 0,
101      vars.clone(),
102      vec![(1,5),(6,10)]
103    );
104    test_distributor(BinarySplit, MiddleVal, 1,
105      vars.clone(),
106      vec![(2,3),(4,4)]
107    );
108    test_distributor(BinarySplit, MiddleVal, 2,
109      vars.clone(),
110      vec![(1,1),(2,2)]
111    );
112  }
113
114  #[test]
115  #[should_panic]
116  fn binary_split_impossible_distribution() {
117    test_distributor(BinarySplit, MiddleVal, 0,
118      vec![(1,1)],
119      vec![]
120    );
121  }
122
123  #[test]
124  #[should_panic]
125  fn binary_split_impossible_distribution_2() {
126    test_distributor(BinarySplit, MiddleVal, 2,
127      vec![(1,5),(2,4),(4,4)],
128      vec![]
129    );
130  }
131}
pcp/search/branching/binary_split.rs

pcp/search/branching/
binary_split.rs
