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

[Martin Sevior]

Hi Bejamin,
<snip>

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

Or you could just embed libabiword through PyAbiWord , which is
already deployed and allows full scale collaboration :-)

Sorry, I couldn't resist :-)

> 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.
>

This is very similar to what we plan for our next version of our
PieceTable. It appears we have converged onto the same solution.

Do you want to help us implement it? I hope to get started within the
next month.

> 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


Thanks very much for the links. Here are a few you may be interested in too.

http://e98cuenc.free.fr/wordprocessor/piecetable.html
http://mirror.linux.org.au/pub/linux.conf.au/2008/Wed/mel8-083.ogg
http://www.abisource.com/wiki/AbiCollab

Cheers,

Martin


> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v2.0.11 (GNU/Linux)
>
> iEYEARECAAYFAkpo84gACgkQUJT6e6HFtqSolACglW8DXc8PgJdcbXBHmCv+TVGc
> 6mgAnRxudNXvakjmWZkuT1JBqiImNzDU
> =mRJf
> -----END PGP SIGNATURE-----
> _______________________________________________
> Sugar-devel mailing list
> Sugar-devel at lists.sugarlabs.org
> http://lists.sugarlabs.org/listinfo/sugar-devel
>