ArrayQueue.scala

import cats.Id

import scala.annotation.tailrec
import scala.reflect.ClassTag

trait Module[ST[_, _]] {
  protected def captureEffect[S, A](a: => A): ST[S, A]

  final class STArrayQueue[S, T] private (
   private var data: Array[T],
   private var front: Int = 0,
   private var rear: Int = -1,
   private var count: Int = 0)
  (implicit T: ClassTag[T]) {

    @inline private[this] def capacity: Int = data.length
    @inline private[this] def next(i: Int) =
      (i + 1) % capacity
    @inline private[this] def prev(i: Int) =
      (i - 1 + capacity) % capacity

    private[this] def doubleCapacity(): Unit = {
      val newCapacity = if (capacity != 0) capacity * 2 else 10
      val newData = Array.ofDim[T](newCapacity)
      @tailrec def go(i: Int, j: Int): Unit = if (i < count) {
        newData.update(i, data(j))
        go(i + 1, (j + 1) % capacity)
      } else ()
      go(0, front)

      data = newData
      front = 0
      rear = count - 1
    }

    def head: ST[S, Option[T]] = captureEffect {
      if (count == 0) None
      else Some(data(front))
    }

    def last: ST[S, Option[T]] = captureEffect {
      if (count == 0) None
      else Some(data(rear))
    }

    def prepend(item: T): ST[S, Unit] = captureEffect {
      if (count == capacity)
        doubleCapacity()

      count += 1
      front = prev(front)
      data(front) = item
    }

    def append(item: T): ST[S, Unit] = captureEffect {
      if (count == capacity)
        doubleCapacity()

      count += 1
      rear = next(rear)
      data(rear) = item
    }

    def popFront: ST[S, Option[T]] = captureEffect {
      if (count == 0) None
      else {
        val result = data(front)
        front = next(front)
        count -= 1
        Some(result)
      }
    }
    def popBack: ST[S, Option[T]] = captureEffect {
      if (count == 0) None
      else {
        val result = data(rear)
        rear = prev(rear)
        count -= 1
        Some(result)
      }
    }

    def size: ST[S, Int] = captureEffect { count }
    def isEmpty: ST[S, Boolean] = captureEffect { count == 0 }
    def nonEmpty: ST[S, Boolean] = captureEffect { count > 0 }
  }

  trait STArrayQueue {
    protected def empty[S, T](implicit T: ClassTag[T]): ST[S, STArrayQueue[S, T]] = captureEffect {
      new STArrayQueue[S, T](Array.ofDim(10), 0, -1, 0)
    }
    protected def unsafeFromArray[S, T](array: Array[T])(implicit T: ClassTag[T]): ST[S, STArrayQueue[S, T]] = captureEffect {
      new STArrayQueue[S, T](array, 0, array.length - 1, array.length)(T)
    }
  }
}

object id0 {
  type IdST[S, A] = Id[A]
}

object id extends Module[id0.IdST] {
  override def capture[S, A](a: => A): Id[A] = a
  
  type ArrayQueue[A] = STArrayQueue[Unit, A]

  object ArrayQueue extends STArrayQueue { self: STArrayQueue =>
    def empty[T](implicit T: ClassTag[T]): ArrayQueue[T] =
      self.empty
    def unsafeFromArray[T](array: Array[T])(implicit T: ClassTag[T]): ArrayQueue[T] =
      self.unsafeFromArray(array)
  }
}

object test {
  val i: Int = id.ArrayQueue.empty.size
}