Is there a hash-like class that maintains insertion order
Bob Hutchison
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/>
Ara.T.Howard
harp:~ > cat a.rb
require 'arrayfields'
a = %w( aaa bbb ccc )
a.fields = %w( a b c )
p a['a'] = a[0]
p a['b'] = a[1]
p a['c'] = a[2]
harp:~ > ruby a.rb
"aaa"
"bbb"
"ccc"
or
harp:~ > cat a.rb
require 'arrayfields'
class HashMaintainingInsertionOrder < ::Array
def initialize
self.fields = []
end
end
a = HashMaintainingInsertionOrder::new
a['a'] = 'aaa'
a['b'] = 'bbb'
a['c'] = 'ccc'
p a['a'] = a[0]
p a['b'] = a[1]
p a['c'] = a[2]
harp:~ > ruby a.rb
"aaa"
"bbb"
"ccc"
this works because assigning to non-existent fields appends a key/val pair.
arrayfields is at
http://codeforpeople.com/lib/ruby/arrayfields/
and cross-listed on the raa. you also may want to check out my personal lib,
alib, at
http://codeforpeople.com/lib/ruby/alib/
which contains an OrderedHash impl. use like
require 'alib'
oh = OrderedHash::new
but this only returns keys in order for methods like each - it does not allow
look-up by number __or__ field.
hth.
-a
--
===============================================================================
| email :: ara [dot] t [dot] howard [at] noaa [dot] gov
| phone :: 303.497.6469
| Your life dwells amoung the causes of death
| Like a lamp standing in a strong breeze. --Nagarjuna
===============================================================================
Logan Capaldo
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.
Bob Hutchison
Ara, your arrayfield is an excellent fit to what I need. Thanks! The
semantics is slightly different (e.g. when you update a field you
don't change it's position in the array) than what I had been
thinking, but the difference is slight and is perfectly sensible.
I've incorporated it into my project (it only took a moment or two)
and all the unit tests I had pass.
Your alib also looks to be very interesting. Certainly worth looking
at just to pick up some Ruby tricks (so is arrayfield for that matter).
I'd be more than happy to use it, but I don't know what the license
terms are. What are they? Same question for alib.
Cheers,
Bob
Bob Hutchison
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,
Ara.T.Howard
> Ara, your arrayfield is an excellent fit to what I need. Thanks! The
> semantics is slightly different (e.g. when you update a field you don't
> change it's position in the array) than what I had been thinking, but the
> difference is slight and is perfectly sensible. I've incorporated it into my
> project (it only took a moment or two) and all the unit tests I had pass.
>
> Your alib also looks to be very interesting. Certainly worth looking at just
> to pick up some Ruby tricks (so is arrayfield for that matter).
>
> I'd be more than happy to use it, but I don't know what the license terms
> are. What are they? Same question for alib.
all my projects use ruby's license - which is dual - so do what you like with
any of my code.
glad it worked out for you.
kind regards.
-a
--
===============================================================================
Kent Sibilev
http://raa.ruby-lang.org/project/ruby-rbtree/
Kent.
Logan Capaldo
On Sep 26, 2005, at 2:33 PM, Kent Sibilev wrote:
> You can also check out the red-black tree implementation at
> http://raa.ruby-lang.org/project/ruby-rbtree/
>
> Kent.
>
This is not quite what he needs. A red-black tree is sort of like a
Sorted Hash, it doesn't maintain insertion order.
eg.
a = InsertionOrderedHash.new
a[3] = "one"
a[1] = "two"
a[2] = "three"
a.each do |x|
puts x
end
one
two
three
b = RedBlackTree.new
a[3] = "one"
a[1] = "two"
a[2] = "three"
b.each do |x|
puts x
end
two
three
one
Bob Hutchison
On Sep 26, 2005, at 10:24 AM, Ara.T.Howard wrote:
> On Mon, 26 Sep 2005, Bob Hutchison wrote:
>
>
>> Ara, your arrayfield is an excellent fit to what I need. Thanks! The
>> semantics is slightly different (e.g. when you update a field you
>> don't
>> change it's position in the array) than what I had been thinking,
>> but the
>> difference is slight and is perfectly sensible. I've incorporated
>> it into my
>> project (it only took a moment or two) and all the unit tests I
>> had pass.
>>
>> Your alib also looks to be very interesting. Certainly worth
>> looking at just
>> to pick up some Ruby tricks (so is arrayfield for that matter).
>>
>> I'd be more than happy to use it, but I don't know what the
>> license terms
>> are. What are they? Same question for alib.
>>
>
> all my projects use ruby's license - which is dual - so do what you
> like with
> any of my code.
>
> glad it worked out for you.
Works beautifully. If you are curious, here is a link to an article I
have just published on my weblog about the project I'm working on:
<http://recursive.ca/hutch/index.php?p=243>
>
> kind regards.
>
> -a
> --
> ======================================================================
> =========
> | email :: ara [dot] t [dot] howard [at] noaa [dot] gov
> | phone :: 303.497.6469
> | Your life dwells amoung the causes of death
> | Like a lamp standing in a strong breeze. --Nagarjuna