All Classes Namespaces Files Functions Variables Typedefs Enumerations Friends Macros Pages
subset_backtrack.hpp
Go to the documentation of this file.
1 
8 #ifndef PAAL_SUBSET_BACKTRACK_HPP
9 #define PAAL_SUBSET_BACKTRACK_HPP
10 
12 #include "paal/utils/concepts.hpp"
14 
15 #include <boost/range/algorithm/copy.hpp>
16 #include <boost/range/join.hpp>
17 
18 #include <vector>
19 
20 namespace paal {
21 namespace detail {
22 
23 template <typename Element> struct tail {
24  tail() = default;
25  tail(const tail &that) = delete;
26  tail(tail &&other) = default;
27  std::vector<Element> m_elems;
28  typename std::vector<Element>::const_iterator m_cur_pos;
29 };
30 
31 }
32 
36 template <typename Element> class subset_backtrack {
37  BOOST_CONCEPT_ASSERT((boost::CopyConstructibleConcept<Element>));
38  BOOST_CONCEPT_ASSERT((boost::DefaultConstructible<Element>));
39  const std::size_t INITIAL_TAILS_SIZE = 1;
41  bool m_start_solving =false;
42  public:
44  template <class Elements>
45  subset_backtrack(const Elements &elements)
46  : m_tails() {
47  BOOST_CONCEPT_ASSERT((utils::concepts::readable_range<Elements>));
48  push(elements);
49  }
50 
55  boost::iterator_range<typename std::vector<Element>::const_iterator>
56  get_moves() const {
57  auto const moves_begin = current_tail().m_cur_pos + m_start_solving,
58  moves_end = current_tail().m_elems.cend();
59  return boost::make_iterator_range(moves_begin, moves_end);
60  };
61 
71  template <typename TryPush, typename OnPop,
72  typename UpdateMoves = std::mem_fun_ref_t<
73  typename std::vector<Element>::iterator, std::vector<int>>>
74  void
75  solve(TryPush try_push, OnPop on_pop,
76  UpdateMoves update_moves = UpdateMoves(&std::vector<Element>::end)) {
77  m_start_solving=true;
78  assert(m_tails.size() == INITIAL_TAILS_SIZE);
79  if (current_tail().m_elems.empty()) return;
80  auto go_down = [&]() {
81  while (try_push(current_element())) {
82  auto &moves = get_new_tail();
83  moves.erase(update_moves(moves), moves.end());
84  if (moves.empty()) {
85  m_tails.pop();
86  on_pop(current_element());
87  break;
88  }
89  };
90  };
91  go_down();
92  while (true) {
93  while (try_increase_back()) go_down();
94  if (m_tails.size() == INITIAL_TAILS_SIZE) break;
95  m_tails.pop();
96  on_pop(current_element());
97  }
98  current_tail().m_cur_pos = current_tail().m_elems.begin();
99  m_start_solving=false;
100  }
101 
102  private:
103  std::vector<Element> &get_new_tail() {
104  push(get_moves());
105  return current_tail().m_elems;
106  }
107 
108  detail::tail<Element> &current_tail() { return m_tails.top(); }
109 
110  const detail::tail<Element> &current_tail() const { return m_tails.top(); }
111 
112  Element current_element() const { return *current_tail().m_cur_pos; }
113 
114  bool try_increase_back() {
115  return ++current_tail().m_cur_pos != current_tail().m_elems.end();
116  }
117 
118  template <typename Elements> void push(Elements &&elements) {
119  m_tails.push();
120  auto &new_tail = m_tails.top();
121  auto &moves = new_tail.m_elems;
122  moves.resize(boost::distance(elements));
123  boost::copy(elements, moves.begin());
124  new_tail.m_cur_pos = moves.begin();
125  };
126 };
127 
128 
130 template <class Elements>
131 auto make_subset_backtrack(const Elements &elements) {
133  elements);
134 }
135 
136 }
137 
138 #endif /* PAAL_SUBSET_BACKTRACK_HPP */
stack that doesn&#39;t call destructor on pop
std::size_t size() const
size
Definition: stack.hpp:36
Concept class for readable range concept.
Definition: concepts.hpp:79
const T & top() const
top
Definition: stack.hpp:30
boost::iterator_range< typename std::vector< Element >::const_iterator > get_moves() const
return range of all Elements that we will be trying to add to the current set
auto make_subset_backtrack(const Elements &elements)
make subset_backtrack
subset_backtrack(const Elements &elements)
constructor
void solve(TryPush try_push, OnPop on_pop, UpdateMoves update_moves=UpdateMoves(&std::vector< Element >::end))
void pop()
pop doesn&#39;t call destructor
Definition: stack.hpp:28