Repository: TheAlgorithms/Java
Pull request #5346 (2024-08-19 07:54:11)

refactor: `DynamicArray`
Improvements to the `DynamicArray` class:

Capacity Management:
Added checks to automatically resize the array if an element is added at an index beyond the current size.
Simplified the add and put methods to ensure they handle capacity correctly.

Boundary and Error Handling:
Added checks for invalid indices (negative values and out-of-bound values).
Enhanced type safety by suppressing warnings for unchecked casts.

Concurrent Modification:
Introduced a `modCount` field to track structural modifications and ensure that the iterator detects concurrent modifications.

Iterator Implementation:
Improved Iterator to correctly detect concurrent modifications and handle the remove operation safely.

Added tests.


<!--
Thank you for your contribution!
In order to reduce the number of notifications sent to the maintainers, please:
- create your PR as draft, cf. https://docs.github.com/en/pull-requests/collaborating-with-pull-requests/proposing-changes-to-your-work-with-pull-requests/about-pull-requests#draft-pull-requests,
- make sure that all of the CI checks pass,
- mark your PR as ready for review, cf. https://docs.github.com/en/pull-requests/collaborating-with-pull-requests/proposing-changes-to-your-work-with-pull-requests/changing-the-stage-of-a-pull-request#marking-a-pull-request-as-ready-for-review
-->

<!-- For completed items, change [ ] to [x] -->

