Buffer

Buffer.scala

import scala.reflect.ClassTag

/** Mutable, indexed buffer abstraction.
  *
  * @groupprio Abstract 0
  * @groupprio Properties 1
  * @groupprio Update 2
  * @groupprio Append 3
  * @groupprio Insert 4
  * @groupprio Shift 5
  * @groupprio Stack Ops 6
  * @groupprio Limit 7
  */
trait Buffer[T] extends (Int => T) {

  /** Index of the last accessible value in the buffer, or -1 if empty. */
  private var topIndex: Int = -1

  /** Returns value at the provided index.
    * @group Abstract */
  def apply(index: Int): T

  /** Updates value at the provided index.
    * @throws IndexOutOfBoundsException if index lower than zero.
    * @group Abstract */
  def update(index: Int, value: T): this.type

  /** Ensures buffer capacity to address provided index.
    * @group Abstract */
  protected def ensureIndex(index: Int): Unit

  /** Returns an Array representing accessible buffer range.
    * @group Abstract */
  def toArray: Array[T]

  /** Returns a Slice representing accessible buffer range.
    * @group Abstract */
  def toSlice: Slice[T]

  /** Updates value at the provided index using the function.
    * Index must fall within range [0,length).
    * @throws IndexOutOfBoundsException if index lower than zero.
    * @group Update */
  def modify(index: Int, f: T => T): this.type = {
    if (index >= 0 && index < length) {
      update(index, f(apply(index)))
      topIndex = Math.max(index, topIndex)
    }
    this
  }

  /** Updates values in the range [startIndex,toIndex)^^[0,length) using the function.
    * One of {startIndex,toIndex} must fall within range [0,length).
    * @throws IndexOutOfBoundsException if index lower than zero.
    * @group Update */
  def modifyRange(fromIndex: Int, toIndex: Int, f: T => T): this.type = {
    if (toIndex > 0 && fromIndex < length) {
      var i = Math.max(0, fromIndex)
      val limit = Math.min(length, toIndex)
      while (i < limit) {
        update(i, f(apply(i)))
        i = i + 1
      }
      topIndex = Math.max(topIndex, i - 1)

    }
    this
  }

  /** Length of the accessible part of the buffer.
    * @group Properties */
  final def length: Int = topIndex + 1

  /** Is the accessible part of the buffer empty?
    * @group Properties */
  @`inline` final def isEmpty: Boolean = length == 0

  /** Is the accessible part of the buffer non empty?
    * @group Properties */
  @`inline` final def nonEmpty: Boolean = length > 0

  /** Sets topIndex value.
    * @group Limit */
  final def set(index: Int): this.type = {
    ensureIndex(index)
    topIndex = Math.max(-1, index)
    this
  }

  /** Returns topIndex value.
    * @group Limit */
  final def top: Int = topIndex

  /** Resets buffer, sets topIndex to -1.
    * Does not clear existing values.
    * @return previous topIndex
    * @group Limit */
  final def reset: Int = {
    val i = topIndex
    topIndex = -1
    i
  }

  /** Appends value at the end of buffer and advances topIndex.
    * @group Append */
  @`inline` final def append(value: T): this.type = {
    update(length, value)
    this
  }

  /** Appends values from the given array at the end of buffer and advances topIndex.
    * @group Append */
  @`inline` final def appendArray(values: Array[T]): this.type =
    insertArray(length, 0, values.length, values)

  /** Appends values from the given sequence at the end of buffer and advances topIndex.
    * @group Append */
  @`inline` final def appendSequence(values: IndexedSeq[T]): this.type =
    insertValues(length, 0, values.length, values)

  /** Appends values from the given iterator at the end of buffer and advances topIndex.
    * @group Append */
  final def appendFromIterator(iterator: Iterator[T]): this.type = {
    while (iterator.hasNext) {
      append(iterator.next())
    }
    this
  }

  /** Appends values from the given iterable at the end of buffer and advances topIndex.
    * @group Append */
  @`inline` final def appendIterable(iterable: Iterable[T]): this.type = appendFromIterator(iterable.iterator)

  /** Shift current content to the right starting from `index`at the `insertLength` distance,
    * and copies array chunk into the gap.
    * Sets topIndex to be at least at the end of the new chunk of values.
    * @group Insert */
  def insertArray(index: Int, sourceIndex: Int, insertLength: Int, sourceArray: Array[T]): this.type

