What the hell? (Coding C++) = solved!

<3

Ok I have a queue and I'm trying to count the number of nodes in the queue.

this is the get length function

int List::Length()
{
   PtrType Temp = Head;
   int length = 0;
   
   while(Temp != NULL)
   {
      length++;
      Temp = Temp->Next;
   }
   return length;
}

For some odd reason it is not traversing through the queue and just returning whatever I set "int length" to be. In this case, 0.

I also have a Print function with is exactly the same

void List::Print() const
{
   PtrType Temp = Head;
   
   while (Temp != NULL)
   {
      cout <<endl<<Temp->Item;
      Temp = Temp->Next;
   }
   cout << endl;
}

This, however, works. It goes through the queue and prints all the nodes.

I don't see what is wrong here.

Valkun

Post the entire code.

Spackle

Hmmm

This is a Queue. This might be a bit off but I'm used to thinking of Queues where the head is the front of the queue like this:

Queue:
|# # # # # # #|
^back(rear)     ^front(head)

So it seems that if this is how your Queue is and you're calculating the length starting from the front, you'll always get 0 because you're going from the front node and trying to go forward but there is nothing there.

Maybe count backwards to the rear? I apologize if this is not your design, just a thought.

Valkun

Spackle, I think you might be confusing a graphical representation of a queue with how it's actually structured.

[Head]->[node]->[node]->[node]->null

==

null<-[node]<-[node]<-[node]<-[Head]

Assuming the queue is made up of a singly linked list, "next" will point to the next node in the queue regardless of its position. Even if the queue in question was doubly linked and Length() was trying to traverse it in the wrong direction, length would still appear as 1.

lowlylowlycook

Are you running it in a debugger? For something like this, stepping through should lead to enlightenment. I for one don't see any errors off hand.

Spackle

Valkun wrote: »

Spackle, I think you might be confusing a graphical representation of a queue with how it's actually structured.

[Head]->[node]->[node]->[node]->null

==

null<-[node]<-[node]<-[node]<-[Head]

Assuming the queue is made up of a singly linked list, "next" will point to the next node in the queue regardless of its position. Even if the queue in question was doubly linked and Length() was trying to traverse it in the wrong direction, length would still appear as 1.

Ah yea good point. Been awhile since C++, data structures are nicely done in .NET so I rarely have to think about the guts. I should have read the whole post anyways as he states that the print function does work.

D'oh! :P

<3

void List::Print() const
{
  PtrType Temp = Head;
  int len = 0;
 
  while (Temp != NULL)
  {
      cout <<endl<<Temp->Item;
      len++;
      Temp = Temp->Next;
  }
  cout endl << len << endl;
}
}

This prints the correct length of the queue. So why is the length function not working when they are the exact same thing?

Janin

Sounds like some sort of memory corruption. Post the entire code.

<3

main.cpp

#include "Vendor.h"
#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

