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