Core/Utils: Changed all Trinity::Containers utilities to work on all container types (including arrays where it makes sense)

* Added MapGetValuePtr to allow writing `if (Val* v = MapGetValuePtr(map, key))`
* Added utility IteratorPair class with begin/end methods and MapEqualRange for use in range for syntax with multimaps

3 files changed, 115 insertions, 48 deletions

diff --git a/src/common/Utilities/Containers.h b/src/common/Utilities/Containers.h
index 7d39b277996..dc0f4d7c244 100644
--- a/src/common/Utilities/Containers.h
+++ b/src/common/Utilities/Containers.h
@@ -21,41 +21,64 @@
 #include "Define.h"
 #include "Random.h"
 #include <algorithm>
-#include <functional>
-#include <list>
+#include <utility>
 #include <vector>
 
 namespace Trinity
 {
+    template<class T>
+    constexpr inline T* AddressOrSelf(T* ptr)
+    {
+        return ptr;
+    }
+
+    template<class T>
+    constexpr inline T* AddressOrSelf(T& not_ptr)
+    {
+        return std::addressof(not_ptr);
+    }
+
     namespace Containers
     {
-        template<class T>
-        void RandomResizeList(std::list<T>& list, uint32 size)
+        // replace with std::size in C++17
+        template<class C>
+        constexpr inline std::size_t Size(C const& container)
+        {
+            return container.size();
+        }
+
+        template<class T, std::size_t size>
+        constexpr inline std::size_t Size(T const(&)[size]) noexcept
         {
-            uint32 list_size = uint32(list.size());
+            return size;
+        }
 
-            while (list_size > size)
+        template<class C>
+        void RandomResizeList(C& container, std::size_t requestedSize)
+        {
+            uint32 currentSize = uint32(Size(container));
+            while (currentSize > requestedSize)
             {
-                typename std::list<T>::iterator itr = list.begin();
-                std::advance(itr, urand(0, list_size - 1));
-                list.erase(itr);
-                --list_size;
+                auto itr = std::begin(container);
+                std::advance(itr, urand(0, currentSize - 1));
+                container.erase(itr);
+                --currentSize;
             }
         }
 
-        template<class T, class Predicate>
-        void RandomResizeList(std::list<T> &list, Predicate predicate, uint32 size)
+        template<class C, class Predicate>
+        void RandomResizeList(C& container, Predicate&& predicate, std::size_t requestedSize)
         {
             //! 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);
+            C containerCopy;
 
-            if (size)
-                RandomResizeList(listCopy, size);
+            if (requestedSize)
+            {
+                std::copy_if(std::begin(container), std::end(container), std::inserter(containerCopy, std::end(containerCopy)), predicate);
+                RandomResizeList(containerCopy, requestedSize);
+            }
 
-            list = std::move(listCopy);
+            container = std::move(containerCopy);
         }
 
         /*
@@ -63,11 +86,11 @@ namespace Trinity
          *
          * Note: container cannot be empty
          */
-        template <class C>
-        typename C::value_type const& SelectRandomContainerElement(C const& container)
+        template<class C>
+        inline auto SelectRandomContainerElement(C const& container) -> decltype(*std::begin(container)) const&
         {
-            typename C::const_iterator it = container.begin();
-            std::advance(it, urand(0, uint32(container.size()) - 1));
+            auto it = std::begin(container);
+            std::advance(it, urand(0, uint32(Size(container)) - 1));
             return *it;
         }
 
@@ -80,12 +103,11 @@ namespace Trinity
          *
          * Note: container cannot be empty
          */
-        template <class C>
-        typename C::const_iterator SelectRandomWeightedContainerElement(C const& container, std::vector<double> weights)
+        template<class C>
+        auto SelectRandomWeightedContainerElement(C const& container, std::vector<double> weights) -> decltype(std::begin(container))
         {
-            std::discrete_distribution<uint32> dd(weights.begin(), weights.end());
-            typename C::const_iterator it = container.begin();
-            std::advance(it, dd(SFMTEngine::Instance()));
+            auto it = std::begin(container);
+            std::advance(it, urandweighted(weights.size(), weights.data()));
             return it;
         }
 
@@ -97,20 +119,20 @@ namespace Trinity
          *
          * Note: container cannot be empty
          */
-        template <class C, class Fn>
-        typename C::const_iterator SelectRandomWeightedContainerElement(C const& container, Fn weightExtractor)
+        template<class C, class Fn>
+        auto SelectRandomWeightedContainerElement(C const& container, Fn weightExtractor) -> decltype(std::begin(container))
         {
             std::vector<double> weights;
-            weights.reserve(container.size());
+            weights.reserve(Size(container));
             double weightSum = 0.0;
-            for (auto itr = container.begin(); itr != container.end(); ++itr)
+            for (auto& val : container)
             {
-                double weight = weightExtractor(*itr);
+                double weight = weightExtractor(val);
                 weights.push_back(weight);
                 weightSum += weight;
             }
             if (weightSum <= 0.0)
-                weights.assign(container.size(), 1.0);
+                weights.assign(Size(container), 1.0);
 
             return SelectRandomWeightedContainerElement(container, weights);
         }
@@ -122,23 +144,23 @@ namespace Trinity
          *
          * @param container Container to reorder
          */
-        template <class C>
-        void RandomShuffle(C& container)
+        template<class C>
+        inline void RandomShuffle(C& container)
         {
-            std::shuffle(container.begin(), container.end(), SFMTEngine::Instance());
+            std::shuffle(std::begin(container), std::end(container), SFMTEngine::Instance());
         }
 
         /**
-        * @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.
+         * @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)
@@ -156,6 +178,41 @@ namespace Trinity
             return false;
         }
 
+        /**
+         * Returns a pointer to mapped value (or the value itself if map stores pointers)
+         */
+        template<class M>
+        inline auto MapGetValuePtr(M& map, typename M::key_type const& key) -> decltype(AddressOrSelf(map.find(key)->second))
+        {
+            auto itr = map.find(key);
+            return itr != map.end() ? AddressOrSelf(itr->second) : nullptr;
+        }
+
+        /**
+         * @class IteratorPair
+         *
+         * @brief Utility class to enable range for loop syntax for multimap.equal_range uses
+         */
+        template<class iterator>
+        class IteratorPair
+        {
+        public:
+            IteratorPair() : _iterators() { }
+            IteratorPair(std::pair<iterator, iterator> iterators) : _iterators(iterators) { }
+
+            iterator begin() const { return _iterators.first; }
+            iterator end() const { return _iterators.second; }
+
+        private:
+            std::pair<iterator, iterator> _iterators;
+        };
+
+        template<class M>
+        inline auto MapEqualRange(M& map, typename M::key_type const& key) -> IteratorPair<decltype(map.begin())>
+        {
+            return { map.equal_range(key) };
+        }
+
         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)
         {
diff --git a/src/common/Utilities/Random.cpp b/src/common/Utilities/Random.cpp
index defe43d82c2..3a0cdedcf4b 100644
--- a/src/common/Utilities/Random.cpp
+++ b/src/common/Utilities/Random.cpp
@@ -20,8 +20,10 @@
 #include "Errors.h"
 #include "SFMT.h"
 #include <boost/thread/tss.hpp>
+#include <random>
 
 static boost::thread_specific_ptr<SFMTRand> sfmtRand;
+static SFMTEngine engine;
 
 static SFMTRand* GetRng()
 {
@@ -84,8 +86,13 @@ double rand_chance()
     return GetRng()->Random() * 100.0;
 }
 
+uint32 urandweighted(size_t count, double const* chances)
+{
+    std::discrete_distribution<uint32> dd(chances, chances + count);
+    return dd(SFMTEngine::Instance());
+}
+
 SFMTEngine& SFMTEngine::Instance()
 {
-    static SFMTEngine engine;
     return engine;
 }
diff --git a/src/common/Utilities/Random.h b/src/common/Utilities/Random.h
index 94a36db42f6..ded0a6c6e5c 100644
--- a/src/common/Utilities/Random.h
+++ b/src/common/Utilities/Random.h
@@ -47,6 +47,9 @@ TC_COMMON_API double rand_norm();
 /* Return a random double from 0.0 to 100.0 (exclusive). */
 TC_COMMON_API double rand_chance();
 
+/* Return a random number in the range 0..count (exclusive) with each value having a different chance of happening */
+TC_COMMON_API uint32 urandweighted(size_t count, double const* chances);
+
 /* Return true if a random roll fits in the specified chance (range 0-100). */
 inline bool roll_chance_f(float chance)
 {