src/com/android/car/rotary/RotaryCache.java - platform/packages/apps/Car/RotaryController - Git at Google

 /*
  * Copyright (C) 2020 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.car.rotary;

 import android.os.SystemClock;
 import android.util.LruCache;
 import android.view.View;
 import android.view.accessibility.AccessibilityNodeInfo;

 import androidx.annotation.IntDef;
 import androidx.annotation.NonNull;
 import androidx.annotation.Nullable;
 import androidx.annotation.VisibleForTesting;

 import java.lang.annotation.Retention;
 import java.lang.annotation.RetentionPolicy;
 import java.util.ArrayList;
 import java.util.Collections;
 import java.util.List;
 import java.util.Map;
 import java.util.Objects;

 /**
  * Cache of rotation and nudge history of rotary controller. With this cache, the users can reverse
  * course and go back where they were if they accidentally nudge too far.
  */
 class RotaryCache {

     /** The cache is disabled. */
     @VisibleForTesting
     static final int CACHE_TYPE_DISABLED = 1;
     /** Entries in the cache will expire after a period of time. */
     @VisibleForTesting
     static final int CACHE_TYPE_EXPIRED_AFTER_SOME_TIME = 2;
     /** Entries in the cache will never expire as long as RotaryService is alive. */
     @VisibleForTesting
     static final int CACHE_TYPE_NEVER_EXPIRE = 3;

     @IntDef(flag = true, value = {
             CACHE_TYPE_DISABLED, CACHE_TYPE_EXPIRED_AFTER_SOME_TIME, CACHE_TYPE_NEVER_EXPIRE})
     @Retention(RetentionPolicy.SOURCE)
     public @interface CacheType {
     }

     @NonNull
     private NodeCopier mNodeCopier = new NodeCopier();

     /** Cache of last focused node by focus area. */
     @NonNull
     private final FocusHistoryCache mFocusHistoryCache;

     /** Cache of target focus area by source focus area and direction (up, down, left or right). */
     @NonNull
     private final FocusAreaHistoryCache mFocusAreaHistoryCache;

     /**
      * Cache of recently focused nodes in recently focused windows. Used to recover when the
      * focused window closes.
      */
     @NonNull
     private final FocusWindowCache mFocusWindowCache;

     /** A record of when a node was focused. */
     private static class FocusHistory {

         /**
          * A node representing a focusable {@link View} or a {@link com.android.car.ui.FocusArea}.
          */
         @NonNull
         final AccessibilityNodeInfo node;

         /** The {@link SystemClock#uptimeMillis} when this history was recorded. */
         final long timestamp;

         FocusHistory(@NonNull AccessibilityNodeInfo node, long timestamp) {
             this.node = node;
             this.timestamp = timestamp;
         }
     }

     /**
      * A combination of a source focus area and a direction (up, down, left or right). Used as a key
      * in {@link #mFocusAreaHistoryCache}.
      */
     private static class FocusAreaHistory {

         @NonNull
         final AccessibilityNodeInfo sourceFocusArea;
         final int direction;

         FocusAreaHistory(@NonNull AccessibilityNodeInfo sourceFocusArea, int direction) {
             this.sourceFocusArea = sourceFocusArea;
             this.direction = direction;
         }

         @Override
         public boolean equals(Object o) {
             if (this == o) {
                 return true;
             }
             if (o == null || getClass() != o.getClass()) {
                 return false;
             }
             FocusAreaHistory that = (FocusAreaHistory) o;
             return direction == that.direction
                     && Objects.equals(sourceFocusArea, that.sourceFocusArea);
         }

         @Override
         public int hashCode() {
             return Objects.hash(sourceFocusArea, direction);
         }
     }

     /** An entry in {@link #mFocusWindowCache}. */
     private static class FocusWindowHistory {
         /** A node in a window representing a focused {@link View}. */
         @NonNull
         final AccessibilityNodeInfo mNode;

         /** The {@link SystemClock#uptimeMillis} when this history was recorded. */
         final long mTimestamp;

         FocusWindowHistory(@NonNull AccessibilityNodeInfo node, long timestamp) {
             this.mNode = node;
             this.mTimestamp = timestamp;
         }

         void recycle() {
             this.mNode.recycle();
         }
     }

     /** A cache of the last focused node by focus area. */
     private class FocusHistoryCache extends LruCache<AccessibilityNodeInfo, FocusHistory> {

         /** Type of the cache. */
         private final @CacheType int mCacheType;

         /** How many milliseconds before an entry in the cache expires. */
         private final int mExpirationTimeMs;

         FocusHistoryCache(@CacheType int cacheType, int size, int expirationTimeMs) {
             super(size);
             mCacheType = cacheType;
             mExpirationTimeMs = expirationTimeMs;
             if (mCacheType == CACHE_TYPE_EXPIRED_AFTER_SOME_TIME && mExpirationTimeMs <= 0) {
                 throw new IllegalArgumentException(
                         "Expiration time must be positive if CacheType is "
                                 + "CACHE_TYPE_EXPIRED_AFTER_SOME_TIME");
             }
         }

         boolean enabled() {
             return mCacheType != CACHE_TYPE_DISABLED;
         }

         boolean isValidFocusHistory(@Nullable FocusHistory focusHistory, long elapsedRealtime) {
             if (focusHistory == null || focusHistory.node == null) {
                 return false;
             }
             switch (mCacheType) {
                 case CACHE_TYPE_NEVER_EXPIRE:
                     return true;
                 case CACHE_TYPE_EXPIRED_AFTER_SOME_TIME:
                     return elapsedRealtime - focusHistory.timestamp < mExpirationTimeMs;
                 default:
                     return false;
             }
         }

         @Override
         protected void entryRemoved(boolean evicted, AccessibilityNodeInfo key,
                 FocusHistory oldValue, FocusHistory newValue) {
             Utils.recycleNode(key);
             Utils.recycleNode(oldValue.node);
         }
     }

     /**
      * A cache of the target focus area to nudge to, by source focus area and direction (up, down,
      * left or right).
      */
     private class FocusAreaHistoryCache extends LruCache<FocusAreaHistory, FocusHistory> {

         /** Type of the cache. */
         private final @CacheType int mCacheType;

         /** How many milliseconds before an entry in the cache expires. */
         private final int mExpirationTimeMs;

         FocusAreaHistoryCache(@CacheType int cacheType, int size, int expirationTimeMs) {
             super(size);
             mCacheType = cacheType;
             mExpirationTimeMs = expirationTimeMs;
             if (mCacheType == CACHE_TYPE_EXPIRED_AFTER_SOME_TIME && mExpirationTimeMs <= 0) {
                 throw new IllegalArgumentException(
                         "Expiration time must be positive if CacheType is "
                                 + "CACHE_TYPE_EXPIRED_AFTER_SOME_TIME");
             }
         }

         boolean enabled() {
             return mCacheType != CACHE_TYPE_DISABLED;
         }

         boolean isValidFocusHistory(@Nullable FocusHistory focusHistory, long elapsedRealtime) {
             if (focusHistory == null || focusHistory.node == null) {
                 return false;
             }
             switch (mCacheType) {
                 case CACHE_TYPE_NEVER_EXPIRE:
                     return true;
                 case CACHE_TYPE_EXPIRED_AFTER_SOME_TIME:
                     return elapsedRealtime - focusHistory.timestamp < mExpirationTimeMs;
                 default:
                     return false;
             }
         }

         @Override
         protected void entryRemoved(boolean evicted, FocusAreaHistory key, FocusHistory oldValue,
                 FocusHistory newValue) {
             Utils.recycleNode(key.sourceFocusArea);
             Utils.recycleNode(oldValue.node);
         }
     }

     /**
      * A cache of recently focused nodes in recently focused windows. Used to recover when the
      * focused window closes.
      */
     private class FocusWindowCache extends LruCache<Integer, FocusWindowHistory> {
         @CacheType
         final int mCacheType;
         final int mExpirationTimeMs;

         FocusWindowCache(@CacheType int cacheType, int size, int expirationTimeMs) {
             super(size);
             mCacheType = cacheType;
             mExpirationTimeMs = expirationTimeMs;
             if (cacheType == CACHE_TYPE_EXPIRED_AFTER_SOME_TIME && expirationTimeMs <= 0) {
                 throw new IllegalArgumentException(
                         "Expiration time must be positive if CacheType is "
                                 + "CACHE_TYPE_EXPIRED_AFTER_SOME_TIME");
             }
         }

         /**
          * Returns whether an entry in this cache is valid. To be valid:
          * <ul>
          *     <li>the cached node must still be in the view tree
          *     <li>the cached node must still be able to take focus
          *     <li>the cache entry must not have expired
          * </ul>
          */
         boolean isValidEntry(@NonNull FocusWindowHistory focusWindowHistory, long elapsedRealtime) {
             if (!focusWindowHistory.mNode.refresh()
                     || !Utils.canTakeFocus(focusWindowHistory.mNode)) {
                 return false;
             }

             switch (mCacheType) {
                 case CACHE_TYPE_NEVER_EXPIRE:
                     return true;
                 case CACHE_TYPE_EXPIRED_AFTER_SOME_TIME:
                     return elapsedRealtime - focusWindowHistory.mTimestamp < mExpirationTimeMs;
                 default:
                     return false;
             }
         }

         /**
          * Stores the given (window ID, node) pair, overwriting the existing pair with the given
          * window ID, if any.
          */
         void put(int windowId, @NonNull AccessibilityNodeInfo node, long elapsedRealtime) {
             if (mCacheType == CACHE_TYPE_DISABLED) {
                 return;
             }
             put(windowId, new FocusWindowHistory(copyNode(node), elapsedRealtime));
         }

         /**
          * Returns the most recently focused valid node in window {@code windowId}, or {@code null}
          * if there are no valid nodes in the cache. The caller is responsible for recycling the
          * result.
          */
         @Nullable
         AccessibilityNodeInfo getMostRecentValidNode(int windowId, long elapsedRealtime) {
             FocusWindowHistory focusWindowHistory = get(windowId);
             if (focusWindowHistory != null && isValidEntry(focusWindowHistory, elapsedRealtime)) {
                 return copyNode(focusWindowHistory.mNode);
             }
             return null;
         }

         @Override
         protected void entryRemoved(boolean evicted, Integer windowId, FocusWindowHistory oldValue,
                 FocusWindowHistory newValue) {
             oldValue.recycle();
         }
     }

     RotaryCache(@CacheType int focusHistoryCacheType,
             int focusHistoryCacheSize,
             int focusHistoryExpirationTimeMs,
             @CacheType int focusAreaHistoryCacheType,
             int focusAreaHistoryCacheSize,
             int focusAreaHistoryExpirationTimeMs,
             @CacheType int focusWindowCacheType,
             int focusWindowCacheSize,
             int focusWindowExpirationTimeMs) {
         mFocusHistoryCache = new FocusHistoryCache(
                 focusHistoryCacheType, focusHistoryCacheSize, focusHistoryExpirationTimeMs);
         mFocusAreaHistoryCache = new FocusAreaHistoryCache(focusAreaHistoryCacheType,
                 focusAreaHistoryCacheSize, focusAreaHistoryExpirationTimeMs);
         mFocusWindowCache = new FocusWindowCache(focusWindowCacheType, focusWindowCacheSize,
                 focusWindowExpirationTimeMs);
     }

     /**
      * Searches the cache to find the last focused node in the given {@code focusArea}. Returns the
      * node, or null if there is nothing in the cache, the cache is stale, the view represented
      * by the node is no longer in the view tree, or the node's state has changed so that it can't
      * take focus any more. The caller is responsible for recycling the result.
      */
     AccessibilityNodeInfo getFocusedNode(@NonNull AccessibilityNodeInfo focusArea,
             long elapsedRealtime) {
         if (mFocusHistoryCache.enabled()) {
             FocusHistory focusHistory = mFocusHistoryCache.get(focusArea);
             if (mFocusHistoryCache.isValidFocusHistory(focusHistory, elapsedRealtime)) {
                 AccessibilityNodeInfo node = copyNode(focusHistory.node);
                 // Refresh the node in case the view represented by the node is no longer in the
                 // view tree, or the node's state (e.g., isFocused()) has changed.
                 AccessibilityNodeInfo refreshedNode = Utils.refreshNode(node);

                 // If the node's state has changed so that it can't take focus any more, return
                 // null.
                 if (refreshedNode != null && !Utils.canTakeFocus(refreshedNode)) {
                     Utils.recycleNode(refreshedNode);
                     refreshedNode = null;
                 }
                 return refreshedNode;
             }
         }
         return null;
     }

     /**
      * Caches the last focused node by focus area. A copy of {@code focusArea} and {@code
      * focusedNode} will be saved in the cache.
      */
     void saveFocusedNode(@NonNull AccessibilityNodeInfo focusArea,
             @NonNull AccessibilityNodeInfo focusedNode, long elapsedRealtime) {
         if (mFocusHistoryCache.enabled()) {
             mFocusHistoryCache.put(
                     copyNode(focusArea), new FocusHistory(copyNode(focusedNode), elapsedRealtime));
         }
     }

     /**
      * Searches the cache to find the target focus area for a nudge in a given {@code direction}
      * from a given focus area. Returns the focus area, or null if there is nothing in the cache,
      * the cache is stale, or the view represented by the node is no longer in the view tree.
      * The caller is responsible for recycling the result.
      */
     AccessibilityNodeInfo getTargetFocusArea(@NonNull AccessibilityNodeInfo sourceFocusArea,
             int direction, long elapsedRealtime) {
         if (mFocusAreaHistoryCache.enabled()) {
             FocusHistory focusHistory =
                     mFocusAreaHistoryCache.get(new FocusAreaHistory(sourceFocusArea, direction));
             if (mFocusAreaHistoryCache.isValidFocusHistory(focusHistory, elapsedRealtime)) {
                 AccessibilityNodeInfo focusArea = copyNode(focusHistory.node);
                 // Refresh the node in case the view represented by the node is no longer in the
                 // view tree.
                 return Utils.refreshNode(focusArea);
             }
         }
         return null;
     }

     /**
      * Caches the focus area nudge history. A copy of {@code sourceFocusArea} and {@code
      * targetFocusArea} will be saved in the cache.
      */
     void saveTargetFocusArea(@NonNull AccessibilityNodeInfo sourceFocusArea,
             @NonNull AccessibilityNodeInfo targetFocusArea, int direction, long elapsedRealtime) {
         if (mFocusAreaHistoryCache.enabled()) {
             int oppositeDirection = getOppositeDirection(direction);
             mFocusAreaHistoryCache
                     .put(new FocusAreaHistory(copyNode(targetFocusArea), oppositeDirection),
                             new FocusHistory(copyNode(sourceFocusArea), elapsedRealtime));
         }
     }

     /** Clears the focus area nudge history cache. */
     void clearFocusAreaHistory() {
         if (mFocusAreaHistoryCache.enabled()) {
             mFocusAreaHistoryCache.evictAll();
         }
     }

     @VisibleForTesting
     boolean isFocusAreaHistoryCacheEmpty() {
         return mFocusAreaHistoryCache.size() == 0;
     }

     /** Saves the most recently focused node within a window. */
     void saveWindowFocus(@NonNull AccessibilityNodeInfo focusedNode, long elapsedRealtime) {
         mFocusWindowCache.put(focusedNode.getWindowId(), focusedNode, elapsedRealtime);
     }

     /**
      * Returns the most recently focused valid node in window {@code windowId}, or {@code null} if
      * there are no valid nodes saved by {@link #saveWindowFocus}. The caller is responsible for
      * recycling the result.
      */
     @Nullable
     AccessibilityNodeInfo getMostRecentFocus(int windowId, long elapsedRealtime) {
         return mFocusWindowCache.getMostRecentValidNode(windowId, elapsedRealtime);
     }

     /** Returns the direction opposite the given {@code direction} */
     @VisibleForTesting
     static int getOppositeDirection(int direction) {
         switch (direction) {
             case View.FOCUS_LEFT:
                 return View.FOCUS_RIGHT;
             case View.FOCUS_RIGHT:
                 return View.FOCUS_LEFT;
             case View.FOCUS_UP:
                 return View.FOCUS_DOWN;
             case View.FOCUS_DOWN:
                 return View.FOCUS_UP;
         }
         throw new IllegalArgumentException("direction must be "
                 + "FOCUS_UP, FOCUS_DOWN, FOCUS_LEFT, or FOCUS_RIGHT.");
     }

     /** Sets a mock {@link NodeCopier} instance for testing. */
     @VisibleForTesting
     void setNodeCopier(@NonNull NodeCopier nodeCopier) {
         mNodeCopier = nodeCopier;
     }

     private AccessibilityNodeInfo copyNode(@Nullable AccessibilityNodeInfo node) {
         return mNodeCopier.copy(node);
     }
 }
	/*
	* Copyright (C) 2020 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.car.rotary;

	import android.os.SystemClock;
	import android.util.LruCache;
	import android.view.View;
	import android.view.accessibility.AccessibilityNodeInfo;

	import androidx.annotation.IntDef;
	import androidx.annotation.NonNull;
	import androidx.annotation.Nullable;
	import androidx.annotation.VisibleForTesting;

	import java.lang.annotation.Retention;
	import java.lang.annotation.RetentionPolicy;
	import java.util.ArrayList;
	import java.util.Collections;
	import java.util.List;
	import java.util.Map;
	import java.util.Objects;

	/**
	* Cache of rotation and nudge history of rotary controller. With this cache, the users can reverse
	* course and go back where they were if they accidentally nudge too far.
	*/
	class RotaryCache {

	/** The cache is disabled. */
	@VisibleForTesting
	static final int CACHE_TYPE_DISABLED = 1;
	/** Entries in the cache will expire after a period of time. */
	@VisibleForTesting
	static final int CACHE_TYPE_EXPIRED_AFTER_SOME_TIME = 2;
	/** Entries in the cache will never expire as long as RotaryService is alive. */
	@VisibleForTesting
	static final int CACHE_TYPE_NEVER_EXPIRE = 3;

	@IntDef(flag = true, value = {
	CACHE_TYPE_DISABLED, CACHE_TYPE_EXPIRED_AFTER_SOME_TIME, CACHE_TYPE_NEVER_EXPIRE})
	@Retention(RetentionPolicy.SOURCE)
	public @interface CacheType {
	}

	@NonNull
	private NodeCopier mNodeCopier = new NodeCopier();

	/** Cache of last focused node by focus area. */
	@NonNull
	private final FocusHistoryCache mFocusHistoryCache;

	/** Cache of target focus area by source focus area and direction (up, down, left or right). */
	@NonNull
	private final FocusAreaHistoryCache mFocusAreaHistoryCache;

	/**
	* Cache of recently focused nodes in recently focused windows. Used to recover when the
	* focused window closes.
	*/
	@NonNull
	private final FocusWindowCache mFocusWindowCache;

	/** A record of when a node was focused. */
	private static class FocusHistory {

	/**
	* A node representing a focusable {@link View} or a {@link com.android.car.ui.FocusArea}.
	*/
	@NonNull
	final AccessibilityNodeInfo node;

	/** The {@link SystemClock#uptimeMillis} when this history was recorded. */
	final long timestamp;

	FocusHistory(@NonNull AccessibilityNodeInfo node, long timestamp) {
	this.node = node;
	this.timestamp = timestamp;
	}
	}

	/**
	* A combination of a source focus area and a direction (up, down, left or right). Used as a key
	* in {@link #mFocusAreaHistoryCache}.
	*/
	private static class FocusAreaHistory {

	@NonNull
	final AccessibilityNodeInfo sourceFocusArea;
	final int direction;

	FocusAreaHistory(@NonNull AccessibilityNodeInfo sourceFocusArea, int direction) {
	this.sourceFocusArea = sourceFocusArea;
	this.direction = direction;
	}

	@Override
	public boolean equals(Object o) {
	if (this == o) {
	return true;
	}
	if (o == null \|\| getClass() != o.getClass()) {
	return false;
	}
	FocusAreaHistory that = (FocusAreaHistory) o;
	return direction == that.direction
	&& Objects.equals(sourceFocusArea, that.sourceFocusArea);
	}

	@Override
	public int hashCode() {
	return Objects.hash(sourceFocusArea, direction);
	}
	}

	/** An entry in {@link #mFocusWindowCache}. */
	private static class FocusWindowHistory {
	/** A node in a window representing a focused {@link View}. */
	@NonNull
	final AccessibilityNodeInfo mNode;

	/** The {@link SystemClock#uptimeMillis} when this history was recorded. */
	final long mTimestamp;

	FocusWindowHistory(@NonNull AccessibilityNodeInfo node, long timestamp) {
	this.mNode = node;
	this.mTimestamp = timestamp;
	}

	void recycle() {
	this.mNode.recycle();
	}
	}

	/** A cache of the last focused node by focus area. */
	private class FocusHistoryCache extends LruCache<AccessibilityNodeInfo, FocusHistory> {

	/** Type of the cache. */
	private final @CacheType int mCacheType;

	/** How many milliseconds before an entry in the cache expires. */
	private final int mExpirationTimeMs;

	FocusHistoryCache(@CacheType int cacheType, int size, int expirationTimeMs) {
	super(size);
	mCacheType = cacheType;
	mExpirationTimeMs = expirationTimeMs;
	if (mCacheType == CACHE_TYPE_EXPIRED_AFTER_SOME_TIME && mExpirationTimeMs <= 0) {
	throw new IllegalArgumentException(
	"Expiration time must be positive if CacheType is "
	+ "CACHE_TYPE_EXPIRED_AFTER_SOME_TIME");
	}
	}

	boolean enabled() {
	return mCacheType != CACHE_TYPE_DISABLED;
	}

	boolean isValidFocusHistory(@Nullable FocusHistory focusHistory, long elapsedRealtime) {
	if (focusHistory == null \|\| focusHistory.node == null) {
	return false;
	}
	switch (mCacheType) {
	case CACHE_TYPE_NEVER_EXPIRE:
	return true;
	case CACHE_TYPE_EXPIRED_AFTER_SOME_TIME:
	return elapsedRealtime - focusHistory.timestamp < mExpirationTimeMs;
	default:
	return false;
	}
	}

	@Override
	protected void entryRemoved(boolean evicted, AccessibilityNodeInfo key,
	FocusHistory oldValue, FocusHistory newValue) {
	Utils.recycleNode(key);
	Utils.recycleNode(oldValue.node);
	}
	}

	/**
	* A cache of the target focus area to nudge to, by source focus area and direction (up, down,
	* left or right).
	*/
	private class FocusAreaHistoryCache extends LruCache<FocusAreaHistory, FocusHistory> {

	/** Type of the cache. */
	private final @CacheType int mCacheType;

	/** How many milliseconds before an entry in the cache expires. */
	private final int mExpirationTimeMs;

	FocusAreaHistoryCache(@CacheType int cacheType, int size, int expirationTimeMs) {
	super(size);
	mCacheType = cacheType;
	mExpirationTimeMs = expirationTimeMs;
	if (mCacheType == CACHE_TYPE_EXPIRED_AFTER_SOME_TIME && mExpirationTimeMs <= 0) {
	throw new IllegalArgumentException(
	"Expiration time must be positive if CacheType is "
	+ "CACHE_TYPE_EXPIRED_AFTER_SOME_TIME");
	}
	}

	boolean enabled() {
	return mCacheType != CACHE_TYPE_DISABLED;
	}

	boolean isValidFocusHistory(@Nullable FocusHistory focusHistory, long elapsedRealtime) {
	if (focusHistory == null \|\| focusHistory.node == null) {
	return false;
	}
	switch (mCacheType) {
	case CACHE_TYPE_NEVER_EXPIRE:
	return true;
	case CACHE_TYPE_EXPIRED_AFTER_SOME_TIME:
	return elapsedRealtime - focusHistory.timestamp < mExpirationTimeMs;
	default:
	return false;
	}
	}

	@Override
	protected void entryRemoved(boolean evicted, FocusAreaHistory key, FocusHistory oldValue,
	FocusHistory newValue) {
	Utils.recycleNode(key.sourceFocusArea);
	Utils.recycleNode(oldValue.node);
	}
	}

	/**
	* A cache of recently focused nodes in recently focused windows. Used to recover when the
	* focused window closes.
	*/
	private class FocusWindowCache extends LruCache<Integer, FocusWindowHistory> {
	@CacheType
	final int mCacheType;
	final int mExpirationTimeMs;

	FocusWindowCache(@CacheType int cacheType, int size, int expirationTimeMs) {
	super(size);
	mCacheType = cacheType;
	mExpirationTimeMs = expirationTimeMs;
	if (cacheType == CACHE_TYPE_EXPIRED_AFTER_SOME_TIME && expirationTimeMs <= 0) {
	throw new IllegalArgumentException(
	"Expiration time must be positive if CacheType is "
	+ "CACHE_TYPE_EXPIRED_AFTER_SOME_TIME");
	}
	}

	/**
	* Returns whether an entry in this cache is valid. To be valid:
	* <ul>
	* <li>the cached node must still be in the view tree
	* <li>the cached node must still be able to take focus
	* <li>the cache entry must not have expired
	* </ul>
	*/
	boolean isValidEntry(@NonNull FocusWindowHistory focusWindowHistory, long elapsedRealtime) {
	if (!focusWindowHistory.mNode.refresh()
	\|\| !Utils.canTakeFocus(focusWindowHistory.mNode)) {
	return false;
	}

	switch (mCacheType) {
	case CACHE_TYPE_NEVER_EXPIRE:
	return true;
	case CACHE_TYPE_EXPIRED_AFTER_SOME_TIME:
	return elapsedRealtime - focusWindowHistory.mTimestamp < mExpirationTimeMs;
	default:
	return false;
	}
	}

	/**
	* Stores the given (window ID, node) pair, overwriting the existing pair with the given
	* window ID, if any.
	*/
	void put(int windowId, @NonNull AccessibilityNodeInfo node, long elapsedRealtime) {
	if (mCacheType == CACHE_TYPE_DISABLED) {
	return;
	}
	put(windowId, new FocusWindowHistory(copyNode(node), elapsedRealtime));
	}

	/**
	* Returns the most recently focused valid node in window {@code windowId}, or {@code null}
	* if there are no valid nodes in the cache. The caller is responsible for recycling the
	* result.
	*/
	@Nullable
	AccessibilityNodeInfo getMostRecentValidNode(int windowId, long elapsedRealtime) {
	FocusWindowHistory focusWindowHistory = get(windowId);
	if (focusWindowHistory != null && isValidEntry(focusWindowHistory, elapsedRealtime)) {
	return copyNode(focusWindowHistory.mNode);
	}
	return null;
	}

	@Override
	protected void entryRemoved(boolean evicted, Integer windowId, FocusWindowHistory oldValue,
	FocusWindowHistory newValue) {
	oldValue.recycle();
	}
	}

	RotaryCache(@CacheType int focusHistoryCacheType,
	int focusHistoryCacheSize,
	int focusHistoryExpirationTimeMs,
	@CacheType int focusAreaHistoryCacheType,
	int focusAreaHistoryCacheSize,
	int focusAreaHistoryExpirationTimeMs,
	@CacheType int focusWindowCacheType,
	int focusWindowCacheSize,
	int focusWindowExpirationTimeMs) {
	mFocusHistoryCache = new FocusHistoryCache(
	focusHistoryCacheType, focusHistoryCacheSize, focusHistoryExpirationTimeMs);
	mFocusAreaHistoryCache = new FocusAreaHistoryCache(focusAreaHistoryCacheType,
	focusAreaHistoryCacheSize, focusAreaHistoryExpirationTimeMs);
	mFocusWindowCache = new FocusWindowCache(focusWindowCacheType, focusWindowCacheSize,
	focusWindowExpirationTimeMs);
	}

	/**
	* Searches the cache to find the last focused node in the given {@code focusArea}. Returns the
	* node, or null if there is nothing in the cache, the cache is stale, the view represented
	* by the node is no longer in the view tree, or the node's state has changed so that it can't
	* take focus any more. The caller is responsible for recycling the result.
	*/
	AccessibilityNodeInfo getFocusedNode(@NonNull AccessibilityNodeInfo focusArea,
	long elapsedRealtime) {
	if (mFocusHistoryCache.enabled()) {
	FocusHistory focusHistory = mFocusHistoryCache.get(focusArea);
	if (mFocusHistoryCache.isValidFocusHistory(focusHistory, elapsedRealtime)) {
	AccessibilityNodeInfo node = copyNode(focusHistory.node);
	// Refresh the node in case the view represented by the node is no longer in the
	// view tree, or the node's state (e.g., isFocused()) has changed.
	AccessibilityNodeInfo refreshedNode = Utils.refreshNode(node);

	// If the node's state has changed so that it can't take focus any more, return
	// null.
	if (refreshedNode != null && !Utils.canTakeFocus(refreshedNode)) {
	Utils.recycleNode(refreshedNode);
	refreshedNode = null;
	}
	return refreshedNode;
	}
	}
	return null;
	}

	/**
	* Caches the last focused node by focus area. A copy of {@code focusArea} and {@code
	* focusedNode} will be saved in the cache.
	*/
	void saveFocusedNode(@NonNull AccessibilityNodeInfo focusArea,
	@NonNull AccessibilityNodeInfo focusedNode, long elapsedRealtime) {
	if (mFocusHistoryCache.enabled()) {
	mFocusHistoryCache.put(
	copyNode(focusArea), new FocusHistory(copyNode(focusedNode), elapsedRealtime));
	}
	}

	/**
	* Searches the cache to find the target focus area for a nudge in a given {@code direction}
	* from a given focus area. Returns the focus area, or null if there is nothing in the cache,
	* the cache is stale, or the view represented by the node is no longer in the view tree.
	* The caller is responsible for recycling the result.
	*/
	AccessibilityNodeInfo getTargetFocusArea(@NonNull AccessibilityNodeInfo sourceFocusArea,
	int direction, long elapsedRealtime) {
	if (mFocusAreaHistoryCache.enabled()) {
	FocusHistory focusHistory =
	mFocusAreaHistoryCache.get(new FocusAreaHistory(sourceFocusArea, direction));
	if (mFocusAreaHistoryCache.isValidFocusHistory(focusHistory, elapsedRealtime)) {
	AccessibilityNodeInfo focusArea = copyNode(focusHistory.node);
	// Refresh the node in case the view represented by the node is no longer in the
	// view tree.
	return Utils.refreshNode(focusArea);
	}
	}
	return null;
	}

	/**
	* Caches the focus area nudge history. A copy of {@code sourceFocusArea} and {@code
	* targetFocusArea} will be saved in the cache.
	*/
	void saveTargetFocusArea(@NonNull AccessibilityNodeInfo sourceFocusArea,
	@NonNull AccessibilityNodeInfo targetFocusArea, int direction, long elapsedRealtime) {
	if (mFocusAreaHistoryCache.enabled()) {
	int oppositeDirection = getOppositeDirection(direction);
	mFocusAreaHistoryCache
	.put(new FocusAreaHistory(copyNode(targetFocusArea), oppositeDirection),
	new FocusHistory(copyNode(sourceFocusArea), elapsedRealtime));
	}
	}

	/** Clears the focus area nudge history cache. */
	void clearFocusAreaHistory() {
	if (mFocusAreaHistoryCache.enabled()) {
	mFocusAreaHistoryCache.evictAll();
	}
	}

	@VisibleForTesting
	boolean isFocusAreaHistoryCacheEmpty() {
	return mFocusAreaHistoryCache.size() == 0;
	}

	/** Saves the most recently focused node within a window. */
	void saveWindowFocus(@NonNull AccessibilityNodeInfo focusedNode, long elapsedRealtime) {
	mFocusWindowCache.put(focusedNode.getWindowId(), focusedNode, elapsedRealtime);
	}

	/**
	* Returns the most recently focused valid node in window {@code windowId}, or {@code null} if
	* there are no valid nodes saved by {@link #saveWindowFocus}. The caller is responsible for
	* recycling the result.
	*/
	@Nullable
	AccessibilityNodeInfo getMostRecentFocus(int windowId, long elapsedRealtime) {
	return mFocusWindowCache.getMostRecentValidNode(windowId, elapsedRealtime);
	}

	/** Returns the direction opposite the given {@code direction} */
	@VisibleForTesting
	static int getOppositeDirection(int direction) {
	switch (direction) {
	case View.FOCUS_LEFT:
	return View.FOCUS_RIGHT;
	case View.FOCUS_RIGHT:
	return View.FOCUS_LEFT;
	case View.FOCUS_UP:
	return View.FOCUS_DOWN;
	case View.FOCUS_DOWN:
	return View.FOCUS_UP;
	}
	throw new IllegalArgumentException("direction must be "
	+ "FOCUS_UP, FOCUS_DOWN, FOCUS_LEFT, or FOCUS_RIGHT.");
	}

	/** Sets a mock {@link NodeCopier} instance for testing. */
	@VisibleForTesting
	void setNodeCopier(@NonNull NodeCopier nodeCopier) {
	mNodeCopier = nodeCopier;
	}

	private AccessibilityNodeInfo copyNode(@Nullable AccessibilityNodeInfo node) {
	return mNodeCopier.copy(node);
	}
	}