From: Josh Cheek <josh.cheek@...>
Date: 2011-07-17T01:10:33+09:00
Subject: Re: does OrderedHash exist?

--20cf3071c73a61761b04a83201d9
Content-Type: text/plain; charset=ISO-8859-1

On Sat, Jul 16, 2011 at 7:32 AM, Robert Klemme
<shortcutter@googlemail.com>wrote:

> On Sat, Jul 16, 2011 at 9:34 AM, Oren Shani <orenshani7@gmail.com> wrote:
> > I created a class called, HashArray which implements a pretty
> > straightforward Hash with order object. Content can be added, deleted,
> > reordered, etc, and then there is the as_array method that enables using
> > the object as an array.
>
> I'm curious how you manage to keep the data structure ordered and keep
> access time O(1).  It surely is O(1) since it's called _Hash_Array,
> isn't it?
>
> Kind regards
>
> robert
>
> --
> remember.guy do |as, often| as.you_can - without end
> http://blog.rubybestpractices.com/
>
>

You don't necessarily have to keep it ordered the whole time. Order only
matters when you try to access it. So you could keep all the hash
properties, then as soon as someone tries to do something ordered, build a
heap O(n) and then iterate as you remove the minimum. Essentially heap sort,
but yielding each object as you remove it.

If you track whether it is sorted, then the first iteration is O(n lg n) and
the rest after that are O(n). Of course, if you keep adding lots of keys and
iterating frequently, then iteration performance would suffer. Seems like in
cases like that, you have to make a trade off somewhere

--20cf3071c73a61761b04a83201d9--