From: Logan Capaldo <logancapaldo@...>
Date: 2005-09-26T11:37:31+09:00
Subject: Re: Is there a hash-like class that maintains insertion order


On Sep 25, 2005, at 10:21 PM, Bob Hutchison wrote:

> Hi,
>
> Is there a Hash-like class that maintains insertion order and,  
> ideally, allows 'retrieval' by either key or index? I googled  
> around for this but can't seem to hit on a query string that is  
> useful.
>
> In a perfect implementation I'd be able to do something like:
>
> hash = HashMaintainingInsertionOrder.new
> hash["a"] = "aaa"
> hash["b"] = "bbb"
> hash["c"] = "ccc"
>
> assert_equal(hash["a"], hash[0])
> assert_equal(hash["b"], hash[1])
> assert_equal(hash["c"], hash[2])
>
> Thanks,
> Bob
>
> ----
> Bob Hutchison          -- blogs at <http://www.recursive.ca/hutch/>
> Recursive Design Inc.  -- <http://www.recursive.ca/>
> Raconteur              -- <http://www.raconteur.info/>
>
>
>
>
>


I can't think of one off the top of my head, but its not to hard to  
write

% cat orderedhash.rb
class OrderedHash < Hash
         def initialize
                 @key_list = []
                 super
         end
         def []=(key, value)
                 if has_key?(key)
                         super(key, value)
                 else
                         @key_list << key
                         super(key, value)
                 end
         end

         def by_index(index)
                 self[@key_list[index]]
         end

         def each
                 @key_list.each do |key|
                         yield(key, self[key] )
                 end
         end

         def delete(key)
                 @key_list = @key_list.delete_if { |x| x == key }
                 super(key)
         end
end

% irb
irb(main):001:0> require 'orderedhash'
=> true
irb(main):002:0> a = OrderedHash.new
=> {}
irb(main):003:0> a['a'] = 2
=> 2
irb(main):004:0> a.by_index(0)
=> 2
irb(main):005:0> a
=> {"a"=>2}
irb(main):006:0> a['b'] = 4
=> 4
irb(main):007:0> a
=> {"a"=>2, "b"=>4}
irb(main):008:0> a.delete('a')
=> 2
irb(main):009:0> a
=> {"b"=>4}
irb(main):010:0> a.by_index(0)
=> 4


Disadvantages include merge won't work properly, and delete is now O 
(n) instead of O(1)

I didn't change [] for it to have different semantics for integers  
vs. "anything else" because what if you want to use an integer as a key.