Dynamic Array - Copy Constructor

[Duki]

Hey guys, I have a function that compares two dynamic arrays and returns true or false if they're identical.

bool Identical(QueType que1, QueType que2)
{
	if (que1.IsEmpty() != true && que2.IsEmpty() != true)
	{
		cout << "in loop\n" ;
		ItemType tmp1 ;
		ItemType tmp2 ;
		que1.Dequeue(tmp1) ;
		que2.Dequeue(tmp2) ;

		if (tmp1 == tmp2)
			Identical(que1, que2) ;
		else
			return false ;

		que1.Enqueue(tmp1) ;
		que2.Enqueue(tmp2) ;
	}
	return true ;
}

I keep getting a runtime error at the very end of this code. I know it's when the function exits because I've put cout << statements at the very end before it returns to main().

I assume this has something to do with the copying being shallow instead of deep, and it's trying to destruct already-destrcuted memory... but i'm not sure.

Please help!

[vmanes]

It would help if you told us exactly what the error message was.

I think I see a couple flaws in the logic of this.
1 - If two dequeued objects are not equivalent, you return false to the previous instance of the function, and those two items do not get put back on the queue.

2 - That return of false has no real effect, as it's returning back to line 12. From there, you jump over the else, requeue the previously removed objects, leave the big if block, and return true in all cases.

3 - (Ok, not a couple) If one queue is empty and the other is not, the if at line 3 fails, you drop down and return - true. I think you need and else clause here.

[siddhant3s]

Have you defined your own copy-constructor, or using the default one?

(que1.IsEmpty() != true && que2.IsEmpty() != true ) is depreciated. Use

( !que1.IsEmpty() && !que2.IsEmpty() )

vmanes is rather right. you must construct a else case also.

Another point to note is, you should avoid recursions as far as possible. This problem could have been done without recursion .

[Duki]

Thanks guys.
I realize I could do without recursion, but it was (for once) the first solution that came to mind.. so I thought what the heck, lets try it.

I'll fix the errors you've noted, thanks!

I don't think I can use the default copy-ctor because once it leaves the function it will destruct my dynamic memory won't it? I've written my own, I don't have it with me but it's something similar to this:

QueType::QueType(QueType const& other)
{
     size = other.size ;
     ItemType * tmp = new ItemType[size] ;
     for (int i = 0 ; i < size ; i++)
           tmp[i] = other.items[i] ;
}

As far as the actual error, I can't remember it really, but I always get this error when trying to pass dynamic memory to a function.
I've read about functions like memcpy() or copy() (in <algorithm>), but I have no clue how to use these.

Thanks again for giving me a hand.

[siddhant3s]

>I don't think I can use the default copy-ctor
Yes you are right. That's why I ask to check if you were stupid enough to use them. So it turns out that you are smart enough.

>I don't have it with me but it's something similar to this
This looks good, but the only problem is that tmp is getting wasted. I mean you need to set some of your data member(which is Pointer to ItemType) to tmp.

[Duki]

I don't understand. How do I set data to tmp?

[siddhant3s]

>I don't understand. How do I set data to tmp?
You would, just look at the piece below:

class Foo
{
int *A;
int B
public
Foo():{A=new int; B=0;}
Foo(const Foo& other)
{
int *tmp= new int;
*tmp=*other.A;
//////////////
A=tmp;//You did not do this step
}
};

[Duki]

Ok, here's my code thus far:

// Test driver
#include "QueType.h"

bool Identical(QueType que1, QueType que2) ;
	// Function:  Determines if two queues are identical.
	// Pre:		que1 and que2 have been initialzed.
	// Post:	Queues are unchanged.
	//			Function value = (queue 1 and queue 2 are identical).

int main()
{
	QueType que ;
	ItemType a = 'a' ;
	ItemType b = 'b' ;
	ItemType c = 'c' ;
	ItemType d = 'd' ;
	ItemType e = 'e' ;
	ItemType f = 'f' ;

	que.Enqueue(a) ;
	que.Enqueue(b) ;
	que.Enqueue(c) ;
	que.Enqueue(d) ;
	que.Enqueue(e) ;
	que.Enqueue(f) ;

	for (int i = 1 ; i <= 6 ; i++)
	{
		ItemType tmp ;
		que.Dequeue(tmp) ;
		cout << "Item " << i << ":  " << tmp << endl ;
	}

	que.Enqueue(a) ;
	que.Enqueue(b) ;
	que.Enqueue(c) ;
	que.Enqueue(d) ;
	que.Enqueue(e) ;
	que.Enqueue(f) ;

	QueType queTwo ;

	queTwo.Enqueue(a) ;
	queTwo.Enqueue(b) ;
	queTwo.Enqueue(c) ;
	queTwo.Enqueue(d) ;
	queTwo.Enqueue(e) ;
	queTwo.Enqueue(f) ;

	bool iden ;
	iden = Identical(que, queTwo) ;

	if (iden)
		cout << "Identical!\n" ;
	else
		cout << "Not Identical!\n" ;


	return 0;
}

