From def5a08b4d360f6035ad4c420f0206ad6f96e0bd Mon Sep 17 00:00:00 2001
From: Kitsune Ral <Kitsune-Ral@users.sf.net>
Date: Mon, 11 Apr 2016 12:43:32 +0900
Subject: Factor out the code that searches an insertion point in a timeline.

This is used once in the library and, I guess, twice more in the
Quaternion. Implemented as a template function that is equally suitable
for Event and Message, and any container that supports STL-style
iterators (QList and other Qt containers do).
---
 CMakeLists.txt |  1 +
 events/event.h | 18 ++++++++++++++++++
 room.cpp       | 10 +---------
 3 files changed, 20 insertions(+), 9 deletions(-)

diff --git a/CMakeLists.txt b/CMakeLists.txt
index bb5a47cb..526249e4 100644
--- a/CMakeLists.txt
+++ b/CMakeLists.txt
@@ -100,6 +100,7 @@ if ( CMAKE_VERSION VERSION_LESS "3.1" )
 else ( CMAKE_VERSION VERSION_LESS "3.1" )
     target_compile_features(qmatrixclient PRIVATE cxx_range_for)
     target_compile_features(qmatrixclient PRIVATE cxx_override)
+    target_compile_features(qmatrixclient PRIVATE cxx_lambdas)
 endif ( CMAKE_VERSION VERSION_LESS "3.1" )
 
 target_link_libraries(qmatrixclient Qt5::Core Qt5::Network Qt5::Gui)
diff --git a/events/event.h b/events/event.h
index b25b1378..6a8d0e89 100644
--- a/events/event.h
+++ b/events/event.h
@@ -19,6 +19,8 @@
 #ifndef QMATRIXCLIENT_EVENT_H
 #define QMATRIXCLIENT_EVENT_H
 
+#include <algorithm>
+
 #include <QtCore/QString>
 #include <QtCore/QDateTime>
 #include <QtCore/QJsonObject>
@@ -53,6 +55,22 @@ namespace QMatrixClient
             class Private;
             Private* d;
     };
+
+    /**
+     * Finds a place in the timeline where a new event/message could be inserted.
+     * @return an iterator to an item with the earliest timestamp after
+     * the one of 'item'; or timeline.end(), if all events are earlier
+     */
+    template <class ItemT, template <typename> class ContT>
+    typename ContT<ItemT *>::iterator
+    findInsertionPos(ContT<ItemT *> & timeline, const ItemT *item)
+    {
+        return std::lower_bound (timeline.begin(), timeline.end(), item,
+            [](const ItemT * a, const ItemT * b) {
+                return a->timestamp() < b->timestamp();
+            }
+        );
+    }
 }
 
 #endif // QMATRIXCLIENT_EVENT_H
diff --git a/room.cpp b/room.cpp
index 99d7f810..c5b674ae 100644
--- a/room.cpp
+++ b/room.cpp
@@ -284,15 +284,7 @@ Connection* Room::connection()
 
 void Room::processMessageEvent(Event* event)
 {
-    for( int i=0; i<d->messageEvents.count(); i++ )
-    {
-        if( event->timestamp() < d->messageEvents.at(i)->timestamp() )
-        {
-            d->messageEvents.insert(i, event);
-            return;
-        }
-    }
-    d->messageEvents.append(event);
+    d->messageEvents.insert(findInsertionPos(d->messageEvents, event), event);
 }
 
 void Room::processStateEvent(Event* event)
-- 
cgit v1.2.3