From: Bob Hutchison <hutch@...>
Date: 2005-09-26T22:04:03+09:00
Subject: Re: Is there a hash-like class that maintains insertion order


On Sep 25, 2005, at 10:37 PM, Logan Capaldo wrote:

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

You are right it doesn't look too difficult to write. I had intended  
to do so if I couldn't find a lazy way out -- which I think I did  
with Ara's arrayfield class. I was a bit worried that something nasty  
would come up when implementing it.

Never-the-less, thanks Logan! I appreciate this.

Cheers,
Bob

----
Bob Hutchison          -- blogs at <http://www.recursive.ca/hutch/>
Recursive Design Inc.  -- <http://www.recursive.ca/>
Raconteur              -- <http://www.raconteur.info/>