Forum: Ruby ordered/sorted hash

Announcement (2017-05-07): www.ruby-forum.com is now read-only since I unfortunately do not have the time to support and maintain the forum any more. Please see rubyonrails.org/community and ruby-lang.org/en/community for other Rails- und Ruby-related community platforms.
D67ca51e6025a5ed5282205e70379798?d=identicon&s=25 robert_kuzelj (Guest)
on 2005-12-08 18:38
(Received via mailing list)
hi,

is there anywhere a class that does soemthing
akin to java.util.SortedMap? that is sorting
and iterating over the hash in the order of its
keys.

i had a look into facets dictionary but that does
only preserve the ordering of insertion which
is not what i want.

any other suggestions?

ciao robertj
45196398e9685000d195ec626d477f0e?d=identicon&s=25 transfire (Guest)
on 2005-12-08 18:58
(Received via mailing list)
Hi Robert,

> i had a look into facets dictionary but that does
> only preserve the ordering of insertion which
> is not what i want.

The dictionary class in Facets/Calibre is basically the ordered hash
written by jan molic. I've been wanting to improve on it. This looks
like the oppornunity. What is it that you need? I'd be happy to work in
your critera.

Thanks,
T.
1b62a85b59ccab03b84ee5ec378f75b4?d=identicon&s=25 slitt (Guest)
on 2005-12-08 19:02
(Received via mailing list)
On Thursday 08 December 2005 12:37 pm, robertj wrote:
> hi,
>
> is there anywhere a class that does soemthing
> akin to java.util.SortedMap? that is sorting
> and iterating over the hash in the order of its
> keys.

When I tried it, it seemed that Ruby automatically sorted the keys. I'm
not
sure if this is what you want, but see this:

http://www.troubleshooters.com/codecorn/ruby/basic...

HTH

SteveT

Steve Litt
http://www.troubleshooters.com
slitt@troubleshooters.com
4feed660d3728526797edeb4f0467384?d=identicon&s=25 billk (Guest)
on 2005-12-08 19:14
(Received via mailing list)
From: "robertj" <robert_kuzelj@yahoo.com>
>
> is there anywhere a class that does soemthing
> akin to java.util.SortedMap? that is sorting
> and iterating over the hash in the order of its
> keys.

Perhaps rbtree?
http://raa.ruby-lang.org/project/ruby-rbtree/


Regards,

Bill
9dfe8c734b0f9b37a4e218425c0a2138?d=identicon&s=25 gene.tani (Guest)
on 2005-12-08 19:18
(Received via mailing list)
Steve Litt wrote:
>
> http://www.troubleshooters.com/codecorn/ruby/basic...
>

Not sure what "it" is, but Hash#sort will convert the hash to a list of
lists, sorted by their keys

Then others have put in rbtrees, arrays accessed by keywords,
http://raa.ruby-lang.org/project/ruby-rbtree/
http://codeforpeople.com/lib/ruby/arrayfields/arra...
F3b7b8756d0c7f71cc7460cc33aefaee?d=identicon&s=25 Daniel.Berger (Guest)
on 2005-12-08 19:23
(Received via mailing list)
Gene Tani wrote:
>>
>>When I tried it, it seemed that Ruby automatically sorted the keys. I'm not
>>sure if this is what you want, but see this:
>>
>>http://www.troubleshooters.com/codecorn/ruby/basic...
>>
>
>
> Not sure what "it" is, but Hash#sort will convert the hash to a list of
> lists, sorted by their keys

True, but unless you need the values stored in order internally, just do
this:

hash.sort.each{ |e| puts "#{e[0]} => #{e[1]}" }

Regards,

Dan
D67ca51e6025a5ed5282205e70379798?d=identicon&s=25 robert_kuzelj (Guest)
on 2005-12-08 19:55
(Received via mailing list)
hi,

the only real requirement is
that #each returns me the
key value pairs in an ordered fashion.

default ordering should be by key.

one could but think of also having
a switch that allows for ordering by
value.

