=begin
def quicksort list
  return [] if list.empty?
  return quicksort(list.select {|x| x < list.first}) + list.select {|x| x == list.first} + quicksort(list.select {|x| x > list.first})
end

puts quicksort([0,1,2,3,4,5,6,7,8].shuffle).inspect
exit 0
=end

require 'test/unit/assertions'
include Test::Unit::Assertions
require 'logger'

# Idea from http://blog.interlinked.org/programming/rfuture.html
class Future
  def initialize(&block)
    @thread = Thread.new do @result = block.call end

    for m in methods
      next if (RUBY_VERSION.start_with? "1.8" and ['__send__', '__id__', '__future_value__', 'method_missing'].include? m) or
              (RUBY_VERSION.start_with? "1.9" and [:__send__,  :object_id,  :__future_value__,  :method_missing ].include? m)
      metaclass = class << self; self; end # don't try to understand it
      metaclass.send(:define_method, m) do |*args|
        __future_value__.__send__(m, *args)
      end
    end
  end

  def method_missing(method_id, *args)
    __future_value__.__send__(method_id, *args)
  end

  def __future_value__
    @thread.join
    @result
  end
end

config = {
  :thread_threshold => 20,
  :log_enter_method => true,
  :log_leave_method => true,
  :logger => Logger.new(STDERR),
  :log_future_fork => true,
  :log_nofuture_fork => true,
  :log_optimization => true,
  :log_cache => true
}

class Cache
  def set_cache_size_for method, count
    @cache_size[method] = count
  end
  def update_cache_for method, param, result
    @cache ||= {}
    @cache[method] ||= {}
    r2 = @cache[method][param] ||= result
    assert_equal r2, result, "Cache: same parameter produces different result"
    # TODO delete cache
    return result
  end
  def has_cache_for? method, param
    @cache ||= {}
    @cache[method] ||= {}
    return (not @cache[method][param].nil?)
  end
  def cached_value_for method, param
    @cache ||= {}
    @cache[method] ||= {}
    return @cache[method][param].nil?
  end
end

# Sort recursive
#
# Using first Element as pivot
# Preserve ordering
# for max 300 elements
# Cache last Items
#
# Open Issues:
# * Enumerable has no empty? method
#
# Open Tasks:
# * use Enumeration#partition method for performance
#
# Parameters:
#   list of type Enumerable
# Result:
#   sorted Array
def quicksort list, config
  config[:logger].debug "Entering quicksort(#{list.inspect})" if config[:log_enter_method]
  assert list.kind_of?(Enumerable), "need Enumerable as Parameter"
  raise :to_many_elements if list.count > 300

  return []   if list.empty?     # FIXME Enumerable hast no empty? method
  return list if list.count == 1 # Enumerable uses count!

  if has_cache_for? :quicksort, list
    config[:logger].debug "return value from cache" if config[:log_cache]
    return cached_value_for :quicksort, list
  end

  result = nil
  if list.size < 5 # saves recursion overhead
    config[:logger].info "optimize sort for #{list.size} elements" if config[:log_optimization]
    result = list.sort
  else
    less = more = nil
    if list.size > 50 # only fork threads if it is enough work to do
      config[:logger].info "creating future for #{list.size} elements" if config[:log_future_fork]
      less = Future.new do quicksort(list.select {|x| x < list.first}, config) end
      more = Future.new do quicksort(list.select {|x| x > list.first}, config) end
    else
      config[:logger].info "creating no future for #{list.size} elements" if config[:log_nofuture_fork]
      # TODO use Enumeration#partition method for performance
      less = quicksort(list.select {|x| x < list.first}, config)
      more = quicksort(list.select {|x| x > list.first}, config)
    end
    pivot = list.select {|x| x == list.first}
    result = less + pivot + more
  end

  assert result.count == list.count, "result has less items than input"
  assert result.kind_of?(Array), "result must be an Array"
  assert result.sort == result, "result must be sorted"

  config[:logger].debug "Leaving quicksort(#{result.inspect})" if config[:log_leave_method]
  update_cache_for :update, list, result
  return result
end

l = (1..200).to_a.shuffle
set_cache_size_for :quicksort, 300
puts quicksort(l, config).inspect