From: Robert Klemme <bob.news@...>
Date: 2003-05-28T18:35:26+09:00
Subject: Re: Binary Tree vs. Hash


"Mauricio Fern�ndez" <batsman.geo@yahoo.com> schrieb im Newsbeitrag
news:20030528084932.GA26844@student.ei.uni-stuttgart.de...

[snip]

> 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.

.... because it's an Array and not a CleverArray.

> 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 ??

AFAIK this is part of 1.8

> We could make it parameterizable to select between implementations as
> different as sorted array, hash or Bloom filter...

I'd prefer separate classes instead of parametrization or a delegation
mechanism. Parametrization is less extensible and less modular.

Cheers

    robert