From: Eric Mahurin <eric.mahurin@...>
Date: 2008-03-11T22:39:03+09:00
Subject: Re: Ordered Collection

------=_Part_3798_1422598.1205242750528
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
Content-Disposition: inline

On Tue, Mar 11, 2008 at 7:52 AM, James Gray <james@grayproductions.net>
wrote:

> On Mar 11, 2008, at 3:43 AM, Peter Hug wrote:
>
> > What I really would like is an array that is always ordered. IOW, I
> > want
> > the object to be inserted at the correct location inside the array
> > when
> > the object is added to the array.
> >
> > Is there an efficient way to do this?
>
> You could use a priority queue.  You can see some pure Ruby code for
> this in an old Ruby Quiz:
>
> http://www.rubyquiz.com/quiz40.html
>
> James Edward Gray II
>
>
Heaps have some limitations that might not work for your application:

* can't delete elements
* can't find an arbitrary element - and iterate over elements in its
vicinity

A tree (red-black, AVL, etc) is quite a bit more flexible if you need more
functionality.  In terms of big-O performance (runtime and memory) and
functionality, I don't believe heaps offer advantages.

For my day job, I use mostly use C++ that has heaps and red-black trees at
your fingertips (in STL).  Occasionally, I've started with a heap because it
fit the functional requirements (and I know it is more memory efficient -
but, not for big-O).  Later, many times I've had to swap it for a tree (i.e.
set or map in STL), because I needed more functionality.

Ruby, unfortunately is really lacking on this front.  When doing geometric
stuff, I find every ounce of C++ STL useful.  An STL-like ruby lib would be
useful.  External iterators are also very important.  Ruby's normal internal
iterators (what others might call visitors) don't have the same flexibility
(caller can go forward/backward/read/write/erase/insert at will).

------=_Part_3798_1422598.1205242750528--