  /** Shift current content to the right starting from `index`at the `insertLength` distance,
    * iterates over the source indexes and copies values into the gap.
    * Sets topIndex to be at least at the end of the new chunk of values.
    * @group Insert */
  final def insertValues(index: Int, sourceIndex: Int, insertLength: Int, source: Int => T): this.type = {
    if (index >= 0 && sourceIndex >= 0) {
      if (insertLength > 0) {
        shiftRight(index, insertLength)
        var i = 0
        while (i < insertLength) {
          update(index + i, source(sourceIndex + i))
          i = i + 1
        }
      }
      topIndex = Math.max(topIndex, index + insertLength - 1)
    }
    this
  }

  /** Shift current content to the right starting from `index`at the `insertLength` distance,
    * and copies iterated values into the gap.
    * Sets topIndex to be at least at the end of the new chunk of values.
    * @group Insert */
  final def insertFromIterator(index: Int, insertLength: Int, iterator: Iterator[T]): this.type = {
    if (index >= 0) {
      if (insertLength > 0) {
        shiftRight(index, insertLength)
        var i = 0
        while (i < insertLength && iterator.hasNext) {
          update(index + i, iterator.next())
          i = i + 1
        }
      }
      topIndex = Math.max(topIndex, index + insertLength - 1)
    }
    this
  }

  /** Moves values [index, length) right to [index+distance, length + distance).
    * Effectively creates a new range [index, index+distance).
    * Ignores negative distance.
    * Does not clear existing values inside [index, index+distance).
    * Moves topIndex if affected.
    * @group Shift */
  def shiftRight(index: Int, distance: Int): this.type

  /** Moves values [index, length) left to [index-distance, length - distance).
    * Effectively removes range (index-distance, index].
    * Ignores negative distance.
    * Moves topIndex if affected.
    * @group Shift */
  def shiftLeft(index: Int, distance: Int): this.type

  /** Replace value at the topIndex.
    * @group Stack Ops */
  final def store(value: T): this.type = {
    if (topIndex < 0) topIndex = 0
    update(topIndex, value)
    this
  }

  /** Appends value to the topIndex.
    * Same as [[append]]
    * @group Stack Ops */
  @`inline` final def push(value: T): this.type = {
    update(length, value)
    this
  }

  /** Returns value at the topIndex.
    * @group Stack Ops */
  final def peek: T = apply(topIndex)

  /** Returns value at the topIndex, and moves topIndex back.
    * @group Stack Ops */
  final def pop: T = {
    val value = peek
    topIndex = topIndex - 1
    value
  }

}

/** Buffer factory. */
object Buffer {

  def apply[T: ClassTag](elems: T*): ArrayBuffer[T] = new ArrayBuffer[T](elems.toArray)

  def apply[T: ClassTag](array: Array[T]): ArrayBuffer[T] = new ArrayBuffer[T](array)

  def ofSize[T: ClassTag](size: Int): ArrayBuffer[T] = new ArrayBuffer[T](new Array[T](size))

  def empty[T: ClassTag] = new ArrayBuffer[T](Array.empty[T])

}

BufferSpec.scala

import com.github.arturopala.tree.util.ArrayBuffer
import org.scalatest.matchers.should.Matchers
import org.scalatest.wordspec.AnyWordSpec

class ArrayBufferSpec extends AnyWordSpec with Matchers {

