By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
455,434 Members | 1,878 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 455,434 IT Pros & Developers. It's quick & easy.

Having problem with Queues

P: n/a
Vmz
HI,
I got two queues, I need to write void function that would check both
queues and remove from first queue all nodes that matches second queue.
Each node has two pointers that shows to previous and next nodes. Here
is what i got so far:

void check(queue que1, queue que2) {
node *temp
temp->next = Galimos.Pirmas;
for(;que1.First != NULL;) {
for(;que2.First != NULL; ) {
if(equal(que1.First->State, que2.First->State)) {
if(que1.First = tempp->next) {
que1.First = que1.First->next;
}
else {
que1.First->previous->next = que1.First->next;
}
que2.First = que2.First->next;
}
que1.First = que1.First->next;
}
}
}

================================================== ======
This seems to be wrong somewhere. Suggestions are wellcome :-)

Nov 23 '05 #1
Share this Question
Share on Google+
8 Replies


P: n/a
Vmz
Here is how queue :: add function works :

==================================================
void queue :: add(node state) {
node * temp;
temp = new node(state);
if(First == NULL) {
temp->next = NULL;
temp->previous = NULL;
First = temp;
Last = temp;
}
else {
if(temp->heuristics <= First->heuristics) {
temp->next = First;
First->previous = temp;
First = temp;
}
else {
Last->next = temp;
temp->previous = Last;
Last = temp;
temp->next = NULL;
}
}
}

================================================== =========

Nov 23 '05 #2

P: n/a

"Vmz" <al**************@gmail.com> wrote in message
news:11*********************@f14g2000cwb.googlegro ups.com...
HI,
I got two queues, I need to write void function that would check both
queues and remove from first queue all nodes that matches second queue.
Each node has two pointers that shows to previous and next nodes. Here
is what i got so far:

void check(queue que1, queue que2) {
node *temp
temp->next = Galimos.Pirmas;
for(;que1.First != NULL;) {
for(;que2.First != NULL; ) {
if(equal(que1.First->State, que2.First->State)) {
if(que1.First = tempp->next) {
que1.First = que1.First->next;
}
else {
que1.First->previous->next = que1.First->next;
}
que2.First = que2.First->next;
}
que1.First = que1.First->next;
}
}
}

================================================== ======
This seems to be wrong somewhere.
That tells us nothing. What specifically is 'wrong'. Doesn't
compile? Wrong results? (if so, state the expect results and
actual results). Also note that you have not provided enough
information to make any meaningful analysis.
Suggestions are wellcome :-)


OK I'll do what I can with the little you presented.

First, I'll assume that your 'rolling your own' queue type is
for academic purposes; otherwise I'd recommend to use the
standard library queue type.

Rather than trying to do the impossible task of analyzing that
without sufficient context, I'll offer more general advice:

Your stated specification implies several needed facilites:

0) The fundamental operations one would expect from a
queue type (e.g. add a node, delete a node, traverse
the nodes, etc.) I can only assume this has already
been done (and tested).

1) Iterate through a queue from beginning to end, being
able to extract the data value from any particular
node along the way. (If you've written your queue
type to be standard library container-compatible,
there are standard library functions you can use
'out of the box'.)

2) Remove a node from a queue

3) Compare the data value of a node from one queue with
that of a node from another queue.

Write (and thoroughly test) separate functions (most
should be member functions of 'queue') for each
of these tasks; then it should be a simple matter to
combine these to form the ultimate solution.

A couple examples of what I mean:

In your example above, in your 'check()' function, you
appear to be trying to write the low-level logic for
traversing a queue and removing a node. Those operations
don't belong in that function. They each belongs in their
own separate functions, which 'check()' can call when needed.

You repeatedly use expressions such as 'que1.First->State'.
This implies that your client code has direct access to
the 'queue' type internal details. Not Good, and very
error prone. IMO you should have created an 'accessor'
member function to get your node 'value', and call it as
needed. E.g. if(que1.state() == que2.state())

You're doing 'low level' processing in what is essentially
a 'high level' function. Manipulation of e.g. 'next' and
'previous' pointers should be hidden details in the queue
type. (For example as part of functions such as 'next()',
'prev()', 'insert()', 'remove()', 'operator==()', etc.)
'Higher level' code such as your above function should
call these functions to perform its work.

Separating your code into discrete functional units has
many advantages, such as quicker development time, ability
to later reuse code, easier testing and debugging, and
much more effective maintenance.

Also consider passing your arguments by reference rather
than by value. When your queue objects get large, you
could see a reduction in performance.

-Mike
Nov 23 '05 #3

P: n/a

"Vmz" <al**************@gmail.com> wrote in message
news:11*********************@o13g2000cwo.googlegro ups.com...
Here is how queue :: add function works :

==================================================
void queue :: add(node state) {
node * temp;
temp = new node(state);
if(First == NULL) {
temp->next = NULL;
temp->previous = NULL;
First = temp;
Last = temp;
}
else {
if(temp->heuristics <= First->heuristics) {
temp->next = First;
First->previous = temp;
First = temp;
}
else {
Last->next = temp;
temp->previous = Last;
Last = temp;
temp->next = NULL;
}
}
}

