Re: How to create a two dimensional queue in Perl

[Laurent_R]

A simple queue can just be an array in which you add new items at the end of the array with the push operator, and remove oldest elements from the front with the shift operator (you could also use pop and unshift, but it seems less natural and it is probably slower).

For a "two dimensional queue", although your description seems to be far from clear in my eyes at least (you don't specify how the items should be managed), you could in principle use an array of arrays (AoA). Or maybe what you really need is just several queues working in parallel (with different types of items). Or, if you really think of a queue within the queue, then you should probably just flatten the whole thing into a single queue, which will work just the same way.

But the very idea of a two dimensional queue seems to somewhat defeat or contradict the essential idea of a queue, i.e. a FIFO data structure in which the oldest element is removed first.

This tends to sound as a case of XY Problem. Please state what you are actually trying to do, rather than asking how to implement what you think is the solution to your problem.

[meena]

I want to write a state machine using queues Meaning :Each state has two or more operations After each operation is there that operation from the given state should be removed ;and only after all operations are done ,the state should be dequeued from the queuue and we should move forward to the next state

[Laurent_R]

Assuming your question is not related to threads (since nothing of what you said in this ... thread relates to threads), my understanding is that you need a queue of items, in which each item is itself a list of successive actions to be performed together one after the other when a certain state is reached. This is not really a queue of queues, but rather a queue of lists.

If such is the case, then an AoA is probably what you need. Something like this:

my @queue = ( [$action1, $action2, $action3], [$action4, $action1, $ac
+tion3], ...);
# or possibly;
my @queue =  ( [1, 2, 3], [4, 1, 3]);
# where [1, 2, 3] is a reference to an array of subscripts on an array
+ of actions defined somewhere else.

To add an item to the queue:

push @queue, [7, 3, 0, 9];

Which results in the following data structure:

0  ARRAY(0x80359f90)
   0  1
   1  2
   2  3
1  ARRAY(0x8035a050)
   0  4
   1  1
   2  3
2  ARRAY(0x803561e8)
   0  7
   1  3
   2  0
   3  9

To retrieve and remove a list of actions from the queue:

my $action_ref = shift @queue;

Now, $action_ref is [1, 2, 3], i.e. a reference to an anonymous array containing (1, 2, 3). You can now retrieve the actions one after the other from that anonymous array. For example, if you want to list the actions you've just dequeued:

 print $_, " - " foreach @$action_ref; # prints: 1 - 2 - 3 -

Is this what you need?

[james2vegas]

Sounds like you want to just use Thread::Queue objects inside a Thread::Queue, dequeue from the parent, then work on the child. A potential problem with this is that you can't modify the child queue in place (except by peeking) and would potentially have to keep a reference to it separate from the parent queue.

Alternatively you could use an actual state machine implementation from CPAN.

[BrowserUk]

I want to write a state machine using queues Meaning :Each state has two or more operations After each operation is there that operation from the given state should be removed ;and only after all operations are done ,the state should be dequeued from the queuue and we should move forward to the next state

Let's visualise that:

[ state1: [ op1; op2; op3 ] ]
[ state2: [ op1; op2; op3; op4 ] ]
[ state3: [ op1; op2; op3; op4; op5; op6 ] ]
[ state4: [ op1; op2; op3; op4; op5 ] ]
[ state5: [ op1; op2 ] ]
[ state6: [ op1; op2; op3; op4 ] ]
[ state7: [ op1; op2; op3 ] ]
[ state8: [ op1; op2; op3; op4 ] ]
[ state9: [ op1; op2 ] ]

Will all of state1 (or state9) operations be completed before any of state2 (state8)?

If so, just enqueue() a bunch of Thread::Queue objects onto a Thread::Queue. Dequeue() them one at a time and dequeue() each operation one at a time and process it. But that isn't a state machine, it's just a pre-serialised series of operations.

If however, it is your intention that the first operation of any of states 1 thru 9 can be processed in any order -- which would make it a state machine -- then you aren't using a queue for the outer level; you are using a random access data structure. Ie. an array.

So, use an array of queues rather than abusing a queue of queues.

[marinersk]

Ah, that makes sense.

How to "dimensionalize" your queue greatly depends on how the queue is implemented.

A simple queue can be a normal array -- that is to say, an array of scalars:

#!/usr/bin/perl -w

use strict;

my @MyQueue = ();

{
     # Add items to queue
     push @MyQueue, 'First Entry';
     push @MyQueue, 'Second Entry';

     # Consume from queue (FIFO)
     my $nextEntry = shift @MyQueue;
}

To dimensionalize this, you could make each entry in the queue an array instead of a scalar -- look up "Array Of Arrays" or AoA. Thought I saw links already embedded in other answers on this thread.

If the queue is a hash instead of an array, syntax for use of the queue is simpler, but now you have to manage the hash keys to ensure uniqueness and sequence (presumably FIFO).

I suppose you could just use a two-dimensional array, but I think doing so you'd lose the very attractive simplicity of push/shift. I'd probably just use a hash at that point.

If I had the privilege of building the two-dimensional queue manager from scratch, the question I'd find most pertinent is whether or not the calling program would benefit from receiving its state steps in an array.

If yes, I'd do the extra work to use AoA.
If no, I'd go with a hash and manage the keys myself.
Reason:I find reading the hash syntax easier.
(Yes, all things considered, that's fairly arbitrary.)

Good luck!

[pemungkah]

I think maybe we should step back one more step than that. What precisely is the state machine meant to do? Perhaps some sample input and output would help us understand better. As BrowserUK says, your description seems to imply just an ordered series of actions, and I think that's not what you mean.

Do the state transitions add more items to the queues or something like that? Otherwise I can't see why a...oh, WAIT.

Is the idea to have a top-level set of states (the "top"), with each state having a "queue" (actually a set) of possible "next" states, and this needs to possibly be variable - or each state is set up to have multiple actions, to be used one-by-one? So the real idea is to have a list of possible current states, with each possible next state linked to it, and one or more actions per each state? More like the right idea?