We are about to switch to a new forum software. Until then we have removed the registration on this forum.
Hi There, I need to implement a queue for one of my programs. I seem to have got some problems with getting the intended results.
My program is as follows. It reads a random set of values. The array is of 20 elements. once it is filled (i.e. 20 elements are pushed(queued ?), and the array is full) the first number (FIFO) is popped(dequeued) out. this process is repeated for 100 times. i.e. the first 80 values are popped out sequentially.
Maybe the program itself does not make sense, but actually in my final implementation, the data that are sent are not random numbers but data from a sensor. I plan to make some calculations using an average of the data in the queue before popping them one at a time.
In my implementation I cant seem to push numbers in after first round of 20 elements...
Many Thanks in advance, Genny
int bufferSize = 20;
int num=0;
void setup()
{
}
void draw() {
background(0);
println("****");
QueueDemo queueDemo = new QueueDemo();
for (int frame = 1; frame <100;frame++) {
//read data from arduino
num = int(random(0, 15));
//println(num);
if (frame < bufferSize) {
queueDemo.push(num);
queueDemo.display();
}
else {
queueDemo.display();
queueDemo.pop();
queueDemo.push(num);
queueDemo.display();
}
}
exit();
}
public class QueueDemo {
final int capacity = bufferSize;
int arr[] = new int[capacity];
//int size = 0;
int top = -1;
int rear = 0;
public void push(int pushedElement) {
if (top < capacity - 1) {
top++;
arr[top] = pushedElement;
println("Element " + pushedElement
+ " is pushed to Queue !");
//display();
}
else {
println("Overflow !");
}
}
public void pop() {
if (top >= rear) {
rear++;
println("Pop operation done !");
//display();
top--;
}
else {
println("Underflow !");
}
}
public void display() {
if (top >= rear) {
print("Elements in Queue : ");
for (int i = rear; i <= top; i++) {
print(arr[i]);
print(" ");
}
println("");
}
}
}
Answers
Why ru creating your own QueueDemo implementation rather than using Java's bundled libraries? :-&
I bet using an ArrayDeque as a Queue would be less prone to bugs? %%-
Take a look at this example:
Thanks for your suggestion. Actually I wasn't that conversant on Java. Hence the idea of writing the code. But I'm studying your suggested solution as an example. In it I notice that "points" is the Queue. My knowledge on graphics is a bit below par, So the methods used in the example are
add, remove
only are needed for queue operations :push , pop
in my example ?Actually, I've got no idea how that algorithm works mathematically either. I'm not its creator! :-S
Nonetheless, I did tweaked it from a List and its slow remove(0) method to a more efficient Queue (FIFO) data-structure! :ar!
Yup! Only add() & remove() plus an unnecessary size() are used on the ArrayDeque object referenced by points there!
And in every draw() iteration, a
new
PVector is added at its back position (tail).However, when some chosen constraint occurs, either MAX # of elements is reached or frameRate drops too much,
the oldest object is removed from its front position (head), and recycled back as a new element to the back (tail).
Those method names are traditionally used for Stack (LIFO) structures instead. (%)
writing a queue is a pretty useful thing to know how to do, though, even if it's not really necessary. Here's one way to write one:
the built-int java Queue class is better because it's generic, so you can make a Queue of any type, but a queue is really just a linked list with some methods to help you add and remove elements.
oh and if you define the method named
toString
and have it return aString
, then that method will be called when you useprintln
(or anything that requires a string, for that matter).Actually it is an interface! And besides being generic, capable of storing PVector references for example,
it also implements the Iterable interface, so we can use it in a loop! o->
... but a queue is really just a linked list with some methods to help you add and remove elements.
Most queue implementations indeed use linked nodes as yours. But the class I used in my example is an ArrayDeque, which is a resizable array implementation of the Deque interface:
docs.oracle.com/javase/7/docs/api/java/util/ArrayDeque.html
For an example of an unbounded thread-safe queue based on linked nodes, try out ConcurrentLinkedQueue class:
docs.oracle.com/javase/7/docs/api/java/util/concurrent/ConcurrentLinkedQueue.html
To modify Brownian Motion to use a ConcurrentLinkedQueue instead, just make these 2 tiny changes:
import java.util.concurrent.ConcurrentLinkedQueue;
final Queue<PVector> points = new ConcurrentLinkedQueue();
Or even a doubly-linked list implementation -> LinkedList:
import java.util.LinkedList;
final Queue<PVector> points = new LinkedList();
Dear All, thank you for the constructive advice. I've tried to re-write my program, using ArrayDequeue class. I seem to have hit a problem with the Pvector implementation in above example. As my programming in processing has been a bit of ver. 1.5 i'm rather new with the pvector class. Can we implement the dequqe for a data type like int used in my example....
This is my current modified program using ArrayDeque
in this case, I get an error :The method add(Pvector) in the type Queue is not applicable for the arguments. I noted from a reference site that for the ArrayDequeue : "As with the other collections classes, only Object types are supported." (Does it mean that primitive data types are not supported ?)
****
in line 4 you use pvector, in line 21 you add an int...
I cant seem to declare line 4 as int...
final Queue<int> dataQueue = new ArrayDeque(bufferSize);
Java's API comes bundled w/ what is called the 8 primitive wrapper classes, each 1 representing 1 of the primitive types! @-)
The corresponding wrapper class for
int
data-type is called Integer.Therefore, to have something like a Queue of
int
types, closest we can get is:static final int BUFFER_SIZE = 20;
final Queue<Integer> dataQueue = new ArrayDeque(BUFFER_SIZE);
Take a look at this post below to know more about the differences between primitive & object/reference types:
http://forum.processing.org/two/discussion/2889/primitives-and-classes
P.S.: Take notice that an ArrayDeque, just like an ArrayList, is boundless. We don't need to specify its capacity like a BUFFER_SIZE.
When we add() a
new
element to it when its capacity is full, it automatically resizes itself bigger. So no worries! :DThank you GotoLoop for your detailed explanation...I didnt know about the wrapper classes. So this is my working program for now
But I still have some difficulty manipulating the dequeue objects - the method .getLast commented above doesnt work, although it is mentioned in the reference site you indicated.
I understood your comment on the size. I was not aware of that either, although I knew there must be a dynamic queue implementation
That method isn't mentioned in the Queue interface, b/c it's actually a Stack (FIFO) method:
http://docs.oracle.com/javase/7/docs/api/java/util/Queue.html
Since your dataQueue variable is of Queue data-type, it's constrained to use only those set of methods,
even though an ArrayDeque object has many more!!! >:)
If you really wanna get access to those FIFO methods, declare dataQueue as a Deque type instead.
But you would be mixing up LIFO & FIFO together; an unholy mess! X_X
Anyways, there's no logic in doing so, b/c when we issue the add() method, it enqueues an element as the last 1 already.
Therefore it's really redundant asking for last element when we're doing queues (FIFO)!
Just use a variable to store and keep track about that information if you need that so! 8-X
About your latest posted code, you're over complicating things:
Java automatically takes care on converting back & forth primitive values to their corresponding wrapper classes for us!
You don't need this wreckage long train of methods:
Integer num = Integer.parseInt(str(int(random(0, 15))));
This is quite enough:
int num = (int) random(15);
Neither explicitly use an Iterator to traverse any Collection such as an ArrayDeque.
Java got an enhanced
for
loop which was created for such cases!Look at line #68 in the "Brownian Motion" example I've posted before. No explicit Iterator whatsoever:
I still don't get how you wanna use the queue approach for your Arduino reading code. The following is my guess: :-/
Anyways, I've tweaked your last code this way: ^#(^
Hi GotoLoop, Thank you very much for correcting my elementary mistakes. I thought to add items to the queue it must assigned via the Integer wrapper class object. 8-| I learnt from your suggestions, and modified code. But just to clarify my intentions :
My code above was purely experimental, but this is roughly what i really wanted to do with processing
My experiment of using Integer queue was a start, as i read, i think in processing Pvectors maybe a better suited for my purpose. However, i'm wondering whether the arraydequeue methods will work for this now - As in each loop i have to average the values of all items in the queue.
That makes no sense! Both my latest example & "Brownian Motion" codes show clearly we can iterate the whole Queue!
This Arduino mock-up now demos again how to traverse a Queue and collect each PVector from it to obtain averages[] from it:
Thank you Gotoloop, and regret my delay in replying. I've noted the methods for the Pvector class, but how can i restrict the random numbers generated as done in the random function. for one, I cant seem to figure out how to fix the following modification. I've basically created a new Pvector (coord) which gets assigned a 2D random values and add it to the queue. Line 14 seems to be saying the local var may not have initialized.
In branching blocks, like
if ()
,for ()
,do ()
,while ()
, if we have only 1 statement, curly braces are optional.Otherwise, we have to scope the block belonging to the branch w/ them! 8-X
In your case, line #14 doesn't belong to the branch
for ()
@ line #11! (~~)Anyways, here's my 1-line block fix. I don't need
{}
again b/c it's just 1-statement block:Thank you yes, I did miss the braces..One (hopefully) final question. In my previous code, In the main loop (code lines 16-26) I need to calculate the average of the first three values in queue - Avg(P1,P2,P3) and last three values in queue - Avg (P18,P19,P20) (during each iteration - and output them to screen each time) ) I learnt from you that the queue iteration, can be simple as line 19, but when we want to add only few selected elements in the queue , how would we proceed ?. My understanding is to use a counter, and total values each time.
Oh, now I got why you wanted the getLast() method from the Deque interface! b-(
Anyways, since a Queue got its elements ordered, we just need to get both the 1st 3 & last 3 readings while iterating over it! %%-
And since an enhanced
for
loop doesn't provide us a counter, we gotta make ourselves 1!And this is how I've implemented the whole iteration selective capturing: :ar!
Whole fixed code below. Any further doubts or tweaks, just ask: =:)
Hey again! I did a remix of the same code. But this time, rather than instantiate a new PVector object when the Queue is full,
it re-uses the removed oldest PVector, gives it new values, then re-insert it as newest element at the tail of the Queue.
Just like I did w/ "Brownian Motion" code. Check it out: >:)
Thank You very much. You have saved me...! Anyway the exact program i wanted is a bit different, I think it works ok for the moment, thanks to your advice. Probably needs a bit more tweaks when reading data from Serial.. Any suggestions on optimising the following code ?
** I just saw your modified code. Looks a brilliant idea! :)
Well, you've got 2
for (PVector dq: dataQueue) {
inner loopsinside
for (int frame = BUFFER_SIZE; frame++ != MAX_READS;) {
outer loop!Just merged those 2 as 1 iterating loop over Queue! :-j
Check it out the "new" code:
Thank you very much GotoLoop. You should start a consultancy service for giving advice!. Your very helpful.
Hi GotoLoop, I'm modifying my program slightly, but i'm thinking of how to proceed. this is the problem at hand :
In the previous example I entered two data (x,y) into the queue. Now I'm getting more data from my hardware for more accuracy, and have data - x,y,z (z can be accommodated in existing pVector) plus another two sets of x,y coordinates Say Xf,Yf and Xs,Ys which I want to calculate using the same way.
So i'm thinking of repeating another two sets of the above code below each other with two new PVectors. Is there any other shorter method to integrate the Seven data elements into a queue ?(rather than using three PVector Queues ?)
Well, how about make a better PVector derivative?
Introducing SuperVec class w/ 2 more additional built-in PVector objects as f & s:
Depending on your necessities, you may expand it further by adding up more methods,
besides clear() & toString() I've already made for ya! =:)
Wow, thanks a lot. i'm a little unfamiliar with the extends reserved word, although i have seen it. let me check on it and modify my code.
You can read about it here: http://processing.org/reference/extends.html
float
fields x, y, & z, it also got 2 more PVector fields: f & s!Hi GoToLoop, Thanks once again, and sorry for not replying earlier, I was working on a different program and this modification was on pause for some time. Nevertheless I have a few issue in modifying my original program, even though the suggestion by you - on extending the class to accommodate two more Pvectors is crystal clear!.
I've added the part from my original code suggested by you (and works fine) to explain the problems i have. As I explained previously in my new problem, i'm dealing with a number of Points in 3D. (Original had just one (x,y,z)) So S and F were the two additional points (added correctly to your suggested code).
I hope the problem is clear. Basically the MainXYZ, S, and F results need to be computed separately, but within the single loop.
** Also in my programme Do i need to use the clear() and toSrting() methods for the superclass ?I feel not, though I am not sure what to add either
I Really appreciate your assistance! :)