[meld] misc: Add helper for merging overlapping highlight ranges

[Kai Willadsen <kaiw src gnome org>]

commit d0df8ed5e32e7c5c000116e3e650885e625fd796
Author: Kai Willadsen <kai willadsen gmail com>
Date:   Sun Nov 22 09:43:01 2015 +1000

    misc: Add helper for merging overlapping highlight ranges

 meld/misc.py      |   35 +++++++++++++++++++++++++++++++++++
 test/test_misc.py |   18 ++++++++++++++++++
 2 files changed, 53 insertions(+), 0 deletions(-)
---
diff --git a/meld/misc.py b/meld/misc.py
index 8f9d4ee..ad323ef 100644
--- a/meld/misc.py
+++ b/meld/misc.py
@@ -433,3 +433,38 @@ def shell_to_regex(pat):
         else:
             res += re.escape(c)
     return res + "$"
+
+
+def merge_intervals(interval_list):
+    """Merge a list of intervals
+
+    Returns a list of itervals as 2-tuples with all overlapping
+    intervals merged.
+
+    interval_list must be a list of 2-tuples of integers representing
+    the start and end of an interval.
+    """
+
+    if len(interval_list) < 2:
+        return interval_list
+
+    interval_list.sort()
+    merged_intervals = [interval_list.pop(0)]
+    current_start, current_end = merged_intervals[-1]
+
+    while interval_list:
+        new_start, new_end = interval_list.pop(0)
+
+        if current_end >= new_end:
+            continue
+
+        if current_end < new_start:
+            # Intervals do not overlap; create a new one
+            merged_intervals.append((new_start, new_end))
+        elif current_end < new_end:
+            # Intervals overlap; extend the current one
+            merged_intervals[-1] = (current_start, new_end)
+
+        current_start, current_end = merged_intervals[-1]
+
+    return merged_intervals
diff --git a/test/test_misc.py b/test/test_misc.py
new file mode 100644
index 0000000..0e81823
--- /dev/null
+++ b/test/test_misc.py
@@ -0,0 +1,18 @@
+
+import pytest
+from meld.misc import merge_intervals
+
+
+ pytest mark parametrize("intervals, expected", [
+    # Dominated by a single range
+    ([(1, 5), (5, 9), (10, 11), (0, 20)], [(0, 20)]),
+    # No overlap
+    ([(1, 5), (6, 9), (10, 11)], [(1, 5), (6, 9), (10, 11)]),
+    # Two overlap points between ranges
+    ([(1, 5), (5, 9), (10, 11), (11, 20)], [(1, 9), (10, 20)]),
+    # Two overlap points between ranges, out of order
+    ([(5, 9), (1, 5), (11, 20), (10, 11)], [(1, 9), (10, 20)]),
+])
+def test_merge_intervals(intervals, expected):
+    merged = merge_intervals(intervals)
+    assert merged == expected