bool Identical(QueType que1, QueType que2)
{
	if (que1.IsEmpty() != true && que2.IsEmpty() != true)
	{
		cout << "in loop\n" ;
		ItemType tmp1 ;
		ItemType tmp2 ;
		que1.Dequeue(tmp1) ;
		que2.Dequeue(tmp2) ;
		cout << "Que 1, Item:  " << tmp1 << endl ;
		cout << "Que 2, Item:  " << tmp2 << endl ;

		if (tmp1 == tmp2)
			Identical(que1, que2) ;
		else
		{
			que1.Enqueue(tmp1) ;
			que2.Enqueue(tmp2) ;
			return false ;
		}

		que1.Enqueue(tmp1) ;
		que2.Enqueue(tmp2) ;
	}
	return true ;
}

#pragma once ;
#include <algorithm> ;
#include <iostream>
#include "QueType.h"
using namespace std;

class FullQueue
{};  

class EmptyQueue
{};  
typedef char ItemType;
class QueType
{
public: 
    QueType();
    // Class constructor.
    // Because there is a default constructor, the precondition 
    // that the queue has been initialized is omitted.
	QueType(QueType const& copy) ;
    QueType(int max);
    // Parameterized class constructor.
    ~QueType();
    // Class destructor.
    void MakeEmpty();
    // Function: Initializes the queue to an empty state.
    // Post: Queue is empty.
    bool IsEmpty() const;
    // Function: Determines whether the queue is empty.
    // Post: Function value = (queue is empty)
    bool IsFull() const;
    // Function: Determines whether the queue is full.
    // Post: Function value = (queue is full)
    void Enqueue(ItemType newItem);
    // Function: Adds newItem to the rear of the queue.
    // Post: If (queue is full) FullQueue exception is thrown
    //       else newItem is at rear of queue.
    void Dequeue(ItemType& item);
    // Function: Removes front item from the queue and returns it in item.
    // Post: If (queue is empty) EmptyQueue exception is thrown
    //       and item is undefined
    //       else front element has been removed from queue and
    //       item is a copy of removed element.
private:
	int size ;
    int front;
    int rear;
    ItemType* items;
    int maxQue;
};

#include "QueType.h"

QueType::QueType(int max)
// Parameterized class constructor
// Post: maxQue, front, and rear have been initialized.
//       The array to hold the queue elements has been dynamically
//       allocated.
{
  maxQue = max + 1;
  front = maxQue - 1;
  rear = maxQue - 1;
  size = 0 ;
  items = new ItemType[maxQue];
}
QueType::QueType()          // Default class constructor
// Post: maxQue, front, and rear have been initialized.
//       The array to hold the queue elements has been dynamically
//       allocated.
{
  maxQue = 501;
  front = maxQue - 1;
  rear = maxQue - 1;
  items = new ItemType[maxQue];
  size = 0 ;
}
QueType::QueType(QueType const& other)
{
	ItemType * tmp = new ItemType[other.size] ;
	size = other.size ;
	for (int i = 0 ; i < size ; i++)
	{
		tmp[i] = other.items[i] ;
		cout << "Copied item " << tmp[i] << " into tmp" << endl ;
	}
	items = tmp ;
}

QueType::~QueType()         // Class destructor
{
  delete [] items;
}

void QueType::MakeEmpty()
// Post: front and rear have been reset to the empty state.
{
  front = maxQue - 1;
  rear = maxQue - 1;
}

bool QueType::IsEmpty() const
// Returns true if the queue is empty; false otherwise.
{
  return (rear == front);
}

bool QueType::IsFull() const
// Returns true if the queue is full; false otherwise.
{
  return ((rear + 1) % maxQue == front);
}

void QueType::Enqueue(ItemType newItem)
// Post: If (queue is not full) newItem is at the rear of the queue;
//       otherwise a FullQueue exception is thrown.  
{
  if (IsFull())
    throw FullQueue();
  else
  {
    rear = (rear +1) % maxQue;
    items[rear] = newItem;
	size++ ;
  }
}

void QueType::Dequeue(ItemType& item)
// Post: If (queue is not empty) the front of the queue has been 
//       removed and a copy returned in item; 
//       othersiwe a EmptyQueue exception has been thrown.
{
  if (IsEmpty())
    throw EmptyQueue();
  else
  {
    front = (front + 1) % maxQue;
    item = items[front];
	size-- ;
  }
}

And here is the output I get before it explodes:

