Ordered hash?

ruby-talk
1

Is there a pure-ruby ordered hash? I'm looking for something that will
preserve the order in which key/value pairs were entered. The one on RAA is
buggy http://raa.ruby-lang.org/project/orderedhash/

Will 2.0 come with a good ordered hash?

Thanks

2

Is there a pure-ruby ordered hash? I'm looking for something that will
preserve the order in which key/value pairs were entered. The one on RAA is
buggy http://raa.ruby-lang.org/project/orderedhash/

What's buggy about it? I have an ohash in the code to PDF::Writer that
you're welcome to use.

Will 2.0 come with a good ordered hash?

The native hashing mechanism has been changed to preserve that order, I think.

-austin

···

On Thu, 2 Dec 2004 09:37:44 +0900, itsme213 <itsme213@hotmail.com> wrote:
--
Austin Ziegler * halostatue@gmail.com
               * Alternate: austin@halostatue.ca

3

"itsme213" <itsme213@hotmail.com> schrieb im Newsbeitrag
news:Mptrd.59198$KQ2.38410@fe2.texas.rr.com...

Is there a pure-ruby ordered hash? I'm looking for something that will
preserve the order in which key/value pairs were entered. The one on RAA

is

buggy http://raa.ruby-lang.org/project/orderedhash/

Whenever I hear "ordered hash" then I think of a hash whose keys are
ordered according to a definable order - not necessarily insertion order.
In fact, insertion order seems to me a very special case. Is this really
widely used?

Will 2.0 come with a good ordered hash?

Dunno.

Kind regards

    robert

4

itsme213 wrote:

Is there a pure-ruby ordered hash? I'm looking for something that will
preserve the order in which key/value pairs were entered. The one on RAA is
buggy http://raa.ruby-lang.org/project/orderedhash/

Will 2.0 come with a good ordered hash?

This works fine for me:

class OrderedHash < Hash
   def initialize
     @order_of_keys =
     super
   end

   def =(key, value)
     @order_of_keys.delete(key) if has_key?(key)
     @order_of_keys << key
     super
   end

   def each
     @order_of_keys.each do |key|
       yield key, self[key]
     end
   end
end

Regards,

   Michael

5

* itsme213 <itsme213@hotmail.com> [Dec 02, 2004 14:00]:

Is there a pure-ruby ordered hash? I'm looking for something that will
preserve the order in which key/value pairs were entered. The one on
RAA is buggy http://raa.ruby-lang.org/project/orderedhash/

