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 
17 package android.support.v7.widget;
18 
19 import java.util.List;
20 
21 import android.support.v7.widget.AdapterHelper.UpdateOp;
22 import static android.support.v7.widget.AdapterHelper.UpdateOp.ADD;
23 import static android.support.v7.widget.AdapterHelper.UpdateOp.MOVE;
24 import static android.support.v7.widget.AdapterHelper.UpdateOp.REMOVE;
25 import static android.support.v7.widget.AdapterHelper.UpdateOp.UPDATE;
26 
27 class OpReorderer {
28 
29     final Callback mCallback;
30 
OpReorderer(Callback callback)31     public OpReorderer(Callback callback) {
32         mCallback = callback;
33     }
34 
reorderOps(List<UpdateOp> ops)35     void reorderOps(List<UpdateOp> ops) {
36         // since move operations breaks continuity, their effects on ADD/RM are hard to handle.
37         // we push them to the end of the list so that they can be handled easily.
38         int badMove;
39         while ((badMove = getLastMoveOutOfOrder(ops)) != -1) {
40             swapMoveOp(ops, badMove, badMove + 1);
41         }
42     }
43 
swapMoveOp(List<UpdateOp> list, int badMove, int next)44     private void swapMoveOp(List<UpdateOp> list, int badMove, int next) {
45         final UpdateOp moveOp = list.get(badMove);
46         final UpdateOp nextOp = list.get(next);
47         switch (nextOp.cmd) {
48             case REMOVE:
49                 swapMoveRemove(list, badMove, moveOp, next, nextOp);
50                 break;
51             case ADD:
52                 swapMoveAdd(list, badMove, moveOp, next, nextOp);
53                 break;
54             case UPDATE:
55                 swapMoveUpdate(list, badMove, moveOp, next, nextOp);
56                 break;
57         }
58     }
59 
swapMoveRemove(List<UpdateOp> list, int movePos, UpdateOp moveOp, int removePos, UpdateOp removeOp)60     void swapMoveRemove(List<UpdateOp> list, int movePos, UpdateOp moveOp,
61             int removePos, UpdateOp removeOp) {
62         UpdateOp extraRm = null;
63         // check if move is nulled out by remove
64         boolean revertedMove = false;
65         final boolean moveIsBackwards;
66 
67         if (moveOp.positionStart < moveOp.itemCount) {
68             moveIsBackwards = false;
69             if (removeOp.positionStart == moveOp.positionStart
70                     && removeOp.itemCount == moveOp.itemCount - moveOp.positionStart) {
71                 revertedMove = true;
72             }
73         } else {
74             moveIsBackwards = true;
75             if (removeOp.positionStart == moveOp.itemCount + 1 &&
76                     removeOp.itemCount == moveOp.positionStart - moveOp.itemCount) {
77                 revertedMove = true;
78             }
79         }
80 
81         // going in reverse, first revert the effect of add
82         if (moveOp.itemCount < removeOp.positionStart) {
83             removeOp.positionStart--;
84         } else if (moveOp.itemCount < removeOp.positionStart + removeOp.itemCount) {
85             // move is removed.
86             removeOp.itemCount --;
87             moveOp.cmd = REMOVE;
88             moveOp.itemCount = 1;
89             if (removeOp.itemCount == 0) {
90                 list.remove(removePos);
91                 mCallback.recycleUpdateOp(removeOp);
92             }
93             // no need to swap, it is already a remove
94             return;
95         }
96 
97         // now affect of add is consumed. now apply effect of first remove
98         if (moveOp.positionStart <= removeOp.positionStart) {
99             removeOp.positionStart++;
100         } else if (moveOp.positionStart < removeOp.positionStart + removeOp.itemCount) {
101             final int remaining = removeOp.positionStart + removeOp.itemCount
102                     - moveOp.positionStart;
103             extraRm = mCallback.obtainUpdateOp(REMOVE, moveOp.positionStart + 1, remaining, null);
104             removeOp.itemCount = moveOp.positionStart - removeOp.positionStart;
105         }
106 
107         // if effects of move is reverted by remove, we are done.
108         if (revertedMove) {
109             list.set(movePos, removeOp);
110             list.remove(removePos);
111             mCallback.recycleUpdateOp(moveOp);
112             return;
113         }
114 
115         // now find out the new locations for move actions
116         if (moveIsBackwards) {
117             if (extraRm != null) {
118                 if (moveOp.positionStart > extraRm.positionStart) {
119                     moveOp.positionStart -= extraRm.itemCount;
120                 }
121                 if (moveOp.itemCount > extraRm.positionStart) {
122                     moveOp.itemCount -= extraRm.itemCount;
123                 }
124             }
125             if (moveOp.positionStart > removeOp.positionStart) {
126                 moveOp.positionStart -= removeOp.itemCount;
127             }
128             if (moveOp.itemCount > removeOp.positionStart) {
129                 moveOp.itemCount -= removeOp.itemCount;
130             }
131         } else {
132             if (extraRm != null) {
133                 if (moveOp.positionStart >= extraRm.positionStart) {
134                     moveOp.positionStart -= extraRm.itemCount;
135                 }
136                 if (moveOp.itemCount >= extraRm.positionStart) {
137                     moveOp.itemCount -= extraRm.itemCount;
138                 }
139             }
140             if (moveOp.positionStart >= removeOp.positionStart) {
141                 moveOp.positionStart -= removeOp.itemCount;
142             }
143             if (moveOp.itemCount >= removeOp.positionStart) {
144                 moveOp.itemCount -= removeOp.itemCount;
145             }
146         }
147 
148         list.set(movePos, removeOp);
149         if (moveOp.positionStart != moveOp.itemCount) {
150             list.set(removePos, moveOp);
151         } else {
152             list.remove(removePos);
153         }
154         if (extraRm != null) {
155             list.add(movePos, extraRm);
156         }
157     }
158 
swapMoveAdd(List<UpdateOp> list, int move, UpdateOp moveOp, int add, UpdateOp addOp)159     private void swapMoveAdd(List<UpdateOp> list, int move, UpdateOp moveOp, int add,
160             UpdateOp addOp) {
161         int offset = 0;
162         // going in reverse, first revert the effect of add
163         if (moveOp.itemCount < addOp.positionStart) {
164             offset--;
165         }
166         if (moveOp.positionStart < addOp.positionStart) {
167             offset++;
168         }
169         if (addOp.positionStart <= moveOp.positionStart) {
170             moveOp.positionStart += addOp.itemCount;
171         }
172         if (addOp.positionStart <= moveOp.itemCount) {
173             moveOp.itemCount += addOp.itemCount;
174         }
175         addOp.positionStart += offset;
176         list.set(move, addOp);
177         list.set(add, moveOp);
178     }
179 
swapMoveUpdate(List<UpdateOp> list, int move, UpdateOp moveOp, int update, UpdateOp updateOp)180     void swapMoveUpdate(List<UpdateOp> list, int move, UpdateOp moveOp, int update,
181             UpdateOp updateOp) {
182         UpdateOp extraUp1 = null;
183         UpdateOp extraUp2 = null;
184         // going in reverse, first revert the effect of add
185         if (moveOp.itemCount < updateOp.positionStart) {
186             updateOp.positionStart--;
187         } else if (moveOp.itemCount < updateOp.positionStart + updateOp.itemCount) {
188             // moved item is updated. add an update for it
189             updateOp.itemCount--;
190             extraUp1 = mCallback.obtainUpdateOp(UPDATE, moveOp.positionStart, 1, updateOp.payload);
191         }
192         // now affect of add is consumed. now apply effect of first remove
193         if (moveOp.positionStart <= updateOp.positionStart) {
194             updateOp.positionStart++;
195         } else if (moveOp.positionStart < updateOp.positionStart + updateOp.itemCount) {
196             final int remaining = updateOp.positionStart + updateOp.itemCount
197                     - moveOp.positionStart;
198             extraUp2 = mCallback.obtainUpdateOp(UPDATE, moveOp.positionStart + 1, remaining,
199                     updateOp.payload);
200             updateOp.itemCount -= remaining;
201         }
202         list.set(update, moveOp);
203         if (updateOp.itemCount > 0) {
204             list.set(move, updateOp);
205         } else {
206             list.remove(move);
207             mCallback.recycleUpdateOp(updateOp);
208         }
209         if (extraUp1 != null) {
210             list.add(move, extraUp1);
211         }
212         if (extraUp2 != null) {
213             list.add(move, extraUp2);
214         }
215     }
216 
getLastMoveOutOfOrder(List<UpdateOp> list)217     private int getLastMoveOutOfOrder(List<UpdateOp> list) {
218         boolean foundNonMove = false;
219         for (int i = list.size() - 1; i >= 0; i--) {
220             final UpdateOp op1 = list.get(i);
221             if (op1.cmd == MOVE) {
222                 if (foundNonMove) {
223                     return i;
224                 }
225             } else {
226                 foundNonMove = true;
227             }
228         }
229         return -1;
230     }
231 
232     static interface Callback {
233 
obtainUpdateOp(int cmd, int startPosition, int itemCount, Object payload)234         UpdateOp obtainUpdateOp(int cmd, int startPosition, int itemCount, Object payload);
235 
recycleUpdateOp(UpdateOp op)236         void recycleUpdateOp(UpdateOp op);
237     }
238 }
239