Moved sequence number specific operations from mod_ops.h

webrtc/modules/video_coding/sequence_number_util.h

+/*
+ *  Copyright (c) 2016 The WebRTC project authors. All Rights Reserved.
+ *
+ *  Use of this source code is governed by a BSD-style license
+ *  that can be found in the LICENSE file in the root of the source
+ *  tree. An additional intellectual property rights grant can be found
+ *  in the file PATENTS.  All contributing project authors may
+ *  be found in the AUTHORS file in the root of the source tree.
+ */
+
+#ifndef WEBRTC_MODULES_VIDEO_CODING_SEQUENCE_NUMBER_UTIL_H_
+#define WEBRTC_MODULES_VIDEO_CODING_SEQUENCE_NUMBER_UTIL_H_
+
+#include <limits>
+#include <type_traits>
+
+#include "webrtc/base/mod_ops.h"
+
+namespace webrtc {
+
+// Test if the sequence number a is ahead or at sequence number b.

[torbjorng (webrtc), 2016/03/17 10:47:27]

Nit: Please quite variable names, e.g. |a|.

[philipel, 2016/03/17 12:32:40]

Done.

+// If the two sequence numbers are at max distance from each other
+// then the sequence number with highest value is considered to
+// be ahead.
+template <typename T, T M>

[torbjorng (webrtc), 2016/03/17 10:47:27]

I cannot work out the intended semantics of this function, I'm afraid.
The first return criterium looks very suspicious, as it will change for
AheadOrAt(a,b) vs AheadOrAt(a+1 (mod M),b+1 (mod M)) for some a,b.

Defining a criteria for full ordering for a ring is slightly odd.  (It will
be true that a > b, b > c, c > a for some a,b,c, which is confusing.)

Is the "max distance' mentioned in the function comment floor(M/2)?
Please spell that out, and please explain why M/2 and more peculiarly
floor(M/2) bears any meaning.

Perhaps it would make more sense to have a 3-way function which allows
callers to explicitly define a "remaining distance" between |a| and |b| mod M?
A caller that thinks floor(M/2) is a good such limit would pass that in.

[philipel, 2016/03/17 12:32:40]

The reason for checking if the two numbers are at the maximum distance from each
other is to make sure that AheadOrAt(a,b) != AheadOrAt(b,a) which can cause
sorting algorithms to never finish. But maybe it is better to just DCHECK that
the numbers aren't at max distance from each other since we can't know, even
according to our own definition, which number that is ahead.

About the ordering, you should not think of wrapping sequence numbers as a ring,
you should think of them as a pragmatic solution for sequence numbers. There is
no strict mathematic definition involved, just pragmatic ideas. :)

I will expand the comment with more details of the behavior of this function.

I don't really understand your suggestion about a 3-way function, could you
clarify?

+inline bool AheadOrAt(T a, T b) {
+  static_assert(std::is_unsigned<T>::value,
+                "Type must be an unsigned integer.");
+  const T maxDist = M / 2;
+  if (MinDiff<T, M>(a, b) == maxDist)

[torbjorng (webrtc), 2016/03/21 12:32:26]

We agree that this ought to be triggered just for even M.
(Test cases also need updating.)

[philipel, 2016/03/21 12:56:20]

Done.

+    return b < a;
+  return ForwardDiff<T, M>(b, a) < maxDist;
+}
+
+template <typename T>
+inline bool AheadOrAt(T a, T b) {
+  static_assert(std::is_unsigned<T>::value,
+                "Type must be an unsigned integer.");
+  const T maxDist = std::numeric_limits<T>::max() / 2 + T(1);
+  if (a - b == maxDist)
+    return b < a;
+  return ForwardDiff(b, a) < maxDist;
+}
+
+// Test if sequence number a is ahead of sequence number b.
+template <typename T, T M>
+inline bool AheadOf(T a, T b) {
+  static_assert(std::is_unsigned<T>::value,
+                "Type must be an unsigned integer.");
+  return a != b && AheadOrAt<T, M>(a, b);
+}
+
+template <typename T>
+inline bool AheadOf(T a, T b) {
+  static_assert(std::is_unsigned<T>::value,
+                "Type must be an unsigned integer.");
+  return a != b && AheadOrAt(a, b);
+}
+
+template <typename T, typename M>
+struct SeqNumComp_;
+
+template <typename T, T M>
+struct SeqNumComp_<T, std::integral_constant<T, M>> {
+  bool operator()(T a, T b) const {
+    return AheadOf<T, M>(a, b);
+  }
+};
+
+template <typename T>
+struct SeqNumComp_<T, std::integral_constant<T, T(0)>> {
+  bool operator()(T a, T b) const {
+    return AheadOf<T>(a, b);
+  }
+};
+
+// Comparator used to compare sequence numbers in a continuous fashion.
+//
+// WARNING! If used to sort sequence numbers of length M then the interval
+//          covered by the sequence numbers may not be larger than floor(M/2).
+template <typename T, T M = 0>
+struct AscendingSeqNumComp :
+        private SeqNumComp_<T, std::integral_constant<T, M>> {
+  bool operator()(T a, T b) const {
+    return SeqNumComp_<T, std::integral_constant<T, M>>::operator()(a, b);
+  }
+};
+
+// Comparator used to compare sequence numbers in a continuous fashion.
+//
+// WARNING! If used to sort sequence numbers of length M then the interval
+//          covered by the sequence numbers may not be larger than floor(M/2).
+template <typename T, T M = 0>
+struct DescendingSeqNumComp :
+        private SeqNumComp_<T, std::integral_constant<T, M>> {
+  bool operator()(T a, T b) const {
+    return SeqNumComp_<T, std::integral_constant<T, M>>::operator()(b, a);
+  }
+};
+
+}  // namespace webrtc
+
+#endif  // WEBRTC_MODULES_VIDEO_CODING_SEQUENCE_NUMBER_UTIL_H_