/*
 * Copyright (C) 2010 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 android.animation;

import android.app.ActivityThread;
import android.app.Application;
import android.os.Build;
import android.os.Looper;
import android.util.AndroidRuntimeException;
import android.util.ArrayMap;
import android.util.Log;
import android.view.animation.Animation;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;

/**
 * This class plays a set of {@link Animator} objects in the specified order. Animations
 * can be set up to play together, in sequence, or after a specified delay.
 *
 * <p>There are two different approaches to adding animations to a <code>AnimatorSet</code>:
 * either the {@link AnimatorSet#playTogether(Animator[]) playTogether()} or
 * {@link AnimatorSet#playSequentially(Animator[]) playSequentially()} methods can be called to add
 * a set of animations all at once, or the {@link AnimatorSet#play(Animator)} can be
 * used in conjunction with methods in the {@link AnimatorSet.Builder Builder}
 * class to add animations
 * one by one.</p>
 *
 * <p>It is possible to set up a <code>AnimatorSet</code> with circular dependencies between
 * its animations. For example, an animation a1 could be set up to start before animation a2, a2
 * before a3, and a3 before a1. The results of this configuration are undefined, but will typically
 * result in none of the affected animations being played. Because of this (and because
 * circular dependencies do not make logical sense anyway), circular dependencies
 * should be avoided, and the dependency flow of animations should only be in one direction.
 *
 * <div class="special reference">
 * <h3>Developer Guides</h3>
 * <p>For more information about animating with {@code AnimatorSet}, read the
 * <a href="{@docRoot}guide/topics/graphics/prop-animation.html#choreography">Property
 * Animation</a> developer guide.</p>
 * </div>
 */
public final class AnimatorSet extends Animator implements AnimationHandler.AnimationFrameCallback {

    private static final String TAG = "AnimatorSet";
    /**
     * Internal variables
     * NOTE: This object implements the clone() method, making a deep copy of any referenced
     * objects. As other non-trivial fields are added to this class, make sure to add logic
     * to clone() to make deep copies of them.
     */

    /**
     * Tracks animations currently being played, so that we know what to
     * cancel or end when cancel() or end() is called on this AnimatorSet
     */
    private ArrayList<Node> mPlayingSet = new ArrayList<Node>();

    /**
     * Contains all nodes, mapped to their respective Animators. When new
     * dependency information is added for an Animator, we want to add it
     * to a single node representing that Animator, not create a new Node
     * if one already exists.
     */
    private ArrayMap<Animator, Node> mNodeMap = new ArrayMap<Animator, Node>();

    /**
     * Contains the start and end events of all the nodes. All these events are sorted in this list.
     */
    private ArrayList<AnimationEvent> mEvents = new ArrayList<>();

    /**
     * Set of all nodes created for this AnimatorSet. This list is used upon
     * starting the set, and the nodes are placed in sorted order into the
     * sortedNodes collection.
     */
    private ArrayList<Node> mNodes = new ArrayList<Node>();

    /**
     * Tracks whether any change has been made to the AnimatorSet, which is then used to
     * determine whether the dependency graph should be re-constructed.
     */
    private boolean mDependencyDirty = false;

    /**
     * Indicates whether an AnimatorSet has been start()'d, whether or
     * not there is a nonzero startDelay.
     */
    private boolean mStarted = false;

    // The amount of time in ms to delay starting the animation after start() is called
    private long mStartDelay = 0;

    // Animator used for a nonzero startDelay
    private ValueAnimator mDelayAnim = ValueAnimator.ofFloat(0f, 1f).setDuration(0);

    // Root of the dependency tree of all the animators in the set. In this tree, parent-child
    // relationship captures the order of animation (i.e. parent and child will play sequentially),
    // and sibling relationship indicates "with" relationship, as sibling animators start at the
    // same time.
    private Node mRootNode = new Node(mDelayAnim);

    // How long the child animations should last in ms. The default value is negative, which
    // simply means that there is no duration set on the AnimatorSet. When a real duration is
    // set, it is passed along to the child animations.
    private long mDuration = -1;

    // Records the interpolator for the set. Null value indicates that no interpolator
    // was set on this AnimatorSet, so it should not be passed down to the children.
    private TimeInterpolator mInterpolator = null;

    // The total duration of finishing all the Animators in the set.
    private long mTotalDuration = 0;

    // In pre-N releases, calling end() before start() on an animator set is no-op. But that is not
    // consistent with the behavior for other animator types. In order to keep the behavior
    // consistent within Animation framework, when end() is called without start(), we will start
    // the animator set and immediately end it for N and forward.
    private final boolean mShouldIgnoreEndWithoutStart;

    // In pre-O releases, calling start() doesn't reset all the animators values to start values.
    // As a result, the start of the animation is inconsistent with what setCurrentPlayTime(0) would
    // look like on O. Also it is inconsistent with what reverse() does on O, as reverse would
    // advance all the animations to the right beginning values for before starting to reverse.
    // From O and forward, we will add an additional step of resetting the animation values (unless
    // the animation was previously seeked and therefore doesn't start from the beginning).
    private final boolean mShouldResetValuesAtStart;

    // In pre-O releases, end() may never explicitly called on a child animator. As a result, end()
    // may not even be properly implemented in a lot of cases. After a few apps crashing on this,
    // it became necessary to use an sdk target guard for calling end().
    private final boolean mEndCanBeCalled;

    // The time, in milliseconds, when last frame of the animation came in. -1 when the animation is
    // not running.
    private long mLastFrameTime = -1;

    // The time, in milliseconds, when the first frame of the animation came in. This is the
    // frame before we start counting down the start delay, if any.
    // -1 when the animation is not running.
    private long mFirstFrame = -1;

    // The time, in milliseconds, when the first frame of the animation came in.
    // -1 when the animation is not running.
    private int mLastEventId = -1;

    // Indicates whether the animation is reversing.
    private boolean mReversing = false;

    // Indicates whether the animation should register frame callbacks. If false, the animation will
    // passively wait for an AnimatorSet to pulse it.
    private boolean mSelfPulse = true;

    // SeekState stores the last seeked play time as well as seek direction.
    private SeekState mSeekState = new SeekState();

    // Indicates where children animators are all initialized with their start values captured.
    private boolean mChildrenInitialized = false;

    /**
     * Set on the next frame after pause() is called, used to calculate a new startTime
     * or delayStartTime which allows the animator set to continue from the point at which
     * it was paused. If negative, has not yet been set.
     */
    private long mPauseTime = -1;

    // This is to work around a bug in b/34736819. This needs to be removed once app team
    // fixes their side.
    private AnimatorListenerAdapter mDummyListener = new AnimatorListenerAdapter() {
        @Override
        public void onAnimationEnd(Animator animation) {
            if (mNodeMap.get(animation) == null) {
                throw new AndroidRuntimeException("Error: animation ended is not in the node map");
            }
            mNodeMap.get(animation).mEnded = true;

        }
    };

    public AnimatorSet() {
        super();
        mNodeMap.put(mDelayAnim, mRootNode);
        mNodes.add(mRootNode);
        boolean isPreO;
        // Set the flag to ignore calling end() without start() for pre-N releases
        Application app = ActivityThread.currentApplication();
        if (app == null || app.getApplicationInfo() == null) {
            mShouldIgnoreEndWithoutStart = true;
            isPreO = true;
        } else {
            if (app.getApplicationInfo().targetSdkVersion < Build.VERSION_CODES.N) {
                mShouldIgnoreEndWithoutStart = true;
            } else {
                mShouldIgnoreEndWithoutStart = false;
            }

            isPreO = app.getApplicationInfo().targetSdkVersion < Build.VERSION_CODES.O;
        }
        mShouldResetValuesAtStart = !isPreO;
        mEndCanBeCalled = !isPreO;
    }

    /**
     * Sets up this AnimatorSet to play all of the supplied animations at the same time.
     * This is equivalent to calling {@link #play(Animator)} with the first animator in the
     * set and then {@link Builder#with(Animator)} with each of the other animators. Note that
     * an Animator with a {@link Animator#setStartDelay(long) startDelay} will not actually
     * start until that delay elapses, which means that if the first animator in the list
     * supplied to this constructor has a startDelay, none of the other animators will start
     * until that first animator's startDelay has elapsed.
     *
     * @param items The animations that will be started simultaneously.
     */
    public void playTogether(Animator... items) {
        if (items != null) {
            Builder builder = play(items[0]);
            for (int i = 1; i < items.length; ++i) {
                builder.with(items[i]);
            }
        }
    }

    /**
     * Sets up this AnimatorSet to play all of the supplied animations at the same time.
     *
     * @param items The animations that will be started simultaneously.
     */
    public void playTogether(Collection<Animator> items) {
        if (items != null && items.size() > 0) {
            Builder builder = null;
            for (Animator anim : items) {
                if (builder == null) {
                    builder = play(anim);
                } else {
                    builder.with(anim);
                }
            }
        }
    }

