Re: Immutable Ropes

On Tue, 15 Mar 2005, Nikolai Weibull wrote:

>  Another nice property is that as one abstracts away the
> pointer-to-char, ropes can be created lazily from IO or other
> generators of data.  As an example, say that we want a String of one
> million a's s = "a" * 1000000 With a Rope, we could have written this
> as: r = Rope.new("a", 1000000) and that could be represented very
> efficiently.  A better example is if we would like to search the
> concatenation of two strings for a regular expression.  Using only
> Strings, we would have to write this as:

One related project is my old project called MetaRuby. I presented it at
the Europ臺sche Ruby Konferenz 2004 (although I wrote all of the code in
2001).

MetaRuby has a concept of virtual strings, that are (by default) mutable
(and freezable), but it's easy to make examples like the ones you give
with it. Here's example code for MetaRuby, that exhibits the kind of
things you can do with mutable strings that have shared mutable segments.
It wouldn't be too much extra work to add a few more variants like one
that's immutable with copy-on-write, O(1) catenation, etc.



require "Hollow/Array"
require "Hollow/String"

module SubList
  # there could/should be a notifier so that when elements are
  # inserted before the @i position, that position is incremented, etc.
  # this requires an Observable Array, which does not exist yet.
  def initialize(list,i,n) @list,@i,@n = list,i,n end
  def length; @n; end
  def get(i) @list[@i+i] end
  def get_seq(i,n) @list[@i+i,n] end
  def put(i,v) @list[@i+i]=v end
  def put_seq(i,n,v)
    raise "can't insert/delete" if v.length!=n
    @list[@i+i,n]=v
  end
end
class SubArray;  include HollowArray,  SimpleArrayP,  SubList
  def self.new(*a) if a.length==0 then "" else super end end
end
class SubString; include HollowString, SimpleStringP, SubList
  def self.new(*a) if a.length==0 then "" else super end end
end
class Array;  def part(i,n)  SubArray.new(self,i,n) end end
class String; def part(i,n) SubString.new(self,i,n) end end

x="machin truc patate"
x.part(7,4).upcase!
p x #==> "machin TRUC patate"
y=x.part(4,5)
p y #==> "in TR"
y.downcase!
p y #==> "in tr"
p x #==> "machin trUC patate"
y.tr! 'a-z','n-za-m'
p x #==> "machva geUC patate"
y[2]="\n"
p x #==> "machva\ngeUC patate"
p y.map {|line| "[#{line.chomp}]" }.join
#==> "[va][ge]"



(However, MetaRuby really should be updated for Ruby 1.8... *I KNOW*)

_____________________________________________________________________
Mathieu Bouchard -=- Montr饌l QC Canada -=- http://artengine.ca/matju