The Battle for Wesnoth  1.15.1+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 /** @file */
15 
16 #pragma once
17 
18 #include "map/location.hpp"
19 #include <set>
20 
21 /**
22  * Function that will add to @a result all elements of @a locs, plus all
23  * on-board (that is: all locs that match @pred1) locations matching @a pred2
24  * that are connected to elements of
25  * locs by a chain of at most @a radius tiles, each of which matches @a pred2.
26  * @a result must be a std::set of locations.
27  *
28  * @a pred1 a fast predicate (used before cachecheck).
29  * @a pred2 a slow predicate (used after cachecheck).
30  */
31 template<typename FPred1, typename FPred2>
32 void get_tiles_radius(std::set<map_location>&& locs, size_t radius, std::set<map_location>& result, const FPred1& pred1, const FPred2& pred2)
33 {
34  typedef std::set<map_location> location_set;
35  location_set must_visit, filtered_out;
36  location_set not_visited = std::move(locs);
37 
38  for ( ; radius != 0 && !not_visited.empty(); --radius )
39  {
40  location_set::const_iterator it = not_visited.begin();
41  location_set::const_iterator it_end = not_visited.end();
42 
43  result.insert(it, it_end);
44  for(; it != it_end; ++it) {
46  get_adjacent_tiles(*it, adj.data());
47  for(size_t i = 0; i < adj.size(); ++i) {
48  const map_location& loc = adj[i];
49  if( pred1(loc) ) {
50  if( !result.count(loc) && !filtered_out.count(loc) ) {
51  if( pred2(loc) ) {
52  must_visit.insert(loc);
53  }
54  else {
55  filtered_out.insert(loc);
56  }
57  }
58  }
59  }
60  }
61 
62  not_visited.swap(must_visit);
63  must_visit.clear();
64  }
65 
66  result.insert(not_visited.begin(), not_visited.end());
67 }
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:517
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...
std::array< map_location, 6 > adjacent_loc_array_t
Definition: location.hpp:170
Encapsulates the map of the game.
Definition: location.hpp:42
std::size_t i
Definition: function.cpp:933
std::set< map_location > location_set