I want to use ArrayBuffer in my program to keep list of numbers. I want to use it as queue. Each time delete the first item in the list and use it. Then I was wondering each time that I am deleting the first item do all other numbers in the queue shift one place. I mean next time can I again read item(0) ?
Add a comment
|
4 Answers
If you look into the Scala source code or ArrayBuffer, you'll see the following implementation of remove:
/** Removes the element on a given index position. It takes time linear in
* the buffer size.
*
* @param n the index which refers to the first element to delete.
* @param count the number of elements to delete
* @throws Predef.IndexOutOfBoundsException if `n` is out of bounds.
*/
override def remove(n: Int, count: Int) {
require(count >= 0, "removing negative number of elements")
if (n < 0 || n > size0 - count) throw new IndexOutOfBoundsException(n.toString)
copy(n + count, n, size0 - (n + count))
reduceToSize(size0 - count)
}
So the removed element will no longer be present in the array, but indeed, the removal means copying all elements ("shifting" in your definition), and it will be slow for longer arrays.
3 Comments
that other guy
Adding to this, Scala has both a mutable and an immutable Queue implementation.
Mahsa
@Ashalynd thanks a lot. I am using remove for that but since my program stops picking elements I thought maybe the reason is behind Arraybuffer. It is reading a line in a binary image it is a continuous line but it stops in some point!
Alboz
@Rubbic still don't understand why you're obsessed with this Array thing and want to use it as a queue. Do you have an allergy to Queue's or you have a better motive?
Why don't you use a Queue as a Queue? Java Queue
It has that nice method called poll() (Retrieves and removes the head of this queue, or returns null if this queue is empty.)
Isn't it what you need? It's also better performing than your Array solution.
1 Comment
Mahsa
thanks but I need some functionality in my program that I am more confident using arraybuffer. Since I talked to you guys and tried different ways, I have decided to change my search algorithm into DFS to use stack, do we have such a thing in Scala or I should implement it myself?
ArrayBuffer is basically an array that implements all the convenient methods of a Buffer.
It works the way you describe: if you remove an element, all the remaining elements are shifted to "fill the gap" and as stated in the doc, it might take some time especially if you remove the first element:
Append, update and random access take constant time (amortized time). Prepends and removes are linear in the buffer size.
Therefore I would not recommend using an ArrayBuffer as a queue.
Actually, best option is your question: simply use a Queue. It is designed to be, well... a queue!
Comments
If you want to use an array-backed data structure (e.g., for runtime (cache locality) or storage (no next pointer) efficiency reasons), you might want to consider java.util.ArrayDeque. This class effectively implements a circular array that resizes when it is full. The poll() (retrieve and remove first element) method is implemented by simply incrementing the start offset
The downside is, that even though this class implements the java.util.Queue interface, there is no implicit conversion to scala.collection.mutable.Queue, so you can't use the Scala collection methods such as map etc.
Note: Scala, as of 2.11, does not have a Deque interface, leave alone an ArrayDeque implementation.
