Quack assignment from Data Structures class

[P1X3]

I haven't been able to attend my data structures class last couple of times and missed some lectures on stacks, queues, and circular arrays.

To be honest I was able to pick up fairly easy but this "quack" assignment is somewhat challenging.

 

If you feel like writing some code then feel free to do so. I think it is a good exercise for those that learn by themselves.

 

Zip file contains base code provided by instructor, html file with instructions, and example of what the output of finished program should look like.

 

P.S. This is solely for training purposes only and I do not need your code so that I can turn it in as "my" code. 

lab2.zip

[alpenwasser]

I think it is a good exercise for those that learn by themselves.

Having had a quick look at it, I agree. I shall dust off my programming skills and

do this when I have some down time, thanks! :)

[TizzyT]

I agree on everything that I dont understand, which is pretty much everything.

[P1X3]

After my first push/pop methods didn't work out as I expected I decided to start out clean.

I even got it to reverse positive numbers, but reversing to negative numbers is just making me mad. I don't even want to think about reverse.

 

So my understand behind rotate is for positive rotation the front has to be adjusted and values from old front until new front (including old front) have to be pushed in the back. Which I kinda did, I hope.

Rotating in negative number should be somewhat oposite. Find a new front and then push old back values to the front... Maybe, idk.

 

Defiantly need help with this. Thank god for libraries and this will never be coded by hand...

 

Here is what I have

