Map-like implementation that associates objects to indices.

IndexMap.java

import com.google.common.base.Preconditions;
import com.google.errorprone.annotations.CanIgnoreReturnValue;
import com.google.errorprone.annotations.CheckReturnValue;
import lombok.Getter;
import org.checkerframework.checker.index.qual.NonNegative;
import org.checkerframework.checker.nullness.qual.NonNull;
import org.checkerframework.checker.nullness.qual.Nullable;
import org.checkerframework.dataflow.qual.Pure;

import java.util.*;
import java.util.function.IntFunction;

/**
 * Map-like implementation that associates objects to indices.
 * <p>This implementation utilizes a resizable array, that dynamically grows and shrinks with
 * elements added and removed.
 *
 * @author aparx (Vinzent Z.)
 * @version 2023-12-01 18:34
 * @since 1.0
 */
public class IndexMap<E> implements Iterable<IndexMap.Entry<E>>, Cloneable {

  public static final int DEFAULT_INITIAL_CAPACITY = 10;

  private static final int INDEX_NOT_FOUND = -1;

  private final int initialCapacity;

  private transient Entry<E>[] array;

  private transient int elementCount;

  public IndexMap() {
    this(DEFAULT_INITIAL_CAPACITY);
  }

  @SuppressWarnings("unchecked")
  public IndexMap(int initialCapacity) {
    this.initialCapacity = Math.max(initialCapacity, 0);
    this.array = new Entry[this.initialCapacity];
  }

  @SuppressWarnings("unchecked")
  public IndexMap(@NonNull Map<Integer, ? extends E> map) {
    this.initialCapacity = map.size();
    this.array = new Entry[initialCapacity];
    putAll(map);
  }

  @SuppressWarnings({"unchecked"})
  public IndexMap(@NonNull IndexMap<E> other) {
    this.initialCapacity = other.capacity();
    this.array = new Entry[initialCapacity];
    this.elementCount = other.elementCount;
    int elemTracker = 0;
    // copy keys & values
    for (int i = 0, len = other.capacity(); i < len; ++i) {
      Entry<E> otherEntry = other.array[i];
      if (otherEntry != null) {
        array[i] = new Entry<>(otherEntry.getIndex(), otherEntry.getObject());
        ++elemTracker;
      }
    }
    if (elemTracker != elementCount)
      throw new ConcurrentModificationException();
  }

  @Pure
  public final @NonNegative int capacity() {
    return array.length;
  }

  @Pure
  public final @NonNegative int size() {
    return elementCount;
  }

  public void clear() {
    int previousCapacity = capacity();
    resizeToCapacity0(initialCapacity, false);
    if (capacity() == previousCapacity)
      Arrays.fill(array, null);
    elementCount = 0;
  }

  public void ensureCapacity(int capacity) {
    if (capacity > capacity())
      resizeToCapacity0(capacity, true);
  }

  public @Nullable E get(int index) {
    Preconditions.checkElementIndex(index, capacity());
    Entry<E> entry = array[index];
    if (entry != null)
      return entry.getValue();
    return null;
  }

  @CanIgnoreReturnValue
  public @Nullable E put(@NonNull Entry<E> entry) {
    Preconditions.checkNotNull(entry, "Entry must not be null");
    return put(entry.getIndex(), entry.getValue());
  }

  @CanIgnoreReturnValue
  public @Nullable E put(int index, E value) {
    Preconditions.checkState(index >= 0, "Index must be positive");
    if (index >= capacity())
      resizeToCapacity0(calculateNewCapacity(1 + index), true);
    Entry<E> entry = array[index];
    E previousValue = null;
    if (entry == null) {
      array[index] = new Entry<>(index, value);
      ++elementCount;
    } else {
      previousValue = entry.getValue();
      entry.setValue(value);
    }
    return previousValue;
  }

