chromium/third_party/blink/renderer/platform/media/interval_map.h

// Copyright 2015 The Chromium Authors
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#ifndef THIRD_PARTY_BLINK_RENDERER_PLATFORM_MEDIA_INTERVAL_MAP_H_
#define THIRD_PARTY_BLINK_RENDERER_PLATFORM_MEDIA_INTERVAL_MAP_H_

#include <algorithm>
#include <limits>
#include <map>

#include "base/check.h"
#include "base/memory/raw_ptr.h"
#include "base/not_fatal_until.h"
#include "third_party/blink/renderer/platform/allow_discouraged_type.h"

namespace blink {

// 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 { … };

// 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)
      : … { … }

  bool operator==(const IntervalMapConstIterator& other) const { … }

  bool operator!=(const IntervalMapConstIterator& other) const { … }

  // Returns the beginning of the current interval.
  KeyType interval_begin() const { … }

  // Returns the end of the current interval, non-inclusive.
  KeyType interval_end() const { … }

  // Returns the current interval.
  Interval<KeyType> interval() const { … }

  // Returns the value associated with the current interval.
  ValueType value() const { … }

  // Needed to make the following construct work:
  // for (const auto& interval_value_pair : interval_map)
  std::pair<Interval<KeyType>, ValueType> operator*() const { … }

  // 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++() { … }

  // 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--() { … }

 private:
  raw_ptr<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() { … }

  // Returns the value at a particular point.
  // Defaults to ValueType().
  ValueType operator[](const KeyType& k) const { … }

  // Increase [from..to) by |how_much|.
  void IncrementInterval(KeyType from, KeyType to, ValueType how_much) { … }

  // Set [from..to) to |how_much|.
  void SetInterval(KeyType from, KeyType to, ValueType how_much) { … }

  // Returns an iterator to the first interval.
  // Note, there is always at least one interval.
  const_iterator begin() const { … }

  // Returns an end marker iterator.
  const_iterator end() const { … }

  // Returns an iterator to the interval containing |k|.
  // Always returns a valid iterator.
  const_iterator find(KeyType k) const { … }

  bool empty() const { … }
  void clear() { … }

 private:
  const MapType& map() const { … }

  // 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) { … }

  // Remove duplicates before and after |i|.
  void RemoveDuplicates(typename MapType::iterator i) { … }

  MapType map_ ALLOW_DISCOURAGED_TYPE("HashMap lacks key sorting.");
};

}  // namespace blink

#endif  // THIRD_PARTY_BLINK_RENDERER_PLATFORM_MEDIA_INTERVAL_MAP_H_