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.util; 18 19import junit.framework.TestCase; 20 21import org.junit.Before; 22import org.junit.Test; 23import org.junit.runner.RunWith; 24import org.junit.runners.JUnit4; 25 26import android.test.suitebuilder.annotation.SmallTest; 27 28import java.util.ArrayList; 29import java.util.Collection; 30import java.util.Collections; 31import java.util.Comparator; 32import java.util.List; 33import java.util.Random; 34 35@RunWith(JUnit4.class) 36@SmallTest 37public class SortedListTest extends TestCase { 38 39 SortedList<Item> mList; 40 List<Pair> mAdditions = new ArrayList<Pair>(); 41 List<Pair> mRemovals = new ArrayList<Pair>(); 42 List<Pair> mMoves = new ArrayList<Pair>(); 43 List<Pair> mUpdates = new ArrayList<Pair>(); 44 private SortedList.Callback<Item> mCallback; 45 InsertedCallback<Item> mInsertedCallback; 46 ChangedCallback<Item> mChangedCallback; 47 48 private Comparator<? super Item> sItemComparator = new Comparator<Item>() { 49 @Override 50 public int compare(Item o1, Item o2) { 51 return mCallback.compare(o1, o2); 52 } 53 }; 54 55 private abstract class InsertedCallback<T> { 56 public abstract void onInserted(int position, int count); 57 } 58 59 private abstract class ChangedCallback<T> { 60 public abstract void onChanged(int position, int count); 61 } 62 63 @Override 64 @Before 65 public void setUp() throws Exception { 66 super.setUp(); 67 mCallback = new SortedList.Callback<Item>() { 68 @Override 69 public int compare(Item o1, Item o2) { 70 return o1.cmpField < o2.cmpField ? -1 : (o1.cmpField == o2.cmpField ? 0 : 1); 71 } 72 73 @Override 74 public void onInserted(int position, int count) { 75 mAdditions.add(new Pair(position, count)); 76 if (mInsertedCallback != null) { 77 mInsertedCallback.onInserted(position, count); 78 } 79 } 80 81 @Override 82 public void onRemoved(int position, int count) { 83 mRemovals.add(new Pair(position, count)); 84 } 85 86 @Override 87 public void onMoved(int fromPosition, int toPosition) { 88 mMoves.add(new Pair(fromPosition, toPosition)); 89 } 90 91 @Override 92 public void onChanged(int position, int count) { 93 mUpdates.add(new Pair(position, count)); 94 if (mChangedCallback != null) { 95 mChangedCallback.onChanged(position, count); 96 } 97 } 98 99 @Override 100 public boolean areContentsTheSame(Item oldItem, Item newItem) { 101 return oldItem.cmpField == newItem.cmpField && oldItem.data == newItem.data; 102 } 103 104 @Override 105 public boolean areItemsTheSame(Item item1, Item item2) { 106 return item1.id == item2.id; 107 } 108 }; 109 mInsertedCallback = null; 110 mChangedCallback = null; 111 mList = new SortedList<Item>(Item.class, mCallback); 112 } 113 114 @Test 115 public void testEmpty() { 116 assertEquals("empty", mList.size(), 0); 117 } 118 119 @Test 120 public void testAdd() { 121 Item item = new Item(); 122 assertEquals(insert(item), 0); 123 assertEquals(size(), 1); 124 assertTrue(mAdditions.contains(new Pair(0, 1))); 125 Item item2 = new Item(); 126 item2.cmpField = item.cmpField + 1; 127 assertEquals(insert(item2), 1); 128 assertEquals(size(), 2); 129 assertTrue(mAdditions.contains(new Pair(1, 1))); 130 Item item3 = new Item(); 131 item3.cmpField = item.cmpField - 1; 132 mAdditions.clear(); 133 assertEquals(insert(item3), 0); 134 assertEquals(size(), 3); 135 assertTrue(mAdditions.contains(new Pair(0, 1))); 136 } 137 138 @Test 139 public void testAddDuplicate() { 140 Item item = new Item(); 141 Item item2 = new Item(item.id, item.cmpField); 142 item2.data = item.data; 143 insert(item); 144 assertEquals(0, insert(item2)); 145 assertEquals(1, size()); 146 assertEquals(1, mAdditions.size()); 147 assertEquals(0, mUpdates.size()); 148 } 149 150 @Test 151 public void testRemove() { 152 Item item = new Item(); 153 assertFalse(remove(item)); 154 assertEquals(0, mRemovals.size()); 155 insert(item); 156 assertTrue(remove(item)); 157 assertEquals(1, mRemovals.size()); 158 assertTrue(mRemovals.contains(new Pair(0, 1))); 159 assertEquals(0, size()); 160 assertFalse(remove(item)); 161 assertEquals(1, mRemovals.size()); 162 } 163 164 @Test 165 public void testRemove2() { 166 Item item = new Item(); 167 Item item2 = new Item(item.cmpField); 168 insert(item); 169 assertFalse(remove(item2)); 170 assertEquals(0, mRemovals.size()); 171 } 172 173 @Test 174 public void clearTest() { 175 insert(new Item(1)); 176 insert(new Item(2)); 177 assertEquals(2, mList.size()); 178 mList.clear(); 179 assertEquals(0, mList.size()); 180 insert(new Item(3)); 181 assertEquals(1, mList.size()); 182 } 183 184 @Test 185 public void testBatch() { 186 mList.beginBatchedUpdates(); 187 for (int i = 0; i < 5; i++) { 188 mList.add(new Item(i)); 189 } 190 assertEquals(0, mAdditions.size()); 191 mList.endBatchedUpdates(); 192 assertTrue(mAdditions.contains(new Pair(0, 5))); 193 } 194 195 @Test 196 public void testRandom() throws Throwable { 197 Random random = new Random(System.nanoTime()); 198 List<Item> copy = new ArrayList<Item>(); 199 StringBuilder log = new StringBuilder(); 200 try { 201 for (int i = 0; i < 10000; i++) { 202 switch (random.nextInt(3)) { 203 case 0://ADD 204 Item item = new Item(); 205 copy.add(item); 206 insert(item); 207 log.append("add ").append(item).append("\n"); 208 break; 209 case 1://REMOVE 210 if (copy.size() > 0) { 211 int index = random.nextInt(mList.size()); 212 item = mList.get(index); 213 log.append("remove ").append(item).append("\n"); 214 assertTrue(copy.remove(item)); 215 assertTrue(mList.remove(item)); 216 } 217 break; 218 case 2://UPDATE 219 if (copy.size() > 0) { 220 int index = random.nextInt(mList.size()); 221 item = mList.get(index); 222 // TODO this cannot work 223 Item newItem = new Item(item.id, item.cmpField); 224 log.append("update ").append(item).append(" to ").append(newItem) 225 .append("\n"); 226 while (newItem.data == item.data) { 227 newItem.data = random.nextInt(1000); 228 } 229 int itemIndex = mList.add(newItem); 230 copy.remove(item); 231 copy.add(newItem); 232 assertSame(mList.get(itemIndex), newItem); 233 assertNotSame(mList.get(index), item); 234 } 235 break; 236 case 3:// UPDATE AT 237 if (copy.size() > 0) { 238 int index = random.nextInt(mList.size()); 239 item = mList.get(index); 240 Item newItem = new Item(item.id, random.nextInt()); 241 mList.updateItemAt(index, newItem); 242 copy.remove(item); 243 copy.add(newItem); 244 } 245 } 246 int lastCmp = Integer.MIN_VALUE; 247 for (int index = 0; index < copy.size(); index++) { 248 assertFalse(mList.indexOf(copy.get(index)) == SortedList.INVALID_POSITION); 249 assertTrue(mList.get(index).cmpField >= lastCmp); 250 lastCmp = mList.get(index).cmpField; 251 assertTrue(copy.contains(mList.get(index))); 252 } 253 254 for (int index = 0; index < mList.size(); index++) { 255 assertNotNull(mList.mData[index]); 256 } 257 for (int index = mList.size(); index < mList.mData.length; index++) { 258 assertNull(mList.mData[index]); 259 } 260 261 } 262 } catch (Throwable t) { 263 Collections.sort(copy, sItemComparator); 264 log.append("Items:\n"); 265 for (Item item : copy) { 266 log.append(item).append("\n"); 267 } 268 log.append("SortedList:\n"); 269 for (int i = 0; i < mList.size(); i++) { 270 log.append(mList.get(i)).append("\n"); 271 } 272 273 throw new Throwable(" \nlog:\n" + log.toString(), t); 274 } 275 } 276 277 private static Item[] createItems(int idFrom, int idTo, int idStep) { 278 final int count = (idTo - idFrom) / idStep + 1; 279 Item[] items = new Item[count]; 280 int id = idFrom; 281 for (int i = 0; i < count; i++) { 282 Item item = new Item(id, id); 283 item.data = id; 284 items[i] = item; 285 id += idStep; 286 } 287 return items; 288 } 289 290 private static Item[] shuffle(Item[] items) { 291 Random random = new Random(System.nanoTime()); 292 final int count = items.length; 293 for (int i = 0; i < count; i++) { 294 int pos1 = random.nextInt(count); 295 int pos2 = random.nextInt(count); 296 if (pos1 != pos2) { 297 Item temp = items[pos1]; 298 items[pos1] = items[pos2]; 299 items[pos2] = temp; 300 } 301 } 302 return items; 303 } 304 305 private void assertIntegrity(int size, String context) { 306 assertEquals(context + ": incorrect size", size, size()); 307 int rangeStart = 0; 308 for (int i = 0; i < size(); i++) { 309 Item item = mList.get(i); 310 assertNotNull(context + ": get returned null @" + i, item); 311 assertEquals(context + ": incorrect indexOf result @" + i, i, mList.indexOf(item)); 312 if (i == 0) { 313 continue; 314 } 315 316 final int compare = mCallback.compare(mList.get(i - 1), item); 317 assertTrue(context + ": incorrect sorting order @" + i, compare <= 0); 318 319 if (compare == 0) { 320 for (int j = rangeStart; j < i; j++) { 321 assertFalse(context + ": duplicates found @" + j + " and " + i, 322 mCallback.areItemsTheSame(mList.get(j), item)); 323 } 324 } else { 325 rangeStart = i; 326 } 327 } 328 } 329 330 private void assertSequentialOrder() { 331 for (int i = 0; i < size(); i++) { 332 assertEquals(i, mList.get(i).cmpField); 333 } 334 } 335 336 @Test 337 public void testAddAllMerge() throws Throwable { 338 mList.addAll(new Item[0]); 339 assertIntegrity(0, "addAll, empty list, empty input"); 340 assertEquals(0, mAdditions.size()); 341 342 // Add first 5 even numbers. Test adding to an empty list. 343 mList.addAll(createItems(0, 8, 2)); 344 assertIntegrity(5, "addAll, empty list, non-empty input"); 345 assertEquals(1, mAdditions.size()); 346 assertTrue(mAdditions.contains(new Pair(0, 5))); 347 348 mList.addAll(new Item[0]); 349 assertIntegrity(5, "addAll, non-empty list, empty input"); 350 assertEquals(1, mAdditions.size()); 351 352 // Add 5 more even numbers, shuffled (test pre-sorting). 353 mList.addAll(shuffle(createItems(10, 18, 2))); 354 assertIntegrity(10, "addAll, shuffled input"); 355 assertEquals(2, mAdditions.size()); 356 assertTrue(mAdditions.contains(new Pair(5, 5))); 357 358 // Add 5 more even numbers, reversed (test pre-sorting). 359 mList.addAll(shuffle(createItems(28, 20, -2))); 360 assertIntegrity(15, "addAll, reversed input"); 361 assertEquals(3, mAdditions.size()); 362 assertTrue(mAdditions.contains(new Pair(10, 5))); 363 364 // Add first 10 odd numbers. 365 // Test the merge when the new items run out first. 366 mList.addAll(createItems(1, 19, 2)); 367 assertIntegrity(25, "addAll, merging in the middle"); 368 assertEquals(13, mAdditions.size()); 369 for (int i = 1; i <= 19; i += 2) { 370 assertTrue(mAdditions.contains(new Pair(i, 1))); 371 } 372 373 // Add 10 more odd numbers. 374 // Test the merge when the old items run out first. 375 mList.addAll(createItems(21, 39, 2)); 376 assertIntegrity(35, "addAll, merging at the end"); 377 assertEquals(18, mAdditions.size()); 378 for (int i = 21; i <= 27; i += 2) { 379 assertTrue(mAdditions.contains(new Pair(i, 1))); 380 } 381 assertTrue(mAdditions.contains(new Pair(29, 6))); 382 383 // Add 5 more even numbers. 384 mList.addAll(createItems(30, 38, 2)); 385 assertIntegrity(40, "addAll, merging more"); 386 assertEquals(23, mAdditions.size()); 387 for (int i = 30; i <= 38; i += 2) { 388 assertTrue(mAdditions.contains(new Pair(i, 1))); 389 } 390 391 assertEquals(0, mMoves.size()); 392 assertEquals(0, mUpdates.size()); 393 assertEquals(0, mRemovals.size()); 394 395 assertSequentialOrder(); 396 } 397 398 @Test 399 public void testAddAllUpdates() throws Throwable { 400 // Add first 5 even numbers. 401 Item[] evenItems = createItems(0, 8, 2); 402 for (Item item : evenItems) { 403 item.data = 1; 404 } 405 mList.addAll(evenItems); 406 assertEquals(5, size()); 407 assertEquals(1, mAdditions.size()); 408 assertTrue(mAdditions.contains(new Pair(0, 5))); 409 assertEquals(0, mUpdates.size()); 410 411 Item[] sameEvenItems = createItems(0, 8, 2); 412 for (Item item : sameEvenItems) { 413 item.data = 1; 414 } 415 mList.addAll(sameEvenItems); 416 assertEquals(1, mAdditions.size()); 417 assertEquals(0, mUpdates.size()); 418 419 Item[] newEvenItems = createItems(0, 8, 2); 420 for (Item item : newEvenItems) { 421 item.data = 2; 422 } 423 mList.addAll(newEvenItems); 424 assertEquals(5, size()); 425 assertEquals(1, mAdditions.size()); 426 assertEquals(1, mUpdates.size()); 427 assertTrue(mUpdates.contains(new Pair(0, 5))); 428 for (int i = 0; i < 5; i++) { 429 assertEquals(2, mList.get(i).data); 430 } 431 432 // Add all numbers from 0 to 9 433 Item[] sequentialItems = createItems(0, 9, 1); 434 for (Item item : sequentialItems) { 435 item.data = 3; 436 } 437 mList.addAll(sequentialItems); 438 439 // Odd numbers should have been added. 440 assertEquals(6, mAdditions.size()); 441 for (int i = 0; i < 5; i++) { 442 assertTrue(mAdditions.contains(new Pair(i * 2 + 1, 1))); 443 } 444 445 // All even items should have been updated. 446 assertEquals(6, mUpdates.size()); 447 for (int i = 0; i < 5; i++) { 448 assertTrue(mUpdates.contains(new Pair(i * 2, 1))); 449 } 450 451 assertEquals(10, size()); 452 453 // All items should have the latest data value. 454 for (int i = 0; i < 10; i++) { 455 assertEquals(3, mList.get(i).data); 456 } 457 assertEquals(0, mMoves.size()); 458 assertEquals(0, mRemovals.size()); 459 assertSequentialOrder(); 460 } 461 462 @Test 463 public void testAddAllWithDuplicates() throws Throwable { 464 final int maxCmpField = 5; 465 final int idsPerCmpField = 10; 466 final int maxUniqueId = maxCmpField * idsPerCmpField; 467 final int maxGeneration = 5; 468 469 Item[] items = new Item[maxUniqueId * maxGeneration]; 470 471 int index = 0; 472 for (int generation = 0; generation < maxGeneration; generation++) { 473 int uniqueId = 0; 474 for (int cmpField = 0; cmpField < maxCmpField; cmpField++) { 475 for (int id = 0; id < idsPerCmpField; id++) { 476 Item item = new Item(uniqueId++, cmpField); 477 item.data = generation; 478 items[index++] = item; 479 } 480 } 481 } 482 483 mList.addAll(items); 484 485 assertIntegrity(maxUniqueId, "addAll with duplicates"); 486 487 // Check that the most recent items have made it to the list. 488 for (int i = 0; i != size(); i++) { 489 Item item = mList.get(i); 490 assertEquals(maxGeneration - 1, item.data); 491 } 492 } 493 494 @Test 495 public void testAddAllFast() throws Throwable { 496 mList.addAll(new Item[0], true); 497 assertIntegrity(0, "addAll(T[],boolean), empty list, with empty input"); 498 assertEquals(0, mAdditions.size()); 499 500 mList.addAll(createItems(0, 9, 1), true); 501 assertIntegrity(10, "addAll(T[],boolean), empty list, non-empty input"); 502 assertEquals(1, mAdditions.size()); 503 assertTrue(mAdditions.contains(new Pair(0, 10))); 504 505 mList.addAll(new Item[0], true); 506 assertEquals(1, mAdditions.size()); 507 assertIntegrity(10, "addAll(T[],boolean), non-empty list, empty input"); 508 509 mList.addAll(createItems(10, 19, 1), true); 510 assertEquals(2, mAdditions.size()); 511 assertTrue(mAdditions.contains(new Pair(10, 10))); 512 assertIntegrity(20, "addAll(T[],boolean), non-empty list, non-empty input"); 513 } 514 515 @Test 516 public void testAddAllCollection() throws Throwable { 517 Collection<Item> itemList = new ArrayList<Item>(); 518 for (int i = 0; i < 5; i++) { 519 itemList.add(new Item(i)); 520 } 521 mList.addAll(itemList); 522 523 assertEquals(1, mAdditions.size()); 524 assertTrue(mAdditions.contains(new Pair(0, itemList.size()))); 525 assertIntegrity(itemList.size(), "addAll on collection"); 526 } 527 528 @Test 529 public void testAddAllStableSort() { 530 int id = 0; 531 Item item = new Item(id++, 0); 532 mList.add(item); 533 534 // Create a few items with the same sort order. 535 Item[] items = new Item[3]; 536 for (int i = 0; i < 3; i++) { 537 items[i] = new Item(id++, item.cmpField); 538 assertEquals(0, mCallback.compare(item, items[i])); 539 } 540 541 mList.addAll(items); 542 assertEquals(1 + items.length, size()); 543 544 // Check that the order has been preserved. 545 for (int i = 0; i < size(); i++) { 546 assertEquals(i, mList.get(i).id); 547 } 548 } 549 550 551 @Test 552 public void testAddAllAccessFromCallbacks() { 553 // Add first 5 even numbers. 554 Item[] evenItems = createItems(0, 8, 2); 555 for (Item item : evenItems) { 556 item.data = 1; 557 } 558 559 mInsertedCallback = new InsertedCallback<Item>() { 560 @Override 561 public void onInserted(int position, int count) { 562 assertEquals(0, position); 563 assertEquals(5, count); 564 for (int i = 0; i < count; i++) { 565 assertEquals(i * 2, mList.get(i).id); 566 } 567 assertIntegrity(5, "onInserted(" + position + ", " + count + ")"); 568 } 569 }; 570 571 mList.addAll(evenItems); 572 assertEquals(1, mAdditions.size()); 573 assertEquals(0, mUpdates.size()); 574 575 // Add all numbers from 0 to 9. This should trigger 5 change and 5 insert notifications. 576 Item[] sequentialItems = createItems(0, 9, 1); 577 for (Item item : sequentialItems) { 578 item.data = 2; 579 } 580 581 mChangedCallback = new ChangedCallback<Item>() { 582 int expectedSize = 5; 583 584 @Override 585 public void onChanged(int position, int count) { 586 assertEquals(1, count); 587 assertEquals(position, mList.get(position).id); 588 assertIntegrity(++expectedSize, "onChanged(" + position + ")"); 589 } 590 }; 591 592 mInsertedCallback = new InsertedCallback<Item>() { 593 int expectedSize = 5; 594 595 @Override 596 public void onInserted(int position, int count) { 597 assertEquals(1, count); 598 assertEquals(position, mList.get(position).id); 599 assertIntegrity(++expectedSize, "onInserted(" + position + ")"); 600 } 601 }; 602 603 mList.addAll(sequentialItems); 604 assertEquals(6, mAdditions.size()); 605 assertEquals(5, mUpdates.size()); 606 } 607 608 @Test 609 public void testModificationFromCallbackThrows() { 610 final Item extraItem = new Item(0); 611 612 Item[] items = createItems(1, 5, 2); 613 for (Item item : items) { 614 item.data = 1; 615 } 616 mList.addAll(items); 617 618 mInsertedCallback = new InsertedCallback<Item>() { 619 @Override 620 public void onInserted(int position, int count) { 621 try { 622 mList.add(new Item()); 623 fail("add must throw from within a callback"); 624 } catch (IllegalStateException e) { 625 } 626 try { 627 mList.addAll(createItems(0, 0, 1)); 628 fail("addAll must throw from within a callback"); 629 } catch (IllegalStateException e) { 630 } 631 try { 632 mList.addAll(createItems(0, 0, 1), true); 633 fail("addAll(T[],boolean) must throw from within a callback"); 634 } catch (IllegalStateException e) { 635 } 636 try { 637 mList.remove(extraItem); 638 fail("remove must throw from within a callback"); 639 } catch (IllegalStateException e) { 640 } 641 try { 642 mList.removeItemAt(0); 643 fail("removeItemAt must throw from within a callback"); 644 } catch (IllegalStateException e) { 645 } 646 try { 647 mList.updateItemAt(0, extraItem); 648 fail("updateItemAt must throw from within a callback"); 649 } catch (IllegalStateException e) { 650 } 651 try { 652 mList.recalculatePositionOfItemAt(0); 653 fail("recalculatePositionOfItemAt must throw from within a callback"); 654 } catch (IllegalStateException e) { 655 } 656 try { 657 mList.clear(); 658 fail("recalculatePositionOfItemAt must throw from within a callback"); 659 } catch (IllegalStateException e) { 660 } 661 } 662 }; 663 664 // Make sure that the last one notification is change, so that the above callback is 665 // not called from endBatchUpdates when the nested alls are actually OK. 666 items = createItems(1, 5, 1); 667 for (Item item : items) { 668 item.data = 2; 669 } 670 mList.addAll(items); 671 assertIntegrity(5, "Modification from callback"); 672 } 673 674 @Test 675 public void testAddAllOutsideBatchedUpdates() { 676 mList.add(new Item(1)); 677 assertEquals(1, mAdditions.size()); 678 mList.add(new Item(2)); 679 assertEquals(2, mAdditions.size()); 680 mList.addAll(new Item(3), new Item(4)); 681 assertEquals(3, mAdditions.size()); 682 mList.add(new Item(5)); 683 assertEquals(4, mAdditions.size()); 684 mList.add(new Item(6)); 685 assertEquals(5, mAdditions.size()); 686 } 687 688 @Test 689 public void testAddAllInsideBatchedUpdates() { 690 mList.beginBatchedUpdates(); 691 692 mList.add(new Item(1)); 693 assertEquals(0, mAdditions.size()); 694 mList.add(new Item(2)); 695 assertEquals(0, mAdditions.size()); 696 mList.addAll(new Item(3), new Item(4)); 697 assertEquals(0, mAdditions.size()); 698 mList.add(new Item(5)); 699 assertEquals(0, mAdditions.size()); 700 mList.add(new Item(6)); 701 assertEquals(0, mAdditions.size()); 702 703 mList.endBatchedUpdates(); 704 705 assertEquals(1, mAdditions.size()); 706 assertTrue(mAdditions.contains(new Pair(0, 6))); 707 } 708 709 private int size() { 710 return mList.size(); 711 } 712 713 private int insert(Item item) { 714 return mList.add(item); 715 } 716 717 private boolean remove(Item item) { 718 return mList.remove(item); 719 } 720 721 static class Item { 722 723 static int idCounter = 0; 724 final int id; 725 726 int cmpField; 727 728 int data = (int) (Math.random() * 1000);//used for comparison 729 730 public Item() { 731 id = idCounter++; 732 cmpField = (int) (Math.random() * 1000); 733 } 734 735 public Item(int cmpField) { 736 id = idCounter++; 737 this.cmpField = cmpField; 738 } 739 740 public Item(int id, int cmpField) { 741 this.id = id; 742 this.cmpField = cmpField; 743 } 744 745 @Override 746 public boolean equals(Object o) { 747 if (this == o) { 748 return true; 749 } 750 if (o == null || getClass() != o.getClass()) { 751 return false; 752 } 753 754 Item item = (Item) o; 755 756 if (cmpField != item.cmpField) { 757 return false; 758 } 759 if (id != item.id) { 760 return false; 761 } 762 763 return true; 764 } 765 766 @Override 767 public int hashCode() { 768 int result = id; 769 result = 31 * result + cmpField; 770 return result; 771 } 772 773 @Override 774 public String toString() { 775 return "Item{" + 776 "id=" + id + 777 ", cmpField=" + cmpField + 778 ", data=" + data + 779 '}'; 780 } 781 } 782 783 private static final class Pair { 784 785 final int first, second; 786 787 public Pair(int first) { 788 this.first = first; 789 this.second = Integer.MIN_VALUE; 790 } 791 792 public Pair(int first, int second) { 793 this.first = first; 794 this.second = second; 795 } 796 797 @Override 798 public boolean equals(Object o) { 799 if (this == o) { 800 return true; 801 } 802 if (o == null || getClass() != o.getClass()) { 803 return false; 804 } 805 806 Pair pair = (Pair) o; 807 808 if (first != pair.first) { 809 return false; 810 } 811 if (second != pair.second) { 812 return false; 813 } 814 815 return true; 816 } 817 818 @Override 819 public int hashCode() { 820 int result = first; 821 result = 31 * result + second; 822 return result; 823 } 824 } 825}