Preserve insert order in a Hash

M

Me Me

Hi,
I would like to know if it's possible to insert values in a Hash and
then extract all of them in the same insertion order.

I noticed that if I then try to print the content of an Hash using
"each" the order is not the same as the insertion.

Thanks
 
P

Peña, Botp

RnJvbTogTWUgTWUgW21haWx0bzplbWFudWVsZWZAdGlzY2FsaS5pdF0gDQojIEkgd291bGQgbGlr
ZSB0byBrbm93IGlmIGl0J3MgcG9zc2libGUgdG8gaW5zZXJ0IHZhbHVlcyBpbiBhIEhhc2ggYW5k
DQojIHRoZW4gZXh0cmFjdCBhbGwgb2YgdGhlbSBpbiB0aGUgc2FtZSBpbnNlcnRpb24gb3JkZXIu
DQoNCm9ubHkgaW4gcnVieSAxLjkNCg0KQzpccnVieTEuOVxiaW4+aXJiLmJhdA0KPiBoPXt9DQo9
PiB7fQ0KDQo+IGhbMV09MQ0KPT4gMQ0KDQo+IGhbMl09MQ0KPT4gMQ0KDQo+IGhbM109MQ0KPT4g
MQ0KDQo+IGgNCj0+IHsxPT4xLCAyPT4xLCAzPT4xfQ0KDQo+IGhbMS41XT0xDQo9PiAxDQoNCj4g
aA0KPT4gezE9PjEsIDI9PjEsIDM9PjEsIDEuNT0+MX0NCg0KPiBoWzBdPTENCj0+IDENCg0KPiBo
DQo9PiB7MT0+MSwgMj0+MSwgMz0+MSwgMS41PT4xLCAwPT4xfQ0KDQo+IFJVQllfVkVSU0lPTg0K
PT4gIjEuOS4wIg0K
 
T

Thomas B.

From: Me Me [mailto:[email protected]]
# I would like to know if it's possible to insert values in a Hash and
# then extract all of them in the same insertion order.

only in ruby 1.9

Could anybody explain why this feature was added? Isn't it going to slow
down the operations on the Hash? I think it is useless to mix Array with
Hash.

TPR.
 
M

Me Me

Thomas said:
From: Me Me [mailto:[email protected]]
# I would like to know if it's possible to insert values in a Hash and
# then extract all of them in the same insertion order.

only in ruby 1.9

Could anybody explain why this feature was added? Isn't it going to slow
down the operations on the Hash? I think it is useless to mix Array with
Hash.

TPR.

well, basically I just need a Hash to use String as indexes like

sourceInfo = Hash.new
sourceInfo["var1"]=123
sourceInfo["var2"]=2
sourceInfo["var3"]=3
sourceInfo["var4"]=23

and then print them in the exact order of insertion
 
D

Dick Davies

Thomas said:
From: Me Me [mailto:[email protected]]
# I would like to know if it's possible to insert values in a Hash and
# then extract all of them in the same insertion order.

only in ruby 1.9

Could anybody explain why this feature was added? Isn't it going to slow
down the operations on the Hash? I think it is useless to mix Array with
Hash.

TPR.

well, basically I just need a Hash to use String as indexes like

sourceInfo =3D Hash.new
sourceInfo["var1"]=3D123
sourceInfo["var2"]=3D2
sourceInfo["var3"]=3D3
sourceInfo["var4"]=3D23

and then print them in the exact order of insertion

Can't you just sort them on the way out?
i.e.

sourceinfo.keys.sort.each { |k|
sourceinfo[k].do_stuff
}
--=20
Rasputnik :: Jack of All Trades - Master of Nuns
http://number9.hellooperator.net/
 
M

Me Me

Dick said:
and then print them in the exact order of insertion

Can't you just sort them on the way out?
i.e.

sourceinfo.keys.sort.each { |k|
sourceinfo[k].do_stuff
}

