From: John W Higgins <wishdev@...>
Date: 2009-10-03T03:02:57+09:00
Subject: Re: Control of Priority Queue Order? And size limits on queues?

--0016362838e696caa70474f792d6
Content-Type: text/plain; charset=ISO-8859-1

Mason,

On Wed, Sep 30, 2009 at 1:50 PM, Mason Kelsey <masonkelsey@gmail.com> wrote:

> I've successfully used the Priority Queue to sort ascending items for
> solving the 8-puzzle problem.  I noticed that the Priority Queue method had
> a unique way of sorting items with matching keys.  It puts the newest items
> furtherest from the top.  The older a matching item is, the further it is
> towards the top.   That is OK by me as it essentially added a negative g(n)
> node value to the h(n) heuristic value that aided in the A* best-first
> algorithm.  If the newest matching item had been added at the top, it would
> have slowed the program down by going down fruitless paths and
> probably would create a less optimal path to the results.
>
> The code I used was: open_queue = PQueue.new(proc{|x,y| x[0]<y[0]}), where
> I
> was sorting on the first element of each item.
>
> But for future use, is there a way to force the Priority Queue to always
> add
> the newest matching item in front of the older matching items?  Please be
> aware I am not asking for a descending sort, which I know how to do.
>


You will need to change the matching process to be smart enough to handle
what you want - fortunately it's fairly easy to do with a couple of changes.
You can do something along either of the following (gist here for easier
reading - http://gist.github.com/199934)

In essence we just create a class to hold your items that is aware of how
you want to sort - you can either subclass
an array if you want to keep that concept or dump the array and move your
records to their own class.


require 'pqueue'

pq = PQueue.new proc{|x, y| x.compare(y)}

#Do either the Array monkey_patch or Record concept

class Array
  attr_reader :insert_time
  def compare(other_record)
    #We want to return TRUE if this record should take
    #priority over the other record in the queue
    if self[0] == other_record[0]
      insert_time > other_record.insert_time
    else
      self[0] < other_record[0]
    end
  end

  def queue(pq)
    @insert_time = Time.now()
    pq.push(self)
  end
end

x = [1, 2, 3, 4]
x.queue(pq)
sleep 1
y = [1, 2, 3, 4]
y.queue(pq)

until pq.empty?
  itm = pq.pop
  p itm
  p itm.insert_time
end

class Record
  attr_accessor :f1, :f2, :f3, :f4
  attr_reader :insert_time

  def initialize(f1, f2, f3, f4)
    @f1, @f2, @f3, @f4 = f1, f2, f3, f4
  end

  def compare(other_record)
    #We want to return TRUE if this record should take
    #priority over the other record in the queue
    if f1 == other_record.f1
      insert_time > other_record.insert_time
    else
      f1 < other_record.f1
    end
  end

  def queue(pq)
    @insert_time = Time.now()
    pq.push(self)
  end
end

x = Record.new(1, 2, 3, 4)
x.queue(pq)
sleep 1
y = Record.new(1, 5, 6, 7)
y.queue(pq)

until pq.empty?
  p pq.pop
end


John

--0016362838e696caa70474f792d6--