Use forward iteration on selections, and take advantage of it when updating

SelectionList::update now is optimized for the common case where changes
are sorted, the algorithm is O(m*n) with m the number of sorted ranges
in the changes. In the common case, m should be very small.

4 files changed, 134 insertions, 108 deletions

diff --git a/src/input_handler.cc b/src/input_handler.cc
index 60cfb618..d5312305 100644
--- a/src/input_handler.cc
+++ b/src/input_handler.cc
@@ -669,21 +669,23 @@ public:
         }
         else if (key == Key::Backspace)
         {
-            for (auto& sel : reversed(context().selections()))
+            std::vector<Selection> sels;
+            for (auto& sel : context().selections())
             {
                 if (sel.cursor() == ByteCoord{0,0})
                     continue;
-                auto pos = buffer.iterator_at(sel.cursor());
-                buffer.erase(utf8::previous(pos), pos);
+                auto pos = sel.cursor();
+                sels.push_back({ buffer.char_prev(pos) });
             }
+            if (not sels.empty())
+                SelectionList{buffer, std::move(sels)}.erase();
         }
         else if (key == Key::Delete)
         {
-            for (auto& sel : reversed(context().selections()))
-            {
-                auto pos = buffer.iterator_at(sel.cursor());
-                buffer.erase(pos, utf8::next(pos));
-            }
+            std::vector<Selection> sels;
+            for (auto& sel : context().selections())
+                sels.push_back({ sel.cursor() });
+            SelectionList{buffer, std::move(sels)}.erase();
         }
         else if (key == Key::Left)
         {
@@ -774,60 +776,55 @@ private:
         SelectionList& selections = context().selections();
         Buffer& buffer = context().buffer();
 
-        for (auto& sel : reversed(selections))
-        {
-            ByteCoord anchor, cursor;
-            switch (mode)
+        switch (mode)
+        {
+        case InsertMode::Insert:
+            for (auto& sel : selections)
+                sel = Selection{sel.max(), sel.min()};
+            break;
+        case InsertMode::Replace:
+            selections.erase();
+            break;
+        case InsertMode::Append:
+            for (auto& sel : selections)
             {
-            case InsertMode::Insert:
-                anchor = sel.max();
-                cursor = sel.min();
-                break;
-            case InsertMode::Replace:
-                anchor = cursor = Kakoune::erase(buffer, sel).coord();
-                break;
-            case InsertMode::Append:
-                anchor = sel.min();
-                cursor = sel.max();
+                sel = Selection{sel.min(), sel.max()};
+                auto& cursor = sel.cursor();
                 // special case for end of lines, append to current line instead
                 if (cursor.column != buffer[cursor.line].length() - 1)
                     cursor = buffer.char_next(cursor);
-                break;
+            }
+            break;
 
-            case InsertMode::OpenLineBelow:
-            case InsertMode::AppendAtLineEnd:
-                anchor = cursor = ByteCoord{sel.max().line, buffer[sel.max().line].length() - 1};
-                break;
+        case InsertMode::OpenLineBelow:
+        case InsertMode::AppendAtLineEnd:
+            for (auto& sel : selections)
+                sel = ByteCoord{sel.max().line, buffer[sel.max().line].length() - 1};
+            break;
 
-            case InsertMode::OpenLineAbove:
-            case InsertMode::InsertAtLineBegin:
-                anchor = sel.min().line;
+        case InsertMode::OpenLineAbove:
+        case InsertMode::InsertAtLineBegin:
+            for (auto& sel : selections)
+            {
+                ByteCoord pos = sel.min().line;
                 if (mode == InsertMode::OpenLineAbove)
-                    anchor = buffer.char_prev(anchor);
+                    pos = buffer.char_prev(pos);
                 else
                 {
-                    auto anchor_non_blank = buffer.iterator_at(anchor);
-                    while (*anchor_non_blank == ' ' or *anchor_non_blank == '\t')
-                        ++anchor_non_blank;
-                    if (*anchor_non_blank != '\n')
-                        anchor = anchor_non_blank.coord();
+                    auto pos_non_blank = buffer.iterator_at(pos);
+                    while (*pos_non_blank == ' ' or *pos_non_blank == '\t')
+                        ++pos_non_blank;
+                    if (*pos_non_blank != '\n')
+                        pos = pos_non_blank.coord();
                 }
-                cursor = anchor;
-                break;
-            case InsertMode::InsertAtNextLineBegin:
-            case InsertMode::InsertCursor:
-                 kak_assert(false); // not implemented
-                 break;
+                sel = pos;
             }
-            if (buffer.is_end(anchor))
-               anchor = buffer.char_prev(anchor);
-            if (buffer.is_end(cursor))
-               cursor = buffer.char_prev(cursor);
-
-            sel.anchor() = anchor;
-            sel.cursor() = cursor;
+            break;
+        case InsertMode::InsertAtNextLineBegin:
+        case InsertMode::InsertCursor:
+             kak_assert(false); // not implemented
+             break;
         }
-        selections.update();
         if (mode == InsertMode::OpenLineBelow or mode == InsertMode::OpenLineAbove)
         {
             insert('\n');
@@ -837,7 +834,7 @@ private:
                 {
                     // special case, the --first line above did nothing, so we need to compensate now
                     if (sel.anchor() == buffer.char_next({0,0}))
-                        sel.anchor() = sel.cursor() = ByteCoord{0,0};
+                        sel = Selection{{0,0}};
                 }
             }
         }
diff --git a/src/normal.cc b/src/normal.cc
index 223d5075..cc7eaa88 100644
--- a/src/normal.cc
+++ b/src/normal.cc
@@ -463,6 +463,7 @@ void erase_selections(Context& context, int)
     RegisterManager::instance()['"'] = context.selections_content();
     ScopedEdition edition(context);
     context.selections().erase();
+    context.selections().avoid_eol();
 }
 
 void cat_erase_selections(Context& context, int)