- [x] I have read [CONTRIBUTING.md](https://github.com/TheAlgorithms/Java/blob/master/CONTRIBUTING.md).
- [x] This pull request is all my own work -- I have not plagiarized it.
- [x] All filenames are in PascalCase.
- [x] All functions and variable names follow Java naming conventions.
- [x] All new algorithms have a URL in their comments that points to Wikipedia or other similar explanations.
- [x] All new code is formatted with `clang-format -i --style=file path/to/your/file.java`

codecov-commenter: ## [Codecov](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5346?dropdown=coverage&src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) Report
Attention: Patch coverage is `89.79592%` with `5 lines` in your changes missing coverage. Please review.
> Project coverage is 43.84%. Comparing base [(`33fd79a`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/33fd79ad55af74c5aae48906c15838f6ed710a85?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) to head [(`051b35a`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/051b35a3e49c9af817b995961c3516886f310ad0?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).

| [Files](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5346?dropdown=coverage&src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) | Patch % | Lines |
|---|---|---|
| [...thms/datastructures/dynamicarray/DynamicArray.java](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5346?src=pr&el=tree&filepath=src%2Fmain%2Fjava%2Fcom%2Fthealgorithms%2Fdatastructures%2Fdynamicarray%2FDynamicArray.java&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms#diff-c3JjL21haW4vamF2YS9jb20vdGhlYWxnb3JpdGhtcy9kYXRhc3RydWN0dXJlcy9keW5hbWljYXJyYXkvRHluYW1pY0FycmF5LmphdmE=) | 89.79% | [1 Missing and 4 partials :warning: ](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5346?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) |

<details><summary>Additional details and impacted files</summary>


```diff
@@             Coverage Diff              @@
##             master    #5346      +/-   ##
============================================
+ Coverage     43.44%   43.84%   +0.39%     
- Complexity     2694     2716      +22     
============================================
  Files           522      522              
  Lines         15440    15440              
  Branches       2954     2953       -1     
============================================
+ Hits           6708     6769      +61     
+ Misses         8440     8376      -64     
- Partials        292      295       +3     
```

</details>

[:umbrella: View full report in Codecov by Sentry](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5346?dropdown=coverage&src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).   
:loudspeaker: Have feedback on the report? [Share it here](https://about.codecov.io/codecov-pr-comment-feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).


Patch:
diff --git a/src/main/java/com/thealgorithms/datastructures/dynamicarray/DynamicArray.java b/src/main/java/com/thealgorithms/datastructures/dynamicarray/DynamicArray.java
index cfec2e3b..a5fa9cbe 100644
--- a/src/main/java/com/thealgorithms/datastructures/dynamicarray/DynamicArray.java
+++ b/src/main/java/com/thealgorithms/datastructures/dynamicarray/DynamicArray.java
@@ -10,145 +10,143 @@ import java.util.stream.Stream;
 import java.util.stream.StreamSupport;
 
 /**
- * This class implements a dynamic array
+ * This class implements a dynamic array.
  *
  * @param <E> the type that each index of the array will hold
  */
 public class DynamicArray<E> implements Iterable<E> {
 
     private static final int DEFAULT_CAPACITY = 16;
-
-    private int capacity;
     private int size;
+    private int modCount; // Tracks structural modifications for the iterator
     private Object[] elements;
 
     /**
-     * constructor
+     * Constructor with initial capacity.
      *
      * @param capacity the starting length of the desired array
+     * @throws IllegalArgumentException if the specified capacity is negative
      */
     public DynamicArray(final int capacity) {
+        if (capacity < 0) {
+            throw new IllegalArgumentException("Capacity cannot be negative.");
+        }
         this.size = 0;
-        this.capacity = capacity;
-        this.elements = new Object[this.capacity];
+        this.modCount = 0;
+        this.elements = new Object[capacity];
     }
 
     /**
-     * No-args constructor
+     * No-args constructor with default capacity.
      */
     public DynamicArray() {
         this(DEFAULT_CAPACITY);
     }
 
     /**
-     * Adds an element to the array If full, creates a copy array twice the size
-     * of the current one
+     * Adds an element to the array. If full, creates a new array with double the size.
      *
-     * @param element the element of type <E> to be added to the array
+     * @param element the element to be added to the array
      */
     public void add(final E element) {
-        if (this.size == this.elements.length) {
-            this.elements = Arrays.copyOf(this.elements, newCapacity(2 * this.capacity));
-        }
-
-        this.elements[this.size] = element;
-        size++;
+        ensureCapacity(size + 1);
+        elements[size++] = element;
+        modCount++; // Increment modification count
     }
 
     /**
-     * Places element of type <E> at the desired index
+     * Places an element at the desired index, expanding capacity if necessary.
      *
-     * @param index the index for the element to be placed
+     * @param index   the index for the element to be placed
      * @param element the element to be inserted
+     * @throws IndexOutOfBoundsException if n is less than 0 or greater or equal to the number of elements in the array
      */
     public void put(final int index, E element) {
-        this.elements[index] = element;
+        if (index < 0) {
+            throw new IndexOutOfBoundsException("Index cannot be negative.");
+        }
+        ensureCapacity(index + 1);
+        elements[index] = element;
+        if (index >= size) {
+            size = index + 1;
+        }
+        modCount++; // Increment modification count
     }
 
     /**
-     * get method for element at a given index returns null if the index is
-     * empty
+     * Gets the element at a given index.
      *
      * @param index the desired index of the element
-     * @return <E> the element at the specified index
+     * @return the element at the specified index
+     * @throws IndexOutOfBoundsException if n is less than 0 or greater or equal to the number of elements in the array
      */
+    @SuppressWarnings("unchecked")
     public E get(final int index) {
-        return getElement(index);
+        if (index < 0 || index >= size) {
+            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
+        }
+        return (E) elements[index];
     }
 
     /**
-     * Removes an element from the array
+     * Removes an element from the array.
      *
      * @param index the index of the element to be removed
-     * @return <E> the element removed
+     * @return the element removed
+     * @throws IndexOutOfBoundsException if n is less than 0 or greater or equal to the number of elements in the array
      */
     public E remove(final int index) {
-        final E oldElement = getElement(index);
-        fastRemove(this.elements, index);
-
-        if (this.capacity > DEFAULT_CAPACITY && size * 4 <= this.capacity) {
-            this.elements = Arrays.copyOf(this.elements, newCapacity(this.capacity / 2));
+        if (index < 0 || index >= size) {
+            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
         }
+        @SuppressWarnings("unchecked") E oldElement = (E) elements[index];
+        fastRemove(index);
+        modCount++; // Increment modification count
         return oldElement;
     }
 
     /**
-     * get method for size field
+     * Gets the size of the array.
      *
-     * @return int size
+     * @return the size
      */
     public int getSize() {
-        return this.size;
+        return size;
     }
 
     /**
-     * isEmpty helper method
+     * Checks if the array is empty.
      *
-     * @return boolean true if the array contains no elements, false otherwise
+     * @return true if the array contains no elements, false otherwise
      */
     public boolean isEmpty() {
-        return this.size == 0;
+        return size == 0;
     }
 
     public Stream<E> stream() {
         return StreamSupport.stream(spliterator(), false);
     }
 
-    private void fastRemove(final Object[] elements, final int index) {
-        final int newSize = this.size - 1;
-
-        if (newSize > index) {
-            System.arraycopy(elements, index + 1, elements, index, newSize - index);
+    private void ensureCapacity(int minCapacity) {
+        if (minCapacity > elements.length) {
+            int newCapacity = Math.max(elements.length * 2, minCapacity);
+            elements = Arrays.copyOf(elements, newCapacity);
         }
-
-        this.size = newSize;
-        this.elements[this.size] = null;
     }
 
-    private E getElement(final int index) {
-        return (E) this.elements[index];
-    }
-
-    private int newCapacity(int capacity) {
-        this.capacity = capacity;
-        return this.capacity;
+    private void fastRemove(int index) {
+        int numMoved = size - index - 1;
+        if (numMoved > 0) {
+            System.arraycopy(elements, index + 1, elements, index, numMoved);
+        }
+        elements[--size] = null; // Clear to let GC do its work
     }
 
-    /**
-     * returns a String representation of this object
-     *
-     * @return String a String representing the array
-     */
     @Override
     public String toString() {
-        return Arrays.toString(Arrays.stream(this.elements).filter(Objects::nonNull).toArray());
+        return Arrays.toString(Arrays.copyOf(elements, size));
     }
 
-    /**
-     * Creates and returns a new Dynamic Array Iterator
-     *
-     * @return Iterator a Dynamic Array Iterator
-     */
     @Override
     public Iterator<E> iterator() {
         return new DynamicArrayIterator();
@@ -157,71 +155,50 @@ public class DynamicArray<E> implements Iterable<E> {
     private final class DynamicArrayIterator implements Iterator<E> {
 
         private int cursor;
+        private int expectedModCount;
+
+        DynamicArrayIterator() {
+            this.expectedModCount = modCount;
+        }
 
         @Override
         public boolean hasNext() {
-            return this.cursor != size;
+            checkForComodification();
+            return cursor < size;
         }
 
         @Override
+        @SuppressWarnings("unchecked")
         public E next() {
-            if (this.cursor > DynamicArray.this.size) {
+            checkForComodification();
+            if (cursor >= size) {
                 throw new NoSuchElementException();
             }
-
-            if (this.cursor > DynamicArray.this.elements.length) {
-                throw new ConcurrentModificationException();
-            }
-
-            final E element = DynamicArray.this.getElement(this.cursor);
-            this.cursor++;
-
-            return element;
+            return (E) elements[cursor++];
         }
 
         @Override
         public void remove() {
-            if (this.cursor < 0) {
+            if (cursor <= 0) {
                 throw new IllegalStateException();
             }
+            checkForComodification();
+            DynamicArray.this.remove(--cursor);
+            expectedModCount = ++modCount;
+        }
 
-            DynamicArray.this.remove(this.cursor);
-            this.cursor--;
+        private void checkForComodification() {
+            if (modCount != expectedModCount) {
+                throw new ConcurrentModificationException();
+            }
         }
 
         @Override
         public void forEachRemaining(Consumer<? super E> action) {
             Objects.requireNonNull(action);
-
-            for (int i = 0; i < DynamicArray.this.size; i++) {
-                action.accept(DynamicArray.this.getElement(i));
+            while (hasNext()) {
+                action.accept(next());
             }
         }
     }
-
-    /**
-     * This class is the driver for the DynamicArray<E> class it tests a variety
-     * of methods and prints the output
-     */
-    public static void main(String[] args) {
-        DynamicArray<String> names = new DynamicArray<>();
-        names.add("Peubes");
-        names.add("Marley");
-
-        for (String name : names) {
-            System.out.println(name);
-        }
-
-        names.stream().forEach(System.out::println);
-
-        System.out.println(names);
-
-        System.out.println(names.getSize());
-
-        names.remove(0);
-
-        for (String name : names) {
-            System.out.println(name);
-        }
-    }
 }


Test patch:
diff --git a/src/test/java/com/thealgorithms/datastructures/dynamicarray/DynamicArrayTest.java b/src/test/java/com/thealgorithms/datastructures/dynamicarray/DynamicArrayTest.java
new file mode 100644
index 00000000..8e067086
--- /dev/null
+++ b/src/test/java/com/thealgorithms/datastructures/dynamicarray/DynamicArrayTest.java
@@ -0,0 +1,255 @@
+package com.thealgorithms.datastructures.dynamicarray;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+import static org.junit.jupiter.api.Assertions.assertFalse;
+import static org.junit.jupiter.api.Assertions.assertThrows;
+import static org.junit.jupiter.api.Assertions.assertTrue;
+
+import java.util.ConcurrentModificationException;
+import java.util.Iterator;
+import java.util.stream.Collectors;
+import org.junit.jupiter.api.BeforeEach;
+import org.junit.jupiter.api.Test;
+
+public class DynamicArrayTest {
+
+    private DynamicArray<String> array;
+
+    @BeforeEach
+    public void setUp() {
+        array = new DynamicArray<>();
+    }
+
+    @Test
+    public void testGetElement() {
+        array.add("Alice");
+        array.add("Bob");
+        assertEquals("Bob", array.get(1));
+    }
+
+    @Test
+    public void testGetInvalidIndex() {
+        assertThrows(IndexOutOfBoundsException.class, () -> array.get(-1));
+        assertThrows(IndexOutOfBoundsException.class, () -> array.get(10));
+    }
+
+    @Test
+    public void testAddElement() {
+        array.add("Alice");
+        array.add("Bob");
+        assertEquals(2, array.getSize());
+        assertEquals("Alice", array.get(0));
+        assertEquals("Bob", array.get(1));
+    }
+
+    @Test
+    public void testAddAndGet() {
+        array.add("Alice");
+        array.add("Bob");
+
+        assertEquals("Alice", array.get(0));
+        assertEquals("Bob", array.get(1));
+        assertThrows(IndexOutOfBoundsException.class, () -> array.get(2));
+    }
+
+    @Test
+    public void testAddBeyondCapacity() {
+        for (int i = 0; i < 20; i++) {
+            array.add("Element " + i);
+        }
+        assertEquals(20, array.getSize());
+        assertEquals("Element 19", array.get(19));
+    }
+
+    @Test
+    public void testPutElement() {
+        array.put(5, "Placeholder");
+        assertEquals(6, array.getSize());
+        assertEquals("Placeholder", array.get(5));
+    }
+
+    @Test
+    public void testPutElementBeyondCapacity() {
+        array.put(20, "FarAway");
+        assertEquals(21, array.getSize());
+        assertEquals("FarAway", array.get(20));
+    }
+
+    @Test
+    public void testPutAndDynamicCapacity() {
+        array.put(0, "Alice");
+        array.put(2, "Bob"); // Tests capacity expansion
+
+        assertEquals("Alice", array.get(0));
+        assertEquals("Bob", array.get(2));
+        assertEquals(3, array.getSize()); // Size should be 3 due to index 2
+    }
+
+    @Test
+    public void testRemoveElement() {
+        array.add("Alice");
+        array.add("Bob");
+        String removed = array.remove(0);
+        assertEquals("Alice", removed);
+        assertEquals(1, array.getSize());
+        assertEquals("Bob", array.get(0));
+    }
+
+    @Test
+    public void testRemoveInvalidIndex() {
+        assertThrows(IndexOutOfBoundsException.class, () -> array.remove(-1));
+        assertThrows(IndexOutOfBoundsException.class, () -> array.remove(10));
+    }
+
+    @Test
+    public void testRemoveComplex() {
+        array.add("Alice");
+        array.add("Bob");
+        array.add("Charlie");
+
+        assertEquals("Bob", array.remove(1));
+        assertEquals("Alice", array.get(0));
+        assertEquals("Charlie", array.get(1));
+        assertThrows(IndexOutOfBoundsException.class, () -> array.remove(2));
+    }
+
+    @Test
+    public void testRemoveEdgeCases() {
+        array.add("Alice");
+        array.add("Bob");
+
+        assertEquals("Alice", array.remove(0));
+        assertEquals(1, array.getSize());
+        assertEquals("Bob", array.get(0));
+
+        assertEquals("Bob", array.remove(0));
+        assertTrue(array.isEmpty());
+        assertThrows(IndexOutOfBoundsException.class, () -> array.get(0));
+    }
+
+    @Test
+    public void testIsEmpty() {
+        assertTrue(array.isEmpty());
+
+        array.add("Alice");
+        assertFalse(array.isEmpty());
+
+        array.remove(0);
+        assertTrue(array.isEmpty());
+    }
+
+    @Test
+    public void testSize() {
+        DynamicArray<String> array = new DynamicArray<>();
+        assertEquals(0, array.getSize());
+
+        array.add("Alice");
+        array.add("Bob");
+        assertEquals(2, array.getSize());
+
+        array.remove(0);
+        assertEquals(1, array.getSize());
+    }
+
+    @Test
+    public void testToString() {
+        array.add("Alice");
+        array.add("Bob");
+
+        assertEquals("[Alice, Bob]", array.toString());
+    }
+
+    @Test
+    public void testIterator() {
+        array.add("Alice");
+        array.add("Bob");
+
+        String result = array.stream().collect(Collectors.joining(", "));
+        assertEquals("Alice, Bob", result);
+    }
+
+    @Test
+    public void testStreamAsString() {
+        array.add("Alice");
+        array.add("Bob");
+
+        String result = array.stream().collect(Collectors.joining(", "));
+        assertEquals("Alice, Bob", result);
+    }
+
+    @Test
+    public void testStream() {
+        array.add("Alice");
+        array.add("Bob");
+        long count = array.stream().count();
+        assertEquals(2, count);
+    }
+
+    @Test
+    public void testAddToFullCapacity() {
+        DynamicArray<String> array = new DynamicArray<>(2);
+        array.add("Alice");
+        array.add("Bob");
+        array.add("Charlie"); // Triggers capacity expansion
+
+        assertEquals(3, array.getSize());
+        assertEquals("Charlie", array.get(2));
+    }
+
+    @Test
+    public void testPutWithNegativeIndex() {
+        assertThrows(IndexOutOfBoundsException.class, () -> array.put(-1, "Alice"));
+    }
+
+    @Test
+    public void testGetWithNegativeIndex() {
+        assertThrows(IndexOutOfBoundsException.class, () -> array.get(-1));
+    }
+
+    @Test
+    public void testIteratorConcurrentModification() {
+        array.add("Alice");
+        array.add("Bob");
+
+        Iterator<String> iterator = array.iterator();
+        array.add("Charlie"); // Modify during iteration
+
+        assertThrows(ConcurrentModificationException.class, iterator::next);
+    }
+
+    @Test
+    public void testIteratorRemove() {
+        array.add("Alice");
+        array.add("Bob");
+
+        Iterator<String> iterator = array.iterator();
+        assertEquals("Alice", iterator.next());
+        iterator.remove();
+        assertEquals(1, array.getSize());
+        assertEquals("Bob", array.get(0));
+    }
+
+    @Test
+    public void testRemoveBeyondCapacity() {
+        DynamicArray<String> array = new DynamicArray<>(2);
+        array.add("Alice");
+        array.add("Bob");
+        array.add("Charlie");
+
+        array.remove(1);
+        assertEquals(2, array.getSize());
+        assertEquals("Alice", array.get(0));
+        assertEquals("Charlie", array.get(1));
+    }
+
+    @Test
+    public void testCapacityDoubling() {
+        DynamicArray<String> array = new DynamicArray<>(1);
+        array.add("Alice");
+        array.add("Bob");
+        array.add("Charlie"); // Ensure capacity expansion is working
+
+        assertEquals(3, array.getSize());
+        assertEquals("Charlie", array.get(2));
+    }
+}