From: "Mauricio Fernández" <batsman.geo@...>
Date: 2003-05-28T17:49:34+09:00
Subject: Re: Binary Tree vs. Hash

On Wed, May 28, 2003 at 05:14:52PM +0900, Robert Klemme wrote:
> Yeah, that's a major point, as I tried to point out.  Imagine
> 
> foo=[]
> foo << 5 << 2 << -1 << 7
> p foo
> 
> foo.sort!{|a,b| a<=>b}
> p foo
> p foo.sorted?
> 
> foo.sort!{|a,b| b<=>a}
> p foo
> p foo.sorted?
> 
> printing
> [5, 2, -1, 7]
> [-1, 2, 5, 7]
> true
> [7, 5, 2, -1]
> true
> 
> Anybody reading the sorted flag must know at the same time, which ordering
> was applied.  So you have to record some of the information outside this
> array which IMHO is not a good idea.
> 
> > An overall better approach might be a SortedArray
> > inheriting from Array -- it could even have its own
> > definitions of << and so on that would preserve
> > sorting. And the method of sorting would (could/
> > should/might?) be fixed on an instance basis.
> 
> Exactly, apart the problems with []= remain, as others have pointed out.

Um, now I begin to see the merits of the original idea:

batsman@tux-chan:/tmp$ expand -t2 ap.rb

module ClearSortedFlag
  def clear_flag_at(*syms)
    syms.each do |meth|
      module_eval <<-EOF
      def #{meth}(*args,&block)
        @sorted = false
        super(*args,&block)
      end
      EOF
    end
  end
end

class CleverArray < Array
  extend ClearSortedFlag

  def initialize(*args)
    @sorted = false
  end

  def sort!(&block)
    @sorted = true
    @sblock = block if block
  end

  clear_flag_at("[]=".intern, :clear, :collect!, :compact!,
  :concat, :fill, :flatten!, :map!, :push, :replace, :reverse,
  :unshift)

  def include?(anObject)
    return super unless defined? @sorted and @sorted
    # perform binary search using @sblock unless nil
    # I am too lazy to implement it now :-)
    # anyway this had better be done in C
  end
end

Note we lose the "@sorted" feature when a new Array object is returned.

It is possible to redefine the methods in Array directly, using
alias_method instead of super. This should be essentially transparent
and straightforward, but I don't know if the speed increase would really
matter. When it really *does*, it is probably better to use a Set
class and give it hints on what can be done to increase speed/decrease
memory needs.

Perhaps we could add a separate core class to Ruby ==> Set ??
We could make it parameterizable to select between implementations as
different as sorted array, hash or Bloom filter...

-- 
 _           _                             
| |__   __ _| |_ ___ _ __ ___   __ _ _ __  
| '_ \ / _` | __/ __| '_ ` _ \ / _` | '_ \ 
| |_) | (_| | |_\__ \ | | | | | (_| | | | |
|_.__/ \__,_|\__|___/_| |_| |_|\__,_|_| |_|
	Running Debian GNU/Linux Sid (unstable)
batsman dot geo at yahoo dot com

Less is more or less more
	-- Y_Plentyn on #LinuxGER