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