“Eugene K.” [email protected] wrote in message
news:JkJDi.3699$tY2.57@trndny01…
“Eric M.” [email protected] wrote in message >
I added dups to Kalenkovich’s code and saw the same 150+MB usage as
Munkby’s dup code. I still don’t understand this.
I’m not sure about Gustav’s code, but for my one memory in duping option
is eaten by normalization, that do not really need any duping at all.
–EK
I’ve modified my code to avoid duping in normalization - at a cost of
ugliness 
(too ugly for quiz submission, and anyway, too late
You can see that memory is fine now.
class NilClass
def length; 0; end
end
class String
def shift
return nil if empty?
res=self[0]
self[0]=“”
res
end
end
class Rope
attr_reader :length, :left, :right
def initialize(left=nil,right=nil,dup=true)
@left = left ? left.kind_of?(Rope)&&dup ? left.dup : left : nil
@right = right ? right.kind_of?(Rope)&&dup ? right.dup : right : nil
@length=left.length+right.length
end
def append(what, dup=true)
len=what.length
if (len>0)
@left=self.dup if @right.length>0
@right=what.kind_of?(Rope)&&dup ? what.dup : what
@length+=len
end
self
end
alias << append
def prepend(what, dup=true)
len=what.length
if (len>0)
@right=self.dup if @left.length>0
@left=what.kind_of?(Rope)&&dup ? what.dup : what
@length+=len
end
self
end
def to_s
@left.to_s + @right.to_s
end
def
return i.match(self.to_s)[0] if i.kind_of? Regexp
if i.kind_of? Range
pos,last=i.first,i.last
pos = @length+pos if pos<0
last = @length+last if last<0
return nil if pos<0 || last<0
return slice(pos,last-pos+1)
end
i = @length+i if i<0
return nil if i<0 || i>@length-1
llen = @left.length
i<llen ? @left[i] : @right[i-llen]
end
def []=(i,val)
#fixnum only
i = @length+i if i<0
“”[i]=0 if i<0 || i> @length-1
@length+=val.length-1
llen = @left.length
i<llen ? @left[i]=val : @right[i-llen]=val
end
def slice(pos,len)
return pos.match(self.to_s)[len] if pos.kind_of? Regexp
pos = @length+pos if pos<0
return nil if pos<0 || len<0 || pos>@length-1
llen = @left.length
return @left.slice(pos,len) if pos+len<=llen || ! @right
return @right.slice(pos-llen, len) if pos>=llen
Rope.new(@left.slice(pos,llen-pos),@right.slice(0,len+pos-llen))
end
def shift
return nil if @length==0
@length-=1
res = @left.length>0 ? @left.shift : @right.shift
@left=nil if @left.length==0
@right=nil if @right.length==0
res
end
def normalize
r=Rebalancer.new(@length)
self.traverse { |str| r.append(str) }
@left, @right=r.get_ropes
self
end
def traverse(&blck)
@left.kind_of?(String) ? yield( @left) : @left.traverse(&blck) if
@left
@right.kind_of?(String) ? yield( @right) : @right.traverse(&blck) if
@right
end
end
class Rebalancer
def initialize len
@limits=[1,2]
@slots=[]
n=2
@limits<< n = @limits[-2] + @limits[-1] while n<len
end
def append str
@slots[0] = @slots[0] ? Rope.new( @slots[0],str, false) : str
i=0
while @slots[i].length>@limits[i]
@slots[i+1] = @slots[i+1] ? Rope.new( @slots[i+1],@slots[i],false)
:
@slots[i]
@slots[i] = nil
i+=1
end
end
def get_ropes
@slots.compact!
(@slots.length-1).times { |i|
@slots[i+1]=@slots[i+1] ? Rope.new(@slots[i+1],@slots[i],false) :
@slots[i]
@slots[i]=nil
i+=1
}
[@slots[-1].left,@slots[-1].right]
end
end