Item 1: a
Item 2: b
Item 3: c
Item 4: d
Item 5: e
Item 6: f
Copied item a into tmp
Copied item b into tmp
Copied item c into tmp
Copied item d into tmp
Copied item e into tmp
Copied item f into tmp
Copied item a into tmp
Copied item b into tmp
Copied item c into tmp
Copied item d into tmp
Copied item e into tmp
Copied item f into tmp
in loop

Then I get a windows run-time error saying the program has stopped working. :(

[Duki]

I get the same error when I'm not using recursion. Here's my non-recursive version:

bool Identical(QueType que1, QueType que2)
{
	bool iden = true ;
	if (que1.GetLen() == que2.GetLen())
	{
		cout << "in loop" << endl ;
		ItemType tmp ;
		ItemType tmp2 ;
		for (int i = 0 ; i < que1.GetLen() ; i++)
		{
			cout << "for loop" << endl ;
			que1.Dequeue(tmp);
			que2.Dequeue(tmp2);
			if (tmp != tmp2)
				 iden = false ;
			que1.Enqueue(tmp) ;
			que2.Enqueue(tmp2) ;
		}
	}
	else
		iden = false ;

	return iden ;
}

It blows up right before the first Dequeue().
Am I still not doing something right in my copy-ctor?

[Duki]

Ok here's my latest code (using the non-recursive version). And I'm stuck.

#pragma once

#include <iostream>
using namespace std;

class FullQueue
{};  

class EmptyQueue
{};  
typedef char ItemType;
class QueType
{
public: 
    QueType();
    // Class constructor.
    // Because there is a default constructor, the precondition 
    // that the queue has been initialized is omitted.
    QueType(int max);
    // Parameterized class constructor.
	QueType(const QueType& other);
	// Copy constructor.
    ~QueType();
    // Class destructor.
    void MakeEmpty();
    // Function: Initializes the queue to an empty state.
    // Post: Queue is empty.
    bool IsEmpty() const;
    // Function: Determines whether the queue is empty.
    // Post: Function value = (queue is empty)
    bool IsFull() const;
    // Function: Determines whether the queue is full.
    // Post: Function value = (queue is full)
    void Enqueue(ItemType newItem);
    // Function: Adds newItem to the rear of the queue.
    // Post: If (queue is full) FullQueue exception is thrown
    //       else newItem is at rear of queue.
    void Dequeue(ItemType& item);
    // Function: Removes front item from the queue and returns it in item.
    // Post: If (queue is empty) EmptyQueue exception is thrown
    //       and item is undefined
    //       else front element has been removed from queue and
    //       item is a copy of removed element.
	int GetLen() ;
private:
    int front;
    int rear;
	int size ;
    ItemType* items;
    int maxQue;
};


#include "QueType.h"

QueType::QueType(int max)
// Parameterized class constructor
// Post: maxQue, front, and rear have been initialized.
//       The array to hold the queue elements has been dynamically
//       allocated.
{
  maxQue = max + 1;
  front = maxQue - 1;
  rear = maxQue - 1;
  items = new ItemType[maxQue];
  size = 0 ;
}
QueType::QueType()          // Default class constructor
// Post: maxQue, front, and rear have been initialized.
//       The array to hold the queue elements has been dynamically
//       allocated.
{
  maxQue = 501;
  front = maxQue - 1;
  rear = maxQue - 1;
  items = new ItemType[maxQue];
  size = 0 ;
}
QueType::~QueType()         // Class destructor
{
  delete [] items;
}

QueType::QueType(const QueType& other)	//copy c-tor
{
	ItemType * tmp = new ItemType[other.size] ;
	size = other.size ;
	for (int i = 0 ; i < size ; i++)
	{
		tmp[i] = other.items[i] ;
		cout << "Copied item " << tmp[i] << " into tmp" << endl ;
	}

	items = tmp ;
	front = other.front ;
	rear = other.rear ;
	size = other.size ;
	maxQue = other.maxQue ;

	cout << items[size-1] << endl ;
	cout << tmp[size-1] << endl ;
}

void QueType::MakeEmpty()
// Post: front and rear have been reset to the empty state.
{
  front = maxQue - 1;
  rear = maxQue - 1;
}

bool QueType::IsEmpty() const
// Returns true if the queue is empty; false otherwise.
{
  return (rear == front);
}

bool QueType::IsFull() const
// Returns true if the queue is full; false otherwise.
{
  return ((rear + 1) % maxQue == front);
}

void QueType::Enqueue(ItemType newItem)
// Post: If (queue is not full) newItem is at the rear of the queue;
//       otherwise a FullQueue exception is thrown.  
{
  if (IsFull())
    throw FullQueue();
  else
  {
    rear = (rear +1) % maxQue;
    items[rear] = newItem;
	size++;
  }
}

void QueType::Dequeue(ItemType& item)
// Post: If (queue is not empty) the front of the queue has been 
//       removed and a copy returned in item; 
//       othersiwe a EmptyQueue exception has been thrown.
{
  if (IsEmpty())
    throw EmptyQueue();
  else
  {
    front = (front + 1) % maxQue;
    item = items[front];
	size-- ;
  }
}

int QueType::GetLen()
{
	return size ;
}


// Test driver
#include "QueType.h"

bool Identical(QueType que1, QueType que2) ;
// Function:  Determines if two queues are identical
// Pre:		  que1 and que2 have been initialized
// Post:	  Queues are unchanged.
//			  Function value = (que1 and que2 are identical).
  
int main()
{
	QueType que ;
	ItemType a = 'a' ;
	ItemType b = 'b' ;
	ItemType c = 'c' ;
	ItemType d = 'd' ;
	ItemType e = 'e' ;
	ItemType f = 'f' ;

	que.Enqueue(a) ;
	que.Enqueue(b) ;
	que.Enqueue(c) ;
	que.Enqueue(d) ;
	que.Enqueue(e) ;
	que.Enqueue(f) ;

	for (int i = 1 ; i <= que.GetLen() ; i++)
	{
		ItemType tmp ;
		que.Dequeue(tmp) ;
		cout << "Item " << i << ":  " << tmp << endl ;
		que.Enqueue(tmp) ;
	}

	QueType queTwo ;

	queTwo.Enqueue(a) ;
	queTwo.Enqueue(b) ;
	queTwo.Enqueue(c) ;
	queTwo.Enqueue(d) ;
	queTwo.Enqueue(e) ;
	queTwo.Enqueue(f) ;

	bool iden ;
	iden = Identical(que, queTwo) ;

	if (iden)
		cout << "Test #1:  Identical!\n" ;
	else
		cout << "Test #1:  Not Identical!\n" ;

	for (int i = 1 ; i <= que.GetLen() ; i++)
	{
		ItemType tmp ;
		que.Dequeue(tmp) ;
		cout << "Item " << i << ":  " << tmp << endl ;
	}

	return 0;
}

bool Identical(QueType que1, QueType que2)
{
	bool iden = true ;
	if (que1.GetLen() == que2.GetLen())
	{
		cout << "in loop" << endl ;
		ItemType tmp ;
		ItemType tmp2 ;
		for (int i = 0 ; i < que1.GetLen() ; i++)
		{
			cout << "for loop" << endl ;
			que1.Dequeue(tmp);
			que2.Dequeue(tmp2);
			cout << "\ntmp dQ:  " << tmp << endl ;
			cout << "tmp2 dQ:  " << tmp2 << endl ;
			if (tmp != tmp2)
			{
				 iden = false ;
				 break ;
			}
			que1.Enqueue(tmp) ;
			que2.Enqueue(tmp2) ;
		}
	}
	else
		iden = false ;

	return iden ;
}

And here's the output I get:

Item 1: a
Item 2: b
Item 3: c
Item 4: d
Item 5: e
Item 6: f
Copied item a into tmp
Copied item b into tmp
Copied item c into tmp
Copied item d into tmp
Copied item e into tmp
Copied item f into tmp
f
f
Copied item a into tmp
Copied item b into tmp
Copied item c into tmp
Copied item d into tmp
Copied item e into tmp
Copied item f into tmp
f
f
in loop
for loop

tmp dQ: ²
tmp2 dQ: a
Test #1: Not Identical!
Item 1: a
Item 2: b
Item 3: c
Press any key to continue . . .

What am I doing wrong?

[John A]

Your copy constructor is broken. You copy from 0..size, which is incorrect because you're assuming that your data starts at 0. Instead you should copy from front+1..rear (remembering to wrap to your maxQue).

[Duki]

Well, crap. Now I get this:

Item 1: a
Item 2: b
Item 3: c
Item 4: d
Item 5: e
Item 6: f
═
═
Copied item a into tmp
Copied item b into tmp
Copied item c into tmp
Copied item d into tmp
Copied item e into tmp
═
═
in loop
for loop

tmp dQ: a
tmp2 dQ: ═

Here is my updated copy c-tor:

QueType::QueType (QueType const& other)	//copy c-tor
{
	ItemType * tmp = new ItemType[other.size] ;
	size = other.size ;
	for (int i = (other.front + 1) ; i < other.rear ; i++)
	{
		tmp[i] = other.items[i] ;
		cout << "Copied item " << tmp[i] << " into tmp" << endl ;
	}

	items = tmp ;
	front = other.front ;
	rear = other.rear ;
	size = other.size ;
	maxQue = other.maxQue ;

	cout << items[size-1] << endl ;
	cout << tmp[size-1] << endl ;
}