  public void putAll(@NonNull Map<@NonNull Integer, ? extends E> map, int indexOffset) {
    Preconditions.checkArgument(indexOffset >= 0, "indexOffset must be zero or positive");
    Preconditions.checkNotNull(map, "Map must not be null");
    ensureCapacity(indexOffset + map.size());
    for (Map.Entry<Integer, ? extends E> entry : map.entrySet())
      put(indexOffset + Objects.requireNonNull(entry.getKey()), entry.getValue());
  }

  public void putAll(@NonNull Map<@NonNull Integer, ? extends E> map) {
    putAll(map, 0);
  }

  public void putAll(E @NonNull [] array, int indexOffset) {
    Preconditions.checkArgument(indexOffset >= 0, "indexOffset must be zero or positive");
    ensureCapacity(indexOffset + array.length);
    for (int i = 0, len = array.length; i < len; ++i)
      put(indexOffset + i, array[i]);
  }

  public void putAll(E @NonNull [] array) {
    putAll(array, 0);
  }

  public void putAll(@NonNull Iterable<? extends E> iterable, int indexOffset) {
    Preconditions.checkArgument(indexOffset >= 0, "indexOffset must be zero or positive");
    if (iterable instanceof Collection)
      ensureCapacity(indexOffset + ((Collection<?>) iterable).size());
    Iterator<? extends E> iterator = iterable.iterator();
    for (int i = 0; iterator.hasNext(); ++i)
      put(indexOffset + i, iterator.next());
  }

  public void putAll(@NonNull Iterable<? extends E> iterable) {
    putAll(iterable, 0);
  }

  @CanIgnoreReturnValue
  public @Nullable E remove(int index) {
    Preconditions.checkElementIndex(index, size());
    E previousValue = null;
    Entry<E> entry = array[index];
    if (entry != null) {
      previousValue = entry.getValue();
      entry.setValue(null);
    }
    array[index] = null;
    --elementCount;
    return previousValue;
  }

  @CanIgnoreReturnValue
  public boolean remove(int index, Object value) {
    Preconditions.checkElementIndex(index, size());
    Entry<E> entry = array[index];
    if (entry != null && Objects.equals(entry.getValue(), value))
      return remove(index) != null;
    return false;
  }

  public boolean containsKey(int index) {
    return index >= 0 && index < capacity() && array[index] != null;
  }

  public boolean containsValue(Object value) {
    return indexOf(value) != INDEX_NOT_FOUND;
  }

  public boolean contains(int index, Object value) {
    if (index < 0 || index >= capacity())
      return false;
    Entry<E> entry = array[index];
    return entry != null && Objects.equals(entry.getValue(), value);
  }

  @CheckReturnValue
  public int indexOf(Object value) {
    if (value == null) {
      for (int i = 0, len = capacity(); i < len; ++i) {
        Entry<E> entry = array[i];
        if (entry != null && entry.object == null)
          return i;
      }
    } else {
      for (int i = 0, len = capacity(); i < len; ++i) {
        Entry<E> entry = array[i];
        if (entry != null && Objects.equals(value, entry.getValue()))
          return i;
      }
    }
    return INDEX_NOT_FOUND;
  }

  @CheckReturnValue
  public int lastIndexOf(Object value) {
    if (value == null) {
      for (int i = capacity(); i > 0; --i) {
        Entry<E> entry = array[i - 1];
        if (entry != null && entry.object == null)
          return i - 1;
      }
    } else {
      for (int i = capacity(); i > 0; --i) {
        Entry<E> entry = array[i - 1];
        if (entry != null && Objects.equals(value, entry.getValue()))
          return i - 1;
      }
    }
    return INDEX_NOT_FOUND;
  }

  public Map<Integer, E> toMap() {
    return toMap(HashMap::new);
  }

  public Map<Integer, E> toMap(@NonNull IntFunction<? extends Map<Integer, E>> factory) {
    Map<Integer, E> map = factory.apply(size());
    for (int i = 0; i < array.length; ++i) {
      Entry<E> entry = array[i];
      if (entry != null)
        map.put(i, entry.getValue());
    }
    return map;
  }

