The Battle for Wesnoth  1.15.12+dev
pathutils_impl.hpp
Go to the documentation of this file.
1 /*
2  Copyright (C) 2018 the Battle for Wesnoth Project https://www.wesnoth.org/
3 
4  This program is free software; you can redistribute it and/or modify
5  it under the terms of the GNU General Public License as published by
6  the Free Software Foundation; either version 2 of the License, or
7  (at your option) any later version.
8  This program is distributed in the hope that it will be useful,
9  but WITHOUT ANY WARRANTY.
10 
11  See the COPYING file for more details.
12 */
13 
14 #pragma once
15 
16 #include "map/location.hpp"
17 #include <set>
18 
19 /**
20  * Function that will add to @a result all elements of @a locs, plus all
21  * on-board (that is: all locs that match @a pred1) locations matching @a pred2
22  * that are connected to elements of
23  * locs by a chain of at most @a radius tiles, each of which matches @a pred2.
24  * @a result must be a std::set of locations.
25  *
26  * @a pred1 a fast predicate (used before cachecheck).
27  * @a pred2 a slow predicate (used after cachecheck).
28  */
29 template<typename FPred1, typename FPred2>
30 void get_tiles_radius(std::set<map_location>&& locs, size_t radius, std::set<map_location>& result, const FPred1& pred1, const FPred2& pred2)
31 {
32  typedef std::set<map_location> location_set;
33  location_set must_visit, filtered_out;
34  location_set not_visited = std::move(locs);
35 
36  for ( ; radius != 0 && !not_visited.empty(); --radius )
37  {
38  location_set::const_iterator it = not_visited.begin();
39  location_set::const_iterator it_end = not_visited.end();
40 
41  result.insert(it, it_end);
42  for(; it != it_end; ++it) {
43  for(const map_location& loc : get_adjacent_tiles(*it)) {
44  if( pred1(loc) ) {
45  if( !result.count(loc) && !filtered_out.count(loc) ) {
46  if( pred2(loc) ) {
47  must_visit.insert(loc);
48  }
49  else {
50  filtered_out.insert(loc);
51  }
52  }
53  }
54  }
55  }
56 
57  not_visited.swap(must_visit);
58  must_visit.clear();
59  }
60 
61  result.insert(not_visited.begin(), not_visited.end());
62 }
void get_adjacent_tiles(const map_location &a, map_location *res)
Function which, given a location, will place all adjacent locations in res.
Definition: location.cpp:474
void get_tiles_radius(std::set< map_location > &&locs, size_t radius, std::set< map_location > &result, const FPred1 &pred1, const FPred2 &pred2)
Function that will add to result all elements of locs, plus all on-board (that is: all locs that matc...
Encapsulates the map of the game.
Definition: location.hpp:37
std::set< map_location > location_set