Add a simple ring buffer and use it for holding TFLite model inputs.

Bug: 167946763
Test: atest libinput_tests
Change-Id: I7e50d38ed0c593aebc5fdc6af4b25868505d48bc
diff --git a/include/input/RingBuffer.h b/include/input/RingBuffer.h
new file mode 100644
index 0000000..67984b7
--- /dev/null
+++ b/include/input/RingBuffer.h
@@ -0,0 +1,293 @@
+/*
+ * Copyright (C) 2023 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#pragma once
+
+#include <algorithm>
+#include <compare>
+#include <cstddef>
+#include <iterator>
+#include <memory>
+#include <type_traits>
+#include <utility>
+
+#include <android-base/logging.h>
+#include <android-base/stringprintf.h>
+
+namespace android {
+
+// A fixed-size ring buffer of elements.
+//
+// Elements can only be removed from the front/back or added to the front/back, but with O(1)
+// performance. Elements from the opposing side are evicted when new elements are pushed onto a full
+// buffer.
+template <typename T>
+class RingBuffer {
+public:
+    using value_type = T;
+    using size_type = size_t;
+    using difference_type = ptrdiff_t;
+    using reference = value_type&;
+    using const_reference = const value_type&;
+    using pointer = value_type*;
+    using const_pointer = const value_type*;
+
+    template <typename U>
+    class Iterator;
+    using iterator = Iterator<T>;
+    using const_iterator = Iterator<const T>;
+
+    // Creates an empty ring buffer that can hold some capacity.
+    explicit RingBuffer(size_type capacity)
+          : mBuffer(std::allocator<value_type>().allocate(capacity)), mCapacity(capacity) {}
+
+    // Creates a full ring buffer holding a fixed number of elements initialised to some value.
+    explicit RingBuffer(size_type count, const_reference value) : RingBuffer(count) {
+        while (count) {
+            pushBack(value);
+            --count;
+        }
+    }
+
+    RingBuffer(const RingBuffer& other) : RingBuffer(other.capacity()) {
+        for (const auto& element : other) {
+            pushBack(element);
+        }
+    }
+
+    RingBuffer(RingBuffer&& other) noexcept { *this = std::move(other); }
+
+    ~RingBuffer() {
+        if (mBuffer) {
+            clear();
+            std::allocator<value_type>().deallocate(mBuffer, mCapacity);
+        }
+    }
+
+    RingBuffer& operator=(const RingBuffer& other) { return *this = RingBuffer(other); }
+
+    RingBuffer& operator=(RingBuffer&& other) noexcept {
+        if (this == &other) {
+            return *this;
+        }
+        if (mBuffer) {
+            clear();
+            std::allocator<value_type>().deallocate(mBuffer, mCapacity);
+        }
+        mBuffer = std::move(other.mBuffer);
+        mCapacity = other.mCapacity;
+        mBegin = other.mBegin;
+        mSize = other.mSize;
+        other.mBuffer = nullptr;
+        other.mCapacity = 0;
+        other.mBegin = 0;
+        other.mSize = 0;
+        return *this;
+    }
+
+    iterator begin() { return {*this, 0}; }
+    const_iterator begin() const { return {*this, 0}; }
+    iterator end() { return {*this, mSize}; }
+    const_iterator end() const { return {*this, mSize}; }
+
+    reference operator[](size_type i) { return mBuffer[bufferIndex(i)]; }
+    const_reference operator[](size_type i) const { return mBuffer[bufferIndex(i)]; }
+
+    // Removes all elements from the buffer.
+    void clear() {
+        std::destroy(begin(), end());
+        mSize = 0;
+    }
+
+    // Removes and returns the first element from the buffer.
+    value_type popFront() {
+        value_type element = mBuffer[mBegin];
+        std::destroy_at(std::addressof(mBuffer[mBegin]));
+        mBegin = next(mBegin);
+        --mSize;
+        return element;
+    }
+
+    // Removes and returns the last element from the buffer.
+    value_type popBack() {
+        size_type backIndex = bufferIndex(mSize - 1);
+        value_type element = mBuffer[backIndex];
+        std::destroy_at(std::addressof(mBuffer[backIndex]));
+        --mSize;
+        return element;
+    }
+
+    // Adds an element to the front of the buffer.
+    void pushFront(const value_type& element) { pushFront(value_type(element)); }
+    void pushFront(value_type&& element) {
+        mBegin = previous(mBegin);
+        if (size() == capacity()) {
+            mBuffer[mBegin] = std::forward<value_type>(element);
+        } else {
+            // The space at mBuffer[mBegin] is uninitialised.
+            // TODO: Use std::construct_at when it becomes available.
+            new (std::addressof(mBuffer[mBegin])) value_type(std::forward<value_type>(element));
+            ++mSize;
+        }
+    }
+
+    // Adds an element to the back of the buffer.
+    void pushBack(const value_type& element) { pushBack(value_type(element)); }
+    void pushBack(value_type&& element) {
+        if (size() == capacity()) {
+            mBuffer[mBegin] = std::forward<value_type>(element);
+            mBegin = next(mBegin);
+        } else {
+            // The space at mBuffer[...] is uninitialised.
+            // TODO: Use std::construct_at when it becomes available.
+            new (std::addressof(mBuffer[bufferIndex(mSize)]))
+                    value_type(std::forward<value_type>(element));
+            ++mSize;
+        }
+    }
+
+    bool empty() const { return mSize == 0; }
+    size_type capacity() const { return mCapacity; }
+    size_type size() const { return mSize; }
+
+    void swap(RingBuffer& other) noexcept {
+        using std::swap;
+        swap(mBuffer, other.mBuffer);
+        swap(mCapacity, other.mCapacity);
+        swap(mBegin, other.mBegin);
+        swap(mSize, other.mSize);
+    }
+
+    friend void swap(RingBuffer& lhs, RingBuffer& rhs) noexcept { lhs.swap(rhs); }
+
+    template <typename U>
+    class Iterator {
+    private:
+        using ContainerType = std::conditional_t<std::is_const_v<U>, const RingBuffer, RingBuffer>;
+
+    public:
+        using iterator_category = std::random_access_iterator_tag;
+        using size_type = ContainerType::size_type;
+        using difference_type = ContainerType::difference_type;
+        using value_type = std::remove_cv_t<U>;
+        using pointer = U*;
+        using reference = U&;
+
+        Iterator(ContainerType& container, size_type index)
+              : mContainer(container), mIndex(index) {}
+
+        Iterator(const Iterator&) = default;
+        Iterator& operator=(const Iterator&) = default;
+
+        Iterator& operator++() {
+            ++mIndex;
+            return *this;
+        }
+
+        Iterator operator++(int) {
+            Iterator iterator(*this);
+            ++(*this);
+            return iterator;
+        }
+
+        Iterator& operator--() {
+            --mIndex;
+            return *this;
+        }
+
+        Iterator operator--(int) {
+            Iterator iterator(*this);
+            --(*this);
+            return iterator;
+        }
+
+        Iterator& operator+=(difference_type n) {
+            mIndex += n;
+            return *this;
+        }
+
+        Iterator operator+(difference_type n) {
+            Iterator iterator(*this);
+            return iterator += n;
+        }
+
+        Iterator& operator-=(difference_type n) { return *this += -n; }
+
+        Iterator operator-(difference_type n) {
+            Iterator iterator(*this);
+            return iterator -= n;
+        }
+
+        difference_type operator-(const Iterator& other) { return mIndex - other.mIndex; }
+
+        bool operator==(const Iterator& rhs) const { return mIndex == rhs.mIndex; }
+
+        bool operator!=(const Iterator& rhs) const { return !(*this == rhs); }
+
+        friend auto operator<=>(const Iterator& lhs, const Iterator& rhs) {
+            return lhs.mIndex <=> rhs.mIndex;
+        }
+
+        reference operator[](difference_type n) { return *(*this + n); }
+
+        reference operator*() const { return mContainer[mIndex]; }
+        pointer operator->() const { return std::addressof(mContainer[mIndex]); }
+
+    private:
+        ContainerType& mContainer;
+        size_type mIndex = 0;
+    };
+
+private:
+    // Returns the index of the next element in mBuffer.
+    size_type next(size_type index) const {
+        if (index == capacity() - 1) {
+            return 0;
+        } else {
+            return index + 1;
+        }
+    }
+
+    // Returns the index of the previous element in mBuffer.
+    size_type previous(size_type index) const {
+        if (index == 0) {
+            return capacity() - 1;
+        } else {
+            return index - 1;
+        }
+    }
+
+    // Converts the index of an element in [0, size()] to its corresponding index in mBuffer.
+    size_type bufferIndex(size_type elementIndex) const {
+        CHECK_LE(elementIndex, size());
+        size_type index = mBegin + elementIndex;
+        if (index >= capacity()) {
+            index -= capacity();
+        }
+        CHECK_LT(index, capacity())
+                << android::base::StringPrintf("Invalid index calculated for element (%zu) "
+                                               "in buffer of size %zu",
+                                               elementIndex, size());
+        return index;
+    }
+
+    pointer mBuffer = nullptr;
+    size_type mCapacity = 0; // Total capacity of mBuffer.
+    size_type mBegin = 0;    // Index of the first initialised element in mBuffer.
+    size_type mSize = 0;     // Total number of initialised elements.
+};
+
+} // namespace android
diff --git a/include/input/TfLiteMotionPredictor.h b/include/input/TfLiteMotionPredictor.h
index ff0f51c..704349c 100644
--- a/include/input/TfLiteMotionPredictor.h
+++ b/include/input/TfLiteMotionPredictor.h
@@ -23,7 +23,8 @@
 #include <optional>
 #include <span>
 #include <string>
-#include <vector>
+
+#include <input/RingBuffer.h>
 
 #include <tensorflow/lite/core/api/error_reporter.h>
 #include <tensorflow/lite/interpreter.h>
@@ -83,11 +84,11 @@
 private:
     int64_t mTimestamp = 0;
 
-    std::vector<float> mInputR;
-    std::vector<float> mInputPhi;
-    std::vector<float> mInputPressure;
-    std::vector<float> mInputTilt;
-    std::vector<float> mInputOrientation;
+    RingBuffer<float> mInputR;
+    RingBuffer<float> mInputPhi;
+    RingBuffer<float> mInputPressure;
+    RingBuffer<float> mInputTilt;
+    RingBuffer<float> mInputOrientation;
 
     // The samples defining the current polar axis.
     std::optional<TfLiteMotionPredictorSample> mAxisFrom;
diff --git a/libs/input/TfLiteMotionPredictor.cpp b/libs/input/TfLiteMotionPredictor.cpp
index 1a337ad..40653d3 100644
--- a/libs/input/TfLiteMotionPredictor.cpp
+++ b/libs/input/TfLiteMotionPredictor.cpp
@@ -104,13 +104,13 @@
 
 } // namespace
 
-TfLiteMotionPredictorBuffers::TfLiteMotionPredictorBuffers(size_t inputLength) {
+TfLiteMotionPredictorBuffers::TfLiteMotionPredictorBuffers(size_t inputLength)
+      : mInputR(inputLength, 0),
+        mInputPhi(inputLength, 0),
+        mInputPressure(inputLength, 0),
+        mInputTilt(inputLength, 0),
+        mInputOrientation(inputLength, 0) {
     LOG_ALWAYS_FATAL_IF(inputLength == 0, "Buffer input size must be greater than 0");
-    mInputR.resize(inputLength);
-    mInputPhi.resize(inputLength);
-    mInputPressure.resize(inputLength);
-    mInputTilt.resize(inputLength);
-    mInputOrientation.resize(inputLength);
 }
 
 void TfLiteMotionPredictorBuffers::reset() {
@@ -186,17 +186,11 @@
     mAxisTo = sample;
 
     // Push the current sample onto the end of the input buffers.
-    mInputR.erase(mInputR.begin());
-    mInputPhi.erase(mInputPhi.begin());
-    mInputPressure.erase(mInputPressure.begin());
-    mInputTilt.erase(mInputTilt.begin());
-    mInputOrientation.erase(mInputOrientation.begin());
-
-    mInputR.push_back(r);
-    mInputPhi.push_back(phi);
-    mInputPressure.push_back(sample.pressure);
-    mInputTilt.push_back(sample.tilt);
-    mInputOrientation.push_back(orientation);
+    mInputR.pushBack(r);
+    mInputPhi.pushBack(phi);
+    mInputPressure.pushBack(sample.pressure);
+    mInputTilt.pushBack(sample.tilt);
+    mInputOrientation.pushBack(orientation);
 }
 
 std::unique_ptr<TfLiteMotionPredictorModel> TfLiteMotionPredictorModel::create(
diff --git a/libs/input/tests/Android.bp b/libs/input/tests/Android.bp
index 916a8f2..f07164c 100644
--- a/libs/input/tests/Android.bp
+++ b/libs/input/tests/Android.bp
@@ -19,6 +19,7 @@
         "InputEvent_test.cpp",
         "InputPublisherAndConsumer_test.cpp",
         "MotionPredictor_test.cpp",
+        "RingBuffer_test.cpp",
         "TfLiteMotionPredictor_test.cpp",
         "TouchResampling_test.cpp",
         "TouchVideoFrame_test.cpp",
diff --git a/libs/input/tests/RingBuffer_test.cpp b/libs/input/tests/RingBuffer_test.cpp
new file mode 100644
index 0000000..8a6ef4c
--- /dev/null
+++ b/libs/input/tests/RingBuffer_test.cpp
@@ -0,0 +1,208 @@
+/*
+ * Copyright (C) 2023 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include <algorithm>
+#include <iterator>
+#include <memory>
+#include <vector>
+
+#include <gmock/gmock.h>
+#include <gtest/gtest.h>
+#include <input/RingBuffer.h>
+
+namespace android {
+namespace {
+
+using ::testing::ElementsAre;
+using ::testing::ElementsAreArray;
+using ::testing::IsEmpty;
+using ::testing::Not;
+using ::testing::SizeIs;
+
+TEST(RingBufferTest, PushPop) {
+    RingBuffer<int> buffer(/*capacity=*/3);
+
+    buffer.pushBack(1);
+    buffer.pushBack(2);
+    buffer.pushBack(3);
+    EXPECT_THAT(buffer, ElementsAre(1, 2, 3));
+
+    buffer.pushBack(4);
+    EXPECT_THAT(buffer, ElementsAre(2, 3, 4));
+
+    buffer.pushFront(1);
+    EXPECT_THAT(buffer, ElementsAre(1, 2, 3));
+
+    EXPECT_EQ(1, buffer.popFront());
+    EXPECT_THAT(buffer, ElementsAre(2, 3));
+
+    buffer.pushBack(4);
+    EXPECT_THAT(buffer, ElementsAre(2, 3, 4));
+
+    buffer.pushBack(5);
+    EXPECT_THAT(buffer, ElementsAre(3, 4, 5));
+
+    EXPECT_EQ(5, buffer.popBack());
+    EXPECT_THAT(buffer, ElementsAre(3, 4));
+
+    EXPECT_EQ(4, buffer.popBack());
+    EXPECT_THAT(buffer, ElementsAre(3));
+
+    EXPECT_EQ(3, buffer.popBack());
+    EXPECT_THAT(buffer, ElementsAre());
+
+    buffer.pushBack(1);
+    EXPECT_THAT(buffer, ElementsAre(1));
+
+    EXPECT_EQ(1, buffer.popFront());
+    EXPECT_THAT(buffer, ElementsAre());
+}
+
+TEST(RingBufferTest, ObjectType) {
+    RingBuffer<std::unique_ptr<int>> buffer(/*capacity=*/2);
+    buffer.pushBack(std::make_unique<int>(1));
+    buffer.pushBack(std::make_unique<int>(2));
+    buffer.pushBack(std::make_unique<int>(3));
+
+    EXPECT_EQ(2, *buffer[0]);
+    EXPECT_EQ(3, *buffer[1]);
+}
+
+TEST(RingBufferTest, ConstructConstantValue) {
+    RingBuffer<int> buffer(/*count=*/3, /*value=*/10);
+    EXPECT_THAT(buffer, ElementsAre(10, 10, 10));
+    EXPECT_EQ(3u, buffer.capacity());
+}
+
+TEST(RingBufferTest, Assignment) {
+    RingBuffer<int> a(/*capacity=*/2);
+    a.pushBack(1);
+    a.pushBack(2);
+
+    RingBuffer<int> b(/*capacity=*/3);
+    b.pushBack(10);
+    b.pushBack(20);
+    b.pushBack(30);
+
+    std::swap(a, b);
+    EXPECT_THAT(a, ElementsAre(10, 20, 30));
+    EXPECT_THAT(b, ElementsAre(1, 2));
+
+    a = b;
+    EXPECT_THAT(a, ElementsAreArray(b));
+
+    RingBuffer<int> c(b);
+    EXPECT_THAT(c, ElementsAreArray(b));
+
+    RingBuffer<int> d(std::move(b));
+    EXPECT_EQ(0u, b.capacity());
+    EXPECT_THAT(b, ElementsAre());
+    EXPECT_THAT(d, ElementsAre(1, 2));
+
+    b = std::move(d);
+    EXPECT_THAT(b, ElementsAre(1, 2));
+    EXPECT_THAT(d, ElementsAre());
+    EXPECT_EQ(0u, d.capacity());
+}
+
+TEST(RingBufferTest, Subscripting) {
+    RingBuffer<int> buffer(/*capacity=*/2);
+    buffer.pushBack(1);
+    EXPECT_EQ(1, buffer[0]);
+
+    buffer.pushFront(0);
+    EXPECT_EQ(0, buffer[0]);
+    EXPECT_EQ(1, buffer[1]);
+
+    buffer.pushFront(-1);
+    EXPECT_EQ(-1, buffer[0]);
+    EXPECT_EQ(0, buffer[1]);
+}
+
+TEST(RingBufferTest, Iterator) {
+    RingBuffer<int> buffer(/*capacity=*/3);
+    buffer.pushFront(2);
+    buffer.pushBack(3);
+
+    auto begin = buffer.begin();
+    auto end = buffer.end();
+
+    EXPECT_NE(begin, end);
+    EXPECT_LE(begin, end);
+    EXPECT_GT(end, begin);
+    EXPECT_EQ(end, begin + 2);
+    EXPECT_EQ(begin, end - 2);
+
+    EXPECT_EQ(2, end - begin);
+    EXPECT_EQ(1, end - (begin + 1));
+
+    EXPECT_EQ(2, *begin);
+    ++begin;
+    EXPECT_EQ(3, *begin);
+    --begin;
+    EXPECT_EQ(2, *begin);
+    begin += 1;
+    EXPECT_EQ(3, *begin);
+    begin += -1;
+    EXPECT_EQ(2, *begin);
+    begin -= -1;
+    EXPECT_EQ(3, *begin);
+}
+
+TEST(RingBufferTest, Clear) {
+    RingBuffer<int> buffer(/*capacity=*/2);
+    EXPECT_THAT(buffer, ElementsAre());
+
+    buffer.pushBack(1);
+    EXPECT_THAT(buffer, ElementsAre(1));
+
+    buffer.clear();
+    EXPECT_THAT(buffer, ElementsAre());
+    EXPECT_THAT(buffer, SizeIs(0));
+    EXPECT_THAT(buffer, IsEmpty());
+
+    buffer.pushFront(1);
+    EXPECT_THAT(buffer, ElementsAre(1));
+}
+
+TEST(RingBufferTest, SizeAndIsEmpty) {
+    RingBuffer<int> buffer(/*capacity=*/2);
+    EXPECT_THAT(buffer, SizeIs(0));
+    EXPECT_THAT(buffer, IsEmpty());
+
+    buffer.pushBack(1);
+    EXPECT_THAT(buffer, SizeIs(1));
+    EXPECT_THAT(buffer, Not(IsEmpty()));
+
+    buffer.pushBack(2);
+    EXPECT_THAT(buffer, SizeIs(2));
+    EXPECT_THAT(buffer, Not(IsEmpty()));
+
+    buffer.pushBack(3);
+    EXPECT_THAT(buffer, SizeIs(2));
+    EXPECT_THAT(buffer, Not(IsEmpty()));
+
+    buffer.popFront();
+    EXPECT_THAT(buffer, SizeIs(1));
+    EXPECT_THAT(buffer, Not(IsEmpty()));
+
+    buffer.popBack();
+    EXPECT_THAT(buffer, SizeIs(0));
+    EXPECT_THAT(buffer, IsEmpty());
+}
+
+} // namespace
+} // namespace android