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

[Benjamin M. Schwartz]

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

Download:
http://bemasc.net/~bens/SharedTextDemo-5.xo

Requires Sugar 0.82 or better.

Short:
This version is faster.  It's fast enough that I can conscionably
recommend it for use with any document that a young student might be
likely to write.  For very long documents, joining a shared session still
takes a considerable amount of time, but there is no delay while typing.

If you would like to add text sharing to your activity, I will gladly show
you the way.

Long:
The shared-text datastructure is represented as a tree of edits, with each
edit referenced to its parent.  Originally, SharedTextDemo computed edits
by explicitly walking this tree every time an edit was made.  This proved
too slow, as the tree tends to have depth O(N) for N characters, and so it
was replaced by a look-up array, which mapped between characters in the
document and the insertions that created those characters.  This still
required O(N) operations for insertion into the middle of the array, but
at least the O(N) represented a tight for-loop.

SharedTextDemo-5 reimplements the lookup-array as a monoid-annotated
self-balancing binary tree, using the AA balancing algorithm [1][2].
Additionally, this tree has a slightly unusual bidirectional linking
structure, in which nodes keep references to their parents as well as
their children, and the balancing algorithms maintain the both directions
of linking.  The net result is O(log(N)) performance for lookup,
insertion, deletion, modification, and search, as well as O(1) succession.

Actually, the data structure in SharedTextDemo-5 is a more complicated
beast, a "HideList".  It needs to maintain not only the positions of all
visible characters, but also all deleted characters, and be able to locate
both "the Nth character" and "the Nth visible character".

If you are interested in these data structures, you can see the code at
http://dev.laptop.org/git/projects/dobject/tree/groupthink/aatree.py

[1] http://scienceblogs.com/goodmath/2009/05/finally_finger_trees.php
[2] http://en.wikipedia.org/wiki/AA_tree
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2.0.11 (GNU/Linux)

iEYEARECAAYFAkpo84gACgkQUJT6e6HFtqSolACglW8DXc8PgJdcbXBHmCv+TVGc
6mgAnRxudNXvakjmWZkuT1JBqiImNzDU
=mRJf
-----END PGP SIGNATURE-----