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