Sorting a Hash


#1

I want to have a hash with its elements sorted with a custom sort order.
Consider the example

#---------------------
test_hash = {“A” => “first”, “B” => “second”}
puts test_hash.keys.join(", ")
order_arr = [“B”, “A”]

test_hash.sort do |x,y|
(order_arr.index(x[0])?order_arr.index(x[0]):order_arr.length) <=>
(order_arr.index(y[0])?order_arr.index(y[0]):order_arr.length)
end
puts test_hash.keys.join(", ")
#----------------------

Output:
A, B
A, B
=> true

I want to order such that the keys (or values) when returned in an array
are
ordered.
Obviously the above snipper does not work because Hash#sort does not
sort
the Hash but returns an array of arrays with elements sorted according
to
sort block.

I can maintain a parallel array of sorted keys but it is kind of kludgy.
Can I sort the hash “in place” such that the Hash#keys and Hash#values
return sorted results, without me having to maintain this array of
arrays
separately?

TIA


#2

On 2/28/07, Nasir K. removed_email_address@domain.invalid wrote:

I can maintain a parallel array of sorted keys but it is kind of kludgy.
Can I sort the hash “in place” such that the Hash#keys and Hash#values
return sorted results, without me having to maintain this array of arrays
separately?

The short answer is “No”. :slight_smile: There’s a bunch of SortedHashes floating
out
there on the net though, so you don’t have to write it yourself.

TIA


#3

On Thu, 1 Mar 2007, Nasir K. wrote:

I want to have a hash with its elements sorted with a custom sort order.
Consider the example

this exactly what rbtree does. look on the raa.

-a


#4

Part of what makes a hash a hash is the fact that the elements in it are
not
in a sequential order, as far as I know. Trying to maintain a hash “in
order” kind of ruins some of its hashiness. (Is that a word? :P)

Dave


#5

On 2/28/07, Nasir K. removed_email_address@domain.invalid wrote:

I want to order such that the keys (or values) when returned in an array are
ordered.
Obviously the above snipper does not work because Hash#sort does not sort
the Hash but returns an array of arrays with elements sorted according to
sort block.

I can maintain a parallel array of sorted keys but it is kind of kludgy.
Can I sort the hash “in place” such that the Hash#keys and Hash#values
return sorted results, without me having to maintain this array of arrays
separately?

Well there’s nothing stopping you from adding methods to Hash to
return sorted keys and values. Of course you can also just do

hash.keys.sort
or
hash.values.sort

The first one will likely do what you want, but I suspect that what
you really want for values is to get them as ordered by the sorted
keys.

Here’s a quick implementation of two additional methods for hash, I
wouldn’t recommend changing the implementation of the existing keys
and values methods:

rick@frodo:/public/rubyscripts$ cat shash.rb
class Hash

def sorted_keys(&sort_block)
keys.sort(&sort_block)
end

def values_sorted_by_keys(&sort_block)
values_at(*sorted_keys(&sort_block))
end
end

test_hash = {“Fred” => “Wilma”, “Barney” => “Betty”,
“Ricky” => “Lucy”, “Fred” => “Ethel”,
“Ralph” => “Alice”, “Ed” => “Trixie”}

p test_hash.keys
p test_hash.values
p test_hash.sorted_keys
p test_hash.values_sorted_by_keys
p test_hash.sorted_keys {|a, b| b <=> a}
p test_hash.values_sorted_by_keys {|a, b| b <=> a}

rick@frodo:/public/rubyscripts$ ruby shash.rb
[“Ralph”, “Ricky”, “Barney”, “Fred”, “Ed”]
[“Alice”, “Lucy”, “Betty”, “Ethel”, “Trixie”]
[“Barney”, “Ed”, “Fred”, “Ralph”, “Ricky”]
[“Betty”, “Trixie”, “Ethel”, “Alice”, “Lucy”]
[“Ricky”, “Ralph”, “Fred”, “Ed”, “Barney”]
[“Lucy”, “Alice”, “Ethel”, “Trixie”, “Betty”]


Rick DeNatale

My blog on Ruby
http://talklikeaduck.denhaven2.com/


#6

Trying to maintain a hash "in

order" kind of ruins some of its hashiness.

Requiring a map to maintain its entries sorted is not that unusual. You
may
need this (like in my case) when you need not just the keyed access to
the
hash elements but also the whole map, but in some order.

Java’s java.util.SortedMap does just that.
As Ara pointed out in one of the responses, rbtree is a Ruby
implementation
of it. But I wonder why RAA download is not available anymore, nor there
is
a gem. Does anyone know if this could be in future Ruby versions?

Thanks Rick for a simple solution which externally does what I want from
it,
however it sorts on each access to keys and values which is not very
efficient for cases when the map is not updated very frequently but is
accessed a number of times.
One could perhaps overload the []= method and maintain a sorted parallel
array in the Hash object (this is what I did in my case).

Thanks for all the responses.


#7

On Fri, 2 Mar 2007, Nasir K. wrote:

One could perhaps overload the []= method and maintain a sorted parallel
array in the Hash object (this is what I did in my case).

Works great in some cases, but array’s function means that some
operations
are very slow.

I have a class library in IOWA that I extracted some time ago as a
microproject that provides a structure that provides both hashlike and
arraylike access semantics using a linked list with a hash key -> node
index.

http://rubyforge.org/frs/download.php/12908/LinkedList_0.99.2.9.tar.gz

Kirk H.