[clean-list] Text Editor Undo and Persistent Data Structures. ..

[Fabien Todescato]

Please Richard,

	Could you tell me more about what you call "AVL DAG" ? I searched
google and the NEC database library about these, but couldn't find anything
but AVL trees.
	I may guess however than an "AVL DAG" is an implementation of
persistent AVL trees, where efficient persistency is obtained by node
sharing, but I wonder how it is applied to text editing... Do you mean that
along the current text version stored in some array is maintained an AVL
tree indexing somehow the changes made to the text ?

Thanks, Fabien TODESCATO

-----Original Message-----
From: Richard A. O'Keefe [mailto:ok@atlas.otago.ac.nz]
Sent: mardi 29 mai 2001 03:08
To: f.todescato@larisys.fr; mg169780@zodiac.mimuw.edu.pl
Cc: clean-list@cs.kun.nl
Subject: Re: [clean-list] Text Editor Undo and Persistent Data
Structures...


	> My question about that is : is there some deep reason why
unlimited UNDO was
	> not implemented in the text editor, and is it possible to use a
persistent
	> data structure to implement it ? Are efficient persistent data
structures
	> known that support : insertion and deletion in the MIDDLE of a
sequence, and
	> random access within a sequence.
	
Yes.  AVL DAGs, for one.  The total size of an AVL DAG is proportional to
the number of changes (for AVL nodes) plus the amount of text changed (for
character storage).  The access time is proportional to log d, where d is
the number of changes pertinent to the relevant version.


_______________________________________________
clean-list mailing list
clean-list@cs.kun.nl
http://www.cs.kun.nl/mailman/listinfo/clean-list