@@ -473,6 +474,7 @@ void cat_erase_selections(Context& context, int)
         str += sel;
     RegisterManager::instance()['"'] = memoryview<String>(str);
     context.selections().erase();
+    context.selections().avoid_eol();
 }
 
 
diff --git a/src/selection.cc b/src/selection.cc
index d3c798b0..a1bd8cbc 100644
--- a/src/selection.cc
+++ b/src/selection.cc
@@ -67,10 +67,60 @@ ByteCoord update_pos(ByteCoord coord, const Buffer::Change& change)
 {
     if (change.type == Buffer::Change::Insert)
         return update_insert(coord, change.begin, change.end);
-    else  
+    else
         return update_erase(coord, change.begin, change.end);
 }
 
+// This tracks position changes for changes that are done
+// in a forward way (each change takes place at a position)
+// *after* the previous one.
+struct PositionChangesTracker
+{
+    ByteCoord last_pos;
+    ByteCoord pos_change;
+
+    void update(const Buffer::Change& change)
+    {
+        if (change.type == Buffer::Change::Insert)
+        {
+            pos_change.line += change.end.line - change.begin.line;
+            if (change.begin.line != last_pos.line)
+                pos_change.column = 0;
+            pos_change.column += change.end.column - change.begin.column;
+            last_pos = change.end;
+        }
+        else if (change.type == Buffer::Change::Erase)
+        {
+            pos_change.line -= change.end.line - change.begin.line;
+            if (last_pos.line != change.end.line)
+                pos_change.column = 0;
+            pos_change.column -= change.end.column - change.begin.column;
+            last_pos = change.begin;
+        }
+    }
+
+    void update(const Buffer& buffer, size_t& timestamp)
+    {
+        for (auto& change : buffer.changes_since(timestamp))
+            update(change);
+        timestamp = buffer.timestamp();
+    }
+
+    ByteCoord get_new_coord(ByteCoord coord)
+    {
+        if (last_pos.line - pos_change.line == coord.line)
+            coord.column += pos_change.column;
+        coord.line += pos_change.line;
+        return coord;
+    }
+
+    void update_sel(Selection& sel)
+    {
+        sel.anchor() = get_new_coord(sel.anchor());
+        sel.cursor() = get_new_coord(sel.cursor());
+    }
+};
+
 }
 
 void SelectionList::update()
@@ -78,13 +128,38 @@ void SelectionList::update()
     if (m_timestamp == m_buffer->timestamp())
         return;
 
