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