Bug in facets 1.8.54

Ruby
1

There seems to be a bug in facets PQueue v1.8.54, at least the behavior
is
inconsistent. Here is the output on machine-1 which is running -

ruby 1.8.5 (2006-08-25) [i386-mswin32]
facets (1.8.51, 1.8.8)

irb(main):001:0> require ‘facets/more/pqueue’
=> true
irb(main):002:0> pqueue = PQueue.new(lambda{|x,y| x<y})
=> #<PQueue:0x2c35c60 @gt=#Proc:0x02c35d28@:2(irb), @size=0,
@qarray=[n
irb(main):003:0>
irb(main):004:0* pqueue.top
=> nil

This is the expected behavior

While on another machine with -

ruby 1.8.6 (2007-03-13 patchlevel 0) [i386-mswin32]
facets (1.8.54)

irb(main):001:0> require ‘facets/more/pqueue’
=> true
irb(main):002:0> @pqueue = PQueue.new(lambda{|x,y| x<y})
c:/ruby/lib/ruby/gems/1.8/gems/facets-1.8.54/lib/facets/more/pqueue.rb:236:
warn
ing: default `to_a’ will be obsolete
=> <PQueue: size=1, top=#Proc:0x02d9bc58@:2(irb)>
irb(main):003:0> @pqueue.top
=> #Proc:0x02d9bc58@:2(irb)

Strangely the lambda supplied as the comparator is inserted in the
queue.
Both Ruby and Facets version is different.

TIA

  • nasir
2

Ah! pqueue.rb was changed to be backward incompatible from facets
1.8.51 -> 1.8.54

1.8.51

def initialize(compareProc=lambda{|x,y| x>y})
# By default, retrieves maximal elements first.
@qarray=[nil]; @size=0; @gt=compareProc; make_legal
end

1.8.54

def initialize(elements=nil, &block) # :yields: a, b
@qarray = [nil]
@size = 0
@gt = block || lambda {|a,b| a > b}
replace(elements) if elements
end

Is there a way to load 1.8.51 version of one file (in this case
pqueue.rb) while use rest of the facets gem 1.8.54?
The other option is to monkey patch :frowning:
Any other option?

  • nasir
3

Le samedi 09 juin 2007 22:14, Nasir K. a écrit :

pqueue.rb) while use rest of the facets gem 1.8.54?
The other option is to monkey patch :frowning:
Any other option?

  • nasir

Hi,

Yes you are right, pqueue was rewritten and the api changed a lot. In
Facets,
there was two different classes for the same purpose, PQueue and Heap,
which
both provided a heap based priority queue. The latter was broken,
although it
had functionalities that pqueue lacked.

So, I merged both classes into one full-featured class, with a different
API,
closer to the Array one and more ruby-like to me. I submitted it, and as
I
based my work on pqueue, it replaced the previous version of the class,
and
Heap was removed.

Here is the notes I transmitted to Trans, who maintains Facets :

  • Initialization can take both initial values and comparison block, both
    optionnaly. Whereas the original PQueue take only a block, and Heap take
    only
    the initial values and needs to be subclassed in order to implement the
    comparison
  • Every methods which take an array as a parameter (initialize,
    push_all,
    replace) can now take any object that responds to #to_a, and are
    optimized in
    the case where the given object is a PQueue itself.
  • Creating a queue from scratch (with #initialize or with #replace) is
    faster
    than for the original PQueue, by adapting the #heapify method from Heap.
  • Added consistent methods #inspect, #==, #initialize_copy.
  • Methods are documented and unit-tested.

I dropped some methods from both original classes :

  • PQueue#make_legal, useless since the PQueue is now always legal
  • PQueue#replace_top_low, which I can’t figure out the purpose :slight_smile:
  • PQueue#each_with_index, already provided by Enumerator
  • Heap#sort_internal, was like an inplace-sort, but it destroyed the
    PQueue.

Actually, I didn’t know it was already commited :slight_smile:
If you used only push, pop, clear and empty? in your client code, then
the
only api change is for the instanciation method, which doesn’t take a
Proc
object as an argument, but a block.

I see no other solution than monkey patching, if you really don’t want
to
modify your client code.

Regards

4

Thanks Olivier.
IMHO def initialize(compareProc=lambda{|x,y| x>y}, elements=nil)
could have preserved backwards compatibility for PQueue users and also
preserved semantics of passing the comparator as an argument rather than
a
block.
Shall work around for now.

Thanks
Nasir