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