void Quack::rotate(int r){	// set new front	// if front = 2 then new front = 4 with r=2	int newFront = queueFront + r; 	if (newFront >= capacity)		newFront = newFront - capacity;	else if (newFront < 0)		newFront = newFront + capacity;	queueFront = newFront;	// Mode items between old front and new front, 	// including old front and excluding new front to the back.	int counter = r;	if (r < 0)		counter *= -1;	for (int i = 1; i <= counter + 1; i++)	{		if (r > 0)		{			int itemToGrab = queueFront - counter;			if (itemToGrab < 0)				itemToGrab = capacity + itemToGrab;			int newBack = queueBack + 1;			if (newBack >= capacity)				newBack = newBack - capacity;			items[newBack] = items[itemToGrab];			queueBack = newBack;			counter--;		}		else // doesnt work, rage...		{			int itemToGrab = queueBack;						int newBack = queueBack + 1;			if (newBack >= capacity)				newBack = newBack - capacity;			items[newBack] = items[itemToGrab];			queueBack = newBack;			counter--;		}	}}

I will be fine either with more in-depth explanation of rotate or just a code to show how it's done.

[alpenwasser]

Ok, before I do anything else, let's just make sure I have actually understood the

concept, since I have never personally done this and it's been a while since my last

C++ challenge. :lol:

I'll start with arrayRegular.txt

pushFront(a)       [ a - - - - - - ]pushFront(b)       [ a - - - - - b ]pushFront(c)       [ a - - - - c b ]pushFront(d)       [ a - - - d c b ]pushBack(z)        [ a z - - d c b ]pushFront(e)       [ a z - e d c b ]popFront -> e      [ a z - e d c b ]popFront -> d      [ a z - e d c b ]pushBack(f)        [ a z f e d c b ]pushBack(g)        [ a z f g d c b ]rotate(2)          [ a z f g c b b ]rotate(-3)         [ a z f g g c b ]

A few questions on that for clarification:

• After doing pushFront->e, the current queue front is at that position (therefore

  at items[3]?

• At that point, the queue's back is at z (items[1])?
• pushBack(f) sets the back at items[2]?
• pushBack(g) sets the back at items[3]?
• After having done pushBack(g), the queue's front is now at items[4], therefore on

  element "d"?

• What exactly is rotate(2) supposed to do to items[]? Whatever happens there looks

  kinda hinky to me. I understand the visual representation of rotate (according to

  lab2RegularCorrectOutput.txt), but the actual operation on the array itself looks

  kinda strange so far, at least according to the above.

In any case, I have found one possible problem in your code itself (I think).

In this block:

 

void Quack::rotate(int r){		if (r > 0)		{			int itemToGrab = queueFront - counter;			if (itemToGrab < 0)				itemToGrab = capacity + itemToGrab;			int newBack = queueBack + 1;			if (newBack >= capacity)				newBack = newBack - capacity;			items[newBack] = items[itemToGrab];			queueBack = newBack;			counter--;		}}

On line 13: You do

items[newBack] = items[itemToGrab];

Where does the value go that was previously stored in items[newBack]? Shouldn't

that be preserved in a temp variable or something like that?

As I've said, my C++ and theoretical data object knowledge is a bit rusty. ;)

EDIT: I've gone through your code up to //...rage, and it seems more

or less sane as far as I can tell without having yet fully understood the problem

in all its details.

[WanderingFool]

Hi P1X3, I just briefly read over the assignment and it looks actually quite interesting.  I don't want to give you a solution, and am too lazy to even complete it myself.  But I will show you a bit of pseudo code that might set you on your way, it will ignore some finer details and could be completely wrong (yay for being awake for 20 hours)

 

The first clue is this:

Your implementation of the Quack class will store its items as a circular array (you can find a description of this concept in the textbook).

Now with your code items[newBack] = items[itemToGrab]; it looks like you are actually swapping the array items, as this is a rotate you shouldn't need to.  If you looks at the assignment it says fewest moves possible, so a rotate should not be changing the array structure (as it is a circular array).

 

Here is a quick bit of pseudo code (Don't put too much reliance on this, it is just something I put together quickly).

//Assume you define 2 new variables for quack_nextFrontIndex = 0 //when initialized_nextRearIndex = 0//Assuming the size of items == capacity//_ stands for variables, and % is mod...a handy feature//when using circular arrays//If you are doing premium you need to expand this when the cap//gets too fullfunc pushFront _value	if(_nitems == cap) exception	_items[_nextFrontIndex] = _value;	_nextFrontIndex = (_nextFrontIndex-1) % _capacity //Ensures 0 - [cap-1]	_nitems++;func pushBack _value	Similar to Frontfunc popFront	_nextFrontIndex = (_nextFrontIndex+1) % _capacity //Ensures 0 - [cap-1]	_nitems--;func popBack	Similar to Frontfunc rotate _r	//This assumes the container is full	//You can do the math for when the container isn't full	_nextFrontIndex = (_nextFrontIndex+r) % _capacity	_nextBackIndex = (_nextBackIndex+r) % _capacityfunc rev	//You can figure this out, it shouldn't be too hard...just regular swapsfunc op<<	_cnt = 0;	for _i = _nextFrontIndex+1; _cnt < nitems; _i++		_cnt++;		os<< _items[_i%capacity];

[alpenwasser]

Ok, I've decided to rid myself of your teacher's restrictions and demands and simply

implement a circular array (or rather: the start of one) first to get a better idea

of how it works and what it's supposed to do without having a cluttered mind (I've

never done one before, so the concept of this problem is rather new to me as well).

This code is not complete!

There are still many essential features missing, for example the rotation of not

completely filled arrays. Also, the "overlap" between the front and the back end

is not yet properly handled (meaning the front and back end can go past each other

without consequence). And I haven't yet checked for bugs (slept three hours last

night, not in the best of shapes tbh, this seems to be the thread for sleep deprived

programmers :lol: ).

However, it does some basic operations and might give you further ideas how to go

about solving your problem.

As WanderingFool has mentioned (and I shamefully forgot in my last post, even though

I very often make use of it in my code), the modulo operator is great for these sorts

of things.

Anyway:

 

#include <iostream>using namespace std;class circular_array{    public:        int get_head();        int get_tail();        void push_head(char);        void push_tail(char);        char pop_head();        char pop_tail();        int remove_from_head();        int remove_from_tail();        void rotate(int);        int get(int index);        void printarr();        circular_array(int capacity);    private:        int decrement_index(int,int);        int increment_index(int,int);        int capacity;        char* items;        int head_index; // index of first element        int tail_index; // index of last element        int size;};circular_array::circular_array(int capacity){    this->items = new char[capacity];    this->capacity=capacity;    this->tail_index=capacity-1;    this->head_index=0;    this->tail_index=0;    this->size=0;}int circular_array::get_head(){    return this->head_index;}int circular_array::get_tail(){    return this->tail_index;}int circular_array::increment_index(int index,int increment){    return (index+increment) % this->capacity;}int circular_array::decrement_index(int index,int decrement){    int new_index = ((index-decrement) % this->capacity);    return (new_index<0) ? new_index+this->capacity : new_index;}void circular_array::push_head(char new_element){    if (this->size==0)        this->items[0]=new_element;    else    {        this->head_index=this->decrement_index(this->head_index,1);        items[this->head_index]=new_element;    }    size += 1;}void circular_array::push_tail(char new_element){    this->tail_index=this->increment_index(this->tail_index,1);    this->items[this->tail_index]=new_element;    size += 1;}char circular_array::pop_head(){    return this->items[head_index];}char circular_array::pop_tail(){    return this->items[tail_index];}void circular_array::rotate(int rotation){    /* only handles filled arrays */    this->head_index=(this->head_index+rotation) % this->capacity;    this->head_index = (this->head_index<0) ?        this->head_index+this->capacity : this->head_index;    this->tail_index=(this->tail_index+rotation) % this->capacity;    this->tail_index = (this->tail_index<0) ?        this->tail_index+this->capacity : this->tail_index;}void circular_array::printarr(){    for (int i=0;i<this->capacity;i++)    {        cout << this->items[i] << " ";    }    cout << "\n";}

For playing around with it, you can use something like:

int main(){    circular_array testarr(5);    testarr.push_head('a');    testarr.push_head('b');    testarr.push_tail('c');    testarr.push_tail('h');    testarr.push_head('g');    cout << testarr.pop_head() << "\n";    cout << testarr.pop_tail() << "\n";    testarr.printarr();    testarr.rotate(-2);    cout << testarr.pop_head() << "\n";    cout << testarr.pop_tail() << "\n";    return 0;}

I've played around with it for a bit and rotate seems to work properly from what

I can tell so far (for filled arrays).

As mentioned, this is definitely not the solution to your problem, but together with

WanderingFool's tips from above you might get some useful inspiration. ;)

[P1X3]

Thank you for replies. This somewhat makes sense to me now that I have seem someone else do it.

 

I noticed that rotating full/filled arrays is way easier because only back and front indexes are moved. However if it's not filled it becomes a bit more trickier.

Here is what complete program should do when rotate(2) is called.

 

pushBack(g)        [ a z f g d c b ]rotate(2)          [ a z f g c b b ]

• After "g" was pushed back it becomes a new back with index of "3" and "c" is still the front with index of "5". All of this is correct before rotate(2)
• After rotate(2) the front index is "previous frontIdx + r" which in case of rotate(2) is "5+2" which is then fixed to 0. So far no elements were moved.
• Then previous front item is pushed at the back which is still set to "g" index 3, so "c" is pushed at the back (pushBack) and then items after "c" (old front) are pushed to the back (pushBack)
• At the end of rotate(2) only two items moved (pushed at the back) and frontIdx = 0 with backIdx = 5

To be honest I don't see any other way to rotate it to get similar array that is provided as an example in "lab2RegularCorrectOutput".

Then looking at rotate(-3) its kinda the opposite of rotate(2)

rotate(2)          [ a z f g c b b ]rotate(-3)         [ a z f g g c b ]

3 back items (g, c, B) were pushed to the front making "g" a new front item, and then new back was set yo whatever was before "g", in this case "f". Again only 3 items were moved.

 

--> pushBack g

 

quack: c, b, a, z, f, g

 

--> rotate 2

 

quack: a, z, f, g, c, b

 

--> rotate -3

 

quack: g, c, b, a, z, f

So this makes me think following

• When rotating by positive number: Do "popFront and pushBack" for however many times we are rotating by (with rotate(2) it will be run 2 times)
• When rotating by negative number: Do "popBack and pushFront" for howmany times we are rotating by (with rotate(-3) it will be run 3 times)

However instructor said we can't call those function.

 

I don't know if this makes sense or not, but I was sitting in class and thinking about buckets in a circle, however it will be harder to explain.

 

I am also sad that I couldn't think of code below on my own  which was posted by WanderingFool :\

_nextFrontIndex = (_nextFrontIndex-1) % _capacity //Ensures 0 - [cap-1]

Edit:

Here is code

	if (r > 0)	{		for (int i = 1; i <= r; i++)		{			char temp;			popFront(temp);			pushBack(temp);		}	}	else	{		for (int i = 1; i <= (r*-1); i++)		{			char temp;			popBack(temp);			pushFront(temp);		}	}

It works with unfilled arrays. However instructions don't allow to use pop and push in rotate.

[WanderingFool]

P1X3, yea sorry missed that it wasn't full last night...if I get time later, I might be able to help you figure it out.

 

Just to say quickly alphen did a good job in implementing _nextFrontIndex = (_nextFrontIndex-1) % _capacity...but basically in c type of code it would look something like

int nextFrontIndex = 0; ///Defined somewherefunc...    nextFrontIndex = (nextFrontIndex - 1) % capacity; //Can't remember what c/c++ will do in this case if negative....assuming strict mod it should work    //If I am wrong then if(nextFrontIndex < 0) nextFrontIndex += capacity; should fix things (after mod is called)

I'll try to post some more help for moving the array when capacity isn't full, when I am not busy

[P1X3]

P1X3, yea sorry missed that it wasn't full last night...if I get time later, I might be able to help you figure it out.

 

Just to say quickly alphen did a good job in implementing _nextFrontIndex = (_nextFrontIndex-1) % _capacity...but basically in c type of code it would look something like

int nextFrontIndex = 0; ///Defined somewherefunc...    nextFrontIndex = (nextFrontIndex - 1) % capacity; //Can't remember what c/c++ will do in this case if negative....assuming strict mod it should work    //If I am wrong then if(nextFrontIndex < 0) nextFrontIndex += capacity; should fix things (after mod is called)

I'll try to post some more help for moving the array when capacity isn't full, when I am not busy

Okay here is a question. If array is unfilled then amount of items to be moved should equal to the how many items we are rotating by. Right? I edit previous code with some push&pop code which handles rotate(2) and rotate(-3) of unfilled arrays like a champ.

 

For example here is comparison of my array using pop&push methods and array provided from arrayRegular.

pushBack(g)        [ a z f g d c b ]

rotate(2)          [ a z f g c b b ]

rotate(-3)         [ a z f g g c b ]

 

pushBack(g)        [ a z f g d c b ]

rotate(2)          [ a z f g c b b ]

rotate(-3)         [ a z f g g c b ]

They are identical, so then why pop&push can't be used because again it will move only 2 and 3 items.

 

I think that either instructor or I am making this more complicated than it should be.

 

P.S. I am worried about unfilled arrays only.

[WanderingFool]

Anyways on a quick break so I can answer a bit of your questions and provide some sloppy pseudocode.

 

Okay here is a question. If array is unfilled then amount of items to be moved should equal to the how many items we are rotating by. Right?

You are right, with a few exceptions:

r > nitems then r = r % nitems, as you will loop around eg rotate(3) when nitems = 2, so rotate(1) is the same

r > nitems/2 then r = r - nitems or something like that, as rotate(2) when nitems = 3 to reduce moves you could use rotate(-1)

 

They are identical, so then why pop&push can't be used because again it will move only 2 and 3 items.

Your instructor I guess is trying to teach you about circular arrays and the efficiencies.  If you have access to an array and you call pop then push, you are just wasting resources with a function call nitems-- then nitems++ when a simpe array replacement will suffice.

 

Here is the sloppy pseudo-code, hope it helps you understand

func rotate®	r = r % nitems	//Excluding the optimization here, you can add it yourself (the r > nitems/2)	int direction;	int *tmpRead, *tmpWrite	if(r > 0) 		direction = 1; //Going right		tmpRead = &nextFrontIndex //tmpRead = whatever nextFrontIndex via pointer		tmpWrite = &nextBackIndex	else		direction = -1;		tmpRead = &nextBackIndex //tmpRead = whatever nextFrontIndex via pointer		tmpWrite = &nextFrontIndex	for(i = 0; i < abs®; i++)		items[*tmpWrite] = itms[*tmpRead]		//Same as before the incompletes will be filled in below		nextFrontIndex = (nextFrontIndex+direction) % capacity		nextBackIndex = (nextBackIndex+direction) % capacity

Of course there are probably more efficient ways, but this is just something thrown together.  With that said it might not work, but the concept of how it should work is roughly there

[P1X3]

Anyways on a quick break so I can answer a bit of your questions and provide some sloppy pseudocode.

 

You are right, with a few exceptions:

r > nitems then r = r % nitems, as you will loop around eg rotate(3) when nitems = 2, so rotate(1) is the same

r > nitems/2 then r = r - nitems or something like that, as rotate(2) when nitems = 3 to reduce moves you could use rotate(-1)

 

Your instructor I guess is trying to teach you about circular arrays and the efficiencies.  If you have access to an array and you call pop then push, you are just wasting resources with a function call nitems-- then nitems++ when a simpe array replacement will suffice.

 

Here is the sloppy pseudo-code, hope it helps you understand

func rotate®	r = r % nitems	//Excluding the optimization here, you can add it yourself (the r > nitems/2)	int direction;	int *tmpRead, *tmpWrite	if(r > 0) 		direction = 1; //Going right		tmpRead = &nextFrontIndex //tmpRead = whatever nextFrontIndex via pointer		tmpWrite = &nextBackIndex	else		direction = -1;		tmpRead = &nextBackIndex //tmpRead = whatever nextFrontIndex via pointer		tmpWrite = &nextFrontIndex	for(i = 0; i < abs®; i++)		items[*tmpWrite] = itms[*tmpRead]		//Same as before the incompletes will be filled in below		nextFrontIndex = (nextFrontIndex+direction) % capacity		nextBackIndex = (nextBackIndex+direction) % capacity

Of course there are probably more efficient ways, but this is just something thrown together.  With that said it might not work, but the concept of how it should work is roughly there

 

Now this makes sense. By calling pop and push I'll be wasting resources and creating un-necessary call stacks. Too bad I haven't though of it.

But there's nothing stopping me from re-using the code from pop&push to implement rotate.

 

I think I got this now.

 

Thanks once again.

[alpenwasser]

Sorry about not getting back sooner, my dog demanded I spend some time with him :lol:

Anyway, WanderingFool has laid things out pretty nicely I think, I agree that your

instructor's point with his push/pop restrictions is probably trying to teach you

to be efficient. If I get the time I might take another stab at this once I've gotten

some sleep (the dog had stomach problems last night so I only got two hours of sleep,

hence I'm not exactly in my most productive state at the moment).

If lack of time (I'm currently trying to teach myself some Perl and do a web project

with it, which takes up quite a bit of my days besides my four-legged friend) prevents

me from finishing this right now I'm certainly looking forward to your results :)

EDIT: Almost forgot, I tried this quickly:

        -2%5;

And it evaluates to -2 (compiler: g++). Just in case you were still wondering.

[P1X3]

So here is my working, yes it's finally working, code for rotate. I have yet too see what will happen if r > nItems but it's not in the instructions so I can care less.

// items are pushed to successively LOWER slots in the circular array// (except for when the beginning of the array "wraps around" to the end)bool Quack::pushFront(const char ch){	if ( nItems >= capacity)		return false;	if (nItems != 0)		queueFront = queueFront - 1;	if (queueFront < 0)		queueFront = queueFront + capacity;	items[queueFront] = ch;	nItems++;	return true;}// items are pushed to successively HIGHER slots in the circular array// (except for when the end of the array "wraps around" to the beginning)bool Quack::pushBack(const char ch){	if ( nItems >= capacity)		return false;	if (nItems != 0)		queueBack = queueBack + 1;	if (queueBack >= capacity)		queueBack = queueBack - capacity;	items[queueBack] = ch;	nItems++;	return true;}bool Quack::popFront(char& ch){	if ( nItems == 0)		return false;		ch = items[queueFront++];	if ( queueFront >= capacity )		queueFront = queueFront - capacity;	nItems--;	return true;}bool Quack::popBack(char& ch){	if ( nItems == 0)		return false;		ch = items[queueBack--];	if (queueBack < 0)		queueBack = capacity - queueBack;	nItems--;	return true;}void Quack::rotate(int r){	// Avoid extra rotations if nItems = 2 and rotate(5) is called	if (r > nItems)		r = r % nItems;	// 	if (r > nItems/2)		r = r - nItems;	if (r > 0)	{		for (int i = 1; i <= r; i++)		{			//char temp;			//popFront(temp);			//pushBack(temp);			//popFront			char ch = items[queueFront];			queueFront = (queueFront+1) % capacity;			//pushBack			queueBack = (queueBack+1) % capacity;			items[queueBack] = ch;					}	}	else	{		for (int i = 1; i <= (r*-1); i++)		{			//popBack			char ch = items[queueBack];			queueBack = (queueBack-1) % capacity;			//pushFront			queueFront = (queueFront-1) % capacity;			if (queueFront < 0)				queueFront = queueFront + capacity;			items[queueFront] = ch;		}	}}

It's not all that perfect but it should be somewhat efficient, and hey, it works..

 

Now onto reverse.

[WanderingFool]

EDIT: Almost forgot, I tried this quickly:

        -2%5;

And it evaluates to -2 (compiler: g++). Just in case you were still wondering.

 

Thanks alpen, I looked up the reason too

"(a/b) * b + a%b shall equal a"

 

It's not all that perfect but it should be somewhat efficient, and hey, it works..

 

Now onto reverse.

Congratulations, things like this become easier the more you implement them, and the more you can compare.

 

As a side note, does your teacher post their solution after all assignments are handed in.  If not I might do this one, just so there is more code to compare with (I will make sure it is after the due date, so there can be no cheating)

[P1X3]

Congratulations, things like this become easier the more you implement them, and the more you can compare.

 

As a side note, does your teacher post their solution after all assignments are handed in.  If not I might do this one, just so there is more code to compare with (I will make sure it is after the due date, so there can be no cheating)

 

No. I am kinda disappointed with the instructor.

All labs come with pre-written code. Students are to write the code so that the output matches the correct output. In the zip there is a file for correct output for regular version as well as what correctarray file to match it with array.txt.

Instructor then simply runs his "python script" to compile the code, run, and compare the outputs and output files. While I admit that it is clever and makes it easier for him, I think that it's not the way to do it. For example my last lab is as efficient as I could make it (with my knowledge) and its output matches with desired output 100%. Yet I received 95%

Also previous teacher allowed to submit labs earlier and resubmit before due date. Also not to mention that there were more students in previous course. I should probably bring this up next time I talk to adviser.

 

Edit:

Finally completed regular version (regular gets a maximum of B, premium A). Feel free to download and check the code. Special thanks to WanderingFool and alpenwasser for helping.

lab2.zip

lab2.zip

[WanderingFool]

Finally completed regular version (regular gets a maximum of B, premium A). Feel free to download and check the code.

Ok read through your code, I would recommend looking at your reverse function on a nonfull list

As an example:

 

[a b c d]

your queueFront pointing to a and queueBack pointing to b

reverse

[d c b a]

from what I read yours will now be pointing to d, and c.  Thus not reversed

 

You only need to do nItems/2 operations, but you used capacity as well

The final comment would be (capacity-1)/2 on an even numbered array (e.g. 4) will only do 1 swap instead of 2

 

Sorry for any spelling mistakes/inconsistencies running on empty at the moment.  With that said I will be taking a nap, so I won't read any responses for a while

 

Edit: Just looked again, and in your rotate if nItems == capacity then you don't have to do any rotations, just change the queueFront and queueBack

[alpenwasser]

Thanks alpen, I looked up the reason too

"(a/b) * b + a%b shall equal a"

Huh, good to know that this isn't just arbitrary but actually based upon reasoning,

thanks! :)

 

No. I am kinda disappointed with the instructor.

All labs come with pre-written code. Students are to write the code so that the output matches the correct output. In the zip there is a file for correct output for regular version as well as what correctarray file to match it with array.txt.

Instructor then simply runs his "python script" to compile the code, run, and compare the outputs and output files. While I admit that it is clever and makes it easier for him, I think that it's not the way to do it. For example my last lab is as efficient as I could make it (with my knowledge) and its output matches with desired output 100%. Yet I received 95%

Also previous teacher allowed to submit labs earlier and resubmit before due date. Also not to mention that there were more students in previous course. I should probably bring this up next time I talk to adviser.

That doesn't really sound like an optimal way to teach imho. Would be a lot better if

(s?)he at least posted his solution. Even better would be to get some actual feedback

on your code from the instructor, otherwise how are you supposed to improve?

Then again, I don't know how much work your teacher has to do in general, so it might

not be realistic for him to go through all the code by hand. My mum is a teacher,

and the stuff you have to do besides actual teaching around here is insane (lots of

bureaucracy, lots of unnecessary and useless seminars/courses/meetings, it's completely

nuts).

 

Preface: Since this is a Visual Studio project I can't really compile it without some

substantial tinkering (I've tried), so I can't comment on whether or not your code works.

So all my statements are based on your code and not on your program's actual behavior ;)

Anyway:

In this section:

bool Quack::popFront(char& ch){	if ( nItems == 0)		return false;		ch = items[queueFront++];	if ( queueFront >= capacity )		queueFront = queueFront - capacity;	nItems--;	return true;}

This line:

 

	ch = items[queueFront++];

I'm assuming since everything works as intended this is by design (and it's a rather

nice trick actually), but just in case you got this accidentally right, a short note

on that:

The following program:

#include <iostream>using namespace std;int main(){	char content[5]={'a','b','c','d','e'};	int index=2;	cout << content[index]<< " " << index << "\n";	cout << content[index++]<< " " << index << "\n";	cout << content[++index]<< " " << index << "\n";	return 0;}

will output this:

 

c 2c 3e 4

This is because index++ increments only after the element has been read from the

array, whereas ++index will increment index first and only then read the respective

array element. Just as a side note, since this can lead to rather tricky bugs. But

of course it's completely legitimate to make use of this feature, so I don't want

to insult your intelligence or anything. But I've seen some pretty smart and even

experienced coders stumble over this behavior. ;)

 

