/***************************************************************************
 *   Copyright (C) 2007 by Manuel Holtgrewe                                *
 *   holtgrewe@ira.uka.de                                                  *
 *   Distributed under the Boost Software License, Version 1.0.            *
 *   (See accompanying file LICENSE_1_0.txt or copy at                     *
 *   http://www.boost.org/LICENSE_1_0.txt)                                 *
 ***************************************************************************/

#include <algorithm>
#include <meta/mcstl_timing.h>
#include <omp.h>

mcstl::Timing<mcstl::active_tag> timer;

int benchmark = false;

/* OpenMP Parallel Counting Sort
 *
 * A simple implementation of a parallel counting sort algorithm.
 *
 * The bucket filling and final result sorting have been parallelized. Copying
 * back the sorted elements into the input iterators is done using std::copy
 * which is already parallelized in the MCSTL.
 *
 * See:
 *  - http://de.wikipedia.org/wiki/Countingsort
 *  - http://www.umiacs.umd.edu/research/EXPAR/papers/3548/node8.html
 *
 * Measurements on a dual CPU, dual core Intel Xeon with 2.4Ghz yielded no speedup
 * with more than 2 threads, speed broke down, possibly because of the very simple
 * algorithm becoming memory bound (GCC 4.2). Results were the same on a 4 core
 * AMD Opteron system. These results hold for array sizes of up to 2**28 (filling
 * 2 GB of RAM on a 64bit machine leaving enough room for the buffer and the OS).
 *
 * See ExperimentalResults.txt.
 *
 * Parameters
 *
 * Sorts elements [begin, end) "in place". The elements must be in the range of
 * [0, max_key].
 */
template <typename RandomIterator, typename HashFunctor>
void counting_sort(RandomIterator *begin, RandomIterator *end, int max_key, HashFunctor hash)
{
	if (benchmark) timer.tic("start");
	
	assert(max_key >= 0);
	
	// number of threads and number of elements to use
	int num_threads = mcstl::HEURISTIC::num_threads;
	int n = end - begin;
	assert(n >= 0);
	
	// *********** STEP 1: COUNTING ***********
	// result of this step: local rank bases
	
	// create one counter array for each thread
	int **thread_counters = new int* [num_threads];
	for (int i = 0; i < num_threads; i++)
		thread_counters[i] = new int[max_key + 1];
	if (benchmark) timer.tic("counting initialization           ");
	
	// count occurences
	int *split_positions = mcstl::equal_splitting(n, num_threads);
	#pragma omp parallel num_threads(num_threads)
	{
		int iam = omp_get_thread_num();
		int *&c = thread_counters[iam];
		
		// reset counters
		for (int i = 0; i <= max_key; i++)
			c[i] = 0;
		
		// count occurences
		for (int i = split_positions[iam]; i < split_positions[iam + 1]; i++)
		{
			c[hash(begin[i])]++;
		}
	}
	if (benchmark) timer.tic("counting & local prefix sums      ");
	
	// Compute global prefix sums / ranks from local ones. We *could*
	// make this parallel, too, but there are only num_threads * (max_key + 1)
	// entries in total.
	for (int i = 0, sum = 0; i <= max_key; i++)
		{
			for (int j = 0; j < num_threads; j++)
				{
					int t = thread_counters[j][i];
					thread_counters[j][i] = sum;
					sum += t;
				}
		}
	if (benchmark) timer.tic("global ranks (prefix sums)        ");
	
	// *********** STEP 2: SORTING ***********
	
	int *buffer = new int[n]; // backbuffer, copied back to input later
	
	// write sorted result to backbuffer
	#pragma omp parallel num_threads(num_threads)
	{
		int iam = omp_get_thread_num();
		int *&c = thread_counters[iam];
		
		for (int i = split_positions[iam]; i < split_positions[iam + 1]; i++)
			{
				assert(hash(begin[i]) <= max_key);
				buffer[c[hash(begin[i])]++] = begin[i];
			}
	}	
	if (benchmark) timer.tic("sorting into backbuffer           ");
	
	// write result from buffer back into input
	std::copy(buffer, buffer + n, begin);
	
	if (benchmark) timer.tic("copying back into input           ");
	
	// cleanup
	delete [] buffer;

	for (int i = 0; i < num_threads; i++)
		delete [] thread_counters[i];
	delete [] thread_counters;

	delete [] split_positions;
	if (benchmark) timer.tic("cleanup                           ");
}

