Source/WebCore/platform/graphics/PlatformTimeRanges.cpp

   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
  32 namespace WebCore {
  33
  34 PlatformTimeRanges::PlatformTimeRanges(const MediaTime& start, const MediaTime& end)
  35 {
  36     add(start, end);
  37 }
  38
  39 PlatformTimeRanges::PlatformTimeRanges(const PlatformTimeRanges& other)
  40 {
  41     copy(other);
  42 }
  43
  44 PlatformTimeRanges& PlatformTimeRanges::operator=(const PlatformTimeRanges& other)
  45 {
  46     return copy(other);
  47 }
  48
  49 PlatformTimeRanges& PlatformTimeRanges::copy(const PlatformTimeRanges& other)
  50 {
  51     unsigned size = other.m_ranges.size();
  52     for (unsigned i = 0; i < size; i++)
  53         add(other.m_ranges[i].m_start, other.m_ranges[i].m_end);
  54
  55     return *this;
  56 }
  57
  58 void PlatformTimeRanges::invert()
  59 {
  60     PlatformTimeRanges inverted;
  61     MediaTime posInf = MediaTime::positiveInfiniteTime();
  62     MediaTime negInf = MediaTime::negativeInfiniteTime();
  63
  64     if (!m_ranges.size())
  65         inverted.add(negInf, posInf);
  66     else {
  67         MediaTime start = m_ranges.first().m_start;
  68         if (start != negInf)
  69             inverted.add(negInf, start);
  70
  71         for (size_t index = 0; index + 1 < m_ranges.size(); ++index)
  72             inverted.add(m_ranges[index].m_end, m_ranges[index + 1].m_start);
  73
  74         MediaTime end = m_ranges.last().m_end;
  75         if (end != posInf)
  76             inverted.add(end, posInf);
  77     }
  78
  79     m_ranges.swap(inverted.m_ranges);
  80 }
  81
  82 void PlatformTimeRanges::intersectWith(const PlatformTimeRanges& other)
  83 {
  84     PlatformTimeRanges invertedOther(other);
  85
  86     invertedOther.invert();
  87     invert();
  88     unionWith(invertedOther);
  89     invert();
  90 }
  91
  92 void PlatformTimeRanges::unionWith(const PlatformTimeRanges& other)
  93 {
  94     PlatformTimeRanges unioned(*this);
  95
  96     for (size_t index = 0; index < other.m_ranges.size(); ++index) {
  97         const Range& range = other.m_ranges[index];
  98         unioned.add(range.m_start, range.m_end);
  99     }
 100
 101     m_ranges.swap(unioned.m_ranges);
 102 }
 103
 104 MediaTime PlatformTimeRanges::start(unsigned index) const
 105 {
 106     bool ignoredValid;
 107     return start(index, ignoredValid);
 108 }
 109
 110 MediaTime PlatformTimeRanges::start(unsigned index, bool& valid) const
 111 {
 112     if (index >= length()) {
 113         valid = false;
 114         return MediaTime::zeroTime();
 115     }
 116
 117     valid = true;
 118     return m_ranges[index].m_start;
 119 }
 120
 121 MediaTime PlatformTimeRanges::end(unsigned index) const
 122 {
 123     bool ignoredValid;
 124     return end(index, ignoredValid);
 125 }
 126
 127 MediaTime PlatformTimeRanges::end(unsigned index, bool& valid) const
 128 {
 129     if (index >= length()) {
 130         valid = false;
 131         return MediaTime::zeroTime();
 132     }
 133
 134     valid = true;
 135     return m_ranges[index].m_end;
 136 }
 137
 138 MediaTime PlatformTimeRanges::duration(unsigned index) const
 139 {
 140     if (index >= length())
 141         return MediaTime::invalidTime();
 142
 143     return m_ranges[index].m_end - m_ranges[index].m_start;
 144 }
 145
 146 MediaTime PlatformTimeRanges::maximumBufferedTime() const
 147 {
 148     if (!length())
 149         return MediaTime::invalidTime();
 150
 151     return m_ranges[length() - 1].m_end;
 152 }
 153
 154 void PlatformTimeRanges::add(const MediaTime& start, const MediaTime& end)
 155 {
 156     ASSERT(start <= end);
 157     unsigned overlappingArcIndex;
 158     Range addedRange(start, end);
 159
 160     // For each present range check if we need to:
 161     // - merge with the added range, in case we are overlapping or contiguous
 162     // - Need to insert in place, we we are completely, not overlapping and not contiguous
 163     // in between two ranges.
 164     //
 165     // TODO: Given that we assume that ranges are correctly ordered, this could be optimized.
 166
 167     for (overlappingArcIndex = 0; overlappingArcIndex < m_ranges.size(); overlappingArcIndex++) {
 168         if (addedRange.isOverlappingRange(m_ranges[overlappingArcIndex]) || addedRange.isContiguousWithRange(m_ranges[overlappingArcIndex])) {
 169             // We need to merge the addedRange and that range.
 170             addedRange = addedRange.unionWithOverlappingOrContiguousRange(m_ranges[overlappingArcIndex]);
 171             m_ranges.remove(overlappingArcIndex);
 172             overlappingArcIndex--;
 173         } else {
 174             // Check the case for which there is no more to do
 175             if (!overlappingArcIndex) {
 176                 if (addedRange.isBeforeRange(m_ranges[0])) {
 177                     // First index, and we are completely before that range (and not contiguous, nor overlapping).
 178                     // We just need to be inserted here.
 179                     break;
 180                 }
 181             } else {
 182                 if (m_ranges[overlappingArcIndex - 1].isBeforeRange(addedRange) && addedRange.isBeforeRange(m_ranges[overlappingArcIndex])) {
 183                     // We are exactly after the current previous range, and before the current range, while
 184                     // not overlapping with none of them. Insert here.
 185                     break;
 186                 }
 187             }
 188         }
 189     }
 190
 191     // Now that we are sure we don't overlap with any range, just add it.
 192     m_ranges.insert(overlappingArcIndex, addedRange);
 193 }
 194
 195 bool PlatformTimeRanges::contain(const MediaTime& time) const
 196 {
 197     return find(time) != notFound;
 198 }
 199
 200 size_t PlatformTimeRanges::find(const MediaTime& time) const
 201 {
 202     bool ignoreInvalid;
 203     for (unsigned n = 0; n < length(); n++) {
 204         if (time >= start(n, ignoreInvalid) && time <= end(n, ignoreInvalid))
 205             return n;
 206     }
 207     return notFound;
 208 }
 209
 210 MediaTime PlatformTimeRanges::nearest(const MediaTime& time) const
 211 {
 212     MediaTime closestDelta = MediaTime::positiveInfiniteTime();
 213     MediaTime closestTime = MediaTime::zeroTime();
 214     unsigned count = length();
 215     bool ignoreInvalid;
 216
 217     for (unsigned ndx = 0; ndx < count; ndx++) {
 218         MediaTime startTime = start(ndx, ignoreInvalid);
 219         MediaTime endTime = end(ndx, ignoreInvalid);
 220         if (time >= startTime && time <= endTime)
 221             return time;
 222
 223         MediaTime startTimeDelta = abs(startTime - time);
 224         if (startTimeDelta < closestDelta) {
 225             closestTime = startTime;
 226             closestDelta = startTimeDelta;
 227         }
 228
 229         MediaTime endTimeDelta = abs(endTime - time);
 230         if (endTimeDelta < closestDelta) {
 231             closestTime = endTime;
 232             closestDelta = endTimeDelta;
 233         }
 234     }
 235     return closestTime;
 236 }
 237
 238 MediaTime PlatformTimeRanges::totalDuration() const
 239 {
 240     MediaTime total = MediaTime::zeroTime();
 241
 242     for (unsigned n = 0; n < length(); n++)
 243         total += abs(end(n) - start(n));
 244     return total;
 245 }
 246
 247 void PlatformTimeRanges::dump(PrintStream& out) const
 248 {
 249     if (!length())
 250         return;
 251
 252     for (size_t i = 0; i < length(); ++i)
 253         out.print("[", start(i), "..", end(i), "] ");
 254 }
 255
 256 }