// Copyright (C) 2003 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library.  This library 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, 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
// GNU General Public License for more details.

// You should have received a copy of the GNU General Public License along
// with this library; see the file COPYING.  If not, write to the Free
// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
// USA.

// As a special exception, you may use this file as part of a free software
// library without restriction.  Specifically, if other files instantiate
// templates or use macros or inline functions from this file, or you compile
// this file and link it with other files to produce an executable, this
// file does not by itself cause the resulting executable to be covered by
// the GNU General Public License.  This exception does not however
// invalidate any other reasons why the executable file might be covered by
// the GNU General Public License.

#include <cmath>
#include <cstdlib>

#include <vector>
#include <algorithm>
#include <list>
#include <deque>
#include <set>

#include <sstream>
#include <testsuite_performance.h>

using namespace std;

typedef double element_t;
typedef void(*test)(element_t*, element_t*);

void array_test(element_t* first, element_t* last)
{
  element_t* array = new element_t[last - first];
  copy(first, last, array);
  sort(array, array + (last - first));
  unique(array, array + (last - first));
  delete [] array;	  
}

void vector_pointer_test(element_t* first, element_t* last)
{ 
  vector<element_t> container(first, last);
  sort(&*container.begin(), &*container.end());
  unique(&*container.begin(), &*container.end());
}

void vector_iterator_test(element_t* first, element_t* last)
{
  vector<element_t> container(first, last);
  sort(container.begin(), container.end());
  unique(container.begin(), container.end());
}

void deque_test(element_t* first, element_t* last)
{  
  deque<element_t> container(first, last);
  copy(first, last, container.begin()); 
  sort(container.begin(), container.end());
  unique(container.begin(), container.end());
}
    
void list_test(element_t* first, element_t* last)
{ 
  list<element_t> container(first, last);
  container.sort();
  container.unique();
}
 
void set_test(element_t* first, element_t* last)
{ set<element_t> container(first, last); }

void multiset_test(element_t* first, element_t* last)
{
  multiset<element_t> container(first, last);
  typedef multiset<element_t>::iterator iterator;
  {
    iterator first = container.begin();
    iterator last = container.end();
    
    while (first != last)
      {
	iterator next = first;
	if (++next == last) break;
	if (*first == *next)
	  container.erase(next);
	else
	  ++first;
      }
  }
}

double logtwo(double x)
{ return log(x)/log(2.0); }

int number_of_tests(int size)
{
  const double n = size;
  const double largest_n = 1000000;
  return int(floor((largest_n * logtwo(largest_n))
		   / (n * logtwo(n))));
}

void initialize(element_t* first, element_t* last)
{
  element_t value = 0.0;
  while (first != last)
    {
      *first++ = value;
      value += 1.;
    }
}

void run_tests(int size, const test* tests, const char** names,
	       int ntests)
{
  using namespace __gnu_test;
  time_counter time;
  resource_counter resource;

  const int n = number_of_tests(size);
  const size_t length = 2 * size;

  // make a random test set of the chosen size:
  vector<element_t> buf(length);
  element_t* buffer = &buf[0];
  element_t* buffer_end = &buf[length];
  initialize(buffer, buffer + size);	 // elements
  initialize(buffer + size, buffer_end); // duplicate elements
  random_shuffle(buffer, buffer_end);

  // test the containers:
  ostringstream oss;
  oss << "size = " << size << " :";
  report_header(__FILE__, oss.str());
  for (int i = 0; i < ntests; ++i)
    {
      start_counters(time, resource);
      for (int j = 0; j < n; ++j)
	tests[i](buffer, buffer_end);
      stop_counters(time, resource);
      report_performance(__FILE__, names[i], time, resource);
      clear_counters(time, resource);
    }
}

int main()
{
  const test tests[] = { &array_test, &vector_pointer_test,
			 &vector_iterator_test, &deque_test,
			 &list_test, &set_test, &multiset_test };
  const int ntests = sizeof(tests) / sizeof(test);
  const char* names[ntests] = { "array", "vector (pointer)",
				"vector (iterator)", "deque",
				"list", "set", "multiset" };

  const int sizes[] = {100, 1000, 10000, 100000};
  for (int i = 0; i < sizeof(sizes) / sizeof(int); ++i)
    run_tests(sizes[i], tests, names, ntests);

  return 0;
}