# C/C++ 로 배우는 자료구조론 연습문제 7.33

class CircularQueue

  def initialize(size)
    @memory = []
    @front = 0
    @rear = 0

    @queue_size = size
  end

  def is_empty
    return @front == @rear
  end

  def is_full
    return ((@rear + 1) % @queue_size) == @front
  end

  def enqueue(data)
    return nil if is_full

    @rear = (@rear + 1) % @queue_size
    @memory[@rear] = data
  end

  def dequeue
    return nil if is_empty
    
    @front = (@front + 1) % @queue_size
    return @memory[@front]
  end

  def size
    if @rear > @front
      return @rear - @front
    elsif @rear == @front
      return 0
    else
      return @rear + @queue_size - @front
    end
  end
end

def print_josephus_problem_survive_index(person_count, execute_interval)
  queue = CircularQueue.new(person_count + 1)

  (1..person_count).each { |i| queue.enqueue i }

  while queue.size >= execute_interval 
    (execute_interval - 1).times do 
	  person = queue.dequeue
	  queue.enqueue person
	end
	
	puts "Executed : " + queue.dequeue.to_s
	
  end

  until queue.is_empty
    puts "Survived : " + queue.dequeue.to_s
  end
end

print_josephus_problem_survive_index(41, 3)

Executed : 3
Executed : 6
Executed : 9
Executed : 12
Executed : 15
Executed : 18
Executed : 21
Executed : 24
Executed : 27
Executed : 30
Executed : 33
Executed : 36
Executed : 39
Executed : 1
Executed : 5
Executed : 10
Executed : 14
Executed : 19
Executed : 23
Executed : 28
Executed : 32
Executed : 37
Executed : 41
Executed : 7
Executed : 13
Executed : 20
Executed : 26
Executed : 34
Executed : 40
Executed : 8
Executed : 17
Executed : 29
Executed : 38
Executed : 11
Executed : 25
Executed : 2
Executed : 22
Executed : 4
Executed : 35
Survived : 16
Survived : 31