--- Daniel Brockman <daniel / brockman.se> wrote:
> Eric Mahurin <eric_mahurin / yahoo.com> writes:
> > I do have an implementation written in ruby for
> Array/String
> > where all insertions/deletions at the front of are O(1),
> 
> I would like to see this implementation.  Particularly the
> Ruby
> implementation of an O(1) String#shift.

Below is what I have now.  You make one of these objects by
just passing an array or a string to Indexed2.new.  It only
uses methods in common to Array and String so it doesn't care
which you use (a nice example of taking advantage of duck
typing).  From then on you can treat one of these Indexed2
objects like an Array or String (using only the common
methods).

This class also has algorithmic speedup for all inserts/deletes
in the first half of the array.  Unfortunately, since Array and
String don't have an efficient way to copy data within the
object, you only see an advantage for about the first quarter
of the sequence.  If all of this was written C, inserts/deletes
on both ends of the Array/String would have the same speed
(O(1)) and the average insert/delete time at any position would
be cut in half.  Because it is not written in C, you don't
start seeing an advantage until you get to 50K+ elements.

class Indexed2
    Growth = 0.5
    Max = 1
    Shrink = 0.25
    BreakPoint = 1.0/4 # should be 0.5 with a good copy method
    def initialize(data=@@data_class.new)
        @data = data
        @offset = 0
    end
    def class
        @@data_class = @data.class
        super
    end
    def size
        @data.size-@offset
    end
    alias length size
    def empty?
        (@data.size-@offset).zero?
    end
    def << (v)
        @data << v
    end
    def slice(index,*len)
        index = size+index.to_i if
(index.nonzero?||1.0/index)<0
        @data.slice(index+@offset,*len)
    end
    alias [] slice
    def slice!(index,*len)
        slice(index,*len)
    ensure
        self[index,len[0]||1] = @data.class.new
    end
    def dup
        self.class.new(@data.dup)
    end
    def []=(index,*len_value)
        value = len_value.pop
        return(@data[index+@offset] = value) if
len_value.empty?
        len = len_value[0]
        size = @data.size-@offset
        index = size+index.to_i if
(index.nonzero?||1.0/index)<0
        delta = value.size-len
        if delta.nonzero? and index<(size*BreakPoint).to_i
            size += delta
            len += delta
            offset0 = (offset = @offset-delta)
            if delta<0
                if offset>Max*size
                    offset = (Shrink*size).to_i
                    @data[offset,index] = @data[@offset,index]
                    @data[index+offset,offset0-offset+len] =
value
                else
                    @data[offset,index] = @data[@offset,index]
                    @data[index+offset,len] = value
                end
            else
                if offset<0
                    offset = (Growth*size).to_i
                    @data[index+len+offset,0] =
                        @data[index+@offset,offset-offset0]
                end
                @data[offset,index] = @data[@offset,index]
                @data[index+offset,len] = value
            end
            @offset = offset
        else
            @data[index+@offset,len] = value
        end
    end
    def shift
        slice!(0)
    end
    def pop
        slice!(-1)
    end
    def push(*args)
        args.each { |v| @data << v }
        self
    end
    def unshift(*args)
        value = @data.class.new
        args.each { |v| value << v }
        self[0,0] = value
        self
    end
end




		
__________________________________ 
Yahoo! Mail for Mobile 
Take Yahoo! Mail with you! Check email on your mobile phone. 
http://mobile.yahoo.com/learn/mail