Re: FYI: GtkText design progress

[Derek Simkowiak <dereks kd-dev com>]

> I have read all of your posting carefully.

	Thank you!  I sincerely appreciate your time.

> So you plan to implement text buffer as a linear gapped array and
> properies as a list.

	It was already implemented this way.  I am simply trying to clean
up the interface (to make the code easy to improve and maintain) and
implement some new features.

	I was hoping to re-use most of the algorithms and semantics that
were already there (sans the "LineBufferCache" and some other stuff).
Most of my original work will be in the displaying algorithms, scrolling, 
and linewrap.

> Seems it's a strange mixture, because you have to iterate through
> properties list on text change anyway.

	It turns out to not be too bad.  One of the worst real-world
scenarios I can think of is C syntax highlighting, which would have, say,
four different text properties on a single line of C code (that is only
two or three dozen characters long).

	If your single C code file is 10,000 lines long (which is
relatively large for a well-written, modular program) then that could be
40,000 list elements for your file.  Incidentally, I'm making these
numbers up in my head.

	Doing a single pointer reference, plus an integer addition, is
fairly fast, even for 40,000 elements.

	I plan to reduce the number of references and additions with the
following algorithm.  Imagine moving from the end of the file, to
someplace near the middle (or from the beginning of the file to someplace 
near the beginning)--you wouldn't want to iterate from the tail backwards 
to the beginning of the file, or vice versa.  So:

1) Assume the number of TextProperties are distributed (more or less)
evenly throughout the buffer.

2) Calculate, as a percentage of the total buffer size, which of the
following is smallest:

	a) The distance from the last known location to the new location
	b) The distance from the beginning of the file to the new location
	c) The distance from the end of the file to the new location

	...then, iterate through the TextPropery linked list to the new
location from (a) the current location, (b) the head of the list, or (c)
the tail of the list.  This will greatly optimize a jump from, say, the
end of a 10Megabyte file to the very beginning.

	I do agree that a linked list approach is not the best way to go.
But at this point in time, while Miguel and Federico talk about the
advanced features of Gnome 2.0, and others are worrying about the improved
GObject system of Gtk+ 1.4, us application developers are stuck without
even a decent widget to implement a text editor.  Qt is light years ahead
of us in this regard, and hence their kIDE application which is bound to
draw application developers towards KDE, and away from Gnome.  So I'm
trying to go with what I have seen before and what is easiest to
understand, and what will get me back to my text-editor application as
soon as possible...

> So why not to implement data storage as a balanced binary tree?
[...]
> Do we have binary tree data storage class in glib? ;)

	Yes, we do have a balanced tree in Glib, but what will be the
nodes of your tree? A single character?  Or a word?

	Also, I can't imagine (at 1:30am) how to make an easy to read line
drawing algorithm if we use a tree.  With the gapped text buffer,
optimizing drawing a line of text to an X window is a fairly
straightforward problem.  Nedit is a prime example of a fast, usable, and
easy-to-understand editor application.  Walking a tree, tracking nodes,
using custom structures at the nodes... it all sounds like a fast headache
:).

	I actually read a Ph.D. thesis where the guy used a tree to store
lexical tokens in the nodes.  It was for a development IDE that included
version control and syntax highlighting, all using the tree.  It was a
brilliant piece of work, but I don't have any source code or a functional,
working example to evaluate.

	Again, thank you for your feedback.


--Derek