thanks
well in this case they will be sorted alphabetically, right?
the example is simplyfied, in my case the keys have differernt names.
 
B

Bill Kelly

From: "Me Me said:
I think this is not my case, I need a Hash as I explained

Here's an implementation for ruby 1.8 ... I apologize for the lack of tests.


class InsertOrderPreservingHash
include Enumerable

def initialize(*args, &block)
@h = Hash.new(*args, &block)
@ordered_keys = []
end

def []=(key, val)
@ordered_keys << key unless @h.has_key? key
@h[key] = val
end

def each
@ordered_keys.each {|k| yield(k, @h[k])}
end
alias :each_pair :each

def each_value
@ordered_keys.each {|k| yield(@h[k])}
end

def each_key
@ordered_keys.each {|k| yield k}
end

def keys
@ordered_keys
end

def values
@ordered_keys.map {|k| @h[k]}
end

def clear
@ordered_keys.clear
@h.clear
end

def delete(k, &block)
@ordered_keys.delete k
@h.delete(k, &block)
end

def reject!
del = []
each_pair {|k,v| del << k if yield k,v}
del.each {|k| delete k}
del.empty? ? nil : self
end

def delete_if(&block)
reject!(&block)
self
end

%w(merge!).each do |name|
define_method(name) do |*args|
raise NotImplementedError, "#{name} not implemented"
end
end

def method_missing(*args)
@h.send(*args)
end
end


# example:

h = InsertOrderPreservingHash.new

h[:aaa] = 0
h[:foo] = 123
h[:bar] = 456
h[:baz] = 789
h.delete :aaa
h[:aaa] = 1

h.each_pair {|k,v| p [k,v]}

# produces:

[:foo, 123]
[:bar, 456]
[:baz, 789]
[:aaa, 1]


Regards,

Bill
 
B

Brian Candler

well, basically I just need a Hash to use String as indexes like
sourceInfo = Hash.new
sourceInfo["var1"]=123
sourceInfo["var2"]=2
sourceInfo["var3"]=3
sourceInfo["var4"]=23

What do you want to happen if sourceInfo["var2"] is assigned a second
time? Do you want to replace it where it originally was in the sequence,
or do you want to delete it and add the new value to the end? Or do you
want both elements to appear at the same time? Or doesn't it matter?

I am just wondering because perhaps all you need is

sourceInfo = []
sourceInfo << ["var1",123]
sourceInfo << ["var2",2]
sourceInfo << ["var3",3]
sourceInfo << ["var4",4]
sourceInfo.each { |k,v| puts "#{k}=>#{v}" }

At least, that's fine if all you want to do is iterate over the
collection and add new elements. Finding or deleting elements by key
requires a linear search:

dummy,value = sourceInfo.find { |k,v| k == "var2" }

However you can optimise this by building a hash as you go which points
to the same elements; or you could build an array containing just the
keys.

class HashAndArray
def initialize
@h, @a = {}, []
end
def [](k)
@h[k]
end
def []=(k,v)
@a << k unless @h.has_key?(k)
@h[k] = v
end
def each
@a.each { |k| yield k,@h[k] }
end
end

sourceInfo = HashAndArray.new
sourceInfo["var1"]=123
sourceInfo["var2"]=2
sourceInfo["var3"]=3
sourceInfo["var4"]=23
sourceInfo.each { |k,v| puts "#{k}=>#{v}" }
puts sourceInfo["var2"]

Adding a delete() method is left as an exercise.
 
R

Rick DeNatale

[Note: parts of this message were removed to make it a legal post.]

Hi,

In message "Re: Preserve insert order in a Hash"
|Could anybody explain why this feature was added?

Useful for some cases, especially for keyword arguments.

|Isn't it going to slow down the operations on the Hash?

No. hash reference operation does not touch order information, only
for iteration. Memory consumption increased a bit.

