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