interval_map.h

// 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_