  @SuppressWarnings({"rawtypes", "unchecked"})
  private void resizeToCapacity0(int newCapacity, boolean copyThisArray) {
    int oldCapacity = capacity();
    if (oldCapacity == newCapacity)
      return;
    Entry[] newArray = new Entry[newCapacity];
    if (copyThisArray && array.length != 0 && newCapacity != 0)
      System.arraycopy(array, 0, newArray, 0, Math.min(array.length, newCapacity));
    this.array = newArray;
  }

  private int calculateNewCapacity(int newCapacity) {
    return (int) Math.ceil(newCapacity * 1.5);
  }

  @Override
  public @NonNull Iterator<Entry<E>> iterator() {
    return new Iterator<>() {

      int cursor = 0;
      Boolean hasNext;

      @Override
      public boolean hasNext() {
        if (hasNext != null)
          return hasNext;
        for (int i = cursor; i < array.length; ++i)
          if (array[i] != null)
            return hasNext = Boolean.TRUE;
        return hasNext = Boolean.FALSE;
      }

      @Override
      public Entry<E> next() {
        hasNext = null;
        while (cursor < array.length) {
          int i = cursor++;
          Entry<E> entry = array[i];
          if (entry != null)
            return entry;
        }
        throw new NoSuchElementException();
      }
    };
  }

  @Override
  @SuppressWarnings("unchecked")
  public IndexMap<E> clone() {
    try {
      IndexMap<E> clone = (IndexMap<E>) super.clone();
      clone.array = array.clone();
      return clone;
    } catch (CloneNotSupportedException e) {
      throw new RuntimeException(e);
    }
  }

  @Getter
  public static final class Entry<E> {
    private final int index;
    private Object object;

    private Entry(int index, Object object) {
      this.index = index;
      this.object = object;
    }

    public static <E> Entry<E> of(int index, E value) {
      Preconditions.checkArgument(index >= 0, "Index must be positive");
      return new Entry<>(index, value);
    }

    public void setValue(E value) {
      this.object = value;
    }

    @SuppressWarnings("unchecked") // OK
    public E getValue() {
      return (E) object;
    }
  }

}

IndexMapTests.java

import org.junit.Test;
import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Order;

import java.util.Map;

/**
 * @author aparx (Vinzent Z.)
 * @version 2023-12-18 10:55
 * @since 1.0
 */
public class IndexMapTests {

  @Test
  @Order(1 + Order.DEFAULT)
  public void size() {
    IndexMap<String> map = new IndexMap<>();
    map.putAll(new String[]{"a", "b", "c", "d", "e"});
    Assertions.assertEquals(5, map.size());
    map.remove(1);
    Assertions.assertEquals(4, map.size());
    map.remove(3);
    Assertions.assertEquals(3, map.size());
    map.clear();
    Assertions.assertEquals(0, map.size());
    Assertions.assertEquals(IndexMap.DEFAULT_INITIAL_CAPACITY, map.capacity());
  }

  @Test
  public void put() {
    IndexMap<String> map = new IndexMap<>();
    map.put(IndexMap.Entry.of(0, "hello"));
    map.put(IndexMap.Entry.of(1, "world"));
    Assertions.assertEquals("hello", map.get(0));
    Assertions.assertEquals("world", map.get(1));
    Assertions.assertEquals("hello", map.put(0, "hello"));
    Assertions.assertEquals("world", map.put(1, "world"));
    Assertions.assertEquals("hello", map.get(0));
    Assertions.assertEquals("world", map.get(1));
    Assertions.assertEquals("hello", map.put(0, "hello"));
    Assertions.assertEquals("world", map.remove(1));
    Assertions.assertNull(map.put(2, "world"));
    Assertions.assertEquals("hello", map.get(0));
    Assertions.assertEquals("world", map.get(2));
    Assertions.assertNull(map.get(1));
  }

