Armel Asselin:
however I do not see in which way it would improve the performance (by an order of magnitude such as N or log N) because as long as we need to update the "displayLine" entry for each following line, we will still have N*M update time (N being number of insertions, M being the lines after insertion position), which is in worst case N^2 when inserting in front of line 1.
Partitioning does not have to 'update the "displayLine" entry for each following line'. As long as there is strong locality of modification (and from your description it looks like each line will be inserted adjacent to the previous insertion or if not, at least close) its constant time per insertion. Partitioning adds to SplitVector the concept of a 'step'. All positions after the step have the step value added to them when returned. Thus if a line is inserted immediately after the previous insertion then the step is moved 1 location and the step value is incremented. This is used in current Scintilla to maintain the line start positions. It may take some time to incorporate this in Scintilla so you may as well do something in your own copy to defer updates till the end of a sequence. However, I don't expect maintaining ContractionState to be expensive enough to add an extra feature, mostly because of the maintenance cost. Neil _______________________________________________ Scintilla-interest mailing list [email protected] http://mailman.lyra.org/mailman/listinfo/scintilla-interest
