log(n) PT works!!!

Hi everyone,
                    With this commit abiword works with the log(N)
PieceTable designed by Joaquin Cuenca Abela and mostly implemented by
our Google Summer of Code student Aditya Manthramurthy. I've provided
many bug fixes.

We've simply re-implented the low level src/text/ptbl/xp/pf_Frag, and
pf_Fragments methods with equivalents from Joaquin's Red/Black tree.

Our pf_Frag's used to be in a doubly linked list with an ordered
vector. This allowed searches in log(n) times but inserts and deletes
happen in linear time.
Operations like insert table and large pastes required time
proportional to N^2 where N is the size of the document.

Now they reside in Joaquin's red/black tree. This allows
searches/inserts/deletes in logorithmic time.

This all works very nicely from my tests so far. More tests and
timings to follow.

To see more about why this is very exciting have a read of these two links.

http://www.abisource.com/wiki/AbiWordDevelopment#PieceTable_speedups.

http://e98cuenc.free.fr/wordprocessor/piecetable.html

With this in place we have the capability to scale to tables of many
thouasands of rows of tables and document sizes ten times bigger than
we can comfortably handle today.

Cheers!

Martin

Author: msevior
Date: 2009-08-19 04:28:36 +0200 (Wed, 19 Aug 2009)
New Revision: 27746

Modified:
   abiword/branches/lognpt/src/text/ptbl/xp/pf_Frag.cpp
   abiword/branches/lognpt/src/text/ptbl/xp/pf_Frag.h
   abiword/branches/lognpt/src/text/ptbl/xp/pf_Frag_Text.cpp
   abiword/branches/lognpt/src/text/ptbl/xp/pf_Fragments.cpp
Log:

Allow the Text Fragments to change in size and adjust the tree when then do.

ABiWord works with log(n) PT now!!!!!!!!
Woot! Woot!
Received on Wed Aug 19 04:53:04 2009