int main(int argc, char * argv[])
{
	srand(time(NULL));

	int numCustomers = 0;
	int numVendors = 0;
	
	cout << "Enter number of customers: ";
	cin >> numCustomers;
	cout << "Enter number of vendors: ";
	cin >> numVendors;

	Queue eventList;
	int ArrivalTime = 0;
	for(int i = 0; i < numCustomers; i++)
	{
		ArrivalTime += (rand() &#37; 10 + 1);
		eventList.enqueue(ArrivalTime);
	}

	Vendor* vendorQueue = new Vendor[numVendors];
	int currentTime = 0;

	while(numCustomers != 0)
	{
		int value = 0;
		eventList.Top(value);

		if(currentTime == value)
		{
			cout << "A customer arrive at " << currentTime << endl;
			eventList.dequeue(value);

			int shortest = vendorQueue[0].getLength();
			int line = 0;
			for(int i = 1; i < numVendors; i++)
			{
				if(vendorQueue[i].getLength() < shortest)
				{
					shortest = vendorQueue[i].getLength();
					line = i;
				}
			}
			
			cout << "Vendor length " << vendorQueue[0].getLength() << endl;
			vendorQueue[0].Print();

			int buyItems = rand() % 10 + 1;
			cout << "Cutomer buys " << buyItems << " items from vendor" << line << " and this will take " << buyItems * vendorQueue[line].getVendingSpeed() << " seconds" << endl;
			vendorQueue[line].enqueue(buyItems * vendorQueue[line].getVendingSpeed());
			vendorQueue[line].handleCustomer();
		}

		++currentTime;
		for(int i = 0; i < numVendors; i++)
		{
			vendorQueue[i].TimeElapsed();

			vendorQueue[i].Top(value);
			if(value == 0)
			{
				vendorQueue[i].dequeue(value);
				--numCustomers;
			}	
		}
	}
	
	
	cout << currentTime << endl;

	return 0;
}

Vendor.h

#include "Queue.h"

class Vendor: public Queue
{
public:
	Vendor();		//default constructor
	~Vendor();	//the destructor

	int getVendingSpeed();
	int getCount();
	bool handleCustomer();
	int getLength();

private:

	int speed;
	int count;
	List vendor;
};

Vender.cpp

#include "Vendor.h"
#include <stdlib.h>
#include <time.h>
using namespace std;

Vendor::Vendor()
{
	speed = 30;
	count = 0;
}

Vendor::~Vendor()
{
}

int Vendor::getVendingSpeed()
{
	return speed;
}

int Vendor::getCount()
{
	return count;
}

bool Vendor::handleCustomer()
{
	++count;
	return true;
}

int Vendor::getLength()
{
	return vendor.Length();
}

Queue.h

#include "List.h"

//The class definition for the Queue
class Queue
{
public:
   Queue();		//default constructor
   ~Queue();	//the destructor

   bool enqueue (const int Value);
   bool dequeue (int &Value);
   bool Top (int &Value) const;
   bool IsEmpty() const;
   void Print();
   void TimeElapsed();

private:
   List queue;	//Linked list based stack declaration
};

Queue.cpp

#include "Queue.h"
using namespace std;

/************The implentation of the "Queue" functions***********/

/* Default constructor - does nothing, 
the default constructor for List handles it */
Queue::Queue()
{
}


/* Default destructor - handled by List default constructor. */
Queue::~Queue()
{
}

/* Add a value to the queue. */
bool Queue::enqueue( const int Value )
{
   return (queue.AddToEnd (Value)); 
}

/* Remove a value from the queue. */
bool Queue::dequeue( int &Value )
{
   return (queue.RemoveFromFront (Value));
}

/* Return the top value from the queue. */
bool Queue::Top( int &Value ) const
{
   return (queue.PeekFirst (Value));
}

/* Return whether or not the queue is empty. */
bool Queue::IsEmpty() const
{
   return (queue.IsEmpty());
}

/*Print the contents of the queue*/
void Queue::Print()
{  
   cout<<"The contents of your queue: ";
   queue.Print();
}

void Queue::TimeElapsed()
{
	queue.Decrement();
}

List.h

#include <iostream>

struct NodeType;
typedef NodeType* PtrType;


//The class declaration for the Linked list data structure
class List
{
public:
   List();                    // default constructor
   List (const List& L);      // copy constructor
   ~List();                   // destructor

   bool AddToFront (const int Item);
   bool AddToEnd (const int Item);
   bool RemoveFromFront (int &Item);
   bool IsEmpty() const;
   bool PeekFirst (int &Item) const;
   void Print() const;
   void Decrement();
   int Length();

private:
   PtrType Head;              
   PtrType Tail;              
};

List.cpp

/*********The implementation of the linked list functions********/
#include "List.h"
using namespace std;

struct NodeType
{
   int Item;
   PtrType Next;
};
          
// ------------------------ constructors and destructors ----------------
// The default constructor
List::List()
{
   Head = NULL;
   Tail = NULL;
};


// The copy constructor
List::List (const List& L)
{
PtrType Cur = L.Head;         // the current node in the original list

   Head = NULL;               // copy is initially empty
   Tail = NULL;

   // loop through the original list, copying nodes one at a time
   while (Cur != NULL)
   {
     AddToEnd (Cur->Item);
     Cur = Cur->Next;
   }
};


// The destructor
List::~List()
{
PtrType Temp;

   // loop through whole list deleting nodes
   while (Head != NULL)
   {
      Temp = Head;
      Head = Head->Next;
      delete Temp;
   }
   Tail = NULL;
};

/*To add a node to the front of the linked list*/
bool List::AddToFront (const int Item)
{
PtrType NewNode;
    
   // make the space for the new node and store the data
   NewNode = new NodeType;
   if (!NewNode)
      return (false);
   else
   {
      NewNode->Item = Item;

      // point from this node to the previous head of the list
      NewNode->Next = Head;

      // if this is the first node in the list, it is also the last node
      if (Head == NULL)
         Tail = NewNode;
 
      // make the head of the list point to this node
      Head = NewNode;
      return (true);
   }
    
};

/*To add a node to the end of the linked list*/
bool List::AddToEnd (const int Item)
{
PtrType NewNode;
      
   /* First make the new node and store the data */
   NewNode = new NodeType;
   if (!NewNode)
      return (false);
   else
   {
      NewNode->Item = Item;
 
      /* Point from this node to NULL (it's the end). */
      NewNode->Next = NULL;

      if (Tail == NULL)
         Head = NewNode;        // this is the first node in the list
      else
         Tail->Next = NewNode;  // add after old end
      
      Tail = NewNode;           // this is the new end
      return (true);
   }
};

/*To remove a node from the front of the linked list*/
bool List::RemoveFromFront (int &Item)
{   
   if (Head == NULL)
      return (false);
   else
   {
      Item = Head->Item;
      Head = Head->Next;

      /* if this was the last node in the list, reset Tail */
      if (Head == NULL)
         Tail = NULL;

	  return (true);
   }  
}

/*To check if the linked list is empty*/
bool List::IsEmpty() const
{
   return (Head == NULL);
}

/*To return the first item at the head of the linked list*/
bool List::PeekFirst(int &Item) const
{   
   if (Head == NULL)
      return (false);
   else
   {
      Item = Head->Item;
      return (true);
   }
}     
 
/*To print the contents of the linked list*/
void List::Print() const
{
   PtrType Temp = Head;
   
   // loop through whole list printing nodes
   while (Temp != NULL)
   {
      cout <<endl<<Temp->Item;
      Temp = Temp->Next;
   }
   cout << endl;
}

int List::Length()
{
   PtrType Temp = Head;
   int length = 0;

   while(Temp != NULL)
   {
      length++;
      Temp = Temp->Next;
   }
   return length;
}

void List::Decrement()
{
	if(Head != NULL)
		Head->Item--;
}

Output

Enter number of customers: 15
Enter number of vendors: 1
A customer arrive at 2
Vendor length 0
The contents of your queue:
Cutomer buys 2 items from vendor0 and this will take 60 seconds
A customer arrive at 11
Vendor length 0
The contents of your queue:
51
Cutomer buys 8 items from vendor0 and this will take 240 seconds
A customer arrive at 20
Vendor length 0
The contents of your queue:
42
240
Cutomer buys 6 items from vendor0 and this will take 180 seconds
A customer arrive at 25
Vendor length 0
The contents of your queue:
37
240
180
Cutomer buys 9 items from vendor0 and this will take 270 seconds
A customer arrive at 31
Vendor length 0
The contents of your queue:
31
240
180
270
Cutomer buys 8 items from vendor0 and this will take 240 seconds
A customer arrive at 41
Vendor length 0
The contents of your queue:
21
240
180
270
240
Cutomer buys 2 items from vendor0 and this will take 60 seconds
A customer arrive at 42
Vendor length 0
The contents of your queue:
20
240
180
270
240
60
Cutomer buys 7 items from vendor0 and this will take 210 seconds
A customer arrive at 44
Vendor length 0
The contents of your queue:
18
240
180
270
240
60
210
Cutomer buys 6 items from vendor0 and this will take 180 seconds
A customer arrive at 48
Vendor length 0
The contents of your queue:
14
240
180
270
240
60
210
180
Cutomer buys 3 items from vendor0 and this will take 90 seconds
A customer arrive at 54
Vendor length 0
The contents of your queue:
8
240
180
270
240
60
210
180
90
Cutomer buys 1 items from vendor0 and this will take 30 seconds
A customer arrive at 58
Vendor length 0
The contents of your queue:
4
240
180
270
240
60
210
180
90
30
Cutomer buys 5 items from vendor0 and this will take 150 seconds
A customer arrive at 67
Vendor length 0
The contents of your queue:
235
180
270
240
60
210
180
90
30
150
Cutomer buys 9 items from vendor0 and this will take 270 seconds
A customer arrive at 72
Vendor length 0
The contents of your queue:
230
180
270
240
60
210
180
90
30
150
270
Cutomer buys 3 items from vendor0 and this will take 90 seconds
A customer arrive at 76
Vendor length 0
The contents of your queue:
226
180
270
240
60
210
180
90
30
150
270
90
Cutomer buys 4 items from vendor0 and this will take 120 seconds
A customer arrive at 82
Vendor length 0
The contents of your queue:
220
180
270
240
60
210
180
90
30
150
270
90
120
Cutomer buys 7 items from vendor0 and this will take 210 seconds
2402
Press any key to continue

Valkun

Vendor::Vendor()
{
speed = 30;
count = 0;
//Should include:
//vendor = new List();
}

It looks like you're not initializing the vendor (list).

Senjutsu

Valkun wrote: »

Vendor::Vendor()
{
speed = 30;
count = 0;
//Should include:
//vendor = new List();
}

It looks like you're not initializing the vendor (list).

It's on the stack according to Vendor.h

Janin

I don't think the problem lies in your List class - I created a small test program, and it seemed to work.

int main ()
{
	List list;
	list.AddToEnd (1);
	list.AddToEnd (2);
	list.AddToEnd (3);
	cout << "list.Length = " << list.Length () << "\n";
	cout << "--printing list--\n";
	list.Print ();
	return 0;
}

list.Length = 3
--printing list--

1
2
3

Valkun

Senjetsu wrote:

It's on the stack according to Vendor.h

Yes, a reference to a List type object is declared, but it's never actually constructed as far as I can tell.

jmillikin, will you try adding "vendor = new List();" to Vendor's constructor?

<3

int List::Length()
{
  PtrType Temp = Head;
  int length = 0;

  while(Temp != NULL)
  {
      length++;
      Temp = Temp->Next;
  }
  return length;
}

I think it's not going through the while loop because for some reason Temp here is always NULL.

if I change while loop in to do while loop, it gives me segfault.

Valkun

It's because you're trying to use a list that hasn't been constructed, ie the one in your vendor class.

Senjutsu

Valkun wrote: »

Senjetsu wrote:

It's on the stack according to Vendor.h

Yes, a reference to a List type object is declared, but it's never actually constructed as far as I can tell.

Java programmer?

"List* foo;" is a reference to a List that needs to be assigned to, the equivalent of Java's "List foo;"

"List foo;", in C++, however, constructs a new List object on the stack instead of the heap. There's no equivalent in Java.

Janin

, the problem is not in List::Length. For some reason, Head is being set to NULL. Furthermore, because your main incorporates random behaviour I cannot know what the correct output would be. If you can reduce your main to where the problem is easy to check, I can help further.

Philodox

Do you have access to a debugger? Put a breakpoint in your length function and step through the function. I plugged your length function into a linked list class I wrote and it worked fine.

*edit* people beat me to it

Valkun

Hmm, it's possible I am getting confused. Taking a Concepts of Programming Languages course this semester. Using Fortran, Java, Javascript, Lisp, Prolog, C, C++, and Perl all at once is bound to obfuscate things.

And yes, Java and C++ are my most experienced languages.

Ok assuming that the list is being created. Nothing is being added to them before calling their lengths. Not to mention that enqueue adds items to the "queue" while getLength is using the list "vendor".

Senjutsu

Here's your problem, I think:

int shortest = vendorQueue[0].getLength();
                        int line = 0;
                        for(int i = 1; i < numVendors; i++)
                        {
                                if(vendorQueue[i].getLength() < shortest)
                                {
                                        shortest = vendorQueue[i].getLength();
                                        line = i;
                                }
                        }
                        
                        cout << "Vendor length " << vendorQueue[0].getLength() << endl;
                        vendorQueue[0].Print();

                        int buyItems = rand() &#37; 10 + 1;
                        cout << "Cutomer buys " << buyItems << " items from vendor" << line << " and this will take " << buyItems * vendorQueue[line].getVendingSpeed() << " seconds" << endl;
                        vendorQueue[line].enqueue(buyItems * vendorQueue[line].getVendingSpeed());
                        vendorQueue[line].handleCustomer();

Ok, so when you first go through this, there's nothing in vendorQueue, so shortest is 0. Line gets set to 0. if(vendorQueue.getLength() < shortest) translates to if(0 < 0), because there's nothing in vendorQueue yet, so line stays set to 0. Everything gets pushed into vendorQueue[0]. From there I can't see how that test is ever going to come out so line gets changed; I *think* (although it's hard to tell, you need to comment more) it gets stuck there forever.

