text: // 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 CHROME_BROWSER_ASH_POLICY_STATUS_COLLECTOR_INTERVAL_MAP_H_
  #define CHROME_BROWSER_ASH_POLICY_STATUS_COLLECTOR_INTERVAL_MAP_H_
  
  #include <algorithm>
  #include <functional>
  #include <limits>
  #include <map>
  #include <type_traits>
  #include <utility>
  
  #include "base/check.h"
  
  namespace policy {
  
  // 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) {
      static_assert(std::is_integral<T>::value, "Integral types only.");
    }
  
    // 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() {
      static_assert(std::is_integral<KeyType>::value, "Integral types only.");
    }
    IntervalMapConstIterator(const MapType* map,
                             typename MapType::const_iterator iter)
        : map_(map), iter_(iter) {
      static_assert(std::is_integral<KeyType>::value, "Integral types only.");
    }
  
    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() {
      static_assert(std::is_integral<KeyType>::value, "Integral types only.");
      // 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 preceding entry, or ValueType() if no preceding 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) {
      auto insert_result = map_.emplace(k, ValueType());
      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 policy
  
  #endif  // CHROME_BROWSER_ASH_POLICY_STATUS_COLLECTOR_INTERVAL_MAP_H_
  