Demonstration of how to keep the product of a queue over a semigroup in amortized O(1) time

queue_prod.rb

#Demonstration of how to keep the product of a queue over a semigroup in amortized O(1) time

arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

inbox = []
inprod =[]
outbox = []
outprod = []


def enqueue_prod(inbox, inprod, elt)
  inbox.push(elt)
  if (inprod.size > 0)
    inprod.push(inprod.last.to_s + "x"+elt.to_s)
  else
    inprod.push(elt.to_s)
  end
end

def dequeue_prod(inbox, outbox, inprod, outprod)
  if (outbox.size <1)
    while inbox.size >0
      elt = inbox.pop
      inprod.pop
      outbox.push(elt)
      if (outprod.size >0)
        outprod.push(elt.to_s + "x" + outprod.last.to_s)
      else
        outprod.push(elt.to_s)
      end
    end
  end
  outbox.pop
  outprod.pop
end

enqueue_prod(inbox, inprod, arr.shift)
enqueue_prod(inbox, inprod, arr.shift)
enqueue_prod(inbox, inprod, arr.shift)
enqueue_prod(inbox, inprod, arr.shift)
enqueue_prod(inbox, inprod, arr.shift)

while (arr.size > 0)
  puts "\ninbox " + inbox.inspect
  puts "outbox " + outbox.inspect
  puts "inbox_product " + inprod.inspect
  puts "outbox_product " + outprod.inspect
  dequeue_prod(inbox, outbox, inprod, outprod)
  enqueue_prod(inbox, inprod, arr.shift)
  total_prod =""
  if (outprod.last != nil)
    total_prod = total_prod + outprod.last
  end
  if (inprod.last != nil)
    if(total_prod.length >0)
      total_prod = total_prod + "x"
    end
    total_prod = total_prod + inprod.last
  end
  puts "Queue product is "+ total_prod
end

#Expected output
#inbox [1, 2, 3, 4, 5]
#outbox []
#inbox_product ["1", "1x2", "1x2x3", "1x2x3x4", "1x2x3x4x5"]
#outbox_product []
#Queue product is 2x3x4x5x6
#
#inbox [6]
#outbox [5, 4, 3, 2]
#inbox_product ["6"]
#outbox_product ["5", "4x5", "3x4x5", "2x3x4x5"]
#Queue product is 3x4x5x6x7
#
#inbox [6, 7]
#outbox [5, 4, 3]
#inbox_product ["6", "6x7"]
#outbox_product ["5", "4x5", "3x4x5"]
#Queue product is 4x5x6x7x8
#
#inbox [6, 7, 8]
#outbox [5, 4]
#inbox_product ["6", "6x7", "6x7x8"]
#outbox_product ["5", "4x5"]
#Queue product is 5x6x7x8x9
#
#inbox [6, 7, 8, 9]
#outbox [5]
#inbox_product ["6", "6x7", "6x7x8", "6x7x8x9"]
#outbox_product ["5"]
#Queue product is 6x7x8x9x10