[Edbrowse-dev] Setters and Post Scan

[Karl Dahlke <eklhad@comcast.net>]

> > perhaps growing as n^2 for the number of html tags,

> Out of interest, how do you arrive at this figure?

Mostly a gut feeling.
As background, consider my garbage collector for lines in a buffer.
This is just edits, no browsing.
Make a change, then make another change, so that there are now some lines
that you won't need even if you undo.
How do I determine and free those lines?
By comparing two maps of pointers.
The pointers in A, not in B, are not needed and can be freed.
The first version was simple and stupid, looking for things in A not in B,
and ran in n^2 time.
This didn't matter for a few years, until I started editing some really big files.
You also have started editing some large files.
If a file has a million lines, thatt's a trillion operations per edit.
I enter a substitute command and wait 2 minutes for a response.
I don't think so!
So a few years ago I rewrote it using quicksort and and internal form of comm,
and it is plenty quick, even for large files.
Look for qsort() in buffers.c.

Now fast forward to today; I am scanning a tree of js objects
and comparing the tags that are implied by those objects with the tags we already have,
and doing, essentially, a diff, so I can report to the user what has changed,
which a sighted person would simply see as a change to something on the screen.
It is very likely that there are quick ways to run this comparison,
but if there absolutely aren't,
and if a web page rewrote itself in a nasty way that like changed every other line,
then maybe the comparison would be as awful as n^2.
But as I say I expect there will be better algorithms
once we really dive into it,
and I'm quite sure that web pages only change small portions of themselves,
the text in various	 boxes, or menus, etc,
and don't completely rewrite themselves,
so that's why I don't think it will be a performance issue,
even if we implement it in a rather direct and plodding way.

Karl Dahlke