pcp/search/engine/
one_solution.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/// OneSolution combinator is a generator over the solution. It returns from `enter` each time it found a solution (with `Satisfiable`) or when no more node can be explored (with `EndOfSearch`). Its method `enter` can be safely call several time to generate more than one solution.
16
17use kernel::*;
18use search::search_tree_visitor::*;
19use search::search_tree_visitor::Status::*;
20use search::branching::branch::*;
21use gcollections::ops::multiset::*;
22use gcollections::*;
23use std::marker::PhantomData;
24
25pub struct OneSolution<C, Q, Space> {
26  pub child: C,
27  queue: Q,
28  started_exploration: bool,
29  phantom_space: PhantomData<Space>
30}
31
32impl<C, Q, Space> OneSolution<C, Q, Space> where
33 Space: Freeze,
34 C: SearchTreeVisitor<Space>,
35 Q: Multiset + Collection<Item=Branch<Space>>
36{
37  pub fn new(child: C) -> OneSolution<C, Q, Space>
38  {
39    OneSolution {
40      queue: Q::empty(),
41      child: child,
42      started_exploration: false,
43      phantom_space: PhantomData
44    }
45  }
46
47  fn push_branches(&mut self, branches: Vec<Branch<Space>>)
48  {
49    // For traversing the tree from left to right.
50    for branch in branches.into_iter().rev() {
51      self.queue.insert(branch);
52    }
53  }
54
55  fn enter_child(&mut self, current: Space, status: &mut Status<Space>) -> Space::FrozenState
56  {
57    let (immutable_state, child_status) = self.child.enter(current);
58    match child_status {
59      Unknown(ref branches) if branches.is_empty() => *status = Status::pruned(),
60      Unknown(branches) => self.push_branches(branches),
61      Satisfiable => *status = Satisfiable,
62      EndOfSearch => *status = EndOfSearch,
63      _ => ()
64    }
65    immutable_state
66  }
67
68  fn fully_explored(&self) -> bool {
69    self.queue.is_empty() && self.started_exploration
70  }
71
72  // Only visit the root if we didn't visit it before (based on the queue emptiness).
73  fn enter_root(&mut self, root: Space, status: &mut Status<Space>) -> Space::FrozenState
74  {
75    if self.queue.is_empty() && !self.started_exploration {
76      self.started_exploration = true;
77      self.enter_child(root, status)
78    } else {
79      root.freeze()
80    }
81  }
82}
83
84impl<C, Q, Space> SearchTreeVisitor<Space> for OneSolution<C, Q, Space> where
85 Space: Freeze,
86 C: SearchTreeVisitor<Space>,
87 Q: Multiset + Collection<Item=Branch<Space>>
88{
89  fn start(&mut self, root: &Space) {
90    self.queue = Q::empty();
91    self.started_exploration = false;
92    self.child.start(root);
93  }
94
95  fn enter(&mut self, root: Space) -> (Space::FrozenState, Status<Space>) {
96    if self.fully_explored() {
97      return (root.freeze(), EndOfSearch);
98    }
99
100    let mut status = Unsatisfiable;
101    let mut immutable_state = self.enter_root(root, &mut status);
102    while status != EndOfSearch && status != Satisfiable && !self.queue.is_empty() {
103      let branch = self.queue.extract().unwrap();
104      let child = branch.commit(immutable_state);
105      immutable_state = self.enter_child(child, &mut status);
106    }
107    (immutable_state, status)
108  }
109}
110
111#[cfg(test)]
112mod test {
113  use super::*;
114  use search::test::*;
115  use search::propagation::*;
116  use search::branching::binary_split::*;
117  use search::branching::brancher::*;
118  use search::branching::first_smallest_var::*;
119  use search::branching::middle_val::*;
120  use gcollections::VectorStack;
121  use gcollections::ops::*;
122
123  #[test]
124  fn example_nqueens() {
125    test_nqueens(1, Satisfiable);
126    test_nqueens(2, Unsatisfiable);
127    test_nqueens(3, Unsatisfiable);
128    for i in 4..12 {
129      test_nqueens(i, Satisfiable);
130    }
131  }
132
133  fn test_nqueens(n: usize, expect: Status<FDSpace>) {
134    let mut space = FDSpace::empty();
135    nqueens(n, &mut space);
136
137    let mut search: OneSolution<_, VectorStack<_>, FDSpace> =
138      OneSolution::new(Propagation::new(Brancher::new(FirstSmallestVar, MiddleVal, BinarySplit)));
139    search.start(&space);
140    let (_, status) = search.enter(space);
141    assert_eq!(status, expect);
142  }
143}
pcp/search/engine/one_solution.rs

pcp/search/engine/
one_solution.rs
