Add algorithm for Residual Echo Detector.

webrtc/modules/audio_processing/echo_detector/sliding_window_minimum.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_AUDIO_PROCESSING_ECHO_DETECTOR_SLIDING_WINDOW_MINIMUM_H_
+#define WEBRTC_MODULES_AUDIO_PROCESSING_ECHO_DETECTOR_SLIDING_WINDOW_MINIMUM_H_
+
+#include <vector>
+
+namespace webrtc {
+
+// This class determines the minimum value of the last entered N values in an
+// efficient way: amortized O(1). The implementation is based on the method
+// described in http://stackoverflow.com/a/17249084.
+class SlidingWindowMinimum {
+ public:
+  explicit SlidingWindowMinimum(size_t window_size);
+  SlidingWindowMinimum(SlidingWindowMinimum&& other);
+  ~SlidingWindowMinimum();
+
+  // Add a new value.
+  void AddValue(size_t new_value);
+  // Get the minimum of the previous N added values.
+  size_t GetMinimum();
+
+ private:
+  // This is a circular buffer containing the previous values.
+  std::vector<size_t> values_;
+  // This is a circular buffer containing the previous "RL" values.
+  std::vector<size_t> right_to_left_min_;
+  // For storing the previous LR value.
+  size_t left_to_right_min_;
+  // Counter for tracking how far into the window we are.
+  size_t window_index_ = 0;
+};
+
+}  // namespace webrtc
+
+#endif  // WEBRTC_MODULES_AUDIO_PROCESSING_ECHO_DETECTOR_SLIDING_WINDOW_MINIMUM_H_