Add process lifecycle heuristic

Change-Id: I433567cdce603ffd8210818d121181588d94222e

3 files changed, 805 insertions, 0 deletions

diff --git a/src/com/android/loganalysis/heuristic/ProcessLifecycleHeuristic.java b/src/com/android/loganalysis/heuristic/ProcessLifecycleHeuristic.java
new file mode 100644
index 0000000..008b0e5
--- /dev/null
+++ b/src/com/android/loganalysis/heuristic/ProcessLifecycleHeuristic.java
@@ -0,0 +1,520 @@
+/*
+ * Copyright (C) 2013 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package com.android.loganalysis.heuristic;
+
+import com.android.loganalysis.item.ConflictingItemException;
+import com.android.loganalysis.item.ProcrankItem;
+
+import org.json.JSONObject;
+
+import java.util.Arrays;
+import java.util.Collection;
+import java.util.Date;
+import java.util.HashMap;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.ListIterator;
+import java.util.Map;
+import java.util.Map.Entry;
+
+/**
+ * A {@link IHeuristic} to detect if there are any abnormalities in the process lifecyle.
+ */
+public class ProcessLifecycleHeuristic extends AbstractHeuristic {
+
+    private static final String HEURISTIC_NAME = "Process lifecycle";
+    private static final String HEURISTIC_TYPE = "PROCESS_LIFECYCLE";
+
+    // TODO: Tune thresholds
+    private static final int PROCESSES_CREATED_THRESHOLD = Integer.MAX_VALUE;
+    private static final int PROCESSES_DESTROYED_THRESHOLD = Integer.MAX_VALUE;
+    private static final int PROCESS_INSTANCE_THRESHOLD = Integer.MAX_VALUE;
+    private static final int PROCESS_LIFESPAN_THRESHOLD = Integer.MAX_VALUE;
+    private static final int PROCESS_RESTART_LATENCY_THRESHOLD = Integer.MAX_VALUE;
+
+
+    /**
+     * Class which holds the basic information for added procranks.
+     */
+    private static class ProcrankItemInfo {
+        public ProcrankItem mProcrank;
+        public Date mTimestamp;
+        public String mUri;
+
+        public ProcrankItemInfo(ProcrankItem procrank, Date timestamp, String uri) {
+            mProcrank = procrank;
+            mTimestamp = timestamp;
+            mUri = uri;
+        }
+    }
+
+    /**
+     * Class which holds basic information for a time interval.  Exposed for unit testing.
+     */
+    static class Interval {
+        public Date mStart;
+        public Date mStop;
+
+        public Interval(Date start, Date stop) {
+            mStart = start;
+            mStop = stop;
+        }
+
+        public Interval(Date timestamp) {
+            mStart = timestamp;
+            mStop = timestamp;
+        }
+
+        public void updateBounds(Date timestamp) {
+            if (timestamp.before(mStart)) {
+                mStart = timestamp;
+            }
+            if (timestamp.after(mStop)) {
+                mStop = timestamp;
+            }
+        }
+
+        public String toString() {
+            return String.format("(%s,  %s)", mStart, mStop);
+        }
+
+        public boolean contains(Interval i) {
+            return (mStart.before(i.mStart) || mStart.equals(i.mStart)) &&
+                    (mStop.after(i.mStop) || mStop.equals(i.mStop));
+        }
+    }
+
+    /**
+     * Blacklist of processes known to exist for short periods.
+     */
+    private static final List<String> PROCESS_BLACKLIST = Arrays.asList(
+            "dumpsys", "logcat", "procrank", "meminfo", "uiautomator");
+
+    /** List of {@link ProcrankItemInfo} sorted by timestamp */
+    private List<ProcrankItemInfo> mProcranks = new LinkedList<ProcrankItemInfo>();
+    /** Map of process name to map of PID to {@link Interval} */
+    private Map<String, Map<Integer, Interval>> mProcesses =
+            new HashMap<String, Map<Integer, Interval>>();
+    /** Map of PID to process names */
+    private Map<Integer, String> mAllProcesses = new HashMap<Integer, String>();
+
+    /**
+     * {@inheritDoc}
+     *
+     * @param procrank The {@link ProcrankItem}.
+     * @param timestamp The {@link Date} of the procrank, may not be {@code null}.
+     * @param uri The URI of the procrank, may be {@code null}.
+     */
+    @Override
+    public void addProcrank(ProcrankItem procrank, Date timestamp, String uri)
+            throws ConflictingItemException {
+        if (timestamp == null) {
+            return;
+        }
+
+        for (int pid : procrank.getPids()) {
+            final String expectedName = mAllProcesses.get(pid);
+            final String name = procrank.getProcessName(pid);
+            if (expectedName == null) {
+                mAllProcesses.put(pid, name);
+            } else if (!expectedName.equals(name)) {
+                throw new ConflictingItemException(String.format(
+                        "PID %d has name %s but had name %s in previous procranks", pid, name,
+                        expectedName));
+            }
+        }
+
+        mergeProcrankInfoItem(new ProcrankItemInfo(procrank, timestamp, uri));
+
+        Map<Integer, Interval> processInfos;
+        for (int pid : procrank.getPids()) {
+            final String processName = procrank.getProcessName(pid);
+            if (!mProcesses.containsKey(processName)) {
+                mProcesses.put(processName, new HashMap<Integer, Interval>());
+            }
+            processInfos = mProcesses.get(processName);
+            if (!processInfos.containsKey(pid)) {
+                processInfos.put(pid, new Interval(timestamp));
+            } else {
+                processInfos.get(pid).updateBounds(timestamp);
+            }
+        }
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    @Override
+    public boolean failed() {
+        final List<Date> timestamps = getProcrankTimestamps();
+
+        // Check processes created
+        for (Date timestamp : timestamps.subList(1, timestamps.size())) {
+            if (getProcessesCreated(timestamp) > PROCESSES_CREATED_THRESHOLD) {
+                return true;
+            }
+        }
+
+        // Check processes destroyed
+        for (Date timestamp : timestamps.subList(0, timestamps.size() - 1)) {
+            if (getProcessesCreated(timestamp) > PROCESSES_DESTROYED_THRESHOLD) {
+                return true;
+            }
+        }
+
+        for (String processName : mProcesses.keySet()) {
+            // Check average lifetime
+            if (getProcessInstanceCount(processName) > PROCESS_INSTANCE_THRESHOLD &&
+                    getAverageLifespan(processName) > PROCESS_LIFESPAN_THRESHOLD) {
+                return true;
+            }
+
+            // Check average restart latency
+            if (getProcessInstanceCount(processName) > PROCESS_INSTANCE_THRESHOLD &&
+                    getAverageRestartLatency(processName) > PROCESS_RESTART_LATENCY_THRESHOLD) {
+                return true;
+            }
+        }
+        return false;
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    @Override
+    public String getType() {
+        return HEURISTIC_TYPE;
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    @Override
+    public String getName() {
+        return HEURISTIC_NAME;
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    @Override
+    public String getSummary() {
+        // TODO: Return a summary
+        return null;
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    @Override
+    public String getDetails() {
+        // TODO: Return details
+        return null;
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    @Override
+    public JSONObject toJson() {
+        // TODO: Return a proper JSON object
+        return super.toJson();
+    }
+
+    /**
+     * Get the combined process names seen in the procranks.
+     *
+     * @return The process names.
+     */
+    Collection<String> getProcessNames() {
+        return mProcesses.keySet();
+    }
+
+    /**
+     * Get the average lifespan in ms for a given process name across all instances of the process.
+     *
+     * @param process The name of the process
+     * @return The average lifespan in ms.
+     */
+    public long getAverageLifespan(String process) {
+        final Map<Integer, Interval> processes = mProcesses.get(process);
+        if (processes == null) {
+            return 0;
+        }
+        long totalLifespan = 0;
+        for (Interval processInfo : processes.values()) {
+            totalLifespan +=
+                    processInfo.mStop.getTime() - processInfo.mStart.getTime();
+        }
+        return totalLifespan / processes.size();
+    }
+
+    /**
+     * Get the average restart latency for a given process name.
+     *
+     * @param process The process name.
+     * @return The average time it took for a process to be restarted. If there are no restarts or
+     * the process was not found, then 0 is returned.
+     */
+    public long getAverageRestartLatency(String process) {
+        final Map<Integer, Interval> processes = mProcesses.get(process);
+        if (processes == null) {
+            return 0;
+        }
+
+        List<Interval> intervals = getMergedIntervals(processes.values());
+        if (intervals.size() < 2) {
+            return 0;
+        }
+
+        long totalRestartLatency = 0;
+        Interval interval0;
+        Interval interval1;
+        for (int i = 0; i < intervals.size() - 1; i++) {
+            interval0 = intervals.get(i);
+            interval1 = intervals.get(i + 1);
+            totalRestartLatency += interval1.mStart.getTime() - interval0.mStop.getTime();
+        }
+        return totalRestartLatency / (intervals.size() - 1);
+    }
+
+    /**
+     * Get the number of instances for a given process name.
+     *
+     * @param process The process name.
+     * @return The total number of distinct PIDs.
+     */
+    public int getProcessInstanceCount(String process) {
+        final Map<Integer, Interval> processes = mProcesses.get(process);
+        if (processes == null) {
+            return 0;
+        }
+
+        return processes.size();
+    }
+
+    /**
+     * Get the number of instances which overlap another instance for a given process name.
+     *
+     * @param process The process name.
+     * @return The total of instances which overlap with another instance of the process.
+     */
+    public int getProcessOverlapCount(String process) {
+        final Map<Integer, Interval> processes = mProcesses.get(process);
+        if (processes == null) {
+            return 0;
+        }
+
+        int count = 0;
+        for (Interval interval : getMergedIntervals(processes.values())) {
+            int intervalCount = 0;
+            for (Interval processInterval : processes.values()) {
+                if (interval.contains(processInterval)) {
+                    intervalCount++;
+                }
+            }
+            if (intervalCount > 1) {
+                count += intervalCount;
+            }
+        }
+        return count;
+    }
+
+    /**
+     * Get a list of the timestamps for the added procranks in chronological order.
+     *
+     * @return The {@link List} of {@link Date} objects in chronological order.
+     */
+    public List<Date> getProcrankTimestamps() {
+        List<Date> timestamps = new LinkedList<Date>();
+        for (ProcrankItemInfo procrank : mProcranks) {
+            timestamps.add(procrank.mTimestamp);
+        }
+        return timestamps;
+    }
+
+    /**
+     * Get the number of procranks added.
+     *
+     * @return The number of procranks added.
+     */
+    public int getProcrankSize() {
+        return mProcranks.size();
+    }
+
+    /**
+     * Get the {@link ProcrankItem} at the specified position in chronological order.
+     *
+     * @param index The index of the procrank to return.
+     * @return The {@link ProcrankItem}.
+     */
+    public ProcrankItem getProcrankItem(int index) {
+        final ProcrankItemInfo procrank =  mProcranks.get(index);
+        if (procrank == null) {
+            return null;
+        }
+        return procrank.mProcrank;
+    }
+
+    /**
+     * Get the timestamp of the procrank at the specified position in chronological order.
+     *
+     * @param index The index of the procrank to return.
+     * @return The timestamp as a {@link Date}.
+     */
+    public Date getProcrankTimestamp(int index) {
+        final ProcrankItemInfo procrank =  mProcranks.get(index);
+        if (procrank == null) {
+            return null;
+        }
+        return procrank.mTimestamp;
+    }
+
+    /**
+     * Get the URI of the procrank at the specified position in chronological order.
+     *
+     * @param index The index of the procrank to return.
+     * @return The URI as a {@link String}.
+     */
+    public String getProcrankUri(int index) {
+        return mProcranks.get(index).mUri;
+    }
+
+    /**
+     * Get the number of processes which where created at a given timestamp.
+     * <p>
+     * This method looks at how many processes (PIDs) were first seen for the given {@link Date}. If
+     * a process was missing in one procrank but appeared again in later procrank, it will be
+     * considered alive for that duration. The timestamp must match the start date exactly, but the
+     * list of timestamps for all added {@link ProcrankItem}s can be obtained with
+     * {@link #getProcrankTimestamps()}.
+     * </p>
+     * @param timestamp The timestamp of the procrank.
+     * @return The number of processes created.
+     * @see #getProcrankTimestamps()
+     * @see #getProcessesDestroyed(Date)
+     */
+    public int getProcessesCreated(Date timestamp) {
+        int count = 0;
+        for (Entry<String, Map<Integer, Interval>> entry : mProcesses.entrySet()) {
+            if (!PROCESS_BLACKLIST.contains(entry.getKey())) {
+                for (Interval i : entry.getValue().values()) {
+                    if (i.mStart.equals(timestamp)) {
+                        count++;
+                    }
+                }
+            }
+        }
+        return count;
+    }
+
+    /**
+     * Get the number of processes which where destroyed at a given timestamp.
+     * <p>
+     * This method looks at how many processes (PIDs) were last seen for the given {@link Date}. If
+     * a process was missing in one procrank but appeared again in later procrank, it will be
+     * considered alive for that duration. The timestamp must match the end date exactly, but the
+     * list of timestamps for all added {@link ProcrankItem}s can be obtained with
+     * {@link #getProcrankTimestamps()}.
+     * </p>
+     * @param timestamp The timestamp of the procrank.
+     * @return The number of processes destroyed.
+     * @see #getProcrankTimestamps()
+     * @see #getProcessesCreated(Date)
+     */
+    public int getProcessesDestroyed(Date timestamp) {
+        int count = 0;
+        for (Entry<String, Map<Integer, Interval>> entry : mProcesses.entrySet()) {
+            if (!PROCESS_BLACKLIST.contains(entry.getKey())) {
+                for (Interval i : entry.getValue().values()) {
+                    if (i.mStop.equals(timestamp)) {
+                        count++;
+                    }
+                }
+            }
+        }
+        return count;
+    }
+
+    /**
+     * Take a collection of intervals and merge them.  All intervals are treated as open intervals.
+     * Exposed for unit testing.
+     */
+    static List<Interval> getMergedIntervals(Collection<Interval> intervals) {
+        List<Interval> mergedIntervals = new LinkedList<Interval>();
+        for (Interval interval : intervals) {
+            mergeInterval(mergedIntervals, interval);
+        }
+        return mergedIntervals;
+    }
+
+    /**
+     * Merge an interval into a list of sorted intervals, combining if necessary.  All intervals
+     * treated as open intervals.  Exposed for unit testing.
+     */
+    static void mergeInterval(List<Interval> intervals, Interval interval) {
+        Interval workingInterval = new Interval(interval.mStart, interval.mStop);
+        if (intervals.size() == 0) {
+            intervals.add(workingInterval);
+            return;
+        }
+
+        int startIndex;
+        for (startIndex = 0; startIndex < intervals.size(); startIndex++) {
+            if (workingInterval.mStart.before(intervals.get(startIndex).mStart) ||
+                    workingInterval.mStart.equals(intervals.get(startIndex).mStart)) {
+                break;
+            } else if (workingInterval.mStart.after(intervals.get(startIndex).mStart) &&
+                    workingInterval.mStart.before(intervals.get(startIndex).mStop)) {
+                workingInterval.mStart = intervals.get(startIndex).mStart;
+                break;
+            }
+        }
+
+        int stopIndex;
+        for (stopIndex = intervals.size() - 1; stopIndex >= 0; stopIndex--) {
+            if (workingInterval.mStop.after(intervals.get(stopIndex).mStop) ||
+                    workingInterval.mStop.equals(intervals.get(stopIndex).mStop)) {
+                break;
+            } else if (workingInterval.mStop.before(intervals.get(stopIndex).mStop) &&
+                    workingInterval.mStop.after(intervals.get(stopIndex).mStart)) {
+                workingInterval.mStop = intervals.get(stopIndex).mStop;
+                break;
+            }
+        }
+
+        for (int i = 0; i < 1 + stopIndex - startIndex; i++) {
+            intervals.remove(startIndex);
+        }
+        intervals.add(startIndex, workingInterval);
+    }
+
+    /**
+     * Merge the {@link ProcrankItemInfo} into the list in chronological order.
+     */
+    private void mergeProcrankInfoItem(ProcrankItemInfo procrank) {
+        // Insert the procrank in chronological order, bias for reverse order.
+        ListIterator<ProcrankItemInfo> iterator = mProcranks.listIterator(mProcranks.size());
+        while (iterator.hasPrevious()) {
+            ProcrankItemInfo item = iterator.previous();
+            if (procrank.mTimestamp.after(item.mTimestamp)) {
+                mProcranks.add(iterator.nextIndex() + 1, procrank);
+                return;
+            }
+        }
+        mProcranks.add(0, procrank);
+    }
+}
diff --git a/tests/src/com/android/loganalysis/UnitTests.java b/tests/src/com/android/loganalysis/UnitTests.java
index 6fb0ad3..4a3eada 100644
--- a/tests/src/com/android/loganalysis/UnitTests.java
+++ b/tests/src/com/android/loganalysis/UnitTests.java
@@ -23,6 +23,7 @@ import com.android.loganalysis.heuristic.KernelResetHeuristicTest;
 import com.android.loganalysis.heuristic.MemoryUsageHeuristicTest;
 import com.android.loganalysis.heuristic.NativeCrashHeuristicTest;
 import com.android.loganalysis.heuristic.PowerUsageHeuristicTest;
+import com.android.loganalysis.heuristic.ProcessLifecycleHeuristicTest;
 import com.android.loganalysis.heuristic.RuntimeRestartHeuristicTest;
 import com.android.loganalysis.item.DumpsysBatteryInfoItemTest;
 import com.android.loganalysis.item.GenericItemTest;
@@ -76,6 +77,7 @@ public class UnitTests extends TestSuite {
         addTestSuite(MemoryUsageHeuristicTest.class);
         addTestSuite(NativeCrashHeuristicTest.class);
         addTestSuite(PowerUsageHeuristicTest.class);
+        addTestSuite(ProcessLifecycleHeuristicTest.class);
         addTestSuite(RuntimeRestartHeuristicTest.class);
 
         // item
diff --git a/tests/src/com/android/loganalysis/heuristic/ProcessLifecycleHeuristicTest.java b/tests/src/com/android/loganalysis/heuristic/ProcessLifecycleHeuristicTest.java
new file mode 100644
index 0000000..6ef2433
--- /dev/null
+++ b/tests/src/com/android/loganalysis/heuristic/ProcessLifecycleHeuristicTest.java
@@ -0,0 +1,283 @@
+/*
+ * Copyright (C) 2013 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package com.android.loganalysis.heuristic;
+
+import com.android.loganalysis.heuristic.ProcessLifecycleHeuristic.Interval;
+import com.android.loganalysis.item.ConflictingItemException;
+import com.android.loganalysis.item.ProcrankItem;
+
+import junit.framework.TestCase;
+
+import java.util.Calendar;
+import java.util.Collection;
+import java.util.Date;
+import java.util.HashSet;
+import java.util.List;
+
+/**
+ * Unit test for {@link ProcessLifecycleHeuristic}.
+ */
+public class ProcessLifecycleHeuristicTest extends TestCase {
+
+    /**
+     * Test that a {@link ConflictingItemException} is thrown if there are conflicting procranks.
+     */
+    public void testConflictingInfo() throws ConflictingItemException {
+        Date now = new Date();
+
+        ProcrankItem p1 = new ProcrankItem();
+        p1.addProcrankLine(0, "name", 0, 0, 0, 0);
+        ProcrankItem p2 = new ProcrankItem();
+        p2.addProcrankLine(0, "wrongName", 0, 0, 0, 0);
+
+        ProcessLifecycleHeuristic heuristic = new ProcessLifecycleHeuristic();
+        heuristic.addProcrank(p1, now, null);
+        try {
+            heuristic.addProcrank(p2, offsetDate(now, Calendar.MINUTE, 1), null);
+            fail("ConflictingItemException not thrown");
+        } catch (ConflictingItemException e) {
+            // Expected
+        }
+    }
+
+    /**
+     * Test that multiple procranks are combined properly and that the stat functions for the
+     * combined procranks all return properly.
+     */
+    public void testCombineProcesses() throws ConflictingItemException {
+        Date now = new Date();
+        ProcessLifecycleHeuristic heuristic = new ProcessLifecycleHeuristic();
+
+        /*
+         * Processes look like:
+         * Proc  PID  0  1  2  3
+         *   p0    0  x
+         *   p0    9        x--x
+         *   p1    1  x-----x--x
+         *   p2    2  x--x
+         *   p3    3  x--x--x
+         *   p4    4  x
+         *   p4    7     x
+         *   p4   10           x
+         *   p5    5  x--x--x
+         *   p5    8     x--x--x
+         *   p6    6     x--x--x
+         */
+        ProcrankItem p0 = new ProcrankItem();
+        p0.addProcrankLine(0, "p0", 0, 0, 0, 0);
+        p0.addProcrankLine(1, "p1", 0, 0, 0, 0);
+        p0.addProcrankLine(2, "p2", 0, 0, 0, 0);
+        p0.addProcrankLine(3, "p3", 0, 0, 0, 0);
+        p0.addProcrankLine(4, "p4", 0, 0, 0, 0);
+        p0.addProcrankLine(5, "p5", 0, 0, 0, 0);
+
+        ProcrankItem p1 = new ProcrankItem();
+        p1.addProcrankLine(2, "p2", 0, 0, 0, 0);
+        p1.addProcrankLine(3, "p3", 0, 0, 0, 0);
+        p1.addProcrankLine(5, "p5", 0, 0, 0, 0);
+        p1.addProcrankLine(6, "p6", 0, 0, 0, 0);
+        p1.addProcrankLine(7, "p4", 0, 0, 0, 0);
+        p1.addProcrankLine(8, "p5", 0, 0, 0, 0);
+
+        ProcrankItem p2 = new ProcrankItem();
+        p2.addProcrankLine(1, "p1", 0, 0, 0, 0);
+        p2.addProcrankLine(3, "p3", 0, 0, 0, 0);
+        p2.addProcrankLine(5, "p5", 0, 0, 0, 0);
+        p2.addProcrankLine(6, "p6", 0, 0, 0, 0);
+        p2.addProcrankLine(8, "p5", 0, 0, 0, 0);
+        p2.addProcrankLine(9, "p0", 0, 0, 0, 0);
+
+        ProcrankItem p3 = new ProcrankItem();
+        p3.addProcrankLine(1, "p1", 0, 0, 0, 0);
+        p3.addProcrankLine(6, "p6", 0, 0, 0, 0);
+        p3.addProcrankLine(8, "p5", 0, 0, 0, 0);
+        p3.addProcrankLine(9, "p0", 0, 0, 0, 0);
+        p3.addProcrankLine(10, "p4", 0, 0, 0, 0);
+
+        // Add out of order to ensure that procranks are placed in chronological order.
+        heuristic.addProcrank(p1, offsetDate(now, Calendar.MINUTE, 1), null);
+        heuristic.addProcrank(p0, now, null);
+        heuristic.addProcrank(p3, offsetDate(now, Calendar.MINUTE, 3), null);
+        heuristic.addProcrank(p2, offsetDate(now, Calendar.MINUTE, 2), null);
+
+        assertEquals(0, heuristic.getAverageLifespan("invalid"));
+        assertEquals(30 * 1000, heuristic.getAverageLifespan("p0")); // 0, 2-3
+        assertEquals(3 * 60 * 1000, heuristic.getAverageLifespan("p1")); // 0-3
+        assertEquals(1 * 60 * 1000, heuristic.getAverageLifespan("p2")); // 0-1
+        assertEquals(2 * 60 * 1000, heuristic.getAverageLifespan("p3")); // 0-2
+        assertEquals(0, heuristic.getAverageLifespan("p4")); // 0, 1, 3
+        assertEquals(2 * 60 * 1000, heuristic.getAverageLifespan("p5")); // 0-2, 1-3
+        assertEquals(2 * 60 * 1000, heuristic.getAverageLifespan("p6")); // 1-3
+
+        assertEquals(0, heuristic.getAverageRestartLatency("invalid"));
+        assertEquals(2 * 60 * 1000, heuristic.getAverageRestartLatency("p0")); // 0, 2-3
+        assertEquals(0, heuristic.getAverageRestartLatency("p1")); // 0-3
+        assertEquals(0, heuristic.getAverageRestartLatency("p2")); // 0-1
+        assertEquals(0, heuristic.getAverageRestartLatency("p3")); // 0-2
+        assertEquals(3 * 60 * 1000 / 2, heuristic.getAverageRestartLatency("p4")); // 0, 1, 3
+        assertEquals(0, heuristic.getAverageRestartLatency("p5")); // 0-2, 1-3
+        assertEquals(0, heuristic.getAverageRestartLatency("p6")); // 1-3
+
+        assertEquals(0, heuristic.getProcessInstanceCount("invalid"));
+        assertEquals(2, heuristic.getProcessInstanceCount("p0")); // 0, 2-3
+        assertEquals(1, heuristic.getProcessInstanceCount("p1")); // 0-3
+        assertEquals(1, heuristic.getProcessInstanceCount("p2")); // 0-1
+        assertEquals(1, heuristic.getProcessInstanceCount("p3")); // 0-2
+        assertEquals(3, heuristic.getProcessInstanceCount("p4")); // 0, 1, 3
+        assertEquals(2, heuristic.getProcessInstanceCount("p5")); // 0-2, 1-3
+        assertEquals(1, heuristic.getProcessInstanceCount("p6")); // 1-3
+
+        assertEquals(0, heuristic.getProcessOverlapCount("invalid"));
+        assertEquals(0, heuristic.getProcessOverlapCount("p0")); // 0, 2-3
+        assertEquals(0, heuristic.getProcessOverlapCount("p1")); // 0-3
+        assertEquals(0, heuristic.getProcessOverlapCount("p2")); // 0-1
+        assertEquals(0, heuristic.getProcessOverlapCount("p3")); // 0-2
+        assertEquals(0, heuristic.getProcessOverlapCount("p4")); // 0, 1, 3
+        assertEquals(2, heuristic.getProcessOverlapCount("p5")); // 0-2, 1-3
+        assertEquals(0, heuristic.getProcessOverlapCount("p6")); // 1-3
+
+        final List<Date> timestamps = heuristic.getProcrankTimestamps();
+        assertEquals(4, timestamps.size());
+        assertEquals(now, timestamps.get(0));
+        assertEquals(offsetDate(now, Calendar.MINUTE, 1), timestamps.get(1));
+        assertEquals(offsetDate(now, Calendar.MINUTE, 2), timestamps.get(2));
+        assertEquals(offsetDate(now, Calendar.MINUTE, 3), timestamps.get(3));
+
+        assertEquals(6, heuristic.getProcessesCreated(now));
+        assertEquals(3, heuristic.getProcessesCreated(offsetDate(now, Calendar.MINUTE, 1)));
+        assertEquals(1, heuristic.getProcessesCreated(offsetDate(now, Calendar.MINUTE, 2)));
+        assertEquals(1, heuristic.getProcessesCreated(offsetDate(now, Calendar.MINUTE, 3)));
+
+        assertEquals(2, heuristic.getProcessesDestroyed(now));
+        assertEquals(2, heuristic.getProcessesDestroyed(offsetDate(now, Calendar.MINUTE, 1)));
+        assertEquals(2, heuristic.getProcessesDestroyed(offsetDate(now, Calendar.MINUTE, 2)));
+        assertEquals(5, heuristic.getProcessesDestroyed(offsetDate(now, Calendar.MINUTE, 3)));
+
+        final int procrankSize = heuristic.getProcrankSize();
+        assertEquals(4, procrankSize);
+
+        assertEquals(now, heuristic.getProcrankTimestamp(0));
+        assertEquals(offsetDate(now, Calendar.MINUTE, 1), heuristic.getProcrankTimestamp(1));
+        assertEquals(offsetDate(now, Calendar.MINUTE, 2), heuristic.getProcrankTimestamp(2));
+        assertEquals(offsetDate(now, Calendar.MINUTE, 3), heuristic.getProcrankTimestamp(3));
+
+        assertEquals(p0, heuristic.getProcrankItem(0));
+        assertEquals(p1, heuristic.getProcrankItem(1));
+        assertEquals(p2, heuristic.getProcrankItem(2));
+        assertEquals(p3, heuristic.getProcrankItem(3));
+    }
+
+    /**
+     * Test that procranks are added in chronological order.
+     */
+    public void testAddProcranks() throws ConflictingItemException {
+        Date now = new Date();
+
+        ProcrankItem p1 = new ProcrankItem();
+
+        ProcessLifecycleHeuristic heuristic = new ProcessLifecycleHeuristic();
+        heuristic.addProcrank(p1, null, null);
+        heuristic.addProcrank(p1, now, null);
+        heuristic.addProcrank(p1, offsetDate(now, Calendar.MINUTE, -1), null);
+        heuristic.addProcrank(p1, offsetDate(now, Calendar.MINUTE, 2), null);
+        heuristic.addProcrank(p1, offsetDate(now, Calendar.MINUTE, 1), null);
+
+        assertEquals(offsetDate(now, Calendar.MINUTE, -1), heuristic.getProcrankTimestamp(0));
+        assertEquals(now, heuristic.getProcrankTimestamp(1));
+        assertEquals(offsetDate(now, Calendar.MINUTE, 1), heuristic.getProcrankTimestamp(2));
+        assertEquals(offsetDate(now, Calendar.MINUTE, 2), heuristic.getProcrankTimestamp(3));
+    }
+
+    /**
+     * Test that the utility function for merging overlapping intervals works properly.
+     */
+    public void testMergeIntervals() {
+        Date now = new Date();
+
+        Collection<Interval> intervals = new HashSet<Interval>();
+        intervals.add(new Interval(now, offsetDate(now, Calendar.MINUTE, 2)));
+        intervals.add(new Interval(
+                offsetDate(now, Calendar.MINUTE, 4), offsetDate(now, Calendar.MINUTE, 6)));
+        intervals.add(new Interval(
+                offsetDate(now, Calendar.MINUTE, 5), offsetDate(now, Calendar.MINUTE, 7)));
+
+        // Expect 0-2, 4-7
+        List<Interval> mergedIntervals = ProcessLifecycleHeuristic.getMergedIntervals(intervals);
+
+        assertEquals(2, mergedIntervals.size());
+        assertEquals(now, mergedIntervals.get(0).mStart);
+        assertEquals(offsetDate(now, Calendar.MINUTE, 2), mergedIntervals.get(0).mStop);
+        assertEquals(offsetDate(now, Calendar.MINUTE, 4), mergedIntervals.get(1).mStart);
+        assertEquals(offsetDate(now, Calendar.MINUTE, 7), mergedIntervals.get(1).mStop);
+
+        // Expect 0-2, 2-4, 4-7
+        ProcessLifecycleHeuristic.mergeInterval(mergedIntervals, new Interval(
+                offsetDate(now, Calendar.MINUTE, 2), offsetDate(now, Calendar.MINUTE, 4)));
+
+        assertEquals(3, mergedIntervals.size());
+        assertEquals(offsetDate(now, Calendar.MINUTE, 2), mergedIntervals.get(1).mStart);
+        assertEquals(offsetDate(now, Calendar.MINUTE, 4), mergedIntervals.get(1).mStop);
+
+        // Expect -1-4, 4-7
+        ProcessLifecycleHeuristic.mergeInterval(mergedIntervals, new Interval(
+                offsetDate(now, Calendar.MINUTE, -1), offsetDate(now, Calendar.MINUTE, 3)));
+
+        assertEquals(2, mergedIntervals.size());
+        assertEquals(offsetDate(now, Calendar.MINUTE, -1), mergedIntervals.get(0).mStart);
+        assertEquals(offsetDate(now, Calendar.MINUTE, 4), mergedIntervals.get(0).mStop);
+
+        // Expect -2-7
+        ProcessLifecycleHeuristic.mergeInterval(mergedIntervals, new Interval(
+                offsetDate(now, Calendar.MINUTE, -2), offsetDate(now, Calendar.MINUTE, 6)));
+
+        assertEquals(1, mergedIntervals.size());
+        assertEquals(offsetDate(now, Calendar.MINUTE, -2), mergedIntervals.get(0).mStart);
+        assertEquals(offsetDate(now, Calendar.MINUTE, 7), mergedIntervals.get(0).mStop);
+
+        // Expect -2-8
+        ProcessLifecycleHeuristic.mergeInterval(mergedIntervals, new Interval(
+                offsetDate(now, Calendar.MINUTE, 1), offsetDate(now, Calendar.MINUTE, 8)));
+
+        System.out.println(mergedIntervals);
+
+        assertEquals(1, mergedIntervals.size());
+        assertEquals(offsetDate(now, Calendar.MINUTE, -2), mergedIntervals.get(0).mStart);
+        assertEquals(offsetDate(now, Calendar.MINUTE, 8), mergedIntervals.get(0).mStop);
+
+        // Expect -2-8
+        ProcessLifecycleHeuristic.mergeInterval(mergedIntervals, new Interval(
+                offsetDate(now, Calendar.MINUTE, -2), offsetDate(now, Calendar.MINUTE, 8)));
+
+        assertEquals(1, mergedIntervals.size());
+        assertEquals(offsetDate(now, Calendar.MINUTE, -2), mergedIntervals.get(0).mStart);
+        assertEquals(offsetDate(now, Calendar.MINUTE, 8), mergedIntervals.get(0).mStop);
+
+        // Expect -2-8, 10-10
+        ProcessLifecycleHeuristic.mergeInterval(mergedIntervals, new Interval(
+                offsetDate(now, Calendar.MINUTE, 10)));
+
+        assertEquals(2, mergedIntervals.size());
+        assertEquals(offsetDate(now, Calendar.MINUTE, 10), mergedIntervals.get(1).mStart);
+        assertEquals(offsetDate(now, Calendar.MINUTE, 10), mergedIntervals.get(1).mStop);
+    }
+
+    private Date offsetDate(Date timestamp, int field, int offset) {
+        Calendar cal = Calendar.getInstance();
+        cal.setTime(timestamp);
+        cal.add(field, offset);
+        return cal.getTime();
+    }
+}