Blimp: add delta encoding family of functions

blimp/net/delta_encoding.h

+// Copyright 2016 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 BLIMP_NET_DELTA_ENCODING_H_
+#define BLIMP_NET_DELTA_ENCODING_H_
+
+#include <algorithm>
+#include <functional>
+#include <utility>
+
+// This file contains utility functions to concisely compute and apply
+// delta encodings of arbitrarily-typed sequences of values. Delta-encoded
+// numeric values tend to be smaller in magnitude than their source values
+// which, when combined with variable integer encoding (a la protobuf), results
+// in a smaller wire size.
+//
+// e.g. DeltaEncode([4, 1, 5]) => [4, -3, 4]
+//      DeltaDecode([4, -3, 4]) => [4, 1, 5]
+//
+// If ordering doesn't matter, then the function SortAndDeltaEncode()
+// can be used to compute a delta encoding with the smallest possible values.
+//
+// e.g. SortAndDeltaEncode([4, 1, 5]) => [1, 3, 1]
+//      DeltaDecode([1, 3, 1]) => [1, 4, 5]
+//
+// Delta encodings can also be computed for structured or non-numeric data
+// types as well, so long as functions are provided for differencing and
+// reconstituting the data. This can also be applied to delta encode or elide
+// across fields of a struct, for example.
+
+namespace blimp {
+
+template <typename T>
+inline T minus(const T& lhs, const T& rhs) {
+  return lhs - rhs;
+}
+
+template <typename T>
+inline T plus(const T& lhs, const T& rhs) {
+  return lhs + rhs;
+}
+
+template <typename T>
+inline bool less(const T& lhs, const T& rhs) {

[Wez, 2016/09/02 20:01:09]

nit: this would be lessthan, I think.

But, again, we should give these less generic names, to avoid naming clashes.

[Kevin M, 2016/09/02 21:12:44]

Done.

+  return lhs < rhs;
+}
+
+// Homogeneously-typed signature for functions that compute and apply deltas.
+template <typename T>
+using BinaryFunction = T (*)(const T&, const T&);
+
+// Delta-encodes a iterated sequence of values in-place.
+// |begin|: An iterator pointing to the beginning of the sequence.
+// |end|: An iterator pointing to the end of the sequence.
+// |compute_delta_fn|: Optional function which computes the delta between
+// every element and its next successor.
+template <typename I>
+void DeltaEncode(I begin,
+                 I end,
+                 BinaryFunction<typename std::iterator_traits<I>::value_type>
+                     compute_delta_fn = &minus) {
+  if (begin == end) {
+    return;
+  }
+
+  I current = begin;
+  typename std::iterator_traits<I>::value_type value = *current;
+  ++current;
+  for (; current != end; ++current) {
+    value = (*compute_delta_fn)(*current, value);
+
+    // Put the delta in place and store the actual value into |value|, ready for
+    // the next iteration.
+    std::swap(*current, value);
+  }
+}
+
+// Delta-decodes a iterated sequence of values in-place.
+// |begin|: An iterator pointing to the beginning of the sequence.
+// |end|: An iterator pointing to the end of the sequence.
+// |apply_fn|: Optional binary function which combines the value of every
+// element with that of its immediate predecessor.
+template <typename I>
+void DeltaDecode(I begin,
+                 I end,
+                 BinaryFunction<typename std::iterator_traits<I>::value_type>
+                     apply_fn = &plus) {
+  if (begin == end) {
+    return;
+  }
+
+  I current = begin;
+  typename std::iterator_traits<I>::value_type previous_value = *current;
+  ++current;
+  for (; current != end; ++current) {
+    *current = apply_fn(previous_value, *current);
+    previous_value = *current;
+  }
+}
+
+// Convenience function for sorting and delta-encoding a sequence of values.
+// The value type must support std::sort(), either by natively supporting
+// inequality comparison or with custom comparison function |comparison_fn|.
+template <typename I>
+inline void SortAndDeltaEncode(
+    I begin,
+    I end,
+    BinaryFunction<typename std::iterator_traits<I>::value_type>
+        compute_delta_fn = &minus,
+    bool (*comparison_fn)(const typename std::iterator_traits<I>::value_type&,
+                          const typename std::iterator_traits<I>::value_type&) =
+        less<typename std::iterator_traits<I>::value_type>) {
+  std::sort(begin, end, comparison_fn);
+  DeltaEncode(begin, end, compute_delta_fn);
+}
+
+}  // namespace blimp
+
+#endif  // BLIMP_NET_DELTA_ENCODING_H_