StaggeredGridLayoutManager.java revision 6b4d950d0d1e26165a1e643a2fd1fe4e283786f1 
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    int mPendingScrollPosition = RecyclerView.NO_POSITION;
148
149    /**
150     * Used to keep the offset value when {@link #scrollToPositionWithOffset(int, int)} is
151     * called.
152     */
153    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 (!state.isPreLayout() && 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 (!state.isPreLayout() && 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        if (!state.isPreLayout()) {
592            mPendingScrollPosition = RecyclerView.NO_POSITION;
593            mPendingScrollPositionOffset = INVALID_OFFSET;
594        }
595        mLastLayoutFromEnd = layoutFromEnd;
596        mPendingSavedState = null; // we don't need this anymore
597    }
598
599    /**
600     * Checks if a child is assigned to the non-optimal span.
601     *
602     * @param startChildIndex Starts checking after this child, inclusive
603     * @param endChildIndex   Starts checking until this child, exclusive
604     * @return The first View that is assigned to the wrong span.
605     */
606    View hasGapsToFix(int startChildIndex, int endChildIndex) {
607        // quick reject
608        if (startChildIndex >= endChildIndex) {
609            return null;
610        }
611        final int firstChildIndex, childLimit;
612        final int nextSpanDiff = mOrientation == VERTICAL && isLayoutRTL() ? 1 : -1;
613
614        if (mShouldReverseLayout) {
615            firstChildIndex = endChildIndex - 1;
616            childLimit = startChildIndex - 1;
617        } else {
618            firstChildIndex = startChildIndex;
619            childLimit = endChildIndex;
620        }
621        final int nextChildDiff = firstChildIndex < childLimit ? 1 : -1;
622        for (int i = firstChildIndex; i != childLimit; i += nextChildDiff) {
623            View child = getChildAt(i);
624            final int start = mPrimaryOrientation.getDecoratedStart(child);
625            final int end = mPrimaryOrientation.getDecoratedEnd(child);
626            LayoutParams layoutParams = (LayoutParams) child.getLayoutParams();
627            if (layoutParams.mFullSpan) {
628                continue; // quick reject
629            }
630            int nextSpanIndex = layoutParams.getSpanIndex() + nextSpanDiff;
631            while (nextSpanIndex >= 0 && nextSpanIndex < mSpanCount) {
632                Span nextSpan = mSpans[nextSpanIndex];
633                if (nextSpan.isEmpty(start, end)) {
634                    return child;
635                }
636                nextSpanIndex += nextSpanDiff;
637            }
638        }
639        // everything looks good
640        return null;
641    }
642
643    @Override
644    public boolean supportsPredictiveItemAnimations() {
645        return mPendingSavedState == null;
646    }
647
648    /**
649     * Returns the adapter position of the first visible view for each span.
650     * <p>
651     * Note that, this value is not affected by layout orientation or item order traversal.
652     * ({@link #setReverseLayout(boolean)}). Views are sorted by their positions in the adapter,
653     * not in the layout.
654     * <p>
655     * If RecyclerView has item decorators, they will be considered in calculations as well.
656     * <p>
657     * StaggeredGridLayoutManager may pre-cache some views that are not necessarily visible. Those
658     * views are ignored in this method.
659     *
660     * @return The adapter position of the first visible item in each span. If a span does not have
661     * any items, {@link RecyclerView#NO_POSITION} is returned for that span.
662     *
663     * @param into An array to put the results into. If you don't provide any, LayoutManager will
664     *             create a new one.
665     * @see #findFirstCompletelyVisibleItemPositions(int[])
666     * @see #findLastVisibleItemPositions(int[])
667     */
668    public int[] findFirstVisibleItemPositions(int[] into) {
669        if (into == null) {
670            into = new int[mSpanCount];
671        } else if (into.length < mSpanCount) {
672            throw new IllegalArgumentException("Provided int[]'s size must be more than or equal"
673                    + " to span count. Expected:" + mSpanCount + ", array size:" + into.length);
674        }
675        for (int i = 0; i < mSpanCount; i ++) {
676            into[i] = mSpans[i].findFirstVisibleItemPosition();
677        }
678        return into;
679    }
680
681    /**
682     * Returns the adapter position of the first completely visible view for each span.
683     * <p>
684     * Note that, this value is not affected by layout orientation or item order traversal.
685     * ({@link #setReverseLayout(boolean)}). Views are sorted by their positions in the adapter,
686     * not in the layout.
687     * <p>
688     * If RecyclerView has item decorators, they will be considered in calculations as well.
689     * <p>
690     * StaggeredGridLayoutManager may pre-cache some views that are not necessarily visible. Those
691     * views are ignored in this method.
692     *
693     * @return The adapter position of the first fully visible item in each span. If a span does
694     * not have any items, {@link RecyclerView#NO_POSITION} is returned for that span.
695     * @param into An array to put the results into. If you don't provide any, LayoutManager will
696     *             create a new one.
697     * @see #findFirstVisibleItemPositions(int[])
698     * @see #findLastCompletelyVisibleItemPositions(int[])
699     */
700    public int[] findFirstCompletelyVisibleItemPositions(int[] into) {
701        if (into == null) {
702            into = new int[mSpanCount];
703        } else if (into.length < mSpanCount) {
704            throw new IllegalArgumentException("Provided int[]'s size must be more than or equal"
705                    + " to span count. Expected:" + mSpanCount + ", array size:" + into.length);
706        }
707        for (int i = 0; i < mSpanCount; i ++) {
708            into[i] = mSpans[i].findFirstCompletelyVisibleItemPosition();
709        }
710        return into;
711    }
712
713    /**
714     * Returns the adapter position of the last visible view for each span.
715     * <p>
716     * Note that, this value is not affected by layout orientation or item order traversal.
717     * ({@link #setReverseLayout(boolean)}). Views are sorted by their positions in the adapter,
718     * not in the layout.
719     * <p>
720     * If RecyclerView has item decorators, they will be considered in calculations as well.
721     * <p>
722     * StaggeredGridLayoutManager may pre-cache some views that are not necessarily visible. Those
723     * views are ignored in this method.
724     *
725     * @return The adapter position of the last visible item in each span. If a span does not have
726     * any items, {@link RecyclerView#NO_POSITION} is returned for that span.
727     *
728     * @param into An array to put the results into. If you don't provide any, LayoutManager will
729     *             create a new one.
730     * @see #findLastCompletelyVisibleItemPositions(int[])
731     * @see #findFirstVisibleItemPositions(int[])
732     */
733    public int[] findLastVisibleItemPositions(int[] into) {
734        if (into == null) {
735            into = new int[mSpanCount];
736        } else if (into.length < mSpanCount) {
737            throw new IllegalArgumentException("Provided int[]'s size must be more than or equal"
738                    + " to span count. Expected:" + mSpanCount + ", array size:" + into.length);
739        }
740        for (int i = 0; i < mSpanCount; i ++) {
741            into[i] = mSpans[i].findLastVisibleItemPosition();
742        }
743        return into;
744    }
745
746    /**
747     * Returns the adapter position of the last completely visible view for each span.
748     * <p>
749     * Note that, this value is not affected by layout orientation or item order traversal.
750     * ({@link #setReverseLayout(boolean)}). Views are sorted by their positions in the adapter,
751     * not in the layout.
752     * <p>
753     * If RecyclerView has item decorators, they will be considered in calculations as well.
754     * <p>
755     * StaggeredGridLayoutManager may pre-cache some views that are not necessarily visible. Those
756     * views are ignored in this method.
757     *
758     * @return The adapter position of the last fully visible item in each span. If a span does not
759     * have any items, {@link RecyclerView#NO_POSITION} is returned for that span.
760     *
761     * @param into An array to put the results into. If you don't provide any, LayoutManager will
762     *             create a new one.
763     * @see #findFirstCompletelyVisibleItemPositions(int[])
764     * @see #findLastVisibleItemPositions(int[])
765     */
766    public int[] findLastCompletelyVisibleItemPositions(int[] into) {
767        if (into == null) {
768            into = new int[mSpanCount];
769        } else if (into.length < mSpanCount) {
770            throw new IllegalArgumentException("Provided int[]'s size must be more than or equal"
771                    + " to span count. Expected:" + mSpanCount + ", array size:" + into.length);
772        }
773        for (int i = 0; i < mSpanCount; i ++) {
774            into[i] = mSpans[i].findLastCompletelyVisibleItemPosition();
775        }
776        return into;
777    }
778
779    private void measureChildWithDecorationsAndMargin(View child, int widthSpec,
780            int heightSpec) {
781        final Rect insets = mRecyclerView.getItemDecorInsetsForChild(child);
782        LayoutParams lp = (LayoutParams) child.getLayoutParams();
783        widthSpec = updateSpecWithExtra(widthSpec, lp.leftMargin + insets.left,
784                lp.rightMargin + insets.right);
785        heightSpec = updateSpecWithExtra(heightSpec, lp.topMargin + insets.top,
786                lp.bottomMargin + insets.bottom);
787        child.measure(widthSpec, heightSpec);
788    }
789
790    private int updateSpecWithExtra(int spec, int startInset, int endInset) {
791        if (startInset == 0 && endInset == 0) {
792            return spec;
793        }
794        final int mode = View.MeasureSpec.getMode(spec);
795        if (mode == View.MeasureSpec.AT_MOST || mode == View.MeasureSpec.EXACTLY) {
796            return View.MeasureSpec.makeMeasureSpec(
797                    View.MeasureSpec.getSize(spec) - startInset - endInset, mode);
798        }
799        return spec;
800    }
801
802    @Override
803    public void onRestoreInstanceState(Parcelable state) {
804        if (state instanceof SavedState) {
805            mPendingSavedState = (SavedState) state;
806            requestLayout();
807        } else if (DEBUG) {
808            Log.d(TAG, "invalid saved state class");
809        }
810    }
811
812    @Override
813    public Parcelable onSaveInstanceState() {
814        if (mPendingSavedState != null) {
815            return new SavedState(mPendingSavedState);
816        }
817        SavedState state = new SavedState();
818        state.mOrientation = mOrientation;
819        state.mReverseLayout = mReverseLayout;
820        state.mSpanCount = mSpanCount;
821        state.mAnchorLayoutFromEnd = mLastLayoutFromEnd;
822        state.mGapStrategy = mGapStrategy;
823
824        if (mLazySpanLookup != null && mLazySpanLookup.mData != null) {
825            state.mSpanLookup = mLazySpanLookup.mData;
826            state.mSpanLookupSize = state.mSpanLookup.length;
827        } else {
828            state.mSpanLookupSize = 0;
829        }
830
831        if (getChildCount() > 0) {
832            state.mAnchorPosition = mLastLayoutFromEnd ? getLastChildPosition()
833                    : getFirstChildPosition();
834            state.mVisibleAnchorPosition = findFirstVisibleItemPositionInt();
835            state.mHasSpanOffsets = true;
836            state.mSpanOffsets = new int[mSpanCount];
837            for (int i = 0; i < mSpanCount; i++) {
838                state.mSpanOffsets[i] = mLastLayoutFromEnd ? mSpans[i].getEndLine(Span.INVALID_LINE)
839                        : mSpans[i].getStartLine(Span.INVALID_LINE);
840            }
841        } else {
842            state.mAnchorPosition = RecyclerView.NO_POSITION;
843            state.mVisibleAnchorPosition = RecyclerView.NO_POSITION;
844            state.mHasSpanOffsets = false;
845        }
846        if (DEBUG) {
847            Log.d(TAG, "saved state:\n" + state);
848        }
849        return state;
850    }
851
852    /**
853     * Finds the first fully visible child to be used as an anchor child if span count changes when
854     * state is restored.
855     */
856    int findFirstVisibleItemPositionInt() {
857        final int start, end, diff;
858        if (mLastLayoutFromEnd) {
859            start = getChildCount() - 1;
860            end = -1;
861            diff = -1;
862        } else {
863            start = 0;
864            end = getChildCount();
865            diff = 1;
866        }
867        final int boundsStart = mPrimaryOrientation.getStartAfterPadding();
868        final int boundsEnd = mPrimaryOrientation.getEndAfterPadding();
869        for (int i = start; i != end; i += diff) {
870            final View child = getChildAt(i);
871            if (mPrimaryOrientation.getDecoratedStart(child) >= boundsStart
872                    && mPrimaryOrientation.getDecoratedEnd(child) <= boundsEnd) {
873                return getPosition(child);
874            }
875        }
876        return RecyclerView.NO_POSITION;
877    }
878
879    private void fixEndGap(RecyclerView.Recycler recycler, RecyclerView.State state,
880            boolean canOffsetChildren) {
881        final int maxEndLine = getMaxEnd(mPrimaryOrientation.getEndAfterPadding());
882        int gap = mPrimaryOrientation.getEndAfterPadding() - maxEndLine;
883        int fixOffset;
884        if (gap > 0) {
885            fixOffset = -scrollBy(-gap, recycler, state);
886        } else {
887            return; // nothing to fix
888        }
889        gap -= fixOffset;
890        if (canOffsetChildren && gap > 0) {
891            mPrimaryOrientation.offsetChildren(gap);
892        }
893    }
894
895    private void fixStartGap(RecyclerView.Recycler recycler, RecyclerView.State state,
896            boolean canOffsetChildren) {
897        final int minStartLine = getMinStart(mPrimaryOrientation.getStartAfterPadding());
898        int gap = minStartLine - mPrimaryOrientation.getStartAfterPadding();
899        int fixOffset;
900        if (gap > 0) {
901            fixOffset = scrollBy(gap, recycler, state);
902        } else {
903            return; // nothing to fix
904        }
905        gap -= fixOffset;
906        if (canOffsetChildren && gap > 0) {
907            mPrimaryOrientation.offsetChildren(-gap);
908        }
909    }
910
911    private void updateLayoutStateToFillStart(int anchorPosition, RecyclerView.State state) {
912        mLayoutState.mAvailable = 0;
913        mLayoutState.mCurrentPosition = anchorPosition;
914        if (isSmoothScrolling()) {
915            final int targetPos = state.getTargetScrollPosition();
916            if (mShouldReverseLayout == targetPos < anchorPosition) {
917                mLayoutState.mExtra = 0;
918            } else {
919                mLayoutState.mExtra = mPrimaryOrientation.getTotalSpace();
920            }
921        } else {
922            mLayoutState.mExtra = 0;
923        }
924        mLayoutState.mLayoutDirection = LAYOUT_START;
925        mLayoutState.mItemDirection = mShouldReverseLayout ? ITEM_DIRECTION_TAIL
926                : ITEM_DIRECTION_HEAD;
927    }
928
929    private void updateLayoutStateToFillEnd(int anchorPosition, RecyclerView.State state) {
930        mLayoutState.mAvailable = 0;
931        mLayoutState.mCurrentPosition = anchorPosition;
932        if (isSmoothScrolling()) {
933            final int targetPos = state.getTargetScrollPosition();
934            if (mShouldReverseLayout == targetPos > anchorPosition) {
935                mLayoutState.mExtra = 0;
936            } else {
937                mLayoutState.mExtra = mPrimaryOrientation.getTotalSpace();
938            }
939        } else {
940            mLayoutState.mExtra = 0;
941        }
942        mLayoutState.mLayoutDirection = LAYOUT_END;
943        mLayoutState.mItemDirection = mShouldReverseLayout ? ITEM_DIRECTION_HEAD
944                : ITEM_DIRECTION_TAIL;
945    }
946
947    @Override
948    public void offsetChildrenHorizontal(int dx) {
949        super.offsetChildrenHorizontal(dx);
950        for (int i = 0; i < mSpanCount; i++) {
951            mSpans[i].onOffset(dx);
952        }
953    }
954
955    @Override
956    public void offsetChildrenVertical(int dy) {
957        super.offsetChildrenVertical(dy);
958        for (int i = 0; i < mSpanCount; i++) {
959            mSpans[i].onOffset(dy);
960        }
961    }
962
963    @Override
964    public void onItemsRemoved(RecyclerView recyclerView, int positionStart, int itemCount) {
965        if (!considerSpanInvalidate(positionStart, itemCount)) {
966            // If positions are not invalidated, move span offsets.
967            mLazySpanLookup.offsetForRemoval(positionStart, itemCount);
968        }
969    }
970
971    @Override
972    public void onItemsAdded(RecyclerView recyclerView, int positionStart, int itemCount) {
973        if (!considerSpanInvalidate(positionStart, itemCount)) {
974            // If positions are not invalidated, move span offsets.
975            mLazySpanLookup.offsetForAddition(positionStart, itemCount);
976        }
977    }
978
979    /**
980     * Checks whether it should invalidate span assignments in response to an adapter change.
981     */
982    private boolean considerSpanInvalidate(int positionStart, int itemCount) {
983        int minPosition = mShouldReverseLayout ? getLastChildPosition() : getFirstChildPosition();
984        if (positionStart + itemCount <= minPosition) {
985            return false;// nothing to update.
986        }
987        int maxPosition = mShouldReverseLayout ? getFirstChildPosition() : getLastChildPosition();
988        mLazySpanLookup.invalidateAfter(positionStart);
989        if (positionStart <= maxPosition) {
990            requestLayout();
991        }
992        return true;
993    }
994
995    private int fill(RecyclerView.Recycler recycler, LayoutState layoutState,
996            RecyclerView.State state) {
997        mRemainingSpans.set(0, mSpanCount, true);
998        // The target position we are trying to reach.
999        final int targetLine;
1000
1001        /*
1002        * The line until which we can recycle, as long as we add views.
1003        * Keep in mind, it is still the line in layout direction which means; to calculate the
1004        * actual recycle line, we should subtract/add the size in orientation.
1005        */
1006        final int recycleLine;
1007        // Line of the furthest row.
1008        if (layoutState.mLayoutDirection == LAYOUT_END) {
1009            // ignore padding for recycler
1010            recycleLine = mPrimaryOrientation.getEndAfterPadding() + mLayoutState.mAvailable;
1011            targetLine = recycleLine + mLayoutState.mExtra + mPrimaryOrientation.getEndPadding();
1012            final int defaultLine = mPrimaryOrientation.getStartAfterPadding();
1013            for (int i = 0; i < mSpanCount; i++) {
1014                final Span span = mSpans[i];
1015                final int line = span.getEndLine(defaultLine);
1016                if (line > targetLine) {
1017                    mRemainingSpans.set(i, false);
1018                }
1019            }
1020        } else { // LAYOUT_START
1021            // ignore padding for recycler
1022            recycleLine = mPrimaryOrientation.getStartAfterPadding() - mLayoutState.mAvailable;
1023            targetLine = recycleLine - mLayoutState.mExtra -
1024                    mPrimaryOrientation.getStartAfterPadding();
1025            for (int i = 0; i < mSpanCount; i++) {
1026                final Span span = mSpans[i];
1027                final int defaultLine = mPrimaryOrientation.getEndAfterPadding();
1028                final int line = span.getStartLine(defaultLine);
1029                if (line < targetLine) {
1030                    mRemainingSpans.set(i, false);
1031                }
1032            }
1033        }
1034
1035        final int widthSpec, heightSpec;
1036        if (mOrientation == VERTICAL) {
1037            widthSpec = View.MeasureSpec.makeMeasureSpec(mSizePerSpan, View.MeasureSpec.EXACTLY);
1038            heightSpec = View.MeasureSpec.makeMeasureSpec(0, View.MeasureSpec.UNSPECIFIED);
1039        } else {
1040            heightSpec = View.MeasureSpec.makeMeasureSpec(mSizePerSpan, View.MeasureSpec.EXACTLY);
1041            widthSpec = View.MeasureSpec.makeMeasureSpec(0, View.MeasureSpec.UNSPECIFIED);
1042        }
1043
1044        while (layoutState.hasMore(state) && !mRemainingSpans.isEmpty()) {
1045            View view = layoutState.next(recycler);
1046            LayoutParams lp = ((LayoutParams) view.getLayoutParams());
1047            if (layoutState.mLayoutDirection == LAYOUT_END) {
1048                addView(view);
1049            } else {
1050                addView(view, 0);
1051            }
1052            if (lp.mFullSpan) {
1053                final int fullSizeSpec = View.MeasureSpec.makeMeasureSpec(
1054                        mSecondaryOrientation.getTotalSpace(), View.MeasureSpec.EXACTLY);
1055                if (mOrientation == VERTICAL) {
1056                    measureChildWithDecorationsAndMargin(view, fullSizeSpec, heightSpec);
1057                } else {
1058                    measureChildWithDecorationsAndMargin(view, widthSpec, fullSizeSpec);
1059                }
1060            } else {
1061                measureChildWithDecorationsAndMargin(view, widthSpec, heightSpec);
1062            }
1063
1064            final int position = getPosition(view);
1065            final int spanIndex = mLazySpanLookup.getSpan(position);
1066            Span currentSpan;
1067            if (spanIndex == LayoutParams.INVALID_SPAN_ID) {
1068                if (lp.mFullSpan) {
1069                    // assign full span items to first span
1070                    currentSpan = mSpans[0];
1071                } else {
1072                    currentSpan = getNextSpan(layoutState);
1073                }
1074                mLazySpanLookup.setSpan(position, currentSpan);
1075            } else {
1076                currentSpan = mSpans[spanIndex];
1077            }
1078            final int start;
1079            final int end;
1080            if (layoutState.mLayoutDirection == LAYOUT_END) {
1081                final int def = mShouldReverseLayout ? mPrimaryOrientation.getEndAfterPadding()
1082                        : mPrimaryOrientation.getStartAfterPadding();
1083                start = lp.mFullSpan ? getMaxEnd(def) : currentSpan.getEndLine(def);
1084                end = start + mPrimaryOrientation.getDecoratedMeasurement(view);
1085                if (lp.mFullSpan) {
1086                    for (int i = 0; i < mSpanCount; i++) {
1087                        mSpans[i].appendToSpan(view);
1088                    }
1089                } else {
1090                    currentSpan.appendToSpan(view);
1091                }
1092            } else {
1093                final int def = mShouldReverseLayout ? mPrimaryOrientation.getEndAfterPadding()
1094                        : mPrimaryOrientation.getStartAfterPadding();
1095                end = lp.mFullSpan ? getMinStart(def) : currentSpan.getStartLine(def);
1096                start = end - mPrimaryOrientation.getDecoratedMeasurement(view);
1097                if (lp.mFullSpan) {
1098                    for (int i = 0; i < mSpanCount; i++) {
1099                        mSpans[i].prependToSpan(view);
1100                    }
1101                } else {
1102                    currentSpan.prependToSpan(view);
1103                }
1104
1105            }
1106            lp.mSpan = currentSpan;
1107
1108            if (DEBUG) {
1109                Log.d(TAG, "adding view item " + lp.getViewPosition() + " between " + start + ","
1110                        + end);
1111            }
1112
1113            final int otherStart = lp.mFullSpan ? mSecondaryOrientation.getStartAfterPadding()
1114                    : currentSpan.mIndex * mSizePerSpan + mSecondaryOrientation
1115                            .getStartAfterPadding();
1116            final int otherEnd = otherStart + mSecondaryOrientation.getDecoratedMeasurement(view);
1117            if (mOrientation == VERTICAL) {
1118                layoutDecoratedWithMargins(view, otherStart, start, otherEnd, end);
1119            } else {
1120                layoutDecoratedWithMargins(view, start, otherStart, end, otherEnd);
1121            }
1122            if (lp.mFullSpan) {
1123                for (int i = 0; i < mSpanCount; i++) {
1124                    updateRemainingSpans(mSpans[i], mLayoutState.mLayoutDirection, targetLine);
1125                }
1126            } else {
1127                updateRemainingSpans(currentSpan, mLayoutState.mLayoutDirection, targetLine);
1128            }
1129            if (mLayoutState.mLayoutDirection == LAYOUT_START) {
1130                // calculate recycle line
1131                int maxStart = getMaxStart(currentSpan.getStartLine());
1132                recycleFromEnd(recycler, Math.max(recycleLine, maxStart) +
1133                        (mPrimaryOrientation.getEnd() - mPrimaryOrientation.getStartAfterPadding()));
1134            } else {
1135                // calculate recycle line
1136                int minEnd = getMinEnd(currentSpan.getEndLine());
1137                recycleFromStart(recycler, Math.min(recycleLine, minEnd) -
1138                        (mPrimaryOrientation.getEnd() - mPrimaryOrientation.getStartAfterPadding()));
1139            }
1140        }
1141        if (DEBUG) {
1142            Log.d(TAG, "fill, " + getChildCount());
1143        }
1144        if (mLayoutState.mLayoutDirection == LAYOUT_START) {
1145            final int minStart = getMinStart(mPrimaryOrientation.getStartAfterPadding());
1146            return Math.max(0, mLayoutState.mAvailable + (recycleLine - minStart));
1147        } else {
1148            final int max = getMaxEnd(mPrimaryOrientation.getEndAfterPadding());
1149            return Math.max(0, mLayoutState.mAvailable + (max - recycleLine));
1150        }
1151    }
1152
1153    private void layoutDecoratedWithMargins(View child, int left, int top, int right,
1154            int bottom) {
1155        LayoutParams lp = (LayoutParams) child.getLayoutParams();
1156        layoutDecorated(child, left + lp.leftMargin, top + lp.topMargin, right - lp.rightMargin
1157                , bottom - lp.bottomMargin);
1158    }
1159
1160    private void updateRemainingSpans(Span span, int layoutDir, int targetLine) {
1161        final int deletedSize = span.getDeletedSize();
1162        if (layoutDir == LAYOUT_START) {
1163            final int line = span.getStartLine();
1164            if (line + deletedSize < targetLine) {
1165                mRemainingSpans.set(span.mIndex, false);
1166            }
1167        } else {
1168            final int line = span.getEndLine();
1169            if (line - deletedSize > targetLine) {
1170                mRemainingSpans.set(span.mIndex, false);
1171            }
1172        }
1173    }
1174
1175    private int getMaxStart(int def) {
1176        int maxStart = mSpans[0].getStartLine(def);
1177        for (int i = 1; i < mSpanCount; i++) {
1178            final int spanStart = mSpans[i].getStartLine(def);
1179            if (spanStart > maxStart) {
1180                maxStart = spanStart;
1181            }
1182        }
1183        return maxStart;
1184    }
1185
1186    private int getMinStart(int def) {
1187        int minStart = mSpans[0].getStartLine(def);
1188        for (int i = 1; i < mSpanCount; i++) {
1189            final int spanStart = mSpans[i].getStartLine(def);
1190            if (spanStart < minStart) {
1191                minStart = spanStart;
1192            }
1193        }
1194        return minStart;
1195    }
1196
1197    private int getMaxEnd(int def) {
1198        int maxEnd = mSpans[0].getEndLine(def);
1199        for (int i = 1; i < mSpanCount; i++) {
1200            final int spanEnd = mSpans[i].getEndLine(def);
1201            if (spanEnd > maxEnd) {
1202                maxEnd = spanEnd;
1203            }
1204        }
1205        return maxEnd;
1206    }
1207
1208    private int getMinEnd(int def) {
1209        int minEnd = mSpans[0].getEndLine(def);
1210        for (int i = 1; i < mSpanCount; i++) {
1211            final int spanEnd = mSpans[i].getEndLine(def);
1212            if (spanEnd < minEnd) {
1213                minEnd = spanEnd;
1214            }
1215        }
1216        return minEnd;
1217    }
1218
1219    private void recycleFromStart(RecyclerView.Recycler recycler, int line) {
1220        if (DEBUG) {
1221            Log.d(TAG, "recycling from start for line " + line);
1222        }
1223        while (getChildCount() > 0) {
1224            View child = getChildAt(0);
1225            if (mPrimaryOrientation.getDecoratedEnd(child) < line) {
1226                LayoutParams lp = (LayoutParams) child.getLayoutParams();
1227                if (lp.mFullSpan) {
1228                    for (int j = 0; j < mSpanCount; j++) {
1229                        mSpans[j].popStart();
1230                    }
1231                } else {
1232                    lp.mSpan.popStart();
1233                }
1234                removeAndRecycleView(child, recycler);
1235            } else {
1236                return;// done
1237            }
1238        }
1239    }
1240
1241    private void recycleFromEnd(RecyclerView.Recycler recycler, int line) {
1242        final int childCount = getChildCount();
1243        int i;
1244        for (i = childCount - 1; i >= 0; i--) {
1245            View child = getChildAt(i);
1246            if (mPrimaryOrientation.getDecoratedStart(child) > line) {
1247                LayoutParams lp = (LayoutParams) child.getLayoutParams();
1248                if (lp.mFullSpan) {
1249                    for (int j = 0; j < mSpanCount; j++) {
1250                        mSpans[j].popEnd();
1251                    }
1252                } else {
1253                    lp.mSpan.popEnd();
1254                }
1255                removeAndRecycleView(child, recycler);
1256            } else {
1257                return;// done
1258            }
1259        }
1260    }
1261
1262    /**
1263     * Finds the span for the next view.
1264     */
1265    private Span getNextSpan(LayoutState layoutState) {
1266        final boolean preferLastSpan = mOrientation == VERTICAL && isLayoutRTL();
1267        if (layoutState.mLayoutDirection == LAYOUT_END) {
1268            Span min = mSpans[0];
1269            int minLine = min.getEndLine(mPrimaryOrientation.getStartAfterPadding());
1270            final int defaultLine = mPrimaryOrientation.getStartAfterPadding();
1271            for (int i = 1; i < mSpanCount; i++) {
1272                final Span other = mSpans[i];
1273                final int otherLine = other.getEndLine(defaultLine);
1274                if (otherLine < minLine || (otherLine == minLine && preferLastSpan)) {
1275                    min = other;
1276                    minLine = otherLine;
1277                }
1278            }
1279            return min;
1280        } else {
1281            Span max = mSpans[0];
1282            int maxLine = max.getStartLine(mPrimaryOrientation.getEndAfterPadding());
1283            final int defaultLine = mPrimaryOrientation.getEndAfterPadding();
1284            for (int i = 1; i < mSpanCount; i++) {
1285                final Span other = mSpans[i];
1286                final int otherLine = other.getStartLine(defaultLine);
1287                if (otherLine > maxLine || (otherLine == maxLine && !preferLastSpan)) {
1288                    max = other;
1289                    maxLine = otherLine;
1290                }
1291            }
1292            return max;
1293        }
1294    }
1295
1296    @Override
1297    public boolean canScrollVertically() {
1298        return mOrientation == VERTICAL;
1299    }
1300
1301    @Override
1302    public boolean canScrollHorizontally() {
1303        return mOrientation == HORIZONTAL;
1304    }
1305
1306    @Override
1307    public int scrollHorizontallyBy(int dx, RecyclerView.Recycler recycler,
1308            RecyclerView.State state) {
1309        return scrollBy(dx, recycler, state);
1310    }
1311
1312    @Override
1313    public int scrollVerticallyBy(int dy, RecyclerView.Recycler recycler,
1314            RecyclerView.State state) {
1315        return scrollBy(dy, recycler, state);
1316    }
1317
1318    private int calculateScrollDirectionForPosition(int position) {
1319        if (getChildCount() == 0) {
1320            return mShouldReverseLayout ? LAYOUT_END : LAYOUT_START;
1321        }
1322        final int firstChildPos = getFirstChildPosition();
1323        return position < firstChildPos != mShouldReverseLayout ? LAYOUT_START : LAYOUT_END;
1324    }
1325
1326    @Override
1327    public void smoothScrollToPosition(RecyclerView recyclerView, RecyclerView.State state,
1328            int position) {
1329        LinearSmoothScroller scroller = new LinearSmoothScroller(recyclerView.getContext()) {
1330            @Override
1331            public PointF computeScrollVectorForPosition(int targetPosition) {
1332                final int direction = calculateScrollDirectionForPosition(targetPosition);
1333                if (direction == 0) {
1334                    return null;
1335                }
1336                if (mOrientation == HORIZONTAL) {
1337                    return new PointF(direction, 0);
1338                } else {
1339                    return new PointF(0, direction);
1340                }
1341            }
1342        };
1343        scroller.setTargetPosition(position);
1344        startSmoothScroll(scroller);
1345    }
1346
1347    @Override
1348    public void scrollToPosition(int position) {
1349        if (mPendingSavedState != null && mPendingSavedState.mAnchorPosition != position) {
1350            mPendingSavedState.invalidateAnchorPositionInfo();
1351        }
1352        mPendingScrollPosition = position;
1353        mPendingScrollPositionOffset = INVALID_OFFSET;
1354        requestLayout();
1355    }
1356
1357    /**
1358     * Scroll to the specified adapter position with the given offset from layout start.
1359     * <p>
1360     * Note that scroll position change will not be reflected until the next layout call.
1361     * <p>
1362     * If you are just trying to make a position visible, use {@link #scrollToPosition(int)}.
1363     *
1364     * @param position Index (starting at 0) of the reference item.
1365     * @param offset   The distance (in pixels) between the start edge of the item view and
1366     *                 start edge of the RecyclerView.
1367     * @see #setReverseLayout(boolean)
1368     * @see #scrollToPosition(int)
1369     */
1370    public void scrollToPositionWithOffset(int position, int offset) {
1371        if (mPendingSavedState != null) {
1372            mPendingSavedState.invalidateAnchorPositionInfo();
1373        }
1374        mPendingScrollPosition = position;
1375        mPendingScrollPositionOffset = offset;
1376        requestLayout();
1377    }
1378
1379    private int scrollBy(int dt, RecyclerView.Recycler recycler, RecyclerView.State state) {
1380        ensureOrientationHelper();
1381        final int referenceChildPosition;
1382        if (dt > 0) { // layout towards end
1383            mLayoutState.mLayoutDirection = LAYOUT_END;
1384            mLayoutState.mItemDirection = mShouldReverseLayout ? ITEM_DIRECTION_HEAD
1385                    : ITEM_DIRECTION_TAIL;
1386            referenceChildPosition = getLastChildPosition();
1387        } else {
1388            mLayoutState.mLayoutDirection = LAYOUT_START;
1389            mLayoutState.mItemDirection = mShouldReverseLayout ? ITEM_DIRECTION_TAIL
1390                    : ITEM_DIRECTION_HEAD;
1391            referenceChildPosition = getFirstChildPosition();
1392        }
1393        mLayoutState.mCurrentPosition = referenceChildPosition + mLayoutState.mItemDirection;
1394        final int absDt = Math.abs(dt);
1395        mLayoutState.mAvailable = absDt;
1396        mLayoutState.mExtra = isSmoothScrolling() ? mPrimaryOrientation.getTotalSpace() : 0;
1397        int consumed = fill(recycler, mLayoutState, state);
1398        final int totalScroll;
1399        if (absDt < consumed) {
1400            totalScroll = dt;
1401        } else if (dt < 0) {
1402            totalScroll = -consumed;
1403        } else { // dt > 0
1404            totalScroll = consumed;
1405        }
1406        if (DEBUG) {
1407            Log.d(TAG, "asked " + dt + " scrolled" + totalScroll);
1408        }
1409
1410        if (mGapStrategy == GAP_HANDLING_LAZY
1411                && mLayoutState.mItemDirection == ITEM_DIRECTION_HEAD) {
1412            final int targetStart = mPrimaryOrientation.getStartAfterPadding();
1413            final int targetEnd = mPrimaryOrientation.getEndAfterPadding();
1414            lazyOffsetSpans(-totalScroll, targetStart, targetEnd);
1415        } else {
1416            mPrimaryOrientation.offsetChildren(-totalScroll);
1417        }
1418        // always reset this if we scroll for a proper save instance state
1419        mLastLayoutFromEnd = mShouldReverseLayout;
1420
1421        if (totalScroll != 0 && mGapStrategy != GAP_HANDLING_NONE
1422                && mLayoutState.mItemDirection == ITEM_DIRECTION_HEAD && !mHasGaps) {
1423            final int addedChildCount = Math.abs(mLayoutState.mCurrentPosition
1424                    - (referenceChildPosition + mLayoutState.mItemDirection));
1425            if (addedChildCount > 0) {
1426                // check if any child has been attached to wrong span. If so, trigger a re-layout
1427                // after scroll
1428                final View viewInWrongSpan;
1429                final View referenceView = findViewByPosition(referenceChildPosition);
1430                if (referenceView == null) {
1431                    viewInWrongSpan = hasGapsToFix(0, getChildCount());
1432                } else {
1433                    if (mLayoutState.mLayoutDirection == LAYOUT_START) {
1434                        viewInWrongSpan = hasGapsToFix(0, addedChildCount);
1435                    } else {
1436                        viewInWrongSpan = hasGapsToFix(getChildCount() - addedChildCount,
1437                                getChildCount());
1438                    }
1439                }
1440                mHasGaps = viewInWrongSpan != null;
1441            }
1442        }
1443        return totalScroll;
1444    }
1445
1446    /**
1447     * The actual method that implements {@link #GAP_HANDLING_LAZY}
1448     */
1449    private void lazyOffsetSpans(int offset, int targetStart, int targetEnd) {
1450        // For each span offset children one by one.
1451        // When a fullSpan item is reached, stop and wait for other spans to reach to that span.
1452        // When all reach, offset fullSpan to max of others and continue.
1453        int childrenToOffset = getChildCount();
1454        int[] indexPerSpan = new int[mSpanCount];
1455        int[] offsetPerSpan = new int[mSpanCount];
1456
1457        final int childOrder = offset > 0 ? ITEM_DIRECTION_TAIL : ITEM_DIRECTION_HEAD;
1458        if (offset > 0) {
1459            Arrays.fill(indexPerSpan, 0);
1460        } else {
1461            for (int i = 0; i < mSpanCount; i++) {
1462                indexPerSpan[i] = mSpans[i].mViews.size() - 1;
1463            }
1464        }
1465
1466        for (int i = 0; i < mSpanCount; i++) {
1467            offsetPerSpan[i] = mSpans[i].getNormalizedOffset(offset, targetStart, targetEnd);
1468        }
1469        if (DEBUG) {
1470            Log.d(TAG, "lazy offset start. normalized: " + Arrays.toString(offsetPerSpan));
1471        }
1472
1473        while (childrenToOffset > 0) {
1474            View fullSpanView = null;
1475            for (int spanIndex = 0; spanIndex < mSpanCount; spanIndex++) {
1476                Span span = mSpans[spanIndex];
1477                int viewIndex;
1478                for (viewIndex = indexPerSpan[spanIndex];
1479                        viewIndex < span.mViews.size() && viewIndex >= 0; viewIndex += childOrder) {
1480                    View view = span.mViews.get(viewIndex);
1481                    if (DEBUG) {
1482                        Log.d(TAG, "span " + spanIndex + ", view:" + viewIndex + ", pos:"
1483                                + getPosition(view));
1484                    }
1485                    LayoutParams lp = (LayoutParams) view.getLayoutParams();
1486                    if (lp.mFullSpan) {
1487                        if (DEBUG) {
1488                            Log.d(TAG, "stopping on full span view on index " + viewIndex
1489                                    + " in span " + spanIndex);
1490                        }
1491                        fullSpanView = view;
1492                        viewIndex += childOrder;// move to next view
1493                        break;
1494                    }
1495                    // offset this child normally
1496                    mPrimaryOrientation.offsetChild(view, offsetPerSpan[spanIndex]);
1497                    final int nextChildIndex = viewIndex + childOrder;
1498                    if (nextChildIndex < span.mViews.size() && nextChildIndex >= 0) {
1499                        View nextView = span.mViews.get(nextChildIndex);
1500                        // find gap between, before offset
1501                        if (childOrder == ITEM_DIRECTION_HEAD) {// negative
1502                            offsetPerSpan[spanIndex] = Math
1503                                    .min(0, mPrimaryOrientation.getDecoratedStart(view)
1504                                            - mPrimaryOrientation.getDecoratedEnd(nextView));
1505                        } else {
1506                            offsetPerSpan[spanIndex] = Math
1507                                    .max(0, mPrimaryOrientation.getDecoratedEnd(view) -
1508                                            mPrimaryOrientation.getDecoratedStart(nextView));
1509                        }
1510                        if (DEBUG) {
1511                            Log.d(TAG, "offset diff:" + offsetPerSpan[spanIndex] + " between "
1512                                    + getPosition(nextView) + " and " + getPosition(view));
1513                        }
1514                    }
1515                    childrenToOffset--;
1516                }
1517                indexPerSpan[spanIndex] = viewIndex;
1518            }
1519            if (fullSpanView != null) {
1520                // we have to offset this view. We'll offset it as the biggest amount necessary
1521                int winnerSpan = 0;
1522                int winnerSpanOffset = Math.abs(offsetPerSpan[winnerSpan]);
1523                for (int i = 1; i < mSpanCount; i++) {
1524                    final int spanOffset = Math.abs(offsetPerSpan[i]);
1525                    if (spanOffset > winnerSpanOffset) {
1526                        winnerSpan = i;
1527                        winnerSpanOffset = spanOffset;
1528                    }
1529                }
1530                if (DEBUG) {
1531                    Log.d(TAG, "winner offset:" + offsetPerSpan[winnerSpan] + " of " + winnerSpan);
1532                }
1533                mPrimaryOrientation.offsetChild(fullSpanView, offsetPerSpan[winnerSpan]);
1534                childrenToOffset--;
1535
1536                for (int spanIndex = 0; spanIndex < mSpanCount; spanIndex++) {
1537                    final int nextViewIndex = indexPerSpan[spanIndex];
1538                    final Span span = mSpans[spanIndex];
1539                    if (nextViewIndex < span.mViews.size() && nextViewIndex > 0) {
1540                        View nextView = span.mViews.get(nextViewIndex);
1541                        // find gap between, before offset
1542                        if (childOrder == ITEM_DIRECTION_HEAD) {// negative
1543                            offsetPerSpan[spanIndex] = Math
1544                                    .min(0, mPrimaryOrientation.getDecoratedStart(fullSpanView)
1545                                            - mPrimaryOrientation.getDecoratedEnd(nextView));
1546                        } else {
1547                            offsetPerSpan[spanIndex] = Math
1548                                    .max(0, mPrimaryOrientation.getDecoratedEnd(fullSpanView) -
1549                                            mPrimaryOrientation.getDecoratedStart(nextView));
1550                        }
1551                    }
1552                }
1553            }
1554        }
1555        for (int spanIndex = 0; spanIndex < mSpanCount; spanIndex++) {
1556            mSpans[spanIndex].invalidateCache();
1557        }
1558    }
1559
1560    private int getLastChildPosition() {
1561        final int childCount = getChildCount();
1562        return childCount == 0 ? 0 : getPosition(getChildAt(childCount - 1));
1563    }
1564
1565    private int getFirstChildPosition() {
1566        final int childCount = getChildCount();
1567        return childCount == 0 ? 0 : getPosition(getChildAt(0));
1568    }
1569
1570    /**
1571     * Finds the first View that can be used as an anchor View.
1572     *
1573     * @return Position of the View or 0 if it cannot find any such View.
1574     */
1575    private int findFirstReferenceChildPosition(int itemCount) {
1576        final int limit = getChildCount();
1577        for (int i = 0; i < limit; i++) {
1578            final View view = getChildAt(i);
1579            final int position = getPosition(view);
1580            if (position >= 0 && position < itemCount) {
1581                return position;
1582            }
1583        }
1584        return 0;
1585    }
1586
1587    /**
1588     * Finds the last View that can be used as an anchor View.
1589     *
1590     * @return Position of the View or 0 if it cannot find any such View.
1591     */
1592    private int findLastReferenceChildPosition(int itemCount) {
1593        for (int i = getChildCount() - 1; i >= 0; i--) {
1594            final View view = getChildAt(i);
1595            final int position = getPosition(view);
1596            if (position >= 0 && position < itemCount) {
1597                return position;
1598            }
1599        }
1600        return 0;
1601    }
1602
1603    @Override
1604    public RecyclerView.LayoutParams generateDefaultLayoutParams() {
1605        return new LayoutParams(ViewGroup.LayoutParams.WRAP_CONTENT,
1606                ViewGroup.LayoutParams.WRAP_CONTENT);
1607    }
1608
1609    @Override
1610    public RecyclerView.LayoutParams generateLayoutParams(Context c, AttributeSet attrs) {
1611        return new LayoutParams(c, attrs);
1612    }
1613
1614    @Override
1615    public RecyclerView.LayoutParams generateLayoutParams(ViewGroup.LayoutParams lp) {
1616        if (lp instanceof ViewGroup.MarginLayoutParams) {
1617            return new LayoutParams((ViewGroup.MarginLayoutParams) lp);
1618        } else {
1619            return new LayoutParams(lp);
1620        }
1621    }
1622
1623    @Override
1624    public boolean checkLayoutParams(RecyclerView.LayoutParams lp) {
1625        return lp instanceof LayoutParams;
1626    }
1627
1628    public int getOrientation() {
1629        return mOrientation;
1630    }
1631
1632
1633    /**
1634     * LayoutParams used by StaggeredGridLayoutManager.
1635     */
1636    public static class LayoutParams extends RecyclerView.LayoutParams {
1637
1638        /**
1639         * Span Id for Views that are not laid out yet.
1640         */
1641        public static final int INVALID_SPAN_ID = -1;
1642
1643        // Package scope to be able to access from tests.
1644        Span mSpan;
1645
1646        boolean mFullSpan;
1647
1648        public LayoutParams(Context c, AttributeSet attrs) {
1649            super(c, attrs);
1650        }
1651
1652        public LayoutParams(int width, int height) {
1653            super(width, height);
1654        }
1655
1656        public LayoutParams(ViewGroup.MarginLayoutParams source) {
1657            super(source);
1658        }
1659
1660        public LayoutParams(ViewGroup.LayoutParams source) {
1661            super(source);
1662        }
1663
1664        public LayoutParams(RecyclerView.LayoutParams source) {
1665            super(source);
1666        }
1667
1668        /**
1669         * When set to true, the item will layout using all span area. That means, if orientation
1670         * is vertical, the view will have full width; if orientation is horizontal, the view will
1671         * have full height.
1672         *
1673         * @param fullSpan True if this item should traverse all spans.
1674         */
1675        public void setFullSpan(boolean fullSpan) {
1676            mFullSpan = fullSpan;
1677        }
1678
1679        /**
1680         * Returns the Span index to which this View is assigned.
1681         *
1682         * @return The Span index of the View. If View is not yet assigned to any span, returns
1683         * {@link #INVALID_SPAN_ID}.
1684         */
1685        public final int getSpanIndex() {
1686            if (mSpan == null) {
1687                return INVALID_SPAN_ID;
1688            }
1689            return mSpan.mIndex;
1690        }
1691    }
1692
1693    // Package scoped to access from tests.
1694    class Span {
1695
1696        static final int INVALID_LINE = Integer.MIN_VALUE;
1697
1698        private ArrayList<View> mViews = new ArrayList<View>();
1699
1700        int mCachedStart = INVALID_LINE;
1701
1702        int mCachedEnd = INVALID_LINE;
1703
1704        int mDeletedSize = 0;
1705
1706        final int mIndex;
1707
1708        private Span(int index) {
1709            mIndex = index;
1710        }
1711
1712        int getStartLine(int def) {
1713            if (mCachedStart != INVALID_LINE) {
1714                return mCachedStart;
1715            }
1716            if (mViews.size() == 0) {
1717                return def;
1718            }
1719            mCachedStart = mPrimaryOrientation.getDecoratedStart(mViews.get(0));
1720            return mCachedStart;
1721        }
1722
1723        // Use this one when default value does not make sense and not having a value means a bug.
1724        int getStartLine() {
1725            if (mCachedStart != INVALID_LINE) {
1726                return mCachedStart;
1727            }
1728            mCachedStart = mPrimaryOrientation.getDecoratedStart(mViews.get(0));
1729            return mCachedStart;
1730        }
1731
1732        int getEndLine(int def) {
1733            if (mCachedEnd != INVALID_LINE) {
1734                return mCachedEnd;
1735            }
1736            final int size = mViews.size();
1737            if (size == 0) {
1738                return def;
1739            }
1740            mCachedEnd = mPrimaryOrientation.getDecoratedEnd(mViews.get(size - 1));
1741            return mCachedEnd;
1742        }
1743
1744        // Use this one when default value does not make sense and not having a value means a bug.
1745        int getEndLine() {
1746            if (mCachedEnd != INVALID_LINE) {
1747                return mCachedEnd;
1748            }
1749            mCachedEnd = mPrimaryOrientation.getDecoratedEnd(mViews.get(mViews.size() - 1));
1750            return mCachedEnd;
1751        }
1752
1753        void prependToSpan(View view) {
1754            LayoutParams lp = getLayoutParams(view);
1755            lp.mSpan = this;
1756            mViews.add(0, view);
1757            mCachedStart = INVALID_LINE;
1758            if (mViews.size() == 1) {
1759                mCachedEnd = INVALID_LINE;
1760            }
1761            if (lp.isItemRemoved() || lp.isItemChanged()) {
1762                mDeletedSize += mPrimaryOrientation.getDecoratedMeasurement(view);
1763            }
1764        }
1765
1766        void appendToSpan(View view) {
1767            LayoutParams lp = getLayoutParams(view);
1768            lp.mSpan = this;
1769            mViews.add(view);
1770            mCachedEnd = INVALID_LINE;
1771            if (mViews.size() == 1) {
1772                mCachedStart = INVALID_LINE;
1773            }
1774            if (lp.isItemRemoved() || lp.isItemChanged()) {
1775                mDeletedSize += mPrimaryOrientation.getDecoratedMeasurement(view);
1776            }
1777        }
1778
1779        // Useful method to preserve positions on a re-layout.
1780        void cacheReferenceLineAndClear(boolean reverseLayout, int offset) {
1781            int reference;
1782            if (reverseLayout) {
1783                reference = getEndLine(INVALID_LINE);
1784            } else {
1785                reference = getStartLine(INVALID_LINE);
1786            }
1787            clear();
1788            if (reference == INVALID_LINE) {
1789                return;
1790            }
1791            if (offset != INVALID_OFFSET) {
1792                reference += offset;
1793            }
1794            mCachedStart = mCachedEnd = reference;
1795        }
1796
1797        void clear() {
1798            mViews.clear();
1799            invalidateCache();
1800            mDeletedSize = 0;
1801        }
1802
1803        void invalidateCache() {
1804            mCachedStart = INVALID_LINE;
1805            mCachedEnd = INVALID_LINE;
1806        }
1807
1808        void setLine(int line) {
1809            mCachedEnd = mCachedStart = line;
1810        }
1811
1812        void popEnd() {
1813            final int size = mViews.size();
1814            View end = mViews.remove(size - 1);
1815            final LayoutParams lp = getLayoutParams(end);
1816            lp.mSpan = null;
1817            if (lp.isItemRemoved() || lp.isItemChanged()) {
1818                mDeletedSize -= mPrimaryOrientation.getDecoratedMeasurement(end);
1819            }
1820            if (size == 1) {
1821                mCachedStart = INVALID_LINE;
1822            }
1823            mCachedEnd = INVALID_LINE;
1824        }
1825
1826        void popStart() {
1827            View start = mViews.remove(0);
1828            final LayoutParams lp = getLayoutParams(start);
1829            lp.mSpan = null;
1830            if (mViews.size() == 0) {
1831                mCachedEnd = INVALID_LINE;
1832            }
1833            if (lp.isItemRemoved() || lp.isItemChanged()) {
1834                mDeletedSize -= mPrimaryOrientation.getDecoratedMeasurement(start);
1835            }
1836            mCachedStart = INVALID_LINE;
1837        }
1838
1839        // TODO cache this.
1840        public int getDeletedSize() {
1841            return mDeletedSize;
1842        }
1843
1844        LayoutParams getLayoutParams(View view) {
1845            return (LayoutParams) view.getLayoutParams();
1846        }
1847
1848        void onOffset(int dt) {
1849            if (mCachedStart != INVALID_LINE) {
1850                mCachedStart += dt;
1851            }
1852            if (mCachedEnd != INVALID_LINE) {
1853                mCachedEnd += dt;
1854            }
1855        }
1856
1857        // normalized offset is how much this span can scroll
1858        int getNormalizedOffset(int dt, int targetStart, int targetEnd) {
1859            if (mViews.size() == 0) {
1860                return 0;
1861            }
1862            if (dt < 0) {
1863                final int endSpace = getEndLine() - targetEnd;
1864                if (endSpace <= 0) {
1865                    return 0;
1866                }
1867                return -dt > endSpace ? -endSpace : dt;
1868            } else {
1869                final int startSpace = targetStart - getStartLine();
1870                if (startSpace <= 0) {
1871                    return 0;
1872                }
1873                return startSpace < dt ? startSpace : dt;
1874            }
1875        }
1876
1877        /**
1878         * Returns if there is no child between start-end lines
1879         *
1880         * @param start The start line
1881         * @param end   The end line
1882         * @return true if a new child can be added between start and end
1883         */
1884        boolean isEmpty(int start, int end) {
1885            final int count = mViews.size();
1886            for (int i = 0; i < count; i++) {
1887                final View view = mViews.get(i);
1888                if (mPrimaryOrientation.getDecoratedStart(view) < end &&
1889                        mPrimaryOrientation.getDecoratedEnd(view) > start) {
1890                    return false;
1891                }
1892            }
1893            return true;
1894        }
1895
1896        public int findFirstVisibleItemPosition() {
1897            return mReverseLayout
1898                    ? findOneVisibleChild(mViews.size() - 1, -1, false)
1899                    : findOneVisibleChild(0, mViews.size(), false);
1900        }
1901
1902        public int findFirstCompletelyVisibleItemPosition() {
1903            return mReverseLayout
1904                    ? findOneVisibleChild(mViews.size() -1, -1, true)
1905                    : findOneVisibleChild(0, mViews.size(), true);
1906        }
1907
1908        public int findLastVisibleItemPosition() {
1909            return mReverseLayout
1910                    ? findOneVisibleChild(0, mViews.size(), false)
1911                    : findOneVisibleChild(mViews.size() - 1, -1, false);
1912        }
1913
1914        public int findLastCompletelyVisibleItemPosition() {
1915            return mReverseLayout
1916                    ? findOneVisibleChild(0, mViews.size(), true)
1917                    : findOneVisibleChild(mViews.size() - 1, -1, true);
1918        }
1919
1920        int findOneVisibleChild(int fromIndex, int toIndex, boolean completelyVisible) {
1921            final int start = mPrimaryOrientation.getStartAfterPadding();
1922            final int end = mPrimaryOrientation.getEndAfterPadding();
1923            final int next = toIndex > fromIndex ? 1 : -1;
1924            for (int i = fromIndex; i != toIndex; i+=next) {
1925                final View child = mViews.get(i);
1926                final int childStart = mPrimaryOrientation.getDecoratedStart(child);
1927                final int childEnd = mPrimaryOrientation.getDecoratedEnd(child);
1928                if (childStart < end && childEnd > start) {
1929                    if (completelyVisible) {
1930                        if (childStart >= start && childEnd <= end) {
1931                            return getPosition(child);
1932                        }
1933                    } else {
1934                        return getPosition(child);
1935                    }
1936                }
1937            }
1938            return RecyclerView.NO_POSITION;
1939        }
1940    }
1941
1942    /**
1943     * An array of mappings from adapter position to span.
1944     * This only grows when a write happens and it grows up to the size of the adapter.
1945     */
1946    static class LazySpanLookup {
1947
1948        private static final int MIN_SIZE = 10;
1949
1950        int[] mData;
1951
1952        int mAdapterSize; // we don't want to grow beyond that, unless it grows
1953
1954        void invalidateAfter(int position) {
1955            if (mData == null) {
1956                return;
1957            }
1958            if (position >= mData.length) {
1959                return;
1960            }
1961            Arrays.fill(mData, position, mData.length, LayoutParams.INVALID_SPAN_ID);
1962        }
1963
1964        int getSpan(int position) {
1965            if (mData == null || position >= mData.length) {
1966                return LayoutParams.INVALID_SPAN_ID;
1967            } else {
1968                return mData[position];
1969            }
1970        }
1971
1972        void setSpan(int position, Span span) {
1973            ensureSize(position);
1974            mData[position] = span.mIndex;
1975        }
1976
1977        int sizeForPosition(int position) {
1978            int len = mData.length;
1979            while (len <= position) {
1980                len *= 2;
1981            }
1982            if (len > mAdapterSize) {
1983                len = mAdapterSize;
1984            }
1985            return len;
1986        }
1987
1988        void ensureSize(int position) {
1989            if (mData == null) {
1990                mData = new int[Math.max(position, MIN_SIZE) + 1];
1991                Arrays.fill(mData, LayoutParams.INVALID_SPAN_ID);
1992            } else if (position >= mData.length) {
1993                int[] old = mData;
1994                mData = new int[sizeForPosition(position)];
1995                System.arraycopy(old, 0, mData, 0, old.length);
1996                Arrays.fill(mData, old.length, mData.length, LayoutParams.INVALID_SPAN_ID);
1997            }
1998        }
1999
2000        void clear() {
2001            if (mData != null) {
2002                Arrays.fill(mData, LayoutParams.INVALID_SPAN_ID);
2003            }
2004        }
2005
2006        void offsetForRemoval(int positionStart, int itemCount) {
2007            ensureSize(positionStart + itemCount);
2008            System.arraycopy(mData, positionStart + itemCount, mData, positionStart,
2009                    mData.length - positionStart - itemCount);
2010            Arrays.fill(mData, mData.length - itemCount, mData.length,
2011                    LayoutParams.INVALID_SPAN_ID);
2012        }
2013
2014        void offsetForAddition(int positionStart, int itemCount) {
2015            ensureSize(positionStart + itemCount);
2016            System.arraycopy(mData, positionStart, mData, positionStart + itemCount,
2017                    mData.length - positionStart - itemCount);
2018            Arrays.fill(mData, positionStart, positionStart + itemCount,
2019                    LayoutParams.INVALID_SPAN_ID);
2020        }
2021    }
2022
2023    static class SavedState implements Parcelable {
2024
2025        int mOrientation;
2026
2027        int mSpanCount;
2028
2029        int mGapStrategy;
2030
2031        int mAnchorPosition;
2032
2033        int mVisibleAnchorPosition; // if span count changes (span offsets are invalidated),
2034        // we use this one instead
2035
2036        int[] mSpanOffsets;
2037
2038        int mSpanLookupSize;
2039
2040        int[] mSpanLookup;
2041
2042        boolean mReverseLayout;
2043
2044        boolean mAnchorLayoutFromEnd;
2045
2046        boolean mHasSpanOffsets;
2047
2048        public SavedState() {
2049        }
2050
2051        SavedState(Parcel in) {
2052            mOrientation = in.readInt();
2053            mSpanCount = in.readInt();
2054            mGapStrategy = in.readInt();
2055            mAnchorPosition = in.readInt();
2056            mVisibleAnchorPosition = in.readInt();
2057            mHasSpanOffsets = in.readInt() == 1;
2058            if (mHasSpanOffsets) {
2059                mSpanOffsets = new int[mSpanCount];
2060                in.readIntArray(mSpanOffsets);
2061            }
2062
2063            mSpanLookupSize = in.readInt();
2064            if (mSpanLookupSize > 0) {
2065                mSpanLookup = new int[mSpanLookupSize];
2066                in.readIntArray(mSpanLookup);
2067            }
2068            mReverseLayout = in.readInt() == 1;
2069            mAnchorLayoutFromEnd = in.readInt() == 1;
2070        }
2071
2072        public SavedState(SavedState other) {
2073            mOrientation = other.mOrientation;
2074            mSpanCount = other.mSpanCount;
2075            mGapStrategy = other.mGapStrategy;
2076            mAnchorPosition = other.mAnchorPosition;
2077            mVisibleAnchorPosition = other.mVisibleAnchorPosition;
2078            mHasSpanOffsets = other.mHasSpanOffsets;
2079            mSpanOffsets = other.mSpanOffsets;
2080            mSpanLookupSize = other.mSpanLookupSize;
2081            mSpanLookup = other.mSpanLookup;
2082            mReverseLayout = other.mReverseLayout;
2083            mAnchorLayoutFromEnd = other.mAnchorLayoutFromEnd;
2084        }
2085
2086        void invalidateSpanInfo() {
2087            mSpanOffsets = null;
2088            mHasSpanOffsets = false;
2089            mSpanCount = -1;
2090            mSpanLookupSize = 0;
2091            mSpanLookup = null;
2092        }
2093
2094        void invalidateAnchorPositionInfo() {
2095            mSpanOffsets = null;
2096            mHasSpanOffsets = false;
2097            mAnchorPosition = RecyclerView.NO_POSITION;
2098            mVisibleAnchorPosition = RecyclerView.NO_POSITION;
2099        }
2100
2101        @Override
2102        public int describeContents() {
2103            return 0;
2104        }
2105
2106        @Override
2107        public void writeToParcel(Parcel dest, int flags) {
2108            dest.writeInt(mOrientation);
2109            dest.writeInt(mSpanCount);
2110            dest.writeInt(mGapStrategy);
2111            dest.writeInt(mAnchorPosition);
2112            dest.writeInt(mVisibleAnchorPosition);
2113            dest.writeInt(mHasSpanOffsets ? 1 : 0);
2114            if (mHasSpanOffsets) {
2115                dest.writeIntArray(mSpanOffsets);
2116            }
2117            dest.writeInt(mSpanLookupSize);
2118            if (mSpanLookupSize > 0) {
2119                dest.writeIntArray(mSpanLookup);
2120            }
2121            dest.writeInt(mReverseLayout ? 1 : 0);
2122            dest.writeInt(mAnchorLayoutFromEnd ? 1 : 0);
2123        }
2124
2125        @Override
2126        public String toString() {
2127            return "SavedState{" +
2128                    "mOrientation=" + mOrientation +
2129                    ", mSpanCount=" + mSpanCount +
2130                    ", mGapStrategy=" + mGapStrategy +
2131                    ", mAnchorPosition=" + mAnchorPosition +
2132                    ", mVisibleAnchorPosition=" + mVisibleAnchorPosition +
2133                    ", mSpanOffsets=" + Arrays.toString(mSpanOffsets) +
2134                    ", mSpanLookupSize=" + mSpanLookupSize +
2135                    ", mSpanLookup=" + Arrays.toString(mSpanLookup) +
2136                    ", mReverseLayout=" + mReverseLayout +
2137                    ", mAnchorLayoutFromEnd=" + mAnchorLayoutFromEnd +
2138                    ", mHasSpanOffsets=" + mHasSpanOffsets +
2139                    '}';
2140        }
2141
2142        public static final Parcelable.Creator<SavedState> CREATOR
2143                = new Parcelable.Creator<SavedState>() {
2144            @Override
2145            public SavedState createFromParcel(Parcel in) {
2146                return new SavedState(in);
2147            }
2148
2149            @Override
2150            public SavedState[] newArray(int size) {
2151                return new SavedState[size];
2152            }
2153        };
2154    }
2155}
2156