Multi-Dimensional Arrays in Priority Queues

Ruby
1

In my program I need to construct a priority queue that sorts ascending.
The basic idea can be expressed in the following simple code that uses a
Priority Queue concept. See:
http://www.math.kobe-u.ac.jp/~kodama/tips-ruby-pqueue.html

1 require “pqueue”
2
3 pq=PQueue.new(proc{|x,y| x<y})
4 pq.push(2)
5 pq.push(3)
6 pq.push(4)
7 pq.push(3)
8 pq.push(2)
9 pq.push(4)
10 print “size:”+pq.size.to_s+“\n”
11 print “each_pop: "
12 pq.each_pop{|x| print x.to_s+” "}
13 print “\n”

This is clean and simple to understand. But I need to be able to put
into
the queue several components per push to make an entire record object.
I
need to have three components: an integer heuristic value, followed by
two 9
digit configuration patterns, such as
pq.push([2], [123456780], [123456708]) But this gives me an argument
error
message:
pqueue.rb:4:in `push’: wrong number of arguments (3 for 1)
(ArgumentError) from pqueue.rb:4

or pq.push(2_123456780_123456708) ignores the underscore separators and
runs
the 3 parts together as one long number.

Still learning Ruby and none of the books address multiple dimensional
arrays very well. Is the Priority Queue not able to handle
multi-dimensional arrays? Can this code be modified to allow
multi-elements
in each push and still sort on the first element?

If I cannot use pqueue, is there another required library of methods
that
will work with three elements in each array entry?

Thanks in advance to those of you who can help. And thanks to all who
help
out on this forum. Very good forum.

No Sam

2

Hi,
In the line:

pq.push([2], [123456780], [123456708])

you’re not passing in a multi-dimensional array, you’re passing 3
parameters
each of which is an array. Try with:

pq.push([[2], [123456780], [123456708]])

(notice the double [ at the beginning and the double ] at the end).

you will also have to change your PQueue creation to something like
this:

pq=PQueue.new(proc{|x,y| x[0]<y[0]})

Haven’t tested this in irb but it (or something very much like it)
should
work.

-Mario.

–
I want to change the world but they won’t give me the source code.

3

Tried it but it didn’t work. Made the following change:

require “pqueue”
pq=PQueue.new(proc{|x,y| x[0]<y[0]})
pq.push([[12], [123456780], [123456708]])
pq.push([[23], [123456780], [123456708]])
pq.push([[4], [123456780], [123456708]])
pq.push([[33], [123456780], [123456708]])
pq.push([[02], [123456780], [123456708]])
pq.push([[54], [123456780], [123456708]])
print “size:”+pq.size.to_s+"\n"
print “each_pop: "
pq.each_pop{|x| print x.to_s+” "}
print “\n”
I got the messages:

ruby simple_pqueue.rb
simple_pqueue.rb:3: undefined local variable or method x' for main:Object (NameError) from ./pqueue.rb:24:in[]’
from ./pqueue.rb:24:in upheap' from ./pqueue.rb:65:inpush’
from simple_pqueue.rb:5
Exit code: 1

The “from” error messages appear to be coming from the code inside of
the
pqueue class methods.

Doesn’t like the brackets. I tried several variations of this and also
got
a message that said the < is an invalid method. Very strange. Sorry
but
I’m totally confused here.

There must be a way to do this.

No Sam

4

On Sep 20, 10:25 pm, Mason K. [email protected] wrote:

In my program I need to construct a priority queue that sorts ascending.
The basic idea can be expressed in the following simple code that uses a
Priority Queue concept. See:priority queue for Ruby(Kodama's tips page)

First, you may want to try the latest version of this class. I had it
in Facets for some time and it has been improved over the years.
Recently though, I made it it’s own project. You should be able to get
it via ‘gem install pqueue’.

1 require “pqueue”
2
3 pq=PQueue.new(proc{|x,y| x<y})

Is this supposed to be a proc and not a block? I think maybe you are
adding a proc to the queue (?). Try

pq=PQueue.new{|x,y| x<y}

Though maybe this is a difference between old and new version.

pq.push([2], [123456780], [123456708])

You need to bracket the whole thing.

pq.push([2, 123456780, 123456708])

However arrays are not comparable, so as has been mentioned:

pq=PQueue.new{|x,y| x[0]<y[0]}

HTH

5

Thanks. This may do what I need. I’ll work with it and see if it is
the
best way to go.

Being new to Ruby much of this is still magic to me. I look forward to
the
day when I’ll move beyond the magic phase.

No Sam

6

On Sun, Sep 20, 2009 at 10:23 PM, Mason K.
[email protected]wrote:

print “size:”+pq.size.to_s+“\n”
from simple_pqueue.rb:5

you’re not passing in a multi-dimensional array, you’re passing 3

wrote:

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

message:
multi-elements
No Sam

require “pqueue”
pq=PQueue.new proc{|x,y| x[0][0]<y[0][0]}
pq.push([[12], [123456780], [123456708]])
pq.push([[23], [123456780], [123456708]])
pq.push([[4], [123456780], [123456708]])
pq.push([[33], [123456780], [123456708]])
pq.push([[02], [123456780], [123456708]])
pq.push([[54], [123456780], [123456708]])
print “size:”+pq.size.to_s+“\n”
print "each_pop: "
pq.each_pop{|x| p x}

END
output that I got:
size:6
each_pop: [[2], [123456780], [123456708]]
[[4], [123456780], [123456708]]
[[12], [123456780], [123456708]]
[[23], [123456780], [123456708]]
[[33], [123456780], [123456708]]
[[54], [123456780], [123456708]]

You were passing a two dimensional array, so x[0] returns an array, ie
[2]
to get it to an integer, you need to go in one more time so x[0][0]
would
return 2, which is comparable to other integers.

You should consider making a class to handle these objects.

7

By the way, your last comment about making a class to handle these
objects.
I have a class and will be putting the method I’m building to push and
pop
these contents into an ordered queue. But the concept of objects is
still a
big mystery to me. I’m working on deeping my knowledge of that but it
will
take some time until it sinks in.

If you have the a method like I described, where does the require
“pqueue”
statement get included? Inside of the Class to end code or above it?

No Sam

8

On Sun, Sep 20, 2009 at 11:38 PM, Mason K.
[email protected]wrote:

pq=PQueue.new(proc{|x,y| x[0]<y[0]})
I got the messages:
The “from” error messages appear to be coming from the code inside of

you’re not passing in a multi-dimensional array, you’re passing 3
pq=PQueue.new(proc{|x,y| x[0]<y[0]})

<

6 pq.push(4)
into
error
dimensional
Thanks in advance to those of you who can help. And thanks to all
pq=PQueue.new proc{|x,y| x[0][0]<y[0][0]}
END
[2]
to get it to an integer, you need to go in one more time so x[0][0] would
return 2, which is comparable to other integers.

You should consider making a class to handle these objects.

It would probably look something like this:

require “pqueue”
class Record
#mix in these methods:
http://www.ruby-doc.org/core/classes/Comparable.html
include Comparable

#declare setters and getters for instance variables
attr_accessor :heuristic , :config1 , :config2

#initialize instance variables
def initialize(heuristic,config1,config2)
@heuristic , @config1 , @config2 = heuristic , config1 , config2
end

#required for Comparable module, compares two instances of Record
def <=>(other_record)
heuristic <=> other_record.heuristic
end

end

pq=PQueue.new proc{|x,y| x < y }

pq.push Record.new(12, 123456780, 123456708)
pq.push Record.new(23, 123456780, 123456708)
pq.push Record.new(4, 123456780, 123456708)
pq.push Record.new(33, 123456780, 123456708)
pq.push Record.new(02, 123456780, 123456708)
pq.push Record.new(54, 123456780, 123456708)

puts “size: #{pq.size.to_s}”

puts “each_pop:”
pq.each_pop{|x| p x}

END
You can override the to_s and inspect methods to alter your output. You
can
change how you implement <=> to change how priority is determined, or
you
can write a separate method to give priority, then change the proc that
you
pass to pq. The point here is that it simplifies the implementation, and
gives you a foundation to easily continue to build more methods and data
around the class. You don’t have to deal with awkward two dimensional
arrays
(by the way, if your data was always going to be in that form, then it
would
have made more sense to use a one-dimensional array).