  "Buffer" should {
    "access and update a value at an index" in {
      val buffer = new ArrayBuffer(Array("a", "b", "c"))
      buffer(0) shouldBe "a"
      buffer(1) shouldBe "b"
      buffer(2) shouldBe "c"
      buffer(0) = "aa"
      buffer(0) shouldBe "aa"
      buffer(1) shouldBe "b"
      buffer(2) shouldBe "c"
      buffer.length shouldBe 3
      buffer(111) = "foo"
      buffer(111) shouldBe "foo"
      buffer.length shouldBe 112
      buffer(9999) = "bar"
      buffer(9999) shouldBe "bar"
      buffer.length shouldBe 10000
    }

    "append value" in {
      val buffer = new ArrayBuffer(Array("a", "b", "c"))
      buffer(0) shouldBe "a"
      buffer(1) shouldBe "b"
      buffer(2) shouldBe "c"
      an[IndexOutOfBoundsException] shouldBe thrownBy(buffer(100))
      buffer.length shouldBe 3
      buffer.append("d").append("e").append("f")
      buffer(0) shouldBe "a"
      buffer(1) shouldBe "b"
      buffer(2) shouldBe "c"
      buffer(3) shouldBe "d"
      buffer(4) shouldBe "e"
      buffer(5) shouldBe "f"
      buffer.length shouldBe 6
      buffer.append("aa").append("aaa").append("aaaa")
      buffer(0) shouldBe "a"
      buffer(1) shouldBe "b"
      buffer(2) shouldBe "c"
      buffer(3) shouldBe "d"
      buffer(4) shouldBe "e"
      buffer(5) shouldBe "f"
      buffer(6) shouldBe "aa"
      buffer(7) shouldBe "aaa"
      buffer(8) shouldBe "aaaa"
      buffer.length shouldBe 9
      buffer(10) = "foo"
      buffer(9) shouldBe null
      buffer(10) shouldBe "foo"
      an[IndexOutOfBoundsException] shouldBe thrownBy(buffer(11))
      buffer.toArray shouldBe Array("a", "b", "c", "d", "e", "f", "aa", "aaa", "aaaa", null, "foo")
      buffer.length shouldBe 11
      buffer(1000) = "bar"
      buffer(999) shouldBe null
      buffer(1000) shouldBe "bar"
      an[IndexOutOfBoundsException] shouldBe thrownBy(buffer(1001))
      buffer.length shouldBe 1001
    }

    "shift values right" in {
      val buffer = new ArrayBuffer(Array("a", "b", "c"))
      buffer.shiftRight(1, 5)
      buffer.toArray shouldBe Array("a", "b", "c", null, null, null, "b", "c")
      buffer.length shouldBe 8
      buffer.shiftRight(7, 1)
      buffer.toArray shouldBe Array("a", "b", "c", null, null, null, "b", "c", "c")
      buffer.length shouldBe 9
      buffer.shiftRight(5, 2)
      buffer.toArray shouldBe Array("a", "b", "c", null, null, null, "b", null, "b", "c", "c")
      buffer.length shouldBe 11
      buffer.shiftRight(5, -2) // ignore negative distance
      buffer.toArray shouldBe Array("a", "b", "c", null, null, null, "b", null, "b", "c", "c")
      buffer.length shouldBe 11
      buffer.shiftRight(-5, 5) // ignore negative index
      buffer.toArray shouldBe Array("a", "b", "c", null, null, null, "b", null, "b", "c", "c")
      buffer.length shouldBe 11

      val buffer2 = new ArrayBuffer(Array.empty[String])
      buffer2.shiftRight(0, 10)
      buffer2.length shouldBe 0
    }

    "shift values left" in {
      val buffer = new ArrayBuffer(Array("a", "d", "e", "b", "c"))
      buffer.shiftLeft(2, 1)
      buffer.toArray shouldBe Array("a", "e", "b", "c")
      buffer.length shouldBe 4
      buffer.shiftLeft(2, 1)
      buffer.toArray shouldBe Array("a", "b", "c")
      buffer.length shouldBe 3
      buffer.shiftLeft(2, 2)
      buffer.toArray shouldBe Array("c")
      buffer.length shouldBe 1
      buffer.shiftLeft(0, 2)
      buffer.toArray shouldBe Array.empty[String]
      buffer.length shouldBe 0

      val buffer2 = new ArrayBuffer(Array.empty[String])
      buffer2.shiftLeft(0, 10)
      buffer2.length shouldBe 0
    }

    "insert new array of values" in {
      val buffer = new ArrayBuffer(Array.empty[String])
      buffer.insertArray(0, 0, 3, Array("a", "b", "c"))
      buffer.toArray shouldBe Array("a", "b", "c")
      buffer.length shouldBe 3
      buffer.insertArray(1, 0, 2, Array("d", "e"))
      buffer.toArray shouldBe Array("a", "d", "e", "b", "c")
      buffer.length shouldBe 5
      buffer.insertArray(0, 1, 1, Array("d", "e"))
      buffer.toArray shouldBe Array("e", "a", "d", "e", "b", "c")
      buffer.length shouldBe 6
      buffer.insertArray(0, 1, 0, Array("d", "e"))
      buffer.toArray shouldBe Array("e", "a", "d", "e", "b", "c")
      buffer.length shouldBe 6
      buffer.insertArray(5, 0, 2, Array("d", "e"))
      buffer.toArray shouldBe Array("e", "a", "d", "e", "b", "d", "e", "c")
      buffer.length shouldBe 8
      buffer.insertArray(10, 0, 5, Array("d", "e"))
      buffer.toArray shouldBe Array("e", "a", "d", "e", "b", "d", "e", "c", null, null, "d", "e")
      buffer.length shouldBe 12
      buffer.insertArray(10, 0, -5, Array("d", "e"))
      buffer.toArray shouldBe Array("e", "a", "d", "e", "b", "d", "e", "c", null, null, "d", "e")
      buffer.length shouldBe 12
    }

    "insert new values from indexed source" in {
      val buffer = new ArrayBuffer(Array.empty[String])
      buffer.insertValues(0, 0, 3, Array("a", "b", "c"))
      buffer.toArray shouldBe Array("a", "b", "c")
      buffer.length shouldBe 3
      buffer.insertValues(1, 0, 2, Array("d", "e"))
      buffer.toArray shouldBe Array("a", "d", "e", "b", "c")
      buffer.length shouldBe 5
      buffer.insertValues(0, 1, 1, Array("d", "e"))
      buffer.toArray shouldBe Array("e", "a", "d", "e", "b", "c")
      buffer.length shouldBe 6
      buffer.insertValues(0, 1, 0, Array("d", "e"))
      buffer.toArray shouldBe Array("e", "a", "d", "e", "b", "c")
      buffer.length shouldBe 6
      buffer.insertValues(5, 0, 2, Array("d", "e"))
      buffer.toArray shouldBe Array("e", "a", "d", "e", "b", "d", "e", "c")
      buffer.length shouldBe 8
      buffer.insertValues(10, 0, 2, Array("d", "e"))
      buffer.toArray shouldBe Array("e", "a", "d", "e", "b", "d", "e", "c", null, null, "d", "e")
      buffer.length shouldBe 12
      buffer.insertValues(10, 0, -5, Array("d", "e"))
      buffer.toArray shouldBe Array("e", "a", "d", "e", "b", "d", "e", "c", null, null, "d", "e")
      buffer.length shouldBe 12
    }

    "insert new values from iterator" in {
      val buffer = new ArrayBuffer(Array.empty[String])
      buffer.insertFromIterator(0, 3, Array("a", "b", "c").iterator)
      buffer.toArray shouldBe Array("a", "b", "c")
      buffer.length shouldBe 3
      buffer.insertFromIterator(1, 2, Array("d", "e").iterator)
      buffer.toArray shouldBe Array("a", "d", "e", "b", "c")
      buffer.length shouldBe 5
      buffer.insertFromIterator(0, 1, Array("e").iterator)
      buffer.toArray shouldBe Array("e", "a", "d", "e", "b", "c")
      buffer.length shouldBe 6
      buffer.insertFromIterator(0, 0, Array("e").iterator)
      buffer.toArray shouldBe Array("e", "a", "d", "e", "b", "c")
      buffer.length shouldBe 6
      buffer.insertFromIterator(5, 2, Array("d", "e").iterator)
      buffer.toArray shouldBe Array("e", "a", "d", "e", "b", "d", "e", "c")
      buffer.length shouldBe 8
      buffer.insertFromIterator(10, 2, Array("d", "e").iterator)
      buffer.toArray shouldBe Array("e", "a", "d", "e", "b", "d", "e", "c", null, null, "d", "e")
      buffer.length shouldBe 12
      buffer.insertFromIterator(10, -5, Array("d", "e").iterator)
      buffer.toArray shouldBe Array("e", "a", "d", "e", "b", "d", "e", "c", null, null, "d", "e")
      buffer.length shouldBe 12
    }

    "append an array" in {
      val buffer = new ArrayBuffer(Array.empty[String])
      buffer.appendArray(Array("a", "b", "c"))
      buffer.length shouldBe 3
      buffer.toArray shouldBe Array("a", "b", "c")
      buffer.appendArray(Array("a", "b", "c"))
      buffer.length shouldBe 6
      buffer.toArray shouldBe Array("a", "b", "c", "a", "b", "c")
      buffer.appendArray(Array("d", "e"))
      buffer.length shouldBe 8
      buffer.toArray shouldBe Array("a", "b", "c", "a", "b", "c", "d", "e")
      buffer.appendArray(Array())
      buffer.length shouldBe 8
    }

    "append sequence of values" in {
      val buffer = new ArrayBuffer(Array.empty[String])
      buffer.appendSequence(IndexedSeq("a", "b", "c"))
      buffer.length shouldBe 3
      buffer.toArray shouldBe Array("a", "b", "c")
      buffer.appendSequence(IndexedSeq("a", "b", "c"))
      buffer.length shouldBe 6
      buffer.toArray shouldBe Array("a", "b", "c", "a", "b", "c")
      buffer.appendSequence(IndexedSeq("d", "e"))
      buffer.length shouldBe 8
      buffer.toArray shouldBe Array("a", "b", "c", "a", "b", "c", "d", "e")
      buffer.appendSequence(IndexedSeq())
      buffer.length shouldBe 8
    }

    "append values from iterator" in {
      val buffer = new ArrayBuffer(Array.empty[String])
      buffer.appendFromIterator(List("a", "b", "c").iterator)
      buffer.length shouldBe 3
      buffer.toArray shouldBe Array("a", "b", "c")
      buffer.appendFromIterator(List("a", "b", "c").iterator)
      buffer.length shouldBe 6
      buffer.toArray shouldBe Array("a", "b", "c", "a", "b", "c")
      buffer.appendFromIterator(List("d", "e").iterator)
      buffer.length shouldBe 8
      buffer.toArray shouldBe Array("a", "b", "c", "a", "b", "c", "d", "e")
      buffer.appendFromIterator(List().iterator)
      buffer.length shouldBe 8
    }

    "set and reset top index" in {
      val buffer = new ArrayBuffer(Array("a", "b", "c"))
      buffer.length shouldBe 3
      buffer.set(10)
      buffer.length shouldBe 11
      buffer.set(3)
      buffer.length shouldBe 4
      buffer.set(10)
      buffer.length shouldBe 11
      buffer.set(-10)
      buffer.length shouldBe 0
      buffer.set(13)
      buffer.length shouldBe 14
      buffer.reset shouldBe 13
      buffer.length shouldBe 0
      buffer.reset shouldBe -1
      buffer.length shouldBe 0
    }

  }

}

