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 org.junit.Before;
20import org.junit.Test;
21import org.junit.runner.RunWith;
22import org.junit.runners.JUnit4;
23
24import java.util.ArrayList;
25import java.util.HashSet;
26import java.util.List;
27import java.util.Random;
28import java.util.Set;
29
30import android.support.v7.widget.AdapterHelper.UpdateOp;
31import android.test.suitebuilder.annotation.SmallTest;
32import android.util.Log;
33
34import static android.support.v7.widget.AdapterHelper.UpdateOp.ADD;
35import static android.support.v7.widget.AdapterHelper.UpdateOp.MOVE;
36import static android.support.v7.widget.AdapterHelper.UpdateOp.REMOVE;
37import static android.support.v7.widget.AdapterHelper.UpdateOp.UPDATE;
38import static org.junit.Assert.*;
39
40@RunWith(JUnit4.class)
41@SmallTest
42public class OpReorderTest {
43
44    private static final String TAG = "OpReorderTest";
45
46    List<UpdateOp> mUpdateOps = new ArrayList<UpdateOp>();
47    List<Item> mAddedItems = new ArrayList<Item>();
48    List<Item> mRemovedItems = new ArrayList<Item>();
49    Set<UpdateOp> mRecycledOps = new HashSet<UpdateOp>();
50    static Random random = new Random(System.nanoTime());
51
52    OpReorderer mOpReorderer = new OpReorderer(new OpReorderer.Callback() {
53        @Override
54        public UpdateOp obtainUpdateOp(int cmd, int startPosition, int itemCount, Object payload) {
55            return new UpdateOp(cmd, startPosition, itemCount, payload);
56        }
57
58        @Override
59        public void recycleUpdateOp(UpdateOp op) {
60            mRecycledOps.add(op);
61        }
62    });
63
64    int itemCount = 10;
65    int updatedItemCount = 0;
66
67    public void setup(int count) {
68        itemCount = count;
69        updatedItemCount = itemCount;
70    }
71
72    @Before
73    public void setUp() throws Exception {
74        cleanState();
75    }
76
77    void cleanState() {
78        mUpdateOps = new ArrayList<UpdateOp>();
79        mAddedItems = new ArrayList<Item>();
80        mRemovedItems = new ArrayList<Item>();
81        mRecycledOps = new HashSet<UpdateOp>();
82        Item.idCounter = 0;
83    }
84
85    @Test
86    public void testMoveRemoved() throws Exception {
87        setup(10);
88        mv(3, 8);
89        rm(7, 3);
90        process();
91    }
92
93    @Test
94    public void testMoveRemove() throws Exception {
95        setup(10);
96        mv(3, 8);
97        rm(3, 5);
98        process();
99    }
100
101    @Test
102    public void test1() {
103        setup(10);
104        mv(3, 5);
105        rm(3, 4);
106        process();
107    }
108
109    @Test
110    public void test2() {
111        setup(5);
112        mv(1, 3);
113        rm(1, 1);
114        process();
115    }
116
117    @Test
118    public void test3() {
119        setup(5);
120        mv(0, 4);
121        rm(2, 1);
122        process();
123    }
124
125    @Test
126    public void test4() {
127        setup(5);
128        mv(3, 0);
129        rm(3, 1);
130        process();
131    }
132
133    @Test
134    public void test5() {
135        setup(10);
136        mv(8, 1);
137        rm(6, 3);
138        process();
139    }
140
141    @Test
142    public void test6() {
143        setup(5);
144        mv(1, 3);
145        rm(0, 3);
146        process();
147    }
148
149    @Test
150    public void test7() {
151        setup(5);
152        mv(3, 4);
153        rm(3, 1);
154        process();
155    }
156
157    @Test
158    public void test8() {
159        setup(5);
160        mv(4, 3);
161        rm(3, 1);
162        process();
163    }
164
165    @Test
166    public void test9() {
167        setup(5);
168        mv(2, 0);
169        rm(2, 2);
170        process();
171    }
172
173    @Test
174    public void testRandom() throws Exception {
175        for (int i = 0; i < 150; i++) {
176            try {
177                cleanState();
178                setup(50);
179                for (int j = 0; j < 50; j++) {
180                    randOp(nextInt(random, nextInt(random, 4)));
181                }
182                Log.d(TAG, "running random test " + i);
183                process();
184            } catch (Throwable t) {
185                throw new Exception(t.getMessage() + "\n" + opsToString(mUpdateOps));
186            }
187        }
188    }
189
190    @Test
191    public void testRandomMoveRemove() throws Exception {
192        for (int i = 0; i < 1000; i++) {
193            try {
194                cleanState();
195                setup(5);
196                orderedRandom(MOVE, REMOVE);
197                process();
198            } catch (Throwable t) {
199                throw new Exception(t.getMessage() + "\n" + opsToString(mUpdateOps));
200            }
201        }
202    }
203
204    @Test
205    public void testRandomMoveAdd() throws Exception {
206        for (int i = 0; i < 1000; i++) {
207            try {
208                cleanState();
209                setup(5);
210                orderedRandom(MOVE, ADD);
211                process();
212            } catch (Throwable t) {
213                throw new Exception(t.getMessage() + "\n" + opsToString(mUpdateOps));
214            }
215        }
216    }
217
218    @Test
219    public void testRandomMoveUpdate() throws Exception {
220        for (int i = 0; i < 1000; i++) {
221            try {
222                cleanState();
223                setup(5);
224                orderedRandom(MOVE, UPDATE);
225                process();
226            } catch (Throwable t) {
227                throw new Exception(t.getMessage() + "\n" + opsToString(mUpdateOps));
228            }
229        }
230    }
231
232    private String opsToString(List<UpdateOp> updateOps) {
233        StringBuilder sb = new StringBuilder();
234        for (UpdateOp op : updateOps) {
235            sb.append("\n").append(op.toString());
236        }
237        return sb.append("\n").toString();
238    }
239
240    public void orderedRandom(int... ops) {
241        for (int op : ops) {
242            randOp(op);
243        }
244    }
245
246    void randOp(int cmd) {
247        switch (cmd) {
248            case REMOVE:
249                if (updatedItemCount > 1) {
250                    int s = nextInt(random, updatedItemCount - 1);
251                    int len = Math.max(1, nextInt(random, updatedItemCount - s));
252                    rm(s, len);
253                }
254                break;
255            case ADD:
256                int s = updatedItemCount == 0 ? 0 : nextInt(random, updatedItemCount);
257                add(s, nextInt(random, 50));
258                break;
259            case MOVE:
260                if (updatedItemCount >= 2) {
261                    int from = nextInt(random, updatedItemCount);
262                    int to;
263                    do {
264                        to = nextInt(random, updatedItemCount);
265                    } while (to == from);
266                    mv(from, to);
267                }
268                break;
269            case UPDATE:
270                if (updatedItemCount > 1) {
271                    s = nextInt(random, updatedItemCount - 1);
272                    int len = Math.max(1, nextInt(random, updatedItemCount - s));
273                    up(s, len);
274                }
275                break;
276        }
277    }
278
279    int nextInt(Random random, int n) {
280        if (n == 0) {
281            return 0;
282        }
283        return random.nextInt(n);
284    }
285
286    UpdateOp rm(int start, int count) {
287        updatedItemCount -= count;
288        return record(new UpdateOp(REMOVE, start, count, null));
289    }
290
291    UpdateOp mv(int from, int to) {
292        return record(new UpdateOp(MOVE, from, to, null));
293    }
294
295    UpdateOp add(int start, int count) {
296        updatedItemCount += count;
297        return record(new UpdateOp(ADD, start, count, null));
298    }
299
300    UpdateOp up(int start, int count) {
301        return record(new UpdateOp(UPDATE, start, count, null));
302    }
303
304    UpdateOp record(UpdateOp op) {
305        mUpdateOps.add(op);
306        return op;
307    }
308
309    void process() {
310        List<Item> items = new ArrayList<Item>(itemCount);
311        for (int i = 0; i < itemCount; i++) {
312            items.add(Item.create());
313        }
314        List<Item> clones = new ArrayList<Item>(itemCount);
315        for (int i = 0; i < itemCount; i++) {
316            clones.add(Item.clone(items.get(i)));
317        }
318        List<UpdateOp> rewritten = rewriteOps(mUpdateOps);
319
320        assertAllMovesAtTheEnd(rewritten);
321
322        apply(items, mUpdateOps);
323        List<Item> originalAdded = mAddedItems;
324        List<Item> originalRemoved = mRemovedItems;
325        if (originalAdded.size() > 0) {
326            Item.idCounter = originalAdded.get(0).id;
327        }
328        mAddedItems = new ArrayList<Item>();
329        mRemovedItems = new ArrayList<Item>();
330        apply(clones, rewritten);
331
332        // now check equality
333        assertListsIdentical(items, clones);
334        assertHasTheSameItems(originalAdded, mAddedItems);
335        assertHasTheSameItems(originalRemoved, mRemovedItems);
336
337        assertRecycledOpsAreNotReused(items);
338        assertRecycledOpsAreNotReused(clones);
339    }
340
341    private void assertRecycledOpsAreNotReused(List<Item> items) {
342        for (Item item : items) {
343            assertFalse(mRecycledOps.contains(item));
344        }
345    }
346
347    private void assertAllMovesAtTheEnd(List<UpdateOp> ops) {
348        boolean foundMove = false;
349        for (UpdateOp op : ops) {
350            if (op.cmd == MOVE) {
351                foundMove = true;
352            } else {
353                assertFalse(foundMove);
354            }
355        }
356    }
357
358    private void assertHasTheSameItems(List<Item> items,
359            List<Item> clones) {
360        String log = "has the same items\n" + toString(items) + "--\n" + toString(clones);
361        assertEquals(log, items.size(), clones.size());
362        for (Item item : items) {
363            for (Item clone : clones) {
364                if (item.id == clone.id && item.version == clone.version) {
365                    clones.remove(clone);
366                    break;
367                }
368            }
369        }
370        assertEquals(log, 0, clones.size());
371    }
372
373    private void assertListsIdentical(List<Item> items, List<Item> clones) {
374        String log = "is identical\n" + toString(items) + "--\n" + toString(clones);
375        assertEquals(items.size(), clones.size());
376        for (int i = 0; i < items.size(); i++) {
377            Item.assertIdentical(log, items.get(i), clones.get(i));
378        }
379    }
380
381    private void apply(List<Item> items, List<UpdateOp> updateOps) {
382        for (UpdateOp op : updateOps) {
383            switch (op.cmd) {
384                case UpdateOp.ADD:
385                    for (int i = 0; i < op.itemCount; i++) {
386                        final Item newItem = Item.create();
387                        mAddedItems.add(newItem);
388                        items.add(op.positionStart + i, newItem);
389                    }
390                    break;
391                case UpdateOp.REMOVE:
392                    for (int i = 0; i < op.itemCount; i++) {
393                        mRemovedItems.add(items.remove(op.positionStart));
394                    }
395                    break;
396                case UpdateOp.MOVE:
397                    items.add(op.itemCount, items.remove(op.positionStart));
398                    break;
399                case UpdateOp.UPDATE:
400                    for (int i = 0; i < op.itemCount; i++) {
401                        final int index = op.positionStart + i;
402                        items.get(index).version = items.get(index).version + 1;
403                    }
404                    break;
405            }
406        }
407    }
408
409    private List<UpdateOp> rewriteOps(List<UpdateOp> updateOps) {
410        List<UpdateOp> copy = new ArrayList<UpdateOp>();
411        for (UpdateOp op : updateOps) {
412            copy.add(new UpdateOp(op.cmd, op.positionStart, op.itemCount, null));
413        }
414        mOpReorderer.reorderOps(copy);
415        return copy;
416    }
417
418    @Test
419    public void testSwapMoveRemove_1() {
420        mv(10, 15);
421        rm(2, 3);
422        swapMoveRemove(mUpdateOps, 0);
423        assertEquals(2, mUpdateOps.size());
424        assertEquals(mv(7, 12), mUpdateOps.get(1));
425        assertEquals(rm(2, 3), mUpdateOps.get(0));
426    }
427
428    @Test
429    public void testSwapMoveRemove_2() {
430        mv(3, 8);
431        rm(4, 2);
432        swapMoveRemove(mUpdateOps, 0);
433        assertEquals(2, mUpdateOps.size());
434        assertEquals(rm(5, 2), mUpdateOps.get(0));
435        assertEquals(mv(3, 6), mUpdateOps.get(1));
436    }
437
438    @Test
439    public void testSwapMoveRemove_3() {
440        mv(3, 8);
441        rm(3, 2);
442        swapMoveRemove(mUpdateOps, 0);
443        assertEquals(2, mUpdateOps.size());
444        assertEquals(rm(4, 2), mUpdateOps.get(0));
445        assertEquals(mv(3, 6), mUpdateOps.get(1));
446    }
447
448    @Test
449    public void testSwapMoveRemove_4() {
450        mv(3, 8);
451        rm(2, 3);
452        swapMoveRemove(mUpdateOps, 0);
453        assertEquals(3, mUpdateOps.size());
454        assertEquals(rm(4, 2), mUpdateOps.get(0));
455        assertEquals(rm(2, 1), mUpdateOps.get(1));
456        assertEquals(mv(2, 5), mUpdateOps.get(2));
457    }
458
459    @Test
460    public void testSwapMoveRemove_5() {
461        mv(3, 0);
462        rm(2, 3);
463        swapMoveRemove(mUpdateOps, 0);
464        assertEquals(3, mUpdateOps.size());
465        assertEquals(rm(4, 1), mUpdateOps.get(0));
466        assertEquals(rm(1, 2), mUpdateOps.get(1));
467        assertEquals(mv(1, 0), mUpdateOps.get(2));
468    }
469
470    @Test
471    public void testSwapMoveRemove_6() {
472        mv(3, 10);
473        rm(2, 3);
474        swapMoveRemove(mUpdateOps, 0);
475        assertEquals(3, mUpdateOps.size());
476        assertEquals(rm(4, 2), mUpdateOps.get(0));
477        assertEquals(rm(2, 1), mUpdateOps.get(1));
478    }
479
480    @Test
481    public void testSwapMoveRemove_7() {
482        mv(3, 2);
483        rm(6, 2);
484        swapMoveRemove(mUpdateOps, 0);
485        assertEquals(2, mUpdateOps.size());
486        assertEquals(rm(6, 2), mUpdateOps.get(0));
487        assertEquals(mv(3, 2), mUpdateOps.get(1));
488    }
489
490    @Test
491    public void testSwapMoveRemove_8() {
492        mv(3, 4);
493        rm(3, 1);
494        swapMoveRemove(mUpdateOps, 0);
495        assertEquals(1, mUpdateOps.size());
496        assertEquals(rm(4, 1), mUpdateOps.get(0));
497    }
498
499    @Test
500    public void testSwapMoveRemove_9() {
501        mv(3, 4);
502        rm(4, 1);
503        swapMoveRemove(mUpdateOps, 0);
504        assertEquals(1, mUpdateOps.size());
505        assertEquals(rm(3, 1), mUpdateOps.get(0));
506    }
507
508    @Test
509    public void testSwapMoveRemove_10() {
510        mv(1, 3);
511        rm(0, 3);
512        swapMoveRemove(mUpdateOps, 0);
513        assertEquals(2, mUpdateOps.size());
514        assertEquals(rm(2, 2), mUpdateOps.get(0));
515        assertEquals(rm(0, 1), mUpdateOps.get(1));
516    }
517
518    @Test
519    public void testSwapMoveRemove_11() {
520        mv(3, 8);
521        rm(7, 3);
522        swapMoveRemove(mUpdateOps, 0);
523        assertEquals(2, mUpdateOps.size());
524        assertEquals(rm(3, 1), mUpdateOps.get(0));
525        assertEquals(rm(7, 2), mUpdateOps.get(1));
526    }
527
528    @Test
529    public void testSwapMoveRemove_12() {
530        mv(1, 3);
531        rm(2, 1);
532        swapMoveRemove(mUpdateOps, 0);
533        assertEquals(2, mUpdateOps.size());
534        assertEquals(rm(3, 1), mUpdateOps.get(0));
535        assertEquals(mv(1, 2), mUpdateOps.get(1));
536    }
537
538    @Test
539    public void testSwapMoveRemove_13() {
540        mv(1, 3);
541        rm(1, 2);
542        swapMoveRemove(mUpdateOps, 0);
543        assertEquals(1, mUpdateOps.size());
544        assertEquals(rm(2, 2), mUpdateOps.get(1));
545    }
546
547    @Test
548    public void testSwapMoveRemove_14() {
549        mv(4, 2);
550        rm(3, 1);
551        swapMoveRemove(mUpdateOps, 0);
552        assertEquals(2, mUpdateOps.size());
553        assertEquals(rm(2, 1), mUpdateOps.get(0));
554        assertEquals(mv(2, 3), mUpdateOps.get(1));
555    }
556
557    @Test
558    public void testSwapMoveRemove_15() {
559        mv(4, 2);
560        rm(3, 2);
561        swapMoveRemove(mUpdateOps, 0);
562        assertEquals(1, mUpdateOps.size());
563        assertEquals(rm(2, 2), mUpdateOps.get(0));
564    }
565
566    @Test
567    public void testSwapMoveRemove_16() {
568        mv(2, 3);
569        rm(1, 2);
570        swapMoveRemove(mUpdateOps, 0);
571        assertEquals(2, mUpdateOps.size());
572        assertEquals(rm(3, 1), mUpdateOps.get(0));
573        assertEquals(rm(1, 1), mUpdateOps.get(1));
574    }
575
576    @Test
577    public void testSwapMoveUpdate_0() {
578        mv(1, 3);
579        up(1, 2);
580        swapMoveUpdate(mUpdateOps, 0);
581        assertEquals(2, mUpdateOps.size());
582        assertEquals(up(2, 2), mUpdateOps.get(0));
583        assertEquals(mv(1, 3), mUpdateOps.get(1));
584    }
585
586    @Test
587    public void testSwapMoveUpdate_1() {
588        mv(0, 2);
589        up(0, 4);
590        swapMoveUpdate(mUpdateOps, 0);
591        assertEquals(3, mUpdateOps.size());
592        assertEquals(up(0, 1), mUpdateOps.get(0));
593        assertEquals(up(1, 3), mUpdateOps.get(1));
594        assertEquals(mv(0, 2), mUpdateOps.get(2));
595    }
596
597    @Test
598    public void testSwapMoveUpdate_2() {
599        mv(2, 0);
600        up(1, 3);
601        swapMoveUpdate(mUpdateOps, 0);
602        assertEquals(3, mUpdateOps.size());
603        assertEquals(up(3, 1), mUpdateOps.get(0));
604        assertEquals(up(0, 2), mUpdateOps.get(1));
605        assertEquals(mv(2, 0), mUpdateOps.get(2));
606    }
607
608    private void swapMoveUpdate(List<UpdateOp> list, int move) {
609        mOpReorderer.swapMoveUpdate(list, move, list.get(move), move + 1, list.get(move + 1));
610    }
611
612    private void swapMoveRemove(List<UpdateOp> list, int move) {
613        mOpReorderer.swapMoveRemove(list, move, list.get(move), move + 1, list.get(move + 1));
614    }
615
616    private String toString(List<Item> items) {
617        StringBuilder sb = new StringBuilder();
618        for (Item item : items) {
619            sb.append(item.toString()).append("\n");
620        }
621        return sb.toString();
622    }
623
624    static class Item {
625
626        static int idCounter = 0;
627        int id;
628        int version;
629
630        Item(int id, int version) {
631            this.id = id;
632            this.version = version;
633        }
634
635        static Item create() {
636            return new Item(idCounter++, 1);
637        }
638
639        static Item clone(Item other) {
640            return new Item(other.id, other.version);
641        }
642
643        public static void assertIdentical(String logPrefix, Item item1, Item item2) {
644            assertEquals(logPrefix + "\n" + item1 + " vs " + item2, item1.id, item2.id);
645            assertEquals(logPrefix + "\n" + item1 + " vs " + item2, item1.version, item2.version);
646        }
647
648        @Override
649        public String toString() {
650            return "Item{" +
651                    "id=" + id +
652                    ", version=" + version +
653                    '}';
654        }
655    }
656}
657