Add algorithm for Residual Echo Detector.

webrtc/modules/audio_processing/echo_detector/sliding_window_minimum.cc

+/*
+ *  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.
+ */
+
+#include "webrtc/modules/audio_processing/echo_detector/sliding_window_minimum.h"
+
+#include <algorithm>
+#include <limits>
+
+#include "webrtc/base/checks.h"
+
+namespace webrtc {
+
+SlidingWindowMinimum::SlidingWindowMinimum(size_t window_size)
+    : values_(window_size), right_to_left_min_(window_size) {}
+SlidingWindowMinimum::SlidingWindowMinimum(SlidingWindowMinimum&& other) =
+    default;
+SlidingWindowMinimum::~SlidingWindowMinimum() = default;
+
+void SlidingWindowMinimum::AddValue(size_t new_value) {
+  left_to_right_min_ = std::min(left_to_right_min_, new_value);
+
+  RTC_DCHECK(window_index_ < values_.size());
+  values_[window_index_] = new_value;
+
+  window_index_++;
+  if (window_index_ == right_to_left_min_.size()) {
+    // Update right to left values.
+    RTC_DCHECK(values_.size() == right_to_left_min_.size());
+    auto i = right_to_left_min_.rbegin();
+    size_t rl = std::numeric_limits<size_t>::max();
+    // This loop is O(n), but it is only executed once every n iterations.
+    for (auto val = values_.rbegin(); val != values_.rend(); ++val, ++i) {
+      rl = std::min(rl, *val);
+      *i = rl;
+    }
+    left_to_right_min_ = std::numeric_limits<size_t>::max();
+    window_index_ = 0;
+  }
+}
+
+size_t SlidingWindowMinimum::GetMinimum() {
+  return std::min(left_to_right_min_, right_to_left_min_[window_index_]);
+}
+
+}  // namespace webrtc