RangeMap: A int->int mapping with fast range operations

media/blink/range_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_RANGE_MAP_H_
+#define MEDIA_BLINK_RANGE_MAP_H_
+
+#include <limits>
+#include <map>
+
+#include "base/logging.h"
+
+namespace media {
+
+// A RangeMap<KeyType, ValueType> is similar to a std::map<KeyType, ValueType>,

[xhwang, 2015/11/11 01:05:06]

This comment really confused me. There's a fundamental difference between a
RangeMap and a std::map. A range map has values defined for all integers from -∞
to +∞. But a std::map only have values defined in the key set.

The RangeMap is more like a Step function
(https://en.wikipedia.org/wiki/Step_function) defined for all integers where
range operations are optimized.

[hubbe, 2015/11/11 01:29:23]

Sure, but I had never heard of a step function before, I don't think that's a
very helpful description.
I'm open to other ideas though.

[xhwang, 2015/11/11 07:46:22]

Agreed step function isn't super self explanatory. Just some comments that could
let people better understand that a RangeMap is should be fine.

+// where incrementing, decrementing and setting ranges of values has been
+// optimized. The default state for a rangemap is to map all values in
+// KeyType to ValueType().
+//
+// Set/Increment operations should generally take
+// O(log(N)) + O(M) time where N is the number of ranges in the map and
+// M is the number of modified ranges.
+//
+// Internally, RangeMap<> uses an std::map, where the beginning of each range
+// is stored along with the value for that range. Adjacent ranges which have the
+// same value are automatically merged. For instance, if you did:
+//
+// RangeMap<int, int> tmp;
+// tmp.IncrementRange(2, 5, 2);
+// tmp.IncrementRange(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 ranges:
+//  -maxint .. 2 => 0
+//  2 .. 4 => 2
+//  4 .. 5 => 3
+//  5 .. 6 => 1
+//  6 .. maxint => 0
+//
+// Internally, this would be stored in a map as:
+//    2:2, 4:3, 5:1, 6:0
+//
+// TODO(hubbe): Consider consolidating with media::Ranges.
+
+// Simple range class.
+// Range ends are always non-inclusive.
+// Please note that end <= begin is a valid (but empty) range.
+template <typename T>
+struct Range {
+ public:
+  Range(const T& begin_, const T& end_) : begin(begin_), end(end_) {}

[xhwang, 2015/11/11 01:05:06]

I don't think we use |begin_| for non-member variables. The following should
just work fine:

Range(const T& begin, const T& end) : begin(begin), end(end) {}

[hubbe, 2015/11/11 01:29:23]

I'm pretty sure that results in an "variable used before initialization"
warning, but I could be wrong. Even if I'm wrong, I still wouldn't do that. I've
seen the begin(begin_) pattern elsewhere in chrome. I could do something like:

Range(const T& begin_init, const T& end_init) : begin(begin_init), end(end_init)
{}

if you prefer though.

[xhwang, 2015/11/11 07:46:22]

It should work:
http://stackoverflow.com/questions/6185020/initializing-member-variables-usin...

We use this a lot for structs.

[hubbe, 2015/11/12 06:57:43]

Done.

+
+  // May return empty ranges (begin >= end).
+  Range Intersect(const Range& other) const {
+    return Range(std::max(begin, other.begin), std::min(end, other.end));
+  }
+
+  bool Empty() const { return begin >= end; }
+
+  T begin;
+  T end;
+};
+
+template <typename KeyType,
+          typename ValueType,
+          class Compare = std::less<KeyType>,
+          class Minmax = std::numeric_limits<KeyType>>

[xhwang, 2015/11/11 01:05:06]

Minmax can be confusing given we have std::minmax. Stick to something like
NumericLimits or Limits?

[hubbe, 2015/11/11 01:29:23]

I choose you, NumericLimits.

+class RangeMapConstIterator {
+ public:
+  typedef std::map<KeyType, ValueType, Compare> MapType;
+  RangeMapConstIterator() {}
+  RangeMapConstIterator(const MapType* map,
+                        typename MapType::const_iterator first,
+                        typename MapType::const_iterator second)
+      : map_(map), first_(first), second_(second) {}
+
+  bool operator==(const RangeMapConstIterator& other) const {
+    return first_ == other.first_ && second_ == other.second_;
+  }
+
+  bool operator!=(const RangeMapConstIterator& other) const {
+    return first_ != other.first_ || second_ != other.second_;
+  }
+
+  // Returns the beginning of the current range.
+  KeyType range_begin() const {
+    if (first_ == map_->end()) {
+      return Minmax::min();
+    } else {
+      return first_->first;
+    }
+  }
+
+  // Returns the end of the current range, non-inclusive.
+  KeyType range_end() const {
+    if (second_ == map_->end()) {
+      return Minmax::max();
+    } else {
+      return second_->first;
+    }
+  }
+
+  // Returns the current range.
+  Range<KeyType> range() const {
+    return Range<KeyType>(range_begin(), range_end());
+  }
+
+  // Returns the value associated with the current range.
+  ValueType value() const {
+    if (first_ == map_->end())
+      return 0;
+    return first_->second;
+  }
+
+  // Needed to make the following construct work:
+  // for (const auto& range_value_pair : rangemap)
+  // Note however that this will skip the "end" range, which
+  // is usually ok since it generally has the default value.
+  std::pair<Range<KeyType>, ValueType> operator*() const {
+    return std::make_pair(range(), value());
+  }
+
+  // Go to the next range.
+  // The beginning of the next range always matches the end of the current
+  // range. (But should always have a different value.)
+  void operator++() {

[xhwang, 2015/11/11 01:05:06]

Add a note that the range could be empty after this operation.

[hubbe, 2015/11/11 01:29:23]

That shouldn't happen.
(Unless you're doing something weird near maxint maybe...)

+    first_ = second_;
+    second_++;
+  }
+
+  // Go to the previous range.
+  void operator--() {

[xhwang, 2015/11/11 01:05:06]

ditto

[hubbe, 2015/11/11 01:29:23]

See comment above.

+    second_ = first_;
+    if (first_ == map_->begin()) {
+      first_ = map_->end();
+    } else {
+      first_--;
+    }
+  }
+
+ private:
+  const MapType* map_;
+
+  // Pointer to the entry in the RangeMap that specifies the
+  // beginning of the current range. (Or map_->end() if we are
+  // currently at the first range.)
+  typename MapType::const_iterator first_;
+
+  // Pointer to the entry in the RangeMap that specifies the
+  // end of the current range (non-inclusive) Or, it will
+  // point to map_->end() if we are currently at the last range.
+  // Note that if there are no entries in map_, both first_ and
+  // second_ will point to map_->end().

[xhwang, 2015/11/11 01:05:06]

This could also happen when we  are at the first range, and operator--() is
called...

[hubbe, 2015/11/11 01:29:23]

Calling operator-- on the first range is not valid.
(Added DCHECKs for that.)

+  typename MapType::const_iterator second_;
+};
+
+template <typename KeyType,
+          typename ValueType,
+          class Compare = std::less<KeyType>,
+          class Minmax = std::numeric_limits<KeyType>>

[xhwang, 2015/11/11 01:05:06]

ditto

[hubbe, 2015/11/11 01:29:23]

Done.

+class RangeMap {
+ public:
+  typedef std::map<KeyType, ValueType, Compare> MapType;
+  typedef RangeMapConstIterator<KeyType, ValueType, Compare, Minmax>
+      const_iterator;
+
+  // 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);
+    if (i == map_.begin()) {
+      return 0;
+    } else {
+      --i;
+      return i->second;
+    }
+  }
+
+  // Increase [from..to) by |how_much|.
+  void IncrementRange(KeyType from, KeyType to, ValueType how_much) {
+    DCHECK_GE(to, from);
+    if (from == to || how_much == 0)

[xhwang, 2015/11/11 01:05:06]

Why do we allow |from == to|?

[hubbe, 2015/11/11 01:29:23]

No reason I suppose, I don't think I use that behaviour, so I can probably
change it to a DCHECK.

+      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 SetRange(KeyType from, KeyType to, ValueType how_much) {
+    DCHECK_GE(to, from);
+    if (from == to)

[xhwang, 2015/11/11 01:05:06]

Why do we allow this?

[hubbe, 2015/11/11 01:29:23]

See comment above.

+      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 range.
+  // Note, there is always at least one range.
+  const_iterator begin() const {
+    return const_iterator(&map(), map_.end(), map_.begin());
+  }
+
+  // Returns an iterator to the last range.
+  // Note that this works slightly different than most containers
+  // as end() returns a valid, but mostly uninteresting iterator.
+  // For example, if you have you do:
+  //   RangeMap<int, int> tmp;
+  //   tmp.IncrementRange(-5, 5, 1);
+  // Then end will return the range [6, maxint) with a value of 0.
+  const_iterator end() const {
+    if (map_.empty()) {
+      return const_iterator(&map(), map_.end(), map_.end());
+    }
+    typename MapType::const_iterator i = map_.end();
+    --i;
+    return const_iterator(&map(), i, map_.end());
+  }
+
+  // Returns an iterator to the range containing |k|.
+  // Always returns a valid iterator.
+  const_iterator find(KeyType k) const {
+    if (map_.empty()) {
+      return const_iterator(&map(), map_.end(), map_.end());
+    }
+    typename MapType::const_iterator i = map_.upper_bound(k);
+    typename MapType::const_iterator j = i;
+    if (j == map_.begin()) {
+      j = map_.end();
+    } else {
+      --j;
+    }
+    return const_iterator(&map(), j, i);
+  }
+
+ 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;
+    if (i == map_.begin() && i->second == 0) {
+      typename MapType::iterator j = i;
+      ++i;
+      map_.erase(j);
+      if (i == map_.end())
+        return;
+    }
+    if (i != map_.begin()) {
+      typename MapType::iterator j = i;
+      --i;
+      if (i->second == j->second) {
+        map_.erase(j);
+      }
+    }
+    typename MapType::iterator j = i;
+    ++j;
+    if (j != map_.end() && i->second == j->second) {
+      map_.erase(j);
+    }
+  }
+
+  MapType map_;
+};
+
+}  // namespace media
+
+#endif  // MEDIA_BLINK_RANGE_MAP_H_