    /**
     * Sets up this AnimatorSet to play each of the supplied animations when the
     * previous animation ends.
     *
     * @param items The animations that will be started one after another.
     */
    public void playSequentially(Animator... items) {
        if (items != null) {
            if (items.length == 1) {
                play(items[0]);
            } else {
                for (int i = 0; i < items.length - 1; ++i) {
                    play(items[i]).before(items[i + 1]);
                }
            }
        }
    }

    /**
     * Sets up this AnimatorSet to play each of the supplied animations when the
     * previous animation ends.
     *
     * @param items The animations that will be started one after another.
     */
    public void playSequentially(List<Animator> items) {
        if (items != null && items.size() > 0) {
            if (items.size() == 1) {
                play(items.get(0));
            } else {
                for (int i = 0; i < items.size() - 1; ++i) {
                    play(items.get(i)).before(items.get(i + 1));
                }
            }
        }
    }

    /**
     * Returns the current list of child Animator objects controlled by this
     * AnimatorSet. This is a copy of the internal list; modifications to the returned list
     * will not affect the AnimatorSet, although changes to the underlying Animator objects
     * will affect those objects being managed by the AnimatorSet.
     *
     * @return ArrayList<Animator> The list of child animations of this AnimatorSet.
     */
    public ArrayList<Animator> getChildAnimations() {
        ArrayList<Animator> childList = new ArrayList<Animator>();
        int size = mNodes.size();
        for (int i = 0; i < size; i++) {
            Node node = mNodes.get(i);
            if (node != mRootNode) {
                childList.add(node.mAnimation);
            }
        }
        return childList;
    }

    /**
     * Sets the target object for all current {@link #getChildAnimations() child animations}
     * of this AnimatorSet that take targets ({@link ObjectAnimator} and
     * AnimatorSet).
     *
     * @param target The object being animated
     */
    @Override
    public void setTarget(Object target) {
        int size = mNodes.size();
        for (int i = 0; i < size; i++) {
            Node node = mNodes.get(i);
            Animator animation = node.mAnimation;
            if (animation instanceof AnimatorSet) {
                ((AnimatorSet)animation).setTarget(target);
            } else if (animation instanceof ObjectAnimator) {
                ((ObjectAnimator)animation).setTarget(target);
            }
        }
    }

    /**
     * @hide
     */
    @Override
    public int getChangingConfigurations() {
        int conf = super.getChangingConfigurations();
        final int nodeCount = mNodes.size();
        for (int i = 0; i < nodeCount; i ++) {
            conf |= mNodes.get(i).mAnimation.getChangingConfigurations();
        }
        return conf;
    }

    /**
     * Sets the TimeInterpolator for all current {@link #getChildAnimations() child animations}
     * of this AnimatorSet. The default value is null, which means that no interpolator
     * is set on this AnimatorSet. Setting the interpolator to any non-null value
     * will cause that interpolator to be set on the child animations
     * when the set is started.
     *
     * @param interpolator the interpolator to be used by each child animation of this AnimatorSet
     */
    @Override
    public void setInterpolator(TimeInterpolator interpolator) {
        mInterpolator = interpolator;
    }

    @Override
    public TimeInterpolator getInterpolator() {
        return mInterpolator;
    }

    /**
     * This method creates a <code>Builder</code> object, which is used to
     * set up playing constraints. This initial <code>play()</code> method
     * tells the <code>Builder</code> the animation that is the dependency for
     * the succeeding commands to the <code>Builder</code>. For example,
     * calling <code>play(a1).with(a2)</code> sets up the AnimatorSet to play
     * <code>a1</code> and <code>a2</code> at the same time,
     * <code>play(a1).before(a2)</code> sets up the AnimatorSet to play
     * <code>a1</code> first, followed by <code>a2</code>, and
     * <code>play(a1).after(a2)</code> sets up the AnimatorSet to play
     * <code>a2</code> first, followed by <code>a1</code>.
     *
     * <p>Note that <code>play()</code> is the only way to tell the
     * <code>Builder</code> the animation upon which the dependency is created,
     * so successive calls to the various functions in <code>Builder</code>
     * will all refer to the initial parameter supplied in <code>play()</code>
     * as the dependency of the other animations. For example, calling
     * <code>play(a1).before(a2).before(a3)</code> will play both <code>a2</code>
     * and <code>a3</code> when a1 ends; it does not set up a dependency between
     * <code>a2</code> and <code>a3</code>.</p>
     *
     * @param anim The animation that is the dependency used in later calls to the
     * methods in the returned <code>Builder</code> object. A null parameter will result
     * in a null <code>Builder</code> return value.
     * @return Builder The object that constructs the AnimatorSet based on the dependencies
     * outlined in the calls to <code>play</code> and the other methods in the
     * <code>Builder</code object.
     */
    public Builder play(Animator anim) {
        if (anim != null) {
            return new Builder(anim);
        }
        return null;
    }

    /**
     * {@inheritDoc}
     *
     * <p>Note that canceling a <code>AnimatorSet</code> also cancels all of the animations that it
     * is responsible for.</p>
     */
    @SuppressWarnings("unchecked")
    @Override
    public void cancel() {
        if (Looper.myLooper() == null) {
            throw new AndroidRuntimeException("Animators may only be run on Looper threads");
        }
        if (isStarted()) {
            ArrayList<AnimatorListener> tmpListeners = null;
            if (mListeners != null) {
                tmpListeners = (ArrayList<AnimatorListener>) mListeners.clone();
                int size = tmpListeners.size();
                for (int i = 0; i < size; i++) {
                    tmpListeners.get(i).onAnimationCancel(this);
                }
            }
            ArrayList<Node> playingSet = new ArrayList<>(mPlayingSet);
            int setSize = playingSet.size();
            for (int i = 0; i < setSize; i++) {
                playingSet.get(i).mAnimation.cancel();
            }
            mPlayingSet.clear();
            endAnimation();
        }
    }

    // Force all the animations to end when the duration scale is 0.
    private void forceToEnd() {
        if (mEndCanBeCalled) {
            end();
            return;
        }

        // Note: we don't want to combine this case with the end() method below because in
        // the case of developer calling end(), we still need to make sure end() is explicitly
        // called on the child animators to maintain the old behavior.
        if (mReversing) {
            handleAnimationEvents(mLastEventId, 0, getTotalDuration());
        } else {
            long zeroScalePlayTime = getTotalDuration();
            if (zeroScalePlayTime == DURATION_INFINITE) {
                // Use a large number for the play time.
                zeroScalePlayTime = Integer.MAX_VALUE;
            }
            handleAnimationEvents(mLastEventId, mEvents.size() - 1, zeroScalePlayTime);
        }
        mPlayingSet.clear();
        endAnimation();
    }

    /**
     * {@inheritDoc}
     *
     * <p>Note that ending a <code>AnimatorSet</code> also ends all of the animations that it is
     * responsible for.</p>
     */
    @Override
    public void end() {
        if (Looper.myLooper() == null) {
            throw new AndroidRuntimeException("Animators may only be run on Looper threads");
        }
        if (mShouldIgnoreEndWithoutStart && !isStarted()) {
            return;
        }
        if (isStarted()) {
            // Iterate the animations that haven't finished or haven't started, and end them.
            if (mReversing) {
                // Between start() and first frame, mLastEventId would be unset (i.e. -1)
                mLastEventId = mLastEventId == -1 ? mEvents.size() : mLastEventId;
                while (mLastEventId > 0) {
                    mLastEventId = mLastEventId - 1;
                    AnimationEvent event = mEvents.get(mLastEventId);
                    Animator anim = event.mNode.mAnimation;
                    if (mNodeMap.get(anim).mEnded) {
                        continue;
                    }
                    if (event.mEvent == AnimationEvent.ANIMATION_END) {
                        anim.reverse();
                    } else if (event.mEvent == AnimationEvent.ANIMATION_DELAY_ENDED
                            && anim.isStarted()) {
                        // Make sure anim hasn't finished before calling end() so that we don't end
                        // already ended animations, which will cause start and end callbacks to be
                        // triggered again.
                        anim.end();
                    }
                }
            } else {
                while (mLastEventId < mEvents.size() - 1) {
                    // Avoid potential reentrant loop caused by child animators manipulating
                    // AnimatorSet's lifecycle (i.e. not a recommended approach).
                    mLastEventId = mLastEventId + 1;
                    AnimationEvent event = mEvents.get(mLastEventId);
                    Animator anim = event.mNode.mAnimation;
                    if (mNodeMap.get(anim).mEnded) {
                        continue;
                    }
                    if (event.mEvent == AnimationEvent.ANIMATION_START) {
                        anim.start();
                    } else if (event.mEvent == AnimationEvent.ANIMATION_END && anim.isStarted()) {
                        // Make sure anim hasn't finished before calling end() so that we don't end
                        // already ended animations, which will cause start and end callbacks to be
                        // triggered again.
                        anim.end();
                    }
                }
            }
            mPlayingSet.clear();
        }
        endAnimation();
    }

    /**
     * Returns true if any of the child animations of this AnimatorSet have been started and have
     * not yet ended. Child animations will not be started until the AnimatorSet has gone past
     * its initial delay set through {@link #setStartDelay(long)}.
     *
     * @return Whether this AnimatorSet has gone past the initial delay, and at least one child
     *         animation has been started and not yet ended.
     */
    @Override
    public boolean isRunning() {
        if (mStartDelay == 0) {
            return mStarted;
        }
        return mLastFrameTime > 0;
    }

    @Override
    public boolean isStarted() {
        return mStarted;
    }

    /**
     * The amount of time, in milliseconds, to delay starting the animation after
     * {@link #start()} is called.
     *
     * @return the number of milliseconds to delay running the animation
     */
    @Override
    public long getStartDelay() {
        return mStartDelay;
    }

    /**
     * The amount of time, in milliseconds, to delay starting the animation after
     * {@link #start()} is called. Note that the start delay should always be non-negative. Any
     * negative start delay will be clamped to 0 on N and above.
     *
     * @param startDelay The amount of the delay, in milliseconds
     */
    @Override
    public void setStartDelay(long startDelay) {
        // Clamp start delay to non-negative range.
        if (startDelay < 0) {
            Log.w(TAG, "Start delay should always be non-negative");
            startDelay = 0;
        }
        long delta = startDelay - mStartDelay;
        if (delta == 0) {
            return;
        }
        mStartDelay = startDelay;
        if (!mDependencyDirty) {
            // Dependency graph already constructed, update all the nodes' start/end time
            int size = mNodes.size();
            for (int i = 0; i < size; i++) {
                Node node = mNodes.get(i);
                if (node == mRootNode) {
                    node.mEndTime = mStartDelay;
                } else {
                    node.mStartTime = node.mStartTime == DURATION_INFINITE ?
                            DURATION_INFINITE : node.mStartTime + delta;
                    node.mEndTime = node.mEndTime == DURATION_INFINITE ?
                            DURATION_INFINITE : node.mEndTime + delta;
                }
            }
            // Update total duration, if necessary.
            if (mTotalDuration != DURATION_INFINITE) {
                mTotalDuration += delta;
            }
        }
    }

    /**
     * Gets the length of each of the child animations of this AnimatorSet. This value may
     * be less than 0, which indicates that no duration has been set on this AnimatorSet
     * and each of the child animations will use their own duration.
     *
     * @return The length of the animation, in milliseconds, of each of the child
     * animations of this AnimatorSet.
     */
    @Override
    public long getDuration() {
        return mDuration;
    }

    /**
     * Sets the length of each of the current child animations of this AnimatorSet. By default,
     * each child animation will use its own duration. If the duration is set on the AnimatorSet,
     * then each child animation inherits this duration.
     *
     * @param duration The length of the animation, in milliseconds, of each of the child
     * animations of this AnimatorSet.
     */
    @Override
    public AnimatorSet setDuration(long duration) {
        if (duration < 0) {
            throw new IllegalArgumentException("duration must be a value of zero or greater");
        }
        mDependencyDirty = true;
        // Just record the value for now - it will be used later when the AnimatorSet starts
        mDuration = duration;
        return this;
    }

    @Override
    public void setupStartValues() {
        int size = mNodes.size();
        for (int i = 0; i < size; i++) {
            Node node = mNodes.get(i);
            if (node != mRootNode) {
                node.mAnimation.setupStartValues();
            }
        }
    }

    @Override
    public void setupEndValues() {
        int size = mNodes.size();
        for (int i = 0; i < size; i++) {
            Node node = mNodes.get(i);
            if (node != mRootNode) {
                node.mAnimation.setupEndValues();
            }
        }
    }

    @Override
    public void pause() {
        if (Looper.myLooper() == null) {
            throw new AndroidRuntimeException("Animators may only be run on Looper threads");
        }
        boolean previouslyPaused = mPaused;
        super.pause();
        if (!previouslyPaused && mPaused) {
            mPauseTime = -1;
        }
    }

    @Override
    public void resume() {
        if (Looper.myLooper() == null) {
            throw new AndroidRuntimeException("Animators may only be run on Looper threads");
        }
        boolean previouslyPaused = mPaused;
        super.resume();
        if (previouslyPaused && !mPaused) {
            if (mPauseTime >= 0) {
                addAnimationCallback(0);
            }
        }
    }

    /**
     * {@inheritDoc}
     *
     * <p>Starting this <code>AnimatorSet</code> will, in turn, start the animations for which
     * it is responsible. The details of when exactly those animations are started depends on
     * the dependency relationships that have been set up between the animations.
     *
     * <b>Note:</b> Manipulating AnimatorSet's lifecycle in the child animators' listener callbacks
     * will lead to undefined behaviors. Also, AnimatorSet will ignore any seeking in the child
     * animators once {@link #start()} is called.
     */
    @SuppressWarnings("unchecked")
    @Override
    public void start() {
        start(false, true);
    }

    @Override
    void startWithoutPulsing(boolean inReverse) {
        start(inReverse, false);
    }

    private void initAnimation() {
        if (mInterpolator != null) {
            for (int i = 0; i < mNodes.size(); i++) {
                Node node = mNodes.get(i);
                node.mAnimation.setInterpolator(mInterpolator);
            }
        }
        updateAnimatorsDuration();
        createDependencyGraph();
    }

    private void start(boolean inReverse, boolean selfPulse) {
        if (Looper.myLooper() == null) {
            throw new AndroidRuntimeException("Animators may only be run on Looper threads");
        }
        mStarted = true;
        mSelfPulse = selfPulse;
        mPaused = false;
        mPauseTime = -1;

        int size = mNodes.size();
        for (int i = 0; i < size; i++) {
            Node node = mNodes.get(i);
            node.mEnded = false;
            node.mAnimation.setAllowRunningAsynchronously(false);
        }

        initAnimation();
        if (inReverse && !canReverse()) {
            throw new UnsupportedOperationException("Cannot reverse infinite AnimatorSet");
        }

        mReversing = inReverse;

        // Now that all dependencies are set up, start the animations that should be started.
        boolean isEmptySet = isEmptySet(this);
        if (!isEmptySet) {
            startAnimation();
        }

        if (mListeners != null) {
            ArrayList<AnimatorListener> tmpListeners =
                    (ArrayList<AnimatorListener>) mListeners.clone();
            int numListeners = tmpListeners.size();
            for (int i = 0; i < numListeners; ++i) {
                tmpListeners.get(i).onAnimationStart(this, inReverse);
            }
        }
        if (isEmptySet) {
            // In the case of empty AnimatorSet, or 0 duration scale, we will trigger the
            // onAnimationEnd() right away.
            end();
        }
    }

    // Returns true if set is empty or contains nothing but animator sets with no start delay.
    private static boolean isEmptySet(AnimatorSet set) {
        if (set.getStartDelay() > 0) {
            return false;
        }
        for (int i = 0; i < set.getChildAnimations().size(); i++) {
            Animator anim = set.getChildAnimations().get(i);
            if (!(anim instanceof AnimatorSet)) {
                // Contains non-AnimatorSet, not empty.
                return false;
            } else {
                if (!isEmptySet((AnimatorSet) anim)) {
                    return false;
                }
            }
        }
        return true;
    }

    private void updateAnimatorsDuration() {
        if (mDuration >= 0) {
            // If the duration was set on this AnimatorSet, pass it along to all child animations
            int size = mNodes.size();
            for (int i = 0; i < size; i++) {
                Node node = mNodes.get(i);
                // TODO: don't set the duration of the timing-only nodes created by AnimatorSet to
                // insert "play-after" delays
                node.mAnimation.setDuration(mDuration);
            }
        }
        mDelayAnim.setDuration(mStartDelay);
    }

    @Override
    void skipToEndValue(boolean inReverse) {
        if (!isInitialized()) {
            throw new UnsupportedOperationException("Children must be initialized.");
        }

        // This makes sure the animation events are sorted an up to date.
        initAnimation();

        // Calling skip to the end in the sequence that they would be called in a forward/reverse
        // run, such that the sequential animations modifying the same property would have
        // the right value in the end.
        if (inReverse) {
            for (int i = mEvents.size() - 1; i >= 0; i--) {
                if (mEvents.get(i).mEvent == AnimationEvent.ANIMATION_DELAY_ENDED) {
                    mEvents.get(i).mNode.mAnimation.skipToEndValue(true);
                }
            }
        } else {
            for (int i = 0; i < mEvents.size(); i++) {
                if (mEvents.get(i).mEvent == AnimationEvent.ANIMATION_END) {
                    mEvents.get(i).mNode.mAnimation.skipToEndValue(false);
                }
            }
        }
    }

    /**
     * Internal only.
     *
     * This method sets the animation values based on the play time. It also fast forward or
     * backward all the child animations progress accordingly.
     *
     * This method is also responsible for calling
     * {@link android.view.animation.Animation.AnimationListener#onAnimationRepeat(Animation)},
     * as needed, based on the last play time and current play time.
     */
    @Override
    void animateBasedOnPlayTime(long currentPlayTime, long lastPlayTime, boolean inReverse) {
        if (currentPlayTime < 0 || lastPlayTime < 0) {
            throw new UnsupportedOperationException("Error: Play time should never be negative.");
        }
        // TODO: take into account repeat counts and repeat callback when repeat is implemented.
        // Clamp currentPlayTime and lastPlayTime

        // TODO: Make this more efficient

        // Convert the play times to the forward direction.
        if (inReverse) {
            if (getTotalDuration() == DURATION_INFINITE) {
                throw new UnsupportedOperationException("Cannot reverse AnimatorSet with infinite"
                        + " duration");
            }
            long duration = getTotalDuration() - mStartDelay;
            currentPlayTime = Math.min(currentPlayTime, duration);
            currentPlayTime = duration - currentPlayTime;
            lastPlayTime = duration - lastPlayTime;
            inReverse = false;
        }
        // Skip all values to start, and iterate mEvents to get animations to the right fraction.
        skipToStartValue(false);

        ArrayList<Node> unfinishedNodes = new ArrayList<>();
        // Assumes forward playing from here on.
        for (int i = 0; i < mEvents.size(); i++) {
            AnimationEvent event = mEvents.get(i);
            if (event.getTime() > currentPlayTime || event.getTime() == DURATION_INFINITE) {
                break;
            }

            // This animation started prior to the current play time, and won't finish before the
            // play time, add to the unfinished list.
            if (event.mEvent == AnimationEvent.ANIMATION_DELAY_ENDED) {
                if (event.mNode.mEndTime == DURATION_INFINITE
                        || event.mNode.mEndTime > currentPlayTime) {
                    unfinishedNodes.add(event.mNode);
                }
            }
            // For animations that do finish before the play time, end them in the sequence that
            // they would in a normal run.
            if (event.mEvent == AnimationEvent.ANIMATION_END) {
                // Skip to the end of the animation.
                event.mNode.mAnimation.skipToEndValue(false);
            }
        }

        // Seek unfinished animation to the right time.
        for (int i = 0; i < unfinishedNodes.size(); i++) {
            Node node = unfinishedNodes.get(i);
            long playTime = getPlayTimeForNode(currentPlayTime, node, inReverse);
            if (!inReverse) {
                playTime -= node.mAnimation.getStartDelay();
            }
            node.mAnimation.animateBasedOnPlayTime(playTime, lastPlayTime, inReverse);
        }
    }

    @Override
    boolean isInitialized() {
        if (mChildrenInitialized) {
            return true;
        }

        boolean allInitialized = true;
        for (int i = 0; i < mNodes.size(); i++) {
            if (!mNodes.get(i).mAnimation.isInitialized()) {
                allInitialized = false;
                break;
            }
        }
        mChildrenInitialized = allInitialized;
        return mChildrenInitialized;
    }

    private void skipToStartValue(boolean inReverse) {
        skipToEndValue(!inReverse);
    }

    /**
     * Sets the position of the animation to the specified point in time. This time should
     * be between 0 and the total duration of the animation, including any repetition. If
     * the animation has not yet been started, then it will not advance forward after it is
     * set to this time; it will simply set the time to this value and perform any appropriate
     * actions based on that time. If the animation is already running, then setCurrentPlayTime()
     * will set the current playing time to this value and continue playing from that point.
     *
     * @param playTime The time, in milliseconds, to which the animation is advanced or rewound.
     *                 Unless the animation is reversing, the playtime is considered the time since
     *                 the end of the start delay of the AnimatorSet in a forward playing direction.
     *
     */
    public void setCurrentPlayTime(long playTime) {
        if (mReversing && getTotalDuration() == DURATION_INFINITE) {
            // Should never get here
            throw new UnsupportedOperationException("Error: Cannot seek in reverse in an infinite"
                    + " AnimatorSet");
        }

        if ((getTotalDuration() != DURATION_INFINITE && playTime > getTotalDuration() - mStartDelay)
                || playTime < 0) {
            throw new UnsupportedOperationException("Error: Play time should always be in between"
                    + "0 and duration.");
        }

        initAnimation();

        if (!isStarted()) {
            if (mReversing) {
                throw new UnsupportedOperationException("Error: Something went wrong. mReversing"
                        + " should not be set when AnimatorSet is not started.");
            }
            if (!mSeekState.isActive()) {
                findLatestEventIdForTime(0);
                // Set all the values to start values.
                initChildren();
                skipToStartValue(mReversing);
                mSeekState.setPlayTime(0, mReversing);
            }
            animateBasedOnPlayTime(playTime, 0, mReversing);
            mSeekState.setPlayTime(playTime, mReversing);
        } else {
            // If the animation is running, just set the seek time and wait until the next frame
            // (i.e. doAnimationFrame(...)) to advance the animation.
            mSeekState.setPlayTime(playTime, mReversing);
        }
    }

    /**
     * Returns the milliseconds elapsed since the start of the animation.
     *
     * <p>For ongoing animations, this method returns the current progress of the animation in
     * terms of play time. For an animation that has not yet been started: if the animation has been
     * seeked to a certain time via {@link #setCurrentPlayTime(long)}, the seeked play time will
     * be returned; otherwise, this method will return 0.
     *
     * @return the current position in time of the animation in milliseconds
     */
    public long getCurrentPlayTime() {
        if (mSeekState.isActive()) {
            return mSeekState.getPlayTime();
        }
        if (mLastFrameTime == -1) {
            // Not yet started or during start delay
            return 0;
        }
        float durationScale = ValueAnimator.getDurationScale();
        durationScale = durationScale == 0 ? 1 : durationScale;
        if (mReversing) {
            return (long) ((mLastFrameTime - mFirstFrame) / durationScale);
        } else {
            return (long) ((mLastFrameTime - mFirstFrame - mStartDelay) / durationScale);
        }
    }

    private void initChildren() {
        if (!isInitialized()) {
            mChildrenInitialized = true;
            // Forcefully initialize all children based on their end time, so that if the start
            // value of a child is dependent on a previous animation, the animation will be
            // initialized after the the previous animations have been advanced to the end.
            skipToEndValue(false);
        }
    }

    /**
     * @param frameTime The frame start time, in the {@link SystemClock#uptimeMillis()} time
     *                  base.
     * @return
     * @hide
     */
    @Override
    public boolean doAnimationFrame(long frameTime) {
        float durationScale = ValueAnimator.getDurationScale();
        if (durationScale == 0f) {
            // Duration scale is 0, end the animation right away.
            forceToEnd();
            return true;
        }

        // After the first frame comes in, we need to wait for start delay to pass before updating
        // any animation values.
        if (mFirstFrame < 0) {
            mFirstFrame = frameTime;
        }

        // Handle pause/resume
        if (mPaused) {
            // Note: Child animations don't receive pause events. Since it's never a contract that
            // the child animators will be paused when set is paused, this is unlikely to be an
            // issue.
            mPauseTime = frameTime;
            removeAnimationCallback();
            return false;
        } else if (mPauseTime > 0) {
                // Offset by the duration that the animation was paused
            mFirstFrame += (frameTime - mPauseTime);
            mPauseTime = -1;
        }

        // Continue at seeked position
        if (mSeekState.isActive()) {
            mSeekState.updateSeekDirection(mReversing);
            if (mReversing) {
                mFirstFrame = (long) (frameTime - mSeekState.getPlayTime() * durationScale);
            } else {
                mFirstFrame = (long) (frameTime - (mSeekState.getPlayTime() + mStartDelay)
                        * durationScale);
            }
            mSeekState.reset();
        }

        if (!mReversing && frameTime < mFirstFrame + mStartDelay * durationScale) {
            // Still during start delay in a forward playing case.
            return false;
        }

        // From here on, we always use unscaled play time. Note this unscaled playtime includes
        // the start delay.
        long unscaledPlayTime = (long) ((frameTime - mFirstFrame) / durationScale);
        mLastFrameTime = frameTime;

        // 1. Pulse the animators that will start or end in this frame
        // 2. Pulse the animators that will finish in a later frame
        int latestId = findLatestEventIdForTime(unscaledPlayTime);
        int startId = mLastEventId;

        handleAnimationEvents(startId, latestId, unscaledPlayTime);

        mLastEventId = latestId;

        // Pump a frame to the on-going animators
        for (int i = 0; i < mPlayingSet.size(); i++) {
            Node node = mPlayingSet.get(i);
            if (!node.mEnded) {
                pulseFrame(node, getPlayTimeForNode(unscaledPlayTime, node));
            }
        }

        // Remove all the finished anims
        for (int i = mPlayingSet.size() - 1; i >= 0; i--) {
            if (mPlayingSet.get(i).mEnded) {
                mPlayingSet.remove(i);
            }
        }

        boolean finished = false;
        if (mReversing) {
            if (mPlayingSet.size() == 1 && mPlayingSet.get(0) == mRootNode) {
                // The only animation that is running is the delay animation.
                finished = true;
            } else if (mPlayingSet.isEmpty() && mLastEventId < 3) {
                // The only remaining animation is the delay animation
                finished = true;
            }
        } else {
            finished = mPlayingSet.isEmpty() && mLastEventId == mEvents.size() - 1;
        }

        if (finished) {
            endAnimation();
            return true;
        }
        return false;
    }

    /**
     * @hide
     */
    @Override
    public void commitAnimationFrame(long frameTime) {
        // No op.
    }

    @Override
    boolean pulseAnimationFrame(long frameTime) {
        return doAnimationFrame(frameTime);
    }

    /**
     * When playing forward, we call start() at the animation's scheduled start time, and make sure
     * to pump a frame at the animation's scheduled end time.
     *
     * When playing in reverse, we should reverse the animation when we hit animation's end event,
     * and expect the animation to end at the its delay ended event, rather than start event.
     */
    private void handleAnimationEvents(int startId, int latestId, long playTime) {
        if (mReversing) {
            startId = startId == -1 ? mEvents.size() : startId;
            for (int i = startId - 1; i >= latestId; i--) {
                AnimationEvent event = mEvents.get(i);
                Node node = event.mNode;
                if (event.mEvent == AnimationEvent.ANIMATION_END) {
                    if (node.mAnimation.isStarted()) {
                        // If the animation has already been started before its due time (i.e.
                        // the child animator is being manipulated outside of the AnimatorSet), we
                        // need to cancel the animation to reset the internal state (e.g. frame
                        // time tracking) and remove the self pulsing callbacks
                        node.mAnimation.cancel();
                    }
                    node.mEnded = false;
                    mPlayingSet.add(event.mNode);
                    node.mAnimation.startWithoutPulsing(true);
                    pulseFrame(node, 0);
                } else if (event.mEvent == AnimationEvent.ANIMATION_DELAY_ENDED && !node.mEnded) {
                    // end event:
                    pulseFrame(node, getPlayTimeForNode(playTime, node));
                }
            }
        } else {
            for (int i = startId + 1; i <= latestId; i++) {
                AnimationEvent event = mEvents.get(i);
                Node node = event.mNode;
                if (event.mEvent == AnimationEvent.ANIMATION_START) {
                    mPlayingSet.add(event.mNode);
                    if (node.mAnimation.isStarted()) {
                        // If the animation has already been started before its due time (i.e.
                        // the child animator is being manipulated outside of the AnimatorSet), we
                        // need to cancel the animation to reset the internal state (e.g. frame
                        // time tracking) and remove the self pulsing callbacks
                        node.mAnimation.cancel();
                    }
                    node.mEnded = false;
                    node.mAnimation.startWithoutPulsing(false);
                    pulseFrame(node, 0);
                } else if (event.mEvent == AnimationEvent.ANIMATION_END && !node.mEnded) {
                    // start event:
                    pulseFrame(node, getPlayTimeForNode(playTime, node));
                }
            }
        }
    }

    /**
     * This method pulses frames into child animations. It scales the input animation play time
     * with the duration scale and pass that to the child animation via pulseAnimationFrame(long).
     *
     * @param node child animator node
     * @param animPlayTime unscaled play time (including start delay) for the child animator
     */
    private void pulseFrame(Node node, long animPlayTime) {
        if (!node.mEnded) {
            float durationScale = ValueAnimator.getDurationScale();
            durationScale = durationScale == 0  ? 1 : durationScale;
            node.mEnded = node.mAnimation.pulseAnimationFrame(
                    (long) (animPlayTime * durationScale));
        }
    }

    private long getPlayTimeForNode(long overallPlayTime, Node node) {
        return getPlayTimeForNode(overallPlayTime, node, mReversing);
    }

    private long getPlayTimeForNode(long overallPlayTime, Node node, boolean inReverse) {
        if (inReverse) {
            overallPlayTime = getTotalDuration() - overallPlayTime;
            return node.mEndTime - overallPlayTime;
        } else {
            return overallPlayTime - node.mStartTime;
        }
    }

    private void startAnimation() {
        addDummyListener();

        // Register animation callback
        addAnimationCallback(0);

        if (mSeekState.getPlayTimeNormalized() == 0 && mReversing) {
            // Maintain old behavior, if seeked to 0 then call reverse, we'll treat the case
            // the same as no seeking at all.
            mSeekState.reset();
        }
        // Set the child animators to the right end:
        if (mShouldResetValuesAtStart) {
            if (isInitialized()) {
                skipToEndValue(!mReversing);
            } else if (mReversing) {
                // Reversing but haven't initialized all the children yet.
                initChildren();
                skipToEndValue(!mReversing);
            } else {
                // If not all children are initialized and play direction is forward
                for (int i = mEvents.size() - 1; i >= 0; i--) {
                    if (mEvents.get(i).mEvent == AnimationEvent.ANIMATION_DELAY_ENDED) {
                        Animator anim = mEvents.get(i).mNode.mAnimation;
                        // Only reset the animations that have been initialized to start value,
                        // so that if they are defined without a start value, they will get the
                        // values set at the right time (i.e. the next animation run)
                        if (anim.isInitialized()) {
                            anim.skipToEndValue(true);
                        }
                    }
                }
            }
        }

        if (mReversing || mStartDelay == 0 || mSeekState.isActive()) {
            long playTime;
            // If no delay, we need to call start on the first animations to be consistent with old
            // behavior.
            if (mSeekState.isActive()) {
                mSeekState.updateSeekDirection(mReversing);
                playTime = mSeekState.getPlayTime();
            } else {
                playTime = 0;
            }
            int toId = findLatestEventIdForTime(playTime);
            handleAnimationEvents(-1, toId, playTime);
            for (int i = mPlayingSet.size() - 1; i >= 0; i--) {
                if (mPlayingSet.get(i).mEnded) {
                    mPlayingSet.remove(i);
                }
            }
            mLastEventId = toId;
        }
    }

    // This is to work around the issue in b/34736819, as the old behavior in AnimatorSet had
    // masked a real bug in play movies. TODO: remove this and below once the root cause is fixed.
    private void addDummyListener() {
        for (int i = 1; i < mNodes.size(); i++) {
            mNodes.get(i).mAnimation.addListener(mDummyListener);
        }
    }

    private void removeDummyListener() {
        for (int i = 1; i < mNodes.size(); i++) {
            mNodes.get(i).mAnimation.removeListener(mDummyListener);
        }
    }

    private int findLatestEventIdForTime(long currentPlayTime) {
        int size = mEvents.size();
        int latestId = mLastEventId;
        // Call start on the first animations now to be consistent with the old behavior
        if (mReversing) {
            currentPlayTime = getTotalDuration() - currentPlayTime;
            mLastEventId = mLastEventId == -1 ? size : mLastEventId;
            for (int j = mLastEventId - 1; j >= 0; j--) {
                AnimationEvent event = mEvents.get(j);
                if (event.getTime() >= currentPlayTime) {
                    latestId = j;
                }
            }
        } else {
            for (int i = mLastEventId + 1; i < size; i++) {
                AnimationEvent event = mEvents.get(i);
                // TODO: need a function that accounts for infinite duration to compare time
                if (event.getTime() != DURATION_INFINITE && event.getTime() <= currentPlayTime) {
                    latestId = i;
                }
            }
        }
        return latestId;
    }

    private void endAnimation() {
        mStarted = false;
        mLastFrameTime = -1;
        mFirstFrame = -1;
        mLastEventId = -1;
        mPaused = false;
        mPauseTime = -1;
        mSeekState.reset();
        mPlayingSet.clear();

        // No longer receive callbacks
        removeAnimationCallback();
        // Call end listener
        if (mListeners != null) {
            ArrayList<AnimatorListener> tmpListeners =
                    (ArrayList<AnimatorListener>) mListeners.clone();
            int numListeners = tmpListeners.size();
            for (int i = 0; i < numListeners; ++i) {
                tmpListeners.get(i).onAnimationEnd(this, mReversing);
            }
        }
        removeDummyListener();
        mSelfPulse = true;
        mReversing = false;
    }

    private void removeAnimationCallback() {
        if (!mSelfPulse) {
            return;
        }
        AnimationHandler handler = AnimationHandler.getInstance();
        handler.removeCallback(this);
    }

    private void addAnimationCallback(long delay) {
        if (!mSelfPulse) {
            return;
        }
        AnimationHandler handler = AnimationHandler.getInstance();
        handler.addAnimationFrameCallback(this, delay);
    }

    @Override
    public AnimatorSet clone() {
        final AnimatorSet anim = (AnimatorSet) super.clone();
        /*
         * The basic clone() operation copies all items. This doesn't work very well for
         * AnimatorSet, because it will copy references that need to be recreated and state
         * that may not apply. What we need to do now is put the clone in an uninitialized
         * state, with fresh, empty data structures. Then we will build up the nodes list
         * manually, as we clone each Node (and its animation). The clone will then be sorted,
         * and will populate any appropriate lists, when it is started.
         */
        final int nodeCount = mNodes.size();
        anim.mStarted = false;
        anim.mLastFrameTime = -1;
        anim.mFirstFrame = -1;
        anim.mLastEventId = -1;
        anim.mPaused = false;
        anim.mPauseTime = -1;
        anim.mSeekState = new SeekState();
        anim.mSelfPulse = true;
        anim.mPlayingSet = new ArrayList<Node>();
        anim.mNodeMap = new ArrayMap<Animator, Node>();
        anim.mNodes = new ArrayList<Node>(nodeCount);
        anim.mEvents = new ArrayList<AnimationEvent>();
        anim.mDummyListener = new AnimatorListenerAdapter() {
            @Override
            public void onAnimationEnd(Animator animation) {
                if (anim.mNodeMap.get(animation) == null) {
                    throw new AndroidRuntimeException("Error: animation ended is not in the node"
                            + " map");
                }
                anim.mNodeMap.get(animation).mEnded = true;

            }
        };
        anim.mReversing = false;
        anim.mDependencyDirty = true;

        // Walk through the old nodes list, cloning each node and adding it to the new nodemap.
        // One problem is that the old node dependencies point to nodes in the old AnimatorSet.
        // We need to track the old/new nodes in order to reconstruct the dependencies in the clone.

        HashMap<Node, Node> clonesMap = new HashMap<>(nodeCount);
        for (int n = 0; n < nodeCount; n++) {
            final Node node = mNodes.get(n);
            Node nodeClone = node.clone();
            // Remove the old internal listener from the cloned child
            nodeClone.mAnimation.removeListener(mDummyListener);
            clonesMap.put(node, nodeClone);
            anim.mNodes.add(nodeClone);
            anim.mNodeMap.put(nodeClone.mAnimation, nodeClone);
        }

        anim.mRootNode = clonesMap.get(mRootNode);
        anim.mDelayAnim = (ValueAnimator) anim.mRootNode.mAnimation;

        // Now that we've cloned all of the nodes, we're ready to walk through their
        // dependencies, mapping the old dependencies to the new nodes
        for (int i = 0; i < nodeCount; i++) {
            Node node = mNodes.get(i);
            // Update dependencies for node's clone
            Node nodeClone = clonesMap.get(node);
            nodeClone.mLatestParent = node.mLatestParent == null
                    ? null : clonesMap.get(node.mLatestParent);
            int size = node.mChildNodes == null ? 0 : node.mChildNodes.size();
            for (int j = 0; j < size; j++) {
                nodeClone.mChildNodes.set(j, clonesMap.get(node.mChildNodes.get(j)));
            }
            size = node.mSiblings == null ? 0 : node.mSiblings.size();
            for (int j = 0; j < size; j++) {
                nodeClone.mSiblings.set(j, clonesMap.get(node.mSiblings.get(j)));
            }
            size = node.mParents == null ? 0 : node.mParents.size();
            for (int j = 0; j < size; j++) {
                nodeClone.mParents.set(j, clonesMap.get(node.mParents.get(j)));
            }
        }
        return anim;
    }


    /**
     * AnimatorSet is only reversible when the set contains no sequential animation, and no child
     * animators have a start delay.
     * @hide
     */
    @Override
    public boolean canReverse() {
        return getTotalDuration() != DURATION_INFINITE;
    }

    /**
     * Plays the AnimatorSet in reverse. If the animation has been seeked to a specific play time
     * using {@link #setCurrentPlayTime(long)}, it will play backwards from the point seeked when
     * reverse was called. Otherwise, then it will start from the end and play backwards. This
     * behavior is only set for the current animation; future playing of the animation will use the
     * default behavior of playing forward.
     * <p>
     * Note: reverse is not supported for infinite AnimatorSet.
     */
    @Override
    public void reverse() {
        start(true, true);
    }

    @Override
    public String toString() {
        String returnVal = "AnimatorSet@" + Integer.toHexString(hashCode()) + "{";
        int size = mNodes.size();
        for (int i = 0; i < size; i++) {
            Node node = mNodes.get(i);
            returnVal += "\n    " + node.mAnimation.toString();
        }
        return returnVal + "\n}";
    }

    private void printChildCount() {
        // Print out the child count through a level traverse.
        ArrayList<Node> list = new ArrayList<>(mNodes.size());
        list.add(mRootNode);
        Log.d(TAG, "Current tree: ");
        int index = 0;
        while (index < list.size()) {
            int listSize = list.size();
            StringBuilder builder = new StringBuilder();
            for (; index < listSize; index++) {
                Node node = list.get(index);
                int num = 0;
                if (node.mChildNodes != null) {
                    for (int i = 0; i < node.mChildNodes.size(); i++) {
                        Node child = node.mChildNodes.get(i);
                        if (child.mLatestParent == node) {
                            num++;
                            list.add(child);
                        }
                    }
                }
                builder.append(" ");
                builder.append(num);
            }
            Log.d(TAG, builder.toString());
        }
    }

    private void createDependencyGraph() {
        if (!mDependencyDirty) {
            // Check whether any duration of the child animations has changed
            boolean durationChanged = false;
            for (int i = 0; i < mNodes.size(); i++) {
                Animator anim = mNodes.get(i).mAnimation;
                if (mNodes.get(i).mTotalDuration != anim.getTotalDuration()) {
                    durationChanged = true;
                    break;
                }
            }
            if (!durationChanged) {
                return;
            }
        }

        mDependencyDirty = false;
        // Traverse all the siblings and make sure they have all the parents
        int size = mNodes.size();
        for (int i = 0; i < size; i++) {
            mNodes.get(i).mParentsAdded = false;
        }
        for (int i = 0; i < size; i++) {
            Node node = mNodes.get(i);
            if (node.mParentsAdded) {
                continue;
            }

            node.mParentsAdded = true;
            if (node.mSiblings == null) {
                continue;
            }

            // Find all the siblings
            findSiblings(node, node.mSiblings);
            node.mSiblings.remove(node);

            // Get parents from all siblings
            int siblingSize = node.mSiblings.size();
            for (int j = 0; j < siblingSize; j++) {
                node.addParents(node.mSiblings.get(j).mParents);
            }

            // Now make sure all siblings share the same set of parents
            for (int j = 0; j < siblingSize; j++) {
                Node sibling = node.mSiblings.get(j);
                sibling.addParents(node.mParents);
                sibling.mParentsAdded = true;
            }
        }

        for (int i = 0; i < size; i++) {
            Node node = mNodes.get(i);
            if (node != mRootNode && node.mParents == null) {
                node.addParent(mRootNode);
            }
        }

        // Do a DFS on the tree
        ArrayList<Node> visited = new ArrayList<Node>(mNodes.size());
        // Assign start/end time
        mRootNode.mStartTime = 0;
        mRootNode.mEndTime = mDelayAnim.getDuration();
        updatePlayTime(mRootNode, visited);

        sortAnimationEvents();
        mTotalDuration = mEvents.get(mEvents.size() - 1).getTime();
    }

    private void sortAnimationEvents() {
        // Sort the list of events in ascending order of their time
        // Create the list including the delay animation.
        mEvents.clear();
        for (int i = 1; i < mNodes.size(); i++) {
            Node node = mNodes.get(i);
            mEvents.add(new AnimationEvent(node, AnimationEvent.ANIMATION_START));
            mEvents.add(new AnimationEvent(node, AnimationEvent.ANIMATION_DELAY_ENDED));
            mEvents.add(new AnimationEvent(node, AnimationEvent.ANIMATION_END));
        }
        mEvents.sort(new Comparator<AnimationEvent>() {
            @Override
            public int compare(AnimationEvent e1, AnimationEvent e2) {
                long t1 = e1.getTime();
                long t2 = e2.getTime();
                if (t1 == t2) {
                    // For events that happen at the same time, we need them to be in the sequence
                    // (end, start, start delay ended)
                    if (e2.mEvent + e1.mEvent == AnimationEvent.ANIMATION_START
                            + AnimationEvent.ANIMATION_DELAY_ENDED) {
                        // Ensure start delay happens after start
                        return e1.mEvent - e2.mEvent;
                    } else {
                        return e2.mEvent - e1.mEvent;
                    }
                }
                if (t2 == DURATION_INFINITE) {
                    return -1;
                }
                if (t1 == DURATION_INFINITE) {
                    return 1;
                }
                // When neither event happens at INFINITE time:
                return (int) (t1 - t2);
            }
        });

        int eventSize = mEvents.size();
        // For the same animation, start event has to happen before end.
        for (int i = 0; i < eventSize;) {
            AnimationEvent event = mEvents.get(i);
            if (event.mEvent == AnimationEvent.ANIMATION_END) {
                boolean needToSwapStart;
                if (event.mNode.mStartTime == event.mNode.mEndTime) {
                    needToSwapStart = true;
                } else if (event.mNode.mEndTime == event.mNode.mStartTime
                        + event.mNode.mAnimation.getStartDelay()) {
                    // Swapping start delay
                    needToSwapStart = false;
                } else {
                    i++;
                    continue;
                }

                int startEventId = eventSize;
                int startDelayEndId = eventSize;
                for (int j = i + 1; j < eventSize; j++) {
                    if (startEventId < eventSize && startDelayEndId < eventSize) {
                        break;
                    }
                    if (mEvents.get(j).mNode == event.mNode) {
                        if (mEvents.get(j).mEvent == AnimationEvent.ANIMATION_START) {
                            // Found start event
                            startEventId = j;
                        } else if (mEvents.get(j).mEvent == AnimationEvent.ANIMATION_DELAY_ENDED) {
                            startDelayEndId = j;
                        }
                    }

                }
                if (needToSwapStart && startEventId == mEvents.size()) {
                    throw new UnsupportedOperationException("Something went wrong, no start is"
                            + "found after stop for an animation that has the same start and end"
                            + "time.");

                }
                if (startDelayEndId == mEvents.size()) {
                    throw new UnsupportedOperationException("Something went wrong, no start"
                            + "delay end is found after stop for an animation");

                }

                // We need to make sure start is inserted before start delay ended event,
                // because otherwise inserting start delay ended events first would change
                // the start event index.
                if (needToSwapStart) {
                    AnimationEvent startEvent = mEvents.remove(startEventId);
                    mEvents.add(i, startEvent);
                    i++;
                }

                AnimationEvent startDelayEndEvent = mEvents.remove(startDelayEndId);
                mEvents.add(i, startDelayEndEvent);
                i += 2;
            } else {
                i++;
            }
        }

        if (!mEvents.isEmpty() && mEvents.get(0).mEvent != AnimationEvent.ANIMATION_START) {
            throw new UnsupportedOperationException(
                    "Sorting went bad, the start event should always be at index 0");
        }

        // Add AnimatorSet's start delay node to the beginning
        mEvents.add(0, new AnimationEvent(mRootNode, AnimationEvent.ANIMATION_START));
        mEvents.add(1, new AnimationEvent(mRootNode, AnimationEvent.ANIMATION_DELAY_ENDED));
        mEvents.add(2, new AnimationEvent(mRootNode, AnimationEvent.ANIMATION_END));

        if (mEvents.get(mEvents.size() - 1).mEvent == AnimationEvent.ANIMATION_START
                || mEvents.get(mEvents.size() - 1).mEvent == AnimationEvent.ANIMATION_DELAY_ENDED) {
            throw new UnsupportedOperationException(
                    "Something went wrong, the last event is not an end event");
        }
    }

    /**
     * Based on parent's start/end time, calculate children's start/end time. If cycle exists in
     * the graph, all the nodes on the cycle will be marked to start at {@link #DURATION_INFINITE},
     * meaning they will ever play.
     */
    private void updatePlayTime(Node parent,  ArrayList<Node> visited) {
        if (parent.mChildNodes == null) {
            if (parent == mRootNode) {
                // All the animators are in a cycle
                for (int i = 0; i < mNodes.size(); i++) {
                    Node node = mNodes.get(i);
                    if (node != mRootNode) {
                        node.mStartTime = DURATION_INFINITE;
                        node.mEndTime = DURATION_INFINITE;
                    }
                }
            }
            return;
        }

        visited.add(parent);
        int childrenSize = parent.mChildNodes.size();
        for (int i = 0; i < childrenSize; i++) {
            Node child = parent.mChildNodes.get(i);
            child.mTotalDuration = child.mAnimation.getTotalDuration();  // Update cached duration.

            int index = visited.indexOf(child);
            if (index >= 0) {
                // Child has been visited, cycle found. Mark all the nodes in the cycle.
                for (int j = index; j < visited.size(); j++) {
                    visited.get(j).mLatestParent = null;
                    visited.get(j).mStartTime = DURATION_INFINITE;
                    visited.get(j).mEndTime = DURATION_INFINITE;
                }
                child.mStartTime = DURATION_INFINITE;
                child.mEndTime = DURATION_INFINITE;
                child.mLatestParent = null;
                Log.w(TAG, "Cycle found in AnimatorSet: " + this);
                continue;
            }

            if (child.mStartTime != DURATION_INFINITE) {
                if (parent.mEndTime == DURATION_INFINITE) {
                    child.mLatestParent = parent;
                    child.mStartTime = DURATION_INFINITE;
                    child.mEndTime = DURATION_INFINITE;
                } else {
                    if (parent.mEndTime >= child.mStartTime) {
                        child.mLatestParent = parent;
                        child.mStartTime = parent.mEndTime;
                    }

                    child.mEndTime = child.mTotalDuration == DURATION_INFINITE
                            ? DURATION_INFINITE : child.mStartTime + child.mTotalDuration;
                }
            }
            updatePlayTime(child, visited);
        }
        visited.remove(parent);
    }

    // Recursively find all the siblings
    private void findSiblings(Node node, ArrayList<Node> siblings) {
        if (!siblings.contains(node)) {
            siblings.add(node);
            if (node.mSiblings == null) {
                return;
            }
            for (int i = 0; i < node.mSiblings.size(); i++) {
                findSiblings(node.mSiblings.get(i), siblings);
            }
        }
    }

    /**
     * @hide
     * TODO: For animatorSet defined in XML, we can use a flag to indicate what the play order
     * if defined (i.e. sequential or together), then we can use the flag instead of calculating
     * dynamically. Note that when AnimatorSet is empty this method returns true.
     * @return whether all the animators in the set are supposed to play together
     */
    public boolean shouldPlayTogether() {
        updateAnimatorsDuration();
        createDependencyGraph();
        // All the child nodes are set out to play right after the delay animation
        return mRootNode.mChildNodes == null || mRootNode.mChildNodes.size() == mNodes.size() - 1;
    }

    @Override
    public long getTotalDuration() {
        updateAnimatorsDuration();
        createDependencyGraph();
        return mTotalDuration;
    }

    private Node getNodeForAnimation(Animator anim) {
        Node node = mNodeMap.get(anim);
        if (node == null) {
            node = new Node(anim);
            mNodeMap.put(anim, node);
            mNodes.add(node);
        }
        return node;
    }

    /**
     * A Node is an embodiment of both the Animator that it wraps as well as
     * any dependencies that are associated with that Animation. This includes
     * both dependencies upon other nodes (in the dependencies list) as
     * well as dependencies of other nodes upon this (in the nodeDependents list).
     */
    private static class Node implements Cloneable {
        Animator mAnimation;

        /**
         * Child nodes are the nodes associated with animations that will be played immediately
         * after current node.
         */
        ArrayList<Node> mChildNodes = null;

        /**
         * Flag indicating whether the animation in this node is finished. This flag
         * is used by AnimatorSet to check, as each animation ends, whether all child animations
         * are mEnded and it's time to send out an end event for the entire AnimatorSet.
         */
        boolean mEnded = false;

        /**
         * Nodes with animations that are defined to play simultaneously with the animation
         * associated with this current node.
         */
        ArrayList<Node> mSiblings;

        /**
         * Parent nodes are the nodes with animations preceding current node's animation. Parent
         * nodes here are derived from user defined animation sequence.
         */
        ArrayList<Node> mParents;

        /**
         * Latest parent is the parent node associated with a animation that finishes after all
         * the other parents' animations.
         */
        Node mLatestParent = null;

        boolean mParentsAdded = false;
        long mStartTime = 0;
        long mEndTime = 0;
        long mTotalDuration = 0;

        /**
         * Constructs the Node with the animation that it encapsulates. A Node has no
         * dependencies by default; dependencies are added via the addDependency()
         * method.
         *
         * @param animation The animation that the Node encapsulates.
         */
        public Node(Animator animation) {
            this.mAnimation = animation;
        }

        @Override
        public Node clone() {
            try {
                Node node = (Node) super.clone();
                node.mAnimation = mAnimation.clone();
                if (mChildNodes != null) {
                    node.mChildNodes = new ArrayList<>(mChildNodes);
                }
                if (mSiblings != null) {
                    node.mSiblings = new ArrayList<>(mSiblings);
                }
                if (mParents != null) {
                    node.mParents = new ArrayList<>(mParents);
                }
                node.mEnded = false;
                return node;
            } catch (CloneNotSupportedException e) {
               throw new AssertionError();
            }
        }