Having an ordered Hash is like saying that arrays should be indexed by
strings--it's simply not what they are meant to be. My RDSL library
(http://rdsly.rubyforge.org/\) contains an implementation of the Treap
ADT. It works like a Hash, but preserves order. It is implemented much
like a Tree but with Heap-like abilities--hence the name. Anyway, the
items are ordered, not by insertion but by comparison. It does not use
a two-level scheme like OrderedHash seems to use, so there's no wasted
memory on keeping ordering information. Also, benchmarks have shown
that it works very fast, even though it's purely ruby.

If a Treap isn't your style, RDSL also includes a SkipList
implementation, that has similar capabilities to that of a Treap; it's
yet another sorted ADT.

Please, if you haven't already commited to some solution, give RDSL a
try. It needs some testing. I'm going to get back to working on it
when I get time, but until then, some love from other users wouldn't
hurt.

End of plug. Thanks,
  nikolai

···

--
::: name: Nikolai Weibull :: aliases: pcp / lone-star / aka :::
::: born: Chicago, IL USA :: loc atm: Gothenburg, Sweden :::
::: page: www.pcppopper.org :: fun atm: gf,lps,ruby,lisp,war3 :::
main(){printf(&linux["\021%six\012\0"],(linux)["have"]+"fun"-97);}

6

What's buggy about it?

It threw an error on '==', I did not dig much deeper after that.

I have an ohash in the code to PDF::Writer that
you're welcome to use.

I'll take a look, thanks.

> Will 2.0 come with a good ordered hash?

The native hashing mechanism has been changed to preserve that order, I

think.

That's good to know. Is this also in the 1.8 stream, or just 1.9 ?

7

That sounds a bit silly. Wouldn't there be a performance overhead
associated with that? Shouldn't that price be paid only by those
people who want that functionality, given that it can be easily
implemented in C or Ruby?

A C-based extension providing an InsertOrderHash, distributed with
Ruby, would be very handy.

Gavin

···

On Thursday, December 2, 2004, 2:30:00 PM, Austin wrote:

Will 2.0 come with a good ordered hash?

The native hashing mechanism has been changed to preserve that order, I think.

8

Hi,

At Thu, 2 Dec 2004 12:30:00 +0900,
Austin Ziegler wrote in [ruby-talk:122119]:

The native hashing mechanism has been changed to preserve that order, I think.

No.

···

--
Nobu Nakada

9

Michael Neumann ha scritto:

itsme213 wrote:

Is there a pure-ruby ordered hash? I'm looking for something that will
preserve the order in which key/value pairs were entered. The one on RAA is
buggy http://raa.ruby-lang.org/project/orderedhash/

Will 2.0 come with a good ordered hash?

This works fine for me:

<snipcode>
  well, but it works just unless you use a different method to access it (i.e. shift). We definitely need an Association/Map mixin, imo.

10

Be that as it may, it is still necessary to have an insertion-ordered
hash-like object.

I use it in PDF::Writer for page objects that can be referred to
meaningfully -- but still render in the order in which they were
inserted.

-austin

···

On Thu, 2 Dec 2004 23:37:34 +0900, Nikolai Weibull <mailing-lists.ruby-talk@rawuncut.elitemail.org> wrote:

* itsme213 <itsme213@hotmail.com> [Dec 02, 2004 14:00]:
> Is there a pure-ruby ordered hash? I'm looking for something that will
> preserve the order in which key/value pairs were entered. The one on
> RAA is buggy http://raa.ruby-lang.org/project/orderedhash/

Having an ordered Hash is like saying that arrays should be indexed by
strings--it's simply not what they are meant to be.

--
Austin Ziegler * halostatue@gmail.com
               * Alternate: austin@halostatue.ca

11

Whenever I hear "ordered hash" then I think of a hash whose keys are
ordered according to a definable order - not necessarily insertion order.

You are right.

In fact, insertion order seems to me a very special case. Is this really
widely used?

It's not uncommon. And not meant to replace comparison -based ordered ADTs.

12

I have an ohash in the code to PDF::Writer that
you're welcome to use.

I may have to add some Hash conveniences, like default blocks. Thanks.

13

Robert Klemme wrote:

"itsme213" <itsme213@hotmail.com> schrieb im Newsbeitrag
news:Mptrd.59198$KQ2.38410@fe2.texas.rr.com...

Is there a pure-ruby ordered hash? I'm looking for something that will
preserve the order in which key/value pairs were entered. The one on RAA

is

buggy http://raa.ruby-lang.org/project/orderedhash/

Whenever I hear "ordered hash" then I think of a hash whose keys are
ordered according to a definable order - not necessarily insertion order.
In fact, insertion order seems to me a very special case. Is this really
widely used?

I'll reply to this, since an ordered hash is on my wish list.

First of all, if it HAS an order, then it can be sorted (reordered)
in any way you want. The (first) important thing to me is that it
HAVE an order.

Secondly, insertion order should IMO be the default -- because of
hash literals, if for no other reason.

If I say {this=>1, that=>2, other=>3} then that is what I expect
(assuming there is any order at all). I would not want my hash
literals scrambled (assuming some ordering, but one not based on
insertion).

But as long as a hash HAS an order, you can order it any way you
like -- just as we can sort an array any way we like.

And yes, I know there are fundamental differences between hashes
and arrays. :wink:

Hal

14

Nikolai Weibull ha scritto:

* itsme213 <itsme213@hotmail.com> [Dec 02, 2004 14:00]:

Is there a pure-ruby ordered hash? I'm looking for something that will
preserve the order in which key/value pairs were entered. The one on
RAA is buggy http://raa.ruby-lang.org/project/orderedhash/

Having an ordered Hash is like saying that arrays should be indexed by
strings--it's simply not what they are meant to be.

<kidding>
but sometimes they are :slight_smile:
>> a=[1,2]
=> [1, 2]
>> b=['one' ,'two']
=> ['one', 'two']
>> c=a,b
=> [[1, 2], ['one', 'two']]
>> c.assoc 'one'
=> ['one', 'two']
</kidding>

15

Hi,

···

In message "Re: ordered hash ?" on Thu, 2 Dec 2004 15:46:58 +0900, nobu.nokada@softhome.net writes:

The native hashing mechanism has been changed to preserve that order, I think.

No.

Additional information:

Nobu himself made a patch to preserve hash order. I have not decided
yet to merge it. The only concern is performance.

              matz.

16

* itsme213 <itsme213@hotmail.com> [Dec 02, 2004 14:00]:

Is there a pure-ruby ordered hash? I'm looking for something that will

         [...]

Having an ordered Hash is like saying that arrays should be indexed by
strings--it's simply not what they are meant to be.

Be that as it may, it is still necessary to have an insertion-ordered
hash-like object.

Is anyone friendly with the Lua crowd? Could they donate us a
table? :slight_smile: Programming in Lua : 11

         Hugh

···

On Thu, 2 Dec 2004, Austin Ziegler wrote:

On Thu, 2 Dec 2004 23:37:34 +0900, Nikolai Weibull > <mailing-lists.ruby-talk@rawuncut.elitemail.org> wrote:

17

* Austin Ziegler <halostatue@gmail.com> [Dec 02, 2004 16:00]:

> > Is there a pure-ruby ordered hash? I'm looking for something that
> > will preserve the order in which key/value pairs were entered. The
> > one on RAA is buggy http://raa.ruby-lang.org/project/orderedhash/

> Having an ordered Hash is like saying that arrays should be indexed
> by strings--it's simply not what they are meant to be.

Be that as it may, it is still necessary to have an insertion-ordered
hash-like object.

I just gave you one--you seem to have missed the gist of my posting.
(You chopped it right off it seems...)
  nikolai

···

--
::: name: Nikolai Weibull :: aliases: pcp / lone-star / aka :::
::: born: Chicago, IL USA :: loc atm: Gothenburg, Sweden :::
::: page: www.pcppopper.org :: fun atm: gf,lps,ruby,lisp,war3 :::
main(){printf(&linux["\021%six\012\0"],(linux)["have"]+"fun"-97);}

18

Austin Ziegler wrote:

On Thu, 2 Dec 2004 23:37:34 +0900, Nikolai Weibull

Having an ordered Hash is like saying that arrays should be indexed by
strings--it's simply not what they are meant to be.

Be that as it may, it is still necessary to have an insertion-ordered
hash-like object.

I use it in PDF::Writer for page objects that can be referred to
meaningfully -- but still render in the order in which they were
inserted.

How is an "OrderedHash" different from something we might call a "HashedArray", i.e. an array where elements also have a string-like address? With this hybrid type, the array-ness and the hash-ness are orthogonal and neither takes precedence. To me, this says that the only solution (that can maintain an arbitrary ordering) is something like Michael's two-layered implementation, where a hash and an array both refer to the same set of objects internally. Hashing destroys ordering, so you have to pay for it somewhere else.

A more flexible altnerative to Michael's OrderedHash implementation might embed an index within each element, or maintain a parallel hash with indices, then sort the elements by index on demand. If you access the elements in sorted order infrequently, this might be a win for performance.

SkipList and related patterns impose an external sort-ordering on the hash elements, so they would not suit Austin's requirements.

···

--
Glenn Parker | glenn.parker-AT-comcast.net | <http://www.tetrafoil.com/&gt;

19

Something like this (hoping GG doesn't mess up the indenting):

# Assumes you're not initializing with values at the beginning, i.e.
# h = InsertOrderHash.new
# Extension to the general case is left as an exercise for the reader
# (I've always wanted to say that :wink:
class InsertOrderHash < Hash
def initialize(*args)
@insert_order = Array.new
end
def []=(key, val)
@insert_order.push key unless self.key? key
super
end
def each # Assumes block follows
@insert_order.each do |key|
    yield key, self[key]
  end
end

20

There are many more methods than just #= and #each that should be
(re)defined for an insert-order Hash --- including #delete, #delete_if,
#clear, #keys, #values, and others. The OrderedHash on RAA goes a
long way towards (re)defining the methods that might make sense
for such an object.

Fixing (or overriding) the #== method (depending on the semantics
you desire) would probably be a trivial matter (adding a check
that the second hash is also an OrderedHash seems a likely choice). That
module's author has been quick to respond to bug reports/fixes in the
past.

regards,
andrew

···

On Thu, 02 Dec 2004 21:51:40 GMT, itsme213 <itsme213@hotmail.com> wrote:

I have an ohash in the code to PDF::Writer that
you're welcome to use.

I may have to add some Hash conveniences, like default blocks. Thanks.