pcp/search/engine/
all_solution.rs

1// Copyright 2016 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/// The `AllSolution` combinator continuously calls its child until it returns `EndOfSearch`. You should use it with the `OneSolution` combinator.
16
17use kernel::*;
18use search::search_tree_visitor::*;
19use search::search_tree_visitor::Status::*;
20
21pub struct AllSolution<C> {
22  pub child: C
23}
24
25impl<C> AllSolution<C>
26{
27  pub fn new(child: C) -> Self
28  {
29    AllSolution {
30      child: child
31    }
32  }
33}
34
35impl<C, Space> SearchTreeVisitor<Space> for AllSolution<C> where
36 Space: Freeze,
37 C: SearchTreeVisitor<Space>
38{
39  fn start(&mut self, root: &Space) {
40    self.child.start(root);
41  }
42
43  fn enter(&mut self, root: Space) -> (Space::FrozenState, Status<Space>) {
44    let (mut immutable_state, mut status) = self.child.enter(root);
45    while status != EndOfSearch {
46      let state = immutable_state.unfreeze();
47      let frozen_state = self.child.enter(state);
48      immutable_state = frozen_state.0;
49      status = frozen_state.1;
50    }
51    (immutable_state, status)
52  }
53}
54
55#[cfg(test)]
56mod test {
57  use super::*;
58  use search::test::*;
59  use search::FDSpace;
60  use search::monitor::*;
61  use search::statistics::*;
62  use search::engine::one_solution::*;
63  use search::propagation::*;
64  use search::branching::binary_split::*;
65  use search::branching::brancher::*;
66  use search::branching::first_smallest_var::*;
67  use search::branching::middle_val::*;
68  use gcollections::VectorStack;
69  use gcollections::ops::*;
70
71  #[test]
72  fn example_nqueens() {
73    // Data from Wikipedia.
74    let nqueens_solution = vec![
75      1, 0, 0, 2, 10, 4, 40, 92, 352
76    ];
77
78    for (n, sol) in nqueens_solution.into_iter().enumerate() {
79      test_nqueens(n+1, sol, EndOfSearch);
80    }
81  }
82
83  fn test_nqueens(n: usize, sol_expected: usize, expect: Status<FDSpace>) {
84    let mut space = FDSpace::empty();
85    nqueens(n, &mut space);
86
87    let mut statistics = Statistics::new();
88    {
89      let mut search: AllSolution<Monitor<Statistics,
90        OneSolution<_, VectorStack<_>, FDSpace>>>
91      =
92        AllSolution::new(Monitor::new(&mut statistics,
93          OneSolution::new(Propagation::new(Brancher::new(FirstSmallestVar, MiddleVal, BinarySplit)))));
94      search.start(&space);
95      let (_, status) = search.enter(space);
96      assert_eq!(status, expect);
97    }
98    assert_eq!(statistics.num_solution, sol_expected);
99  }
100}
pcp/search/engine/all_solution.rs

pcp/search/engine/
all_solution.rs
