DynamicSelectionList: optimize updating on buffer modification

Now that we know selections are sorted, we can get the set of selections
needing updating in log(n) time using a binary search, for modification
not changing the line count, this makes updating selections run in log(n)
instead of n.

1 files changed, 69 insertions, 37 deletions

diff --git a/src/dynamic_selection_list.cc b/src/dynamic_selection_list.cc
index 647bf22b..bca16293 100644
--- a/src/dynamic_selection_list.cc
+++ b/src/dynamic_selection_list.cc
@@ -72,62 +72,94 @@ void DynamicSelectionList::check_invariant() const
 #endif
 }
 
-static void update_insert(BufferIterator& it,
-                          const BufferCoord& begin, const BufferCoord& end)
+namespace
 {
-    BufferCoord coord = it.coord();
-    if (coord < begin)
-        return;
 
-    if (begin.line == coord.line)
-        coord.column = end.column + coord.column - begin.column;
-    coord.line += end.line - begin.line;
+template<template <bool, bool> class UpdateFunc>
+void on_buffer_change(SelectionList& sels, const BufferCoord& begin, const BufferCoord& end, LineCount end_line)
+{
+    auto update_beg = std::lower_bound(sels.begin(), sels.end(), begin,
+                                       [](const Selection& s, const BufferCoord& c) { return std::max(s.first(), s.last()).coord() < c; });
+    auto update_only_line_beg = std::upper_bound(sels.begin(), sels.end(), end_line,
+                                                 [](LineCount l, const Selection& s) { return l < std::min(s.first(), s.last()).line(); });
 
-    it = coord;
+    if (update_beg != update_only_line_beg)
+    {
+        // for the first one, we are not sure if min < begin
+        UpdateFunc<false, false>{}(update_beg->first(), begin, end);
+        UpdateFunc<false, false>{}(update_beg->last(), begin, end);
+    }
+    for (auto it = update_beg+1; it < update_only_line_beg; ++it)
+    {
+        UpdateFunc<false, true>{}(it->first(), begin, end);
+        UpdateFunc<false, true>{}(it->last(), begin, end);
+    }
+    if (end.line > begin.line)
+    {
+        for (auto it = update_only_line_beg; it != sels.end(); ++it)
+        {
+            UpdateFunc<true, true>{}(it->first(), begin, end);
+            UpdateFunc<true, true>{}(it->last(), begin, end);
+        }
+    }
 }
 
-static void update_erase(BufferIterator& it,
-                         const BufferCoord& begin, const BufferCoord& end)
+template<bool assume_different_line, bool assume_greater_than_begin>
+struct UpdateInsert
 {
-    BufferCoord coord = it.coord();
-    if (coord < begin)
-        return;
+    void operator()(BufferIterator& it,
+                    const BufferCoord& begin, const BufferCoord& end) const
+    {
+        BufferCoord coord = it.coord();
+        if (assume_different_line)
+            assert(begin.line < coord.line);
+        if (not assume_greater_than_begin and coord < begin)
+            return;
+        if (not assume_different_line and begin.line == coord.line)
+            coord.column = end.column + coord.column - begin.column;
+
+        coord.line += end.line - begin.line;
+        it = coord;
+    }
+};
 
-    if (coord <= end)
-        coord = it.buffer().clamp(begin);
-    else
+template<bool assume_different_line, bool assume_greater_than_begin>
+struct UpdateErase
+{
+    void operator()(BufferIterator& it,
+                    const BufferCoord& begin, const BufferCoord& end) const
     {
-        if (end.line == coord.line)
+        BufferCoord coord = it.coord();
+        if (not assume_greater_than_begin and coord < begin)
+            return;
+        if (assume_different_line)
+            assert(end.line < coord.line);
+        if (not assume_different_line and coord <= end)
+            coord = it.buffer().clamp(begin);
+        else
         {
-            coord.line = begin.line;
-            coord.column = begin.column + coord.column - end.column;
+            if (not assume_different_line and end.line == coord.line)
+            {
+                coord.line = begin.line;
+                coord.column = begin.column + coord.column - end.column;
+            }
+            else
+                coord.line -= end.line - begin.line;
         }
-        else
-            coord.line -= end.line - begin.line;
+        it = coord;
     }
-    it = coord;
+};
+
 }
 
 void DynamicSelectionList::on_insert(const BufferIterator& begin, const BufferIterator& end)
 {
-    const BufferCoord begin_coord{begin.coord()};
-    const BufferCoord end_coord{end.coord()};
-    for (auto& sel : *this)
-    {
-        update_insert(sel.first(), begin_coord, end_coord);
-        update_insert(sel.last(), begin_coord, end_coord);
-    }
+    on_buffer_change<UpdateInsert>(*this, begin.coord(), end.coord(), begin.line());
 }
 
 void DynamicSelectionList::on_erase(const BufferIterator& begin, const BufferIterator& end)
 {
-    const BufferCoord begin_coord{begin.coord()};
-    const BufferCoord end_coord{end.coord()};
-    for (auto& sel : *this)
-    {
-        update_erase(sel.first(), begin_coord, end_coord);
-        update_erase(sel.last(), begin_coord, end_coord);
-    }
+    on_buffer_change<UpdateErase>(*this, begin.coord(), end.coord(), end.line());
 }
 
 }