  @Test
  public void putAll() {
    IndexMap<String> map = new IndexMap<>();
    map.put(0, "hello");
    map.put(3, "world");
    map.putAll(new String[]{"a", "b", "c"});
    Assertions.assertEquals("a", map.get(0));
    Assertions.assertEquals("b", map.get(1));
    Assertions.assertEquals("c", map.get(2));
    Assertions.assertEquals("world", map.get(3));

    map.putAll(Map.of(0, "hello", 3, "there"));
    Assertions.assertEquals("hello", map.get(0));
    Assertions.assertEquals("b", map.get(1));
    Assertions.assertEquals("c", map.get(2));
    Assertions.assertEquals("there", map.get(3));
  }

  @Test
  public void contains() {
    IndexMap<String> map = new IndexMap<>();
    map.put(0, "a");
    map.put(1, "b");
    map.put(2, "c");
    map.put(3, null);
    map.put(5, null);
    Assertions.assertTrue(map.contains(0, "a"));
    Assertions.assertFalse(map.contains(0, "b"));
    Assertions.assertTrue(map.contains(1, "b"));
    Assertions.assertFalse(map.contains(1, "c"));
    Assertions.assertTrue(map.contains(2, "c"));
    Assertions.assertFalse(map.contains(3, "d"));
    Assertions.assertTrue(map.contains(3, null));
    Assertions.assertFalse(map.contains(4, null));
    Assertions.assertTrue(map.contains(5, null));
    Assertions.assertFalse(map.contains(6, "a"));
  }

  @Test
  public void containsKey() {
    IndexMap<String> map = new IndexMap<>();
    map.put(0, "a");
    map.put(1, "b");
    map.put(2, "c");
    map.put(3, null);
    map.put(5, null);
    Assertions.assertTrue(map.containsKey(0));
    Assertions.assertTrue(map.containsKey(1));
    Assertions.assertTrue(map.containsKey(2));
    Assertions.assertTrue(map.containsKey(3));
    Assertions.assertFalse(map.containsKey(4));
    Assertions.assertTrue(map.containsKey(5));
    Assertions.assertFalse(map.containsKey(6));
    Assertions.assertFalse(map.containsKey(7));
  }

  @Test
  public void containsValue() {
    IndexMap<String> map = new IndexMap<>();
    map.put(0, "a");
    map.put(1, "b");
    map.put(2, "c");
    map.put(3, null);
    map.put(5, null);
    Assertions.assertTrue(map.containsValue("a"));
    Assertions.assertTrue(map.containsValue("b"));
    Assertions.assertTrue(map.containsValue("c"));
    Assertions.assertTrue(map.containsValue(null));
    Assertions.assertFalse(map.containsValue("d"));
  }

  @Test
  public void indexOf() {
    IndexMap<String> map = new IndexMap<>();
    map.put(0, "a");
    map.put(1, "b");
    map.put(2, "c");
    map.put(3, null);
    map.put(5, null);
    Assertions.assertEquals(0, map.indexOf("a"));
    Assertions.assertEquals(1, map.indexOf("b"));
    Assertions.assertEquals(2, map.indexOf("c"));
    Assertions.assertEquals(3, map.indexOf(null));
    Assertions.assertEquals(-1, map.indexOf("d"));
  }

  @Test
  public void lastIndexOf() {
    IndexMap<String> map = new IndexMap<>();
    map.put(0, "a");
    map.put(1, "a");
    map.put(2, "b");
    map.put(3, "b");
    map.put(4, "c");
    map.put(5, "c");
    map.put(6, null);
    map.put(7, null);
    Assertions.assertEquals(1, map.lastIndexOf("a"));
    Assertions.assertEquals(3, map.lastIndexOf("b"));
    Assertions.assertEquals(5, map.lastIndexOf("c"));
    Assertions.assertEquals(7, map.lastIndexOf(null));
    Assertions.assertEquals(-1, map.lastIndexOf("d"));
  }


}