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