class Array
def with_indices
n = 0
collect{|x| n+=1; [x, n]}
end
def without_indices
collect{|x| x[0]}
end
def stable_sort
if block_given?
with_indices.sort{ |a, b|
res = yield(a[0], b[0])
res = a[1] <=> b[1] if res == 0
res
}.without_indices
else
sort
end
end
end
Refactorings
No refactoring yet !
Tj Holowaychuk
December 14, 2009, December 14, 2009 16:07, permalink
whats wrong sort ?
Marc-Andre
December 15, 2009, December 15, 2009 03:08, permalink
Calling #sort if no block is given won't really work if the class of the sorted elements has redefined <=> (for example to be case insensitive).
Moreover you might as well define stable_sort on Enumerable in general. Finally, your #with_indices already exist (in enumerator form): each_with_index
Note: if running 1.8.6: require 'backports'
module Enumerable
def stable_sort(&block)
block &&= Proc.new do |(x, i), (y, j)|
yield(x, y).nonzero? || i <=> j
end
each_with_index.sort(&block).map(&:first)
end
end
9.downto(1).sort{|x,y| x % 2 <=> y % 2} # => [8, 2, 4, 6, 5, 7, 3, 9, 1]
9.downto(1).stable_sort{|x,y| x % 2 <=> y % 2} # => [8, 6, 4, 2, 9, 7, 5, 3, 1]
Kartik Agaram
December 15, 2009, December 15, 2009 05:24, permalink
Beautiful and educational. Thanks!
(Still figuring out what block &&= does..)
Colin Curtin
December 16, 2009, December 16, 2009 01:49, permalink
Kartik:
&&= is "and" conditional assignment. Think ||= but with &&.
@hello ||= 'hi'
is: @hello || @hello = 'hi'
@hello &&= 'hi'
is: @hello && @hello = hi.
So in effect, the code Marc-Andre posted would read like this:
block && block = Proc.new (... something using block before reassignment)
Then the block passed to each_with_index is assigned to the new Proc, but only if there was a block passed into #stable_sort.
Kartik Agaram
December 16, 2009, December 16, 2009 10:25, permalink
Yes, I know what && does, and I can see what the block&&= does in the code above, but I still don't see how the code within Proc.new uses the existing code, or how && knows how to deal with blocks. Is it a special case? If so, is this documented somewhere? Thanks Colin.
peernohell.myopenid.com
December 16, 2009, December 16, 2009 13:17, permalink
bloc code is call in new proc with yield function
look her for exemple : http://www.tutorialspoint.com/ruby/ruby_blocks.htm
Ruby's sort isn't stable. Let's finally fix this wart once and for all.