1 /* 2 * Copyright (C) 2007, 2009, 2010 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 COMPUTER, 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 COMPUTER, 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 "core/html/TimeRanges.h" 28 29 #include "bindings/core/v8/ExceptionMessages.h" 30 #include "bindings/core/v8/ExceptionState.h" 31 #include "bindings/core/v8/ExceptionStatePlaceholder.h" 32 #include "core/dom/ExceptionCode.h" 33 #include <math.h> 34 35 using namespace blink; 36 37 TimeRanges::TimeRanges(double start, double end) 38 { 39 add(start, end); 40 } 41 42 PassRefPtrWillBeRawPtr<TimeRanges> TimeRanges::create(const blink::WebTimeRanges& webRanges) 43 { 44 RefPtrWillBeRawPtr<TimeRanges> ranges = TimeRanges::create(); 45 46 unsigned size = webRanges.size(); 47 for (unsigned i = 0; i < size; ++i) 48 ranges->add(webRanges[i].start, webRanges[i].end); 49 50 return ranges.release(); 51 } 52 53 PassRefPtrWillBeRawPtr<TimeRanges> TimeRanges::copy() const 54 { 55 RefPtrWillBeRawPtr<TimeRanges> newSession = TimeRanges::create(); 56 57 unsigned size = m_ranges.size(); 58 for (unsigned i = 0; i < size; i++) 59 newSession->add(m_ranges[i].m_start, m_ranges[i].m_end); 60 61 return newSession.release(); 62 } 63 64 void TimeRanges::invert() 65 { 66 RefPtrWillBeRawPtr<TimeRanges> inverted = TimeRanges::create(); 67 double posInf = std::numeric_limits<double>::infinity(); 68 double negInf = -std::numeric_limits<double>::infinity(); 69 70 if (!m_ranges.size()) 71 inverted->add(negInf, posInf); 72 else { 73 double start = m_ranges.first().m_start; 74 if (start != negInf) 75 inverted->add(negInf, start); 76 77 for (size_t index = 0; index + 1 < m_ranges.size(); ++index) 78 inverted->add(m_ranges[index].m_end, m_ranges[index + 1].m_start); 79 80 double end = m_ranges.last().m_end; 81 if (end != posInf) 82 inverted->add(end, posInf); 83 } 84 85 m_ranges.swap(inverted->m_ranges); 86 } 87 88 void TimeRanges::intersectWith(const TimeRanges* other) 89 { 90 ASSERT(other); 91 92 if (other == this) 93 return; 94 95 RefPtrWillBeRawPtr<TimeRanges> invertedOther = other->copy(); 96 invertedOther->invert(); 97 98 invert(); 99 unionWith(invertedOther.get()); 100 invert(); 101 } 102 103 void TimeRanges::unionWith(const TimeRanges* other) 104 { 105 ASSERT(other); 106 RefPtrWillBeRawPtr<TimeRanges> unioned = copy(); 107 for (size_t index = 0; index < other->m_ranges.size(); ++index) { 108 const Range& range = other->m_ranges[index]; 109 unioned->add(range.m_start, range.m_end); 110 } 111 112 m_ranges.swap(unioned->m_ranges); 113 } 114 115 double TimeRanges::start(unsigned index, ExceptionState& exceptionState) const 116 { 117 if (index >= length()) { 118 exceptionState.throwDOMException(IndexSizeError, ExceptionMessages::indexExceedsMaximumBound("index", index, length())); 119 return 0; 120 } 121 return m_ranges[index].m_start; 122 } 123 124 double TimeRanges::end(unsigned index, ExceptionState& exceptionState) const 125 { 126 if (index >= length()) { 127 exceptionState.throwDOMException(IndexSizeError, ExceptionMessages::indexExceedsMaximumBound("index", index, length())); 128 return 0; 129 } 130 return m_ranges[index].m_end; 131 } 132 133 void TimeRanges::add(double start, double end) 134 { 135 ASSERT(start <= end); 136 unsigned overlappingArcIndex; 137 Range addedRange(start, end); 138 139 // For each present range check if we need to: 140 // - merge with the added range, in case we are overlapping or contiguous 141 // - Need to insert in place, we we are completely, not overlapping and not contiguous 142 // in between two ranges. 143 // 144 // TODO: Given that we assume that ranges are correctly ordered, this could be optimized. 145 146 for (overlappingArcIndex = 0; overlappingArcIndex < m_ranges.size(); overlappingArcIndex++) { 147 if (addedRange.isOverlappingRange(m_ranges[overlappingArcIndex]) 148 || addedRange.isContiguousWithRange(m_ranges[overlappingArcIndex])) { 149 // We need to merge the addedRange and that range. 150 addedRange = addedRange.unionWithOverlappingOrContiguousRange(m_ranges[overlappingArcIndex]); 151 m_ranges.remove(overlappingArcIndex); 152 overlappingArcIndex--; 153 } else { 154 // Check the case for which there is no more to do 155 if (!overlappingArcIndex) { 156 if (addedRange.isBeforeRange(m_ranges[0])) { 157 // First index, and we are completely before that range (and not contiguous, nor overlapping). 158 // We just need to be inserted here. 159 break; 160 } 161 } else { 162 if (m_ranges[overlappingArcIndex - 1].isBeforeRange(addedRange) 163 && addedRange.isBeforeRange(m_ranges[overlappingArcIndex])) { 164 // We are exactly after the current previous range, and before the current range, while 165 // not overlapping with none of them. Insert here. 166 break; 167 } 168 } 169 } 170 } 171 172 // Now that we are sure we don't overlap with any range, just add it. 173 m_ranges.insert(overlappingArcIndex, addedRange); 174 } 175 176 bool TimeRanges::contain(double time) const 177 { 178 for (unsigned n = 0; n < length(); n++) { 179 if (time >= start(n, IGNORE_EXCEPTION) && time <= end(n, IGNORE_EXCEPTION)) 180 return true; 181 } 182 return false; 183 } 184 185 double TimeRanges::nearest(double newPlaybackPosition, double currentPlaybackPosition) const 186 { 187 unsigned count = length(); 188 double bestMatch = 0; 189 double bestDelta = std::numeric_limits<double>::infinity(); 190 for (unsigned ndx = 0; ndx < count; ndx++) { 191 double startTime = start(ndx, IGNORE_EXCEPTION); 192 double endTime = end(ndx, IGNORE_EXCEPTION); 193 if (newPlaybackPosition >= startTime && newPlaybackPosition <= endTime) 194 return newPlaybackPosition; 195 196 double delta, match; 197 if (newPlaybackPosition < startTime) { 198 delta = startTime - newPlaybackPosition; 199 match = startTime; 200 } else { 201 delta = newPlaybackPosition - endTime; 202 match = endTime; 203 } 204 205 if (delta < bestDelta || (delta == bestDelta 206 && std::abs(currentPlaybackPosition - match) < std::abs(currentPlaybackPosition - bestMatch))) { 207 bestDelta = delta; 208 bestMatch = match; 209 } 210 } 211 return bestMatch; 212 } 213 214 void TimeRanges::trace(Visitor* visitor) 215 { 216 visitor->trace(m_ranges); 217 } 218