ordered/sorted hash

Discussion in 'Ruby' started by robertj, Dec 8, 2005.

  1. robertj

    robertj Guest

    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
     
    robertj, Dec 8, 2005
    #1
    1. Advertising

  2. robertj

    Trans Guest

    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.
     
    Trans, Dec 8, 2005
    #2
    1. Advertising

  3. robertj

    Steve Litt Guest

    Steve Litt, Dec 8, 2005
    #3
  4. robertj

    Bill Kelly Guest

    From: "robertj" <>
    >
    > 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
     
    Bill Kelly, Dec 8, 2005
    #4
  5. robertj

    Gene Tani Guest

    Steve Litt wrote:
    > 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/basictutorial.htm#_Hashes
    >


    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/arrayfields-3.5.0/README
     
    Gene Tani, Dec 8, 2005
    #5
  6. Gene Tani wrote:
    > Steve Litt wrote:
    >
    >>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/basictutorial.htm#_Hashes
    >>

    >
    >
    > 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
     
    Daniel Berger, Dec 8, 2005
    #6
  7. robertj

    robertj Guest

    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
     
    robertj, Dec 8, 2005
    #7
  8. robertj

    robertj Guest

    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
     
    robertj, Dec 8, 2005
    #8
  9. robertj

    robertj Guest

    hi T.

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

    ciao robertj
     
    robertj, Dec 8, 2005
    #9
  10. robertj

    Trans Guest

    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.
     
    Trans, Dec 8, 2005
    #10
  11. robertj

    Trans Guest

    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.
     
    Trans, Dec 8, 2005
    #11
  12. robertj wrote:
    > 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


    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
     
    Simon Kröger, Dec 8, 2005
    #12
  13. robertj

    Guest

    On Fri, 9 Dec 2005, robertj wrote:

    > 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


    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
    --
    ===============================================================================
    | ara [dot] t [dot] howard [at] noaa [dot] gov
    | all happiness comes from the desire for others to be happy. all misery
    | comes from the desire for oneself to be happy.
    | -- bodhicaryavatara
    ===============================================================================
     
    , Dec 9, 2005
    #13
  14. robertj

    Hal Fulton Guest

    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
     
    Hal Fulton, Dec 9, 2005
    #14
  15. robertj

    Trans Guest

    wrote:
    > On Fri, 9 Dec 2005, robertj wrote:
    >
    > > 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

    >
    > 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


    Insertion order?

    T.
     
    Trans, Dec 9, 2005
    #15
  16. robertj

    Guest

    On Fri, 9 Dec 2005, Trans wrote:

    >>> 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

    >>
    >> 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

    >
    > 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
    --
    ===============================================================================
    | ara [dot] t [dot] howard [at] noaa [dot] gov
    | all happiness comes from the desire for others to be happy. all misery
    | comes from the desire for oneself to be happy.
    | -- bodhicaryavatara
    ===============================================================================
     
    , Dec 9, 2005
    #16
  17. robertj

    Trans Guest

    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.
     
    Trans, Dec 9, 2005
    #17
  18. robertj

    robertj Guest

    hi T.,

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

    ciao robertj
     
    robertj, Dec 10, 2005
    #18
  19. robertj

    Trans Guest

    robertj wrote:
    > hi T.,
    >
    > thats way cool.
    > what about
    > Dictionary.key and
    > Dictionary,value as names?


    Good good. I'll do that.

    Thanks,
    T.
     
    Trans, Dec 11, 2005
    #19
  20. 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"]
     
    William James, Dec 11, 2005
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. rp
    Replies:
    1
    Views:
    562
    red floyd
    Nov 10, 2011
  2. Hal Fulton

    A use case for an ordered hash

    Hal Fulton, Aug 13, 2006, in forum: Ruby
    Replies:
    89
    Views:
    675
    Haoqi Haoqi
    May 5, 2007
  3. Devi Web Development

    Ordered Hash Usefulness

    Devi Web Development, Nov 13, 2007, in forum: Ruby
    Replies:
    18
    Views:
    288
    Ralph Siegler
    Nov 26, 2007
  4. Ben Johnson

    Ordered hash hack for < ruby 1.9?

    Ben Johnson, Oct 1, 2008, in forum: Ruby
    Replies:
    21
    Views:
    273
    Charles Oliver Nutter
    Oct 3, 2008
  5. DL

    Ordered list inside ordered list

    DL, Nov 9, 2009, in forum: Javascript
    Replies:
    6
    Views:
    349
    Dr J R Stockton
    Nov 21, 2009
Loading...

Share This Page