class SortArray < Array
  attr_reader :log


  Log = Struct.new( :id, :x, :y )


  def initialize npoints
    super npoints
    @log = []
  end


  def []=( index, value )
    super index, value
    @log << Log.new( index, index, value )
  end
end


class Sort
  attr_reader :target


  def initialize npoints
    @target = SortArray.new( npoints )
    @target.each_index do | each |
      while( @target.include?( value = rand( npoints ) ) ) do; end
      @target[ each ] = value
    end
  end


  def swap i, j
    t = @target[ i ]
    @target[ i ] = @target[ j ]
    @target[ j ] = t
  end


  def partition left, right
    pivot = @target[ left ]
    pivot_idx = left

    ( ( left + 1 )..right ).each do | i |
      if @target[ i ] < pivot
        swap( pivot_idx, i )
        pivot_idx += 1
        swap( pivot_idx, i )
      end
    end
    return pivot_idx
  end


  def sort_log
    @target.log
  end
end


class MergeSort < Sort
  def sort
    @work = Array.new( @target.size / 2 + 1 )
    sort_internal 0, @target.size - 1
  end


  def sort_internal first, last
    if first < last
      middle = ( first + last ) / 2
      sort_internal first, middle
      sort_internal middle + 1, last
      p = 0
      first.upto( middle ) do | i |
        @work[ p ] = @target[ i ]
        p += 1
      end
      i = middle + 1
      j = 0
      k = first
      while i <= last && j < p
        if @work[ j ] <= @target[ i ]
          @target[ k ] = @work[ j ]
          k += 1
          j += 1
        else
          @target[ k ] = @target[ i ]
          k += 1
          i += 1
        end
      end
      while j < p
        @target[ k ] = @work[ j ]
        k += 1
        j += 1
      end
    end
  end
end


class HeapSort < Sort
  def sort
    n = @target.size

    ( n / 2 ).downto( 1 ) do | k |
      i = k
      x = @target[ i - 1 ]
      while ( j = 2 * i ) <= n
        if ( j < n && @target[ j - 1 ] < @target[ j ] )
          j += 1
        end
        if x >= @target[ j - 1 ]
          break
        end
        @target[ i - 1 ] = @target[ j - 1 ]
        i = j
      end
      @target[ i - 1 ] = x
    end

    while n > 1
      x = @target[ n - 1 ]
      @target[ n - 1 ] = @target[ 0 ]
      n -= 1
      i = 1
      while (j = 2 * i) <= n
        if j < n && @target[ j - 1 ] < @target[ j ]
          j += 1
        end
        if x >= @target[ j - 1 ]
          break
        end
        @target[ i - 1 ] = @target[ j - 1 ]
        i = j
      end
      @target[ i - 1 ] = x
    end
  end
end


class ShellSort < Sort
  def sort
    h = 13
    while( h < @target.size )
      h = 3 * h + 1
    end
    h /= 9

    while h > 0
      ( h..( @target.size - 1 ) ).each do | i |
        x = @target[ i ]
        j = i - h
        while( j >= 0 && @target[ j ] > x )
          @target[ j + h ] = @target[ j ]
          j -= h
        end
        @target[ j + h ] = x
      end
      h /= 3
    end
  end
end


class QuickSort < Sort
  def sort
    sort_internal 0, @target.size - 1
  end


  def sort_internal left, right
    if right - left >= 1
      pivot_idx = partition( left, right )
      sort_internal left, pivot_idx
      sort_internal pivot_idx + 1, right
    end
  end
end


class BubbleSort < Sort
  def sort
    @last_swap_index = @target.size - 1
    while @last_swap_index
      j = nil

      ( 1..@last_swap_index ).each do | i |
        if @target[ i - 1 ] > @target[ i ]
          j = i - 1
          swap i, j
        end
      end
      @last_swap_index = j
    end
  end
end


class SelectionSort < Sort
  def sort
    ( 0..( @target.size - 1 ) ).each do | each |
      min = @target[ each ]
      min_idx = each

      ( ( each + 1 )..( @target.size - 1 ) ).each do | j |
        if @target[ j ] < min
          min = @target[ j ]
          min_idx = j
        end

        @target[ min_idx ] = @target[ each ]
        @target[ each ] = min
        min_idx = each
      end
    end
  end
end


class InsertionSort < Sort
  def sort
    ( 1..( @target.size - 1 ) ).each do | i |
      pivot = @target[ i ]
      j = i - 1
      loop do
        break if j < 0
        break if @target[ j ] <= pivot
        @target[ j + 1 ] = @target[ j ]
        j -= 1
      end
      @target[ j + 1 ] = pivot
    end
  end
end


$npoints = 50
$oval_size = 10


Shoes.app :title => 'Sort Kun', :width => $npoints * $oval_size, :height => $npoints * $oval_size + 105, :resizable => false do
  @current_algorithm = 'insertion'


  def xpos x
    $oval_size * x
  end


  def ypos y
    $npoints * $oval_size - $oval_size * ( y + 1 )
  end


  def init
    @ovals = Array.new( $npoints )
    0.upto( $npoints - 1 ) do | each |
      @ovals[ each ] = oval( xpos( each ), ypos( each ), $oval_size, $oval_size )
    end
  end


  def start
    log_idx = $npoints

    @algorithm.sort
    @anim = animate( 10 ) do
      $npoints.times do
        log = @algorithm.sort_log[ log_idx ]
        if log
          @ovals[ log.id ].move xpos( log.x ), ypos( log.y )
          log_idx += 1
        end
      end
    end
  end


  def reset
    @anim.stop if @anim
    @algorithm.sort_log.each do | each |
      @ovals[ each.id ].move xpos( each.x ), ypos( each.y )
    end
  end


  def set_algorithm name
    @current_algorithm = name
    @algorithm = eval( @current_algorithm.capitalize + 'Sort' ).__send__( :new, $npoints )
    @label.replace strong( "#{ @current_algorithm.capitalize } Sort" )
  end


  stack :width => width, :height => 45 do
    background black
    @label = para strong( "#{ @current_algorithm.capitalize } Sort" ), :stroke => white, :align => 'center', :font => "Arial 30px"
  end

  stack :width => width, :height => $npoints * $oval_size do
    background "#DFA"
    nostroke

    init
    set_algorithm @current_algorithm
  end

  stack :width => width, :height => 30 do
    background '#FFF'
    para 'Select: ', link( 'bubble' ) { set_algorithm( 'bubble' ); reset; start }, ', ',
                     link( 'heap' ) { set_algorithm( 'heap' ); reset; start }, ', ',
                     link( 'insertion' ) { set_algorithm( 'insertion' ); reset; start }, ', ',
                     link( 'merge' ) { set_algorithm( 'merge' ); reset; start }, ', ',
                     link( 'quick' ) { set_algorithm( 'quick' ); reset; start }, ', ',
                     link( 'selection' ) { set_algorithm( 'selection' ); reset; start }, ', ',
                     link( 'shell' ) { set_algorithm( 'shell' ); reset; start }
  end

  stack :width => width, :height => 30 do
    background '#FFF'
    para link( 'reset' ) { reset; start }, :align => 'right'
  end
end