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 ++++++++++++++++++++++++++++++++++++++ 1 file changed, 152 insertions(+) create mode 100644 src/common/Utilities/Containers.h (limited to 'src/common/Utilities/Containers.h') 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 -- cgit v1.2.3