content: /*
   * Licensed to the Apache Software Foundation (ASF) under one or more
   * contributor license agreements. See the NOTICE file distributed with
   * this work for additional information regarding copyright ownership.
   * The ASF licenses this file to You under the Apache License, Version 2.0
   * (the "License"); you may not use this file except in compliance with
   * the License. You may obtain a copy of the License at
   *
   *    http://www.apache.org/licenses/LICENSE-2.0
   *
   * Unless required by applicable law or agreed to in writing, software
   * distributed under the License is distributed on an "AS IS" BASIS,
   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   * See the License for the specific language governing permissions and
   * limitations under the License.
   */
  package org.apache.kafka.common.utils;
  
  import org.junit.jupiter.api.Test;
  import org.junit.jupiter.api.Timeout;
  
  import java.util.ArrayList;
  import java.util.Collection;
  import java.util.Comparator;
  import java.util.Iterator;
  import java.util.LinkedHashSet;
  import java.util.List;
  import java.util.ListIterator;
  import java.util.Random;
  import java.util.Set;
  
  import static org.junit.jupiter.api.Assertions.assertEquals;
  import static org.junit.jupiter.api.Assertions.assertFalse;
  import static org.junit.jupiter.api.Assertions.assertNotEquals;
  import static org.junit.jupiter.api.Assertions.assertNull;
  import static org.junit.jupiter.api.Assertions.assertSame;
  import static org.junit.jupiter.api.Assertions.assertThrows;
  import static org.junit.jupiter.api.Assertions.assertTrue;
  import static org.junit.jupiter.api.Assertions.fail;
  
  /**
   * A unit test for ImplicitLinkedHashCollection.
   */
  @Timeout(120)
  public class ImplicitLinkedHashCollectionTest {
  
      static final class TestElement implements ImplicitLinkedHashCollection.Element {
          private int prev = ImplicitLinkedHashCollection.INVALID_INDEX;
          private int next = ImplicitLinkedHashCollection.INVALID_INDEX;
          private final int key;
          private final int val;
  
          TestElement(int key) {
              this.key = key;
              this.val = 0;
          }
  
          TestElement(int key, int val) {
              this.key = key;
              this.val = val;
          }
  
          @Override
          public int prev() {
              return prev;
          }
  
          @Override
          public void setPrev(int prev) {
              this.prev = prev;
          }
  
          @Override
          public int next() {
              return next;
          }
  
          @Override
          public void setNext(int next) {
              this.next = next;
          }
  
          @Override
          public boolean elementKeysAreEqual(Object o) {
              if (this == o) return true;
              if ((o == null) || (o.getClass() != TestElement.class)) return false;
              TestElement that = (TestElement) o;
              return key == that.key;
          }
  
          @Override
          public boolean equals(Object o) {
              if (this == o) return true;
              if ((o == null) || (o.getClass() != TestElement.class)) return false;
              TestElement that = (TestElement) o;
              return key == that.key && val == that.val;
          }
  
          @Override
          public String toString() {
              return "TestElement(key=" + key + ", val=" + val + ")";
          }
  
          @Override
          public int hashCode() {
              long hashCode = 2654435761L * key;
              return (int) (hashCode >> 32);
          }
      }
  
      @Test
      public void testNullForbidden() {
          ImplicitLinkedHashMultiCollection<TestElement> multiColl = new ImplicitLinkedHashMultiCollection<>();
          assertFalse(multiColl.add(null));
      }
  
      @Test
      public void testInsertDelete() {
          ImplicitLinkedHashCollection<TestElement> coll = new ImplicitLinkedHashCollection<>(100);
          assertTrue(coll.add(new TestElement(1)));
          TestElement second = new TestElement(2);
          assertTrue(coll.add(second));
          assertTrue(coll.add(new TestElement(3)));
          assertFalse(coll.add(new TestElement(3)));
          assertEquals(3, coll.size());
          assertTrue(coll.contains(new TestElement(1)));
          assertFalse(coll.contains(new TestElement(4)));
          TestElement secondAgain = coll.find(new TestElement(2));
          assertSame(second, secondAgain);
          assertTrue(coll.remove(new TestElement(1)));
          assertFalse(coll.remove(new TestElement(1)));
          assertEquals(2, coll.size());
          coll.clear();
          assertEquals(0, coll.size());
      }
  
      static void expectTraversal(Iterator<TestElement> iterator, Integer... sequence) {
          int i = 0;
          while (iterator.hasNext()) {
              TestElement element = iterator.next();
              assertTrue(i < sequence.length, "Iterator yieled " + (i + 1) + " elements, but only " +
                  sequence.length + " were expected.");
              assertEquals(sequence[i].intValue(), element.key, "Iterator value number " + (i + 1) + " was incorrect.");
              i = i + 1;
          }
          assertEquals(sequence.length, i, "Iterator yieled " + (i + 1) + " elements, but " +
                  sequence.length + " were expected.");
      }
  
      static void expectTraversal(Iterator<TestElement> iter, Iterator<Integer> expectedIter) {
          int i = 0;
          while (iter.hasNext()) {
              TestElement element = iter.next();
              assertTrue(expectedIter.hasNext(), "Iterator yieled " + (i + 1) + " elements, but only " + i +
                  " were expected.");
              Integer expected = expectedIter.next();
              assertEquals(expected.intValue(), element.key, "Iterator value number " + (i + 1) + " was incorrect.");
              i = i + 1;
          }
          assertFalse(expectedIter.hasNext(), "Iterator yieled " + i + " elements, but at least " + (i + 1) +
              " were expected.");
      }
  
      @Test
      public void testTraversal() {
          ImplicitLinkedHashCollection<TestElement> coll = new ImplicitLinkedHashCollection<>();
          expectTraversal(coll.iterator());
          assertTrue(coll.add(new TestElement(2)));
          expectTraversal(coll.iterator(), 2);
          assertTrue(coll.add(new TestElement(1)));
          expectTraversal(coll.iterator(), 2, 1);
          assertTrue(coll.add(new TestElement(100)));
          expectTraversal(coll.iterator(), 2, 1, 100);
          assertTrue(coll.remove(new TestElement(1)));
          expectTraversal(coll.iterator(), 2, 100);
          assertTrue(coll.add(new TestElement(1)));
          expectTraversal(coll.iterator(), 2, 100, 1);
          Iterator<TestElement> iter = coll.iterator();
          iter.next();
          iter.next();
          iter.remove();
          iter.next();
          assertFalse(iter.hasNext());
          expectTraversal(coll.iterator(), 2, 1);
          List<TestElement> list = new ArrayList<>();
          list.add(new TestElement(1));
          list.add(new TestElement(2));
          assertTrue(coll.removeAll(list));
          assertFalse(coll.removeAll(list));
          expectTraversal(coll.iterator());
          assertEquals(0, coll.size());
          assertTrue(coll.isEmpty());
      }
  
      @Test
      public void testSetViewGet() {
          ImplicitLinkedHashCollection<TestElement> coll = new ImplicitLinkedHashCollection<>();
          coll.add(new TestElement(1));
          coll.add(new TestElement(2));
          coll.add(new TestElement(3));
  
          Set<TestElement> set = coll.valuesSet();
          assertTrue(set.contains(new TestElement(1)));
          assertTrue(set.contains(new TestElement(2)));
          assertTrue(set.contains(new TestElement(3)));
          assertEquals(3, set.size());
      }
  
      @Test
      public void testSetViewModification() {
          ImplicitLinkedHashCollection<TestElement> coll = new ImplicitLinkedHashCollection<>();
          coll.add(new TestElement(1));
          coll.add(new TestElement(2));
          coll.add(new TestElement(3));
  
          // Removal from set is reflected in collection
          Set<TestElement> set = coll.valuesSet();
          set.remove(new TestElement(1));
          assertFalse(coll.contains(new TestElement(1)));
          assertEquals(2, coll.size());
  
          // Addition to set is reflected in collection
          set.add(new TestElement(4));
          assertTrue(coll.contains(new TestElement(4)));
          assertEquals(3, coll.size());
  
          // Removal from collection is reflected in set
          coll.remove(new TestElement(2));
          assertFalse(set.contains(new TestElement(2)));
          assertEquals(2, set.size());
  
          // Addition to collection is reflected in set
          coll.add(new TestElement(5));
          assertTrue(set.contains(new TestElement(5)));
          assertEquals(3, set.size());
  
          // Ordering in the collection is maintained
          int key = 3;
          for (TestElement e : coll) {
              assertEquals(key, e.key);
              ++key;
          }
      }
  
      @Test
      public void testListViewGet() {
          ImplicitLinkedHashCollection<TestElement> coll = new ImplicitLinkedHashCollection<>();
          coll.add(new TestElement(1));
          coll.add(new TestElement(2));
          coll.add(new TestElement(3));
  
          List<TestElement> list = coll.valuesList();
          assertEquals(1, list.get(0).key);
          assertEquals(2, list.get(1).key);
          assertEquals(3, list.get(2).key);
          assertEquals(3, list.size());
      }
  
      @Test
      public void testListViewModification() {
          ImplicitLinkedHashCollection<TestElement> coll = new ImplicitLinkedHashCollection<>();
          coll.add(new TestElement(1));
          coll.add(new TestElement(2));
          coll.add(new TestElement(3));
  
          // Removal from list is reflected in collection
          List<TestElement> list = coll.valuesList();
          list.remove(1);
          assertTrue(coll.contains(new TestElement(1)));
          assertFalse(coll.contains(new TestElement(2)));
          assertTrue(coll.contains(new TestElement(3)));
          assertEquals(2, coll.size());
  
          // Removal from collection is reflected in list
          coll.remove(new TestElement(1));
          assertEquals(3, list.get(0).key);
          assertEquals(1, list.size());
  
          // Addition to collection is reflected in list
          coll.add(new TestElement(4));
          assertEquals(3, list.get(0).key);
          assertEquals(4, list.get(1).key);
          assertEquals(2, list.size());
      }
  
      @Test
      public void testEmptyListIterator() {
          ImplicitLinkedHashCollection<TestElement> coll = new ImplicitLinkedHashCollection<>();
          ListIterator<TestElement> iter = coll.valuesList().listIterator();
          assertFalse(iter.hasNext());
          assertFalse(iter.hasPrevious());
          assertEquals(0, iter.nextIndex());
          assertEquals(-1, iter.previousIndex());
      }
  
      @Test
      public void testListIteratorCreation() {
          ImplicitLinkedHashCollection<TestElement> coll = new ImplicitLinkedHashCollection<>();
          coll.add(new TestElement(1));
          coll.add(new TestElement(2));
          coll.add(new TestElement(3));
  
          // Iterator created at the start of the list should have a next but no prev
          ListIterator<TestElement> iter = coll.valuesList().listIterator();
          assertTrue(iter.hasNext());
          assertFalse(iter.hasPrevious());
          assertEquals(0, iter.nextIndex());
          assertEquals(-1, iter.previousIndex());
  
          // Iterator created in the middle of the list should have both a next and a prev
          iter = coll.valuesList().listIterator(2);
          assertTrue(iter.hasNext());
          assertTrue(iter.hasPrevious());
          assertEquals(2, iter.nextIndex());
          assertEquals(1, iter.previousIndex());
  
          // Iterator created at the end of the list should have a prev but no next
          iter = coll.valuesList().listIterator(3);
          assertFalse(iter.hasNext());
          assertTrue(iter.hasPrevious());
          assertEquals(3, iter.nextIndex());
          assertEquals(2, iter.previousIndex());
      }
  
      @Test
      public void testListIteratorTraversal() {
          ImplicitLinkedHashCollection<TestElement> coll = new ImplicitLinkedHashCollection<>();
          coll.add(new TestElement(1));
          coll.add(new TestElement(2));
          coll.add(new TestElement(3));
          ListIterator<TestElement> iter = coll.valuesList().listIterator();
  
          // Step the iterator forward to the end of the list
          assertTrue(iter.hasNext());
          assertFalse(iter.hasPrevious());
          assertEquals(0, iter.nextIndex());
          assertEquals(-1, iter.previousIndex());
  
          assertEquals(1, iter.next().key);
          assertTrue(iter.hasNext());
          assertTrue(iter.hasPrevious());
          assertEquals(1, iter.nextIndex());
          assertEquals(0, iter.previousIndex());
  
          assertEquals(2, iter.next().key);
          assertTrue(iter.hasNext());
          assertTrue(iter.hasPrevious());
          assertEquals(2, iter.nextIndex());
          assertEquals(1, iter.previousIndex());
  
          assertEquals(3, iter.next().key);
          assertFalse(iter.hasNext());
          assertTrue(iter.hasPrevious());
          assertEquals(3, iter.nextIndex());
          assertEquals(2, iter.previousIndex());
  
          // Step back to the middle of the list
          assertEquals(3, iter.previous().key);
          assertTrue(iter.hasNext());
          assertTrue(iter.hasPrevious());
          assertEquals(2, iter.nextIndex());
          assertEquals(1, iter.previousIndex());
  
          assertEquals(2, iter.previous().key);
          assertTrue(iter.hasNext());
          assertTrue(iter.hasPrevious());
          assertEquals(1, iter.nextIndex());
          assertEquals(0, iter.previousIndex());
  
          // Step forward one and then back one, return value should remain the same
          assertEquals(2, iter.next().key);
          assertTrue(iter.hasNext());
          assertTrue(iter.hasPrevious());
          assertEquals(2, iter.nextIndex());
          assertEquals(1, iter.previousIndex());
  
          assertEquals(2, iter.previous().key);
          assertTrue(iter.hasNext());
          assertTrue(iter.hasPrevious());
          assertEquals(1, iter.nextIndex());
          assertEquals(0, iter.previousIndex());
  
          // Step back to the front of the list
          assertEquals(1, iter.previous().key);
          assertTrue(iter.hasNext());
          assertFalse(iter.hasPrevious());
          assertEquals(0, iter.nextIndex());
          assertEquals(-1, iter.previousIndex());
      }
  
      @Test
      public void testListIteratorRemove() {
          ImplicitLinkedHashCollection<TestElement> coll = new ImplicitLinkedHashCollection<>();
          coll.add(new TestElement(1));
          coll.add(new TestElement(2));
          coll.add(new TestElement(3));
          coll.add(new TestElement(4));
          coll.add(new TestElement(5));
  
          ListIterator<TestElement> iter = coll.valuesList().listIterator();
          try {
              iter.remove();
              fail("Calling remove() without calling next() or previous() should raise an exception");
          } catch (IllegalStateException e) {
              // expected
          }
  
          // Remove after next()
          iter.next();
          iter.next();
          iter.next();
          iter.remove();
          assertTrue(iter.hasNext());
          assertTrue(iter.hasPrevious());
          assertEquals(2, iter.nextIndex());
          assertEquals(1, iter.previousIndex());
  
          try {
              iter.remove();
              fail("Calling remove() twice without calling next() or previous() in between should raise an exception");
          } catch (IllegalStateException e) {
              // expected
          }
  
          // Remove after previous()
          assertEquals(2, iter.previous().key);
          iter.remove();
          assertTrue(iter.hasNext());
          assertTrue(iter.hasPrevious());
          assertEquals(1, iter.nextIndex());
          assertEquals(0, iter.previousIndex());
  
          // Remove the first element of the list
          assertEquals(1, iter.previous().key);
          iter.remove();
          assertTrue(iter.hasNext());
          assertFalse(iter.hasPrevious());
          assertEquals(0, iter.nextIndex());
          assertEquals(-1, iter.previousIndex());
  
          // Remove the last element of the list
          assertEquals(4, iter.next().key);
          assertEquals(5, iter.next().key);
          iter.remove();
          assertFalse(iter.hasNext());
          assertTrue(iter.hasPrevious());
          assertEquals(1, iter.nextIndex());
          assertEquals(0, iter.previousIndex());
  
          // Remove the final remaining element of the list
          assertEquals(4, iter.previous().key);
          iter.remove();
          assertFalse(iter.hasNext());
          assertFalse(iter.hasPrevious());
          assertEquals(0, iter.nextIndex());
          assertEquals(-1, iter.previousIndex());
  
      }
  
      @Test
      public void testCollisions() {
          ImplicitLinkedHashCollection<TestElement> coll = new ImplicitLinkedHashCollection<>(5);
          assertEquals(11, coll.numSlots());
          assertTrue(coll.add(new TestElement(11)));
          assertTrue(coll.add(new TestElement(0)));
          assertTrue(coll.add(new TestElement(22)));
          assertTrue(coll.add(new TestElement(33)));
          assertEquals(11, coll.numSlots());
          expectTraversal(coll.iterator(), 11, 0, 22, 33);
          assertTrue(coll.remove(new TestElement(22)));
          expectTraversal(coll.iterator(), 11, 0, 33);
          assertEquals(3, coll.size());
          assertFalse(coll.isEmpty());
      }
  
      @Test
      public void testEnlargement() {
          ImplicitLinkedHashCollection<TestElement> coll = new ImplicitLinkedHashCollection<>(5);
          assertEquals(11, coll.numSlots());
          for (int i = 0; i < 6; i++) {
              assertTrue(coll.add(new TestElement(i)));
          }
          assertEquals(23, coll.numSlots());
          assertEquals(6, coll.size());
          expectTraversal(coll.iterator(), 0, 1, 2, 3, 4, 5);
          for (int i = 0; i < 6; i++) {
              assertTrue(coll.contains(new TestElement(i)), "Failed to find element " + i);
          }
          coll.remove(new TestElement(3));
          assertEquals(23, coll.numSlots());
          assertEquals(5, coll.size());
          expectTraversal(coll.iterator(), 0, 1, 2, 4, 5);
      }
  
      @Test
      public void testManyInsertsAndDeletes() {
          Random random = new Random(123);
          LinkedHashSet<Integer> existing = new LinkedHashSet<>();
          ImplicitLinkedHashCollection<TestElement> coll = new ImplicitLinkedHashCollection<>();
          for (int i = 0; i < 100; i++) {
              addRandomElement(random, existing, coll);
              addRandomElement(random, existing, coll);
              addRandomElement(random, existing, coll);
              removeRandomElement(random, existing);
              expectTraversal(coll.iterator(), existing.iterator());
          }
      }
  
      @Test
      public void testInsertingTheSameObjectMultipleTimes() {
          ImplicitLinkedHashCollection<TestElement> coll = new ImplicitLinkedHashCollection<>();
          TestElement element = new TestElement(123);
          assertTrue(coll.add(element));
          assertFalse(coll.add(element));
          assertFalse(coll.add(element));
          assertTrue(coll.remove(element));
          assertFalse(coll.remove(element));
          assertTrue(coll.add(element));
          assertFalse(coll.add(element));
      }
  
      @Test
      public void testEquals() {
          ImplicitLinkedHashCollection<TestElement> coll1 = new ImplicitLinkedHashCollection<>();
          coll1.add(new TestElement(1));
          coll1.add(new TestElement(2));
          coll1.add(new TestElement(3));
  
          ImplicitLinkedHashCollection<TestElement> coll2 = new ImplicitLinkedHashCollection<>();
          coll2.add(new TestElement(1));
          coll2.add(new TestElement(2));
          coll2.add(new TestElement(3));
  
          ImplicitLinkedHashCollection<TestElement> coll3 = new ImplicitLinkedHashCollection<>();
          coll3.add(new TestElement(1));
          coll3.add(new TestElement(3));
          coll3.add(new TestElement(2));
  
          assertEquals(coll1, coll2);
          assertNotEquals(coll1, coll3);
          assertNotEquals(coll2, coll3);
      }
  
      @Test
      public void testFindContainsRemoveOnEmptyCollection() {
          ImplicitLinkedHashCollection<TestElement> coll = new ImplicitLinkedHashCollection<>();
          assertNull(coll.find(new TestElement(2)));
          assertFalse(coll.contains(new TestElement(2)));
          assertFalse(coll.remove(new TestElement(2)));
      }
  
      private void addRandomElement(Random random, LinkedHashSet<Integer> existing,
                                    ImplicitLinkedHashCollection<TestElement> set) {
          int next;
          do {
              next = random.nextInt();
          } while (existing.contains(next));
          existing.add(next);
          set.add(new TestElement(next));
      }
  
      @SuppressWarnings("unlikely-arg-type")
      private void removeRandomElement(Random random, Collection<Integer> existing) {
          int removeIdx = random.nextInt(existing.size());
          Iterator<Integer> iter = existing.iterator();
          Integer element = null;
          for (int i = 0; i <= removeIdx; i++) {
              element = iter.next();
          }
          existing.remove(new TestElement(element));
      }
  
      @Test
      public void testSameKeysDifferentValues() {
          ImplicitLinkedHashCollection<TestElement> coll = new ImplicitLinkedHashCollection<>();
          assertTrue(coll.add(new TestElement(1, 1)));
          assertFalse(coll.add(new TestElement(1, 2)));
          TestElement element2 = new TestElement(1, 2);
          TestElement element1 = coll.find(element2);
          assertNotEquals(element2, element1);
          assertTrue(element2.elementKeysAreEqual(element1));
      }
  
      @Test
      public void testMoveToEnd() {
          ImplicitLinkedHashCollection<TestElement> coll = new ImplicitLinkedHashCollection<>();
          TestElement e1 = new TestElement(1, 1);
          TestElement e2 = new TestElement(2, 2);
          TestElement e3 = new TestElement(3, 3);
          assertTrue(coll.add(e1));
          assertTrue(coll.add(e2));
          assertTrue(coll.add(e3));
          coll.moveToEnd(e1);
          expectTraversal(coll.iterator(), 2, 3, 1);
          assertThrows(RuntimeException.class, () -> coll.moveToEnd(new TestElement(4, 4)));
      }
  
      @Test
      public void testRemovals() {
          ImplicitLinkedHashCollection<TestElement> coll = new ImplicitLinkedHashCollection<>();
          List<TestElement> elements  = new ArrayList<>();
          for (int i = 0; i < 100; i++) {
              TestElement element  = new TestElement(i, i);
              elements.add(element);
              coll.add(element);
          }
          assertEquals(100, coll.size());
          Iterator<TestElement> iter = coll.iterator();
          for (int i = 0; i < 50; i++) {
              iter.next();
              iter.remove();
          }
          assertEquals(50, coll.size());
          for (int i = 50; i < 100; i++) {
              assertEquals(new TestElement(i, i), coll.find(elements.get(i)));
          }
      }
  
      static class TestElementComparator implements Comparator<TestElement> {
          static final TestElementComparator INSTANCE = new TestElementComparator();
  
          @Override
          public int compare(TestElement a, TestElement b) {
              if (a.key < b.key) {
                  return -1;
              } else if (a.key > b.key) {
                  return 1;
              } else return Integer.compare(a.val, b.val);
          }
      }
  
      static class ReverseTestElementComparator implements Comparator<TestElement> {
          static final ReverseTestElementComparator INSTANCE = new ReverseTestElementComparator();
  
          @Override
          public int compare(TestElement a, TestElement b) {
              return TestElementComparator.INSTANCE.compare(b, a);
          }
      }
  
      @Test
      public void testSort() {
          ImplicitLinkedHashCollection<TestElement> coll = new ImplicitLinkedHashCollection<>();
          coll.add(new TestElement(3, 3));
          coll.add(new TestElement(1, 1));
          coll.add(new TestElement(10, 10));
          coll.add(new TestElement(9, 9));
          coll.add(new TestElement(2, 2));
          coll.add(new TestElement(4, 4));
          coll.add(new TestElement(0, 0));
          coll.add(new TestElement(30, 30));
          coll.add(new TestElement(20, 20));
          coll.add(new TestElement(11, 11));
          coll.add(new TestElement(15, 15));
          coll.add(new TestElement(5, 5));
  
          expectTraversal(coll.iterator(), 3, 1, 10, 9, 2, 4, 0, 30, 20, 11, 15, 5);
          coll.sort(TestElementComparator.INSTANCE);
          expectTraversal(coll.iterator(), 0, 1, 2, 3, 4, 5, 9, 10, 11, 15, 20, 30);
          coll.sort(TestElementComparator.INSTANCE);
          expectTraversal(coll.iterator(), 0, 1, 2, 3, 4, 5, 9, 10, 11, 15, 20, 30);
          coll.sort(ReverseTestElementComparator.INSTANCE);
          expectTraversal(coll.iterator(), 30, 20, 15, 11, 10, 9, 5, 4, 3, 2, 1, 0);
      }
  }
  