//*************************************************************************
//
//  Advanced_Benchmark_StdDeque (STL Container) - C++ language
//
//  Advanced_Benchmark_StdDeque.cpp
//
//  Developed by Armando Giuseppe BONATTO MINELLA.
//
//*************************************************************************
#include <QtCore>
#include <deque>
#include <iostream>
#include <iterator>
#include <time.h>
#include <unistd.h>
#include <vector>
//*************************************************************************
#define SOURCE_FILESIZE_MIN   42949672960ll
#define ELEMENTS_EXPONENT_MIN           1
#define ELEMENTS_EXPONENT_MAX          30
#define RANGE_OF_VALUES_MIN             2ull
#define RANGE_OF_VALUES_MAX       1048576ull
#define SEED_MIN                        0ll
#define SEED_MAX               8589934592ll
#define TIME_LIMIT_MIN                  0ull // 0 = Unlimited
#define TIME_LIMIT_MAX           31536000ull // About one year
#define ROUNDS_EXPONENT                30
//*************************************************************************
typedef enum : std::int32_t
{
  Executable       = 0,
  SourceFilename   = 1,
  ElementsExponent = 2,
  RangeOfValues    = 3,
  Seed             = 4,
  TimeLimit        = 5
} Arguments_t;
//*************************************************************************
typedef std::deque<std::uint64_t>           Container_t;
typedef std::deque<std::uint64_t>::iterator Iterator_t ;
//*************************************************************************
std::int32_t main (std::int32_t   argc   ,
                   char         * argv [] )
{
  bool valid = false;
  //-------------------------------------
  if (!((argc                                                                >  Arguments_t::TimeLimit) &&
        QFile::exists (QString (argv [Arguments_t::SourceFilename]))                                    &&
        (QFile (QString (argv [Arguments_t::SourceFilename])).size ()        >= SOURCE_FILESIZE_MIN)    &&
        (QString (argv [Arguments_t::ElementsExponent]).toInt (& (valid))    >= ELEMENTS_EXPONENT_MIN)  &&
        valid                                                                                           &&
        (QString (argv [Arguments_t::ElementsExponent]).toInt (& (valid))    <= ELEMENTS_EXPONENT_MAX)  &&
        valid                                                                                           &&
        (QString (argv [Arguments_t::RangeOfValues]).toULongLong (& (valid)) >= RANGE_OF_VALUES_MIN)    &&
        valid                                                                                           &&
        (QString (argv [Arguments_t::RangeOfValues]).toULongLong (& (valid)) <= RANGE_OF_VALUES_MAX)    &&
        valid                                                                                           &&
        (QString (argv [Arguments_t::Seed]).toLongLong (& (valid))           >= SEED_MIN)               &&
        valid                                                                                           &&
        (QString (argv [Arguments_t::Seed]).toLongLong (& (valid))           <= SEED_MAX)               &&
        valid                                                                                           &&
        (QString (argv [Arguments_t::TimeLimit]).toULongLong (& (valid))     <= TIME_LIMIT_MAX)         &&
        valid                                                                                             ))
  {
    std::cout << ""                                                                                                                                                                     << std::endl
              << "WARNING: invalid command line arguments"                                                                                                                              << std::endl
              << ""                                                                                                                                                                     << std::endl
              << "Usage: Advanced_Benchmark_StdDeque <Source filename> <Elements exponent> <Range of values> <Seed> <Time limit>"                                                       << std::endl
              << "       +--> Source filename"                                                                                                                                          << std::endl
              << "       |    +--> Minimum size of " << QString::asprintf ("%'lld",SOURCE_FILESIZE_MIN).toStdString () << " bytes"                                                      << std::endl
              << "       +--> Elements exponent (power of 2)"                                                                                                                           << std::endl
              << "       |    +--> From " << QString::asprintf ("%'d",ELEMENTS_EXPONENT_MIN).toStdString () << " to " << QString::asprintf ("%'d",ELEMENTS_EXPONENT_MAX).toStdString () << std::endl
              << "       +--> Range of values"                                                                                                                                          << std::endl
              << "       |    +--> From " << QString::asprintf ("%'llu",RANGE_OF_VALUES_MIN).toStdString () << " to " << QString::asprintf ("%'llu",RANGE_OF_VALUES_MAX).toStdString () << std::endl
              << "       +--> Seed"                                                                                                                                                     << std::endl
              << "       |    +--> From " << QString::asprintf ("%'lld",SEED_MIN).toStdString () << " to " << QString::asprintf ("%'lld",SEED_MAX).toStdString ()                       << std::endl
              << "       +--> Time limit"                                                                                                                                               << std::endl
              << "            +--> From " << QString::asprintf ("%'llu",TIME_LIMIT_MIN).toStdString () << " to " << QString::asprintf ("%'llu",TIME_LIMIT_MAX).toStdString ()           << std::endl
              << "                 +--> 0              = unlimited"                                                                                                                     << std::endl
              << "                 +--> Greater than 0 = time limit in seconds"                                                                                                         << std::endl
              << ""                                                                                                                                                                     << std::endl;
  }
  else
  {
    QString       sourceFilename                    = QString (argv [Arguments_t::SourceFilename])              ;
    std::int32_t  elementsExponent                  = QString (argv [Arguments_t::ElementsExponent]).toInt ()   ;
    std::uint64_t rangeOfValues                     = QString (argv [Arguments_t::RangeOfValues]).toULongLong ();
    std::int64_t  seed                              = QString (argv [Arguments_t::Seed]).toLongLong ()          ;
    std::uint64_t timeLimit                         = QString (argv [Arguments_t::TimeLimit]).toULongLong ()    ;
    std::uint64_t elements                          = (1ull << elementsExponent)                                ;
    std::uint64_t rounds                            = (1ull << ROUNDS_EXPONENT)                                 ;
    std::uint16_t endianness                        = 1u                                                        ;
    QFile         sourceFile       (sourceFilename)                                                             ;
    //-------------------------------------
    std::cout << "Container......: " << "std::deque (STL Container)"                                                      << std::endl
              << "Benchmark......: " << "Advanced"                                                                        << std::endl
              << "Payload........: " << "8 bytes (64 bits)"                                                               << std::endl
              << "Source file....: " << sourceFilename.toStdString ()                                                     << std::endl
              << "Endianness.....: " << ((* ((std::uint8_t *) (& (endianness)))) ?
                                         "Little"                                :
                                         "Big"                                    ) << "-Endian"                          << std::endl
              << "Elements.......: " << QString::asprintf ("%'13llu",((unsigned long long) elements)).toStdString ()      << std::endl
              << "Range of values: " << QString::asprintf ("%'13llu",((unsigned long long) rangeOfValues)).toStdString () << std::endl
              << "Seed...........: " << QString::asprintf ("%'13lld",((long long) seed)).toStdString ()                   << std::endl
              << "Rounds.........: " << QString::asprintf ("%'13llu",((unsigned long long) rounds)).toStdString ()        << std::endl
              << "Time limit.....: " << ((timeLimit == 0ull)                                                           ?
                                         "Unlimited"                                                                   :
                                         QString::asprintf ("%'13llu",((unsigned long long) timeLimit)).toStdString ()  ) << std::endl
              << ""                                                                                                       << std::endl
              << "Rounds        Time [s]                Digest (SHA-256)"                                                 << std::endl;
    if (sourceFile.open (QIODeviceBase::ReadOnly))
    {
      if (sourceFile.seek (seed))
      {
        QCryptographicHash         hash               (QCryptographicHash::Algorithm::Sha256)          ;
        std::vector<std::uint64_t> occurrenceCounters (rangeOfValues,
                                                       0ull          )                                 ;
        Container_t                container                                                           ;
        Iterator_t                 containerIterator                                                   ;
        timespec                   timeStart                                                  = { 0,0 };
        timespec                   timeStop                                                   = { 0,0 };
        std::uint64_t              timeElapsed                                                = 0ull   ;
        std::uint64_t              counter                                                    = 0ull   ;
        std::uint64_t              index                                                      = 0ull   ;
        std::uint64_t              value                                                      = 0ull   ;
        std::uint64_t              nextDigest                                                 = 1ull   ;
        std::uint64_t              containerIndex                                             = 0ull   ;
        //-------------------------------------
        // Preload container and output initial digest
        //-------------------------------------
        while (container.size () < elements)
        {
          sourceFile.read (((char *) (& (value))),
                           sizeof (std::uint64_t) );
          value                      %= rangeOfValues; // Normalize value to rangeOfValues
          occurrenceCounters [value] += 1ull;
          container.push_back (value);
        }
        for (Iterator_t iterator = container.begin ();(iterator != container.end ());++iterator)
        {
          hash.addData (QByteArrayView (((char *) (& (* iterator))),
                                        sizeof (std::uint64_t)      ));
        }
        std::cout << "            0"                                  << " "
                  << "            0.000000000"                        << " "
                  << QString (hash.result ().toHex ()).toStdString () << std::endl;
        //-------------------------------------
        clock_gettime (CLOCK_PROCESS_CPUTIME_ID,
                       (& (timeStart))          );
        while (counter < rounds)
        {
          //*************************************
          // Remove
          //*************************************
          sourceFile.read (((char *) (& (index))),
                           sizeof (std::uint64_t) );
          containerIndex    = (index             %
                               container.size ()  ); // Get the containerIndex normalizing index to container size
          containerIterator = (container.begin () +
                               containerIndex      );
          value             = (* containerIterator);
          if (occurrenceCounters [value] >= 2ull)
          {
            //-------------------------------------
            // Get the occurrence index of value
            //-------------------------------------
            std::uint64_t occurrenceIndex = 0ull;
            //-------------------------------------
            if (containerIndex >= (container.size () /
                                   2ull               ))
            {
              for (Iterator_t iterator = containerIterator;(iterator != container.end ());++iterator)
              {
                if ((* iterator) == value)
                {
                  ++occurrenceIndex;
                }
              }
              occurrenceIndex = (occurrenceCounters [value] -
                                 occurrenceIndex             );
            }
            else
            {
              for (Iterator_t iterator = container.begin ();(iterator != containerIterator);++iterator)
              {
                if ((* iterator) == value)
                {
                  ++occurrenceIndex;
                }
              }
            }
            //-------------------------------------
            // Get the occurrence index to remove
            //-------------------------------------
            std::uint64_t occurrenceIndexToRemove = ((occurrenceIndex +
                                                      index            )        %
                                                     occurrenceCounters [value]  );
            //-------------------------------------
            // Get the container position to remove
            //-------------------------------------
            if (occurrenceIndex < occurrenceIndexToRemove)
            {
              do
              {
                ++containerIterator;
                if ((* containerIterator) == value)
                {
                  ++occurrenceIndex;
                  if (occurrenceIndex == occurrenceIndexToRemove)
                  {
                    break;
                  }
                }
              }
              while (true);
            }
            else
            {
              if (occurrenceIndex > occurrenceIndexToRemove)
              {
                do
                {
                  --containerIterator;
                  if ((* containerIterator) == value)
                  {
                    --occurrenceIndex;
                    if (occurrenceIndex == occurrenceIndexToRemove)
                    {
                      break;
                    }
                  }
                }
                while (true);
              }
            }
          }
          //-------------------------------------
          // Remove and update the counter of occurrences
          //-------------------------------------
          container.erase (containerIterator);
          occurrenceCounters [value] -= 1ull;
          //*************************************
          // Insert
          //*************************************
          sourceFile.read (((char *) (& (index))),
                           sizeof (std::uint64_t) );
          containerIndex    = (index             %
                               container.size ()  ); // Get the containerIndex normalizing index to container size
          containerIterator = (container.begin () +
                               containerIndex      );
          value             = (* containerIterator);
          if (occurrenceCounters [value] >= 2ull)
          {
            //-------------------------------------
            // Get the occurrence index of value
            //-------------------------------------
            std::uint64_t occurrenceIndex = 0ull;
            //-------------------------------------
            if (containerIndex >= (container.size () /
                                   2ull               ))
            {
              for (Iterator_t iterator = containerIterator;(iterator != container.end ());++iterator)
              {
                if ((* iterator) == value)
                {
                  ++occurrenceIndex;
                }
              }
              occurrenceIndex = (occurrenceCounters [value] -
                                 occurrenceIndex             );
            }
            else
            {
              for (Iterator_t iterator = container.begin ();(iterator != containerIterator);++iterator)
              {
                if ((* iterator) == value)
                {
                  ++occurrenceIndex;
                }
              }
            }
            //-------------------------------------
            // Get the occurrence index to insert
            //-------------------------------------
            std::uint64_t occurrenceIndexToInsert = ((occurrenceIndex +
                                                      index            )        %
                                                     occurrenceCounters [value]  );
            //-------------------------------------
            // Get the container position to insert
            //-------------------------------------
            if (occurrenceIndex < occurrenceIndexToInsert)
            {
              do
              {
                ++containerIterator;
                if ((* containerIterator) == value)
                {
                  ++occurrenceIndex;
                  if (occurrenceIndex == occurrenceIndexToInsert)
                  {
                    break;
                  }
                }
              }
              while (true);
            }
            else
            {
              if (occurrenceIndex > occurrenceIndexToInsert)
              {
                do
                {
                  --containerIterator;
                  if ((* containerIterator) == value)
                  {
                    --occurrenceIndex;
                    if (occurrenceIndex == occurrenceIndexToInsert)
                    {
                      break;
                    }
                  }
                }
                while (true);
              }
            }
          }
          //-------------------------------------
          // Insert the new value and update the counter of occurrences
          //-------------------------------------
          sourceFile.read (((char *) (& (value))),
                           sizeof (std::uint64_t) );
          value %= rangeOfValues; // Normalize value to rangeOfValues
          container.insert (containerIterator,
                            value             );
          occurrenceCounters [value] += 1ull;
          //-------------------------------------
          ++counter;
          if (counter == nextDigest)
          {
            clock_gettime (CLOCK_PROCESS_CPUTIME_ID,
                           (& (timeStop))           );
            timeElapsed += (((((std::uint64_t) timeStop.tv_sec) *
                              1000000000ull                      ) +
                             ((std::uint64_t) timeStop.tv_nsec)     )  -
                            ((((std::uint64_t) timeStart.tv_sec) *
                              1000000000ull                       ) +
                             ((std::uint64_t) timeStart.tv_nsec)     )  );
            hash.reset ();
            for (Iterator_t iterator = container.begin ();(iterator != container.end ());++iterator)
            {
              hash.addData (QByteArrayView (((char *) (& (* iterator))),
                                            sizeof (std::uint64_t)      ));
            }
            std::cout << QString::asprintf ("%'13llu",((unsigned long long) counter)).toStdString () << " "
                      << QString::asprintf ("%'23.9f",(((double) timeElapsed) /
                                                       1000000000.0            )).toStdString ()     << " "
                      << QString (hash.result ().toHex ()).toStdString ()                            << std::endl;
            if ((counter   <  rounds)            &&
                (timeLimit >  0ull)              &&
                (timeLimit <= (timeElapsed   /
                               1000000000ull  ))   )
            {
              do
              {
                counter *= 2ull;
                std::cout << QString::asprintf ("%'13llu",((unsigned long long) counter)).toStdString () << std::endl;
              }
              while (counter < rounds);
              break;
            }
            nextDigest <<= 1ull;
            clock_gettime (CLOCK_PROCESS_CPUTIME_ID,
                           (& (timeStart))          );
          }
        }
      }
      else
      {
        std::cout << "ERROR: cannot seek source file ('" << sourceFilename.toStdString () << "')" << std::endl;
        sourceFile.close ();
        return (EXIT_FAILURE);
      }
      sourceFile.close ();
    }
    else
    {
      std::cout << "ERROR: cannot open source file ('" << sourceFilename.toStdString () << "')" << std::endl;
      return (EXIT_FAILURE);
    }
    std::cout << std::endl;
  }
  return (EXIT_SUCCESS);
}
//*************************************************************************