On Sun, 4 Jun 2006, Victor Shepelev wrote:

> Hi all.
>
> Is somewhere __effective__ realization of "sorted list" container?
> ("effective" here means "right algorithm", not "written in C")
>
> Thanks.
>
> V.

if you can't use C then you rule out every single one of ruby's built-ins ;-)

rbtree is very good - i've been using it for years - i'd highly reccomend
compiling it up and running with it

     harp:~ > cat a.rb
     require 'rbtree'
     class SortedList
       def initialize *elems
         @rbt = RBTree.new
         insert *elems
       end
       def insert *elems
         elems.each{|e| @rbt[e] = e}
         self
       end
       alias_method "<<", "insert"
       def to_a() @rbt.values end
       def inspect() to_a.inspect end
       class << self
         alias_method "[]", "new"
       end
     end

     sl = SortedList[ 0, 3, 1, 4, 2 ]
     p sl

     sl << -1 << 5
     p sl


     harp:~ > ruby a.rb
     [0, 1, 2, 3, 4]
     [-1, 0, 1, 2, 3, 4, 5]


on a side note - rbtree is amazingly fast.

regards.

-a
-- 
suffering increases your inner strength.  also, the wishing for suffering
makes the suffering disappear.
- h.h. the 14th dali lama