From: Peter Hug <pete@...>
Date: 2008-03-12T06:53:12+09:00
Subject: Re: Ordered Collection

Robert Klemme wrote:
> 2008/3/11, Peter Hug <pete@kapiti.co.nz>:
>> If class X has a method <=>(aX), I can sort an Array containing
>>  instances of X using Array.sort!.
>>
>>  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?
> 
> Yes.  You can either use binary search on the Array to insert or you
> use a Tree.  Both can be found in RAA:
> 
> http://raa.ruby-lang.org/project/ruby-bsearch/
> http://raa.ruby-lang.org/project/ruby-rbtree/

Thanks Robert, this RAA is a little treasure chest!

Actually, I found the the bsearch array extensions do a fantastic job 
for what I need. The only thing I added was a couple of methods to 
add/remove elements:

#
# Add an element at the correct location (does not allow duplicates)
#
def bsearch_insert(element)
  bounds = bsearch_range { | x | x <=> element }
  if bounds.first == bounds.last then
    self.insert(bounds.first, element)
    bounds.first
  else
    nil
  end
end

#
# Delete an element from the array
#
def bsearch_delete(element)
  idx = bsearch_first { | x | x <=> element }
  self.delete_at(idx) unless idx == nil
end

Thanks heaps (to all the other people who replied too of course!)
Pete
-- 
Posted via http://www.ruby-forum.com/.