pcp/search/
stop_node.rs

1// Copyright 2017 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::space::*;
17use search::search_tree_visitor::*;
18use concept::*;
19
20pub struct StopNode<C> {
21  child: C,
22  limit: usize,
23  nodes_explored: usize
24}
25
26impl<C> StopNode<C> {
27  pub fn new(limit: usize, child: C) -> StopNode<C> {
28    StopNode {
29      child: child,
30      limit: limit,
31      nodes_explored: 0
32    }
33  }
34}
35
36impl<VStore, CStore, R, C> SearchTreeVisitor<Space<VStore, CStore, R>> for StopNode<C> where
37  VStore: VStoreConcept,
38  CStore: IntCStore<VStore>,
39  C: SearchTreeVisitor<Space<VStore, CStore, R>>,
40  R: FreezeSpace<VStore, CStore> + Snapshot<State=Space<VStore, CStore, R>>
41{
42  fn start(&mut self, root: &Space<VStore, CStore, R>) {
43    self.child.start(root);
44  }
45
46  fn enter(&mut self, current: Space<VStore, CStore, R>)
47    -> (<Space<VStore, CStore, R> as Freeze>::FrozenState, Status<Space<VStore, CStore, R>>)
48  {
49    let (space, status) = self.child.enter(current);
50    self.nodes_explored += 1;
51    // If we reached the limit, we stop the search by changing the status.
52    if self.nodes_explored >= self.limit {
53      (space, Status::EndOfSearch)
54    }
55    else {
56      (space, status)
57    }
58  }
59}
60
61#[cfg(test)]
62mod test {
63  use super::*;
64  use search::test::*;
65  use search::FDSpace;
66  use search::monitor::*;
67  use search::statistics::*;
68  use search::engine::one_solution::*;
69  use search::engine::all_solution::*;
70  use search::propagation::*;
71  use search::branching::binary_split::*;
72  use search::branching::brancher::*;
73  use search::branching::first_smallest_var::*;
74  use search::branching::middle_val::*;
75  use gcollections::VectorStack;
76  use gcollections::ops::*;
77
78  #[test]
79  fn test_stop() {
80    let n = 6;
81    let mut space = FDSpace::empty();
82    nqueens(n, &mut space);
83
84    let nodes_limit = 10;
85    let mut statistics = Statistics::new();
86    {
87      let mut search: AllSolution<OneSolution<_, VectorStack<_>, FDSpace>>
88      =
89        AllSolution::new(OneSolution::new(
90          Monitor::new(&mut statistics, StopNode::new(nodes_limit,
91            Propagation::new(Brancher::new(FirstSmallestVar, MiddleVal, BinarySplit))))));
92      search.start(&space);
93      let (_, status) = search.enter(space);
94      assert_eq!(status, Status::EndOfSearch);
95    }
96    assert_eq!(statistics.num_nodes, nodes_limit);
97  }
98}
pcp/search/stop_node.rs

pcp/search/
stop_node.rs
