StaggeredGridLayoutManager.java revision 7c7fba8365684e1ccfc4f39f286df4d100c6c81f 
1/*
2 * Copyright (C) 2014 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.support.v7.widget;
18
19import android.content.Context;
20import android.graphics.PointF;
21import android.graphics.Rect;
22import android.os.Parcel;
23import android.os.Parcelable;
24import android.support.v4.view.ViewCompat;
25import android.util.AttributeSet;
26import android.util.Log;
27import android.view.View;
28import android.view.ViewGroup;
29
30
31import java.util.ArrayList;
32import java.util.Arrays;
33import java.util.BitSet;
34
35
36import static android.support.v7.widget.LayoutState.LAYOUT_START;
37import static android.support.v7.widget.LayoutState.LAYOUT_END;
38import static android.support.v7.widget.LayoutState.ITEM_DIRECTION_HEAD;
39import static android.support.v7.widget.LayoutState.ITEM_DIRECTION_TAIL;
40/**
41 * A LayoutManager that lays out children in a staggered grid formation.
42 * It supports horizontal & vertical layout as well as an ability to layout children in reverse.
43 * <p>
44 * Staggered grids are likely to have gaps at the edges of the layout. To avoid these gaps,
45 * StaggeredGridLayoutManager can offset spans independently or move items between spans. You can
46 * control this behavior via {@link #setGapStrategy(int)}.
47 */
48public class StaggeredGridLayoutManager extends RecyclerView.LayoutManager {
49
50    public static final String TAG = "StaggeredGridLayoutManager";
51
52    private static final boolean DEBUG = false;
53
54    public static final int HORIZONTAL = OrientationHelper.HORIZONTAL;
55
56    public static final int VERTICAL = OrientationHelper.VERTICAL;
57
58    /**
59     * Does not do anything to hide gaps
60     */
61    public static final int GAP_HANDLING_NONE = 0;
62
63    /**
64     * Scroll the shorter span slower to avoid gaps in the UI.
65     * <p>
66     * For example, if LayoutManager ends up with the following layout:
67     * <code>
68     * BXC
69     * DEF
70     * </code>
71     * Where B has two spans height, if user scrolls down it will keep the positions of 2nd and 3rd
72     * columns,
73     * which will result in:
74     * <code>
75     * BXC
76     * BEF
77     * </code>
78     * instead of
79     * <code>
80     * B
81     * BEF
82     * </code>
83     */
84    public static final int GAP_HANDLING_LAZY = 1;
85
86    /**
87     * On scroll, LayoutManager checks for a view that is assigned to wrong span.
88     * When such a situation is detected, LayoutManager will wait until scroll is complete and then
89     * move children to their correct spans.
90     * <p>
91     * For example, if LayoutManager ends up with the following layout due to adapter changes:
92     * <code>
93     * AAA
94     * _BC
95     * DDD
96     * </code>
97     * It will animate to the following state:
98     * <code>
99     * AAA
100     * BC_
101     * DDD
102     * </code>
103     */
104    public static final int GAP_HANDLING_MOVE_ITEMS_BETWEEN_SPANS = 2;
105
106    private static final int INVALID_OFFSET = Integer.MIN_VALUE;
107
108    /**
109     * Number of spans
110     */
111    private int mSpanCount = -1;
112
113    private Span[] mSpans;
114
115    /**
116     * Primary orientation is the layout's orientation, secondary orientation is the orientation
117     * for spans. Having both makes code much cleaner for calculations.
118     */
119    OrientationHelper mPrimaryOrientation;
120    OrientationHelper mSecondaryOrientation;
121
122    private int mOrientation;
123
124    /**
125     * The width or height per span, depending on the orientation.
126     */
127    private int mSizePerSpan;
128
129    private LayoutState mLayoutState;
130
131    private boolean mReverseLayout = false;
132
133    /**
134     * Aggregated reverse layout value that takes RTL into account.
135     */
136    private boolean mShouldReverseLayout = false;
137
138    /**
139     * Temporary variable used during fill method to check which spans needs to be filled.
140     */
141    private BitSet mRemainingSpans;
142
143    /**
144     * When LayoutManager needs to scroll to a position, it sets this variable and requests a
145     * layout which will check this variable and re-layout accordingly.
146     */
147    private int mPendingScrollPosition = RecyclerView.NO_POSITION;
148
149    /**
150     * Used to keep the offset value when {@link #scrollToPositionWithOffset(int, int)} is
151     * called.
152     */
153    private int mPendingScrollPositionOffset = INVALID_OFFSET;
154
155    /**
156     * Keeps the mapping between the adapter positions and spans. This is necessary to provide
157     * a consistent experience when user scrolls the list.
158     */
159    LazySpanLookup mLazySpanLookup = new LazySpanLookup();
160
161    /**
162     * how we handle gaps in UI.
163     */
164    private int mGapStrategy = GAP_HANDLING_MOVE_ITEMS_BETWEEN_SPANS;
165
166    /**
167     * Saved state needs this information to properly layout on restore.
168     */
169    private boolean mLastLayoutFromEnd;
170
171    /**
172     * SavedState is not handled until a layout happens. This is where we keep it until next
173     * layout.
174     */
175    private SavedState mPendingSavedState;
176
177    /**
178     * If LayoutManager detects an unwanted gap in the layout, it sets this flag which will trigger
179     * a runnable after scrolling ends and will re-check. If invalid view state is still present,
180     * it will request a layout to fix it.
181     */
182    private boolean mHasGaps;
183
184    /**
185     * Creates a StaggeredGridLayoutManager with given parameters.
186     *
187     * @param spanCount   If orientation is vertical, spanCount is number of columns. If
188     *                    orientation is horizontal, spanCount is number of rows.
189     * @param orientation {@link #VERTICAL} or {@link #HORIZONTAL}
190     */
191    public StaggeredGridLayoutManager(int spanCount, int orientation) {
192        mOrientation = orientation;
193        setSpanCount(spanCount);
194    }
195
196    @Override
197    public void onScrollStateChanged(int state) {
198        if (state == RecyclerView.SCROLL_STATE_IDLE && mHasGaps) {
199            // re-check for gaps
200            View gapView = hasGapsToFix(0, getChildCount());
201            if (gapView == null) {
202                mHasGaps = false; // yay, gap disappeared :)
203                // We should invalidate positions after the last visible child. No reason to
204                // re-layout.
205                final int lastVisiblePosition = mShouldReverseLayout ? getFirstChildPosition()
206                        : getLastChildPosition();
207                mLazySpanLookup.invalidateAfter(lastVisiblePosition + 1);
208            } else {
209                mLazySpanLookup.invalidateAfter(getPosition(gapView));
210                requestSimpleAnimationsInNextLayout();
211                requestLayout(); // Trigger a re-layout which will fix the layout assignments.
212            }
213        }
214    }
215
216    /**
217     * Sets the number of spans for the layout. This will invalidate all of the span assignments
218     * for Views.
219     * <p>
220     * Calling this method will automatically result in a new layout request unless the spanCount
221     * parameter is equal to current span count.
222     *
223     * @param spanCount Number of spans to layout
224     */
225    public void setSpanCount(int spanCount) {
226        assertNotInLayoutOrScroll(null);
227        if (mPendingSavedState != null && mPendingSavedState.mSpanCount != spanCount) {
228            // invalidate span info in saved state
229            mPendingSavedState.invalidateSpanInfo();
230            mPendingSavedState.mSpanCount = spanCount;
231            mPendingSavedState.mAnchorPosition = mPendingSavedState.mVisibleAnchorPosition;
232        }
233        if (spanCount != mSpanCount) {
234            invalidateSpanAssignments();
235            mSpanCount = spanCount;
236            mRemainingSpans = new BitSet(mSpanCount);
237            mSpans = new Span[mSpanCount];
238            for (int i = 0; i < mSpanCount; i++) {
239                mSpans[i] = new Span(i);
240            }
241            requestLayout();
242        }
243    }
244
245    /**
246     * Sets the orientation of the layout. StaggeredGridLayoutManager will do its best to keep
247     * scroll position.
248     *
249     * @param orientation {@link OrientationHelper#HORIZONTAL} or {@link OrientationHelper#VERTICAL}
250     */
251    public void setOrientation(int orientation) {
252        if (orientation != HORIZONTAL && orientation != VERTICAL) {
253            throw new IllegalArgumentException("invalid orientation.");
254        }
255        assertNotInLayoutOrScroll(null);
256        if (mPendingSavedState != null && mPendingSavedState.mOrientation != orientation) {
257            // override pending state
258            mPendingSavedState.mOrientation = orientation;
259        }
260        if (orientation == mOrientation) {
261            return;
262        }
263        mOrientation = orientation;
264        if (mPrimaryOrientation != null && mSecondaryOrientation != null) {
265            // swap
266            OrientationHelper tmp = mPrimaryOrientation;
267            mPrimaryOrientation = mSecondaryOrientation;
268            mSecondaryOrientation = tmp;
269        }
270        requestLayout();
271    }
272
273    /**
274     * Sets whether LayoutManager should start laying out items from the end of the UI. The order
275     * items are traversed is not affected by this call.
276     * <p>
277     * This behaves similar to the layout change for RTL views. When set to true, first item is
278     * laid out at the end of the ViewGroup, second item is laid out before it etc.
279     * <p>
280     * For horizontal layouts, it depends on the layout direction.
281     * When set to true, If {@link RecyclerView} is LTR, than it will layout from RTL, if
282     * {@link RecyclerView}} is RTL, it will layout from LTR.
283     *
284     * @param reverseLayout Whether layout should be in reverse or not
285     */
286    public void setReverseLayout(boolean reverseLayout) {
287        assertNotInLayoutOrScroll(null);
288        if (mPendingSavedState != null && mPendingSavedState.mReverseLayout != reverseLayout) {
289            mPendingSavedState.mReverseLayout = reverseLayout;
290        }
291        mReverseLayout = reverseLayout;
292        requestLayout();
293    }
294
295    /**
296     * Returns the current gap handling strategy for StaggeredGridLayoutManager.
297     * <p>
298     * Staggered grid may have gaps in the layout as items may have different sizes. To avoid gaps,
299     * StaggeredGridLayoutManager provides 3 options. Check {@link #GAP_HANDLING_NONE},
300     * {@link #GAP_HANDLING_MOVE_ITEMS_BETWEEN_SPANS}, {@link #GAP_HANDLING_LAZY} for details.
301     * <p>
302     * By default, StaggeredGridLayoutManager uses {@link #GAP_HANDLING_MOVE_ITEMS_BETWEEN_SPANS}.
303     *
304     * @return Current gap handling strategy.
305     * @see #setGapStrategy(int)
306     * @see #GAP_HANDLING_NONE
307     * @see #GAP_HANDLING_LAZY
308     * @see #GAP_HANDLING_MOVE_ITEMS_BETWEEN_SPANS
309     */
310    public int getGapStrategy() {
311        return mGapStrategy;
312    }
313
314    /**
315     * Sets the gap handling strategy for StaggeredGridLayoutManager. If the gapStrategy parameter
316     * is different than the current strategy, calling this method will trigger a layout request.
317     *
318     * @param gapStrategy The new gap handling strategy. Should be {@link #GAP_HANDLING_LAZY}
319     *                    , {@link #GAP_HANDLING_MOVE_ITEMS_BETWEEN_SPANS} or
320     *                    {@link #GAP_HANDLING_NONE}
321     * @see #getGapStrategy()
322     */
323    public void setGapStrategy(int gapStrategy) {
324        assertNotInLayoutOrScroll(null);
325        if (mPendingSavedState != null && mPendingSavedState.mGapStrategy != gapStrategy) {
326            mPendingSavedState.mGapStrategy = gapStrategy;
327        }
328        if (gapStrategy == mGapStrategy) {
329            return;
330        }
331        if (gapStrategy != GAP_HANDLING_LAZY && gapStrategy != GAP_HANDLING_NONE &&
332                gapStrategy != GAP_HANDLING_MOVE_ITEMS_BETWEEN_SPANS) {
333            throw new IllegalArgumentException("invalid gap strategy. Must be GAP_HANDLING_NONE "
334                    + ", GAP_HANDLING_LAZY or GAP_HANDLING_MOVE_ITEMS_BETWEEN_SPANS");
335        }
336        mGapStrategy = gapStrategy;
337        requestLayout();
338    }
339
340    @Override
341    public void assertNotInLayoutOrScroll(String message) {
342        if (mPendingSavedState == null) {
343            super.assertNotInLayoutOrScroll(message);
344        }
345    }
346
347    /**
348     * Returns the number of spans laid out by StaggeredGridLayoutManager.
349     *
350     * @return Number of spans in the layout
351     */
352    public int getSpanCount() {
353        return mSpanCount;
354    }
355
356    /**
357     * For consistency, StaggeredGridLayoutManager keeps a mapping between spans and items.
358     * <p>
359     * If you need to cancel current assignments, you can call this method which will clear all
360     * assignments and request a new layout.
361     */
362    public void invalidateSpanAssignments() {
363        mLazySpanLookup.clear();
364        requestLayout();
365    }
366
367    private void ensureOrientationHelper() {
368        if (mPrimaryOrientation == null) {
369            mPrimaryOrientation = OrientationHelper.createOrientationHelper(this, mOrientation);
370            mSecondaryOrientation = OrientationHelper
371                    .createOrientationHelper(this, 1 - mOrientation);
372            mLayoutState = new LayoutState();
373        }
374    }
375
376    /**
377     * Calculates the views' layout order. (e.g. from end to start or start to end)
378     * RTL layout support is applied automatically. So if layout is RTL and
379     * {@link #getReverseLayout()} is {@code true}, elements will be laid out starting from left.
380     */
381    private void resolveShouldLayoutReverse() {
382        // A == B is the same result, but we rather keep it readable
383        if (mOrientation == VERTICAL || !isLayoutRTL()) {
384            mShouldReverseLayout = mReverseLayout;
385        } else {
386            mShouldReverseLayout = !mReverseLayout;
387        }
388    }
389
390    private boolean isLayoutRTL() {
391        return getLayoutDirection() == ViewCompat.LAYOUT_DIRECTION_RTL;
392    }
393
394    /**
395     * Returns whether views are laid out in reverse order or not.
396     * <p>
397     * Not that this value is not affected by RecyclerView's layout direction.
398     *
399     * @return True if layout is reversed, false otherwise
400     * @see #setReverseLayout(boolean)
401     */
402    public boolean getReverseLayout() {
403        return mReverseLayout;
404    }
405
406    @Override
407    public void onLayoutChildren(RecyclerView.Recycler recycler, RecyclerView.State state) {
408        ensureOrientationHelper();
409        // Update adapter size.
410        mLazySpanLookup.mAdapterSize = state.getItemCount();
411        int anchorItemPosition;
412        int anchorOffset;
413        // This value may change if we are jumping to a position.
414        boolean layoutFromEnd;
415
416        // If set to true, spans will clear their offsets and they'll be laid out from start
417        // depending on the layout direction. Invalidating span offsets is necessary to be able
418        // to jump to a position.
419        boolean invalidateSpanOffsets = false;
420
421        if (mPendingSavedState != null) {
422            if (DEBUG) {
423                Log.d(TAG, "found saved state: " + mPendingSavedState);
424            }
425            setOrientation(mPendingSavedState.mOrientation);
426            setSpanCount(mPendingSavedState.mSpanCount);
427            setGapStrategy(mPendingSavedState.mGapStrategy);
428            setReverseLayout(mPendingSavedState.mReverseLayout);
429            resolveShouldLayoutReverse();
430
431            if (mPendingSavedState.mAnchorPosition != RecyclerView.NO_POSITION) {
432                mPendingScrollPosition = mPendingSavedState.mAnchorPosition;
433                layoutFromEnd = mPendingSavedState.mAnchorLayoutFromEnd;
434            } else {
435                layoutFromEnd = mShouldReverseLayout;
436            }
437            if (mPendingSavedState.mHasSpanOffsets) {
438                for (int i = 0; i < mSpanCount; i++) {
439                    mSpans[i].clear();
440                    mSpans[i].setLine(mPendingSavedState.mSpanOffsets[i]);
441                }
442            }
443            if (mPendingSavedState.mSpanLookupSize > 1) {
444                mLazySpanLookup.mData = mPendingSavedState.mSpanLookup;
445            }
446
447        } else {
448            resolveShouldLayoutReverse();
449            layoutFromEnd = mShouldReverseLayout; // get updated value.
450        }
451
452        // Validate scroll position if exists.
453        if (mPendingScrollPosition != RecyclerView.NO_POSITION) {
454            // Validate it.
455            if (mPendingScrollPosition < 0 || mPendingScrollPosition >= state.getItemCount()) {
456                mPendingScrollPosition = RecyclerView.NO_POSITION;
457                mPendingScrollPositionOffset = INVALID_OFFSET;
458            }
459        }
460
461        if (mPendingScrollPosition != RecyclerView.NO_POSITION) {
462            if (mPendingSavedState == null
463                    || mPendingSavedState.mAnchorPosition == RecyclerView.NO_POSITION
464                    || !mPendingSavedState.mHasSpanOffsets) {
465                // If item is visible, make it fully visible.
466                final View child = findViewByPosition(mPendingScrollPosition);
467                if (child != null) {
468                    if (mPendingScrollPositionOffset != INVALID_OFFSET) {
469                        // Use regular anchor position.
470                        anchorItemPosition = mShouldReverseLayout ? getLastChildPosition()
471                                : getFirstChildPosition();
472                        if (layoutFromEnd) {
473                            final int target = mPrimaryOrientation.getEndAfterPadding() -
474                                    mPendingScrollPositionOffset;
475                            anchorOffset = target - mPrimaryOrientation.getDecoratedEnd(child);
476                        } else {
477                            final int target = mPrimaryOrientation.getStartAfterPadding() +
478                                    mPendingScrollPositionOffset;
479                            anchorOffset = target - mPrimaryOrientation.getDecoratedStart(child);
480                        }
481                    } else {
482                        final int startGap = mPrimaryOrientation.getDecoratedStart(child)
483                                - mPrimaryOrientation.getStartAfterPadding();
484                        final int endGap = mPrimaryOrientation.getEndAfterPadding() -
485                                mPrimaryOrientation.getDecoratedEnd(child);
486                        final int childSize = mPrimaryOrientation.getDecoratedMeasurement(child);
487                        // Use regular anchor item, just offset the layout.
488                        anchorItemPosition = mShouldReverseLayout ? getLastChildPosition()
489                                : getFirstChildPosition();
490                        if (childSize > mPrimaryOrientation.getTotalSpace()) {
491                            // Item does not fit. Fix depending on layout direction.
492                            anchorOffset = layoutFromEnd ? mPrimaryOrientation.getEndAfterPadding()
493                                    : mPrimaryOrientation.getStartAfterPadding();
494                        } else if (startGap < 0) {
495                            anchorOffset = -startGap;
496                        } else if (endGap < 0) {
497                            anchorOffset = endGap;
498                        } else {
499                            // Nothing to do, just layout normal.
500                            anchorItemPosition = mShouldReverseLayout ? getLastChildPosition()
501                                    : getFirstChildPosition();
502                            anchorOffset = INVALID_OFFSET;
503                        }
504                    }
505                } else {
506                    // Child is not visible. Set anchor coordinate depending on in which direction
507                    // child will be visible.
508                    anchorItemPosition = mPendingScrollPosition;
509                    if (mPendingScrollPositionOffset == INVALID_OFFSET) {
510                        final int position = calculateScrollDirectionForPosition(
511                                anchorItemPosition);
512                        if (position == LAYOUT_START) {
513                            anchorOffset = mPrimaryOrientation.getStartAfterPadding();
514                            layoutFromEnd = false;
515                        } else {
516                            anchorOffset = mPrimaryOrientation.getEndAfterPadding();
517                            layoutFromEnd = true;
518                        }
519                    } else {
520                        if (layoutFromEnd) {
521                            anchorOffset = mPrimaryOrientation.getEndAfterPadding()
522                                    - mPendingScrollPositionOffset;
523                        } else {
524                            anchorOffset = mPrimaryOrientation.getStartAfterPadding()
525                                    + mPendingScrollPositionOffset;
526                        }
527                    }
528                    invalidateSpanOffsets = true;
529                }
530            } else {
531                anchorOffset = INVALID_OFFSET;
532                anchorItemPosition = mPendingScrollPosition;
533            }
534
535        } else {
536            // We don't recycle views out of adapter order. This way, we can rely on the first or
537            // last child as the anchor position.
538            anchorItemPosition = mShouldReverseLayout
539                    ? findLastReferenceChildPosition(state.getItemCount())
540                    : findFirstReferenceChildPosition(state.getItemCount());
541            anchorOffset = INVALID_OFFSET;
542        }
543        if (getChildCount() > 0 && (mPendingSavedState == null ||
544                !mPendingSavedState.mHasSpanOffsets)) {
545            if (invalidateSpanOffsets || mHasGaps) {
546                for (int i = 0; i < mSpanCount; i++) {
547                    // Scroll to position is set, clear.
548                    mSpans[i].clear();
549                    if (anchorOffset != INVALID_OFFSET) {
550                        mSpans[i].setLine(anchorOffset);
551                    }
552                }
553            } else {
554                for (int i = 0; i < mSpanCount; i++) {
555                    mSpans[i].cacheReferenceLineAndClear(mShouldReverseLayout, anchorOffset);
556                }
557                if (DEBUG) {
558                    for (int i = 0; i < mSpanCount; i++) {
559                        Log.d(TAG, "cached start-end lines for " + i + ":" +
560                                mSpans[i].mCachedStart + ":" + mSpans[i].mCachedEnd);
561                    }
562                }
563            }
564        }
565        mSizePerSpan = mSecondaryOrientation.getTotalSpace() / mSpanCount;
566        detachAndScrapAttachedViews(recycler);
567        // Layout start.
568        updateLayoutStateToFillStart(anchorItemPosition, state);
569        if (!layoutFromEnd) {
570            mLayoutState.mCurrentPosition += mLayoutState.mItemDirection;
571        }
572        fill(recycler, mLayoutState, state);
573
574        // Layout end.
575        updateLayoutStateToFillEnd(anchorItemPosition, state);
576        if (layoutFromEnd) {
577            mLayoutState.mCurrentPosition += mLayoutState.mItemDirection;
578        }
579        fill(recycler, mLayoutState, state);
580
581        if (getChildCount() > 0) {
582            if (mShouldReverseLayout) {
583                fixEndGap(recycler, state, true);
584                fixStartGap(recycler, state, false);
585            } else {
586                fixStartGap(recycler, state, true);
587                fixEndGap(recycler, state, false);
588            }
589        }
590
591        mPendingScrollPosition = RecyclerView.NO_POSITION;
592        mPendingScrollPositionOffset = INVALID_OFFSET;
593        mLastLayoutFromEnd = layoutFromEnd;
594        mPendingSavedState = null; // we don't need this anymore
595    }
596
597    /**
598     * Checks if a child is assigned to the non-optimal span.
599     *
600     * @param startChildIndex Starts checking after this child, inclusive
601     * @param endChildIndex   Starts checking until this child, exclusive
602     * @return The first View that is assigned to the wrong span.
603     */
604    View hasGapsToFix(int startChildIndex, int endChildIndex) {
605        // quick reject
606        if (startChildIndex >= endChildIndex) {
607            return null;
608        }
609        final int firstChildIndex, childLimit;
610        final int nextSpanDiff = mOrientation == VERTICAL && isLayoutRTL() ? 1 : -1;
611
612        if (mShouldReverseLayout) {
613            firstChildIndex = endChildIndex - 1;
614            childLimit = startChildIndex - 1;
615        } else {
616            firstChildIndex = startChildIndex;
617            childLimit = endChildIndex;
618        }
619        final int nextChildDiff = firstChildIndex < childLimit ? 1 : -1;
620        for (int i = firstChildIndex; i != childLimit; i += nextChildDiff) {
621            View child = getChildAt(i);
622            final int start = mPrimaryOrientation.getDecoratedStart(child);
623            final int end = mPrimaryOrientation.getDecoratedEnd(child);
624            LayoutParams layoutParams = (LayoutParams) child.getLayoutParams();
625            if (layoutParams.mFullSpan) {
626                continue; // quick reject
627            }
628            int nextSpanIndex = layoutParams.getSpanIndex() + nextSpanDiff;
629            while (nextSpanIndex >= 0 && nextSpanIndex < mSpanCount) {
630                Span nextSpan = mSpans[nextSpanIndex];
631                if (nextSpan.isEmpty(start, end)) {
632                    return child;
633                }
634                nextSpanIndex += nextSpanDiff;
635            }
636        }
637        // everything looks good
638        return null;
639    }
640
641    @Override
642    public boolean supportsPredictiveItemAnimations() {
643        return true;
644    }
645
646    /**
647     * Returns the adapter position of the first visible view for each span.
648     * <p>
649     * Note that, this value is not affected by layout orientation or item order traversal.
650     * ({@link #setReverseLayout(boolean)}). Views are sorted by their positions in the adapter,
651     * not in the layout.
652     * <p>
653     * If RecyclerView has item decorators, they will be considered in calculations as well.
654     * <p>
655     * StaggeredGridLayoutManager may pre-cache some views that are not necessarily visible. Those
656     * views are ignored in this method.
657     *
658     * @return The adapter position of the first visible item in each span. If a span does not have
659     * any items, {@link RecyclerView#NO_POSITION} is returned for that span.
660     *
661     * @param into An array to put the results into. If you don't provide any, LayoutManager will
662     *             create a new one.
663     * @see #findFirstCompletelyVisibleItemPositions(int[])
664     * @see #findLastVisibleItemPositions(int[])
665     */
666    public int[] findFirstVisibleItemPositions(int[] into) {
667        if (into == null) {
668            into = new int[mSpanCount];
669        } else if (into.length < mSpanCount) {
670            throw new IllegalArgumentException("Provided int[]'s size must be more than or equal"
671                    + " to span count. Expected:" + mSpanCount + ", array size:" + into.length);
672        }
673        for (int i = 0; i < mSpanCount; i ++) {
674            into[i] = mSpans[i].findFirstVisibleItemPosition();
675        }
676        return into;
677    }
678
679    /**
680     * Returns the adapter position of the first completely visible view for each span.
681     * <p>
682     * Note that, this value is not affected by layout orientation or item order traversal.
683     * ({@link #setReverseLayout(boolean)}). Views are sorted by their positions in the adapter,
684     * not in the layout.
685     * <p>
686     * If RecyclerView has item decorators, they will be considered in calculations as well.
687     * <p>
688     * StaggeredGridLayoutManager may pre-cache some views that are not necessarily visible. Those
689     * views are ignored in this method.
690     *
691     * @return The adapter position of the first fully visible item in each span. If a span does
692     * not have any items, {@link RecyclerView#NO_POSITION} is returned for that span.
693     * @param into An array to put the results into. If you don't provide any, LayoutManager will
694     *             create a new one.
695     * @see #findFirstVisibleItemPositions(int[])
696     * @see #findLastCompletelyVisibleItemPositions(int[])
697     */
698    public int[] findFirstCompletelyVisibleItemPositions(int[] into) {
699        if (into == null) {
700            into = new int[mSpanCount];
701        } else if (into.length < mSpanCount) {
702            throw new IllegalArgumentException("Provided int[]'s size must be more than or equal"
703                    + " to span count. Expected:" + mSpanCount + ", array size:" + into.length);
704        }
705        for (int i = 0; i < mSpanCount; i ++) {
706            into[i] = mSpans[i].findFirstCompletelyVisibleItemPosition();
707        }
708        return into;
709    }
710
711    /**
712     * Returns the adapter position of the last visible view for each span.
713     * <p>
714     * Note that, this value is not affected by layout orientation or item order traversal.
715     * ({@link #setReverseLayout(boolean)}). Views are sorted by their positions in the adapter,
716     * not in the layout.
717     * <p>
718     * If RecyclerView has item decorators, they will be considered in calculations as well.
719     * <p>
720     * StaggeredGridLayoutManager may pre-cache some views that are not necessarily visible. Those
721     * views are ignored in this method.
722     *
723     * @return The adapter position of the last visible item in each span. If a span does not have
724     * any items, {@link RecyclerView#NO_POSITION} is returned for that span.
725     *
726     * @param into An array to put the results into. If you don't provide any, LayoutManager will
727     *             create a new one.
728     * @see #findLastCompletelyVisibleItemPositions(int[])
729     * @see #findFirstVisibleItemPositions(int[])
730     */
731    public int[] findLastVisibleItemPositions(int[] into) {
732        if (into == null) {
733            into = new int[mSpanCount];
734        } else if (into.length < mSpanCount) {
735            throw new IllegalArgumentException("Provided int[]'s size must be more than or equal"
736                    + " to span count. Expected:" + mSpanCount + ", array size:" + into.length);
737        }
738        for (int i = 0; i < mSpanCount; i ++) {
739            into[i] = mSpans[i].findLastVisibleItemPosition();
740        }
741        return into;
742    }
743
744    /**
745     * Returns the adapter position of the last completely visible view for each span.
746     * <p>
747     * Note that, this value is not affected by layout orientation or item order traversal.
748     * ({@link #setReverseLayout(boolean)}). Views are sorted by their positions in the adapter,
749     * not in the layout.
750     * <p>
751     * If RecyclerView has item decorators, they will be considered in calculations as well.
752     * <p>
753     * StaggeredGridLayoutManager may pre-cache some views that are not necessarily visible. Those
754     * views are ignored in this method.
755     *
756     * @return The adapter position of the last fully visible item in each span. If a span does not
757     * have any items, {@link RecyclerView#NO_POSITION} is returned for that span.
758     *
759     * @param into An array to put the results into. If you don't provide any, LayoutManager will
760     *             create a new one.
761     * @see #findFirstCompletelyVisibleItemPositions(int[])
762     * @see #findLastVisibleItemPositions(int[])
763     */
764    public int[] findLastCompletelyVisibleItemPositions(int[] into) {
765        if (into == null) {
766            into = new int[mSpanCount];
767        } else if (into.length < mSpanCount) {
768            throw new IllegalArgumentException("Provided int[]'s size must be more than or equal"
769                    + " to span count. Expected:" + mSpanCount + ", array size:" + into.length);
770        }
771        for (int i = 0; i < mSpanCount; i ++) {
772            into[i] = mSpans[i].findLastCompletelyVisibleItemPosition();
773        }
774        return into;
775    }
776
777    private void measureChildWithDecorationsAndMargin(View child, int widthSpec,
778            int heightSpec) {
779        final Rect insets = mRecyclerView.getItemDecorInsetsForChild(child);
780        LayoutParams lp = (LayoutParams) child.getLayoutParams();
781        widthSpec = updateSpecWithExtra(widthSpec, lp.leftMargin + insets.left,
782                lp.rightMargin + insets.right);
783        heightSpec = updateSpecWithExtra(heightSpec, lp.topMargin + insets.top,
784                lp.bottomMargin + insets.bottom);
785        child.measure(widthSpec, heightSpec);
786    }
787
788    private int updateSpecWithExtra(int spec, int startInset, int endInset) {
789        if (startInset == 0 && endInset == 0) {
790            return spec;
791        }
792        final int mode = View.MeasureSpec.getMode(spec);
793        if (mode == View.MeasureSpec.AT_MOST || mode == View.MeasureSpec.EXACTLY) {
794            return View.MeasureSpec.makeMeasureSpec(
795                    View.MeasureSpec.getSize(spec) - startInset - endInset, mode);
796        }
797        return spec;
798    }
799
800    @Override
801    public void onRestoreInstanceState(Parcelable state) {
802        if (state instanceof SavedState) {
803            mPendingSavedState = (SavedState) state;
804            requestLayout();
805        } else if (DEBUG) {
806            Log.d(TAG, "invalid saved state class");
807        }
808    }
809
810    @Override
811    public Parcelable onSaveInstanceState() {
812        if (mPendingSavedState != null) {
813            return new SavedState(mPendingSavedState);
814        }
815        SavedState state = new SavedState();
816        state.mOrientation = mOrientation;
817        state.mReverseLayout = mReverseLayout;
818        state.mSpanCount = mSpanCount;
819        state.mAnchorLayoutFromEnd = mLastLayoutFromEnd;
820        state.mGapStrategy = mGapStrategy;
821
822        if (mLazySpanLookup != null && mLazySpanLookup.mData != null) {
823            state.mSpanLookup = mLazySpanLookup.mData;
824            state.mSpanLookupSize = state.mSpanLookup.length;
825        } else {
826            state.mSpanLookupSize = 0;
827        }
828
829        if (getChildCount() > 0) {
830            state.mAnchorPosition = mLastLayoutFromEnd ? getLastChildPosition()
831                    : getFirstChildPosition();
832            state.mVisibleAnchorPosition = findFirstVisibleItemPositionInt();
833            state.mHasSpanOffsets = true;
834            state.mSpanOffsets = new int[mSpanCount];
835            for (int i = 0; i < mSpanCount; i++) {
836                state.mSpanOffsets[i] = mLastLayoutFromEnd ? mSpans[i].getEndLine()
837                        : mSpans[i].getStartLine();
838            }
839        } else {
840            state.mAnchorPosition = RecyclerView.NO_POSITION;
841            state.mVisibleAnchorPosition = RecyclerView.NO_POSITION;
842            state.mHasSpanOffsets = false;
843        }
844        if (DEBUG) {
845            Log.d(TAG, "saved state:\n" + state);
846        }
847        return state;
848    }
849
850    /**
851     * Finds the first fully visible child to be used as an anchor child if span count changes when
852     * state is restored.
853     */
854    int findFirstVisibleItemPositionInt() {
855        final int start, end, diff;
856        if (mLastLayoutFromEnd) {
857            start = getChildCount() - 1;
858            end = -1;
859            diff = -1;
860        } else {
861            start = 0;
862            end = getChildCount();
863            diff = 1;
864        }
865        final int boundsStart = mPrimaryOrientation.getStartAfterPadding();
866        final int boundsEnd = mPrimaryOrientation.getEndAfterPadding();
867        for (int i = start; i != end; i += diff) {
868            final View child = getChildAt(i);
869            if (mPrimaryOrientation.getDecoratedStart(child) >= boundsStart
870                    && mPrimaryOrientation.getDecoratedEnd(child) <= boundsEnd) {
871                return getPosition(child);
872            }
873        }
874        return RecyclerView.NO_POSITION;
875    }
876
877    private void fixEndGap(RecyclerView.Recycler recycler, RecyclerView.State state,
878            boolean canOffsetChildren) {
879        final int maxEndLine = getMaxEnd(mPrimaryOrientation.getEndAfterPadding());
880        int gap = mPrimaryOrientation.getEndAfterPadding() - maxEndLine;
881        int fixOffset;
882        if (gap > 0) {
883            fixOffset = -scrollBy(-gap, recycler, state);
884        } else {
885            return; // nothing to fix
886        }
887        gap -= fixOffset;
888        if (canOffsetChildren && gap > 0) {
889            mPrimaryOrientation.offsetChildren(gap);
890        }
891    }
892
893    private void fixStartGap(RecyclerView.Recycler recycler, RecyclerView.State state,
894            boolean canOffsetChildren) {
895        final int minStartLine = getMinStart(mPrimaryOrientation.getStartAfterPadding());
896        int gap = minStartLine - mPrimaryOrientation.getStartAfterPadding();
897        int fixOffset;
898        if (gap > 0) {
899            fixOffset = scrollBy(gap, recycler, state);
900        } else {
901            return; // nothing to fix
902        }
903        gap -= fixOffset;
904        if (canOffsetChildren && gap > 0) {
905            mPrimaryOrientation.offsetChildren(-gap);
906        }
907    }
908
909    private void updateLayoutStateToFillStart(int anchorPosition, RecyclerView.State state) {
910        mLayoutState.mAvailable = 0;
911        mLayoutState.mCurrentPosition = anchorPosition;
912        if (isSmoothScrolling()) {
913            final int targetPos = state.getTargetScrollPosition();
914            if (mShouldReverseLayout == targetPos < anchorPosition) {
915                mLayoutState.mExtra = 0;
916            } else {
917                mLayoutState.mExtra = mPrimaryOrientation.getTotalSpace();
918            }
919        } else {
920            mLayoutState.mExtra = 0;
921        }
922        mLayoutState.mLayoutDirection = LAYOUT_START;
923        mLayoutState.mItemDirection = mShouldReverseLayout ? ITEM_DIRECTION_TAIL
924                : ITEM_DIRECTION_HEAD;
925    }
926
927    private void updateLayoutStateToFillEnd(int anchorPosition, RecyclerView.State state) {
928        mLayoutState.mAvailable = 0;
929        mLayoutState.mCurrentPosition = anchorPosition;
930        if (isSmoothScrolling()) {
931            final int targetPos = state.getTargetScrollPosition();
932            if (mShouldReverseLayout == targetPos > anchorPosition) {
933                mLayoutState.mExtra = 0;
934            } else {
935                mLayoutState.mExtra = mPrimaryOrientation.getTotalSpace();
936            }
937        } else {
938            mLayoutState.mExtra = 0;
939        }
940        mLayoutState.mLayoutDirection = LAYOUT_END;
941        mLayoutState.mItemDirection = mShouldReverseLayout ? ITEM_DIRECTION_HEAD
942                : ITEM_DIRECTION_TAIL;
943    }
944
945    @Override
946    public void offsetChildrenHorizontal(int dx) {
947        super.offsetChildrenHorizontal(dx);
948        for (int i = 0; i < mSpanCount; i++) {
949            mSpans[i].onOffset(dx);
950        }
951    }
952
953    @Override
954    public void offsetChildrenVertical(int dy) {
955        super.offsetChildrenVertical(dy);
956        for (int i = 0; i < mSpanCount; i++) {
957            mSpans[i].onOffset(dy);
958        }
959    }
960
961    @Override
962    public void onItemsRemoved(RecyclerView recyclerView, int positionStart, int itemCount) {
963        if (!considerSpanInvalidate(positionStart, itemCount)) {
964            // If positions are not invalidated, move span offsets.
965            mLazySpanLookup.offsetForRemoval(positionStart, itemCount);
966        }
967    }
968
969    @Override
970    public void onItemsAdded(RecyclerView recyclerView, int positionStart, int itemCount) {
971        if (!considerSpanInvalidate(positionStart, itemCount)) {
972            // If positions are not invalidated, move span offsets.
973            mLazySpanLookup.offsetForAddition(positionStart, itemCount);
974        }
975    }
976
977    /**
978     * Checks whether it should invalidate span assignments in response to an adapter change.
979     */
980    private boolean considerSpanInvalidate(int positionStart, int itemCount) {
981        int minPosition = mShouldReverseLayout ? getLastChildPosition() : getFirstChildPosition();
982        if (positionStart + itemCount <= minPosition) {
983            return false;// nothing to update.
984        }
985        int maxPosition = mShouldReverseLayout ? getFirstChildPosition() : getLastChildPosition();
986        mLazySpanLookup.invalidateAfter(positionStart);
987        if (positionStart <= maxPosition) {
988            requestLayout();
989        }
990        return true;
991    }
992
993    private int fill(RecyclerView.Recycler recycler, LayoutState layoutState,
994            RecyclerView.State state) {
995        mRemainingSpans.set(0, mSpanCount, true);
996        // The target position we are trying to reach.
997        final int targetLine;
998
999        /*
1000        * The line until which we can recycle, as long as we add views.
1001        * Keep in mind, it is still the line in layout direction which means; to calculate the
1002        * actual recycle line, we should subtract/add the size in orientation.
1003        */
1004        final int recycleLine;
1005        // Line of the furthest row.
1006        if (layoutState.mLayoutDirection == LAYOUT_END) {
1007            // ignore padding for recycler
1008            recycleLine = mPrimaryOrientation.getEndAfterPadding() + mLayoutState.mAvailable;
1009            targetLine = recycleLine + mLayoutState.mExtra + mPrimaryOrientation.getEndPadding();
1010            final int defaultLine = mPrimaryOrientation.getStartAfterPadding();
1011            for (int i = 0; i < mSpanCount; i++) {
1012                final Span span = mSpans[i];
1013                final int line = span.getEndLine(defaultLine);
1014                if (line > targetLine) {
1015                    mRemainingSpans.set(i, false);
1016                }
1017            }
1018        } else { // LAYOUT_START
1019            // ignore padding for recycler
1020            recycleLine = mPrimaryOrientation.getStartAfterPadding() - mLayoutState.mAvailable;
1021            targetLine = recycleLine - mLayoutState.mExtra -
1022                    mPrimaryOrientation.getStartAfterPadding();
1023            for (int i = 0; i < mSpanCount; i++) {
1024                final Span span = mSpans[i];
1025                final int defaultLine = mPrimaryOrientation.getEndAfterPadding();
1026                final int line = span.getStartLine(defaultLine);
1027                if (line < targetLine) {
1028                    mRemainingSpans.set(i, false);
1029                }
1030            }
1031        }
1032
1033        final int widthSpec, heightSpec;
1034        if (mOrientation == VERTICAL) {
1035            widthSpec = View.MeasureSpec.makeMeasureSpec(mSizePerSpan, View.MeasureSpec.EXACTLY);
1036            heightSpec = View.MeasureSpec.makeMeasureSpec(0, View.MeasureSpec.UNSPECIFIED);
1037        } else {
1038            heightSpec = View.MeasureSpec.makeMeasureSpec(mSizePerSpan, View.MeasureSpec.EXACTLY);
1039            widthSpec = View.MeasureSpec.makeMeasureSpec(0, View.MeasureSpec.UNSPECIFIED);
1040        }
1041
1042        while (layoutState.hasMore(state) && !mRemainingSpans.isEmpty()) {
1043            View view = layoutState.next(recycler);
1044            LayoutParams lp = ((LayoutParams) view.getLayoutParams());
1045            if (layoutState.mLayoutDirection == LAYOUT_END) {
1046                addView(view);
1047            } else {
1048                addView(view, 0);
1049            }
1050            if (lp.mFullSpan) {
1051                final int fullSizeSpec = View.MeasureSpec.makeMeasureSpec(
1052                        mSecondaryOrientation.getTotalSpace(), View.MeasureSpec.EXACTLY);
1053                if (mOrientation == VERTICAL) {
1054                    measureChildWithDecorationsAndMargin(view, fullSizeSpec, heightSpec);
1055                } else {
1056                    measureChildWithDecorationsAndMargin(view, widthSpec, fullSizeSpec);
1057                }
1058            } else {
1059                measureChildWithDecorationsAndMargin(view, widthSpec, heightSpec);
1060            }
1061
1062            final int position = getPosition(view);
1063            final int spanIndex = mLazySpanLookup.getSpan(position);
1064            Span currentSpan;
1065            if (spanIndex == LayoutParams.INVALID_SPAN_ID) {
1066                if (lp.mFullSpan) {
1067                    // assign full span items to first span
1068                    currentSpan = mSpans[0];
1069                } else {
1070                    currentSpan = getNextSpan(layoutState);
1071                }
1072                mLazySpanLookup.setSpan(position, currentSpan);
1073            } else {
1074                currentSpan = mSpans[spanIndex];
1075            }
1076            final int start;
1077            final int end;
1078            if (layoutState.mLayoutDirection == LAYOUT_END) {
1079                final int def = mShouldReverseLayout ? mPrimaryOrientation.getEndAfterPadding()
1080                        : mPrimaryOrientation.getStartAfterPadding();
1081                start = lp.mFullSpan ? getMaxEnd(def) : currentSpan.getEndLine(def);
1082                end = start + mPrimaryOrientation.getDecoratedMeasurement(view);
1083                if (lp.mFullSpan) {
1084                    for (int i = 0; i < mSpanCount; i++) {
1085                        mSpans[i].appendToSpan(view);
1086                    }
1087                } else {
1088                    currentSpan.appendToSpan(view);
1089                }
1090            } else {
1091                final int def = mShouldReverseLayout ? mPrimaryOrientation.getEndAfterPadding()
1092                        : mPrimaryOrientation.getStartAfterPadding();
1093                end = lp.mFullSpan ? getMinStart(def) : currentSpan.getStartLine(def);
1094                start = end - mPrimaryOrientation.getDecoratedMeasurement(view);
1095                if (lp.mFullSpan) {
1096                    for (int i = 0; i < mSpanCount; i++) {
1097                        mSpans[i].prependToSpan(view);
1098                    }
1099                } else {
1100                    currentSpan.prependToSpan(view);
1101                }
1102
1103            }
1104            lp.mSpan = currentSpan;
1105
1106            if (DEBUG) {
1107                Log.d(TAG, "adding view item " + lp.getViewPosition() + " between " + start + ","
1108                        + end);
1109            }
1110
1111            final int otherStart = lp.mFullSpan ? mSecondaryOrientation.getStartAfterPadding()
1112                    : currentSpan.mIndex * mSizePerSpan + mSecondaryOrientation
1113                            .getStartAfterPadding();
1114            final int otherEnd = otherStart + mSecondaryOrientation.getDecoratedMeasurement(view);
1115            if (mOrientation == VERTICAL) {
1116                layoutDecoratedWithMargins(view, otherStart, start, otherEnd, end);
1117            } else {
1118                layoutDecoratedWithMargins(view, start, otherStart, end, otherEnd);
1119            }
1120            if (lp.mFullSpan) {
1121                for (int i = 0; i < mSpanCount; i++) {
1122                    updateRemainingSpans(mSpans[i], mLayoutState.mLayoutDirection, targetLine);
1123                }
1124            } else {
1125                updateRemainingSpans(currentSpan, mLayoutState.mLayoutDirection, targetLine);
1126            }
1127            if (mLayoutState.mLayoutDirection == LAYOUT_START) {
1128                // calculate recycle line
1129                int maxStart = getMaxStart(currentSpan.getStartLine());
1130                recycleFromEnd(recycler, Math.max(recycleLine, maxStart) +
1131                        (mPrimaryOrientation.getEnd() - mPrimaryOrientation.getStartAfterPadding()));
1132            } else {
1133                // calculate recycle line
1134                int minEnd = getMinEnd(currentSpan.getEndLine());
1135                recycleFromStart(recycler, Math.min(recycleLine, minEnd) -
1136                        (mPrimaryOrientation.getEnd() - mPrimaryOrientation.getStartAfterPadding()));
1137            }
1138        }
1139        if (DEBUG) {
1140            Log.d(TAG, "fill, " + getChildCount());
1141        }
1142        if (mLayoutState.mLayoutDirection == LAYOUT_START) {
1143            final int minStart = getMinStart(mPrimaryOrientation.getStartAfterPadding());
1144            return Math.max(0, mLayoutState.mAvailable + (recycleLine - minStart));
1145        } else {
1146            final int max = getMaxEnd(mPrimaryOrientation.getEndAfterPadding());
1147            return Math.max(0, mLayoutState.mAvailable + (max - recycleLine));
1148        }
1149    }
1150
1151    private void layoutDecoratedWithMargins(View child, int left, int top, int right,
1152            int bottom) {
1153        LayoutParams lp = (LayoutParams) child.getLayoutParams();
1154        layoutDecorated(child, left + lp.leftMargin, top + lp.topMargin, right - lp.rightMargin
1155                , bottom - lp.bottomMargin);
1156    }
1157
1158    private void updateRemainingSpans(Span span, int layoutDir, int targetLine) {
1159        final int deletedSize = span.getDeletedSize();
1160        if (layoutDir == LAYOUT_START) {
1161            final int line = span.getStartLine();
1162            if (line + deletedSize < targetLine) {
1163                mRemainingSpans.set(span.mIndex, false);
1164            }
1165        } else {
1166            final int line = span.getEndLine();
1167            if (line - deletedSize > targetLine) {
1168                mRemainingSpans.set(span.mIndex, false);
1169            }
1170        }
1171    }
1172
1173    private int getMaxStart(int def) {
1174        int maxStart = mSpans[0].getStartLine(def);
1175        for (int i = 1; i < mSpanCount; i++) {
1176            final int spanStart = mSpans[i].getStartLine(def);
1177            if (spanStart > maxStart) {
1178                maxStart = spanStart;
1179            }
1180        }
1181        return maxStart;
1182    }
1183
1184    private int getMinStart(int def) {
1185        int minStart = mSpans[0].getStartLine(def);
1186        for (int i = 1; i < mSpanCount; i++) {
1187            final int spanStart = mSpans[i].getStartLine(def);
1188            if (spanStart < minStart) {
1189                minStart = spanStart;
1190            }
1191        }
1192        return minStart;
1193    }
1194
1195    private int getMaxEnd(int def) {
1196        int maxEnd = mSpans[0].getEndLine(def);
1197        for (int i = 1; i < mSpanCount; i++) {
1198            final int spanEnd = mSpans[i].getEndLine(def);
1199            if (spanEnd > maxEnd) {
1200                maxEnd = spanEnd;
1201            }
1202        }
1203        return maxEnd;
1204    }
1205
1206    private int getMinEnd(int def) {
1207        int minEnd = mSpans[0].getEndLine(def);
1208        for (int i = 1; i < mSpanCount; i++) {
1209            final int spanEnd = mSpans[i].getEndLine(def);
1210            if (spanEnd < minEnd) {
1211                minEnd = spanEnd;
1212            }
1213        }
1214        return minEnd;
1215    }
1216
1217    private void recycleFromStart(RecyclerView.Recycler recycler, int line) {
1218        if (DEBUG) {
1219            Log.d(TAG, "recycling from start for line " + line);
1220        }
1221        while (getChildCount() > 0) {
1222            View child = getChildAt(0);
1223            if (mPrimaryOrientation.getDecoratedEnd(child) < line) {
1224                LayoutParams lp = (LayoutParams) child.getLayoutParams();
1225                if (lp.mFullSpan) {
1226                    for (int j = 0; j < mSpanCount; j++) {
1227                        mSpans[j].popStart();
1228                    }
1229                } else {
1230                    lp.mSpan.popStart();
1231                }
1232                removeAndRecycleView(child, recycler);
1233            } else {
1234                return;// done
1235            }
1236        }
1237    }
1238
1239    private void recycleFromEnd(RecyclerView.Recycler recycler, int line) {
1240        final int childCount = getChildCount();
1241        int i;
1242        for (i = childCount - 1; i >= 0; i--) {
1243            View child = getChildAt(i);
1244            if (mPrimaryOrientation.getDecoratedStart(child) > line) {
1245                LayoutParams lp = (LayoutParams) child.getLayoutParams();
1246                if (lp.mFullSpan) {
1247                    for (int j = 0; j < mSpanCount; j++) {
1248                        mSpans[j].popEnd();
1249                    }
1250                } else {
1251                    lp.mSpan.popEnd();
1252                }
1253                removeAndRecycleView(child, recycler);
1254            } else {
1255                return;// done
1256            }
1257        }
1258    }
1259
1260    /**
1261     * Finds the span for the next view.
1262     */
1263    private Span getNextSpan(LayoutState layoutState) {
1264        final boolean preferLastSpan = mOrientation == VERTICAL && isLayoutRTL();
1265        if (layoutState.mLayoutDirection == LAYOUT_END) {
1266            Span min = mSpans[0];
1267            int minLine = min.getEndLine(mPrimaryOrientation.getStartAfterPadding());
1268            final int defaultLine = mPrimaryOrientation.getStartAfterPadding();
1269            for (int i = 1; i < mSpanCount; i++) {
1270                final Span other = mSpans[i];
1271                final int otherLine = other.getEndLine(defaultLine);
1272                if (otherLine < minLine || (otherLine == minLine && preferLastSpan)) {
1273                    min = other;
1274                    minLine = otherLine;
1275                }
1276            }
1277            return min;
1278        } else {
1279            Span max = mSpans[0];
1280            int maxLine = max.getStartLine(mPrimaryOrientation.getEndAfterPadding());
1281            final int defaultLine = mPrimaryOrientation.getEndAfterPadding();
1282            for (int i = 1; i < mSpanCount; i++) {
1283                final Span other = mSpans[i];
1284                final int otherLine = other.getStartLine(defaultLine);
1285                if (otherLine > maxLine || (otherLine == maxLine && !preferLastSpan)) {
1286                    max = other;
1287                    maxLine = otherLine;
1288                }
1289            }
1290            return max;
1291        }
1292    }
1293
1294    @Override
1295    public boolean canScrollVertically() {
1296        return mOrientation == VERTICAL;
1297    }
1298
1299    @Override
1300    public boolean canScrollHorizontally() {
1301        return mOrientation == HORIZONTAL;
1302    }
1303
1304    @Override
1305    public int scrollHorizontallyBy(int dx, RecyclerView.Recycler recycler,
1306            RecyclerView.State state) {
1307        return scrollBy(dx, recycler, state);
1308    }
1309
1310    @Override
1311    public int scrollVerticallyBy(int dy, RecyclerView.Recycler recycler,
1312            RecyclerView.State state) {
1313        return scrollBy(dy, recycler, state);
1314    }
1315
1316    private int calculateScrollDirectionForPosition(int position) {
1317        if (getChildCount() == 0) {
1318            return mShouldReverseLayout ? LAYOUT_END : LAYOUT_START;
1319        }
1320        final int firstChildPos = getFirstChildPosition();
1321        return position < firstChildPos != mShouldReverseLayout ? LAYOUT_START : LAYOUT_END;
1322    }
1323
1324    @Override
1325    public void smoothScrollToPosition(RecyclerView recyclerView, RecyclerView.State state,
1326            int position) {
1327        LinearSmoothScroller scroller = new LinearSmoothScroller(recyclerView.getContext()) {
1328            @Override
1329            public PointF computeScrollVectorForPosition(int targetPosition) {
1330                final int direction = calculateScrollDirectionForPosition(targetPosition);
1331                if (direction == 0) {
1332                    return null;
1333                }
1334                if (mOrientation == HORIZONTAL) {
1335                    return new PointF(direction, 0);
1336                } else {
1337                    return new PointF(0, direction);
1338                }
1339            }
1340        };
1341        scroller.setTargetPosition(position);
1342        startSmoothScroll(scroller);
1343    }
1344
1345    @Override
1346    public void scrollToPosition(int position) {
1347        if (mPendingSavedState != null && mPendingSavedState.mAnchorPosition != position) {
1348            mPendingSavedState.invalidateAnchorPositionInfo();
1349        }
1350        mPendingScrollPosition = position;
1351        mPendingScrollPositionOffset = INVALID_OFFSET;
1352        requestLayout();
1353    }
1354
1355    /**
1356     * Scroll to the specified adapter position with the given offset from layout start.
1357     * <p>
1358     * Note that scroll position change will not be reflected until the next layout call.
1359     * <p>
1360     * If you are just trying to make a position visible, use {@link #scrollToPosition(int)}.
1361     *
1362     * @param position Index (starting at 0) of the reference item.
1363     * @param offset   The distance (in pixels) between the start edge of the item view and
1364     *                 start edge of the RecyclerView.
1365     * @see #setReverseLayout(boolean)
1366     * @see #scrollToPosition(int)
1367     */
1368    public void scrollToPositionWithOffset(int position, int offset) {
1369        if (mPendingSavedState != null) {
1370            mPendingSavedState.invalidateAnchorPositionInfo();
1371        }
1372        mPendingScrollPosition = position;
1373        mPendingScrollPositionOffset = offset;
1374        requestLayout();
1375    }
1376
1377    private int scrollBy(int dt, RecyclerView.Recycler recycler, RecyclerView.State state) {
1378        ensureOrientationHelper();
1379        final int referenceChildPosition;
1380        if (dt > 0) { // layout towards end
1381            mLayoutState.mLayoutDirection = LAYOUT_END;
1382            mLayoutState.mItemDirection = mShouldReverseLayout ? ITEM_DIRECTION_HEAD
1383                    : ITEM_DIRECTION_TAIL;
1384            referenceChildPosition = getLastChildPosition();
1385        } else {
1386            mLayoutState.mLayoutDirection = LAYOUT_START;
1387            mLayoutState.mItemDirection = mShouldReverseLayout ? ITEM_DIRECTION_TAIL
1388                    : ITEM_DIRECTION_HEAD;
1389            referenceChildPosition = getFirstChildPosition();
1390        }
1391        mLayoutState.mCurrentPosition = referenceChildPosition + mLayoutState.mItemDirection;
1392        final int absDt = Math.abs(dt);
1393        mLayoutState.mAvailable = absDt;
1394        mLayoutState.mExtra = isSmoothScrolling() ? mPrimaryOrientation.getTotalSpace() : 0;
1395        int consumed = fill(recycler, mLayoutState, state);
1396        final int totalScroll;
1397        if (absDt < consumed) {
1398            totalScroll = dt;
1399        } else if (dt < 0) {
1400            totalScroll = -consumed;
1401        } else { // dt > 0
1402            totalScroll = consumed;
1403        }
1404        if (DEBUG) {
1405            Log.d(TAG, "asked " + dt + " scrolled" + totalScroll);
1406        }
1407
1408        if (mGapStrategy == GAP_HANDLING_LAZY
1409                && mLayoutState.mItemDirection == ITEM_DIRECTION_HEAD) {
1410            final int targetStart = mPrimaryOrientation.getStartAfterPadding();
1411            final int targetEnd = mPrimaryOrientation.getEndAfterPadding();
1412            lazyOffsetSpans(-totalScroll, targetStart, targetEnd);
1413        } else {
1414            mPrimaryOrientation.offsetChildren(-totalScroll);
1415        }
1416        // always reset this if we scroll for a proper save instance state
1417        mLastLayoutFromEnd = mShouldReverseLayout;
1418
1419        if (totalScroll != 0 && mGapStrategy != GAP_HANDLING_NONE
1420                && mLayoutState.mItemDirection == ITEM_DIRECTION_HEAD && !mHasGaps) {
1421            final int addedChildCount = Math.abs(mLayoutState.mCurrentPosition
1422                    - (referenceChildPosition + mLayoutState.mItemDirection));
1423            if (addedChildCount > 0) {
1424                // check if any child has been attached to wrong span. If so, trigger a re-layout
1425                // after scroll
1426                final View viewInWrongSpan;
1427                final View referenceView = findViewByPosition(referenceChildPosition);
1428                if (referenceView == null) {
1429                    viewInWrongSpan = hasGapsToFix(0, getChildCount());
1430                } else {
1431                    if (mLayoutState.mLayoutDirection == LAYOUT_START) {
1432                        viewInWrongSpan = hasGapsToFix(0, addedChildCount);
1433                    } else {
1434                        viewInWrongSpan = hasGapsToFix(getChildCount() - addedChildCount,
1435                                getChildCount());
1436                    }
1437                }
1438                mHasGaps = viewInWrongSpan != null;
1439            }
1440        }
1441        return totalScroll;
1442    }
1443
1444    /**
1445     * The actual method that implements {@link #GAP_HANDLING_LAZY}
1446     */
1447    private void lazyOffsetSpans(int offset, int targetStart, int targetEnd) {
1448        // For each span offset children one by one.
1449        // When a fullSpan item is reached, stop and wait for other spans to reach to that span.
1450        // When all reach, offset fullSpan to max of others and continue.
1451        int childrenToOffset = getChildCount();
1452        int[] indexPerSpan = new int[mSpanCount];
1453        int[] offsetPerSpan = new int[mSpanCount];
1454
1455        final int childOrder = offset > 0 ? ITEM_DIRECTION_TAIL : ITEM_DIRECTION_HEAD;
1456        if (offset > 0) {
1457            Arrays.fill(indexPerSpan, 0);
1458        } else {
1459            for (int i = 0; i < mSpanCount; i++) {
1460                indexPerSpan[i] = mSpans[i].mViews.size() - 1;
1461            }
1462        }
1463
1464        for (int i = 0; i < mSpanCount; i++) {
1465            offsetPerSpan[i] = mSpans[i].getNormalizedOffset(offset, targetStart, targetEnd);
1466        }
1467        if (DEBUG) {
1468            Log.d(TAG, "lazy offset start. normalized: " + Arrays.toString(offsetPerSpan));
1469        }
1470
1471        while (childrenToOffset > 0) {
1472            View fullSpanView = null;
1473            for (int spanIndex = 0; spanIndex < mSpanCount; spanIndex++) {
1474                Span span = mSpans[spanIndex];
1475                int viewIndex;
1476                for (viewIndex = indexPerSpan[spanIndex];
1477                        viewIndex < span.mViews.size() && viewIndex >= 0; viewIndex += childOrder) {
1478                    View view = span.mViews.get(viewIndex);
1479                    if (DEBUG) {
1480                        Log.d(TAG, "span " + spanIndex + ", view:" + viewIndex + ", pos:"
1481                                + getPosition(view));
1482                    }
1483                    LayoutParams lp = (LayoutParams) view.getLayoutParams();
1484                    if (lp.mFullSpan) {
1485                        if (DEBUG) {
1486                            Log.d(TAG, "stopping on full span view on index " + viewIndex
1487                                    + " in span " + spanIndex);
1488                        }
1489                        fullSpanView = view;
1490                        viewIndex += childOrder;// move to next view
1491                        break;
1492                    }
1493                    // offset this child normally
1494                    mPrimaryOrientation.offsetChild(view, offsetPerSpan[spanIndex]);
1495                    final int nextChildIndex = viewIndex + childOrder;
1496                    if (nextChildIndex < span.mViews.size() && nextChildIndex >= 0) {
1497                        View nextView = span.mViews.get(nextChildIndex);
1498                        // find gap between, before offset
1499                        if (childOrder == ITEM_DIRECTION_HEAD) {// negative
1500                            offsetPerSpan[spanIndex] = Math
1501                                    .min(0, mPrimaryOrientation.getDecoratedStart(view)
1502                                            - mPrimaryOrientation.getDecoratedEnd(nextView));
1503                        } else {
1504                            offsetPerSpan[spanIndex] = Math
1505                                    .max(0, mPrimaryOrientation.getDecoratedEnd(view) -
1506                                            mPrimaryOrientation.getDecoratedStart(nextView));
1507                        }
1508                        if (DEBUG) {
1509                            Log.d(TAG, "offset diff:" + offsetPerSpan[spanIndex] + " between "
1510                                    + getPosition(nextView) + " and " + getPosition(view));
1511                        }
1512                    }
1513                    childrenToOffset--;
1514                }
1515                indexPerSpan[spanIndex] = viewIndex;
1516            }
1517            if (fullSpanView != null) {
1518                // we have to offset this view. We'll offset it as the biggest amount necessary
1519                int winnerSpan = 0;
1520                int winnerSpanOffset = Math.abs(offsetPerSpan[winnerSpan]);
1521                for (int i = 1; i < mSpanCount; i++) {
1522                    final int spanOffset = Math.abs(offsetPerSpan[i]);
1523                    if (spanOffset > winnerSpanOffset) {
1524                        winnerSpan = i;
1525                        winnerSpanOffset = spanOffset;
1526                    }
1527                }
1528                if (DEBUG) {
1529                    Log.d(TAG, "winner offset:" + offsetPerSpan[winnerSpan] + " of " + winnerSpan);
1530                }
1531                mPrimaryOrientation.offsetChild(fullSpanView, offsetPerSpan[winnerSpan]);
1532                childrenToOffset--;
1533
1534                for (int spanIndex = 0; spanIndex < mSpanCount; spanIndex++) {
1535                    final int nextViewIndex = indexPerSpan[spanIndex];
1536                    final Span span = mSpans[spanIndex];
1537                    if (nextViewIndex < span.mViews.size() && nextViewIndex > 0) {
1538                        View nextView = span.mViews.get(nextViewIndex);
1539                        // find gap between, before offset
1540                        if (childOrder == ITEM_DIRECTION_HEAD) {// negative
1541                            offsetPerSpan[spanIndex] = Math
1542                                    .min(0, mPrimaryOrientation.getDecoratedStart(fullSpanView)
1543                                            - mPrimaryOrientation.getDecoratedEnd(nextView));
1544                        } else {
1545                            offsetPerSpan[spanIndex] = Math
1546                                    .max(0, mPrimaryOrientation.getDecoratedEnd(fullSpanView) -
1547                                            mPrimaryOrientation.getDecoratedStart(nextView));
1548                        }
1549                    }
1550                }
1551            }
1552        }
1553        for (int spanIndex = 0; spanIndex < mSpanCount; spanIndex++) {
1554            mSpans[spanIndex].invalidateCache();
1555        }
1556    }
1557
1558    private int getLastChildPosition() {
1559        final int childCount = getChildCount();
1560        return childCount == 0 ? 0 : getPosition(getChildAt(childCount - 1));
1561    }
1562
1563    private int getFirstChildPosition() {
1564        final int childCount = getChildCount();
1565        return childCount == 0 ? 0 : getPosition(getChildAt(0));
1566    }
1567
1568    /**
1569     * Finds the first View that can be used as an anchor View.
1570     *
1571     * @return Position of the View or 0 if it cannot find any such View.
1572     */
1573    private int findFirstReferenceChildPosition(int itemCount) {
1574        final int limit = getChildCount();
1575        for (int i = 0; i < limit; i++) {
1576            final View view = getChildAt(i);
1577            final int position = getPosition(view);
1578            if (position >= 0 && position < itemCount) {
1579                return position;
1580            }
1581        }
1582        return 0;
1583    }
1584
1585    /**
1586     * Finds the last View that can be used as an anchor View.
1587     *
1588     * @return Position of the View or 0 if it cannot find any such View.
1589     */
1590    private int findLastReferenceChildPosition(int itemCount) {
1591        for (int i = getChildCount() - 1; i >= 0; i--) {
1592            final View view = getChildAt(i);
1593            final int position = getPosition(view);
1594            if (position >= 0 && position < itemCount) {
1595                return position;
1596            }
1597        }
1598        return 0;
1599    }
1600
1601    @Override
1602    public RecyclerView.LayoutParams generateDefaultLayoutParams() {
1603        return new LayoutParams(ViewGroup.LayoutParams.WRAP_CONTENT,
1604                ViewGroup.LayoutParams.WRAP_CONTENT);
1605    }
1606
1607    @Override
1608    public RecyclerView.LayoutParams generateLayoutParams(Context c, AttributeSet attrs) {
1609        return new LayoutParams(c, attrs);
1610    }
1611
1612    @Override
1613    public RecyclerView.LayoutParams generateLayoutParams(ViewGroup.LayoutParams lp) {
1614        if (lp instanceof ViewGroup.MarginLayoutParams) {
1615            return new LayoutParams((ViewGroup.MarginLayoutParams) lp);
1616        } else {
1617            return new LayoutParams(lp);
1618        }
1619    }
1620
1621    @Override
1622    public boolean checkLayoutParams(RecyclerView.LayoutParams lp) {
1623        return lp instanceof LayoutParams;
1624    }
1625
1626    public int getOrientation() {
1627        return mOrientation;
1628    }
1629
1630
1631    /**
1632     * LayoutParams used by StaggeredGridLayoutManager.
1633     */
1634    public static class LayoutParams extends RecyclerView.LayoutParams {
1635
1636        /**
1637         * Span Id for Views that are not laid out yet.
1638         */
1639        public static final int INVALID_SPAN_ID = -1;
1640
1641        // Package scope to be able to access from tests.
1642        Span mSpan;
1643
1644        boolean mFullSpan;
1645
1646        public LayoutParams(Context c, AttributeSet attrs) {
1647            super(c, attrs);
1648        }
1649
1650        public LayoutParams(int width, int height) {
1651            super(width, height);
1652        }
1653
1654        public LayoutParams(ViewGroup.MarginLayoutParams source) {
1655            super(source);
1656        }
1657
1658        public LayoutParams(ViewGroup.LayoutParams source) {
1659            super(source);
1660        }
1661
1662        public LayoutParams(RecyclerView.LayoutParams source) {
1663            super(source);
1664        }
1665
1666        /**
1667         * When set to true, the item will layout using all span area. That means, if orientation
1668         * is vertical, the view will have full width; if orientation is horizontal, the view will
1669         * have full height.
1670         *
1671         * @param fullSpan True if this item should traverse all spans.
1672         */
1673        public void setFullSpan(boolean fullSpan) {
1674            mFullSpan = fullSpan;
1675        }
1676
1677        /**
1678         * Returns the Span index to which this View is assigned.
1679         *
1680         * @return The Span index of the View. If View is not yet assigned to any span, returns
1681         * {@link #INVALID_SPAN_ID}.
1682         */
1683        public final int getSpanIndex() {
1684            if (mSpan == null) {
1685                return INVALID_SPAN_ID;
1686            }
1687            return mSpan.mIndex;
1688        }
1689    }
1690
1691    // Package scoped to access from tests.
1692    class Span {
1693
1694        final int INVALID_LINE = Integer.MIN_VALUE;
1695
1696        private ArrayList<View> mViews = new ArrayList<View>();
1697
1698        int mCachedStart = INVALID_LINE;
1699
1700        int mCachedEnd = INVALID_LINE;
1701
1702        int mDeletedSize = 0;
1703
1704        final int mIndex;
1705
1706        private Span(int index) {
1707            mIndex = index;
1708        }
1709
1710        int getStartLine(int def) {
1711            if (mCachedStart != INVALID_LINE) {
1712                return mCachedStart;
1713            }
1714            if (mViews.size() == 0) {
1715                return def;
1716            }
1717            mCachedStart = mPrimaryOrientation.getDecoratedStart(mViews.get(0));
1718            return mCachedStart;
1719        }
1720
1721        // Use this one when default value does not make sense and not having a value means a bug.
1722        int getStartLine() {
1723            if (mCachedStart != INVALID_LINE) {
1724                return mCachedStart;
1725            }
1726            mCachedStart = mPrimaryOrientation.getDecoratedStart(mViews.get(0));
1727            return mCachedStart;
1728        }
1729
1730        int getEndLine(int def) {
1731            if (mCachedEnd != INVALID_LINE) {
1732                return mCachedEnd;
1733            }
1734            final int size = mViews.size();
1735            if (size == 0) {
1736                return def;
1737            }
1738            mCachedEnd = mPrimaryOrientation.getDecoratedEnd(mViews.get(size - 1));
1739            return mCachedEnd;
1740        }
1741
1742        // Use this one when default value does not make sense and not having a value means a bug.
1743        int getEndLine() {
1744            if (mCachedEnd != INVALID_LINE) {
1745                return mCachedEnd;
1746            }
1747            mCachedEnd = mPrimaryOrientation.getDecoratedEnd(mViews.get(mViews.size() - 1));
1748            return mCachedEnd;
1749        }
1750
1751        void prependToSpan(View view) {
1752            LayoutParams lp = getLayoutParams(view);
1753            lp.mSpan = this;
1754            mViews.add(0, view);
1755            mCachedStart = INVALID_LINE;
1756            if (mViews.size() == 1) {
1757                mCachedEnd = INVALID_LINE;
1758            }
1759            if (lp.isItemRemoved() || lp.isItemChanged()) {
1760                mDeletedSize += mPrimaryOrientation.getDecoratedMeasurement(view);
1761            }
1762        }
1763
1764        void appendToSpan(View view) {
1765            LayoutParams lp = getLayoutParams(view);
1766            lp.mSpan = this;
1767            mViews.add(view);
1768            mCachedEnd = INVALID_LINE;
1769            if (mViews.size() == 1) {
1770                mCachedStart = INVALID_LINE;
1771            }
1772            if (lp.isItemRemoved() || lp.isItemChanged()) {
1773                mDeletedSize += mPrimaryOrientation.getDecoratedMeasurement(view);
1774            }
1775        }
1776
1777        // Useful method to preserve positions on a re-layout.
1778        void cacheReferenceLineAndClear(boolean reverseLayout, int offset) {
1779            int reference;
1780            if (reverseLayout) {
1781                reference = getEndLine(INVALID_LINE);
1782            } else {
1783                reference = getStartLine(INVALID_LINE);
1784            }
1785            clear();
1786            if (reference == INVALID_LINE) {
1787                return;
1788            }
1789            if (offset != INVALID_OFFSET) {
1790                reference += offset;
1791            }
1792            mCachedStart = mCachedEnd = reference;
1793        }
1794
1795        void clear() {
1796            mViews.clear();
1797            invalidateCache();
1798            mDeletedSize = 0;
1799        }
1800
1801        void invalidateCache() {
1802            mCachedStart = INVALID_LINE;
1803            mCachedEnd = INVALID_LINE;
1804        }
1805
1806        void setLine(int line) {
1807            mCachedEnd = mCachedStart = line;
1808        }
1809
1810        void popEnd() {
1811            final int size = mViews.size();
1812            View end = mViews.remove(size - 1);
1813            final LayoutParams lp = getLayoutParams(end);
1814            lp.mSpan = null;
1815            if (lp.isItemRemoved() || lp.isItemChanged()) {
1816                mDeletedSize -= mPrimaryOrientation.getDecoratedMeasurement(end);
1817            }
1818            if (size == 1) {
1819                mCachedStart = INVALID_LINE;
1820            }
1821            mCachedEnd = INVALID_LINE;
1822        }
1823
1824        void popStart() {
1825            View start = mViews.remove(0);
1826            final LayoutParams lp = getLayoutParams(start);
1827            lp.mSpan = null;
1828            if (mViews.size() == 0) {
1829                mCachedEnd = INVALID_LINE;
1830            }
1831            if (lp.isItemRemoved() || lp.isItemChanged()) {
1832                mDeletedSize -= mPrimaryOrientation.getDecoratedMeasurement(start);
1833            }
1834            mCachedStart = INVALID_LINE;
1835        }
1836
1837        // TODO cache this.
1838        public int getDeletedSize() {
1839            return mDeletedSize;
1840        }
1841
1842        LayoutParams getLayoutParams(View view) {
1843            return (LayoutParams) view.getLayoutParams();
1844        }
1845
1846        void onOffset(int dt) {
1847            if (mCachedStart != INVALID_LINE) {
1848                mCachedStart += dt;
1849            }
1850            if (mCachedEnd != INVALID_LINE) {
1851                mCachedEnd += dt;
1852            }
1853        }
1854
1855        // normalized offset is how much this span can scroll
1856        int getNormalizedOffset(int dt, int targetStart, int targetEnd) {
1857            if (mViews.size() == 0) {
1858                return 0;
1859            }
1860            if (dt < 0) {
1861                final int endSpace = getEndLine() - targetEnd;
1862                if (endSpace <= 0) {
1863                    return 0;
1864                }
1865                return -dt > endSpace ? -endSpace : dt;
1866            } else {
1867                final int startSpace = targetStart - getStartLine();
1868                if (startSpace <= 0) {
1869                    return 0;
1870                }
1871                return startSpace < dt ? startSpace : dt;
1872            }
1873        }
1874
1875        /**
1876         * Returns if there is no child between start-end lines
1877         *
1878         * @param start The start line
1879         * @param end   The end line
1880         * @return true if a new child can be added between start and end
1881         */
1882        boolean isEmpty(int start, int end) {
1883            final int count = mViews.size();
1884            for (int i = 0; i < count; i++) {
1885                final View view = mViews.get(i);
1886                if (mPrimaryOrientation.getDecoratedStart(view) < end &&
1887                        mPrimaryOrientation.getDecoratedEnd(view) > start) {
1888                    return false;
1889                }
1890            }
1891            return true;
1892        }
1893
1894        public int findFirstVisibleItemPosition() {
1895            return mReverseLayout
1896                    ? findOneVisibleChild(mViews.size() - 1, -1, false)
1897                    : findOneVisibleChild(0, mViews.size(), false);
1898        }
1899
1900        public int findFirstCompletelyVisibleItemPosition() {
1901            return mReverseLayout
1902                    ? findOneVisibleChild(mViews.size() -1, -1, true)
1903                    : findOneVisibleChild(0, mViews.size(), true);
1904        }
1905
1906        public int findLastVisibleItemPosition() {
1907            return mReverseLayout
1908                    ? findOneVisibleChild(0, mViews.size(), false)
1909                    : findOneVisibleChild(mViews.size() - 1, -1, false);
1910        }
1911
1912        public int findLastCompletelyVisibleItemPosition() {
1913            return mReverseLayout
1914                    ? findOneVisibleChild(0, mViews.size(), true)
1915                    : findOneVisibleChild(mViews.size() - 1, -1, true);
1916        }
1917
1918        int findOneVisibleChild(int fromIndex, int toIndex, boolean completelyVisible) {
1919            final int start = mPrimaryOrientation.getStartAfterPadding();
1920            final int end = mPrimaryOrientation.getEndAfterPadding();
1921            final int next = toIndex > fromIndex ? 1 : -1;
1922            for (int i = fromIndex; i != toIndex; i+=next) {
1923                final View child = mViews.get(i);
1924                final int childStart = mPrimaryOrientation.getDecoratedStart(child);
1925                final int childEnd = mPrimaryOrientation.getDecoratedEnd(child);
1926                if (childStart < end && childEnd > start) {
1927                    if (completelyVisible) {
1928                        if (childStart >= start && childEnd <= end) {
1929                            return getPosition(child);
1930                        }
1931                    } else {
1932                        return getPosition(child);
1933                    }
1934                }
1935            }
1936            return RecyclerView.NO_POSITION;
1937        }
1938    }
1939
1940    /**
1941     * An array of mappings from adapter position to span.
1942     * This only grows when a write happens and it grows up to the size of the adapter.
1943     */
1944    static class LazySpanLookup {
1945
1946        private static final int MIN_SIZE = 10;
1947
1948        int[] mData;
1949
1950        int mAdapterSize; // we don't want to grow beyond that, unless it grows
1951
1952        void invalidateAfter(int position) {
1953            if (mData == null) {
1954                return;
1955            }
1956            if (position >= mData.length) {
1957                return;
1958            }
1959            Arrays.fill(mData, position, mData.length, LayoutParams.INVALID_SPAN_ID);
1960        }
1961
1962        int getSpan(int position) {
1963            if (mData == null || position >= mData.length) {
1964                return LayoutParams.INVALID_SPAN_ID;
1965            } else {
1966                return mData[position];
1967            }
1968        }
1969
1970        void setSpan(int position, Span span) {
1971            ensureSize(position);
1972            mData[position] = span.mIndex;
1973        }
1974
1975        int sizeForPosition(int position) {
1976            int len = mData.length;
1977            while (len <= position) {
1978                len *= 2;
1979            }
1980            if (len > mAdapterSize) {
1981                len = mAdapterSize;
1982            }
1983            return len;
1984        }
1985
1986        void ensureSize(int position) {
1987            if (mData == null) {
1988                mData = new int[Math.max(position, MIN_SIZE) + 1];
1989                Arrays.fill(mData, LayoutParams.INVALID_SPAN_ID);
1990            } else if (position >= mData.length) {
1991                int[] old = mData;
1992                mData = new int[sizeForPosition(position)];
1993                System.arraycopy(old, 0, mData, 0, old.length);
1994                Arrays.fill(mData, old.length, mData.length, LayoutParams.INVALID_SPAN_ID);
1995            }
1996        }
1997
1998        void clear() {
1999            if (mData != null) {
2000                Arrays.fill(mData, LayoutParams.INVALID_SPAN_ID);
2001            }
2002        }
2003
2004        void offsetForRemoval(int positionStart, int itemCount) {
2005            ensureSize(positionStart + itemCount);
2006            System.arraycopy(mData, positionStart + itemCount, mData, positionStart,
2007                    mData.length - positionStart - itemCount);
2008            Arrays.fill(mData, mData.length - itemCount, mData.length,
2009                    LayoutParams.INVALID_SPAN_ID);
2010        }
2011
2012        void offsetForAddition(int positionStart, int itemCount) {
2013            ensureSize(positionStart + itemCount);
2014            System.arraycopy(mData, positionStart, mData, positionStart + itemCount,
2015                    mData.length - positionStart - itemCount);
2016            Arrays.fill(mData, positionStart, positionStart + itemCount,
2017                    LayoutParams.INVALID_SPAN_ID);
2018        }
2019    }
2020
2021    static class SavedState implements Parcelable {
2022
2023        int mOrientation;
2024
2025        int mSpanCount;
2026
2027        int mGapStrategy;
2028
2029        int mAnchorPosition;
2030
2031        int mVisibleAnchorPosition; // if span count changes (span offsets are invalidated),
2032        // we use this one instead
2033
2034        int[] mSpanOffsets;
2035
2036        int mSpanLookupSize;
2037
2038        int[] mSpanLookup;
2039
2040        boolean mReverseLayout;
2041
2042        boolean mAnchorLayoutFromEnd;
2043
2044        boolean mHasSpanOffsets;
2045
2046        public SavedState() {
2047        }
2048
2049        SavedState(Parcel in) {
2050            mOrientation = in.readInt();
2051            mSpanCount = in.readInt();
2052            mGapStrategy = in.readInt();
2053            mAnchorPosition = in.readInt();
2054            mVisibleAnchorPosition = in.readInt();
2055            mHasSpanOffsets = in.readInt() == 1;
2056            if (mHasSpanOffsets) {
2057                mSpanOffsets = new int[mSpanCount];
2058                in.readIntArray(mSpanOffsets);
2059            }
2060
2061            mSpanLookupSize = in.readInt();
2062            if (mSpanLookupSize > 0) {
2063                mSpanLookup = new int[mSpanLookupSize];
2064                in.readIntArray(mSpanLookup);
2065            }
2066            mReverseLayout = in.readInt() == 1;
2067            mAnchorLayoutFromEnd = in.readInt() == 1;
2068        }
2069
2070        public SavedState(SavedState other) {
2071            mOrientation = other.mOrientation;
2072            mSpanCount = other.mSpanCount;
2073            mGapStrategy = other.mGapStrategy;
2074            mAnchorPosition = other.mAnchorPosition;
2075            mVisibleAnchorPosition = other.mVisibleAnchorPosition;
2076            mHasSpanOffsets = other.mHasSpanOffsets;
2077            mSpanOffsets = other.mSpanOffsets;
2078            mSpanLookupSize = other.mSpanLookupSize;
2079            mSpanLookup = other.mSpanLookup;
2080            mReverseLayout = other.mReverseLayout;
2081            mAnchorLayoutFromEnd = other.mAnchorLayoutFromEnd;
2082        }
2083
2084        void invalidateSpanInfo() {
2085            mSpanOffsets = null;
2086            mHasSpanOffsets = false;
2087            mSpanCount = -1;
2088            mSpanLookupSize = 0;
2089            mSpanLookup = null;
2090        }
2091
2092        void invalidateAnchorPositionInfo() {
2093            mSpanOffsets = null;
2094            mHasSpanOffsets = false;
2095            mAnchorPosition = RecyclerView.NO_POSITION;
2096            mVisibleAnchorPosition = RecyclerView.NO_POSITION;
2097        }
2098
2099        @Override
2100        public int describeContents() {
2101            return 0;
2102        }
2103
2104        @Override
2105        public void writeToParcel(Parcel dest, int flags) {
2106            dest.writeInt(mOrientation);
2107            dest.writeInt(mSpanCount);
2108            dest.writeInt(mGapStrategy);
2109            dest.writeInt(mAnchorPosition);
2110            dest.writeInt(mVisibleAnchorPosition);
2111            dest.writeInt(mHasSpanOffsets ? 1 : 0);
2112            if (mHasSpanOffsets) {
2113                dest.writeIntArray(mSpanOffsets);
2114            }
2115            dest.writeInt(mSpanLookupSize);
2116            if (mSpanLookupSize > 0) {
2117                dest.writeIntArray(mSpanLookup);
2118            }
2119            dest.writeInt(mReverseLayout ? 1 : 0);
2120            dest.writeInt(mAnchorLayoutFromEnd ? 1 : 0);
2121        }
2122
2123        @Override
2124        public String toString() {
2125            return "SavedState{" +
2126                    "mOrientation=" + mOrientation +
2127                    ", mSpanCount=" + mSpanCount +
2128                    ", mGapStrategy=" + mGapStrategy +
2129                    ", mAnchorPosition=" + mAnchorPosition +
2130                    ", mVisibleAnchorPosition=" + mVisibleAnchorPosition +
2131                    ", mSpanOffsets=" + Arrays.toString(mSpanOffsets) +
2132                    ", mSpanLookupSize=" + mSpanLookupSize +
2133                    ", mSpanLookup=" + Arrays.toString(mSpanLookup) +
2134                    ", mReverseLayout=" + mReverseLayout +
2135                    ", mAnchorLayoutFromEnd=" + mAnchorLayoutFromEnd +
2136                    ", mHasSpanOffsets=" + mHasSpanOffsets +
2137                    '}';
2138        }
2139
2140        public static final Parcelable.Creator<SavedState> CREATOR
2141                = new Parcelable.Creator<SavedState>() {
2142            @Override
2143            public SavedState createFromParcel(Parcel in) {
2144                return new SavedState(in);
2145            }
2146
2147            @Override
2148            public SavedState[] newArray(int size) {
2149                return new SavedState[size];
2150            }
2151        };
2152    }
2153}
2154