content: /*
   * Copyright (C) 2013 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.bitmap;
  
  import android.util.Log;
  import android.util.SparseArray;
  
  import com.android.bitmap.util.Trace;
  
  import java.util.ArrayDeque;
  import java.util.Iterator;
  import java.util.Queue;
  
  /**
   * An implementation of a task aggregator that executes tasks in the order that they are expected
   * . All tasks that is given to {@link #execute(Object, Runnable)} must correspond to a key. This
   * key must have been previously declared with {@link #expect(Object, Callback)}.
   * The task will be scheduled to run when its corresponding key becomes the first expected key
   * amongst the other keys in this aggregator.
   * <p/>
   * If on {@link #execute(Object, Runnable)} the key is not expected, the task will be executed
   * immediately as an edge case.
   * <p/>
   * A characteristic scenario is as follows:
   * <ol>
   * <li>Expect keys <b>A</b>, <b>B</b>, <b>C</b>, and <b>Z</b>, in that order. Key <b>A</b> is now
   * the first expected key.</li>
   * <li>Execute task <b>2</b> for key <b>B</b>. The first expected key is <b>A</b>,
   * which has no task associated with it, so we store task <b>2</b>. </li>
   * <li>Execute task <b>4</b> for key <b>Z</b>. We store task <b>4</b>. </li>
   * <li>Execute task <b>1</b> for key <b>A</b>. We run task <b>1</b> because its key <b>A</b> is
   * the first expected, then we remove key <b>A</b> from the list of keys that we expect.</li>
   * <li>This causes key <b>B</b> to be the first expected key, and we see that we have previously
   * stored task <b>2</b> for that key. We run task <b>2</b> and remove key <b>B</b>. </li>
   * <li>Key <b>C</b> is now the first expected key, but it has no task,
   * so nothing happens. Task <b>4</b>, which was previously stored,
   * cannot run until its corresponding key <b>Z</b> becomes the first expected key. This can
   * happen if a task comes in for key <b>C</b> or if forget is called on key <b>C</b>.</li>
   * </ol>
   * <p/>
   * ContiguousFIFOAggregator is not thread safe.
   */
  public class ContiguousFIFOAggregator<T> {
      private final Queue<T> mExpected;
      private final SparseArray<Value> mTasks;
  
      private static final String TAG = ContiguousFIFOAggregator.class.getSimpleName();
      private static final boolean DEBUG = false;
  
      /**
       * Create a new ContiguousFIFOAggregator.
       * <p/>
       * The nature of the prioritization means that the number of stored keys and tasks may grow
       * unbounded. This may happen, for instance, if the top priority key is never given a task to
       * {@link #execute(Object, Runnable)}. However, in practice, if you are generating tasks in
       * response to UI elements appearing on the screen, you will only have a bounded set of keys.
       * UI elements that scroll off the screen will call {@link #forget(Object)} while new elements
       * will call {@link #expect(Object, Callback)}. This means that the expected
       * number of keys and tasks is
       * the maximum number of UI elements that you expect to show on the screen at any time.
       */
      public ContiguousFIFOAggregator() {
          mExpected = new ArrayDeque<T>();
          mTasks = new SparseArray<Value>();
      }
  
      /**
       * Declare a key to be expected in the future. The order in which you expect keys is very
       * important. Keys that are declared first are guaranteed to have their tasks run first. You
       * must call either {@link #forget(Object)} or {@link #execute(Object, Runnable)}
       * with this key in the future, or you will leak the key.
       *
       * If you call expect with a previously expected key, the key will be placed at the back of
       * the expected queue and its callback will be replaced with this one.
       *
       * @param key      the key to expect a task for. Use the same key when setting the task later
       *                 with {@link #execute (Object, Runnable)}.
       * @param callback the callback to notify when the key becomes the first expected key, or null.
       */
      public void expect(final T key, final Callback<T> callback) {
          if (key == null) {
              throw new IllegalArgumentException("Do not use null keys.");
          }
  
          Trace.beginSection("pool expect");
          final int hash = key.hashCode();
          if (contains(key)) {
              mExpected.remove(key);
              mTasks.remove(hash);
          }
          final boolean isFirst = mExpected.isEmpty();
          mExpected.offer(key);
          mTasks.put(hash, new Value(callback, null));
          if (DEBUG) {
              Log.d(TAG, String.format("ContiguousFIFOAggregator >> tasks: %s", prettyPrint()));
          }
  
          if (isFirst) {
              onFirstExpectedChanged(key);
          }
          Trace.endSection();
      }
  
      /**
       * Remove a previously declared key that we no longer expect to execute a task for. This
       * potentially allows another key to now become the first expected key,
       * and so this may trigger one or more tasks to be executed.
       *
       * @param key the key previously declared in {@link #expect(Object, Callback)}.
       *
       */
      public void forget(final T key) {
          if (key == null) {
              throw new IllegalArgumentException("Do not use null keys.");
          }
  
          if (!contains(key)) {
              return;
          }
  
          Trace.beginSection("pool forget");
          final boolean removedFirst = key.equals(mExpected.peek());
          mExpected.remove(key);
          mTasks.delete(key.hashCode());
          if (DEBUG) {
              Log.d(TAG, String.format("ContiguousFIFOAggregator  < tasks: %s", prettyPrint()));
          }
  
          final T second;
          if (removedFirst && (second = mExpected.peek()) != null) {
              // We removed the first key. The second key is now first.
              onFirstExpectedChanged(second);
          }
  
          maybeExecuteNow();
          Trace.endSection();
      }
  
      /**
       * Attempt to execute a task corresponding to a previously declared key. If the key is the
       * first expected key, the task will be executed immediately. Otherwise, the task is stored
       * until its key becomes the first expected key. Execution of a task results in the removal
       * of that key, which potentially allows another key to now become the first expected key,
       * and may cause one or more other tasks to be executed.
       * <p/>
       * If the key is not expected, the task will be executed immediately as an edge case.
       *
       * @param key  the key previously declared in {@link #expect(Object, Callback)}.
       * @param task the task to execute or store, depending on its corresponding key.
       */
      public void execute(final T key, final Runnable task) {
          Trace.beginSection("pool execute");
          final int hash = key.hashCode();
          final Value value = mTasks.get(hash);
          if (value == null || task == null) {
              if (task != null) {
                  task.run();
              }
              Trace.endSection();
              return;
          }
          value.task = task;
          if (DEBUG) {
              Log.d(TAG, String.format("ContiguousFIFOAggregator ++ tasks: %s", prettyPrint()));
          }
          maybeExecuteNow();
          Trace.endSection();
      }
  
      /**
       * Triggered by {@link #execute(Object, Runnable)} and {@link #forget(Object)}. The keys or
       * tasks have changed, which may cause one or more tasks to be executed. This method will
       * continue to execute tasks associated with the first expected key to the last expected key,
       * stopping when it finds that the first expected key has not yet been assigned a task.
       */
      private void maybeExecuteNow() {
          T first;
          int count = 0;
          while (!mExpected.isEmpty()) {
              Trace.beginSection("pool maybeExecuteNow loop");
              first = mExpected.peek();
              if (count > 0) {
                  // When count == 0, the key is already first.
                  onFirstExpectedChanged(first);
              }
  
              final int hash = first.hashCode();
              final Value value = mTasks.get(hash);
              if (value.task == null) {
                  Trace.endSection();
                  break;
              }
  
              mExpected.poll();
              mTasks.delete(hash);
              if (DEBUG) {
                  Log.d(TAG, String.format("ContiguousFIFOAggregator  - tasks: %s", prettyPrint()));
              }
              value.task.run();
              count++;
              Trace.endSection();
          }
      }
  
      /**
       * This method should only be called once for any key.
       * @param key The key that has become the new first expected key.
       */
      private void onFirstExpectedChanged(final T key) {
          final int hash = key.hashCode();
          final Value value = mTasks.get(hash);
          if (value == null) {
              return;
          }
          final Callback<T> callback = value.callback;
          if (callback == null) {
              return;
          }
          if (DEBUG) {
              Log.d(TAG, String.format("ContiguousFIFOAggregator    first: %d", hash));
          }
          callback.onBecomeFirstExpected(key);
      }
  
      private boolean contains(final T key) {
          return mTasks.get(key.hashCode()) != null;
      }
  
      /**
       * Get a pretty string representing the internal data.
       * @return  a String for the internal data.
       */
      private String prettyPrint() {
          if (mExpected.isEmpty()) {
              return "{}";
          }
  
          StringBuilder buffer = new StringBuilder(mExpected.size() * 28);
          buffer.append('{');
          Iterator<T> it = mExpected.iterator();
          while (it.hasNext()) {
              final T key = it.next();
              final int hash = key.hashCode();
              buffer.append(hash);
              buffer.append('=');
              final Value value = mTasks.get(hash);
              buffer.append(value);
              if (it.hasNext()) {
                  buffer.append(", ");
              }
          }
          buffer.append('}');
          if (mExpected.size() != mTasks.size()) {
              buffer.append(" error");
          }
          return buffer.toString();
      }
  
      /**
       * Implement this interface if you want to be notified when the key becomes the first
       * expected key.
       * @param <T> The type of the key used for the aggregator.
       */
      public interface Callback<T> {
  
          /**
           * The key you declared as expected has become the first expected key in this aggregator.
           *
           * We don't need a noLongerFirstExpected() method because this aggregator strictly adds
           * additional to the end of the queue. For a first expected key to no longer be the first
           * expected, it would either have to be forgotten with {@link #forget(Object)} or a task
           * assigned and executed with {@link #execute(Object, Runnable)}.
           *
           * @param key The key that became first. We provide the key so the callback can either not
           *            keep state, or it can keep state which may have changed so the callback can do
           *            a comparison.
           */
          void onBecomeFirstExpected(final T key);
      }
  
      /**
       * Holds the callback and task for when a key later becomes the first expected key.
       */
      private class Value {
  
          final Callback<T> callback;
          Runnable task;
  
          Value(final Callback<T> callback, final Runnable task) {
              this.callback = callback;
              this.task = task;
          }
  
          @Override
          public String toString() {
              return String.valueOf(task);
          }
      }
  }
  