-    for (auto& change : m_buffer->changes_since(m_timestamp))
+    auto compare = [](const Buffer::Change& lhs, const Buffer::Change& rhs)
+        { return lhs.begin < rhs.begin; };
+    auto relevant = [](const Buffer::Change& change, const ByteCoord& coord)
+        { return change.type == Buffer::Change::Insert ? change.begin <= coord
+                                                       : change.begin < coord; };
+
+    auto changes = m_buffer->changes_since(m_timestamp);
+    auto change_it = changes.begin();
+    while (change_it != changes.end())
     {
+        auto change_end = std::is_sorted_until(change_it, changes.end(), compare);
+        PositionChangesTracker changes_tracker;
+
+        auto advance_while_relevant = [&](const ByteCoord& pos) mutable {
+            while (relevant(*change_it, pos) and change_it != change_end)
+                changes_tracker.update(*change_it++);
+            while (change_it != change_end and
+                  change_it->begin == changes_tracker.last_pos)
+                changes_tracker.update(*change_it++);
+        };
+
         for (auto& sel : m_selections)
         {
-            sel.anchor() = update_pos(sel.anchor(), change);
-            sel.cursor() = update_pos(sel.cursor(), change);
+            auto& sel_min = sel.min();
+            auto& sel_max = sel.max();
+            advance_while_relevant(sel_min);
+            sel_min = changes_tracker.get_new_coord(sel_min);
+
+            advance_while_relevant(sel_max);
+            sel_max = changes_tracker.get_new_coord(sel_max);
         }
+        change_it = change_end;
     }
     for (auto& sel : m_selections)
     {
@@ -193,56 +268,6 @@ BufferIterator prepare_insert(Buffer& buffer, const Selection& sel, InsertMode m
     return {};
 }
 
-// This tracks position changes for changes that are done
-// in a forward way (each change takes place at a position)
-// *after* the previous one.
-struct PositionChangesTracker 
-{
-    ByteCoord last_pos;
-    ByteCoord pos_change;
-
-    void update(const Buffer::Change& change)
-    {
-        if (change.type == Buffer::Change::Insert)
-        {
-            pos_change.line += change.end.line - change.begin.line;
-            if (change.begin.line != last_pos.line)
-                pos_change.column = 0;
-            pos_change.column += change.end.column - change.begin.column;
-            last_pos = change.end;
-        }
-        else if (change.type == Buffer::Change::Erase)
-        {
-            pos_change.line -= change.end.line - change.begin.line;
-            if (last_pos.line != change.end.line)
-                pos_change.column = 0;
-            pos_change.column -= change.end.column - change.begin.column;
-            last_pos = change.begin;
-        }
-    }
-
-    void update(const Buffer& buffer, size_t& timestamp)
-    {
-        for (auto& change : buffer.changes_since(timestamp))
-            update(change);
-        timestamp = buffer.timestamp();
-    }
-
-    ByteCoord get_new_coord(ByteCoord coord)
-    {
-        if (last_pos.line - pos_change.line == coord.line)
-            coord.column += pos_change.column;
-        coord.line += pos_change.line;
-        return coord;
-    }
-
-    void update_sel(Selection& sel)
-    {
-        sel.anchor() = get_new_coord(sel.anchor());
-        sel.cursor() = get_new_coord(sel.cursor());
-    }
-};
-
 void SelectionList::insert(memoryview<String> strings, InsertMode mode)
 {
     if (strings.empty())
@@ -294,7 +319,6 @@ void SelectionList::erase()
         sel.anchor() = sel.cursor() = m_buffer->clamp(pos.coord());
         changes_tracker.update(*m_buffer, m_timestamp);
     }
-    avoid_eol();
     m_buffer->check_invariant();
 }
 
diff --git a/src/selection.hh b/src/selection.hh
index 7e6fb2ad..651ee3fd 100644
--- a/src/selection.hh
+++ b/src/selection.hh
@@ -34,8 +34,11 @@ struct Selection
         return m_anchor == other.m_anchor and m_cursor == other.m_cursor;
     }
 
-    const ByteCoord& min() const { return std::min(m_anchor, m_cursor); }
-    const ByteCoord& max() const { return std::max(m_anchor, m_cursor); }
+    const ByteCoord& min() const { return m_anchor < m_cursor ? m_anchor : m_cursor; }
+    const ByteCoord& max() const { return m_anchor < m_cursor ? m_cursor : m_anchor; }
+
+    ByteCoord& min() { return m_anchor < m_cursor ? m_anchor : m_cursor; }
+    ByteCoord& max() { return m_anchor < m_cursor ? m_cursor : m_anchor; }
 
 private:
     ByteCoord m_anchor;