TrinityCore
Containers.h
Go to the documentation of this file.
1/*
2 * This file is part of the TrinityCore Project. See AUTHORS file for Copyright information
3 *
4 * This program is free software; you can redistribute it and/or modify it
5 * under the terms of the GNU General Public License as published by the
6 * Free Software Foundation; either version 2 of the License, or (at your
7 * option) any later version.
8 *
9 * This program is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
12 * more details.
13 *
14 * You should have received a copy of the GNU General Public License along
15 * with this program. If not, see <http://www.gnu.org/licenses/>.
16 */
17
18#ifndef TRINITY_CONTAINERS_H
19#define TRINITY_CONTAINERS_H
20
21#include "Define.h"
22#include "MapUtils.h"
23#include "Random.h"
24#include <algorithm>
25#include <iterator>
26#include <span>
27#include <stdexcept>
28#include <type_traits>
29#include <utility>
30#include <vector>
31
32namespace Trinity
33{
34 template <class T>
36 {
37 public:
38 using iterator_category = std::output_iterator_tag;
39 using value_type = void;
40 using pointer = T*;
41 using reference = T&;
42 using difference_type = std::ptrdiff_t;
43
44 CheckedBufferOutputIterator(T* buf, size_t n) : _buf(buf), _end(buf+n) {}
45
46 T& operator*() const { check(); return *_buf; }
49
50 size_t remaining() const { return (_end - _buf); }
51
52 private:
53 T* _buf;
54 T* _end;
55 void check() const
56 {
57 if (!(_buf < _end))
58 throw std::out_of_range("index");
59 }
60 };
61
62 namespace Containers
63 {
64 // resizes <container> to have at most <requestedSize> elements
65 // if it has more than <requestedSize> elements, the elements to keep are selected randomly
66 template<class C>
67 void RandomResize(C& container, std::size_t requestedSize)
68 {
69 static_assert(std::is_base_of<std::forward_iterator_tag, typename std::iterator_traits<typename C::iterator>::iterator_category>::value, "Invalid container passed to Trinity::Containers::RandomResize");
70 if (std::size(container) <= requestedSize)
71 return;
72 auto keepIt = std::begin(container), curIt = std::begin(container);
73 uint32 elementsToKeep = requestedSize, elementsToProcess = std::size(container);
74 while (elementsToProcess)
75 {
76 // this element has chance (elementsToKeep / elementsToProcess) of being kept
77 if (urand(1, elementsToProcess) <= elementsToKeep)
78 {
79 if (keepIt != curIt)
80 *keepIt = std::move(*curIt);
81 ++keepIt;
82 --elementsToKeep;
83 }
84 ++curIt;
85 --elementsToProcess;
86 }
87 container.erase(keepIt, std::end(container));
88 }
89
90 template<class C, class Predicate>
91 void RandomResize(C& container, Predicate&& predicate, std::size_t requestedSize)
92 {
94 C containerCopy;
95 std::copy_if(std::begin(container), std::end(container), std::inserter(containerCopy, std::end(containerCopy)), predicate);
96
97 if (requestedSize)
98 RandomResize(containerCopy, requestedSize);
99
100 container = std::move(containerCopy);
101 }
102
103 /*
104 * Select a random element from a container.
105 *
106 * Note: container cannot be empty
107 */
108 template<class C>
109 inline auto SelectRandomContainerElement(C const& container) -> typename std::add_const<decltype(*std::begin(container))>::type&
110 {
111 auto it = std::begin(container);
112 std::advance(it, urand(0, uint32(std::size(container)) - 1));
113 return *it;
114 }
115
116 /*
117 * Select a random element from a container where each element has a different chance to be selected.
118 *
119 * @param container Container to select an element from
120 * @param weights Chances of each element to be selected, must be in the same order as elements in container.
121 * Caller is responsible for checking that sum of all weights is greater than 0.
122 *
123 * Note: container cannot be empty
124 */
125 template<class C>
126 inline auto SelectRandomWeightedContainerElement(C const& container, std::span<double> const& weights) -> decltype(std::begin(container))
127 {
128 auto it = std::begin(container);
129 std::advance(it, urandweighted(weights.size(), weights.data()));
130 return it;
131 }
132
133 /*
134 * Select a random element from a container where each element has a different chance to be selected.
135 *
136 * @param container Container to select an element from
137 * @param weightExtractor Function retrieving chance of each element in container, expected to take an element of the container and returning a double
138 *
139 * Note: container cannot be empty
140 */
141 template<class C, class Fn>
142 inline auto SelectRandomWeightedContainerElement(C const& container, Fn weightExtractor) -> decltype(std::begin(container))
143 {
144 std::size_t size = std::size(container);
145 std::size_t i = 0;
146 double* weights = new double[size];
147 double weightSum = 0.0;
148 for (auto const& val : container)
149 {
150 double weight = weightExtractor(val);
151 weights[i++] = weight;
152 weightSum += weight;
153 }
154
155 auto it = std::begin(container);
156 std::advance(it, weightSum > 0.0 ? urandweighted(size, weights) : urand(0, uint32(std::size(container)) - 1));
157 delete[] weights;
158 return it;
159 }
160
169 template<class Iterator>
170 inline void RandomShuffle(Iterator begin, Iterator end)
171 {
172 std::shuffle(begin, end, RandomEngine::Instance());
173 }
174
182 template<class C>
183 inline void RandomShuffle(C& container)
184 {
185 RandomShuffle(std::begin(container), std::end(container));
186 }
187
200 template<class Iterator1, class Iterator2>
201 inline bool Intersects(Iterator1 first1, Iterator1 last1, Iterator2 first2, Iterator2 last2)
202 {
203 while (first1 != last1 && first2 != last2)
204 {
205 if (*first1 < *first2)
206 ++first1;
207 else if (*first2 < *first1)
208 ++first2;
209 else
210 return true;
211 }
212
213 return false;
214 }
215
229 template<class Iterator1, class Iterator2, class Predicate>
230 inline bool Intersects(Iterator1 first1, Iterator1 last1, Iterator2 first2, Iterator2 last2, Predicate&& equalPred)
231 {
232 while (first1 != last1 && first2 != last2)
233 {
234 if (*first1 < *first2)
235 ++first1;
236 else if (*first2 < *first1)
237 ++first2;
238 else if (!equalPred(*first1, *first2))
239 ++first1, ++first2;
240 else
241 return true;
242 }
243
244 return false;
245 }
246
247 namespace Impl
248 {
249 template <typename Container, typename Predicate>
250 void EraseIfMoveAssignable(Container& c, Predicate p)
251 {
252 auto wpos = c.begin();
253 for (auto rpos = c.begin(), end = c.end(); rpos != end; ++rpos)
254 {
255 if (!p(*rpos))
256 {
257 if (rpos != wpos)
258 std::swap(*rpos, *wpos);
259 ++wpos;
260 }
261 }
262 c.erase(wpos, c.end());
263 }
264
265 template <typename Container, typename Predicate>
266 void EraseIfNotMoveAssignable(Container& c, Predicate p)
267 {
268 for (auto it = c.begin(); it != c.end();)
269 {
270 if (p(*it))
271 it = c.erase(it);
272 else
273 ++it;
274 }
275 }
276 }
277
278 template <typename Container, typename Predicate>
279 void EraseIf(Container& c, Predicate p)
280 {
281 if constexpr (std::is_move_assignable_v<decltype(*c.begin())>)
282 Impl::EraseIfMoveAssignable(c, std::ref(p));
283 else
284 Impl::EraseIfNotMoveAssignable(c, std::ref(p));
285 }
286
294 template<typename T>
295 inline decltype(auto) EnsureWritableVectorIndex(std::vector<T>& vec, typename std::vector<T>::size_type i)
296 {
297 if (i >= vec.size())
298 vec.resize(i + 1);
299
300 return vec[i];
301 }
302
309 template<typename T>
310 inline decltype(auto) EnsureWritableVectorIndex(std::vector<T>& vec, typename std::vector<T>::size_type i, T const& resizeDefault)
311 {
312 if (i >= vec.size())
313 vec.resize(i + 1, resizeDefault);
314
315 return vec[i];
316 }
317 }
319}
321
322#endif
uint32_t uint32
Definition: Define.h:143
uint32 urandweighted(size_t count, double const *chances)
Definition: Random.cpp:87
uint32 urand(uint32 min, uint32 max)
Definition: Random.cpp:42
static RandomEngine & Instance()
Definition: Random.cpp:93
CheckedBufferOutputIterator operator++(int)
Definition: Containers.h:48
CheckedBufferOutputIterator & operator++()
Definition: Containers.h:47
std::output_iterator_tag iterator_category
Definition: Containers.h:38
CheckedBufferOutputIterator(T *buf, size_t n)
Definition: Containers.h:44
void EraseIfMoveAssignable(Container &c, Predicate p)
Definition: Containers.h:250
void EraseIfNotMoveAssignable(Container &c, Predicate p)
Definition: Containers.h:266
decltype(auto) EnsureWritableVectorIndex(std::vector< T > &vec, typename std::vector< T >::size_type i)
Definition: Containers.h:295
void RandomShuffle(Iterator begin, Iterator end)
Reorder the elements of the iterator range randomly.
Definition: Containers.h:170
auto SelectRandomWeightedContainerElement(C const &container, std::span< double > const &weights) -> decltype(std::begin(container))
Definition: Containers.h:126
auto SelectRandomContainerElement(C const &container) -> typename std::add_const< decltype(*std::begin(container))>::type &
Definition: Containers.h:109
bool Intersects(Iterator1 first1, Iterator1 last1, Iterator2 first2, Iterator2 last2)
Definition: Containers.h:201
void EraseIf(Container &c, Predicate p)
Definition: Containers.h:279
void RandomResize(C &container, std::size_t requestedSize)
Definition: Containers.h:67
constexpr std::size_t size()
Definition: UpdateField.h:796