ciao robertj
D67ca51e6025a5ed5282205e70379798?d=identicon&s=25 robert_kuzelj (Guest)
on 2005-12-08 19:59
(Received via mailing list)
hi daniel,

>>hash.sort.each{ |e| puts "#{e[0]} => #{e[1]}" }
this has the effect that clients of that hash
need to know that they must order the hash +
the interface for iteration has changed.

instead of hash.each { |k, v| ...} you get hash.sort.each { |v| ...}

in short your solution requires "sorting" to become part of
the "official" interface of my hash.

ciao robertj
D67ca51e6025a5ed5282205e70379798?d=identicon&s=25 robert_kuzelj (Guest)
on 2005-12-08 20:03
(Received via mailing list)
hi T.

another idea would be to be able to define
a comperator block that does the actual
comparisson.

ciao robertj
4299e35bacef054df40583da2d51edea?d=identicon&s=25 James Gray (bbazzarrakk)
on 2005-12-08 20:24
(Received via mailing list)
On Dec 8, 2005, at 12:57 PM, robertj wrote:

> the "official" interface of my hash.
You could easily wrap a Hash and provide an each() that sorted before
yielding.

James Edward Gray II
45196398e9685000d195ec626d477f0e?d=identicon&s=25 transfire (Guest)
on 2005-12-08 20:28
(Received via mailing list)
robertj wrote:
> another idea would be to be able to define
> a comperator block that does the actual
> comparisson.

I see. So you want a way to tell the object itself how it's to order
the elements. The default wprobably should stay insertion order, but
you'd like to specify an alternative like alpahnumeric key order. Is
that right? If so, I can put in an optional parameter for that no
problem. Although you may have to set it post instantiation, something
like

  d = Dictionary.new.sort_on { |a,b| a.key <=> b.key }

As a shorthand:

  d = Dictionary.new.sort_on(:key)

While I would like to add this as a block/parameter of the initialize
method itself, it may be a problem b/c this should probably be used for
a default block like hash has.

T.
45196398e9685000d195ec626d477f0e?d=identicon&s=25 transfire (Guest)
on 2005-12-08 20:41
(Received via mailing list)
Thank robertj I'll work on it now.

By the way have you seen calibre/association? That's kind of neat. It
isn't quite like a regular hash, but you can use it do order hash-like
strucutures.

  require 'calibre/association'

  assoc_array = [ :a >> 1, :b >> :2, :c >> 3 ]

  assoc_array.each{ |k,v| p k,v }

produces

  :a
  1
  :b
  2
  :c
  3

T.
A9c4658e9e475e13d790ae419acf01b6?d=identicon&s=25 SimonKroeger (Guest)
on 2005-12-08 21:17
(Received via mailing list)
robertj wrote:
> value.
>
> ciao robertj

hi,

if speed isn't an issue:

---------------------------------------------
class SortedHash < Hash
   alias :unsorted_each :each
   def each
     keys.sort.each{|k| yield k, self[k]}
   end
end

h = SortedHash[*Array.new(20){rand(100)}]
h.each{|k, v| puts "#{k} => #{v}"}
---------------------------------------------

this isn't meant to replace a red black tree
implementation of course.

cheers

Simon
Cb48ca5059faf7409a5ab3745a964696?d=identicon&s=25 ara.t.howard (Guest)
on 2005-12-09 04:45
(Received via mailing list)
On Fri, 9 Dec 2005, robertj wrote:

>
> ciao robertj

   harp:~ > cat a.rb
   require "alib"
   include ALib

   oh = OrderedHash::new
   oh["first"] = 42
   oh["second"] = "forty-two"

   puts "---"
   oh.each{|k,v| puts "#{ k } : #{ v }"}

   harp:~ > ruby a.rb
   ---
   first : 42
   second : forty-two


-a
C1bcb559f87f356698cfad9f6d630235?d=identicon&s=25 hal9000 (Guest)
on 2005-12-09 05:50
(Received via mailing list)
James Edward Gray II wrote:
>
> You could easily wrap a Hash and provide an each() that sorted before
> yielding.
>

