1/*
2 * Copyright (C) 2010 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 *      http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17package android.app;
18
19import com.android.internal.util.FastPrintWriter;
20
21import android.graphics.Rect;
22import android.os.Parcel;
23import android.os.Parcelable;
24import android.text.TextUtils;
25import android.transition.Transition;
26import android.transition.TransitionManager;
27import android.transition.TransitionSet;
28import android.util.ArrayMap;
29import android.util.Log;
30import android.util.LogWriter;
31import android.util.SparseArray;
32import android.view.View;
33import android.view.ViewGroup;
34import android.view.ViewTreeObserver;
35
36import java.io.FileDescriptor;
37import java.io.PrintWriter;
38import java.util.ArrayList;
39import java.util.List;
40
41final class BackStackState implements Parcelable {
42    final int[] mOps;
43    final int mTransition;
44    final int mTransitionStyle;
45    final String mName;
46    final int mIndex;
47    final int mBreadCrumbTitleRes;
48    final CharSequence mBreadCrumbTitleText;
49    final int mBreadCrumbShortTitleRes;
50    final CharSequence mBreadCrumbShortTitleText;
51    final ArrayList<String> mSharedElementSourceNames;
52    final ArrayList<String> mSharedElementTargetNames;
53
54    public BackStackState(FragmentManagerImpl fm, BackStackRecord bse) {
55        int numRemoved = 0;
56        BackStackRecord.Op op = bse.mHead;
57        while (op != null) {
58            if (op.removed != null) {
59                numRemoved += op.removed.size();
60            }
61            op = op.next;
62        }
63        mOps = new int[bse.mNumOp * 7 + numRemoved];
64
65        if (!bse.mAddToBackStack) {
66            throw new IllegalStateException("Not on back stack");
67        }
68
69        op = bse.mHead;
70        int pos = 0;
71        while (op != null) {
72            mOps[pos++] = op.cmd;
73            mOps[pos++] = op.fragment != null ? op.fragment.mIndex : -1;
74            mOps[pos++] = op.enterAnim;
75            mOps[pos++] = op.exitAnim;
76            mOps[pos++] = op.popEnterAnim;
77            mOps[pos++] = op.popExitAnim;
78            if (op.removed != null) {
79                final int N = op.removed.size();
80                mOps[pos++] = N;
81                for (int i = 0; i < N; i++) {
82                    mOps[pos++] = op.removed.get(i).mIndex;
83                }
84            } else {
85                mOps[pos++] = 0;
86            }
87            op = op.next;
88        }
89        mTransition = bse.mTransition;
90        mTransitionStyle = bse.mTransitionStyle;
91        mName = bse.mName;
92        mIndex = bse.mIndex;
93        mBreadCrumbTitleRes = bse.mBreadCrumbTitleRes;
94        mBreadCrumbTitleText = bse.mBreadCrumbTitleText;
95        mBreadCrumbShortTitleRes = bse.mBreadCrumbShortTitleRes;
96        mBreadCrumbShortTitleText = bse.mBreadCrumbShortTitleText;
97        mSharedElementSourceNames = bse.mSharedElementSourceNames;
98        mSharedElementTargetNames = bse.mSharedElementTargetNames;
99    }
100
101    public BackStackState(Parcel in) {
102        mOps = in.createIntArray();
103        mTransition = in.readInt();
104        mTransitionStyle = in.readInt();
105        mName = in.readString();
106        mIndex = in.readInt();
107        mBreadCrumbTitleRes = in.readInt();
108        mBreadCrumbTitleText = TextUtils.CHAR_SEQUENCE_CREATOR.createFromParcel(in);
109        mBreadCrumbShortTitleRes = in.readInt();
110        mBreadCrumbShortTitleText = TextUtils.CHAR_SEQUENCE_CREATOR.createFromParcel(in);
111        mSharedElementSourceNames = in.createStringArrayList();
112        mSharedElementTargetNames = in.createStringArrayList();
113    }
114
115    public BackStackRecord instantiate(FragmentManagerImpl fm) {
116        BackStackRecord bse = new BackStackRecord(fm);
117        int pos = 0;
118        int num = 0;
119        while (pos < mOps.length) {
120            BackStackRecord.Op op = new BackStackRecord.Op();
121            op.cmd = mOps[pos++];
122            if (FragmentManagerImpl.DEBUG) {
123                Log.v(FragmentManagerImpl.TAG,
124                        "Instantiate " + bse + " op #" + num + " base fragment #" + mOps[pos]);
125            }
126            int findex = mOps[pos++];
127            if (findex >= 0) {
128                Fragment f = fm.mActive.get(findex);
129                op.fragment = f;
130            } else {
131                op.fragment = null;
132            }
133            op.enterAnim = mOps[pos++];
134            op.exitAnim = mOps[pos++];
135            op.popEnterAnim = mOps[pos++];
136            op.popExitAnim = mOps[pos++];
137            final int N = mOps[pos++];
138            if (N > 0) {
139                op.removed = new ArrayList<Fragment>(N);
140                for (int i = 0; i < N; i++) {
141                    if (FragmentManagerImpl.DEBUG) {
142                        Log.v(FragmentManagerImpl.TAG,
143                                "Instantiate " + bse + " set remove fragment #" + mOps[pos]);
144                    }
145                    Fragment r = fm.mActive.get(mOps[pos++]);
146                    op.removed.add(r);
147                }
148            }
149            bse.addOp(op);
150            num++;
151        }
152        bse.mTransition = mTransition;
153        bse.mTransitionStyle = mTransitionStyle;
154        bse.mName = mName;
155        bse.mIndex = mIndex;
156        bse.mAddToBackStack = true;
157        bse.mBreadCrumbTitleRes = mBreadCrumbTitleRes;
158        bse.mBreadCrumbTitleText = mBreadCrumbTitleText;
159        bse.mBreadCrumbShortTitleRes = mBreadCrumbShortTitleRes;
160        bse.mBreadCrumbShortTitleText = mBreadCrumbShortTitleText;
161        bse.mSharedElementSourceNames = mSharedElementSourceNames;
162        bse.mSharedElementTargetNames = mSharedElementTargetNames;
163        bse.bumpBackStackNesting(1);
164        return bse;
165    }
166
167    public int describeContents() {
168        return 0;
169    }
170
171    public void writeToParcel(Parcel dest, int flags) {
172        dest.writeIntArray(mOps);
173        dest.writeInt(mTransition);
174        dest.writeInt(mTransitionStyle);
175        dest.writeString(mName);
176        dest.writeInt(mIndex);
177        dest.writeInt(mBreadCrumbTitleRes);
178        TextUtils.writeToParcel(mBreadCrumbTitleText, dest, 0);
179        dest.writeInt(mBreadCrumbShortTitleRes);
180        TextUtils.writeToParcel(mBreadCrumbShortTitleText, dest, 0);
181        dest.writeStringList(mSharedElementSourceNames);
182        dest.writeStringList(mSharedElementTargetNames);
183    }
184
185    public static final Parcelable.Creator<BackStackState> CREATOR
186            = new Parcelable.Creator<BackStackState>() {
187        public BackStackState createFromParcel(Parcel in) {
188            return new BackStackState(in);
189        }
190
191        public BackStackState[] newArray(int size) {
192            return new BackStackState[size];
193        }
194    };
195}
196
197/**
198 * @hide Entry of an operation on the fragment back stack.
199 */
200final class BackStackRecord extends FragmentTransaction implements
201        FragmentManager.BackStackEntry, Runnable {
202    static final String TAG = FragmentManagerImpl.TAG;
203
204    final FragmentManagerImpl mManager;
205
206    static final int OP_NULL = 0;
207    static final int OP_ADD = 1;
208    static final int OP_REPLACE = 2;
209    static final int OP_REMOVE = 3;
210    static final int OP_HIDE = 4;
211    static final int OP_SHOW = 5;
212    static final int OP_DETACH = 6;
213    static final int OP_ATTACH = 7;
214
215    static final class Op {
216        Op next;
217        Op prev;
218        int cmd;
219        Fragment fragment;
220        int enterAnim;
221        int exitAnim;
222        int popEnterAnim;
223        int popExitAnim;
224        ArrayList<Fragment> removed;
225    }
226
227    Op mHead;
228    Op mTail;
229    int mNumOp;
230    int mEnterAnim;
231    int mExitAnim;
232    int mPopEnterAnim;
233    int mPopExitAnim;
234    int mTransition;
235    int mTransitionStyle;
236    boolean mAddToBackStack;
237    boolean mAllowAddToBackStack = true;
238    String mName;
239    boolean mCommitted;
240    int mIndex = -1;
241
242    int mBreadCrumbTitleRes;
243    CharSequence mBreadCrumbTitleText;
244    int mBreadCrumbShortTitleRes;
245    CharSequence mBreadCrumbShortTitleText;
246
247    ArrayList<String> mSharedElementSourceNames;
248    ArrayList<String> mSharedElementTargetNames;
249
250    @Override
251    public String toString() {
252        StringBuilder sb = new StringBuilder(128);
253        sb.append("BackStackEntry{");
254        sb.append(Integer.toHexString(System.identityHashCode(this)));
255        if (mIndex >= 0) {
256            sb.append(" #");
257            sb.append(mIndex);
258        }
259        if (mName != null) {
260            sb.append(" ");
261            sb.append(mName);
262        }
263        sb.append("}");
264        return sb.toString();
265    }
266
267    public void dump(String prefix, FileDescriptor fd, PrintWriter writer, String[] args) {
268        dump(prefix, writer, true);
269    }
270
271    void dump(String prefix, PrintWriter writer, boolean full) {
272        if (full) {
273            writer.print(prefix);
274            writer.print("mName=");
275            writer.print(mName);
276            writer.print(" mIndex=");
277            writer.print(mIndex);
278            writer.print(" mCommitted=");
279            writer.println(mCommitted);
280            if (mTransition != FragmentTransaction.TRANSIT_NONE) {
281                writer.print(prefix);
282                writer.print("mTransition=#");
283                writer.print(Integer.toHexString(mTransition));
284                writer.print(" mTransitionStyle=#");
285                writer.println(Integer.toHexString(mTransitionStyle));
286            }
287            if (mEnterAnim != 0 || mExitAnim != 0) {
288                writer.print(prefix);
289                writer.print("mEnterAnim=#");
290                writer.print(Integer.toHexString(mEnterAnim));
291                writer.print(" mExitAnim=#");
292                writer.println(Integer.toHexString(mExitAnim));
293            }
294            if (mPopEnterAnim != 0 || mPopExitAnim != 0) {
295                writer.print(prefix);
296                writer.print("mPopEnterAnim=#");
297                writer.print(Integer.toHexString(mPopEnterAnim));
298                writer.print(" mPopExitAnim=#");
299                writer.println(Integer.toHexString(mPopExitAnim));
300            }
301            if (mBreadCrumbTitleRes != 0 || mBreadCrumbTitleText != null) {
302                writer.print(prefix);
303                writer.print("mBreadCrumbTitleRes=#");
304                writer.print(Integer.toHexString(mBreadCrumbTitleRes));
305                writer.print(" mBreadCrumbTitleText=");
306                writer.println(mBreadCrumbTitleText);
307            }
308            if (mBreadCrumbShortTitleRes != 0 || mBreadCrumbShortTitleText != null) {
309                writer.print(prefix);
310                writer.print("mBreadCrumbShortTitleRes=#");
311                writer.print(Integer.toHexString(mBreadCrumbShortTitleRes));
312                writer.print(" mBreadCrumbShortTitleText=");
313                writer.println(mBreadCrumbShortTitleText);
314            }
315        }
316
317        if (mHead != null) {
318            writer.print(prefix);
319            writer.println("Operations:");
320            String innerPrefix = prefix + "    ";
321            Op op = mHead;
322            int num = 0;
323            while (op != null) {
324                String cmdStr;
325                switch (op.cmd) {
326                    case OP_NULL:
327                        cmdStr = "NULL";
328                        break;
329                    case OP_ADD:
330                        cmdStr = "ADD";
331                        break;
332                    case OP_REPLACE:
333                        cmdStr = "REPLACE";
334                        break;
335                    case OP_REMOVE:
336                        cmdStr = "REMOVE";
337                        break;
338                    case OP_HIDE:
339                        cmdStr = "HIDE";
340                        break;
341                    case OP_SHOW:
342                        cmdStr = "SHOW";
343                        break;
344                    case OP_DETACH:
345                        cmdStr = "DETACH";
346                        break;
347                    case OP_ATTACH:
348                        cmdStr = "ATTACH";
349                        break;
350                    default:
351                        cmdStr = "cmd=" + op.cmd;
352                        break;
353                }
354                writer.print(prefix);
355                writer.print("  Op #");
356                writer.print(num);
357                writer.print(": ");
358                writer.print(cmdStr);
359                writer.print(" ");
360                writer.println(op.fragment);
361                if (full) {
362                    if (op.enterAnim != 0 || op.exitAnim != 0) {
363                        writer.print(innerPrefix);
364                        writer.print("enterAnim=#");
365                        writer.print(Integer.toHexString(op.enterAnim));
366                        writer.print(" exitAnim=#");
367                        writer.println(Integer.toHexString(op.exitAnim));
368                    }
369                    if (op.popEnterAnim != 0 || op.popExitAnim != 0) {
370                        writer.print(innerPrefix);
371                        writer.print("popEnterAnim=#");
372                        writer.print(Integer.toHexString(op.popEnterAnim));
373                        writer.print(" popExitAnim=#");
374                        writer.println(Integer.toHexString(op.popExitAnim));
375                    }
376                }
377                if (op.removed != null && op.removed.size() > 0) {
378                    for (int i = 0; i < op.removed.size(); i++) {
379                        writer.print(innerPrefix);
380                        if (op.removed.size() == 1) {
381                            writer.print("Removed: ");
382                        } else {
383                            if (i == 0) {
384                                writer.println("Removed:");
385                            }
386                            writer.print(innerPrefix);
387                            writer.print("  #");
388                            writer.print(i);
389                            writer.print(": ");
390                        }
391                        writer.println(op.removed.get(i));
392                    }
393                }
394                op = op.next;
395                num++;
396            }
397        }
398    }
399
400    public BackStackRecord(FragmentManagerImpl manager) {
401        mManager = manager;
402    }
403
404    public int getId() {
405        return mIndex;
406    }
407
408    public int getBreadCrumbTitleRes() {
409        return mBreadCrumbTitleRes;
410    }
411
412    public int getBreadCrumbShortTitleRes() {
413        return mBreadCrumbShortTitleRes;
414    }
415
416    public CharSequence getBreadCrumbTitle() {
417        if (mBreadCrumbTitleRes != 0) {
418            return mManager.mHost.getContext().getText(mBreadCrumbTitleRes);
419        }
420        return mBreadCrumbTitleText;
421    }
422
423    public CharSequence getBreadCrumbShortTitle() {
424        if (mBreadCrumbShortTitleRes != 0) {
425            return mManager.mHost.getContext().getText(mBreadCrumbShortTitleRes);
426        }
427        return mBreadCrumbShortTitleText;
428    }
429
430    void addOp(Op op) {
431        if (mHead == null) {
432            mHead = mTail = op;
433        } else {
434            op.prev = mTail;
435            mTail.next = op;
436            mTail = op;
437        }
438        op.enterAnim = mEnterAnim;
439        op.exitAnim = mExitAnim;
440        op.popEnterAnim = mPopEnterAnim;
441        op.popExitAnim = mPopExitAnim;
442        mNumOp++;
443    }
444
445    public FragmentTransaction add(Fragment fragment, String tag) {
446        doAddOp(0, fragment, tag, OP_ADD);
447        return this;
448    }
449
450    public FragmentTransaction add(int containerViewId, Fragment fragment) {
451        doAddOp(containerViewId, fragment, null, OP_ADD);
452        return this;
453    }
454
455    public FragmentTransaction add(int containerViewId, Fragment fragment, String tag) {
456        doAddOp(containerViewId, fragment, tag, OP_ADD);
457        return this;
458    }
459
460    private void doAddOp(int containerViewId, Fragment fragment, String tag, int opcmd) {
461        fragment.mFragmentManager = mManager;
462
463        if (tag != null) {
464            if (fragment.mTag != null && !tag.equals(fragment.mTag)) {
465                throw new IllegalStateException("Can't change tag of fragment "
466                        + fragment + ": was " + fragment.mTag
467                        + " now " + tag);
468            }
469            fragment.mTag = tag;
470        }
471
472        if (containerViewId != 0) {
473            if (fragment.mFragmentId != 0 && fragment.mFragmentId != containerViewId) {
474                throw new IllegalStateException("Can't change container ID of fragment "
475                        + fragment + ": was " + fragment.mFragmentId
476                        + " now " + containerViewId);
477            }
478            fragment.mContainerId = fragment.mFragmentId = containerViewId;
479        }
480
481        Op op = new Op();
482        op.cmd = opcmd;
483        op.fragment = fragment;
484        addOp(op);
485    }
486
487    public FragmentTransaction replace(int containerViewId, Fragment fragment) {
488        return replace(containerViewId, fragment, null);
489    }
490
491    public FragmentTransaction replace(int containerViewId, Fragment fragment, String tag) {
492        if (containerViewId == 0) {
493            throw new IllegalArgumentException("Must use non-zero containerViewId");
494        }
495
496        doAddOp(containerViewId, fragment, tag, OP_REPLACE);
497        return this;
498    }
499
500    public FragmentTransaction remove(Fragment fragment) {
501        Op op = new Op();
502        op.cmd = OP_REMOVE;
503        op.fragment = fragment;
504        addOp(op);
505
506        return this;
507    }
508
509    public FragmentTransaction hide(Fragment fragment) {
510        Op op = new Op();
511        op.cmd = OP_HIDE;
512        op.fragment = fragment;
513        addOp(op);
514
515        return this;
516    }
517
518    public FragmentTransaction show(Fragment fragment) {
519        Op op = new Op();
520        op.cmd = OP_SHOW;
521        op.fragment = fragment;
522        addOp(op);
523
524        return this;
525    }
526
527    public FragmentTransaction detach(Fragment fragment) {
528        Op op = new Op();
529        op.cmd = OP_DETACH;
530        op.fragment = fragment;
531        addOp(op);
532
533        return this;
534    }
535
536    public FragmentTransaction attach(Fragment fragment) {
537        Op op = new Op();
538        op.cmd = OP_ATTACH;
539        op.fragment = fragment;
540        addOp(op);
541
542        return this;
543    }
544
545    public FragmentTransaction setCustomAnimations(int enter, int exit) {
546        return setCustomAnimations(enter, exit, 0, 0);
547    }
548
549    public FragmentTransaction setCustomAnimations(int enter, int exit,
550            int popEnter, int popExit) {
551        mEnterAnim = enter;
552        mExitAnim = exit;
553        mPopEnterAnim = popEnter;
554        mPopExitAnim = popExit;
555        return this;
556    }
557
558    public FragmentTransaction setTransition(int transition) {
559        mTransition = transition;
560        return this;
561    }
562
563    @Override
564    public FragmentTransaction addSharedElement(View sharedElement, String name) {
565        String transitionName = sharedElement.getTransitionName();
566        if (transitionName == null) {
567            throw new IllegalArgumentException("Unique transitionNames are required for all" +
568                    " sharedElements");
569        }
570        if (mSharedElementSourceNames == null) {
571            mSharedElementSourceNames = new ArrayList<String>();
572            mSharedElementTargetNames = new ArrayList<String>();
573        }
574        mSharedElementSourceNames.add(transitionName);
575        mSharedElementTargetNames.add(name);
576        return this;
577    }
578
579    public FragmentTransaction setTransitionStyle(int styleRes) {
580        mTransitionStyle = styleRes;
581        return this;
582    }
583
584    public FragmentTransaction addToBackStack(String name) {
585        if (!mAllowAddToBackStack) {
586            throw new IllegalStateException(
587                    "This FragmentTransaction is not allowed to be added to the back stack.");
588        }
589        mAddToBackStack = true;
590        mName = name;
591        return this;
592    }
593
594    public boolean isAddToBackStackAllowed() {
595        return mAllowAddToBackStack;
596    }
597
598    public FragmentTransaction disallowAddToBackStack() {
599        if (mAddToBackStack) {
600            throw new IllegalStateException(
601                    "This transaction is already being added to the back stack");
602        }
603        mAllowAddToBackStack = false;
604        return this;
605    }
606
607    public FragmentTransaction setBreadCrumbTitle(int res) {
608        mBreadCrumbTitleRes = res;
609        mBreadCrumbTitleText = null;
610        return this;
611    }
612
613    public FragmentTransaction setBreadCrumbTitle(CharSequence text) {
614        mBreadCrumbTitleRes = 0;
615        mBreadCrumbTitleText = text;
616        return this;
617    }
618
619    public FragmentTransaction setBreadCrumbShortTitle(int res) {
620        mBreadCrumbShortTitleRes = res;
621        mBreadCrumbShortTitleText = null;
622        return this;
623    }
624
625    public FragmentTransaction setBreadCrumbShortTitle(CharSequence text) {
626        mBreadCrumbShortTitleRes = 0;
627        mBreadCrumbShortTitleText = text;
628        return this;
629    }
630
631    void bumpBackStackNesting(int amt) {
632        if (!mAddToBackStack) {
633            return;
634        }
635        if (FragmentManagerImpl.DEBUG) {
636            Log.v(TAG, "Bump nesting in " + this
637                    + " by " + amt);
638        }
639        Op op = mHead;
640        while (op != null) {
641            if (op.fragment != null) {
642                op.fragment.mBackStackNesting += amt;
643                if (FragmentManagerImpl.DEBUG) {
644                    Log.v(TAG, "Bump nesting of "
645                            + op.fragment + " to " + op.fragment.mBackStackNesting);
646                }
647            }
648            if (op.removed != null) {
649                for (int i = op.removed.size() - 1; i >= 0; i--) {
650                    Fragment r = op.removed.get(i);
651                    r.mBackStackNesting += amt;
652                    if (FragmentManagerImpl.DEBUG) {
653                        Log.v(TAG, "Bump nesting of "
654                                + r + " to " + r.mBackStackNesting);
655                    }
656                }
657            }
658            op = op.next;
659        }
660    }
661
662    public int commit() {
663        return commitInternal(false);
664    }
665
666    public int commitAllowingStateLoss() {
667        return commitInternal(true);
668    }
669
670    int commitInternal(boolean allowStateLoss) {
671        if (mCommitted) {
672            throw new IllegalStateException("commit already called");
673        }
674        if (FragmentManagerImpl.DEBUG) {
675            Log.v(TAG, "Commit: " + this);
676            LogWriter logw = new LogWriter(Log.VERBOSE, TAG);
677            PrintWriter pw = new FastPrintWriter(logw, false, 1024);
678            dump("  ", null, pw, null);
679            pw.flush();
680        }
681        mCommitted = true;
682        if (mAddToBackStack) {
683            mIndex = mManager.allocBackStackIndex(this);
684        } else {
685            mIndex = -1;
686        }
687        mManager.enqueueAction(this, allowStateLoss);
688        return mIndex;
689    }
690
691    public void run() {
692        if (FragmentManagerImpl.DEBUG) {
693            Log.v(TAG, "Run: " + this);
694        }
695
696        if (mAddToBackStack) {
697            if (mIndex < 0) {
698                throw new IllegalStateException("addToBackStack() called after commit()");
699            }
700        }
701
702        bumpBackStackNesting(1);
703
704        SparseArray<Fragment> firstOutFragments = new SparseArray<Fragment>();
705        SparseArray<Fragment> lastInFragments = new SparseArray<Fragment>();
706        calculateFragments(firstOutFragments, lastInFragments);
707        beginTransition(firstOutFragments, lastInFragments, false);
708
709        Op op = mHead;
710        while (op != null) {
711            switch (op.cmd) {
712                case OP_ADD: {
713                    Fragment f = op.fragment;
714                    f.mNextAnim = op.enterAnim;
715                    mManager.addFragment(f, false);
716                }
717                break;
718                case OP_REPLACE: {
719                    Fragment f = op.fragment;
720                    int containerId = f.mContainerId;
721                    if (mManager.mAdded != null) {
722                        for (int i = 0; i < mManager.mAdded.size(); i++) {
723                            Fragment old = mManager.mAdded.get(i);
724                            if (FragmentManagerImpl.DEBUG) {
725                                Log.v(TAG,
726                                        "OP_REPLACE: adding=" + f + " old=" + old);
727                            }
728                            if (old.mContainerId == containerId) {
729                                if (old == f) {
730                                    op.fragment = f = null;
731                                } else {
732                                    if (op.removed == null) {
733                                        op.removed = new ArrayList<Fragment>();
734                                    }
735                                    op.removed.add(old);
736                                    old.mNextAnim = op.exitAnim;
737                                    if (mAddToBackStack) {
738                                        old.mBackStackNesting += 1;
739                                        if (FragmentManagerImpl.DEBUG) {
740                                            Log.v(TAG, "Bump nesting of "
741                                                    + old + " to " + old.mBackStackNesting);
742                                        }
743                                    }
744                                    mManager.removeFragment(old, mTransition, mTransitionStyle);
745                                }
746                            }
747                        }
748                    }
749                    if (f != null) {
750                        f.mNextAnim = op.enterAnim;
751                        mManager.addFragment(f, false);
752                    }
753                }
754                break;
755                case OP_REMOVE: {
756                    Fragment f = op.fragment;
757                    f.mNextAnim = op.exitAnim;
758                    mManager.removeFragment(f, mTransition, mTransitionStyle);
759                }
760                break;
761                case OP_HIDE: {
762                    Fragment f = op.fragment;
763                    f.mNextAnim = op.exitAnim;
764                    mManager.hideFragment(f, mTransition, mTransitionStyle);
765                }
766                break;
767                case OP_SHOW: {
768                    Fragment f = op.fragment;
769                    f.mNextAnim = op.enterAnim;
770                    mManager.showFragment(f, mTransition, mTransitionStyle);
771                }
772                break;
773                case OP_DETACH: {
774                    Fragment f = op.fragment;
775                    f.mNextAnim = op.exitAnim;
776                    mManager.detachFragment(f, mTransition, mTransitionStyle);
777                }
778                break;
779                case OP_ATTACH: {
780                    Fragment f = op.fragment;
781                    f.mNextAnim = op.enterAnim;
782                    mManager.attachFragment(f, mTransition, mTransitionStyle);
783                }
784                break;
785                default: {
786                    throw new IllegalArgumentException("Unknown cmd: " + op.cmd);
787                }
788            }
789
790            op = op.next;
791        }
792
793        mManager.moveToState(mManager.mCurState, mTransition,
794                mTransitionStyle, true);
795
796        if (mAddToBackStack) {
797            mManager.addBackStackState(this);
798        }
799    }
800
801    private static void setFirstOut(SparseArray<Fragment> fragments, Fragment fragment) {
802        if (fragment != null) {
803            int containerId = fragment.mContainerId;
804            if (containerId != 0 && !fragment.isHidden() && fragment.isAdded() &&
805                    fragment.getView() != null && fragments.get(containerId) == null) {
806                fragments.put(containerId, fragment);
807            }
808        }
809    }
810
811    private void setLastIn(SparseArray<Fragment> fragments, Fragment fragment) {
812        if (fragment != null) {
813            int containerId = fragment.mContainerId;
814            if (containerId != 0) {
815                fragments.put(containerId, fragment);
816            }
817        }
818    }
819
820    /**
821     * Finds the first removed fragment and last added fragments when going forward.
822     * If none of the fragments have transitions, then both lists will be empty.
823     *
824     * @param firstOutFragments The list of first fragments to be removed, keyed on the
825     *                          container ID. This list will be modified by the method.
826     * @param lastInFragments The list of last fragments to be added, keyed on the
827     *                        container ID. This list will be modified by the method.
828     */
829    private void calculateFragments(SparseArray<Fragment> firstOutFragments,
830            SparseArray<Fragment> lastInFragments) {
831        if (!mManager.mContainer.onHasView()) {
832            return; // nothing to see, so no transitions
833        }
834        Op op = mHead;
835        while (op != null) {
836            switch (op.cmd) {
837                case OP_ADD:
838                    setLastIn(lastInFragments, op.fragment);
839                    break;
840                case OP_REPLACE: {
841                    Fragment f = op.fragment;
842                    if (mManager.mAdded != null) {
843                        for (int i = 0; i < mManager.mAdded.size(); i++) {
844                            Fragment old = mManager.mAdded.get(i);
845                            if (f == null || old.mContainerId == f.mContainerId) {
846                                if (old == f) {
847                                    f = null;
848                                } else {
849                                    setFirstOut(firstOutFragments, old);
850                                }
851                            }
852                        }
853                    }
854                    setLastIn(lastInFragments, f);
855                    break;
856                }
857                case OP_REMOVE:
858                    setFirstOut(firstOutFragments, op.fragment);
859                    break;
860                case OP_HIDE:
861                    setFirstOut(firstOutFragments, op.fragment);
862                    break;
863                case OP_SHOW:
864                    setLastIn(lastInFragments, op.fragment);
865                    break;
866                case OP_DETACH:
867                    setFirstOut(firstOutFragments, op.fragment);
868                    break;
869                case OP_ATTACH:
870                    setLastIn(lastInFragments, op.fragment);
871                    break;
872            }
873
874            op = op.next;
875        }
876    }
877
878    /**
879     * Finds the first removed fragment and last added fragments when popping the back stack.
880     * If none of the fragments have transitions, then both lists will be empty.
881     *
882     * @param firstOutFragments The list of first fragments to be removed, keyed on the
883     *                          container ID. This list will be modified by the method.
884     * @param lastInFragments The list of last fragments to be added, keyed on the
885     *                        container ID. This list will be modified by the method.
886     */
887    public void calculateBackFragments(SparseArray<Fragment> firstOutFragments,
888            SparseArray<Fragment> lastInFragments) {
889        if (!mManager.mContainer.onHasView()) {
890            return; // nothing to see, so no transitions
891        }
892        Op op = mHead;
893        while (op != null) {
894            switch (op.cmd) {
895                case OP_ADD:
896                    setFirstOut(firstOutFragments, op.fragment);
897                    break;
898                case OP_REPLACE:
899                    if (op.removed != null) {
900                        for (int i = op.removed.size() - 1; i >= 0; i--) {
901                            setLastIn(lastInFragments, op.removed.get(i));
902                        }
903                    }
904                    setFirstOut(firstOutFragments, op.fragment);
905                    break;
906                case OP_REMOVE:
907                    setLastIn(lastInFragments, op.fragment);
908                    break;
909                case OP_HIDE:
910                    setLastIn(lastInFragments, op.fragment);
911                    break;
912                case OP_SHOW:
913                    setFirstOut(firstOutFragments, op.fragment);
914                    break;
915                case OP_DETACH:
916                    setLastIn(lastInFragments, op.fragment);
917                    break;
918                case OP_ATTACH:
919                    setFirstOut(firstOutFragments, op.fragment);
920                    break;
921            }
922
923            op = op.next;
924        }
925    }
926
927    /**
928     * When custom fragment transitions are used, this sets up the state for each transition
929     * and begins the transition. A different transition is started for each fragment container
930     * and consists of up to 3 different transitions: the exit transition, a shared element
931     * transition and an enter transition.
932     *
933     * <p>The exit transition operates against the leaf nodes of the first fragment
934     * with a view that was removed. If no such fragment was removed, then no exit
935     * transition is executed. The exit transition comes from the outgoing fragment.</p>
936     *
937     * <p>The enter transition operates against the last fragment that was added. If
938     * that fragment does not have a view or no fragment was added, then no enter
939     * transition is executed. The enter transition comes from the incoming fragment.</p>
940     *
941     * <p>The shared element transition operates against all views and comes either
942     * from the outgoing fragment or the incoming fragment, depending on whether this
943     * is going forward or popping the back stack. When going forward, the incoming
944     * fragment's enter shared element transition is used, but when going back, the
945     * outgoing fragment's return shared element transition is used. Shared element
946     * transitions only operate if there is both an incoming and outgoing fragment.</p>
947     *
948     * @param firstOutFragments The list of first fragments to be removed, keyed on the
949     *                          container ID.
950     * @param lastInFragments The list of last fragments to be added, keyed on the
951     *                        container ID.
952     * @param isBack true if this is popping the back stack or false if this is a
953     *               forward operation.
954     * @return The TransitionState used to complete the operation of the transition
955     * in {@link #setNameOverrides(android.app.BackStackRecord.TransitionState, java.util.ArrayList,
956     * java.util.ArrayList)}.
957     */
958    private TransitionState beginTransition(SparseArray<Fragment> firstOutFragments,
959            SparseArray<Fragment> lastInFragments, boolean isBack) {
960        TransitionState state = new TransitionState();
961
962        // Adding a non-existent target view makes sure that the transitions don't target
963        // any views by default. They'll only target the views we tell add. If we don't
964        // add any, then no views will be targeted.
965        state.nonExistentView = new View(mManager.mHost.getContext());
966
967        // Go over all leaving fragments.
968        for (int i = 0; i < firstOutFragments.size(); i++) {
969            int containerId = firstOutFragments.keyAt(i);
970            configureTransitions(containerId, state, isBack, firstOutFragments,
971                    lastInFragments);
972        }
973
974        // Now go over all entering fragments that didn't have a leaving fragment.
975        for (int i = 0; i < lastInFragments.size(); i++) {
976            int containerId = lastInFragments.keyAt(i);
977            if (firstOutFragments.get(containerId) == null) {
978                configureTransitions(containerId, state, isBack, firstOutFragments,
979                        lastInFragments);
980            }
981        }
982        return state;
983    }
984
985    private static Transition cloneTransition(Transition transition) {
986        if (transition != null) {
987            transition = transition.clone();
988        }
989        return transition;
990    }
991
992    private static Transition getEnterTransition(Fragment inFragment, boolean isBack) {
993        if (inFragment == null) {
994            return null;
995        }
996        return cloneTransition(isBack ? inFragment.getReenterTransition() :
997                inFragment.getEnterTransition());
998    }
999
1000    private static Transition getExitTransition(Fragment outFragment, boolean isBack) {
1001        if (outFragment == null) {
1002            return null;
1003        }
1004        return cloneTransition(isBack ? outFragment.getReturnTransition() :
1005                outFragment.getExitTransition());
1006    }
1007
1008    private static TransitionSet getSharedElementTransition(Fragment inFragment,
1009            Fragment outFragment, boolean isBack) {
1010        if (inFragment == null || outFragment == null) {
1011            return null;
1012        }
1013        Transition transition = cloneTransition(isBack
1014                ? outFragment.getSharedElementReturnTransition()
1015                : inFragment.getSharedElementEnterTransition());
1016        if (transition == null) {
1017            return null;
1018        }
1019        TransitionSet transitionSet = new TransitionSet();
1020        transitionSet.addTransition(transition);
1021        return transitionSet;
1022    }
1023
1024    private static ArrayList<View> captureExitingViews(Transition exitTransition,
1025            Fragment outFragment, ArrayMap<String, View> namedViews, View nonExistentView) {
1026        ArrayList<View> viewList = null;
1027        if (exitTransition != null) {
1028            viewList = new ArrayList<View>();
1029            View root = outFragment.getView();
1030            root.captureTransitioningViews(viewList);
1031            if (namedViews != null) {
1032                viewList.removeAll(namedViews.values());
1033            }
1034            if (!viewList.isEmpty()) {
1035                viewList.add(nonExistentView);
1036                addTargets(exitTransition, viewList);
1037            }
1038        }
1039        return viewList;
1040    }
1041
1042    private ArrayMap<String, View> remapSharedElements(TransitionState state, Fragment outFragment,
1043            boolean isBack) {
1044        ArrayMap<String, View> namedViews = new ArrayMap<String, View>();
1045        if (mSharedElementSourceNames != null) {
1046            outFragment.getView().findNamedViews(namedViews);
1047            if (isBack) {
1048                namedViews.retainAll(mSharedElementTargetNames);
1049            } else {
1050                namedViews = remapNames(mSharedElementSourceNames, mSharedElementTargetNames,
1051                        namedViews);
1052            }
1053        }
1054
1055        if (isBack) {
1056            outFragment.mEnterTransitionCallback.onMapSharedElements(
1057                    mSharedElementTargetNames, namedViews);
1058            setBackNameOverrides(state, namedViews, false);
1059        } else {
1060            outFragment.mExitTransitionCallback.onMapSharedElements(
1061                    mSharedElementTargetNames, namedViews);
1062            setNameOverrides(state, namedViews, false);
1063        }
1064
1065        return namedViews;
1066    }
1067
1068    /**
1069     * Prepares the enter transition by adding a non-existent view to the transition's target list
1070     * and setting it epicenter callback. By adding a non-existent view to the target list,
1071     * we can prevent any view from being targeted at the beginning of the transition.
1072     * We will add to the views before the end state of the transition is captured so that the
1073     * views will appear. At the start of the transition, we clear the list of targets so that
1074     * we can restore the state of the transition and use it again.
1075     *
1076     * <p>The shared element transition maps its shared elements immediately prior to
1077     * capturing the final state of the Transition.</p>
1078     */
1079    private ArrayList<View> addTransitionTargets(final TransitionState state,
1080            final Transition enterTransition, final TransitionSet sharedElementTransition,
1081            final Transition overallTransition, final View container,
1082            final Fragment inFragment, final Fragment outFragment,
1083            final ArrayList<View> hiddenFragmentViews, final boolean isBack,
1084            final ArrayList<View> sharedElementTargets) {
1085        if (enterTransition == null && sharedElementTransition == null &&
1086                overallTransition == null) {
1087            return null;
1088        }
1089        final ArrayList<View> enteringViews = new ArrayList<View>();
1090        container.getViewTreeObserver().addOnPreDrawListener(
1091                new ViewTreeObserver.OnPreDrawListener() {
1092                    @Override
1093                    public boolean onPreDraw() {
1094                        container.getViewTreeObserver().removeOnPreDrawListener(this);
1095
1096                        // Don't include any newly-hidden fragments in the transition.
1097                        if (inFragment != null) {
1098                            excludeHiddenFragments(hiddenFragmentViews, inFragment.mContainerId,
1099                                    overallTransition);
1100                        }
1101
1102                        ArrayMap<String, View> namedViews = null;
1103                        if (sharedElementTransition != null) {
1104                            namedViews = mapSharedElementsIn(state, isBack, inFragment);
1105                            removeTargets(sharedElementTransition, sharedElementTargets);
1106                            setSharedElementTargets(sharedElementTransition,
1107                                    state.nonExistentView, namedViews, sharedElementTargets);
1108
1109                            setEpicenterIn(namedViews, state);
1110
1111                            callSharedElementEnd(state, inFragment, outFragment, isBack,
1112                                    namedViews);
1113                        }
1114
1115                        if (enterTransition != null) {
1116                            enterTransition.removeTarget(state.nonExistentView);
1117                            View view = inFragment.getView();
1118                            if (view != null) {
1119                                view.captureTransitioningViews(enteringViews);
1120                                if (namedViews != null) {
1121                                    enteringViews.removeAll(namedViews.values());
1122                                }
1123                                enteringViews.add(state.nonExistentView);
1124                                // We added this earlier to prevent any views being targeted.
1125                                addTargets(enterTransition, enteringViews);
1126                            }
1127                            setSharedElementEpicenter(enterTransition, state);
1128                        }
1129                        return true;
1130                    }
1131                });
1132        return enteringViews;
1133    }
1134
1135    private void callSharedElementEnd(TransitionState state, Fragment inFragment,
1136            Fragment outFragment, boolean isBack, ArrayMap<String, View> namedViews) {
1137        SharedElementCallback sharedElementCallback = isBack ?
1138                outFragment.mEnterTransitionCallback :
1139                inFragment.mEnterTransitionCallback;
1140        ArrayList<String> names = new ArrayList<String>(namedViews.keySet());
1141        ArrayList<View> views = new ArrayList<View>(namedViews.values());
1142        sharedElementCallback.onSharedElementEnd(names, views, null);
1143    }
1144
1145    private void setEpicenterIn(ArrayMap<String, View> namedViews, TransitionState state) {
1146        if (mSharedElementTargetNames != null && !namedViews.isEmpty()) {
1147            // now we know the epicenter of the entering transition.
1148            View epicenter = namedViews
1149                    .get(mSharedElementTargetNames.get(0));
1150            if (epicenter != null) {
1151                state.enteringEpicenterView = epicenter;
1152            }
1153        }
1154    }
1155
1156    private ArrayMap<String, View> mapSharedElementsIn(TransitionState state,
1157            boolean isBack, Fragment inFragment) {
1158        // Now map the shared elements in the incoming fragment
1159        ArrayMap<String, View> namedViews = mapEnteringSharedElements(state, inFragment, isBack);
1160
1161        // remap shared elements and set the name mapping used
1162        // in the shared element transition.
1163        if (isBack) {
1164            inFragment.mExitTransitionCallback.onMapSharedElements(
1165                    mSharedElementTargetNames, namedViews);
1166            setBackNameOverrides(state, namedViews, true);
1167        } else {
1168            inFragment.mEnterTransitionCallback.onMapSharedElements(
1169                    mSharedElementTargetNames, namedViews);
1170            setNameOverrides(state, namedViews, true);
1171        }
1172        return namedViews;
1173    }
1174
1175    private static Transition mergeTransitions(Transition enterTransition,
1176            Transition exitTransition, Transition sharedElementTransition, Fragment inFragment,
1177            boolean isBack) {
1178        boolean overlap = true;
1179        if (enterTransition != null && exitTransition != null && inFragment != null) {
1180            overlap = isBack ? inFragment.getAllowReturnTransitionOverlap() :
1181                    inFragment.getAllowEnterTransitionOverlap();
1182        }
1183
1184        // Wrap the transitions. Explicit targets like in enter and exit will cause the
1185        // views to be targeted regardless of excluded views. If that happens, then the
1186        // excluded fragments views (hidden fragments) will still be in the transition.
1187
1188        Transition transition;
1189        if (overlap) {
1190            // Regular transition -- do it all together
1191            TransitionSet transitionSet = new TransitionSet();
1192            if (enterTransition != null) {
1193                transitionSet.addTransition(enterTransition);
1194            }
1195            if (exitTransition != null) {
1196                transitionSet.addTransition(exitTransition);
1197            }
1198            if (sharedElementTransition != null) {
1199                transitionSet.addTransition(sharedElementTransition);
1200            }
1201            transition = transitionSet;
1202        } else {
1203            // First do exit, then enter, but allow shared element transition to happen
1204            // during both.
1205            Transition staggered = null;
1206            if (exitTransition != null && enterTransition != null) {
1207                staggered = new TransitionSet()
1208                        .addTransition(exitTransition)
1209                        .addTransition(enterTransition)
1210                        .setOrdering(TransitionSet.ORDERING_SEQUENTIAL);
1211            } else if (exitTransition != null) {
1212                staggered = exitTransition;
1213            } else if (enterTransition != null) {
1214                staggered = enterTransition;
1215            }
1216            if (sharedElementTransition != null) {
1217                TransitionSet together = new TransitionSet();
1218                if (staggered != null) {
1219                    together.addTransition(staggered);
1220                }
1221                together.addTransition(sharedElementTransition);
1222                transition = together;
1223            } else {
1224                transition = staggered;
1225            }
1226        }
1227        return transition;
1228    }
1229
1230    /**
1231     * Configures custom transitions for a specific fragment container.
1232     *
1233     * @param containerId The container ID of the fragments to configure the transition for.
1234     * @param state The Transition State keeping track of the executing transitions.
1235     * @param firstOutFragments The list of first fragments to be removed, keyed on the
1236     *                          container ID.
1237     * @param lastInFragments The list of last fragments to be added, keyed on the
1238     *                        container ID.
1239     * @param isBack true if this is popping the back stack or false if this is a
1240     *               forward operation.
1241     */
1242    private void configureTransitions(int containerId, TransitionState state, boolean isBack,
1243            SparseArray<Fragment> firstOutFragments, SparseArray<Fragment> lastInFragments) {
1244        ViewGroup sceneRoot = (ViewGroup) mManager.mContainer.onFindViewById(containerId);
1245        if (sceneRoot != null) {
1246            Fragment inFragment = lastInFragments.get(containerId);
1247            Fragment outFragment = firstOutFragments.get(containerId);
1248
1249            Transition enterTransition = getEnterTransition(inFragment, isBack);
1250            TransitionSet sharedElementTransition =
1251                    getSharedElementTransition(inFragment, outFragment, isBack);
1252            Transition exitTransition = getExitTransition(outFragment, isBack);
1253
1254            if (enterTransition == null && sharedElementTransition == null &&
1255                    exitTransition == null) {
1256                return; // no transitions!
1257            }
1258            if (enterTransition != null) {
1259                enterTransition.addTarget(state.nonExistentView);
1260            }
1261            ArrayMap<String, View> namedViews = null;
1262            ArrayList<View> sharedElementTargets = new ArrayList<View>();
1263            if (sharedElementTransition != null) {
1264                namedViews = remapSharedElements(state, outFragment, isBack);
1265                setSharedElementTargets(sharedElementTransition,
1266                        state.nonExistentView, namedViews, sharedElementTargets);
1267
1268                // Notify the start of the transition.
1269                SharedElementCallback callback = isBack ?
1270                        outFragment.mEnterTransitionCallback :
1271                        inFragment.mEnterTransitionCallback;
1272                ArrayList<String> names = new ArrayList<String>(namedViews.keySet());
1273                ArrayList<View> views = new ArrayList<View>(namedViews.values());
1274                callback.onSharedElementStart(names, views, null);
1275            }
1276
1277            ArrayList<View> exitingViews = captureExitingViews(exitTransition, outFragment,
1278                    namedViews, state.nonExistentView);
1279            if (exitingViews == null || exitingViews.isEmpty()) {
1280                exitTransition = null;
1281            }
1282
1283            // Set the epicenter of the exit transition
1284            if (mSharedElementTargetNames != null && namedViews != null) {
1285                View epicenterView = namedViews.get(mSharedElementTargetNames.get(0));
1286                if (epicenterView != null) {
1287                    if (exitTransition != null) {
1288                        setEpicenter(exitTransition, epicenterView);
1289                    }
1290                    if (sharedElementTransition != null) {
1291                        setEpicenter(sharedElementTransition, epicenterView);
1292                    }
1293                }
1294            }
1295
1296            Transition transition = mergeTransitions(enterTransition, exitTransition,
1297                    sharedElementTransition, inFragment, isBack);
1298
1299            if (transition != null) {
1300                ArrayList<View> hiddenFragments = new ArrayList<View>();
1301                ArrayList<View> enteringViews = addTransitionTargets(state, enterTransition,
1302                        sharedElementTransition, transition, sceneRoot, inFragment,
1303                        outFragment, hiddenFragments, isBack, sharedElementTargets);
1304
1305                transition.setNameOverrides(state.nameOverrides);
1306                // We want to exclude hidden views later, so we need a non-null list in the
1307                // transition now.
1308                transition.excludeTarget(state.nonExistentView, true);
1309                // Now exclude all currently hidden fragments.
1310                excludeHiddenFragments(hiddenFragments, containerId, transition);
1311                TransitionManager.beginDelayedTransition(sceneRoot, transition);
1312                // Remove the view targeting after the transition starts
1313                removeTargetedViewsFromTransitions(sceneRoot, state.nonExistentView,
1314                        enterTransition, enteringViews, exitTransition, exitingViews,
1315                        sharedElementTransition, sharedElementTargets, transition,
1316                        hiddenFragments);
1317            }
1318        }
1319    }
1320
1321    /**
1322     * Finds all children of the shared elements and sets the wrapping TransitionSet
1323     * targets to point to those. It also limits transitions that have no targets to the
1324     * specific shared elements. This allows developers to target child views of the
1325     * shared elements specifically, but this doesn't happen by default.
1326     */
1327    private static void setSharedElementTargets(TransitionSet transition,
1328            View nonExistentView, ArrayMap<String, View> namedViews,
1329            ArrayList<View> sharedElementTargets) {
1330        sharedElementTargets.clear();
1331        sharedElementTargets.addAll(namedViews.values());
1332
1333        final List<View> views = transition.getTargets();
1334        views.clear();
1335        final int count = sharedElementTargets.size();
1336        for (int i = 0; i < count; i++) {
1337            final View view = sharedElementTargets.get(i);
1338            bfsAddViewChildren(views, view);
1339        }
1340        sharedElementTargets.add(nonExistentView);
1341        addTargets(transition, sharedElementTargets);
1342    }
1343
1344    /**
1345     * Uses a breadth-first scheme to add startView and all of its children to views.
1346     * It won't add a child if it is already in views.
1347     */
1348    private static void bfsAddViewChildren(final List<View> views, final View startView) {
1349        final int startIndex = views.size();
1350        if (containedBeforeIndex(views, startView, startIndex)) {
1351            return; // This child is already in the list, so all its children are also.
1352        }
1353        views.add(startView);
1354        for (int index = startIndex; index < views.size(); index++) {
1355            final View view = views.get(index);
1356            if (view instanceof ViewGroup) {
1357                ViewGroup viewGroup = (ViewGroup) view;
1358                final int childCount =  viewGroup.getChildCount();
1359                for (int childIndex = 0; childIndex < childCount; childIndex++) {
1360                    final View child = viewGroup.getChildAt(childIndex);
1361                    if (!containedBeforeIndex(views, child, startIndex)) {
1362                        views.add(child);
1363                    }
1364                }
1365            }
1366        }
1367    }
1368
1369    /**
1370     * Does a linear search through views for view, limited to maxIndex.
1371     */
1372    private static boolean containedBeforeIndex(final List<View> views, final View view,
1373            final int maxIndex) {
1374        for (int i = 0; i < maxIndex; i++) {
1375            if (views.get(i) == view) {
1376                return true;
1377            }
1378        }
1379        return false;
1380    }
1381
1382    /**
1383     * After the transition has started, remove all targets that we added to the transitions
1384     * so that the transitions are left in a clean state.
1385     */
1386    private void removeTargetedViewsFromTransitions(
1387            final ViewGroup sceneRoot, final View nonExistingView,
1388            final Transition enterTransition, final ArrayList<View> enteringViews,
1389            final Transition exitTransition, final ArrayList<View> exitingViews,
1390            final Transition sharedElementTransition, final ArrayList<View> sharedElementTargets,
1391            final Transition overallTransition, final ArrayList<View> hiddenViews) {
1392        if (overallTransition != null) {
1393            sceneRoot.getViewTreeObserver().addOnPreDrawListener(new ViewTreeObserver.OnPreDrawListener() {
1394                @Override
1395                public boolean onPreDraw() {
1396                    sceneRoot.getViewTreeObserver().removeOnPreDrawListener(this);
1397                    if (enterTransition != null) {
1398                        removeTargets(enterTransition, enteringViews);
1399                    }
1400                    if (exitTransition != null) {
1401                        removeTargets(exitTransition, exitingViews);
1402                    }
1403                    if (sharedElementTransition != null) {
1404                        removeTargets(sharedElementTransition, sharedElementTargets);
1405                    }
1406                    int numViews = hiddenViews.size();
1407                    for (int i = 0; i < numViews; i++) {
1408                        overallTransition.excludeTarget(hiddenViews.get(i), false);
1409                    }
1410                    overallTransition.excludeTarget(nonExistingView, false);
1411                    return true;
1412                }
1413            });
1414        }
1415    }
1416
1417    /**
1418     * This method removes the views from transitions that target ONLY those views.
1419     * The views list should match those added in addTargets and should contain
1420     * one view that is not in the view hierarchy (state.nonExistentView).
1421     */
1422    public static void removeTargets(Transition transition, ArrayList<View> views) {
1423        if (transition instanceof TransitionSet) {
1424            TransitionSet set = (TransitionSet) transition;
1425            int numTransitions = set.getTransitionCount();
1426            for (int i = 0; i < numTransitions; i++) {
1427                Transition child = set.getTransitionAt(i);
1428                removeTargets(child, views);
1429            }
1430        } else if (!hasSimpleTarget(transition)) {
1431            List<View> targets = transition.getTargets();
1432            if (targets != null && targets.size() == views.size() &&
1433                    targets.containsAll(views)) {
1434                // We have an exact match. We must have added these earlier in addTargets
1435                for (int i = views.size() - 1; i >= 0; i--) {
1436                    transition.removeTarget(views.get(i));
1437                }
1438            }
1439        }
1440    }
1441
1442    /**
1443     * This method adds views as targets to the transition, but only if the transition
1444     * doesn't already have a target. It is best for views to contain one View object
1445     * that does not exist in the view hierarchy (state.nonExistentView) so that
1446     * when they are removed later, a list match will suffice to remove the targets.
1447     * Otherwise, if you happened to have targeted the exact views for the transition,
1448     * the removeTargets call will remove them unexpectedly.
1449     */
1450    public static void addTargets(Transition transition, ArrayList<View> views) {
1451        if (transition instanceof TransitionSet) {
1452            TransitionSet set = (TransitionSet) transition;
1453            int numTransitions = set.getTransitionCount();
1454            for (int i = 0; i < numTransitions; i++) {
1455                Transition child = set.getTransitionAt(i);
1456                addTargets(child, views);
1457            }
1458        } else if (!hasSimpleTarget(transition)) {
1459            List<View> targets = transition.getTargets();
1460            if (isNullOrEmpty(targets)) {
1461                // We can just add the target views
1462                int numViews = views.size();
1463                for (int i = 0; i < numViews; i++) {
1464                    transition.addTarget(views.get(i));
1465                }
1466            }
1467        }
1468    }
1469
1470    private static boolean hasSimpleTarget(Transition transition) {
1471        return !isNullOrEmpty(transition.getTargetIds()) ||
1472                !isNullOrEmpty(transition.getTargetNames()) ||
1473                !isNullOrEmpty(transition.getTargetTypes());
1474    }
1475
1476    private static boolean isNullOrEmpty(List list) {
1477        return list == null || list.isEmpty();
1478    }
1479
1480    /**
1481     * Remaps a name-to-View map, substituting different names for keys.
1482     *
1483     * @param inMap A list of keys found in the map, in the order in toGoInMap
1484     * @param toGoInMap A list of keys to use for the new map, in the order of inMap
1485     * @param namedViews The current mapping
1486     * @return a new Map after it has been mapped with the new names as keys.
1487     */
1488    private static ArrayMap<String, View> remapNames(ArrayList<String> inMap,
1489            ArrayList<String> toGoInMap, ArrayMap<String, View> namedViews) {
1490        ArrayMap<String, View> remappedViews = new ArrayMap<String, View>();
1491        if (!namedViews.isEmpty()) {
1492            int numKeys = inMap.size();
1493            for (int i = 0; i < numKeys; i++) {
1494                View view = namedViews.get(inMap.get(i));
1495
1496                if (view != null) {
1497                    remappedViews.put(toGoInMap.get(i), view);
1498                }
1499            }
1500        }
1501        return remappedViews;
1502    }
1503
1504    /**
1505     * Maps shared elements to views in the entering fragment.
1506     *
1507     * @param state The transition State as returned from {@link #beginTransition(
1508     * android.util.SparseArray, android.util.SparseArray, boolean)}.
1509     * @param inFragment The last fragment to be added.
1510     * @param isBack true if this is popping the back stack or false if this is a
1511     *               forward operation.
1512     */
1513    private ArrayMap<String, View> mapEnteringSharedElements(TransitionState state,
1514            Fragment inFragment, boolean isBack) {
1515        ArrayMap<String, View> namedViews = new ArrayMap<String, View>();
1516        View root = inFragment.getView();
1517        if (root != null) {
1518            if (mSharedElementSourceNames != null) {
1519                root.findNamedViews(namedViews);
1520                if (isBack) {
1521                    namedViews = remapNames(mSharedElementSourceNames,
1522                            mSharedElementTargetNames, namedViews);
1523                } else {
1524                    namedViews.retainAll(mSharedElementTargetNames);
1525                }
1526            }
1527        }
1528        return namedViews;
1529    }
1530
1531    private void excludeHiddenFragments(final ArrayList<View> hiddenFragmentViews, int containerId,
1532            Transition transition) {
1533        if (mManager.mAdded != null) {
1534            for (int i = 0; i < mManager.mAdded.size(); i++) {
1535                Fragment fragment = mManager.mAdded.get(i);
1536                if (fragment.mView != null && fragment.mContainer != null &&
1537                        fragment.mContainerId == containerId) {
1538                    if (fragment.mHidden) {
1539                        if (!hiddenFragmentViews.contains(fragment.mView)) {
1540                            transition.excludeTarget(fragment.mView, true);
1541                            hiddenFragmentViews.add(fragment.mView);
1542                        }
1543                    } else {
1544                        transition.excludeTarget(fragment.mView, false);
1545                        hiddenFragmentViews.remove(fragment.mView);
1546                    }
1547                }
1548            }
1549        }
1550    }
1551
1552    private static void setEpicenter(Transition transition, View view) {
1553        final Rect epicenter = new Rect();
1554        view.getBoundsOnScreen(epicenter);
1555
1556        transition.setEpicenterCallback(new Transition.EpicenterCallback() {
1557            @Override
1558            public Rect onGetEpicenter(Transition transition) {
1559                return epicenter;
1560            }
1561        });
1562    }
1563
1564    private void setSharedElementEpicenter(Transition transition, final TransitionState state) {
1565        transition.setEpicenterCallback(new Transition.EpicenterCallback() {
1566            private Rect mEpicenter;
1567
1568            @Override
1569            public Rect onGetEpicenter(Transition transition) {
1570                if (mEpicenter == null && state.enteringEpicenterView != null) {
1571                    mEpicenter = new Rect();
1572                    state.enteringEpicenterView.getBoundsOnScreen(mEpicenter);
1573                }
1574                return mEpicenter;
1575            }
1576        });
1577    }
1578
1579    public TransitionState popFromBackStack(boolean doStateMove, TransitionState state,
1580            SparseArray<Fragment> firstOutFragments, SparseArray<Fragment> lastInFragments) {
1581        if (FragmentManagerImpl.DEBUG) {
1582            Log.v(TAG, "popFromBackStack: " + this);
1583            LogWriter logw = new LogWriter(Log.VERBOSE, TAG);
1584            PrintWriter pw = new FastPrintWriter(logw, false, 1024);
1585            dump("  ", null, pw, null);
1586            pw.flush();
1587        }
1588
1589        if (state == null) {
1590            if (firstOutFragments.size() != 0 || lastInFragments.size() != 0) {
1591                state = beginTransition(firstOutFragments, lastInFragments, true);
1592            }
1593        } else if (!doStateMove) {
1594            setNameOverrides(state, mSharedElementTargetNames, mSharedElementSourceNames);
1595        }
1596
1597        bumpBackStackNesting(-1);
1598
1599        Op op = mTail;
1600        while (op != null) {
1601            switch (op.cmd) {
1602                case OP_ADD: {
1603                    Fragment f = op.fragment;
1604                    f.mNextAnim = op.popExitAnim;
1605                    mManager.removeFragment(f,
1606                            FragmentManagerImpl.reverseTransit(mTransition),
1607                            mTransitionStyle);
1608                }
1609                break;
1610                case OP_REPLACE: {
1611                    Fragment f = op.fragment;
1612                    if (f != null) {
1613                        f.mNextAnim = op.popExitAnim;
1614                        mManager.removeFragment(f,
1615                                FragmentManagerImpl.reverseTransit(mTransition),
1616                                mTransitionStyle);
1617                    }
1618                    if (op.removed != null) {
1619                        for (int i = 0; i < op.removed.size(); i++) {
1620                            Fragment old = op.removed.get(i);
1621                            old.mNextAnim = op.popEnterAnim;
1622                            mManager.addFragment(old, false);
1623                        }
1624                    }
1625                }
1626                break;
1627                case OP_REMOVE: {
1628                    Fragment f = op.fragment;
1629                    f.mNextAnim = op.popEnterAnim;
1630                    mManager.addFragment(f, false);
1631                }
1632                break;
1633                case OP_HIDE: {
1634                    Fragment f = op.fragment;
1635                    f.mNextAnim = op.popEnterAnim;
1636                    mManager.showFragment(f,
1637                            FragmentManagerImpl.reverseTransit(mTransition), mTransitionStyle);
1638                }
1639                break;
1640                case OP_SHOW: {
1641                    Fragment f = op.fragment;
1642                    f.mNextAnim = op.popExitAnim;
1643                    mManager.hideFragment(f,
1644                            FragmentManagerImpl.reverseTransit(mTransition), mTransitionStyle);
1645                }
1646                break;
1647                case OP_DETACH: {
1648                    Fragment f = op.fragment;
1649                    f.mNextAnim = op.popEnterAnim;
1650                    mManager.attachFragment(f,
1651                            FragmentManagerImpl.reverseTransit(mTransition), mTransitionStyle);
1652                }
1653                break;
1654                case OP_ATTACH: {
1655                    Fragment f = op.fragment;
1656                    f.mNextAnim = op.popExitAnim;
1657                    mManager.detachFragment(f,
1658                            FragmentManagerImpl.reverseTransit(mTransition), mTransitionStyle);
1659                }
1660                break;
1661                default: {
1662                    throw new IllegalArgumentException("Unknown cmd: " + op.cmd);
1663                }
1664            }
1665
1666            op = op.prev;
1667        }
1668
1669        if (doStateMove) {
1670            mManager.moveToState(mManager.mCurState,
1671                    FragmentManagerImpl.reverseTransit(mTransition), mTransitionStyle, true);
1672            state = null;
1673        }
1674
1675        if (mIndex >= 0) {
1676            mManager.freeBackStackIndex(mIndex);
1677            mIndex = -1;
1678        }
1679        return state;
1680    }
1681
1682    private static void setNameOverride(ArrayMap<String, String> overrides,
1683            String source, String target) {
1684        if (source != null && target != null && !source.equals(target)) {
1685            for (int index = 0; index < overrides.size(); index++) {
1686                if (source.equals(overrides.valueAt(index))) {
1687                    overrides.setValueAt(index, target);
1688                    return;
1689                }
1690            }
1691            overrides.put(source, target);
1692        }
1693    }
1694
1695    private static void setNameOverrides(TransitionState state, ArrayList<String> sourceNames,
1696            ArrayList<String> targetNames) {
1697        if (sourceNames != null && targetNames != null) {
1698            for (int i = 0; i < sourceNames.size(); i++) {
1699                String source = sourceNames.get(i);
1700                String target = targetNames.get(i);
1701                setNameOverride(state.nameOverrides, source, target);
1702            }
1703        }
1704    }
1705
1706    private void setBackNameOverrides(TransitionState state, ArrayMap<String, View> namedViews,
1707            boolean isEnd) {
1708        int targetCount = mSharedElementTargetNames == null ? 0 : mSharedElementTargetNames.size();
1709        int sourceCount = mSharedElementSourceNames == null ? 0 : mSharedElementSourceNames.size();
1710        final int count = Math.min(targetCount, sourceCount);
1711        for (int i = 0; i < count; i++) {
1712            String source = mSharedElementSourceNames.get(i);
1713            String originalTarget = mSharedElementTargetNames.get(i);
1714            View view = namedViews.get(originalTarget);
1715            if (view != null) {
1716                String target = view.getTransitionName();
1717                if (isEnd) {
1718                    setNameOverride(state.nameOverrides, source, target);
1719                } else {
1720                    setNameOverride(state.nameOverrides, target, source);
1721                }
1722            }
1723        }
1724    }
1725
1726    private void setNameOverrides(TransitionState state, ArrayMap<String, View> namedViews,
1727            boolean isEnd) {
1728        int count = namedViews == null ? 0 : namedViews.size();
1729        for (int i = 0; i < count; i++) {
1730            String source = namedViews.keyAt(i);
1731            String target = namedViews.valueAt(i).getTransitionName();
1732            if (isEnd) {
1733                setNameOverride(state.nameOverrides, source, target);
1734            } else {
1735                setNameOverride(state.nameOverrides, target, source);
1736            }
1737        }
1738    }
1739
1740    public String getName() {
1741        return mName;
1742    }
1743
1744    public int getTransition() {
1745        return mTransition;
1746    }
1747
1748    public int getTransitionStyle() {
1749        return mTransitionStyle;
1750    }
1751
1752    public boolean isEmpty() {
1753        return mNumOp == 0;
1754    }
1755
1756    public class TransitionState {
1757        public ArrayMap<String, String> nameOverrides = new ArrayMap<String, String>();
1758        public View enteringEpicenterView;
1759        public View nonExistentView;
1760    }
1761}
1762