You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
We can make make an isolated change to the way we use the internal array (making it a ring-buffer) to get the following performance:
constant-time: append, get, update, prepend, trimStart, trimRight, clear
linear-time: remove (removing x items from start or end is also constant-time)
This is strictly better than the current implementation and the change required is minimal.
Here is a proof of concept implementation:
importscala.collection.mutableimportscala.reflect.ClassTag/** * A data structure that provides O(1) get, update, length, append, prepend, clear, trimStart and trimRight * @tparamA*/classCircularBuffer[A:ClassTag](initialSize: Int=1<<4) extends mutable.Buffer[A] {
privatevararray=Array.ofDim[A](initialSize)
privatevarstart, end=0overridedefapply(idx: Int) = {
checkIndex(idx)
array(mod(start + idx))
}
overridedefupdate(idx: Int, elem: A) = {
checkIndex(idx)
array(mod(start + idx)) = elem
}
overridedeflength= mod(mod(end) - mod(start))
overridedef+=(elem: A) = {
ensureCapacity()
array(mod(end)) = elem
end +=1this
}
overridedefclear() = start = end
overridedef+=:(elem: A) = {
ensureCapacity()
start -=1
array(mod(start)) = elem
this
}
overridedefprependAll(xs: TraversableOnce[A]) =
xs.toSeq.reverse.foreach(x => x +=:this)
overridedefinsertAll(idx: Int, elems: Traversable[A]) = {
checkIndex(idx)
if (idx ==0) {
prependAll(elems)
} else {
valshift= (idx until size).map(this)
end = start + idx
this++= elems ++= shift
}
}
overridedefremove(idx: Int) = {
valelem=this(idx)
remove(idx, 1)
elem
}
overridedefremove(idx: Int, count: Int) = {
checkIndex(idx)
if (idx + count >= size) {
end = start + idx
} elseif (count >0) {
if (idx ==0) {
start += count
} else {
((idx + count) until size).foreach(i =>this(i - count) =this(i))
end -= count
}
}
}
/** * Trims the capacity of this CircularBuffer's instance to be the current size*/deftrimToSize():Unit= resizeTo(size)
overridedefiterator= indices.iterator.map(apply)
overridedeftrimStart(n: Int) =if (n >= size) clear() elseif (n >=0) start += n
overridedeftrimEnd(n: Int) =if (n >= size) clear() elseif (n >=0) end -= n
overridedefhead=this(0)
overridedeflast=this(size -1)
privatedefmod(x: Int) =Math.floorMod(x, array.length)
privatedefresizeTo(len: Int) = {
require(len >= size)
valarray2=Array.ofDim[A](len)
val (l, r) = (mod(start), mod(end))
if (l <= r) {
Array.copy(src = array, srcPos = l, dest = array2, destPos =0, length = size)
} else {
vals= array.length - l
Array.copy(src = array, srcPos = l, dest = array2, destPos =0, length = s)
Array.copy(src = array, srcPos =0, dest = array2, destPos = s, length = r)
}
end = size
start =0
array = array2
}
privatedefcheckIndex(idx: Int) =if(!isDefinedAt(idx)) thrownewIndexOutOfBoundsException(idx.toString)
privatedefensureCapacity() =if (size == array.length -1) resizeTo(2* array.length)
}
Scala's
mutable.ArrayBuffer
provides the following asymptotic run-times:We can make make an isolated change to the way we use the internal array (making it a ring-buffer) to get the following performance:
This is strictly better than the current implementation and the change required is minimal.
Here is a proof of concept implementation:
Source + Tests: pathikrit/scalgos@478c353
The text was updated successfully, but these errors were encountered: