From ae20b2ab561bc07d85f443ae914bc597c9d6ac6e Mon Sep 17 00:00:00 2001 From: Shauren Date: Thu, 24 Dec 2015 19:48:39 +0100 Subject: Core/Utils: Moved rng functions to separate header and added utility functions to select a random element from a container where each element can have different chance of being selected --- src/common/Utilities/Containers.h | 152 ++++++++++++++++++++++++++++++++++++++ src/common/Utilities/Random.cpp | 83 +++++++++++++++++++++ src/common/Utilities/Random.h | 72 ++++++++++++++++++ src/common/Utilities/Util.cpp | 57 -------------- src/common/Utilities/Util.h | 34 +-------- src/server/shared/Containers.h | 113 ---------------------------- 6 files changed, 308 insertions(+), 203 deletions(-) create mode 100644 src/common/Utilities/Containers.h create mode 100644 src/common/Utilities/Random.cpp create mode 100644 src/common/Utilities/Random.h delete mode 100644 src/server/shared/Containers.h (limited to 'src') diff --git a/src/common/Utilities/Containers.h b/src/common/Utilities/Containers.h new file mode 100644 index 00000000000..df97e342932 --- /dev/null +++ b/src/common/Utilities/Containers.h @@ -0,0 +1,152 @@ +/* + * Copyright (C) 2008-2015 TrinityCore + * + * This program is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License as published by the + * Free Software Foundation; either version 2 of the License, or (at your + * option) any later version. + * + * This program is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for + * more details. + * + * You should have received a copy of the GNU General Public License along + * with this program. If not, see . + */ + +#ifndef TRINITY_CONTAINERS_H +#define TRINITY_CONTAINERS_H + +#include "Define.h" +#include "Random.h" +#include +#include +#include + +namespace Trinity +{ + namespace Containers + { + template + void RandomResizeList(std::list &list, uint32 size) + { + uint32 list_size = uint32(list.size()); + + while (list_size > size) + { + typename std::list::iterator itr = list.begin(); + std::advance(itr, urand(0, list_size - 1)); + list.erase(itr); + --list_size; + } + } + + template + void RandomResizeList(std::list &list, Predicate& predicate, uint32 size) + { + //! First use predicate filter + std::list listCopy; + for (typename std::list::iterator itr = list.begin(); itr != list.end(); ++itr) + if (predicate(*itr)) + listCopy.push_back(*itr); + + if (size) + RandomResizeList(listCopy, size); + + list = listCopy; + } + + /* + * Select a random element from a container. + * + * Note: container cannot be empty + */ + template + typename C::value_type const& SelectRandomContainerElement(C const& container) + { + typename C::const_iterator it = container.begin(); + std::advance(it, urand(0, uint32(container.size()) - 1)); + return *it; + } + + /* + * Select a random element from a container where each element has a different chance to be selected. + * + * @param container Container to select an element from + * @param weightExtractor Function retrieving chance of each element in container + * + * Note: container cannot be empty + */ + template + typename C::const_iterator SelectRandomWeightedContainerElement(C const& container, std::function weightExtractor) + { + std::vector weights; + weights.reserve(container.size()); + std::transform(container.begin(), container.end(), std::back_inserter(weights), weightExtractor); + return SelectRandomWeightedContainerElement(container, weights); + } + + /* + * Select a random element from a container where each element has a different chance to be selected. + * + * @param container Container to select an element from + * @param weights Chances of each element to be selected, must be in the same order as elements in container + * + * Note: container cannot be empty + */ + template + typename C::const_iterator SelectRandomWeightedContainerElement(C const& container, std::vector weights) + { + std::discrete_distribution dd(weights.begin(), weights.end()); + typename C::const_iterator it = container.begin(); + std::advance(it, dd(SFMTEngine::Instance())); + return it; + } + + /** + * @fn bool Trinity::Containers::Intersects(Iterator first1, Iterator last1, Iterator first2, Iterator last2) + * + * @brief Checks if two SORTED containers have a common element + * + * @param first1 Iterator pointing to start of the first container + * @param last1 Iterator pointing to end of the first container + * @param first2 Iterator pointing to start of the second container + * @param last2 Iterator pointing to end of the second container + * + * @return true if containers have a common element, false otherwise. + */ + template + bool Intersects(Iterator1 first1, Iterator1 last1, Iterator2 first2, Iterator2 last2) + { + while (first1 != last1 && first2 != last2) + { + if (*first1 < *first2) + ++first1; + else if (*first2 < *first1) + ++first2; + else + return true; + } + + return false; + } + + template class M, class... Rest> + void MultimapErasePair(M& multimap, K const& key, V const& value) + { + auto range = multimap.equal_range(key); + for (auto itr = range.first; itr != range.second;) + { + if (itr->second == value) + itr = multimap.erase(itr); + else + ++itr; + } + } + } + //! namespace Containers +} +//! namespace Trinity + +#endif //! #ifdef TRINITY_CONTAINERS_H diff --git a/src/common/Utilities/Random.cpp b/src/common/Utilities/Random.cpp new file mode 100644 index 00000000000..cc013110b01 --- /dev/null +++ b/src/common/Utilities/Random.cpp @@ -0,0 +1,83 @@ +/* + * Copyright (C) 2008-2015 TrinityCore + * + * This program is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License as published by the + * Free Software Foundation; either version 2 of the License, or (at your + * option) any later version. + * + * This program is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for + * more details. + * + * You should have received a copy of the GNU General Public License along + * with this program. If not, see . + */ + +#include "Random.h" +#include "Common.h" +#include "Errors.h" +#include "SFMT.h" +#include + +static boost::thread_specific_ptr sfmtRand; + +static SFMTRand* GetRng() +{ + SFMTRand* rand = sfmtRand.get(); + + if (!rand) + { + rand = new SFMTRand(); + sfmtRand.reset(rand); + } + + return rand; +} + +int32 irand(int32 min, int32 max) +{ + ASSERT(max >= min); + return int32(GetRng()->IRandom(min, max)); +} + +uint32 urand(uint32 min, uint32 max) +{ + ASSERT(max >= min); + return GetRng()->URandom(min, max); +} + +uint32 urandms(uint32 min, uint32 max) +{ + ASSERT(max >= min); + ASSERT(INT_MAX / IN_MILLISECONDS >= max); + return GetRng()->URandom(min * IN_MILLISECONDS, max * IN_MILLISECONDS); +} + +float frand(float min, float max) +{ + ASSERT(max >= min); + return float(GetRng()->Random() * (max - min) + min); +} + +uint32 rand32() +{ + return GetRng()->BRandom(); +} + +double rand_norm() +{ + return GetRng()->Random(); +} + +double rand_chance() +{ + return GetRng()->Random() * 100.0; +} + +SFMTEngine& SFMTEngine::Instance() +{ + static SFMTEngine engine; + return engine; +} diff --git a/src/common/Utilities/Random.h b/src/common/Utilities/Random.h new file mode 100644 index 00000000000..c919c28bcc8 --- /dev/null +++ b/src/common/Utilities/Random.h @@ -0,0 +1,72 @@ +/* + * Copyright (C) 2008-2015 TrinityCore + * + * This program is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License as published by the + * Free Software Foundation; either version 2 of the License, or (at your + * option) any later version. + * + * This program is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for + * more details. + * + * You should have received a copy of the GNU General Public License along + * with this program. If not, see . + */ + +#ifndef Random_h__ +#define Random_h__ + +#include "Define.h" +#include + +/* Return a random number in the range min..max. */ +int32 irand(int32 min, int32 max); + +/* Return a random number in the range min..max (inclusive). */ +uint32 urand(uint32 min, uint32 max); + +/* Return a random millisecond value between min and max seconds. Functionally equivalent to urand(min*IN_MILLISECONDS, max*IN_MILLISECONDS). */ +uint32 urandms(uint32 min, uint32 max); + +/* Return a random number in the range 0 .. UINT32_MAX. */ +uint32 rand32(); + +/* Return a random number in the range min..max */ +float frand(float min, float max); + +/* Return a random double from 0.0 to 1.0 (exclusive). */ +double rand_norm(); + +/* Return a random double from 0.0 to 100.0 (exclusive). */ +double rand_chance(); + +/* Return true if a random roll fits in the specified chance (range 0-100). */ +inline bool roll_chance_f(float chance) +{ + return chance > rand_chance(); +} + +/* Return true if a random roll fits in the specified chance (range 0-100). */ +inline bool roll_chance_i(int chance) +{ + return chance > irand(0, 99); +} + +/* +* SFMT wrapper satisfying UniformRandomNumberGenerator concept for use in algorithms +*/ +class SFMTEngine +{ +public: + typedef uint32 result_type; + + result_type min() const { return std::numeric_limits::min(); } + result_type max() const { return std::numeric_limits::max(); } + result_type operator()() const { return rand32(); } + + static SFMTEngine& Instance(); +}; + +#endif // Random_h__ diff --git a/src/common/Utilities/Util.cpp b/src/common/Utilities/Util.cpp index 0488978ae17..21ccb37d6e7 100644 --- a/src/common/Utilities/Util.cpp +++ b/src/common/Utilities/Util.cpp @@ -20,10 +20,8 @@ #include "Common.h" #include "CompilerDefs.h" #include "utf8.h" -#include "SFMT.h" #include "Errors.h" // for ASSERT #include -#include #include #if COMPILER == COMPILER_GNU @@ -32,61 +30,6 @@ #include #endif -static boost::thread_specific_ptr sfmtRand; - -static SFMTRand* GetRng() -{ - SFMTRand* rand = sfmtRand.get(); - - if (!rand) - { - rand = new SFMTRand(); - sfmtRand.reset(rand); - } - - return rand; -} - -int32 irand(int32 min, int32 max) -{ - ASSERT(max >= min); - return int32(GetRng()->IRandom(min, max)); -} - -uint32 urand(uint32 min, uint32 max) -{ - ASSERT(max >= min); - return GetRng()->URandom(min, max); -} - -uint32 urandms(uint32 min, uint32 max) -{ - ASSERT(max >= min); - ASSERT(INT_MAX/IN_MILLISECONDS >= max); - return GetRng()->URandom(min * IN_MILLISECONDS, max * IN_MILLISECONDS); -} - -float frand(float min, float max) -{ - ASSERT(max >= min); - return float(GetRng()->Random() * (max - min) + min); -} - -uint32 rand32() -{ - return GetRng()->BRandom(); -} - -double rand_norm() -{ - return GetRng()->Random(); -} - -double rand_chance() -{ - return GetRng()->Random() * 100.0; -} - Tokenizer::Tokenizer(const std::string &src, const char sep, uint32 vectorReserve) { m_str = new char[src.length() + 1]; diff --git a/src/common/Utilities/Util.h b/src/common/Utilities/Util.h index 468b0201680..4126dc40f56 100644 --- a/src/common/Utilities/Util.h +++ b/src/common/Utilities/Util.h @@ -21,6 +21,7 @@ #include "Define.h" #include "Errors.h" +#include "Random.h" #include #include @@ -78,39 +79,6 @@ std::string secsToTimeString(uint64 timeInSecs, bool shortText = false, bool hou uint32 TimeStringToSecs(const std::string& timestring); std::string TimeToTimestampStr(time_t t); -/* Return a random number in the range min..max. */ -int32 irand(int32 min, int32 max); - -/* Return a random number in the range min..max (inclusive). */ -uint32 urand(uint32 min, uint32 max); - -/* Return a random millisecond value between min and max seconds. Functionally equivalent to urand(min*IN_MILLISECONDS, max*IN_MILLISECONDS). */ -uint32 urandms(uint32 min, uint32 max); - -/* Return a random number in the range 0 .. UINT32_MAX. */ -uint32 rand32(); - -/* Return a random number in the range min..max */ -float frand(float min, float max); - -/* Return a random double from 0.0 to 1.0 (exclusive). */ -double rand_norm(); - -/* Return a random double from 0.0 to 100.0 (exclusive). */ -double rand_chance(); - -/* Return true if a random roll fits in the specified chance (range 0-100). */ -inline bool roll_chance_f(float chance) -{ - return chance > rand_chance(); -} - -/* Return true if a random roll fits in the specified chance (range 0-100). */ -inline bool roll_chance_i(int chance) -{ - return chance > irand(0, 99); -} - inline void ApplyPercentModFloatVar(float& var, float val, bool apply) { if (val == -100.0f) // prevent set var to zero diff --git a/src/server/shared/Containers.h b/src/server/shared/Containers.h deleted file mode 100644 index 685acea05e3..00000000000 --- a/src/server/shared/Containers.h +++ /dev/null @@ -1,113 +0,0 @@ -/* - * Copyright (C) 2008-2015 TrinityCore - * - * This program is free software; you can redistribute it and/or modify it - * under the terms of the GNU General Public License as published by the - * Free Software Foundation; either version 2 of the License, or (at your - * option) any later version. - * - * This program is distributed in the hope that it will be useful, but WITHOUT - * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or - * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for - * more details. - * - * You should have received a copy of the GNU General Public License along - * with this program. If not, see . - */ - -#ifndef TRINITY_CONTAINERS_H -#define TRINITY_CONTAINERS_H - -#include "Define.h" -#include - -//! Because circular includes are bad -extern uint32 urand(uint32 min, uint32 max); - -namespace Trinity -{ - namespace Containers - { - template - void RandomResizeList(std::list &list, uint32 size) - { - uint32 list_size = uint32(list.size()); - - while (list_size > size) - { - typename std::list::iterator itr = list.begin(); - std::advance(itr, urand(0, list_size - 1)); - list.erase(itr); - --list_size; - } - } - - template - void RandomResizeList(std::list &list, Predicate& predicate, uint32 size) - { - //! First use predicate filter - std::list listCopy; - for (typename std::list::iterator itr = list.begin(); itr != list.end(); ++itr) - if (predicate(*itr)) - listCopy.push_back(*itr); - - if (size) - RandomResizeList(listCopy, size); - - list = listCopy; - } - - /* Select a random element from a container. Note: make sure you explicitly empty check the container */ - template typename C::value_type const& SelectRandomContainerElement(C const& container) - { - typename C::const_iterator it = container.begin(); - std::advance(it, urand(0, uint32(container.size()) - 1)); - return *it; - } - - /** - * @fn bool Trinity::Containers::Intersects(Iterator first1, Iterator last1, Iterator first2, Iterator last2) - * - * @brief Checks if two SORTED containers have a common element - * - * @param first1 Iterator pointing to start of the first container - * @param last1 Iterator pointing to end of the first container - * @param first2 Iterator pointing to start of the second container - * @param last2 Iterator pointing to end of the second container - * - * @return true if containers have a common element, false otherwise. - */ - template - bool Intersects(Iterator1 first1, Iterator1 last1, Iterator2 first2, Iterator2 last2) - { - while (first1 != last1 && first2 != last2) - { - if (*first1 < *first2) - ++first1; - else if (*first2 < *first1) - ++first2; - else - return true; - } - - return false; - } - - template class M, class... Rest> - void MultimapErasePair(M& multimap, K const& key, V const& value) - { - auto range = multimap.equal_range(key); - for (auto itr = range.first; itr != range.second;) - { - if (itr->second == value) - itr = multimap.erase(itr); - else - ++itr; - } - } - } - //! namespace Containers -} -//! namespace Trinity - -#endif //! #ifdef TRINITY_CONTAINERS_H -- cgit v1.2.3