content: /*
   * Copyright (C) 2019 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.
   */
  
  package com.android.server.display.utils;
  
  /**
   * A buffer that supports adding new values and truncating old ones.
   */
  public class RollingBuffer {
  
      private static final int INITIAL_SIZE = 50;
  
      private int mSize;
      private int mCount;
      private int mStart;
      private int mEnd;
  
      private long[] mTimes; // Milliseconds
      private float[] mValues;
  
      public RollingBuffer() {
          mSize = INITIAL_SIZE;
          mTimes = new long[INITIAL_SIZE];
          mValues = new float[INITIAL_SIZE];
          clear();
      }
  
      /**
       * Add a value at a given time.
       *
       * @param time
       *      The time (in milliseconds).
       * @param value
       *      The value.
       */
      public void add(long time, float value) {
          if (mCount >= mSize) {
              expandBuffer();
          }
          mTimes[mEnd] = time;
          mValues[mEnd] = value;
          mEnd = (mEnd + 1) % mSize;
          mCount++;
      }
  
      /**
       * Get the size of the buffer.
       *
       * @return The size of the buffer.
       */
      public int size() {
          return mCount;
      }
  
      /**
       * Return whether the buffer is empty or not.
       *
       * @return Whether the buffer is empty or not.
       */
      public boolean isEmpty() {
          return size() == 0;
      }
  
      /**
       * Get a time.
       *
       * @param index
       *      The index of the time.
       *
       * @return The time.
       */
      public long getTime(int index) {
          return mTimes[offsetOf(index)];
      }
  
      /**
       * Get a value.
       *
       * @param index
       *      The index of the value.
       *
       * @return The value.
       */
      public float getValue(int index) {
          return mValues[offsetOf(index)];
      }
  
      /**
       * Truncate old values.
       *
       * @param minTime
       *      The minimum time (all values older than this time are truncated).
       */
      public void truncate(long minTime) {
          if (isEmpty() || getTime(0) >= minTime) {
              return;
          }
          final int index = getLatestIndexBefore(minTime);
          mStart = offsetOf(index);
          mCount -= index;
          // Remove everything that happened before mTimes[index], but set the index-th value time to
          // minTime rather than dropping it, as that would've been the value between the minTime and
          // mTimes[index+1].
          //
          // -*---*---|---*---*- => xxxxxxxxx|*--*---*- rather than xxxxxxxxx|???*---*-
          //      ^       ^                   ^  ^                               ^
          //      i      i+1                  i i+1                             i+1
          mTimes[mStart] = minTime;
      }
  
      /**
       * Clears the buffer.
       */
      public void clear() {
          mCount = 0;
          mStart = 0;
          mEnd = 0;
      }
  
      /**
       * Convert the buffer to string.
       *
       * @return The buffer as string.
       */
      public String toString() {
          StringBuffer sb = new StringBuffer();
          sb.append("[");
          for (int i = 0; i < mCount; i++) {
              final int index = offsetOf(i);
              sb.append(mValues[index] + " @ " + mTimes[index]);
              if (i + 1 != mCount) {
                  sb.append(", ");
              }
          }
          sb.append("]");
          return sb.toString();
      }
  
      private int offsetOf(int index) {
          if (index < 0 || index >= mCount) {
              throw new ArrayIndexOutOfBoundsException("invalid index: " + index + ", mCount= "
                      + mCount);
          }
          return (mStart + index) % mSize;
      }
  
      private void expandBuffer() {
          final int size = mSize * 2;
          long[] times = new long[size];
          float[] values = new float[size];
          System.arraycopy(mTimes, mStart, times, 0, mCount - mStart);
          System.arraycopy(mTimes, 0, times, mCount - mStart, mStart);
          System.arraycopy(mValues, mStart, values, 0, mCount - mStart);
          System.arraycopy(mValues, 0, values, mCount - mStart, mStart);
          mSize = size;
          mStart = 0;
          mEnd = mCount;
          mTimes = times;
          mValues = values;
      }
  
      private int getLatestIndexBefore(long time) {
          for (int i = 1; i < mCount; i++) {
              if (mTimes[offsetOf(i)] > time) {
                  return i - 1;
              }
          }
          return mCount - 1;
      }
  
  }
  