IntBuffer.scala

/** Growable, mutable array of integers.
  * Unlike [[ArrayBuffer]] allows to address elements outside the range. */
final class IntBuffer(initialSize: Int = 8) extends ArrayBufferLike[Int] {

  override protected var array = new Array[Int](initialSize)

  /** Returns value at the given index or 0 if out of scope. */
  @`inline` def apply(index: Int): Int =
    if (index < 0 || index >= array.length) 0
    else array(index)

  override protected def ensureIndex(index: Int): Unit =
    if (index >= array.length) {
      val newArray: Array[Int] = new Array(Math.max(array.length * 2, index + 1))
      java.lang.System.arraycopy(array, 0, newArray, 0, array.length)
      array = newArray
    }

  /** Increments the value at index.s */
  def increment(index: Int): this.type = {
    update(index, apply(index) + 1)
    this
  }

  /** Returns copy of the underlying array trimmed to length. */
  def toArray: Array[Int] = java.util.Arrays.copyOf(array, length)

  /** Wraps underlying array as a Slice. */
  def toSlice: IntSlice = IntSlice.of(array, 0, length)

  /** Copy values directly from IntSlice's array into the buffer array. */
  def copyFrom(index: Int, slice: IntSlice): Unit = {
    ensureIndex(index + slice.length - 1)
    java.lang.System.arraycopy(slice.array, slice.fromIndex, array, index, slice.length)
  }

}

