Containers.h

Go to the documentation of this file.

/*
 * This file is part of the TrinityCore Project. See AUTHORS file for Copyright information
 *
 * 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 "MapUtils.h"
#include "Random.h"
#include <algorithm>
#include <iterator>
#include <span>
#include <stdexcept>
#include <type_traits>
#include <utility>
#include <vector>
 
namespace Trinity
{
 template <class T>
 class CheckedBufferOutputIterator
 {
 public:
 using iterator_category = std::output_iterator_tag;
 using value_type = void;
 using pointer = T*;
 using reference = T&;
 using difference_type = std::ptrdiff_t;
 
 CheckedBufferOutputIterator(T* buf, size_t n) : _buf(buf), _end(buf+n) {}
 
 T& operator*() const { check(); return *_buf; }
 CheckedBufferOutputIterator& operator++() { check(); ++_buf; return *this; }
 CheckedBufferOutputIterator operator++(int) { CheckedBufferOutputIterator v = *this; operator++(); return v; }
 
 size_t remaining() const { return (_end - _buf); }
 
 private:
 T* _buf;
 T* _end;
 void check() const
 {
 if (!(_buf < _end))
 throw std::out_of_range("index");
 }
 };
 
 namespace Containers
 {
 // resizes <container> to have at most <requestedSize> elements
 // if it has more than <requestedSize> elements, the elements to keep are selected randomly
 template<class C>
 void RandomResize(C& container, std::size_t requestedSize)
 {
 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");
 if (std::size(container) <= requestedSize)
 return;
 auto keepIt = std::begin(container), curIt = std::begin(container);
 uint32 elementsToKeep = requestedSize, elementsToProcess = std::size(container);
 while (elementsToProcess)
 {
 // this element has chance (elementsToKeep / elementsToProcess) of being kept
 if (urand(1, elementsToProcess) <= elementsToKeep)
 {
 if (keepIt != curIt)
 *keepIt = std::move(*curIt);
 ++keepIt;
 --elementsToKeep;
 }
 ++curIt;
 --elementsToProcess;
 }
 container.erase(keepIt, std::end(container));
 }
 
 template<class C, class Predicate>
 void RandomResize(C& container, Predicate&& predicate, std::size_t requestedSize)
 {
 C containerCopy;
 std::copy_if(std::begin(container), std::end(container), std::inserter(containerCopy, std::end(containerCopy)), predicate);
 
 if (requestedSize)
 RandomResize(containerCopy, requestedSize);
 
 container = std::move(containerCopy);
 }
 
 /*
 * Select a random element from a container.
 *
 * Note: container cannot be empty
 */
 template<class C>
 inline auto SelectRandomContainerElement(C const& container) -> typename std::add_const<decltype(*std::begin(container))>::type&
 {
 auto it = std::begin(container);
 std::advance(it, urand(0, uint32(std::size(container)) - 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 weights Chances of each element to be selected, must be in the same order as elements in container.
 * Caller is responsible for checking that sum of all weights is greater than 0.
 *
 * Note: container cannot be empty
 */
 template<class C>
 inline auto SelectRandomWeightedContainerElement(C const& container, std::span<double> const& weights) -> decltype(std::begin(container))
 {
 auto it = std::begin(container);
 std::advance(it, urandweighted(weights.size(), weights.data()));
 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, expected to take an element of the container and returning a double
 *
 * Note: container cannot be empty
 */
 template<class C, class Fn>
 inline auto SelectRandomWeightedContainerElement(C const& container, Fn weightExtractor) -> decltype(std::begin(container))
 {
 std::size_t size = std::size(container);
 std::size_t i = 0;
 double* weights = new double[size];
 double weightSum = 0.0;
 for (auto const& val : container)
 {
 double weight = weightExtractor(val);
 weights[i++] = weight;
 weightSum += weight;
 }
 
 auto it = std::begin(container);
 std::advance(it, weightSum > 0.0 ? urandweighted(size, weights) : urand(0, uint32(std::size(container)) - 1));
 delete[] weights;
 return it;
 }
 
 template<class Iterator>
 inline void RandomShuffle(Iterator begin, Iterator end)
 {
 std::shuffle(begin, end, RandomEngine::Instance());
 }
 
 template<class C>
 inline void RandomShuffle(C& container)
 {
 RandomShuffle(std::begin(container), std::end(container));
 }
 
 template<class Iterator1, class Iterator2>
 inline 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 Iterator1, class Iterator2, class Predicate>
 inline bool Intersects(Iterator1 first1, Iterator1 last1, Iterator2 first2, Iterator2 last2, Predicate&& equalPred)
 {
 while (first1 != last1 && first2 != last2)
 {
 if (*first1 < *first2)
 ++first1;
 else if (*first2 < *first1)
 ++first2;
 else if (!equalPred(*first1, *first2))
 ++first1, ++first2;
 else
 return true;
 }
 
 return false;
 }
 
 namespace Impl
 {
 template <typename Container, typename Predicate>
 void EraseIfMoveAssignable(Container& c, Predicate p)
 {
 auto wpos = c.begin();
 for (auto rpos = c.begin(), end = c.end(); rpos != end; ++rpos)
 {
 if (!p(*rpos))
 {
 if (rpos != wpos)
 std::swap(*rpos, *wpos);
 ++wpos;
 }
 }
 c.erase(wpos, c.end());
 }
 
 template <typename Container, typename Predicate>
 void EraseIfNotMoveAssignable(Container& c, Predicate p)
 {
 for (auto it = c.begin(); it != c.end();)
 {
 if (p(*it))
 it = c.erase(it);
 else
 ++it;
 }
 }
 }
 
 template <typename Container, typename Predicate>
 void EraseIf(Container& c, Predicate p)
 {
 if constexpr (std::is_move_assignable_v<decltype(*c.begin())>)
 Impl::EraseIfMoveAssignable(c, std::ref(p));
 else
 Impl::EraseIfNotMoveAssignable(c, std::ref(p));
 }
 
 template<typename T>
 inline decltype(auto) EnsureWritableVectorIndex(std::vector<T>& vec, typename std::vector<T>::size_type i)
 {
 if (i >= vec.size())
 vec.resize(i + 1);
 
 return vec[i];
 }
 
 template<typename T>
 inline decltype(auto) EnsureWritableVectorIndex(std::vector<T>& vec, typename std::vector<T>::size_type i, T const& resizeDefault)
 {
 if (i >= vec.size())
 vec.resize(i + 1, resizeDefault);
 
 return vec[i];
 }
 }
}
 
#endif