Is there a hash-like class that maintains insertion order

ruby-talk
1

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

2

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

···

On Mon, 26 Sep 2005, 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/&gt;
Recursive Design Inc. -- <http://www.recursive.ca/&gt;
Raconteur -- <http://www.raconteur.info/&gt;

--

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

===============================================================================

3

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.

···

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/&gt;
Recursive Design Inc. -- <http://www.recursive.ca/&gt;
Raconteur -- <http://www.raconteur.info/&gt;

4

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

Kent.

···

On Mon, 2005-09-26 at 11:21 +0900, 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/&gt;
Recursive Design Inc. -- <http://www.recursive.ca/&gt;
Raconteur -- <http://www.raconteur.info/&gt;

5

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

···

On Sep 25, 2005, at 10:34 PM, Ara.T.Howard wrote:

On Mon, 26 Sep 2005, 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/&gt;
Recursive Design Inc. -- <http://www.recursive.ca/&gt;
Raconteur -- <http://www.raconteur.info/&gt;

  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 -- blogs at <http://www.recursive.ca/hutch/&gt;
Recursive Design Inc. -- <http://www.recursive.ca/&gt;
Raconteur -- <http://www.raconteur.info/&gt;

6

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

···

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/&gt;
Recursive Design Inc. -- <http://www.recursive.ca/&gt;
Raconteur -- <http://www.raconteur.info/&gt;

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 -- blogs at <http://www.recursive.ca/hutch/&gt;
Recursive Design Inc. -- <http://www.recursive.ca/&gt;
Raconteur -- <http://www.raconteur.info/&gt;

7

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

···

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.

8

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

···

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.

--

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

===============================================================================

9

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&gt;

···

On Sep 26, 2005, at 10:24 AM, Ara.T.Howard wrote:

On Mon, 26 Sep 2005, Bob Hutchison wrote:

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

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