Operational transformationについて、その１

　鉄は熱いうちに打てってことで、
GoogleWaveでの並行編集処理の基本アルゴリズムであるOperational transformationの復習。

　よく解らないモノは、書き出してみると良いってことで
以下、Operational transformation - WikipediaのBasics,OT Functionsを参考に
Rubyで基本アルゴリズムを実装。

class Operation
  attr_accessor :p
  attr_reader   :c,:sid
  
  def initialize p,c,sid;  @p,@c,@sid = p,c,sid;  end
end

class InsOp < Operation
  attr_reader :op
  
  def initialize p,c,sid
    super(p,c,sid);    @op = :ins
  end
end

class DelOp < Operation
  attr_reader :op
  
  def initialize p,c,sid
    super(p,c,sid);    @op = :del
  end
end

    

class String
  def apply op
    case op.op
    when :ins
      insert op.p,op.c
    when :del
      raise "err" unless self[op.p,1] == op.c
      slice! op.p
    end
  end
  
  def T op1,op2
    case
    when op2.nil?
      apply op1
    when op1.p < op2.p
      apply op1
    when (op1.p == op2.p and op1.sid < op2.sid)
      apply op1
    else
      op1 = op1.clone
      op1.p += 1
      apply op1
    end
  end
end

o1 = InsOp.new(0,"x",0)
o2 = DelOp.new(2,"c",1)


server = "abc"
server.T o1,nil
server.T o2,o1
p server


client = "abc"
client.T o2,nil
client.T o1,o2
p client

　このアルゴリズムだけだと、serverとclientが結局交互に操作される前提でないと破綻するｗ；
まあ基本アルゴリズムなんで実際動作させるにはイロイロ足りてないでしょうね＾＾；

調べることいっぱい＞＜