Is there a hash-like class that maintains insertion order

[Bob Hutchison]

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

 

[Ara.T.Howard]

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

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]

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

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

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

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

 

[Bob Hutchison]

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

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

 

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

 

[Kent Sibilev]

You can also check out the red-black tree implementation at
http://raa.ruby-lang.org/project/ruby-rbtree/

Kent.

 

[Logan Capaldo]

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]

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:

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