        void addChild(Node node) {
            if (mChildNodes == null) {
                mChildNodes = new ArrayList<>();
            }
            if (!mChildNodes.contains(node)) {
                mChildNodes.add(node);
                node.addParent(this);
            }
        }

        public void addSibling(Node node) {
            if (mSiblings == null) {
                mSiblings = new ArrayList<Node>();
            }
            if (!mSiblings.contains(node)) {
                mSiblings.add(node);
                node.addSibling(this);
            }
        }

        public void addParent(Node node) {
            if (mParents == null) {
                mParents =  new ArrayList<Node>();
            }
            if (!mParents.contains(node)) {
                mParents.add(node);
                node.addChild(this);
            }
        }

        public void addParents(ArrayList<Node> parents) {
            if (parents == null) {
                return;
            }
            int size = parents.size();
            for (int i = 0; i < size; i++) {
                addParent(parents.get(i));
            }
        }
    }

    /**
     * This class is a wrapper around a node and an event for the animation corresponding to the
     * node. The 3 types of events represent the start of an animation, the end of a start delay of
     * an animation, and the end of an animation. When playing forward (i.e. in the non-reverse
     * direction), start event marks when start() should be called, and end event corresponds to
     * when the animation should finish. When playing in reverse, start delay will not be a part
     * of the animation. Therefore, reverse() is called at the end event, and animation should end
     * at the delay ended event.
     */
    private static class AnimationEvent {
        static final int ANIMATION_START = 0;
        static final int ANIMATION_DELAY_ENDED = 1;
        static final int ANIMATION_END = 2;
        final Node mNode;
        final int mEvent;

        AnimationEvent(Node node, int event) {
            mNode = node;
            mEvent = event;
        }

        long getTime() {
            if (mEvent == ANIMATION_START) {
                return mNode.mStartTime;
            } else if (mEvent == ANIMATION_DELAY_ENDED) {
                return mNode.mStartTime == DURATION_INFINITE
                        ? DURATION_INFINITE : mNode.mStartTime + mNode.mAnimation.getStartDelay();
            } else {
                return mNode.mEndTime;
            }
        }

        public String toString() {
            String eventStr = mEvent == ANIMATION_START ? "start" : (
                    mEvent == ANIMATION_DELAY_ENDED ? "delay ended" : "end");
            return eventStr + " " + mNode.mAnimation.toString();
        }
    }

    private class SeekState {
        private long mPlayTime = -1;
        private boolean mSeekingInReverse = false;
        void reset() {
            mPlayTime = -1;
            mSeekingInReverse = false;
        }

        void setPlayTime(long playTime, boolean inReverse) {
            // TODO: This can be simplified.

            // Clamp the play time
            if (getTotalDuration() != DURATION_INFINITE) {
                mPlayTime = Math.min(playTime, getTotalDuration() - mStartDelay);
            }
            mPlayTime = Math.max(0, mPlayTime);
            mSeekingInReverse = inReverse;
        }

        void updateSeekDirection(boolean inReverse) {
            // Change seek direction without changing the overall fraction
            if (inReverse && getTotalDuration() == DURATION_INFINITE) {
                throw new UnsupportedOperationException("Error: Cannot reverse infinite animator"
                        + " set");
            }
            if (mPlayTime >= 0) {
                if (inReverse != mSeekingInReverse) {
                    mPlayTime = getTotalDuration() - mStartDelay - mPlayTime;
                    mSeekingInReverse = inReverse;
                }
            }
        }

        long getPlayTime() {
            return mPlayTime;
        }

        /**
         * Returns the playtime assuming the animation is forward playing
         */
        long getPlayTimeNormalized() {
            if (mReversing) {
                return getTotalDuration() - mStartDelay - mPlayTime;
            }
            return mPlayTime;
        }

        boolean isActive() {
            return mPlayTime != -1;
        }
    }

    /**
     * The <code>Builder</code> object is a utility class to facilitate adding animations to a
     * <code>AnimatorSet</code> along with the relationships between the various animations. The
     * intention of the <code>Builder</code> methods, along with the {@link
     * AnimatorSet#play(Animator) play()} method of <code>AnimatorSet</code> is to make it possible
     * to express the dependency relationships of animations in a natural way. Developers can also
     * use the {@link AnimatorSet#playTogether(Animator[]) playTogether()} and {@link
     * AnimatorSet#playSequentially(Animator[]) playSequentially()} methods if these suit the need,
     * but it might be easier in some situations to express the AnimatorSet of animations in pairs.
     * <p/>
     * <p>The <code>Builder</code> object cannot be constructed directly, but is rather constructed
     * internally via a call to {@link AnimatorSet#play(Animator)}.</p>
     * <p/>
     * <p>For example, this sets up a AnimatorSet to play anim1 and anim2 at the same time, anim3 to
     * play when anim2 finishes, and anim4 to play when anim3 finishes:</p>
     * <pre>
     *     AnimatorSet s = new AnimatorSet();
     *     s.play(anim1).with(anim2);
     *     s.play(anim2).before(anim3);
     *     s.play(anim4).after(anim3);
     * </pre>
     * <p/>
     * <p>Note in the example that both {@link Builder#before(Animator)} and {@link
     * Builder#after(Animator)} are used. These are just different ways of expressing the same
     * relationship and are provided to make it easier to say things in a way that is more natural,
     * depending on the situation.</p>
     * <p/>
     * <p>It is possible to make several calls into the same <code>Builder</code> object to express
     * multiple relationships. However, note that it is only the animation passed into the initial
     * {@link AnimatorSet#play(Animator)} method that is the dependency in any of the successive
     * calls to the <code>Builder</code> object. For example, the following code starts both anim2
     * and anim3 when anim1 ends; there is no direct dependency relationship between anim2 and
     * anim3:
     * <pre>
     *   AnimatorSet s = new AnimatorSet();
     *   s.play(anim1).before(anim2).before(anim3);
     * </pre>
     * If the desired result is to play anim1 then anim2 then anim3, this code expresses the
     * relationship correctly:</p>
     * <pre>
     *   AnimatorSet s = new AnimatorSet();
     *   s.play(anim1).before(anim2);
     *   s.play(anim2).before(anim3);
     * </pre>
     * <p/>
     * <p>Note that it is possible to express relationships that cannot be resolved and will not
     * result in sensible results. For example, <code>play(anim1).after(anim1)</code> makes no
     * sense. In general, circular dependencies like this one (or more indirect ones where a depends
     * on b, which depends on c, which depends on a) should be avoided. Only create AnimatorSets
     * that can boil down to a simple, one-way relationship of animations starting with, before, and
     * after other, different, animations.</p>
     */
    public class Builder {

        /**
         * This tracks the current node being processed. It is supplied to the play() method
         * of AnimatorSet and passed into the constructor of Builder.
         */
        private Node mCurrentNode;

        /**
         * package-private constructor. Builders are only constructed by AnimatorSet, when the
         * play() method is called.
         *
         * @param anim The animation that is the dependency for the other animations passed into
         * the other methods of this Builder object.
         */
        Builder(Animator anim) {
            mDependencyDirty = true;
            mCurrentNode = getNodeForAnimation(anim);
        }

        /**
         * Sets up the given animation to play at the same time as the animation supplied in the
         * {@link AnimatorSet#play(Animator)} call that created this <code>Builder</code> object.
         *
         * @param anim The animation that will play when the animation supplied to the
         * {@link AnimatorSet#play(Animator)} method starts.
         */
        public Builder with(Animator anim) {
            Node node = getNodeForAnimation(anim);
            mCurrentNode.addSibling(node);
            return this;
        }

        /**
         * Sets up the given animation to play when the animation supplied in the
         * {@link AnimatorSet#play(Animator)} call that created this <code>Builder</code> object
         * ends.
         *
         * @param anim The animation that will play when the animation supplied to the
         * {@link AnimatorSet#play(Animator)} method ends.
         */
        public Builder before(Animator anim) {
            Node node = getNodeForAnimation(anim);
            mCurrentNode.addChild(node);
            return this;
        }

        /**
         * Sets up the given animation to play when the animation supplied in the
         * {@link AnimatorSet#play(Animator)} call that created this <code>Builder</code> object
         * to start when the animation supplied in this method call ends.
         *
         * @param anim The animation whose end will cause the animation supplied to the
         * {@link AnimatorSet#play(Animator)} method to play.
         */
        public Builder after(Animator anim) {
            Node node = getNodeForAnimation(anim);
            mCurrentNode.addParent(node);
            return this;
        }

        /**
         * Sets up the animation supplied in the
         * {@link AnimatorSet#play(Animator)} call that created this <code>Builder</code> object
         * to play when the given amount of time elapses.
         *
         * @param delay The number of milliseconds that should elapse before the
         * animation starts.
         */
        public Builder after(long delay) {
            // setup dummy ValueAnimator just to run the clock
            ValueAnimator anim = ValueAnimator.ofFloat(0f, 1f);
            anim.setDuration(delay);
            after(anim);
            return this;
        }

    }

}