#pragma once
#pragma region CPL License
/*
Nuclex Unreal Module
Copyright (C) 2014-2021 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

#include <CoreMinimal.h>

// --------------------------------------------------------------------------------------------- //

/// Container that selects items by rank, giving preference to the least recently used ones
template<typename TItem>
class NUCLEX_API RankedVariegator {

  /// Initializes a new ranked variegator
  public: RankedVariegator() {}

  /// Adds a ranked item for the variegator to select from
  /// @param  rank  Rank under which the item will be stored
  /// @param  item  Item that will be added to the pool
  public: void Insert(float rank, const TItem &item) {
    int32 count = this->items.Num();

    for(int32 index = 0; index < count; ++index) {
      if(this->items[index].Key >= rank) {
        this->items.Insert(RankedItemType(rank, item), index);
        return;
      }
    }

    this->items.Add(RankedItemType(rank, item));
  }

  /// Looks up a not recently used item matching the specified rank
  /// @param  rank  Rank of the item that should be returned
  /// @returns A random, not recently used item with the specified rank
  public: TItem Pick(float rank) {
    int32 count = this->items.Num();
    if(count == 0) {
      UE_LOG(
        LogTemp, Error,
        TEXT("RankedVariegator::Pick() - There are no items to choose from!")
      );
      return TItem();
    }

    // Index of the first and last element matching the specified rank
    int32 startIndex = findFirstIndexWithNearestRank(rank);
    int32 endIndex = findLastItemWithEqualRank(startIndex);

    // Use the biased random generated to pick an item
    if(endIndex > startIndex) {
      int32 offset = cubicRandom(endIndex - startIndex + 1);
      return moveItemToLast(startIndex + offset);
    } else {
      return this->items[startIndex].Value;
    }
  }

  /// Looks up a not recently used item matching (or close to) the specified rank
  /// @param  rank                 Rank of the item that should be returned
  /// @param  consideredItemCount  Minmum number of items that wil be considered.
  ///                              If less items wit the desired rank exist, items closest in
  ///                              rank will be recruited until the required count is reached
  /// @returns An item with the specified rank (or close to it if additional items had to
  ///          be recruited to reach the specified minimum item count)
  public: TItem Pick(float rank, int32 consideredItemCount) {
    int32 count = this->items.Num();
    if(count == 0) {
      UE_LOG(
        LogTemp, Error,
        TEXT("RankedVariegator::Pick() - There are no items to choose from!")
      );
      return TItem();
    }

    // Index of the first and last element matching the specified rank
    int32 startIndex = findFirstIndexWithNearestRank(rank);
    int32 endIndex = findLastItemWithEqualRank(startIndex);
    int32 matchingItemCount = endIndex - startIndex + 1;

    // If we have enough matching items, just pick one of them by (biased) random
    if(matchingItemCount >= consideredItemCount) {
      int32 offset = cubicRandom(consideredItemCount);
      return moveItemToLast(startIndex + offset);
    }

    // Pick a (biased) random index disregarding the number of matching items
    int32 offset = cubicRandom(FMath::Min(count, consideredItemCount));

    // If the index just happened to be within the matching items, this is simple:
    if(offset < matchingItemCount) {
      return moveItemToLast(startIndex + offset);
    }

    int32 index = endIndex;

    // If the index was beyond the matching items, we need to get creative.
    // Take closest neighboring items until we've brought the offset down to zero.
    offset -= matchingItemCount;
    while(offset > 0) {
      int32 nextEndIndex = endIndex + 1;
      int32 prevStartIndex = startIndex - 1;
      if(nextEndIndex < count) { // Can we consider the next item?
        if(prevStartIndex > 0) { // Can we also consider the previous item?
          float startDelta = FMath::Abs(this->items[prevStartIndex].Key - rank);
          float endDelta = FMath::Abs(this->items[nextEndIndex].Key - rank);
          if(endDelta < startDelta) {
            endIndex = nextEndIndex;
            index = endIndex;
          } else {
            startIndex = prevStartIndex;
            index = startIndex;
          }
        } else { // We only have a next item
          endIndex = nextEndIndex;
          index = endIndex;
        }
      } else if(prevStartIndex > 0) { // Can we consider the previous item
        startIndex = prevStartIndex;
        index = startIndex;
      } else {
        UE_LOG(
          LogTemp, Error,
          TEXT("RankedVariegator::Pick() - Calculated offset was invalid!")
        );
      }

      --offset;
    }

    return moveItemToLast(index);
  }

  /// Moves the item to the last place amongst its rank and returns its value
  /// @param  index  Current index of the item that will be moved into last place
  /// @returns The moved item
  private: TItem moveItemToLast(int32 index) {
    int32 lastIndex = this->items.Num() - 1;
    if(index < lastIndex) {
      float rank = this->items[index].Key;
      do {
        int32 nextIndex = index + 1;
        float nextRank = this->items[nextIndex].Key;

        if(rank < nextRank) {
          break;
        }

        this->items.Swap(index, nextIndex);
        index = nextIndex;
      } while(index < lastIndex);
    }

    return this->items[index].Value;
  }

  /// Returns the index of the first element with a rank equal or greater than the one specified
  /// @param  rank  Rank of which the first item should be located
  /// @returns The index of the first item with the specified rank
  private: int32 findFirstIndexWithNearestRank(float rank) {
    float previousRank = this->items[0].Key;
    float smallestDelta = FMath::Abs(previousRank - rank);
    int32 nearestRankStartIndex = 0;

    int32 count = this->items.Num();
    for(int32 index = 1; index < count; ++index) {
      float currentRank = this->items[index].Key;
      if(currentRank != previousRank) {
        float currentDelta = FMath::Abs(currentRank - rank);
        if(currentDelta < smallestDelta) {
          smallestDelta = currentDelta;
          nearestRankStartIndex = index;
        } else {
          break; // Deltas are increasing, we've run past the closest index
        }
        previousRank = currentRank;
      }
    }

    return nearestRankStartIndex;
  }

  /// Counts the number of items following the specified item with the specified rank
  /// @param  startIndex  Index of the item at which the search will began
  /// @returns The last item with the same rank after the specified item index
  private: int32 findLastItemWithEqualRank(int32 startIndex) {
    int32 count = this->items.Num();

    float startRank = this->items[startIndex].Key;
    ++startIndex;
    while(startIndex < count) {
      if(this->items[startIndex].Key != startRank) {
        break;
      }
      ++startIndex;
    }

    return (startIndex - 1);
  }

  /// Returns a random integer that is more likely to be one of the lower numbers
  /// @param  max  Maximum (exclusive) random number that should be returned
  /// @returns A random integer up to the specified maximum
  private: int32 cubicRandom(int32 max) {
    float randomInterval = FMath::FRandRange(0.0f, 1.0f);
    randomInterval *= randomInterval;

    return FMath::Min(
      static_cast<int32>(randomInterval * static_cast<float>(max)),
      max - 1
    );
  }

  /// Pair storing an item together with its rank
  private: typedef TPair<float, TItem> RankedItemType;
  /// List of ranked items
  private: typedef TArray<RankedItemType> ItemListType;

  /// Items the variegator can select from, sorted by rank
  private: ItemListType items;

};

// --------------------------------------------------------------------------------------------- //