Buffer[T] and Slice[T]

This is a micro-library for Scala providing lightweight Buffer and Slice abstractions.

"com.github.arturopala" %% "buffer-and-slice" % "1.63.0"

Cross-compiles to Scala versions 2.13.12, 2.12.18, 3.3.1, and ScalaJS version 1.14.0, and ScalaNative version 0.4.15.

Motivation

Working directly with mutable arrays, even in Scala, is not always as simple and efficient as it could be. While Array features Scala Collections API, the first reason to use arrays is to fully exploit its compactness and mutability for performance reasons. I've found it reasonable to have a separate, focused set of low-overhead tools dealing with an Array.

Another concern was a proliferation of ClassTag context parameter, making it hard to offer Array-based variants of a generic data-structures. This API requires now ClassTag only for explicit .toArray[T1 >: T] call, nowhere else.

Why at all using arrays in the era of functional programming?

Arrays are the most primitive but very efficient data structures, with fast access time, compact representation, unbeatable copy performance and taking advantage of the CPU cache line.

The FP solution is to exploit arrays but avoid sharing its mutable state around. This is where the Buffer and the Slice concept fits in.

Design

This library provides two complementary abstractions, two sides of the coin: mutable Buffer and immutable lazy Slice.

A Buffer role is to help easily build a growable array using mixed buffer- and stack- like APIs.
A Slice role is to share an immutable slice of the array.

The usual workflow will use Buffer to build an array and Slice to share the result outside of a component/function.

Both Buffer and Slice come in variants:

generic ArrayBuffer[T] and ArraySlice[T],
specialized IntBuffer and IntSlice with additional numeric API,
specialized ByteBuffer and ByteSlice.
LazyMapArraySlice provides very light mapping operation on Slice without forcing underlying array copy.
RangeMapSlice provides a slice of function of integers.
DeferredArrayBuffer[T] makes it possible to defer underlying array type decision for abstract types.

Dependencies

Depends only on a standard built-in Scala library.

API

Buffer offers comprehensive API, together with Stack- and List- like interfaces.

For the purpose of using as a mutable List, the top element is a head.

For more details, see:

Performance

The principle of this library is to avoid creating intermediary arrays as much as possible, and use native java.lang.System.arraycopy and java.util.Arrays.copyOf where applicable.

Lightweight operations:

creating new Buffer or Slice from an array
slicing (asSlice, slice, take, drop, takeRight, dropRight)
mapping the slice
using iterators or toIterable
making Slice.copyToArray
subsequent detaching

Heavier operations, making a copy of an array:

detaching a slice first-time, if not detached already
updating a slice
making a copy of a buffer
exporting slice or buffer (toArray, toList, toBuffer)

E.g. the following code makes no copy of an array a:

import com.github.arturopala.bufferandslice._

val a = Array.fill(1000)(1)
val buffer = Buffer(a,100)
val slice1 = buffer.slice(13,31).map(_ * 2)
buffer.insertSlice(23, slice1.map(_ * 3))
buffer.replaceFromSlice(87, slice1.drop(7))
val slice2 = buffer.slice(17,71)
slice2.map(_+10).iterator.mkString("[",",","]")
buffer.appendSlice(slice2)

Index tracking

Buffer manipulations, like shift.., move.., or swap.. can change the buffer layout in a complex way.

An IndexTracker object provides set of functions to keep your external index buffer or list in sync with those changes.

Examples

Buffer

Open in Scastie

import com.github.arturopala.bufferandslice._

Buffer.empty[String]
// res4: Buffer[String] = []

Buffer.empty[Double]
// res5: Buffer[Double] = []

Buffer.empty[Int]
// res6: Buffer[Int] = []

Buffer.empty[Byte]
// res7: Buffer[Byte] = []

Buffer("a","b","c")
// res8: Buffer[String] = [a,b,c]

Buffer(Array("a","b","c"))
// res9: Buffer[String] = [a,b,c]

Buffer(1,2,3).apply(1)
// res10: Int = 2

Buffer(1,2,3).get(2)
// res11: Option[Int] = Some(value = 3)

Buffer("a","b","c").head
// res12: String = "c"

Buffer("a","b","c").last
// res13: String = "a"

Buffer("a","b","c").tail
// res14: Buffer[String] = [a,b]

Buffer("a","b","c").init
// res15: Buffer[String] = [b,c]

Buffer(1,2,3,4,5,6,7,8,9).asSlice
// res16: Slice[Int] = Slice(1,2,3,4,5,6,7,8,9)

