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 #include #include #include "base/logging.h" namespace media { // An IntervalMap 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 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 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 , class NumericLimits = std::numeric_limits> class IntervalMapConstIterator { public: typedef std::map 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 interval() const { return Interval(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, 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 , class NumericLimits = std::numeric_limits> class IntervalMap { public: typedef std::map MapType; typedef IntervalMapConstIterator 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 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_