Shrink method in array stack (scala)-CodePudding

I am trying to implement a resize function that shrinks and grows an array stack depending on its number of elements and the array's size in Scala3. Here is my code below:

package adt

import scala.reflect.ClassTag

class ArrayStack[A: ClassTag]:

  private var dataArray: Array[A] = Array.fill(10)(null.asInstanceOf[A])
  private var top: Int = 0
  private var sz: Int = 10

  def push(elem: A): Unit =
    if top == sz then resize(grow = true)
    dataArray(top) = elem
    top  = 1

  def pop(): A =
    if top == (sz / 2) - 1 then resize(grow = false)
    top -= 1
    dataArray(top)

  def peek(): A =
    dataArray(top - 1)

  def isEmpty(): Boolean =
    top == 0

  def resize(grow: Boolean): Unit =
    val newSize = if grow then sz * 2 else sz / 2
    val newArray: Array[A] = Array.fill(newSize)(null.asInstanceOf[A])
    for (a <- 0 until dataArray.length) do newArray(a) = dataArray(a)
    dataArray = newArray
    sz = newSize

However, in my JUnit tests, I get an array index out of bounds exception.

  @Test def pushMultiple(): Unit =
    val stack = new ArrayStack[Int]
    val pushArr = Array.tabulate(100)(i => Math.round(i * 100))
    pushArr.foreach(stack.push(_))
    for (n <- pushArr.reverse) do assertEquals(n, stack.pop())

  @Test def popMultiple(): Unit =
    val stack = new ArrayStack[Int]
    val pushArr = Array.tabulate(100)(i => Math.round(i * 100))
    pushArr.foreach(stack.push(_))
    for (i <- 1 to 1000) do stack.pop()
    assertTrue(stack.isEmpty())

Error message:

    Test arraystack_test.pushMultiple failed: java.lang.ArrayIndexOutOfBoundsException: Index 80 out of bounds for length 80, took 0.032 sec
    at scala.runtime.ScalaRunTime$.array_update(ScalaRunTime.scala:75)
ScalaRunTime.scala:75
    at adt.ArrayStack.resize$$anonfun$1(ArrayStack.scala:30)
ArrayStack.scala:30
    at scala.runtime.java8.JFunction1$mcVI$sp.apply(JFunction1$mcVI$sp.scala:18)
    at scala.collection.immutable.Range.foreach(Range.scala:190)
Range.scala:190
    at adt.ArrayStack.resize(ArrayStack.scala:30)
ArrayStack.scala:30
    at adt.ArrayStack.pop(ArrayStack.scala:17)
ArrayStack.scala:17
    at arraystack_test.pushMultiple$$anonfun$2(arraystack_test.scala:26)
    at scala.runtime.java8.JFunction1$mcVI$sp.apply(JFunction1$mcVI$sp.scala:18)
    at scala.collection.ArrayOps$.foreach$extension(ArrayOps.scala:1324)
ArrayOps.scala:1324
    at arraystack_test.pushMultiple(arraystack_test.scala:26)
    at jdk.internal.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
NativeMethodAccessorImpl.java:34
    at jdk.internal.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:62)
NativeMethodAccessorImpl.java:62
    at jdk.internal.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
DelegatingMethodAccessorImpl.java:43
    at java.lang.reflect.Method.invoke(Method.java:566)
Method.java:566
    ...
Test arraystack_test.popMultiple failed: java.lang.ArrayIndexOutOfBoundsException: Index 80 out of bounds for length 80, took 0.0 sec
    at scala.runtime.ScalaRunTime$.array_update(ScalaRunTime.scala:75)
ScalaRunTime.scala:75
    at adt.ArrayStack.resize$$anonfun$1(ArrayStack.scala:30)
ArrayStack.scala:30
    at scala.runtime.java8.JFunction1$mcVI$sp.apply(JFunction1$mcVI$sp.scala:18)
    at scala.collection.immutable.Range.foreach(Range.scala:190)
Range.scala:190
    at adt.ArrayStack.resize(ArrayStack.scala:30)
ArrayStack.scala:30
    at adt.ArrayStack.pop(ArrayStack.scala:17)
ArrayStack.scala:17
    at arraystack_test.popMultiple$$anonfun$2(arraystack_test.scala:32)
    at scala.runtime.java8.JFunction1$mcII$sp.apply(JFunction1$mcII$sp.scala:17)
    at scala.collection.immutable.Range.foreach(Range.scala:190)
Range.scala:190
    at arraystack_test.popMultiple(arraystack_test.scala:32)
    at jdk.internal.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
NativeMethodAccessorImpl.java:34
    at jdk.internal.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:62)
NativeMethodAccessorImpl.java:62
    at jdk.internal.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
DelegatingMethodAccessorImpl.java:43
    at java.lang.reflect.Method.invoke(Method.java:566)

Can anyone please help me figure out why my resize shrink function does not work?

CodePudding user response：

Nevermind, I figured it out.

In the resize method, this causes an index out of bounds exception

    for (a <- 0 until dataArray.length) do newArray(a) = dataArray(a)

When the method is called for grow, it works fine. But, when the method is called for shrink, newArray has a length that is half of dataArray, so it will cause an index out of bounds exception.

To fix this:

  def resize(grow: Boolean): Unit =
    val newSize = if grow then sz * 2 else sz / 2
    val endRange: Int = if grow then dataArray.length else newSize
    val newArray: Array[A] = Array.fill(newSize)(null.asInstanceOf[A])
    for (a <- 0 until endRange) do newArray(a) = dataArray(a)
    dataArray = newArray
    sz = newSize