Using Java PriorityQueue in Matlab

Question

I need a min-heap in Matlab and I'm trying to use Java's PriorityQueue. I'm stuck on how to supply the Comparator. So far I have initialized the PriorityQueue and can add one value-index pair to it:

>> q = java.util.PriorityQueue
q =
[]
>> q.add({1,3})
ans =
     1

The problem occurs when I try to add more data:

>> q.add({2,4})
??? Java exception occurred: 
java.lang.ClassCastException: [Ljava.lang.Object; cannot be cast to java.lang.Comparable
    at java.util.PriorityQueue.siftUpComparable(Unknown Source)
    at java.util.PriorityQueue.siftUp(Unknown Source)
    at java.util.PriorityQueue.offer(Unknown Source)
    at java.util.PriorityQueue.add(Unknown Source)

From this post, I see that I need to supply a Comparator function, but I don't know how to do this.

Drowsy

I suspect you have to write the comparator function in Java and compile it separately. – Carolanncarole

Yeah, it looks like that is the way to do it. I'm not that fluent in Java so I've looked for other solutions and found an entry on the file exchange (mathworks.com/matlabcentral/fileexchange/…) that does what I need, although it crashes rather ungracefully if try to push something from an empty queue. – Drowsy

Answer 1

Priority queues need to either contain objects that implement Comparable, or you need to pass in a Comparator function at construction time.

There isn't a way currently in MATLAB to either implement Java interfaces with MATLAB code, or supply literal Java code.

So you'd have to follow @nibot's suggestion and make a small .jar file containing a class implementing Comparator.

Tannate

Answer 2

Here's a partial answer assuming you can use non-negative floating values and integer indices. The idea is to stringy the pair and use that as the comparable object in the java queue.

q = java.util.PriorityQueue;
q.add(encode(1.2,4));
q.add(encode(1.1,8));
q.add(encode(8.0,1));
q.add(encode(1e-7,0));

% Pop and print
while ~q.isEmpty()
  [value,index] = decode(q.remove());
  fprintf('%g,%d\n',value,index)
end

function u = encode(value,index)
  % value should be non-negative
  % index should be an integer
  u = sprintf('%010d,%d',uint64(java.lang.Float.floatToIntBits(value)),index);
end
function [value,index] = decode(u)
  value_index = sscanf(u,'%d,%d',2);
  value = java.lang.Float.intBitsToFloat(value_index(1));
  index = value_index(2);
end

On a quick and dirty test, pushing and then popping 10000 random floats takes 0.5secs compared to pushing then popping 10000 (random float, index) pairs takes 0.75secs. There's overhead, but maybe not a killer.

Sacha

Answer 3

import java.util.*;

q = java.util.PriorityQueue();
for i=1:10
q.add(i);
end
disp(q)
[1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0]

Autocrat

While this code may answer the question, it would be better to include some context, explaining how it works and when to use it. Code-only answers are not useful in the long run. – Occur