[gsharp-cvs] CVS update: gsharp/Flexichain/Doc/flexichain.tex

[Robert Strandh]

Update of /project/gsharp/cvsroot/gsharp/Flexichain/Doc
In directory common-lisp.net:/tmp/cvs-serv27009/Doc

Modified Files:
	flexichain.tex 
Log Message:
Completely modified the implementation of cursors. 

Now, a cursorchain can hold a large number of cursors without any
negative impact on performance.

For cursorchains, the flexichain buffer now has a parallel that holds
per-element lists of cursors that stick to that element.  

Introduced new generic functions in the internal protocol fill-gap and
resize-buffer.

Updated the documentation accordingly. 


Date: Fri Aug  6 08:47:36 2004
Author: rstrandh

Index: gsharp/Flexichain/Doc/flexichain.tex
diff -u gsharp/Flexichain/Doc/flexichain.tex:1.1 gsharp/Flexichain/Doc/flexichain.tex:1.2
--- gsharp/Flexichain/Doc/flexichain.tex:1.1	Sun Aug  1 08:27:20 2004
+++ gsharp/Flexichain/Doc/flexichain.tex	Fri Aug  6 08:47:36 2004
@@ -526,12 +526,18 @@
 
 \subsection{Performance}
 
-We assume that the number of cursors of a particular chain is
-relatively small.  Although under normal circumstances simple
-operations like insert and delete will not take a time proportional to
-the number of cursors, it is possible that cursors need to be
-updated from time to time.  We do not promise any bound on complexity
-for a large number of cursors.
+There can be a very large number of cursors in a chain without any
+negative impact on performance.  In particular, a sequence of insert
+operations is not affected by the number of cursors of the chain.
+For insert operations, we maintain the complexity proportional to the
+distance between two consecutive positions.  
+
+A delete operation takes time proportional to the number of
+left-sticky cursors to the right of the element to delete plus the
+number of right-sticky cursors to the left of it. 
+
+The only bad case is thus a delete operation of an element with an
+unbounded number of cursors sticking to it. 
 
 \subsection{Protocol classes and functions}
 
@@ -683,7 +689,9 @@
 \section{Implementation of the \texttt{flexicursor} protocol}
 
 Cursors are stored as lists of weak references so that they can be
-recycled when no longer referenced by client code. 
+recycled when no longer referenced by client code.  A vector that
+parallels the one holding elements of the flexichain holds per-element
+lists of cursors that stick to that element. 
 
 A cursor contains its \textit{index in the vector} as opposed to its
 \textit{position in the sequence}.  This method avoids most updates of
@@ -693,11 +701,12 @@
 right-sticky cursors, we store $p$ itself. 
 
 After a delete operation, cursors with indexes equal to the old value
-of \texttt{gap-end} need to be updated to the new value of
-\texttt{gap-end}, including the cursor that was used in the call.
+of \texttt{gap-end} need to be updated.  Right-sticky cursors will be
+attached to the index corresponding to the new value of
+\texttt{gap-end}, whereas left-sticky cursors get attached to the
+position immediately preceding \texttt{gap-start}. 
 
-After an insert operation, only the cursor used in the call needs to
-be incremented.  All other cursors remain the same.
+Insert operations do not affect cursors at all. 
 
 Mixing of \texttt{flexicursor} and \texttt{flexichain} editing
 operations is possible thanks to an internal protocol for moving the