Room: change the way messages are ordered

This replaces the one-by-one timestamp-ordering algorithm of adding new
messages with copying the whole group of just-arrived messages to either
the beginning or the end of the timeline.

Since origin timestamps do not provide a reasonable order,
findInsertionPos() is entirely deleted. processMessageEvent() is
replaced by two functions: addNewMessageEvents() appends at
messageEvents.end() while addHistoricalMessageEvents() inserts them at
messageEvents.begin(). There's no official way to insert messages in the
middle; cases when getPreviousContent() is called in parallel or a
RoomMessagesJob runs on a gap somewhere in the middle of the timeline
weren't considered before this commit and aren't considered in it.

The new ordering requires you to understand where you have got your
events from (or rather, where you want to insert them). In particular,
updateData() that processes /sync results uses addNewMessageEvents();
getPreviousContent() calls addHistoricalMessageEvents().

In order to notify clients, a single newMessages() signal gives way to
3 new signals: 2 aboutToAdd*Messages() and a common addedMessages().
In addition, clients can derive from Room and use doAdd*Messages()
virtual functions to alter/extend the behaviour.

3 files changed, 48 insertions, 41 deletions

diff --git a/events/event.h b/events/event.h
index a66f5e68..6b566be0 100644
--- a/events/event.h
+++ b/events/event.h
@@ -35,7 +35,7 @@ namespace QMatrixClient
         RoomMessage, RoomName, RoomAliases, RoomCanonicalAlias,
         RoomMember, RoomTopic, Typing, Receipt, Unknown
     };
-    
+
     class Event
     {
         public:
@@ -61,28 +61,7 @@ namespace QMatrixClient
     };
     using Events = QVector<Event*>;
 
-    Events eventsFromJson(const QJsonArray& contents);
-
-    /**
-     * 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, class ContT>
-    typename ContT::iterator
-    findInsertionPos(ContT & timeline, const ItemT *item)
-    {
-        return std::lower_bound (timeline.begin(), timeline.end(), item,
-            [](const typename ContT::value_type a, const ItemT * b) {
-                // FIXME: We should not order the message list by origin timestamp.
-                // Rather, an order of receiving should be used (which actually
-                // poses a question on whether this method is needed at all -
-                // or we'd just prepend and append, depending on whether we
-                // received something from /sync or from /messages.
-                return a->timestamp() < b->timestamp();
-            }
-        );
-    }
+    Events eventsFromJson(const QJsonArray& json);
 
     /**
      * @brief Lookup a value by a key in a varargs list
diff --git a/room.cpp b/room.cpp
index 3683781b..64ff5a85 100644
--- a/room.cpp
+++ b/room.cpp
@@ -340,13 +340,14 @@ void Room::updateData(const SyncRoomData& data)
         processStateEvent(stateEvent);
     }
 
-    for( Event* timelineEvent: data.timeline )
+    if (!data.timeline.empty())
     {
-
-        processMessageEvent(timelineEvent);
-        emit newMessage(timelineEvent);
-        // State changes can arrive in a timeline event - try to check those.
-        processStateEvent(timelineEvent);
+        for( Event* e: data.timeline )
+        {
+            // State changes can arrive in a timeline event; so check those.
+            processStateEvent(e);
+        }
+        addNewMessageEvents(data.timeline);
     }
 
     for( Event* ephemeralEvent: data.ephemeral )
@@ -379,11 +380,7 @@ void Room::Private::getPreviousContent()
         connect( roomMessagesJob, &RoomMessagesJob::result, [=]() {
             if( !roomMessagesJob->error() )
             {
-                for( Event* event: roomMessagesJob->events() )
-                {
-                    q->processMessageEvent(event);
-                    emit q->newMessage(event);
-                }
+                q->addHistoricalMessageEvents(roomMessagesJob->events());
                 prevBatch = roomMessagesJob->end();
             }
             roomMessagesJob = nullptr;
@@ -396,9 +393,32 @@ Connection* Room::connection() const
     return d->connection;
 }
 
-void Room::processMessageEvent(Event* event)
+void Room::addNewMessageEvents(const Events& events)
+{
+    emit aboutToAddNewMessages(events);
+    doAddNewMessageEvents(events);
+    emit addedMessages();
+}
+
+void Room::doAddNewMessageEvents(const Events& events)
+{
+    d->messageEvents.reserve(d->messageEvents.size() + events.size());
+    std::copy(events.begin(), events.end(), std::back_inserter(d->messageEvents));
+}
+
+void Room::addHistoricalMessageEvents(const Events& events)
+{
+    emit aboutToAddHistoricalMessages(events);
+    doAddHistoricalMessageEvents(events);
+    emit addedMessages();
+}
+
+void Room::doAddHistoricalMessageEvents(const Events& events)
 {
-    d->messageEvents.insert(findInsertionPos(d->messageEvents, event), event);
+    // Preserver the order of messages when inserting the block in the
+    // beginning of the container.
+    std::reverse_copy(events.begin(), events.end(),
+                      std::front_inserter(d->messageEvents));
 }
 
 void Room::processStateEvent(Event* event)
diff --git a/room.h b/room.h
index 8f6a65a6..c64bed6f 100644
--- a/room.h
+++ b/room.h
@@ -82,13 +82,17 @@ namespace QMatrixClient
             void userRenamed(User* user, QString oldName);
 
         signals:
-            void newMessage(Event* event);
+            void aboutToAddHistoricalMessages(const Events& events);
+            void aboutToAddNewMessages(const Events& events);
+            void addedMessages();
+
             /**
-             * Triggered when the room name, canonical alias or other aliases
-             * change. Not triggered when displayname changes.
+             * @brief The room name, the canonical alias or other aliases changed
+             *
+             * Not triggered when displayname changes.
              */
             void namesChanged(Room* room);
-            /** Triggered only for changes in the room displayname. */
+            /** @brief The room displayname changed */
             void displaynameChanged(Room* room);
             void topicChanged();
             void userAdded(User* user);
@@ -101,13 +105,17 @@ namespace QMatrixClient
 
         protected:
             Connection* connection() const;
-            virtual void processMessageEvent(Event* event);
+            virtual void doAddNewMessageEvents(const Events& events);
+            virtual void doAddHistoricalMessageEvents(const Events& events);
             virtual void processStateEvent(Event* event);
             virtual void processEphemeralEvent(Event* event);
 
         private:
             class Private;
             Private* d;
+
+            void addNewMessageEvents(const Events& events);
+            void addHistoricalMessageEvents(const Events& events);
     };
 }