Vcsn  2.4
Be Rational
algorithm.hh
Go to the documentation of this file.
1 #pragma once
2 
3 #include <algorithm>
4 #include <iterator> // next
5 #include <vector>
6 
7 #include <boost/range/algorithm/set_algorithm.hpp>
8 #include <boost/range/iterator_range_core.hpp>
9 
10 namespace vcsn
11 {
12  namespace detail
13  {
14  // Not in Boost 1.49.
15  template <typename Range, typename Predicate>
16  bool any_of(const Range &r, Predicate p)
17  {
18  using std::begin;
19  using std::end;
20  return std::any_of(begin(r), end(r), p);
21  }
22 
23  template <typename Range>
24  bool any_of(const Range &r)
25  {
26  using std::begin;
27  using std::end;
28  return std::any_of(begin(r), end(r),
29  [](const auto& p) -> bool { return p; });
30  }
31 
35  template <typename Container>
36  typename Container::value_type
37  back(const Container& container)
38  {
39  using std::begin;
40  using std::end;
41  auto i = begin(container);
42  auto iend = end(container);
43  assert(i != iend);
44  auto res = *i;
45  for (++i; i != iend; ++i)
46  res = *i;
47  return res;
48  }
49 
50  template <typename Container, typename Predicate>
51  void erase_if(Container& c, const Predicate& p)
52  {
53  using std::begin;
54  using std::end;
55  for (auto i = begin(c); i != end(c); /* nothing. */)
56  {
57  if (p(*i))
58  i = c.erase(i);
59  else
60  ++i;
61  }
62  }
63 
64 
66  template <typename Container>
67  typename Container::value_type
68  front(const Container& container)
69  {
70  using std::begin;
71  using std::end;
72  auto i = begin(container);
73  assert(i != end(container));
74  return *i;
75  }
76 
78  template <typename Iterator, typename Pred, typename Less>
79  boost::iterator_range<Iterator>
80  initial_sorted_range(Iterator begin, Iterator end,
81  Pred pred, Less less)
82  {
83  if (pred(*begin))
84  for (auto i = begin;; ++i)
85  {
86  auto next = std::next(i);
87  if (next == end
88  || !pred(*next)
89  || less(*next, *i))
90  return {begin, next};
91  }
92  else
93  return {end, end};
94  }
95 
100  template <typename Container, typename Compare>
101  bool is_sorted_forward(const Container& container, Compare comp)
102  {
103  auto i = std::begin(container);
104  auto end = std::end(container);
105  if (i != end)
106  {
107  auto prev = *i;
108  for (++i; i != end; ++i)
109  if (comp(prev, *i))
110  prev = *i;
111  else
112  return false;
113  }
114  return true;
115  }
116 
119  template <typename Container>
120  typename Container::value_type
121  max_forward(const Container& container)
122  {
123  auto i = std::begin(container);
124  auto end = std::end(container);
125  assert(i != end);
126  if (i != end)
127  {
128  auto res = *i;
129  for (++i; i != end; ++i)
130  if (res < *i)
131  res = *i;
132  return res;
133  }
134  abort();
135  }
136 
137  // Boost 1.49 does not have boost/algorithm/cxx11/none_of.hpp and the like.
138  template <typename Range, typename Predicate>
139  bool none_of(const Range &r, Predicate p)
140  {
141  using std::begin;
142  using std::end;
143  return std::none_of(begin(r), end(r), p);
144  }
145 
146  // Not in Boost 1.49.
147  template <typename Range, typename Value>
148  bool none_of_equal(const Range &r, const Value& value)
149  {
150  return none_of(r, [&value](const Value& v) { return v == value; });
151  }
152 
153 
156  template <typename Container, typename Fun>
157  auto transform(const Container& c, Fun&& fun)
158  {
159  using value_t = decltype(std::forward<Fun>(fun)(*begin(c)));
160  auto res = std::vector<value_t>(c.size());
161  std::transform(begin(c), end(c), begin(res), std::forward<Fun>(fun));
162  return res;
163  }
164  }
165 
167  template <typename Container,
168  // SFINAE.
169  typename = typename Container::value_type>
170  Container
171  set_difference(const Container& s1, const Container& s2)
172  {
173  auto res = Container{s1.key_comp(), s1.get_allocator()};
174  auto i = std::insert_iterator<Container>{res, res.begin()};
175  boost::set_difference(s1, s2, i, s1.key_comp());
176  return res;
177  }
178 
180  template <typename Container,
181  // SFINAE.
182  typename = typename Container::value_type>
183  Container
184  set_intersection(const Container& s1, const Container& s2)
185  {
186  auto res = Container{s1.key_comp(), s1.get_allocator()};
187  auto i = std::insert_iterator<Container>{res, res.begin()};
188  boost::set_intersection(s1, s2, i, s1.key_comp());
189  return res;
190  }
191 
193  template <typename Container>
194  bool
195  same_domain(const Container& x, const Container& y)
196  {
197  if (x.size() == y.size())
198  {
199  using std::begin; using std::end;
200  for (auto xi = begin(x), xend = end(x), yi = begin(y);
201  xi != xend;
202  ++xi, ++yi)
203  if (x.key_comp()(xi->first, yi->first)
204  || x.key_comp()(yi->first, xi->first))
205  return false;
206  return true;
207  }
208  else
209  return false;
210  }
211 
213  template <typename Container,
214  // SFINAE.
215  typename = typename Container::value_type>
216  Container
217  set_union(const Container& s1, const Container& s2)
218  {
219  auto res = Container{s1.key_comp(), s1.get_allocator()};
220  auto i = std::insert_iterator<Container>{res, res.begin()};
221  boost::set_union(s1, s2, i, s1.key_comp());
222  return res;
223  }
224 }
Container::value_type front(const Container &container)
The first member of this Container.
Definition: algorithm.hh:68
void erase_if(Container &c, const Predicate &p)
Definition: algorithm.hh:51
return res
Definition: multiply.hh:398
bool any_of(const Range &r, Predicate p)
Definition: algorithm.hh:16
Functor to compare Values of ValueSets.
Definition: functional.hh:76
Container set_intersection(const Container &s1, const Container &s2)
The intersection of two sets.
Definition: algorithm.hh:184
bool any_of(const Range &r)
Definition: algorithm.hh:24
Container set_union(const Container &s1, const Container &s2)
The union of two sets.
Definition: algorithm.hh:217
Provide a variadic mul on top of a binary mul(), and one().
Definition: fwd.hh:46
Container set_difference(const Container &s1, const Container &s2)
The set of members of s1 that are not members of s2.
Definition: algorithm.hh:171
Definition: a-star.hh:8
auto transform(const Container &c, Fun &&fun)
Map a unary function on a container of values, and return the vector the results. ...
Definition: algorithm.hh:157
boost::iterator_range< Iterator > initial_sorted_range(Iterator begin, Iterator end, Pred pred, Less less)
The longest initial range of elements matching the predicate.
Definition: algorithm.hh:80
bool none_of(const Range &r, Predicate p)
Definition: algorithm.hh:139
bool same_domain(const Container &x, const Container &y)
Check that two associative containers have the same keys.
Definition: algorithm.hh:195
bool is_sorted_forward(const Container &container, Compare comp)
Same as std::is_sorted, but works with an input iterator, not just a forward iterator.
Definition: algorithm.hh:101
Container::value_type back(const Container &container)
The last member of this Container.
Definition: algorithm.hh:37
bool none_of_equal(const Range &r, const Value &value)
Definition: algorithm.hh:148
Container::value_type max_forward(const Container &container)
Same as *std::max_element, but works with an input iterator, not just a forward iterator.
Definition: algorithm.hh:121