1 files changed, 112 insertions, 0 deletions
diff --git a/third_party/WebKit/Source/devtools/front_end/common/SegmentedRange.js b/third_party/WebKit/Source/devtools/front_end/common/SegmentedRange.js
new file mode 100644
index 0000000..6505aaa
--- /dev/null
+++ b/third_party/WebKit/Source/devtools/front_end/common/SegmentedRange.js
@@ -0,0 +1,112 @@
+// Copyright 2016 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+/**
+ * @constructor
+ * @param {number} begin
+ * @param {number} end
+ * @param {*} data
+ */
+WebInspector.Segment = function(begin, end, data)
+{
+    if (begin > end)
+        console.assert(false, "Invalid segment");
+    this.begin = begin;
+    this.end = end;
+    this.data = data;
+}
+
+WebInspector.Segment.prototype = {
+    /**
+     * @param {!WebInspector.Segment} that
+     * @return {boolean}
+     */
+    intersects: function(that)
+    {
+        return this.begin < that.end && that.begin < this.end;
+    }
+};
+
+/**
+ * @constructor
+ * @param {(function(!WebInspector.Segment, !WebInspector.Segment): ?WebInspector.Segment)=} mergeCallback
+ */
+WebInspector.SegmentedRange = function(mergeCallback)
+{
+    /** @type {!Array<!WebInspector.Segment>} */
+    this._segments = [];
+    this._mergeCallback = mergeCallback;
+}
+
+WebInspector.SegmentedRange.prototype = {
+    /**
+     * @param {!WebInspector.Segment} newSegment
+     */
+    append: function(newSegment)
+    {
+        // 1. Find the proper insertion point for new segment
+        var startIndex = this._segments.lowerBound(newSegment, (a, b) => a.begin - b.begin);
+        var endIndex = startIndex;
+        var merged = null;
+        if (startIndex > 0) {
+            // 2. Try mering the preceding segment
+            var precedingSegment = this._segments[startIndex - 1];
+            merged = this._tryMerge(precedingSegment, newSegment);
+            if (merged) {
+                --startIndex;
+                newSegment = merged;
+            } else if (this._segments[startIndex - 1].end >= newSegment.begin) {
+                // 2a. If merge failed and segments overlap, adjust preceding segment.
+                // If an old segment entirely contains new one, split it in two.
+                if (newSegment.end < precedingSegment.end)
+                    this._segments.splice(startIndex, 0, new WebInspector.Segment(newSegment.end, precedingSegment.end, precedingSegment.data));
+                precedingSegment.end = newSegment.begin;
+            }
+        }
+        // 3. Consume all segments that are entirely covered by the new one.
+        while (endIndex < this._segments.length && this._segments[endIndex].end <= newSegment.end)
+            ++endIndex;
+        // 4. Merge or adjust the succeeding segment if it overlaps.
+        if (endIndex < this._segments.length) {
+            merged = this._tryMerge(newSegment, this._segments[endIndex]);
+            if (merged) {
+                endIndex++;
+                newSegment = merged;
+            } else if (newSegment.intersects(this._segments[endIndex]))
+                this._segments[endIndex].begin = newSegment.end;
+        }
+        this._segments.splice(startIndex, endIndex - startIndex, newSegment);
+    },
+
+    /**
+     * @param {!WebInspector.SegmentedRange} that
+     */
+    appendRange: function(that)
+    {
+        that.segments().forEach(segment => this.append(segment));
+    },
+
+    /**
+     * @return {!Array<!WebInspector.Segment>}
+     */
+    segments: function()
+    {
+        return this._segments;
+    },
+
+    /**
+     * @param {!WebInspector.Segment} first
+     * @param {!WebInspector.Segment} second
+     * @return {?WebInspector.Segment}
+     */
+    _tryMerge: function(first, second)
+    {
+        var merged = this._mergeCallback && this._mergeCallback(first, second);
+        if (!merged)
+            return null;
+        merged.begin = first.begin;
+        merged.end = Math.max(first.end, second.end);
+        return merged;
+    }
+}