[Sugar-devel] GSoC Groupthink Update: SharedTextDemo-2

[Benjamin M. Schwartz]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

SharedTextDemo-2 is now available at
http://dev.laptop.org/~bemasc/SharedTextDemo-2.xo.

This version is functionally identical to (and even protocol-compatible
with) version 1.  However, I have redesigned the entire operational
transformation engine.  The new algorithms are still O(N), and the demo is
still too slow to write a whole essay.  However, I can now recommend
Groupthink's SharedTextView to anyone who wants instant collaboration in a
GTK TextView, and is editing less than 1 Kilobyte of text (on an XO-1, or
proportionally more on more powerful machines).

Please contact me if you would like help using Groupthink in your activity.

The new algorithms are moderately interesting.  I have completely removed
all explicit trees, and all walking of trees.  Instead, the new algorithm
maintains two Lists, and a Dict for their inverted index.  This allows
determining the Nth character, locating an existing edit, or computing a
new edit, in constant time.  Actually performing an edit requires O(N)
time, but the O(N) component is now a small, simple loop.  I am hopeful
that these algorithms are amenable to integration with a self-balancing
tree (most likely a customized variant of a Rope), for log-time
performance on all operations.  Time permitting, I may implement this.

- --Ben
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2.0.11 (GNU/Linux)

iEYEARECAAYFAko0Ac8ACgkQUJT6e6HFtqTdLQCfaUT9HilltmtM0803ZGv4Ja4t
bpQAn1LQKDMy1DvD845J8X722m6ayKuv
=ZBzM
-----END PGP SIGNATURE-----