1/*
2 * Copyright (C) 2014 Apple Inc. All rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
6 * are met:
7 * 1. Redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer.
9 * 2. Redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution.
12 *
13 * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
14 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
17 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24 */
25
26#include "config.h"
27#include "PlatformTimeRanges.h"
28
29#include <math.h>
30#include <wtf/PrintStream.h>
31
32namespace WebCore {
33
34PlatformTimeRanges::PlatformTimeRanges(const MediaTime& start, const MediaTime& end)
35{
36 add(start, end);
37}
38
39void PlatformTimeRanges::invert()
40{
41 PlatformTimeRanges inverted;
42 MediaTime posInf = MediaTime::positiveInfiniteTime();
43 MediaTime negInf = MediaTime::negativeInfiniteTime();
44
45 if (!m_ranges.size())
46 inverted.add(negInf, posInf);
47 else {
48 MediaTime start = m_ranges.first().m_start;
49 if (start != negInf)
50 inverted.add(negInf, start);
51
52 for (size_t index = 0; index + 1 < m_ranges.size(); ++index)
53 inverted.add(m_ranges[index].m_end, m_ranges[index + 1].m_start);
54
55 MediaTime end = m_ranges.last().m_end;
56 if (end != posInf)
57 inverted.add(end, posInf);
58 }
59
60 m_ranges.swap(inverted.m_ranges);
61}
62
63void PlatformTimeRanges::intersectWith(const PlatformTimeRanges& other)
64{
65 PlatformTimeRanges invertedOther(other);
66
67 invertedOther.invert();
68 invert();
69 unionWith(invertedOther);
70 invert();
71}
72
73void PlatformTimeRanges::unionWith(const PlatformTimeRanges& other)
74{
75 PlatformTimeRanges unioned(*this);
76
77 for (size_t index = 0; index < other.m_ranges.size(); ++index) {
78 const Range& range = other.m_ranges[index];
79 unioned.add(range.m_start, range.m_end);
80 }
81
82 m_ranges.swap(unioned.m_ranges);
83}
84
85MediaTime PlatformTimeRanges::start(unsigned index) const
86{
87 bool ignoredValid;
88 return start(index, ignoredValid);
89}
90
91MediaTime PlatformTimeRanges::start(unsigned index, bool& valid) const
92{
93 if (index >= length()) {
94 valid = false;
95 return MediaTime::zeroTime();
96 }
97
98 valid = true;
99 return m_ranges[index].m_start;
100}
101
102MediaTime PlatformTimeRanges::end(unsigned index) const
103{
104 bool ignoredValid;
105 return end(index, ignoredValid);
106}
107
108MediaTime PlatformTimeRanges::end(unsigned index, bool& valid) const
109{
110 if (index >= length()) {
111 valid = false;
112 return MediaTime::zeroTime();
113 }
114
115 valid = true;
116 return m_ranges[index].m_end;
117}
118
119MediaTime PlatformTimeRanges::duration(unsigned index) const
120{
121 if (index >= length())
122 return MediaTime::invalidTime();
123
124 return m_ranges[index].m_end - m_ranges[index].m_start;
125}
126
127MediaTime PlatformTimeRanges::maximumBufferedTime() const
128{
129 if (!length())
130 return MediaTime::invalidTime();
131
132 return m_ranges[length() - 1].m_end;
133}
134
135void PlatformTimeRanges::add(const MediaTime& start, const MediaTime& end)
136{
137#if !PLATFORM(MAC) // https://bugs.webkit.org/show_bug.cgi?id=180253
138 ASSERT(start.isValid());
139 ASSERT(end.isValid());
140#endif
141 ASSERT(start <= end);
142
143 unsigned overlappingArcIndex;
144 Range addedRange(start, end);
145
146 // For each present range check if we need to:
147 // - merge with the added range, in case we are overlapping or contiguous
148 // - Need to insert in place, we we are completely, not overlapping and not contiguous
149 // in between two ranges.
150 //
151 // TODO: Given that we assume that ranges are correctly ordered, this could be optimized.
152
153 for (overlappingArcIndex = 0; overlappingArcIndex < m_ranges.size(); overlappingArcIndex++) {
154 if (addedRange.isOverlappingRange(m_ranges[overlappingArcIndex]) || addedRange.isContiguousWithRange(m_ranges[overlappingArcIndex])) {
155 // We need to merge the addedRange and that range.
156 addedRange = addedRange.unionWithOverlappingOrContiguousRange(m_ranges[overlappingArcIndex]);
157 m_ranges.remove(overlappingArcIndex);
158 overlappingArcIndex--;
159 } else {
160 // Check the case for which there is no more to do
161 if (!overlappingArcIndex) {
162 if (addedRange.isBeforeRange(m_ranges[0])) {
163 // First index, and we are completely before that range (and not contiguous, nor overlapping).
164 // We just need to be inserted here.
165 break;
166 }
167 } else {
168 if (m_ranges[overlappingArcIndex - 1].isBeforeRange(addedRange) && addedRange.isBeforeRange(m_ranges[overlappingArcIndex])) {
169 // We are exactly after the current previous range, and before the current range, while
170 // not overlapping with none of them. Insert here.
171 break;
172 }
173 }
174 }
175 }
176
177 // Now that we are sure we don't overlap with any range, just add it.
178 m_ranges.insert(overlappingArcIndex, addedRange);
179}
180
181bool PlatformTimeRanges::contain(const MediaTime& time) const
182{
183 return find(time) != notFound;
184}
185
186size_t PlatformTimeRanges::find(const MediaTime& time) const
187{
188 bool ignoreInvalid;
189 for (unsigned n = 0; n < length(); n++) {
190 if (time >= start(n, ignoreInvalid) && time <= end(n, ignoreInvalid))
191 return n;
192 }
193 return notFound;
194}
195
196MediaTime PlatformTimeRanges::nearest(const MediaTime& time) const
197{
198 MediaTime closestDelta = MediaTime::positiveInfiniteTime();
199 MediaTime closestTime = MediaTime::zeroTime();
200 unsigned count = length();
201 if (!count)
202 return MediaTime::invalidTime();
203
204 bool ignoreInvalid;
205
206 for (unsigned ndx = 0; ndx < count; ndx++) {
207 MediaTime startTime = start(ndx, ignoreInvalid);
208 MediaTime endTime = end(ndx, ignoreInvalid);
209 if (time >= startTime && time <= endTime)
210 return time;
211
212 MediaTime startTimeDelta = abs(startTime - time);
213 if (startTimeDelta < closestDelta) {
214 closestTime = startTime;
215 closestDelta = startTimeDelta;
216 }
217
218 MediaTime endTimeDelta = abs(endTime - time);
219 if (endTimeDelta < closestDelta) {
220 closestTime = endTime;
221 closestDelta = endTimeDelta;
222 }
223 }
224 return closestTime;
225}
226
227MediaTime PlatformTimeRanges::totalDuration() const
228{
229 MediaTime total = MediaTime::zeroTime();
230
231 for (unsigned n = 0; n < length(); n++)
232 total += abs(end(n) - start(n));
233 return total;
234}
235
236void PlatformTimeRanges::dump(PrintStream& out) const
237{
238 if (!length())
239 return;
240
241 for (size_t i = 0; i < length(); ++i)
242 out.print("[", start(i), "..", end(i), "] ");
243}
244
245}
246