================================================== =========


Presumably you also have the counterpart to 'add()' --
'remove()' (or whatever name you gave it). Don't you
think it would make sense to have 'check()' call 'remove()'
instead of essentially writing that logic over again (with
the very real possibility of not getting it right?)

The same principle applies to other things 'check()' is
doing, e.g. traversing your queue. You should have
member functions for doing these 'general' operations,
and call them from higher level code (i.e. don't keep
writing the logic over and over all over the place).
That is the recipe for 'spaghetti', a.k.a. 'maintenance
nightmare'.

Another basic operation you'll want to include (if you
haven't already) in your queue type to support 'check()',
is a 'find()' function.

-Mike
Nov 23 '05 #4

P: n/a
"vmz" wrote
if(que1.First = tempp->next)


I do not see where tempp is defined (could you mean temp?) Also,
shouldn't you be using "==" instead of "="?

Nov 23 '05 #5

P: n/a
Vmz
argh, sorry, for bit messing up. when i was translating to english made
some mistakes, it should be:

void check(queue que1, queue que2) {
node temp
temp->next = que1.First;
//Remembering first element
for(;que1.First != NULL;) {
for(;que2.First != NULL; ) {
if(equal(que1.First->State, que2.First->State)) { //checking if
nodes of queues are

//equal, if yes then ..
if(que1.First == tempp->next) {
//checking if its the first node
que1.First = que1.First->next; //Changing que1.First
pointer to second node
}
else { //if the node which is equal is somewhere in the
middle of queue
//remove it from middle of queue
que1.First->previous->next = que1.First->next;
}
que2.First = que2.First->next;
}
que1.First = que1.First->next;
}
}
}
=======================================
I did some little explanation here. I think the problem is in the
second part when I have to remove node from the middle of queue. Could
any1 supply my with algorithm that I could implement it having
queue.First and queue.Last pointers ?

Nov 23 '05 #6

P: n/a
Vmz
> That tells us nothing. What specifically is 'wrong'. Doesn't
compile? Wrong results? (if so, state the expect results and
actual results). Also note that you have not provided enough
information to make any meaningful analysis.


It does compile, the program works, one of my tasks is to check for
repeated states, so i make to queues, one with present states(nodes)
and second with those which already happened. The program gives me
wrong results after ~10 checks, and the two states start repeat. for
example:
-------
|1|5|6|
-------
|0|2|3|
-------
|7|8|4|
-------
|
\/
-------
|1|5|6|
-------
|2|0|3|
-------
|7|8|4|
-------
|
\/
-------
|1|5|6|
-------
|0|2|3|
-------
|7|8|4|

======================================
I'm making 8-puzzle game.

Nov 23 '05 #7

P: n/a

"Vmz" <al**************@gmail.com> wrote in message
news:11**********************@g43g2000cwa.googlegr oups.com...
That tells us nothing. What specifically is 'wrong'. Doesn't
compile? Wrong results? (if so, state the expect results and
actual results). Also note that you have not provided enough
information to make any meaningful analysis.


It does compile, the program works, one of my tasks is to check for
repeated states, so i make to queues, one with present states(nodes)
and second with those which already happened. The program gives me
wrong results after ~10 checks, and the two states start repeat. for
example:


The occurrence of exactly these kinds of problems is why
I strongly recommend a much more modular design: small
discrete functions which each doing only a single task;
each fully tested and debugged. That makes the higher
level stuff much easier to implement, debug and maintain.

And even without redesigning your code, you've still not
given nearly enough information (code) to do any kind
of analysis.

-Mike
Nov 23 '05 #8

P: n/a
Vmz wrote:
HI,
I got two queues, I need to write void function that would check both
queues and remove from first queue all nodes that matches second queue.
Each node has two pointers that shows to previous and next nodes. Here
is what i got so far:

void check(queue que1, queue que2) {
node *temp
temp->next = Galimos.Pirmas;
for(;que1.First != NULL;) {
for(;que2.First != NULL; ) {
if(equal(que1.First->State, que2.First->State)) {
if(que1.First = tempp->next) {
que1.First = que1.First->next;
}
else {
que1.First->previous->next = que1.First->next;
}
que2.First = que2.First->next;
}
que1.First = que1.First->next;
}
}
}

================================================== ======
This seems to be wrong somewhere. Suggestions are wellcome :-)


I'll second the suggestions of Mike Wahler, he gave a lot of good advice
which you should not ignore, even though it wasn't what you wanted to hear.

However there is one error I can see even from what you've posted.

void check(queue que1, queue que2) {
node *temp
temp->next = Galimos.Pirmas;

'temp' is an uninitialised pointer, but you are using it as if it
pointed somewhere meaningful.

john
Nov 23 '05 #9

This discussion thread is closed

Replies have been disabled for this discussion.