Janin

Not to mention the Vendor list is never even used. The only part of Vendor.cpp it appears in is when you try to get its length, which will always be zero. If you want it to be different, try adding something to it.

<3

jmillikin wrote: »

, the problem is not in List::Length. For some reason, Head is being set to NULL. Furthermore, because your main incorporates random behaviour I cannot know what the correct output would be. If you can reduce your main to where the problem is easy to check, I can help further.

Yea I figured that Head was NULL for that instance, but I don't know why. Even if I call Length before Print, it has the same result as calling Print before Length.

I'm pretty certain that Head is not being moved.

Janin

Are you sure you're adding anything to that list? Try putting some prints in AddToFront and AddToEnd, just to make sure the list is actually being used. It looks like you're just leaving the vendor list empty.

<3

jmillikin wrote: »

Not to mention the Vendor list is never even used. The only part of Vendor.cpp it appears in is when you try to get its length, which will always be zero. If you want it to be different, try adding something to it.

I used getVendingSpeed and handleCustomer from Vendor.

Philodox

Is there a reason why you have a list declared in Queue as well as Vendor? It looks like whenever you add an element to the vendor class you're actually calling it to Queue's local instance of List. When you call getLength, you're calling it on Vendor's copy (which is empty, of course).

Instead, change the queue class to have its List member be protected and remove the List variable from vendor.

