///////////////////////////////////////////////////////////////////
//                                                               //
//  Copyright (c) 2006, Martin Knoblauch                         //
//                                                               //
//  Permission is hereby granted, free of charge, to any person  //
//  obtaining a copy of this software and associated             //
//  documentation files (the "Software"), to deal in the         //
//  Software without restriction, including without limitation   //
//  the rights to use, copy, modify, merge, publish, distribute, //
//  sublicense, and/or sell copies of the Software, and to       //
//  permit persons to whom the Software is furnished to do so,   //
//  subject to the following conditions:                         //
//                                                               //
//  The above copyright notice and this permission notice shall  //
//  be included in all copies or substantial portions of the     //
//  Software.                                                    //
//                                                               //
//  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY    //
//  KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE   //
//  WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR      //
//  PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS   //
//  OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR     //
//  OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR   //
//  OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE    //
//  SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.       //
//                                                               //
///////////////////////////////////////////////////////////////////

/*
    AVL Array 1.0 performance test

    This program is part of a free software project hosted at:
    http://sourceforge.net/projects/avl-array

    The code listed here is just a rough test. It shows that
    AVL Arrays outperform vector and list UNDER VERY PARTICULAR
    CONDITIONS. AVL Arrays are the best choice in cases where
    _BOTH_ kinds of operations (random access and insert/erase at
    any point) are performed frequently in highly populated
    containers.

    Some results can be found at the end of this file.

    I'm a newbie on implementing STL-like templates, so if you
    see anything wrong here, have any suggestion, or decide to
    use AVL Arrays in something, please drop me some lines and
    tell me!  ;-)

                        October, 2006
                        Martin Knoblauch Revuelta
                        comocomocomo at users.sourceforge.net
*/

#include <list>
#include <vector>
#include <iostream>
#include <ctime>

#include "stlavlarray.h"

using namespace std;

// CONFIGURATION --------------------------------------------------

#define MAX_TIME 120U        // Max seconds per fill-flush cycle

#define INITIAL_SIZE 10000U  // Number of elements for the first
                             // fill-flush cycle. Lower values are
                             // interesting too, but current time
                             // resolution is 1 second, and
                             // frequent calls to time() might
                             // jeopardize the results so...

// HELPER FUNCTIONS -----------------------------------------------

unsigned random (unsigned max) // Return a random number
{                              // in the interval [0,max)
  unsigned n;                  // That is:
                               //  * greatter or equal to 0
  n = (unsigned)               //  * strictly lesser than max
      ( max *
        ( (double)rand() / RAND_MAX ) );

  return n>=max ? max-1 : n;
}

inline list<unsigned>::iterator operator+       // Provide a +
                 (list<unsigned>::iterator it,  // operator for
                  unsigned u)                   // iterators of
{                                               // std::list
  while (u--)
    ++ it;        // Advance u times

  return it;
}

// TESTING ALGORITHM ----------------------------------------------

template<class C,class I>      // The unused parameters enforce C
void test (C unused,           // and I to be the correct classes
           I unused_too,       // An explicit instantiation like
           const char * name)  // test<list...> () failed in some
{                                                // old compilers
  unsigned size, elapsed, start;
  unsigned i, pos, result;

  cout << endl << "Testing: " << name << endl     // Title and
       << "Size\tTime\tFinal element" << endl;    // table header

  size = INITIAL_SIZE;      // Start trying a 'little'
                            // amount of elements, grow it
  for (;;)                  // a 50% and try again... and so on
  {                         // until the time exceeds MAX_TIME
    cout << size << '\t';

    // START COUNTING TIME HERE ----------------vvvvvv-------------
    start = (unsigned) time (NULL);
    elapsed = 0;

    {                // Enclose container and iterator in a block
      C container;   // so that they are destroyed before we
      I it;          // stop counting time

      for (i=0; i<size && elapsed<MAX_TIME; i++) // Insert 'size'
      {                                          // elements in
        pos = random (i+1);                      // random
        it = container.begin() + pos;            // positions
        container.insert (it, rand());

        elapsed = (unsigned) time (NULL) - start;
      }

      if (i<size)                                // If maximum time
      {                                          // was reached,
        cout << '>' << elapsed                   // abort
             << "\tAborted ("
             << i*100/size << "% inserted)" << endl;

        break;
      }

      for (i=size; i>1 && elapsed<MAX_TIME; i--) // Extract 'size'-1
      {                                          // elements from
        pos = random (i);                        // random
        it = container.begin() + pos;            // positions
        container.erase (it);

        elapsed = (unsigned) time (NULL) - start;
      }

      if (i>1)                                   // If maximum time
      {                                          // was reached,
        cout << '>' << elapsed                   // abort
             << "\tAborted (100% inserted, "
             << i*100/size << "% removed)"
             << endl;
        break;
      }

      result = *container.begin();   // Store the result and
    }                                // destroy the container

    // STOP COUNTING TIME HERE ---------------^^^^^^---------------
    elapsed = (unsigned) time (NULL) - start;

    cout << elapsed << '\t'    // Show the result (just for
         << result             // verifying that all containers
         << endl;              // get the same one)

    size += size/2;            // Next time: 150% of current size
  }
}

// PROGRAM BODY ---------------------------------------------------

int main ()
{
  unsigned seed;
                                           // Make a random seed
  seed = (unsigned) time (NULL);           // with the current time
  cout << "Random seed: " << seed << endl;

  srand (seed);
  test (list<unsigned>(),
        list<unsigned>::iterator(),
        "list<unsigned>");
                                           // Test every container
  srand (seed);                            // with the same random
  test (vector<unsigned>(),                // sequence
        vector<unsigned>::iterator(),
        "vector<unsigned>");

  srand (seed);
  test (avl_array<unsigned>(),
        avl_array<unsigned>::iterator(),
        "avl_array<unsigned>");

  getchar ();    // Wait until the user presses ENTER
  return 0;
}

/*
-------------------------------------------------------------------

    Results obtained with:

      - Compiler: Dev-C++ 4.9.9.0
        (Project configured for best optimizations and no debug)
      - Processor: Pentium 4 Mobile runnig at 1.59 GHz
      - RAM: 512 MB
      - MAX_TIME: 120 seconds
      - INITIAL_SIZE: 10000 elements


Random seed: 1161255263

Testing: list<unsigned>
Size    Time    Final element
10000   2       17726
15000   3       7751
22500   8       31105
33750   30      22881
50625   >120    Aborted (100% inserted, 42% removed)

Testing: vector<unsigned>
Size    Time    Final element
10000   0       17726
15000   0       7751
22500   1       31105
33750   1       22881
50625   3       19482
75937   7       17297
113905  16      24626
170857  43      9936
256285  >120    Aborted (100% inserted, 69% removed)

Testing: avl_array<unsigned>
Size    Time    Final element
10000   0       17726
15000   0       7751
22500   0       31105
33750   0       22881
50625   1       19482
75937   0       17297
113905  2       24626
170857  2       9936
256285  4       19218
384427  6       14219
576640  10      31187
864960  16      28103
1297440 25      18557
1946160 42      23947
2919240 68      2762
4378860 110     24869
6568290 >120    Aborted (100% inserted, 65% removed)
-------------------------------------------------------------------
*/