#!/usr/bin/eval ruby

require 'set'

class JBBBinaryHeap
    def initialize(isMaxHeap = false)
        @mStorage = []
        @mCompareProc = (isMaxHeap) ? lambda { |x, y| x < y } : lambda { |x, y| x > y }
    end

    def add(objectToAdd)
        @mStorage.push(nil)
        lastIndex = @mStorage.length - 1
        while (lastIndex > 0)
            parent = (lastIndex - 1) / 2
            parentNode = @mStorage[parent]
            break if (@mCompareProc.call(objectToAdd, parentNode))
            @mStorage[lastIndex] = parentNode
            lastIndex = parent
        end
        @mStorage[lastIndex] = objectToAdd
    end

    def remove
        returnNode = @mStorage[0]
        lastNode = @mStorage.pop
        shiftDown(0, lastNode)
        return returnNode
    end

    def min
        return @mStorage[0]
    end

    def shiftDown(index, objectToShift)
        return if @mStorage.empty?

        while (index < (@mStorage.size / 2))
            child = (2 * index) + 1
        
            child += 1 if ((child < (@mStorage.size - 1)) and @mCompareProc.call(@mStorage[child], @mStorage[child + 1]))

            break unless (@mCompareProc.call(objectToShift, @mStorage[child]))

            @mStorage[index] = @mStorage[child]
            index = child
        end
        @mStorage[index] = objectToShift
    end

    def size
        return @mStorage.size
    end
    alias length size

    def empty?
        return @mStorage.empty?
    end

    def to_s
        return @mStorage.to_s
    end
end

class JBBPQueue
    def initialize(isMaxQueue = false)
        @mObjs = JBBBinaryHeap.new(isMaxQueue)
        @mObjsArray = []
        @mHeapified = false
    end

    def buildHeap
        return if (@mHeapified)

        @mObjsArray.each { |item| @mObjs.add(item) }
        @mObjsArray.clear
        @mHeapified = true
    end

    def push(objectToAdd)
        if (@mHeapified)
            @mObjs.add(objectToAdd)
        else
            @mObjsArray.push(objectToAdd)
        end
    end

    def pushObjects(objectsToAdd = [])
        @mHeapified = false

        @mObjsArray += objectsToAdd
    end

    def pop
        return nil if empty?

        buildHeap

        return @mObjs.remove
    end

    def size
        return @mObjs.size + @mObjsArray.size
    end

    def empty?
        return (size == 0)
    end

    def to_s
        buildHeap

        return @mObjs.to_s
    end
end

class String
    def swap(first, second)
        self.dup.swap!(first, second)
    end
    
    def swap!(first, second)
        self[first], self[second] = self[second], self[first]
        return self
    end
    
    def altSwap(first, second)
        self.dup.altSwap!(first, second)
    end
    
    def altSwap!(first, second)
        temp_store = self[first]
        self[first] = self[second]
        self[second] = temp_store
        return self
    end
end

class JBBNode
    include Comparable
    
    attr_reader :priority
    attr_reader :level
    
    def initialize(priority = 0)
        @priority = priority
        @level = rand(5)
        $globalCounter += 1
    end
    
    def children
        (1..5).collect { |offset|
            newPriority = @priority + offset
            JBBNode.new(newPriority) unless $globalSet.include?(newPriority)
        }.compact
    end
    
    def <=>(rhs)
        return -1 if @level < rhs.level
        return 1 if @level > rhs.level
        return @priority <=> rhs.priority
    end
end

$tempTime = Time.new

# first test
puts
puts("Test 001 -- String character swap, 2500000 times")


$staticString = "asdfghjkl;123456789"
$firstTime = 0.0
$secondTime = Time.new
2500000.times {
    randOne = rand($staticString.length)
    randTwo = rand($staticString.length)
    $tempTime = Time.new
    newString = $staticString.swap(randOne, randTwo)
    $firstTime += Time.new - $tempTime
}
$secondTime = Time.new - $secondTime

puts("Test 001: %.4f seconds" % [$firstTime])
puts("Overall: %.4f seconds" % [$secondTime])
puts

# second test
puts
puts("Test 002 -- String character swap (alternate), 2500000 times")

$firstTime = 0.0
$secondTime = Time.new
2500000.times {
    randOne = rand($staticString.length)
    randTwo = rand($staticString.length)
    $tempTime = Time.new
    newString = $staticString.altSwap(randOne, randTwo)
    $firstTime += Time.new - $tempTime
}
$secondTime = Time.new - $secondTime

puts("Test 002: %.4f seconds" % [$firstTime])
puts("Overall: %.4f seconds" % [$secondTime])
puts

# third and fourth tests
puts
puts("Test 003 and 004 -- Insert 500000 nodes into a priority queue using pop/push (003), plus Set calls (004)")

$globalSet = Set.new
$globalQueue = JBBPQueue.new
$globalCounter = 0

$firstTime = 0.0
$secondTime = 0.0
$thirdTime = Time.new

$tempTime = Time.new
$globalQueue.push(JBBNode.new)
$firstTime += Time.new - $tempTime

while (searchNode = $globalQueue.pop())
    $firstTime += Time.new - $tempTime
    
    break unless ($globalCounter <= 500000)
    
    $tempTime = Time.new
    if ($globalSet.include?(searchNode.priority))
        $secondTime += Time.new - $tempTime
        next
    else
        $secondTime += Time.new - $tempTime
    end
    
    $tempTime = Time.new
    $globalSet.add(searchNode.priority)
    $secondTime += Time.new - $tempTime
    searchNode.children.each { |item|
        $tempTime = Time.new
        $globalQueue.push(item)
        $firstTime += Time.new - $tempTime
    }
end
$thirdTime = Time.new - $thirdTime

puts("Test 003: %.4f seconds" % [$firstTime])
puts("Test 004: %.4f seconds" % [$secondTime])
puts("Overall: %.4f seconds" % [$thirdTime])
puts

# fifth and sixth tests
puts
puts("Test 005 and 006 -- Insert 500000 nodes into a priority queue using pop/pushObjects (005), plus Set calls (006)")

$globalSet = Set.new
$globalQueue = JBBPQueue.new
$globalCounter = 0

$firstTime = 0.0
$secondTime = 0.0
$thirdTime = Time.new

$tempTime = Time.new
$globalQueue.push(JBBNode.new)
$firstTime += Time.new - $tempTime

while (searchNode = $globalQueue.pop())
    $firstTime += Time.new - $tempTime
    
    break unless ($globalCounter <= 500000)
    
    $tempTime = Time.new
    if ($globalSet.include?(searchNode.priority))
        $secondTime += Time.new - $tempTime
        next
    else
        $secondTime += Time.new - $tempTime
    end
    
    $tempTime = Time.new
    $globalSet.add(searchNode.priority)
    $secondTime += Time.new - $tempTime
    
    $tempTime = Time.new
    $globalQueue.pushObjects(searchNode.children)
    $firstTime += Time.new - $tempTime
end
$thirdTime = Time.new - $thirdTime

puts("Test 005: %.4f seconds" % [$firstTime])
puts("Test 006: %.4f seconds" % [$secondTime])
puts("Overall: %.4f seconds" % [$thirdTime])
puts