I've been discussing this off and on for years. What you say is true,
and it's also true that we can easily write a class that acts like an
ordered hash.

The problem is literals or constants. Nothing I do will ensure that
the hash  { x=>a, y=>b, z=>c }  will be iterated over in that
original specified order.


Hal
45196398e9685000d195ec626d477f0e?d=identicon&s=25 transfire (Guest)
on 2005-12-09 05:58
(Received via mailing list)
ara.t.howard@noaa.gov wrote:
> >
>    oh["second"] = "forty-two"
>
>    puts "---"
>    oh.each{|k,v| puts "#{ k } : #{ v }"}
>
>    harp:~ > ruby a.rb
>    ---
>    first : 42
>    second : forty-two

Insertion order?

T.
Cb48ca5059faf7409a5ab3745a964696?d=identicon&s=25 ara.t.howard (Guest)
on 2005-12-09 06:15
(Received via mailing list)
On Fri, 9 Dec 2005, Trans wrote:

>>>
>>    puts "---"
>>    oh.each{|k,v| puts "#{ k } : #{ v }"}
>>
>>    harp:~ > ruby a.rb
>>    ---
>>    first : 42
>>    second : forty-two
>
> Insertion order?

yup.  this is my favourite usage:

     harp:~ > cat a.rb
     require "alib"

     config = ALib::OrderedAutoHash::new

     config["db"]["port"] = 5432
     config["db"]["host"] = "localhost"
     config["db"]["host"] = "postgres"

     config["site"]["uri"] = "http://codeforpeople.com"

     y config


     harp:~ > ruby a.rb
     ---
     db:
       port: 5432
       host: postgres
     site:
       uri: http://codeforpeople.com

ahhh.

-a
45196398e9685000d195ec626d477f0e?d=identicon&s=25 transfire (Guest)
on 2005-12-09 18:06
(Received via mailing list)
Okay, I have preliminary implementation of Dictionary class with
built-in ordering. Its important to note that the implementation isn't
as efficient as sorting externally b/c the class sorts the pairs *every
time* #each is called (if order_by is set). There are ways to improve
the efficiency, but that's a task for another day.

The basic way to do it:

  d = Dictionary.new.order_by{ |k,v| k }

This creates a dictionary orderd by the key. The block allows you to
define almost any order mechisim you like. Since alphanumeric key order
is likely the most common (after the default of insertion order) I
created a special constructor method just for it:

  d = Dictionary.alpha

This does the exact same thing is the last example. The only thing I'm
not so sure about is the name of this method. Is this good or would
something else be better?

BTW, Ara, you inspired me:

  d = Dictionary.auto

will do the same as OrderedAutoHash::new. Thanks for that idea. Of
course, I have the same question about my choice of method name here
too.

T.
D67ca51e6025a5ed5282205e70379798?d=identicon&s=25 robert_kuzelj (Guest)
on 2005-12-10 16:15
(Received via mailing list)
hi T.,

thats way cool.
what about
Dictionary.key and
Dictionary,value as names?

ciao robertj
45196398e9685000d195ec626d477f0e?d=identicon&s=25 transfire (Guest)
on 2005-12-11 15:33
(Received via mailing list)
robertj wrote:
> hi T.,
>
> thats way cool.
> what about
> Dictionary.key and
> Dictionary,value as names?

Good good. I'll do that.

Thanks,
T.
2ee1a7960cc761a6e92efb5000c0f2c9?d=identicon&s=25 William James (Guest)
on 2005-12-11 17:27
(Received via mailing list)
Hal Fulton wrote:

> The problem is literals or constants. Nothing I do will ensure that
> the hash  { x=>a, y=>b, z=>c }  will be iterated over in that
> original specified order.


>> [ ['x','a'], ['y','b'], ['z','c'] ].each{|x| p x}
["x", "a"]
["y", "b"]
["z", "c"]

>> [ ['x','a'], ['y','b'], ['z','c'] ].assoc('z')
=> ["z", "c"]
This topic is locked and can not be replied to.