Buffer(1,2,3,4,5,6,7,8,9).toArray
// res17: Array[Int] = Array(1, 2, 3, 4, 5, 6, 7, 8, 9)

Buffer(1d,2d,3d,4d,5d,6d,7d,8d,9d).asArray
// res18: Array[Double] = Array(1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0)

val b1 = ByteBuffer(1,2)
// b1: ByteBuffer = [1,2]

b1.copy.append(3)
// res19: ByteBuffer = [1,2,3]

b1.copy.append(4)
// res20: ByteBuffer = [1,2,4]

b1.emptyCopy.append(9)
// res21: ByteBuffer = [9]

Specialized IntBuffer:

IntBuffer(0,1,2,3)
// res22: IntBuffer = [0,1,2,3]

IntBuffer(Array(0,1,2,3))
// res23: IntBuffer = [0,1,2,3]

IntBuffer(0,1,2,3).asSlice
// res24: IntSlice = Slice(0,1,2,3)

Specialized ByteBuffer:

ByteBuffer(0,1,2,3)
// res25: ByteBuffer = [0,1,2,3]

ByteBuffer(Array(0,1,2,3).map(_.toByte))
// res26: ByteBuffer = [0,1,2,3]

ByteBuffer(0,1,2,3).asSlice
// res27: ByteSlice = Slice(0,1,2,3)

Modifying the content:

ByteBuffer(1,2,3).update(1,0)
// res28: ByteBuffer = [1,0,3]

Buffer(0,0,0).modify(1,_ + 1)
// res29: Buffer[Int] = [0,1,0]

Buffer("c").append("a")
// res30: Buffer[String] = [c,a]

Buffer("x","y","z").insert(1,"a")
// res31: Buffer[String] = [x,a,y,z]

Buffer("a","b","c").remove(1)
// res32: Buffer[String] = [a,c]

IntBuffer(0,1,1).appendSlice(Slice(0,1,2,3))
// res33: IntBuffer = [0,1,1,0,1,2,3]

IntBuffer(0,1,1).appendArray(Array(0,1,2,3))
// res34: IntBuffer = [0,1,1,0,1,2,3]

Buffer("a").appendSequence(IndexedSeq("a","a","a"))
// res35: Buffer[String] = [a,a,a,a]

Buffer(0).appendIterable(1 to 10)
// res36: Buffer[Int] = [0,1,2,3,4,5,6,7,8,9,10]

Buffer("b").appendFromIterator(Iterator.fill(10)("a"))
// res37: Buffer[String] = [b,a,a,a,a,a,a,a,a,a,a]

Buffer("b").appendFromIterator(3, Iterator.fill(10)("a"))
// res38: Buffer[String] = [b,a,a,a]

Buffer(0,0,0).insertValues(1,2,3,List(0,1,2,3,4,5))
// res39: Buffer[Int] = [0,2,3,4,0,0]

Buffer(0,0,0).insertFromIterator(2, 3, (1 to 7).iterator)
// res40: Buffer[Int] = [0,0,1,2,3,0]

Buffer(0,0,0).insertFromIterator(2, (1 to 7).iterator)
// res41: Buffer[Int] = [0,0,1,2,3,4,5,6,7,0]

Buffer(0,0,0).insertFromIteratorReverse(1, 5, (1 to 7).iterator)
// res42: Buffer[Int] = [0,5,4,3,2,1,0,0]

Buffer(0,0,0).insertFromIteratorReverse(1, (1 to 7).iterator)
// res43: Buffer[Int] = [0,7,6,5,4,3,2,1,0,0]

Buffer("a","b","c").insertSlice(1, Slice("e","f"))
// res44: Buffer[String] = [a,e,f,b,c]

Buffer(0,0,0).insertArray(1,2,3,Array(0,1,2,3,4,5))
// res45: Buffer[Int] = [0,2,3,4,0,0]

Buffer("a","b","c","d","e","f").replaceFromSlice(4,Slice("a","b","c"))
// res46: Buffer[String] = [a,b,c,d,a,b,c]

Buffer(0,0,0).replaceValues(1,2,3,List(0,1,2,3,4,5))
// res47: Buffer[Int] = [0,2,3,4]

Buffer(0,0,0).replaceFromIterator(2,3, (1 to 7).iterator)
// res48: Buffer[Int] = [0,0,1,2,3]

Buffer(0,0,0,0,0,0,0).replaceFromIteratorReverse(5,3, (1 to 7).iterator)
// res49: Buffer[Int] = [0,0,0,0,0,3,2,1]

