OLD | NEW |
1 // Copyright 2016 The Chromium Authors. All rights reserved. | 1 // Copyright 2016 The Chromium Authors. All rights reserved. |
2 // Use of this source code is governed by a BSD-style license that can be | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | |
5 /** | 4 /** |
6 * @constructor | 5 * @unrestricted |
7 * @param {number} begin | |
8 * @param {number} end | |
9 * @param {*} data | |
10 */ | 6 */ |
11 WebInspector.Segment = function(begin, end, data) | 7 WebInspector.Segment = class { |
12 { | 8 /** |
| 9 * @param {number} begin |
| 10 * @param {number} end |
| 11 * @param {*} data |
| 12 */ |
| 13 constructor(begin, end, data) { |
13 if (begin > end) | 14 if (begin > end) |
14 console.assert(false, "Invalid segment"); | 15 console.assert(false, 'Invalid segment'); |
15 this.begin = begin; | 16 this.begin = begin; |
16 this.end = end; | 17 this.end = end; |
17 this.data = data; | 18 this.data = data; |
18 }; | 19 } |
19 | 20 |
20 WebInspector.Segment.prototype = { | 21 /** |
21 /** | 22 * @param {!WebInspector.Segment} that |
22 * @param {!WebInspector.Segment} that | 23 * @return {boolean} |
23 * @return {boolean} | 24 */ |
24 */ | 25 intersects(that) { |
25 intersects: function(that) | 26 return this.begin < that.end && that.begin < this.end; |
26 { | 27 } |
27 return this.begin < that.end && that.begin < this.end; | |
28 } | |
29 }; | 28 }; |
30 | 29 |
31 /** | 30 /** |
32 * @constructor | 31 * @unrestricted |
33 * @param {(function(!WebInspector.Segment, !WebInspector.Segment): ?WebInspecto
r.Segment)=} mergeCallback | |
34 */ | 32 */ |
35 WebInspector.SegmentedRange = function(mergeCallback) | 33 WebInspector.SegmentedRange = class { |
36 { | 34 /** |
| 35 * @param {(function(!WebInspector.Segment, !WebInspector.Segment): ?WebInspec
tor.Segment)=} mergeCallback |
| 36 */ |
| 37 constructor(mergeCallback) { |
37 /** @type {!Array<!WebInspector.Segment>} */ | 38 /** @type {!Array<!WebInspector.Segment>} */ |
38 this._segments = []; | 39 this._segments = []; |
39 this._mergeCallback = mergeCallback; | 40 this._mergeCallback = mergeCallback; |
| 41 } |
| 42 |
| 43 /** |
| 44 * @param {!WebInspector.Segment} newSegment |
| 45 */ |
| 46 append(newSegment) { |
| 47 // 1. Find the proper insertion point for new segment |
| 48 var startIndex = this._segments.lowerBound(newSegment, (a, b) => a.begin - b
.begin); |
| 49 var endIndex = startIndex; |
| 50 var merged = null; |
| 51 if (startIndex > 0) { |
| 52 // 2. Try mering the preceding segment |
| 53 var precedingSegment = this._segments[startIndex - 1]; |
| 54 merged = this._tryMerge(precedingSegment, newSegment); |
| 55 if (merged) { |
| 56 --startIndex; |
| 57 newSegment = merged; |
| 58 } else if (this._segments[startIndex - 1].end >= newSegment.begin) { |
| 59 // 2a. If merge failed and segments overlap, adjust preceding segment. |
| 60 // If an old segment entirely contains new one, split it in two. |
| 61 if (newSegment.end < precedingSegment.end) |
| 62 this._segments.splice( |
| 63 startIndex, 0, new WebInspector.Segment(newSegment.end, precedingS
egment.end, precedingSegment.data)); |
| 64 precedingSegment.end = newSegment.begin; |
| 65 } |
| 66 } |
| 67 // 3. Consume all segments that are entirely covered by the new one. |
| 68 while (endIndex < this._segments.length && this._segments[endIndex].end <= n
ewSegment.end) |
| 69 ++endIndex; |
| 70 // 4. Merge or adjust the succeeding segment if it overlaps. |
| 71 if (endIndex < this._segments.length) { |
| 72 merged = this._tryMerge(newSegment, this._segments[endIndex]); |
| 73 if (merged) { |
| 74 endIndex++; |
| 75 newSegment = merged; |
| 76 } else if (newSegment.intersects(this._segments[endIndex])) |
| 77 this._segments[endIndex].begin = newSegment.end; |
| 78 } |
| 79 this._segments.splice(startIndex, endIndex - startIndex, newSegment); |
| 80 } |
| 81 |
| 82 /** |
| 83 * @param {!WebInspector.SegmentedRange} that |
| 84 */ |
| 85 appendRange(that) { |
| 86 that.segments().forEach(segment => this.append(segment)); |
| 87 } |
| 88 |
| 89 /** |
| 90 * @return {!Array<!WebInspector.Segment>} |
| 91 */ |
| 92 segments() { |
| 93 return this._segments; |
| 94 } |
| 95 |
| 96 /** |
| 97 * @param {!WebInspector.Segment} first |
| 98 * @param {!WebInspector.Segment} second |
| 99 * @return {?WebInspector.Segment} |
| 100 */ |
| 101 _tryMerge(first, second) { |
| 102 var merged = this._mergeCallback && this._mergeCallback(first, second); |
| 103 if (!merged) |
| 104 return null; |
| 105 merged.begin = first.begin; |
| 106 merged.end = Math.max(first.end, second.end); |
| 107 return merged; |
| 108 } |
40 }; | 109 }; |
41 | |
42 WebInspector.SegmentedRange.prototype = { | |
43 /** | |
44 * @param {!WebInspector.Segment} newSegment | |
45 */ | |
46 append: function(newSegment) | |
47 { | |
48 // 1. Find the proper insertion point for new segment | |
49 var startIndex = this._segments.lowerBound(newSegment, (a, b) => a.begin
- b.begin); | |
50 var endIndex = startIndex; | |
51 var merged = null; | |
52 if (startIndex > 0) { | |
53 // 2. Try mering the preceding segment | |
54 var precedingSegment = this._segments[startIndex - 1]; | |
55 merged = this._tryMerge(precedingSegment, newSegment); | |
56 if (merged) { | |
57 --startIndex; | |
58 newSegment = merged; | |
59 } else if (this._segments[startIndex - 1].end >= newSegment.begin) { | |
60 // 2a. If merge failed and segments overlap, adjust preceding se
gment. | |
61 // If an old segment entirely contains new one, split it in two. | |
62 if (newSegment.end < precedingSegment.end) | |
63 this._segments.splice(startIndex, 0, new WebInspector.Segmen
t(newSegment.end, precedingSegment.end, precedingSegment.data)); | |
64 precedingSegment.end = newSegment.begin; | |
65 } | |
66 } | |
67 // 3. Consume all segments that are entirely covered by the new one. | |
68 while (endIndex < this._segments.length && this._segments[endIndex].end
<= newSegment.end) | |
69 ++endIndex; | |
70 // 4. Merge or adjust the succeeding segment if it overlaps. | |
71 if (endIndex < this._segments.length) { | |
72 merged = this._tryMerge(newSegment, this._segments[endIndex]); | |
73 if (merged) { | |
74 endIndex++; | |
75 newSegment = merged; | |
76 } else if (newSegment.intersects(this._segments[endIndex])) | |
77 this._segments[endIndex].begin = newSegment.end; | |
78 } | |
79 this._segments.splice(startIndex, endIndex - startIndex, newSegment); | |
80 }, | |
81 | |
82 /** | |
83 * @param {!WebInspector.SegmentedRange} that | |
84 */ | |
85 appendRange: function(that) | |
86 { | |
87 that.segments().forEach(segment => this.append(segment)); | |
88 }, | |
89 | |
90 /** | |
91 * @return {!Array<!WebInspector.Segment>} | |
92 */ | |
93 segments: function() | |
94 { | |
95 return this._segments; | |
96 }, | |
97 | |
98 /** | |
99 * @param {!WebInspector.Segment} first | |
100 * @param {!WebInspector.Segment} second | |
101 * @return {?WebInspector.Segment} | |
102 */ | |
103 _tryMerge: function(first, second) | |
104 { | |
105 var merged = this._mergeCallback && this._mergeCallback(first, second); | |
106 if (!merged) | |
107 return null; | |
108 merged.begin = first.begin; | |
109 merged.end = Math.max(first.end, second.end); | |
110 return merged; | |
111 } | |
112 }; | |
OLD | NEW |