Re: RE : Piece Table with O(log(n)) operations

From: Martin Sevior (msevior@physics.unimelb.edu.au)
Date: Mon Jan 06 2003 - 20:00:40 EST

  • Next message: Robert: "abiword with recent Xft"

    On Tue, 7 Jan 2003, Joaquin Cuenca Abela wrote:

    > Martin wrote:
    > >
    > > On Sat, 4 Jan 2003, Joaquin Cuenca Abela wrote:
    > >
    > > > I've find a way to get O(log(n)) as the worst case with any
    > > operation
    > > > on the piece table. I've put a description in
    > > > http://e98cuenc.free.fr/wordprocessor/piecetable.html
    > > >
    > > > The main affected class will be pf_Fragments. In the web
    > > page (still
    > > > not finished) I discuss all the gory details.
    > > >
    > >
    > > This is a extremely interesting Joaquin and is very, very cool :-)
    > >
    > > I start to see peicetable performance issues when dealling
    > > with documents
    > > of about 100 pages or larger right now. Particularly when typing or
    > > deleting. You new code would certainly fix those!
    > >
    > > I haven't looked through your code yet but I assume you rewritten the
    > > setNext()/getNext()/setPrev()/getPrev()/getPos() methods in the
    > > piecetable? Right?
    >
    > Just for the record, roughly setNext() is my insertRight(), getNext() is
    > ++, setPrev() is insertLeft(), getPrev() is -- and getPos is
    > documentPosition().
    >

    When we get to merging this in I suggest you keep the getNext/setNext etc.
    I think everything will Just Work if you maintain the Logical idea of a
    doubly linked list and keep the current interface to the rest of the
    piecetable code as it is.

    Cheers

    Martin

    This archive was generated by hypermail 2.1.4 : Mon Jan 06 2003 - 20:04:47 EST