/** IntBuffer factory. */
object IntBuffer {

  /** Create buffer with initial values. */
  def apply(elems: Int*): IntBuffer = new IntBuffer(elems.size).appendArray(elems.toArray)

  /** Create buffer from an array copy. */
  def apply(array: Array[Int]): IntBuffer = new IntBuffer(array.length).appendArray(array)

  /** An empty buffer. */
  def empty = new IntBuffer(0)
}

IntBufferSpec.scala

import com.github.arturopala.tree.util.IntBuffer
import org.scalatest.matchers.should.Matchers
import org.scalatest.wordspec.AnyWordSpec

class IntBufferSpec extends AnyWordSpec with Matchers {

  "IntBuffer" should {
    "access and update a value at an index" in {
      val buffer = new IntBuffer()
      buffer(0) shouldBe 0
      buffer.length shouldBe 0
      buffer(1000) shouldBe 0
      buffer.length shouldBe 0
      buffer(0) = 3
      buffer(0) shouldBe 3
      buffer.length shouldBe 1
      buffer(111) = 13
      buffer(111) shouldBe 13
      buffer.length shouldBe 112
      buffer(9999) = -13
      buffer(9999) shouldBe -13
      buffer.length shouldBe 10000
    }

    "append values" in {
      val buffer = new IntBuffer()
      buffer.append(13).append(7).append(16)
      buffer(0) shouldBe 13
      buffer(1) shouldBe 7
      buffer(2) shouldBe 16
      buffer.append(9).append(90).append(900)
      buffer(3) shouldBe 9
      buffer(4) shouldBe 90
      buffer(5) shouldBe 900
      buffer(10) = 1000
      buffer(5) shouldBe 900
      buffer(6) shouldBe 0
      buffer(7) shouldBe 0
      buffer(8) shouldBe 0
      buffer(9) shouldBe 0
      buffer(10) shouldBe 1000
      buffer(11) shouldBe 0
      buffer(12) shouldBe 0
      buffer(13) shouldBe 0
      buffer(14) shouldBe 0
      buffer.append(1).append(2).append(3)
      buffer(11) shouldBe 1
      buffer(12) shouldBe 2
      buffer(13) shouldBe 3
      buffer(14) shouldBe 0
      buffer.toArray shouldBe Array(13, 7, 16, 9, 90, 900, 0, 0, 0, 0, 1000, 1, 2, 3)
      buffer.length shouldBe 14
      buffer(1000) = -13
      buffer(1000) shouldBe -13
      buffer.length shouldBe 1001
    }

    "modify value at an index" in {
      val buffer = IntBuffer(0, 1, 2, 3, 4, 5, 6, 7, 8, 9)
      buffer.modify(0, _ + 10).toArray shouldBe Array(10, 1, 2, 3, 4, 5, 6, 7, 8, 9)
      buffer.modify(1, _ + 1).toArray shouldBe Array(10, 2, 2, 3, 4, 5, 6, 7, 8, 9)
      buffer.modify(1, _ + 1).toArray shouldBe Array(10, 3, 2, 3, 4, 5, 6, 7, 8, 9)
      buffer.modify(2, _ - 1).toArray shouldBe Array(10, 3, 1, 3, 4, 5, 6, 7, 8, 9)
      buffer.modify(1, _ - 1).toArray shouldBe Array(10, 2, 1, 3, 4, 5, 6, 7, 8, 9)
    }

    "modify values in the range" in {
      val buffer = IntBuffer(0, 1, 2, 3, 4, 5, 6, 7, 8, 9)
      buffer.modifyRange(0, 2, _ + 10).toArray shouldBe Array(10, 11, 2, 3, 4, 5, 6, 7, 8, 9)
      buffer.modifyRange(1, 5, _ + 1).toArray shouldBe Array(10, 12, 3, 4, 5, 5, 6, 7, 8, 9)
      buffer.modifyRange(2, 9, _ + 1).toArray shouldBe Array(10, 12, 4, 5, 6, 6, 7, 8, 9, 9)
      buffer.modifyRange(2, 1, _ - 1).toArray shouldBe Array(10, 12, 4, 5, 6, 6, 7, 8, 9, 9)
      buffer.modifyRange(0, 1, _ - 1).toArray shouldBe Array(9, 12, 4, 5, 6, 6, 7, 8, 9, 9)

      IntBuffer(0, 1).modifyRange(2, 5, _ + 1).toArray shouldBe Array(0, 1)
      IntBuffer(0, 1).modifyRange(0, 0, _ + 1).toArray shouldBe Array(0, 1)
    }
  }

}