Buffer(0,0,0).replaceFromArray(1,2,3,Array(0,1,2,3,4,5))
// res50: Buffer[Int] = [0,2,3,4]

Buffer("a","b","c","d","e").removeRange(1,4)
// res51: Buffer[String] = [a,e]

Buffer(1,2,3,5,6).mapInPlace(_ * 2)
// res52: Buffer[Int] = [2,4,6,10,12]

Buffer(1,2,3,5,6).modifyAll(_ + 1)
// res53: Buffer[Int] = [2,3,4,6,7]

Buffer(1,2,3,5,6).modifyAllWhen(_ + 1, _ % 2 == 0)
// res54: Buffer[Int] = [1,3,3,5,7]

Buffer(0,0,0,0,0).modifyRange(1, 3, _ + 1)
// res55: Buffer[Int] = [0,1,1,0,0]

Buffer(1,2,3,4,5).modifyRangeWhen(1, 3, _ + 1, _ % 2 != 0)
// res56: Buffer[Int] = [1,2,4,4,5]

IntBuffer(1,2,3,4,5,6,7,8,9).shiftLeft(5,3)
// res57: IntBuffer = [1,2,6,7,8,9]

Buffer(1,2,3,4,5,6,7,8,9).shiftRight(5,3)
// res58: Buffer[Int] = [1,2,3,4,5,6,7,8,6,7,8,9]

Buffer(1,2,3,4,5,6,7,8,9).moveRangeRight(1,4,3)
// res59: Buffer[Int] = [1,5,6,7,2,3,4,8,9]

Buffer(1,2,3,4,5,6,7,8,9).moveRangeLeft(6,8,4)
// res60: Buffer[Int] = [1,2,7,8,3,4,5,6,9]

Buffer(1,2,3,4).swap(0,3)
// res61: Buffer[Int] = [4,2,3,1]

Buffer(1,2,3,4,5,6,7,8,9).swapRange(0,5,3)
// res62: Buffer[Int] = [6,7,8,4,5,1,2,3,9]

Buffer(1,2,3,4,5,6,7,8,9).contains(7)
// res63: Boolean = true

Buffer(1,2,3,4,5,6,7,8,9).exists(_ > 8)
// res64: Boolean = true

Buffer(1,2,3,4,5,6,7,8,9).exists(_ < 0)
// res65: Boolean = false

Using Buffer as a stack:

Buffer(1,2,3).peek
// res66: Int = 3

Buffer(1,2,3).peek(1)
// res67: Int = 2

Buffer(1,2,3).peekOption(2)
// res68: Option[Int] = Some(value = 1)

Buffer(1,2,3).peekOption(3)
// res69: Option[Int] = None

Buffer(1,2,3).pop
// res70: Int = 3

Buffer(1,2,3).push(1).push(1).push(0)
// res71: Buffer[Int] = [1,2,3,1,1,0]

Manipulating topIndex limit:

Buffer(1,2,3).top
// res72: Int = 2

Buffer(1,2,3).set(1)
// res73: Buffer[Int] = [1,2]

Buffer(1,2,3).forward(3)
// res74: Buffer[Int] = [1,2,3,0,0,0]

Buffer(1,2,3).rewind(2)
// res75: Buffer[Int] = [1]

Buffer(1,2,3).reset
// res76: Int = 2

Making a Slice of a Buffer:

Buffer(1,2,3,4,5,6,7,8,9).asSlice
// res77: Slice[Int] = Slice(1,2,3,4,5,6,7,8,9)

Buffer(1,2,3,4,5,6,7,8,9).slice(2,6)
// res78: Slice[Int] = Slice(3,4,5,6)

Buffer("a","c","e").asSlice
// res79: Slice[String] = Slice(a,c,e)

Buffer("a","c","e","d","b").slice(2,6)
// res80: Slice[String] = Slice(e,d,b)

Accessing buffer content

Buffer("a","c","e").toArray
// res81: Array[String] = Array("a", "c", "e")

Buffer("a","c","e").asSlice.toList
// res82: List[String] = List("a", "c", "e")

Buffer(1,2,3,4,5,6,7,8,9).iterator
// res83: Iterator[Int] = non-empty iterator

Buffer(1,2,3,4,5,6,7,8,9).reverseIterator
// res84: Iterator[Int] = non-empty iterator

val s = "abscdefghijklmnopqrstuvxyz"
// s: String = "abscdefghijklmnopqrstuvxyz"

Buffer(1,2,3,4,5,6,7,8,9).map(s.apply).toList
// res85: List[Char] = List('b', 's', 'c', 'd', 'e', 'f', 'g', 'h', 'i')

Slice