<3

jmillikin wrote: »

Are you sure you're adding anything to that list? Try putting some prints in AddToFront and AddToEnd, just to make sure the list is actually being used. It looks like you're just leaving the vendor list empty.

Vendor length 0
The contents of your queue:
226
180
270
240
60
210
180
90
30
150
270
90

Queue is being filled up.

<3

Philodox wrote: »

Is there a reason why you have a list declared in Queue as well as Vendor?

Vendor is derived from Queue?

Janin

He's not defining List in either class. He's defining that those classes contain an instance of List. Or, two instances in each Vendor.

ecchi

Have you tried putting a breakpoint at your call to length and walking through it?

Valkun

You must have missed my post.

When you're adding stuff to the array of Vendor's, you're putting them into a List called Queue. When you try to read the length, you're getting the length of the List called Vendor. Your Vendor classes have two lists in them.

Janin

wrote: »

Philodox wrote: »

Is there a reason why you have a list declared in Queue as well as Vendor?

Vendor is derived from Queue?

Um, yes?

class Vendor: public Queue {

<3

jmillikin wrote: »

wrote: »

Philodox wrote: »

Is there a reason why you have a list declared in Queue as well as Vendor?

Vendor is derived from Queue?

Um, yes?

class Vendor: public Queue {

It was rhetorical.

<3

Valkun wrote: »

You must have missed my post.

When you're adding stuff to the array of Vendor's, you're putting them into a List called Queue. When you try to read the length, you're getting the length of the List called Vendor. Your Vendor classes have two lists in them.

vendorQueue[line].enqueue(buyItems * vendorQueue[line].getVendingSpeed());

You mean this? I'm putting stuff in to the vendor list.

Philodox

int Vendor::getLength()
{
        return vendor.Length();
}

/* Add a value to the queue. */
bool Queue::enqueue( const int Value )
{
  return (queue.AddToEnd (Value));
}

This is your problem.

Valkun

wrote:

You mean this? I'm putting stuff in to the vendor list.

No, you're not. As you said, Vendor is derived from Queue, as is the enqueue function. enqueue puts items into the list called "queue". Am I wrong?

Senjutsu

wrote: »

Valkun wrote: »

You must have missed my post.

When you're adding stuff to the array of Vendor's, you're putting them into a List called Queue. When you try to read the length, you're getting the length of the List called Vendor. Your Vendor classes have two lists in them.

vendorQueue[line].enqueue(buyItems * vendorQueue[line].getVendingSpeed());

You mean this? I'm putting stuff in to the vendor list.

No, he means that enqueue put that in the List declared in Queue.h.

getLength then reads the length from the List declared in Vendor.h

Janin

wrote: »

Valkun wrote: »

You must have missed my post.

When you're adding stuff to the array of Vendor's, you're putting them into a List called Queue. When you try to read the length, you're getting the length of the List called Vendor. Your Vendor classes have two lists in them.

vendorQueue[line].enqueue(buyItems * vendorQueue[line].getVendingSpeed());

You mean this? I'm putting stuff in to the vendor list.

Anyway, what's happening is something like this:

Vendor.enqueue (1)
   --> Queue.enqueue (1)
         --> Queue.queue.AddToEnd (1)
               --> List.AddToEnd (1)       <--- This is List A

Vendor.Length ()
  --> Vendor.vendor.Length ()
         --> List.Length ()               <--- This is List B
               --> 0

Philodox

jmillikin is correct. Change Queue's List member variable to be protected, and get rid of your Vendor class's List member.

Valkun

Philodox wrote:

jmillikin is correct.

D=.

Philodox

Not that you're wrong, jmillikin explained it the best.

Janin

Valkun wrote: »

Philodox wrote:

jmillikin is correct.

D=.

ASCII art saves my day, one more