#pragma region CPL License /* Nuclex Native Framework Copyright (C) 2002-2023 Nuclex Development Labs This library is free software; you can redistribute it and/or modify it under the terms of the IBM Common Public License as published by the IBM Corporation; either version 1.0 of the License, or (at your option) any later version. This library 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 IBM Common Public License for more details. You should have received a copy of the IBM Common Public License along with this library */ #pragma endregion // CPL License #ifndef NUCLEX_SUPPORT_COLLECTIONS_VARIEGATOR_H #define NUCLEX_SUPPORT_COLLECTIONS_VARIEGATOR_H #include // for std::size_t #include // for std::default_random_engine, std::uniform_int_distribution #include // for std::vector #include // for std::unordered_set #include // for std::unordered_map namespace Nuclex { namespace Support { namespace Collections { // ------------------------------------------------------------------------------------------- // /// Randomly selects between different options, trying to avoid repetition /// Type of keys through which values can be looked up /// Type of values provided by the variegator /// Allocator used to reserve memory for values /// /// /// This class is useful wherever randomness is involved in a game: picking random /// actions for an NPC to execute, selecting different songs to play, displaying /// different dialogue and more. /// /// /// In principle, it works like a multimap, associating keys with a number of values /// and allowing you to look up a values by their keys. Unlike a multimap, it will /// avoid handing out a previously provided value again. /// /// /// A typical usage would be to set up a mapping between situations and dialogue lines. /// Upon calling with the situation 'detected-player-stealing', /// the variegator would return a random (but not recently used) value which in this case /// might contain a commentary an NPC might make upon encountering that situation. /// Other NPCs requesting dialogue lines for the same situation would receive different /// random commentary for as long as long as available data allows. /// /// template> class Variegator { /// Initializes a new variegator /// /// How far into the past the variegator will look to avoid repetition /// public: Variegator(std::size_t historyLength = 64) : historyLength(historyLength), historyFull(false), historyTailIndex(0), history(this->valueAllocator.allocate(historyLength)) {} /// Destroys the variegator and reclaims all memory public: ~Variegator() { freeHistory(); this->valueAllocator.deallocate(this->history, this->historyLength); } /// Removes all entries from the variegator /// /// This is mainly useful if you are storing smart pointers to values of substantial /// size (eg. audio clips instead of just resource proxies or paths) and need to /// reclaim memory. /// public: void Clear() { this->values.clear(); freeHistory(); this->historyFull = false; this->historyTailIndex = 0; } /// Checks whether the variegator is empty /// True if there are no entries in the variegator public: bool IsEmpty() const { return this->values.empty(); } /// Returns the number of values in the variegator /// The number of values stored in the variegator /// /// If the same value is added with different keys (a situation that doesn't make /// sense because such reuse should be covered by specifying multiple keys in /// a query), it will be counted multiple times. /// public: std::size_t GetSize() const { return this->values.size(); } /// /// Insert a new value that can be returned when requesting the specified key /// /// Key of the value that will be inserted /// Value that will be inserted under the provided key public: void Insert(const TKey &key, const TValue &value) { this->values.insert(ValueMap::value_type(key, value)); } /// Retrieves a random value associated with the specified key /// For for which a value will be looked up /// A random value associated with the specified key public: TValue Get(const TKey &key) const { return Get(&key, std::size_t(1)); } /// Retrieves a random value associated with one of the specified keys /// First key in a list of keys that will be considered /// Number of keys following the first key in the list /// /// In many cases, you have generic situations (such as 'detected-player-stealing', /// 'observed-hostile-action') and specified situations (such as /// 'detected-player-stealing-from-beggar', 'observed-hostile-action-on-cop') /// where a values from both pools should be considered. This method allows you /// to specify any number of keys, creating a greater set of values the variegator /// can pick between. /// public: template TValue Get( TInputIterator first, std::size_t count = 1 ) const { std::unordered_set candidates; while(count > 0) { std::pair valueRange = this->values.equal_range(*first); // Add all candidate values into our set. Could do this via std::copy() with // std::inserter(), but it yields the same amount of code and adds a header dependency while(valueRange.first != valueRange.second) { candidates.insert(valueRange.first->second); ++valueRange.first; } ++first; --count; } TValue result = destructivePickCandidateValue(candidates); addRecentlyUsedValue(result); return result; } /// Retrieves a random value associated with one of the specified keys /// First key in a list of keys that will be considered /// /// Iterator past the last in the list of keys that will be considered /// /// /// In many cases, you have generic situations (such as 'detected-player-stealing', /// 'observed-hostile-action') and specific situations (such as /// 'detected-player-stealing-from-beggar', 'observed-hostile-action-on-cop') /// where a values from both pools should be considered. This method allows you /// to specify any number of keys, creating a greater set of values the variegator /// can pick between. /// public: template TValue Get( TInputIterator first, TInputIterator onePastLast ) const { std::unordered_set candidates; while(first != onePastLast) { std::pair valueRange = this->values.equal_range(*first); // Add all candidate values into our set. Could do this via std::copy() with // std::inserter(), but it yields the same amount of code and adds a header dependency while(valueRange.first != valueRange.second) { candidates.insert(valueRange.first->second); ++valueRange.first; } ++first; } TValue result = destructivePickCandidateValue(candidates); addRecentlyUsedValue(result); return result; } /// Picks amongst the values in a set /// /// Set containing the candidats values to consider. Will be destroyed. /// /// The least recently used candidate value or a random one private: TValue destructivePickCandidateValue(std::unordered_set &candidates) const { //removeRuleDeviatingValues(candidates); removeRecentlyUsedValues(candidates); switch(candidates.size()) { case 0: { throw std::runtime_error("No values mapped to this key"); } case 1: { return *candidates.begin(); } default: { std::uniform_int_distribution distributor(0, candidates.size() - 1); std::size_t index = distributor(this->randomNumberGenerator); std::unordered_set::const_iterator iterator = candidates.begin(); while(index > 0) { ++iterator; --index; } return *iterator; } } } /// Adds a recently used value to the history /// Value that will be added to the history private: void addRecentlyUsedValue(const TValue &value) const { if(this->historyTailIndex == this->historyLength) { this->historyFull = true; this->history[0] = value; this->historyTailIndex = 1; } else if(this->historyFull) { this->history[this->historyTailIndex] = value; ++this->historyTailIndex; } else { this->valueAllocator.construct(this->history + this->historyTailIndex, value); ++this->historyTailIndex; } } /// Removes all values that are in the recent use list from a set /// Set from which recently used values are removed /// /// Stops removing values when there's only 1 value left in the set /// private: void removeRecentlyUsedValues(std::unordered_set &candidates) const { if(candidates.size() <= 1) { return; } if(this->historyFull) { // History buffer has wrapped around std::size_t index = this->historyTailIndex; while(index > 0) { --index; if(candidates.erase(this->history[index])) { if(candidates.size() <= 1) { return; } } } index = this->historyLength; while(index > this->historyTailIndex) { --index; if(candidates.erase(this->history[index])) { if(candidates.size() <= 1) { return; } } } } else { // History buffer was not full yet std::size_t index = this->historyTailIndex; while(index > 0) { --index; if(candidates.erase(this->history[index])) { if(candidates.size() <= 1) { return; } } } } } /// Frees all memory used by the individual history entries /// /// The history array itself is kept alive and the tail index + full flag will /// not be reset. /// private: void freeHistory() { if(this->historyFull) { // History buffer has wrapped around std::size_t index = this->historyTailIndex; while(index > 0) { --index; this->valueAllocator.destroy(this->history + index); } index = this->historyLength; while(index > this->historyTailIndex) { --index; this->valueAllocator.destroy(this->history + index); } } else { // History buffer was not full yet std::size_t index = this->historyTailIndex; while(index > 0) { --index; this->valueAllocator.destroy(this->history + index); } } } private: Variegator(const Variegator &); private: Variegator &operator =(const Variegator &); /// Map by which potential values can be looked up via their key private: typedef std::unordered_multimap ValueMap; /// Stores the entries the variegator can select from by their keys private: ValueMap values; /// Random number generator that will be used to pick random values private: mutable std::default_random_engine randomNumberGenerator; /// Used to allocate values in the recently used list private: mutable TValueAllocator valueAllocator; /// Number of entries in the recently used list private: std::size_t historyLength; /// Array containing the most recently provided values private: mutable TValue *history; /// Index of the tail in the recently used value array private: mutable std::size_t historyTailIndex; /// Whether the recently used value history is at capacity private: mutable bool historyFull; }; // ------------------------------------------------------------------------------------------- // }}} // namespace Nuclex::Support::Collections #endif // NUCLEX_SUPPORT_COLLECTIONS_VARIEGATOR_H