If I remember correctly, it's been a while since I looked at the code, 1.9
implements this by using a singly linked list which introduces a small
overhead only when elements are either added or deleted.
 
R

Rick DeNatale

[Note: parts of this message were removed to make it a legal post.]

well, basically I just need a Hash to use String as indexes like

sourceInfo = Hash.new
sourceInfo["var1"]=123
sourceInfo["var2"]=2
sourceInfo["var3"]=3
sourceInfo["var4"]=23

What do you want to happen if sourceInfo["var2"] is assigned a second
time? Do you want to replace it where it originally was in the sequence,
or do you want to delete it and add the new value to the end? Or do you
want both elements to appear at the same time? Or doesn't it matter?


FWIW, Ruby 1.9 seems to keep the original insertion order, reassiging a
value to an existing key leaves the order unchanged:

$ irb1.9
irb(main):001:0> a = {a: 1, b: 2, c: 3}
=> {:a=>1, :b=>2, :c=>3}
irb(main):002:0> a.keys
=> [:a, :b, :c]
irb(main):003:0> a[:b] = 4
=> 4
irb(main):004:0> a.keys
=> [:a, :b, :c]
irb(main):005:0> a
=> {:a=>1, :b=>4, :c=>3}
irb(main):006:0>

At least my somewhat out of date 1.9 does

$ ruby1.9 -v
ruby 1.9.0 (2008-03-21 revision 0) [i686-darwin9.2.2]
 
A

ara.t.howard

Hi,
I would like to know if it's possible to insert values in a Hash and
then extract all of them in the same insertion order.

I noticed that if I then try to print the content of an Hash using
"each" the order is not the same as the insertion.

Thanks


gem install orderedhash

a @ http://codeforpeople.com/
 
J

jim finucane

[Note: parts of this message were removed to make it a legal post.]

If scale is needed this has been implemented by Takuma Ozawa as a very
efficient RB tree which I used on a Mac:

sudo gem install rbtree
irb
require 'rbtree'
a=RBTree.new
a['x']=1
a['z']=2
a['y']=3
a
============> #RBTree:{'x'=>1,'y'=>3,'z'=>2}
 
A

ara.t.howard

If scale is needed this has been implemented by Takuma Ozawa as a very
efficient RB tree which I used on a Mac:

sudo gem install rbtree
irb
require 'rbtree'
a=RBTree.new
a['x']=1
a['z']=2
a['y']=3
a


cfp:~ > cat a.rb
require 'rubygems'
require 'rbtree'


# rbtree is sorted by the keys 'natural' sort order
# *not* the insertion order

rb = RBTree.new

rb['z'] = 3
rb['y'] = 2
rb['x'] = 1

rb.each do |key, value|
puts "#{ key } : #{ value }"
end



cfp:~ > ruby a.rb
x : 1
y : 2
z : 3


a @ http://codeforpeople.com/
 
L

Lloyd Linklater

From: Me Me [mailto:[email protected]]
# I would like to know if it's possible to insert values in a Hash and
# then extract all of them in the same insertion order.

only in ruby 1.9

Well, that is not *entirely* true.

h={}
p h
h[1]=1
p h
h[2]=1
p h
h[3]=1
p h
h
p h
h[1.5]=1
p h
h
p h
h[0]=1
p h
h
p h

yields:

{}
{1=>1}
{1=>1, 2=>1}
{1=>1, 2=>1, 3=>1}
{1=>1, 2=>1, 3=>1}
{1=>1, 2=>1, 3=>1, 1.5=>1}
{1=>1, 2=>1, 3=>1, 1.5=>1}
{1=>1, 2=>1, 3=>1, 1.5=>1, 0=>1}
{1=>1, 2=>1, 3=>1, 1.5=>1, 0=>1}


in JRUBY 1.1 which I am running on windows under netbeans.
 

Ask a Question

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

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,776
Messages
2,569,603
Members
45,189
Latest member
CryptoTaxSoftware

Latest Threads

Top