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

1 files changed, 152 insertions, 0 deletions

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 <http://www.trinitycore.org/>
+ *
+ * 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 <http://www.gnu.org/licenses/>.
+ */
+
+#ifndef TRINITY_CONTAINERS_H
+#define TRINITY_CONTAINERS_H
+
+#include "Define.h"
+#include "Random.h"
+#include <functional>
+#include <list>
+#include <vector>
+
+namespace Trinity
+{
+    namespace Containers
+    {
+        template<class T>
+        void RandomResizeList(std::list<T> &list, uint32 size)
+        {
+            uint32 list_size = uint32(list.size());
+
+            while (list_size > size)
+            {
+                typename std::list<T>::iterator itr = list.begin();
+                std::advance(itr, urand(0, list_size - 1));
+                list.erase(itr);
+                --list_size;
+            }
+        }
+
+        template<class T, class Predicate>
+        void RandomResizeList(std::list<T> &list, Predicate& predicate, uint32 size)
+        {
+            //! First use predicate filter
+            std::list<T> listCopy;
+            for (typename std::list<T>::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 <class C>
+        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 <class C>
+        typename C::const_iterator SelectRandomWeightedContainerElement(C const& container, std::function<double(typename C::value_type const&)> weightExtractor)
+        {
+            std::vector<double> 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 <class C>
+        typename C::const_iterator SelectRandomWeightedContainerElement(C const& container, std::vector<double> weights)
+        {
+            std::discrete_distribution<uint32> 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<class Iterator1, class Iterator2>
+        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 K, class V, template<class, class, class...> class M, class... Rest>
+        void MultimapErasePair(M<K, V, Rest...>& 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