Edit: Just looked again, and in your rotate if nItems == capacity then you don't have to do any rotations, just change the queueFront and queueBack

I would agree with this.

 

Ok read through your code, I would recommend looking at your reverse function on a nonfull list

As an example:

 

[a b c d]

your queueFront pointing to a and queueBack pointing to b

reverse

[d c b a]

from what I read yours will now be pointing to d, and c.  Thus not reversed

 

You only need to do nItems/2 operations, but you used capacity as well

The final comment would be (capacity-1)/2 on an even numbered array (e.g. 4) will only do 1 swap instead of 2

I have gone through it with pen and paper (writing out what is done by the program),

and I get the same result. Reverse is not quite right yet.

Rotate: If I take the following:

[a b c d][F B    ]

And feed it into rotate(2), I get the following result (I think, I've only done

this with pen and paper since I can't compile the project yet):

 

[a a a d][    F B]

If you look at the first for loop in rotate():

	for (int i = 1; i <= r; i++)		{			//char temp;			//popFront(temp);			//pushBack(temp);			//popFront			char ch = items[queueFront];			queueFront = (queueFront+1) % capacity;			//pushBack			queueBack = (queueBack+1) % capacity;			items[queueBack] = ch;					}

The value that is previously stored in items[queueBack] is being

overwritten here without being preserved (from what I can tell):

			items[queueBack] = ch;						

If I do rotate(-2) on the same structure, I get the following result

(again, I haven't run the program but just done this pen/paper style,

so I might be wrong):

Input:

[a b c d][F B    ]

Output:

[a b a b][    F  ]//queueBack=-1 in this case

Again, I haven't yet found a mechanism that preserves the old value

stored in the slots being overwritten. Also, there is no catch for

queueBack going below 0.

Just for clarity, the code I'm basing this conclusion on is the following

loop in rotate:

		for (int i = 1; i <= (r*-1); i++)		{			//popBack			char ch = items[queueBack];			queueBack = (queueBack-1) % capacity;			//pushFront			queueFront = (queueFront-1) % capacity;			if (queueFront < 0)				queueFront = queueFront + capacity;			items[queueFront] = ch;		}

As I've mentioned, this is all based on pen/paper, not the actual compiled

program, so I might be wrong. Maybe I've also completely misunderstood or

overlooked something. Since you say rotate is working I think I've gotten

something wrong here, feel free to point it out.

[P1X3]

I went over the code this morning with a fresh head and thought "Who the hell wrote this code?"

But then I checked if the outputs and arrays match with what instructor provided and it's perfect match. If this was different assignment or had a meaning/purpose, for example double threaded linked list (from lab1) of wineries, then I would like it to work perfectly.

 

Once again, thank you for pointing out my mistakes and helping me get through this.

[WanderingFool]

Alphenwasser makes some good points...to Alphenwasser though there are just two details which I can help explain, why it worked

 

	for (int i = 1; i <= r; i++)		{			//char temp;			//popFront(temp);			//pushBack(temp);			//popFront			char ch = items[queueFront];			queueFront = (queueFront+1) % capacity;			//pushBack			queueBack = (queueBack+1) % capacity;			items[queueBack] = ch;					}

The value that is previously stored in items[queueBack] is being
overwritten here without being preserved (from what I can tell):

			items[queueBack] = ch;						

Alphenwasser, in this case it is acceptable to trash the items[queueBack] before queueBack is changed...assuming the array isn't full.  What ends up happening is rotating you load the front to the back, killing the back data (which is in theory "empty") and cannot be retrieved anyways.

 

And feed it into rotate(2), I get the following result (I think, I've only done
this with pen and paper since I can't compile the project yet):

the r = r%nItems protects his code from running into that issue, as the circular array would loop around.  So rotate(2) becomes rotate(0) thus reducing the operations needed.

 

 

As a side note, I decided to do the assignment (based on some of the pseudo code I posted earlier, which had a few flaws and a few gaps).  So I do have the finished results, but I won't be posting it, until the assignment is over.

[alpenwasser]

P1X3, on 10 May 2013 - 5:52 PM, said:

I went over the code this morning with a fresh head and thought "Who the hell wrote this code?"

Haha, I'm familiar with that feeling. :lol:

I've done a web project in PHP over the winter (well, the first part of if anyway, second

part will be done over the summer once I have all my computers up and running again),

and when I went over the code for some refactoring and bug fixing last month I had

the exact same thought from time to time.

It was also interesting to see that I could clearly tell my early code apart from

my newer code since my coding practices had changed quite a bit in the meantime

I'm not a professional programmer, let alone web developer, and had never done PHP

before, so it was quite interesting to actually see my learning curve represented

in the project's code.

 

P1X3, on 10 May 2013 - 5:52 PM, said:

But then I checked if the outputs and arrays match with what instructor provided and it's perfect match. If this was different assignment or had a meaning/purpose, for example double threaded linked list (from lab1) of wineries, then I would like it to work perfectly.

Once again, thank you for pointing out my mistakes and helping me get through this.

Yeah I get that, one has to be economical with one's time when it comes to school

projects. As long as it's doing what it's supposed to do within the context in which

it will be running and you understand what you've actually done the main objective

has been achieved I suppose.

[P1X3]

A "Quack" is my simplified version of the vector class from the C++ Standard Library.

Vector is used to store lists of data items.

Is this true? The "Quack" part.

[WanderingFool]

But then I checked if the outputs and arrays match with what instructor provided and it's perfect match. If this was different assignment or had a meaning/purpose

P1X3, the reverse is still wrong, you happened to get lucky the array was arranged perfectly to allow your results to match the teachers.  Adding in another reverse, but when the array is full however produces quite a different results.  I have provided the portion I tested yours with:

--> rotate -4quack: g, y, f, z, a, b, c--> reversequack: f, y, g, c, b, a, z

In general I would say this lab has quite a lot of meaning and purpose.  It enforces the concept of circular arrays, which as you write more software you might be finding yourself using them more often....linked lists are handy if you want to do something similar to circular arrays, but have flexible inserts; however the issue arises if you need the nth item in the list/array.  Circular buffer the access time is O(1), vs O(n/2) for linked list (I hope I got this right, been a while since I used big O notation).

 

A prime example of a circular buffer, which I have used, is if you are reading in data and as each piece of data arrives you only neeed the last 100 pieces, but they must come in order (Perhaps a weighted moving average).

[alpenwasser]

WanderingFool, on 10 May 2013 - 5:54 PM, said:

Alphenwasser, in this case it is acceptable to trash the items[queueBack] before queueBack is changed...assuming the array isn't full.

Yes, I see that with a not completely full array. It would cause problems

for a full one though as far as I can tell, or not?

WanderingFool, on 10 May 2013 - 5:54 PM, said:

the r = r%nItems protects his code from running into that issue, as the circular array would loop around. So rotate(2) becomes rotate(0) thus reducing the operations needed.

Hm, I think I might be overlooking something here. To avoid misunderstandings,

you are talking about line 5 in the following code, correct?

void Quack::rotate(int r){	// Avoid extra rotations if nItems = 2 and rotate(5) is called	if (r > nItems)		r = r % nItems;	// 	if (r > nItems/2)		r = r - nItems;	if (r > 0)	{		for (int i = 1; i <= r; i++)		{			//char temp;			//popFront(temp);			//pushBack(temp);			//popFront			char ch = items[queueFront];			queueFront = (queueFront+1) % capacity;			//pushBack			queueBack = (queueBack+1) % capacity;			items[queueBack] = ch;					}	}	else	{		for (int i = 1; i <= (r*-1); i++)		{			//popBack			char ch = items[queueBack];			queueBack = (queueBack-1) % capacity;			//pushFront			queueFront = (queueFront-1) % capacity;			if (queueFront < 0)				queueFront = queueFront + capacity;			items[queueFront] = ch;		}	}}

With the following array:

[a b c d] // from what I can tell, nItems is 4 here?[F B    ]

I get with rotate(2):

if (r > nItems) // Evaluates to false, since 2 is not >4		r = r % nItems; // Is not executed, but would be 2%4=2, so not 0, I think?	// 	if (r > nItems/2) // Evaluates to false since nItems/2=2 and r=2 as far as I can tell		r = r - nItems; //Not executed

I don't quite get to r=0 with this. If this doesn't make sense I can

write down my complete train of thought, maybe that would help?

WanderingFool, on 10 May 2013 - 5:54 PM, said:

As a side note, I decided to do the assignment (based on some of the pseudo code I posted earlier, which had a few flaws and a few gaps). So I do have the finished results, but I won't be posting it, until the assignment is over.

It's definitely a nice exercise imho, especially to revive my admittedly slightly

rusty C++ again (haven't really used it since summer of 2010 :( ). I might actually

do this myself when (if) I get the time, or something similar and inspired by it.

But at the moment Perl is taking up most of my coding time, and the rest goes

to my dog and building some new PC's for our household. :lol:

WanderingFool, on 10 May 2013 - 6:14 PM, said:

In general I would say this lab has quite a lot of meaning and purpose. It enforces the concept of circular arrays, which as you write more software you might be finding yourself using them more often....linked lists are handy if you want to do something similar to circular arrays, but have flexible inserts; however the issue arises if you need the nth item in the list/array. Circular buffer the access time is O(1), vs O(n/2) for linked list (I hope I got this right, been a while since I used big O notation).

A prime example of a circular buffer, which I have used, is if you are reading in data and as each piece of data arrives you only neeed the last 100 pieces, but they must come in order (Perhaps a weighted moving average).

I've actually thought about doing this with a linked list, or even something completely

different (there are lots of interesting data structures out there waiting to be explored

by the curious mind :lol: ). But before that, I would definitely do it more or less like

demanded by this problem.

[WanderingFool]

Yes, I see that with a not completely full array. It would cause problems

for a full one though as far as I can tell, or not?

Hm, I think I might be overlooking something here. To avoid misunderstandings,

you are talking about line 5 in the following code, correct?

 

With the following array:

[a b c d] // from what I can tell, nItems is 4 here?[F B    ]

I get with rotate(2):

if (r > nItems) // Evaluates to false, since 2 is not >4		r = r % nItems; // Is not executed, but would be 2%4=2, so not 0, I think?

I don't quite get to r=0 with this. If this doesn't make sense I can

write down my complete train of thought, maybe that would help?

 

Oh bother, sorry my bad, you are right...I totally ignored the if statement :P .  On another note capacity = 4, nItems = 2 in your example.  P1X3 you don't need the if statement....just go r = r%nItems, no matter what r is.

 

Assuming there is no if statement though, I believe it should be correct