blob: aa530034a008f4f406928ba1556885bbbe893bcb [file] [log] [blame]
// Copyright 2015 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
#ifndef MEDIA_BLINK_INTERVAL_MAP_H_
#define MEDIA_BLINK_INTERVAL_MAP_H_
#include <algorithm>
#include <limits>
#include <map>
#include "base/logging.h"
namespace media {
// An IntervalMap<KeyType, ValueType> maps every value of KeyType to
// a ValueType, and incrementing, decrementing and setting ranges of values
// has been optimized. The default state is to map all values in
// KeyType to ValueType(). (Which is usually zero.)
//
// Set/Increment operations should generally take
// O(log(N)) + O(M) time where N is the number of intervals in the map and
// M is the number of modified intervals.
//
// Internally, IntervalMap<> uses an std::map, where the beginning of each
// interval is stored along with the value for that interval. Adjacent intervals
// which have the same value are automatically merged. For instance, if you did:
//
// IntervalMap<int, int> tmp;
// tmp.IncrementInterval(2, 5, 2);
// tmp.IncrementInterval(4, 6, 1);
//
// Then:
// tmp[0] = 0
// tmp[1] = 0
// tmp[2] = 2
// tmp[3] = 2
// tmp[4] = 3
// tmp[5] = 1
// tmp[6] = 0
//
// If you iterate over tmp, you get the following intervals:
// -maxint .. 2 => 0
// 2 .. 4 => 2
// 4 .. 5 => 3
// 5 .. 6 => 1
// 6 .. maxint => 0
//
// Internally, this would be stored in a map as:
// -maxint:0, 2:2, 4:3, 5:1, 6:0
//
// TODO(hubbe): Consider consolidating with media::Ranges.
// Simple interval class.
// Interval ends are always non-inclusive.
// Please note that end <= begin is a valid (but empty) interval.
template <typename T>
struct Interval {
public:
Interval(const T& begin, const T& end) : begin(begin), end(end) {}
// May return empty intervals (begin >= end).
Interval Intersect(const Interval& other) const {
return Interval(std::max(begin, other.begin), std::min(end, other.end));
}
bool Empty() const { return begin >= end; }
T begin;
T end;
};
// The IntervalMapConstIterator points to an interval in an
// IntervalMap where all values are the same. Calling ++/--
// goes to the next/previous interval, which is guaranteed to
// have values different from the current interval.
template <typename KeyType,
typename ValueType,
class Compare = std::less<KeyType>,
class NumericLimits = std::numeric_limits<KeyType>>
class IntervalMapConstIterator {
public:
typedef std::map<KeyType, ValueType, Compare> MapType;
IntervalMapConstIterator() {}
IntervalMapConstIterator(const MapType* map,
typename MapType::const_iterator iter)
: map_(map), iter_(iter) {}
bool operator==(const IntervalMapConstIterator& other) const {
return iter_ == other.iter_;
}
bool operator!=(const IntervalMapConstIterator& other) const {
return iter_ != other.iter_;
}
// Returns the beginning of the current interval.
KeyType interval_begin() const {
DCHECK(iter_ != map_->end());
return iter_->first;
}
// Returns the end of the current interval, non-inclusive.
KeyType interval_end() const {
DCHECK(iter_ != map_->end());
typename MapType::const_iterator next = iter_;
++next;
if (next == map_->end()) {
return NumericLimits::max();
} else {
return next->first;
}
}
// Returns the current interval.
Interval<KeyType> interval() const {
return Interval<KeyType>(interval_begin(), interval_end());
}
// Returns the value associated with the current interval.
ValueType value() const {
DCHECK(iter_ != map_->end());
return iter_->second;
}
// Needed to make the following construct work:
// for (const auto& interval_value_pair : interval_map)
std::pair<Interval<KeyType>, ValueType> operator*() const {
return std::make_pair(interval(), value());
}
// Go to the next interval.
// The beginning of the next interval always matches the end of the current
// interval. (But should always have a different value.)
// Not allowed if we're already at map_->end().
void operator++() {
DCHECK(iter_ != map_->end());
++iter_;
}
// Go to the previous interval.
// The end of the previous interval always matches the beginning of the
// current interval. (But should always have a different value.)
// Not allowed if we're already at map_->begin().
void operator--() {
DCHECK(iter_ != map_->begin());
--iter_;
}
private:
const MapType* map_;
// Pointer to the entry in the IntervalMap that specifies the
// beginning of the current interval.
typename MapType::const_iterator iter_;
};
template <typename KeyType,
typename ValueType,
class Compare = std::less<KeyType>,
class NumericLimits = std::numeric_limits<KeyType>>
class IntervalMap {
public:
typedef std::map<KeyType, ValueType, Compare> MapType;
typedef IntervalMapConstIterator<KeyType, ValueType, Compare, NumericLimits>
const_iterator;
IntervalMap() {
// Adding an explicit entry for the default interval is not strictly needed,
// but simplifies the code a lot.
map_[NumericLimits::min()] = ValueType();
}
// Returns the value at a particular point.
// Defaults to ValueType().
ValueType operator[](const KeyType& k) const {
typename MapType::const_iterator i = map_.upper_bound(k);
DCHECK(i != map_.begin());
--i;
return i->second;
}
// Increase [from..to) by |how_much|.
void IncrementInterval(KeyType from, KeyType to, ValueType how_much) {
if (to <= from || how_much == 0)
return;
typename MapType::iterator a = MakeEntry(from);
typename MapType::iterator b = MakeEntry(to);
for (typename MapType::iterator i = a; i != b; ++i) {
i->second += how_much;
}
RemoveDuplicates(a);
// b may be invalid
RemoveDuplicates(map_.lower_bound(to));
}
// Set [from..to) to |how_much|.
void SetInterval(KeyType from, KeyType to, ValueType how_much) {
if (to <= from)
return;
typename MapType::iterator a = MakeEntry(from);
typename MapType::iterator b = MakeEntry(to);
a->second = how_much;
while (true) {
typename MapType::iterator c = a;
++c;
if (c == b) {
break;
} else {
map_.erase(c);
}
}
RemoveDuplicates(a);
// b may be invalid
RemoveDuplicates(map_.lower_bound(to));
}
// Returns an iterator to the first interval.
// Note, there is always at least one interval.
const_iterator begin() const { return const_iterator(&map(), map_.begin()); }
// Returns an end marker iterator.
const_iterator end() const { return const_iterator(&map(), map_.end()); }
// Returns an iterator to the interval containing |k|.
// Always returns a valid iterator.
const_iterator find(KeyType k) const {
typename MapType::const_iterator iter = map_.upper_bound(k);
DCHECK(iter != map_.begin());
--iter;
return const_iterator(&map(), iter);
}
bool empty() const { return map().size() == 1; }
void clear() {
map_.clear();
map_[NumericLimits::min()] = ValueType();
}
private:
const MapType& map() const { return map_; }
// Make an entry in map_ with the key |k| and return it's iterator.
// If such an entry already exists, just re-use it.
// If a new entry is created, it's value will be set to the same
// as the preceeding entry, or ValueType() if no preceeding entry exists.
// After calling this function, we'll need to call RemoveDuplicates()
// to clean up any duplicates that we made.
typename MapType::iterator MakeEntry(KeyType k) {
typename MapType::value_type tmp(k, 0);
std::pair<typename MapType::iterator, bool> insert_result;
insert_result = map_.insert(tmp);
if (insert_result.second) {
if (insert_result.first != map_.begin()) {
typename MapType::iterator i = insert_result.first;
--i;
insert_result.first->second = i->second;
}
}
return insert_result.first;
}
// Remove duplicates before and after |i|.
void RemoveDuplicates(typename MapType::iterator i) {
if (i == map_.end())
return;
typename MapType::iterator first = i;
typename MapType::iterator second = i;
if (i != map_.begin()) {
--first;
if (first->second == second->second) {
map_.erase(second);
second = first;
} else {
first = second;
}
}
++second;
if (second != map_.end() && first->second == second->second) {
map_.erase(second);
}
}
MapType map_;
};
} // namespace media
#endif // MEDIA_BLINK_INTERVAL_MAP_H_