tmf.ui: use binary search when adding child to TimeGraphEntry

This brings the search time complexity to O(log(n)) down from
O(n).

Change-Id: I5b97c0f341bfe712d1bb8f9fd95cffc9ccd8686c
Signed-off-by: Loïc Prieur-Drevon <loic.prieurdrevon@gmail.com>
Reviewed-on: https://git.eclipse.org/r/86000
Reviewed-by: Hudson CI
Reviewed-by: Jonathan Rajotte Julien <jonathan.rajotte-julien@efficios.com>
Reviewed-by: Patrick Tasse <patrick.tasse@gmail.com>
Tested-by: Patrick Tasse <patrick.tasse@gmail.com>

diff --git a/tmf/org.eclipse.tracecompass.tmf.ui/src/org/eclipse/tracecompass/tmf/ui/widgets/timegraph/model/TimeGraphEntry.java b/tmf/org.eclipse.tracecompass.tmf.ui/src/org/eclipse/tracecompass/tmf/ui/widgets/timegraph/model/TimeGraphEntry.java
index 5d06e922121d4da7b2e07eda1199da8dea7fdb77..95b99d9e92b58a6e3c47a3fc165376feb44abece 100644 (file)
--- a/tmf/org.eclipse.tracecompass.tmf.ui/src/org/eclipse/tracecompass/tmf/ui/widgets/timegraph/model/TimeGraphEntry.java
+++ b/tmf/org.eclipse.tracecompass.tmf.ui/src/org/eclipse/tracecompass/tmf/ui/widgets/timegraph/model/TimeGraphEntry.java
@@ -15,6 +15,7 @@ package org.eclipse.tracecompass.tmf.ui.widgets.timegraph.model;
 
 import java.util.ArrayList;
 import java.util.Arrays;
+import java.util.Collections;
 import java.util.Comparator;
 import java.util.Iterator;
 import java.util.List;
@@ -265,13 +266,9 @@ public class TimeGraphEntry implements ITimeGraphEntry {
         if (fComparator == null) {
             addChild(fChildren.size(), child);
         } else {
-            int i;
-            for (i = 0; i < fChildren.size(); i++) {
-                ITimeGraphEntry entry = fChildren.get(i);
-                if (fComparator.compare(child, entry) < 0) {
-                    break;
-                }
-            }
+            int i = Collections.binarySearch(fChildren, child, fComparator);
+            /* Deal with negative insertion points from binarySearch */
+            i = i >= 0 ? i : -i - 1;
             addChild(i, child);
         }
     }