# =============================================================================
# Purpose: Refactored TestCase for simple Rails ActiveRecord::Base and 
#          ActiveForm classes.
# Author:  Manuel Holtgrewe <purestorm at ggnore dot net>
# License: Public Domain
#
# Feel free to flesh out the tests further and make it a more poweful library.
# Drop me a line if you find the module useful or if you created something more
# powerful on top of it.
# =============================================================================
#
# Include this module in your test classes. Then, you define some valid data,
# the model class to test and some "patches" to the valid data to make it invalid.
#
# Sure, this will only work for very simple models but you want to spend as few
# time on those as possible, right?
#
# Assuming you have the following model:
#
#   class MyModel < ActiveRecord::Base
#     validates_length_of :title, :in => 10..100
#     validates_numericality_of :number
#   end
#
# You can then write the following TestCase:
#
#  class MyModelTest < Test::Unit::TestCase
#    include SimpleMethodTests # The basic tests are defined in this module.
#
#    fixtures :my_models
#
#    def setup
#      @model_class = MyModel
#      @valid_data = { :title => 'Abracabra!', :number => 10 }
#      @invalid_patches =
#        [
#          [ :title, nil ], [ :title, 'a' * 9 ], [ :title, 'a' * 101 ],
#          [ :number, nil ], [ :number, 'a' ], [ :title, '123a' ],
#        ]
#    end
#
#    def test_a_nonbasic_test
#      flunk, "Wheee!"
#    end
#
#    # Overwrite a test from the mixin.
#    def test_valid_should_return_false_and_add_errors_with_invalid_data
#      assert true, "Removing this test!"
#    end
#  end
#
# You can both test ActiveRecord::Base and ActiveForm classes (CRUD is not tested
# on ActiveForm classes). If you test ActiveRecord::Base classes then you have to
# provide at least one fixture.
module SimpleModelTests
  def test_valid_should_return_true_with_valid_data
    # Do not use Model.new(attributes) since some might be marked as protected.
    model = @model_class.new
    @valid_data.each { |key, value| model.send("#{key}=".to_sym, value) }

    assert model.valid?
    assert_equal 0, model.errors.count
  end
  
  def test_valid_should_return_false_and_add_errors_with_invalid_data
    @invalid_patches.each do |key, value|
      invalid_data = @valid_data.dup
      invalid_data[key] = value
    
      # Do not use Model.new(attributes) since some might be marked as protected.
      model = @model_class.new
      invalid_data.each { |invalid_key, invalid_value| model.send("#{invalid_key}=".to_sym, invalid_value) }

      assert !model.valid?, "invalid_data[#{key.inspect}] == #{value.inspect}, errors: #{model.errors.full_messages.join('; ')}"
      
      # If the property we set was a foreign key named NAME_id then the error 
      # gets added to the property NAME of the object if the object is an
      # ActiveRecord::Base object.
      if key.to_s =~ /^(.*)_id$/ and model.respond_to?($1.to_sym) then
        assert_not_nil model.errors.on($1.to_sym), "invalid_data[#{$1.to_sym.inspect}] == #{value.inspect}"
      else
        assert_not_nil model.errors.on(key), "invalid_data[#{key.inspect}] == #{value.inspect}"
      end
    end
  end
  
  def test_create_should_work_correctly
    # We only want to test this if we test an ActiveRecord::Base class.
    return if not @model_class.new.respond_to?(:save)
    
    old_count = @model_class.count
    
    # Do not use Model.new(attributes) since some might be marked as protected.
    model = @model_class.new
    @valid_data.each { |key, value| model.send("#{key}=".to_sym, value) }
    
    assert model.save, "errors: #{model.errors.full_messages.join('; ')}"
    assert model.reload
    
    assert_equal old_count+1, @model_class.count
  end
  
  def test_update_should_work_correctly
    # We only want to test update if the model objects have a method "save".
    return if not @model_class.new.respond_to?(:update)
    
    # We assume that there is at least one valid record in the database with
    # different data than the @valid_data you specified above.
    #
    # We order by id to make the result predictable.
    model = @model_class.find(:first, :order => 'id ASC')
    
    @valid_data.each { |key, value| model.send("#{key}=".to_sym, value) }
  
    assert model.save, "errors: #{model.errors.full_messages.join('; ')}"
    assert model.reload
    
    @valid_data.each do |key, value|
      case value
      when Float then
        assert_in_delta value, model.send(key), 0.01
      else
        assert_equal value, model.send(key)
      end
    end
  end
  
  def test_destroy_should_work_correctly
    # We only want to test this if we test an ActiveRecord::Base class.
    return if not @model_class.new.respond_to?(:destroy)
    
    old_count = @model_class.count
    
    model = @model_class.find(:first)
    
    id = model.id
    
    model.destroy
    
    assert_raises(ActiveRecord::RecordNotFound) { @model_class.find(id) }
    
    assert_equal old_count-1, @model_class.count
  end
end

class Array
  # Returns the "power set" for this Array. This means that an array with all
  # subsets of the array's elements will be returned.
  def power
    # the power set line is stolen from http://johncarrino.net/blog/2006/08/11/powerset-in-ruby/
    inject([[]]){|c,y|r=[];c.each{|i|r<<i;r<<i+[y]};r}
  end
end

openssl s_client -connect ${URL}:${PORT}

openssl s_client -connect checkout.google.com:443