while loop seemingly refuses to stop

[kanesoban]

Okay, here's the code:

		while (L.notEmpty)
		{
			cout << "( " << L.Next().x << " ; " << L.Next().y << " )" << '\n';
			L.removeAfter();
			std::cout << L.notEmpty << '\n';
		}

This is the last part of the main function. If this while loop ends, the program ends.

You don't need to know what L.Next and L.removeAfter does. The important part is, that the std::cout << L.notEmpty << '\n'; line writes "0". L.notEmpty is a type bool variable.
What should happen, is that the program ends, instead, after writing out the "0", it gives me a segfault, and i don't know why.

[helios]

notEmpty should be a function, not a variable.
I'm afraid I will have to see the code for removeAfter().

[Zaita]

notEmpty should be a function, not a variable.

Only because this satisfies encapsulation. Unless your thinking of another reason?


+1 for having to see the code, you haven't provided enough information here. But it looks like you've developed your own linked list? Why not just use the STL type?

[helios]

How about that notEmpty being a variable, it's not read only?
Also, it has to be updated every time a method changes the structure, instead of every time it's needed. Not to mention that this also creates duplicate code.

[kanesoban]

I'm afraid I will have to see the code for removeAfter().

template <class T>
void ChainedList<T>::removeAfter()
{
	if ( Head == 0 )
		{
			notEmpty = 0;
			return;
		}
	Node<T> * nodeBeingRemoved = Head;
	Head = Head->Next;
	delete nodeBeingRemoved;
	if ( Head == 0 )
		notEmpty = 0;

The code is a bit rushed, i know.

Here is the Node type:

#ifndef NODE_H
#define NODE_H
		template <class T>
		class Node
			{
				public:
				Node()
					{
						Next = 0;
					}
				Node(T _Data)
					{
						Data = _Data;
						Next = 0;
					}
				T Data;
				Node<T> * Next;
			};

#endif 

But it looks like you've developed your own linked list? Why not just use the STL type?

Because i just made the implementation (just like this program) for C++ programming practice.

[helios]

It seems to me that "removeAfter" is a misnomer, since you're deleting the head of the list.

Ah, here's your problem.
If I understand your code correctly, this is your implementation of ChainedList<T>::Next():

T ChainedList<T>::Next(){
	return *(this->Head->Next);
}

This wouldn't be a problem if it wasn't for the fact that when the list is of size 1, this->Head->Next==0. Dereferencing a null pointer causes segmentation faults if you're lucky and undefined behavior if you're unlucky.
What you should do is have a method like Head() that will return a copy of the data at the head of the list.a

[kanesoban]

template <class T>
T ChainedList<T>::Next()
{
	return Head->Data;
}

Yeah, i know that it has a misleading name, but Next() doesn't do what it's name implies.

[helios]

In that case, I don't think I will be able to help without directly debugging. Could you post the entire code?

[kanesoban]

Well ok, but it's about 500 LOC.

main.cpp:

#ifdef HAVE_CONFIG_H
#include <config.h>
#endif

#include <iostream>
#include <cstdlib>
#include "ChainedList.h"
#include "Pont.h"
#include "Node.h"

using namespace std;

//template <class T>
//void GrahamScan(Pont array[], ChainedList<T> &L, int n);




// 0 : a pontok egy vonalon vannak ; 0 < : balra fordul ; 0 > : jobbra fordul
double Whatdirection(Pont p1, Pont p2, Pont p3)
	{
		return (p2.x-p1.x) * (p3.y-p1.y) - (p2.y-p1.y) * (p3.x-p1.x);
	}


void GetTangents(Pont p1 , Pont p2 , Pont Pivot, double &p1tangent, double &p2tangent)
{


	if (p1.y - Pivot.y < 0 )
		p1tangent = -1 * (p1.y - Pivot.y);
	else
		p1tangent =  (p1.y - Pivot.y);

	if (p1.x - Pivot.x < 0 )
		p1tangent /= -1 * (p1.x - Pivot.x);
	else
		p1tangent /=  (p1.x - Pivot.x);


	if (p2.y - Pivot.y < 0 )
		p2tangent = -1 * (p2.y - Pivot.y);
	else
		p2tangent =  (p2.y - Pivot.y);

	if (p2.x - Pivot.x < 0 )
		p2tangent /= -1 * (p2.x - Pivot.x);
	else
		p2tangent /=  (p2.x - Pivot.x);


}



bool Smaller (Pont p1 , Pont p2 , Pont Pivot)
{
	cout << Pivot.x << '\n';
	double p1tangent,p2tangent;

//Speciális eset kategória #1: amikor az x koordináta megegyezik (90 fokot zár be az x tengellyel)

	if (Pivot.x == p2.x) // A p2 és a Pivot vonala 90 fokot zár be az x tengellyel
		{
			if (Pivot.x == p1.x) //mindkét ponttal 90 fokot zár be, tehát egyik sem "kisebb"
				return 0;
			else
				return 1; //a p1 valóban "kisebb" p2-nél
		}
	if (Pivot.x == p1.x)
		return 0;

// Normális eset(ek):
	GetTangents(p1 , p2 , Pivot, p1tangent, p2tangent);
	return p1tangent < p2tangent;
}




bool Greater (Pont p1 , Pont p2 , Pont Pivot)
{
	double p1tangent,p2tangent;

//Speciális eset kategória #1: amikor az x koordináta megegyezik (90 fokot zár be az x tengellyel)

	if (Pivot.x == p1.x) // A p1 és a Pivot vonala 90 fokot zár be az x tengellyel
		{
			if (Pivot.x == p2.x) //mindkét ponttal 90 fokot zár be, tehát egyik sem "kisebb"
				return 0;
			else
				return 1; //a p2 valóban "kisebb" p2-nél
		}
	if (Pivot.x == p2.x)
		return 0;

// Normális eset(ek):

	GetTangents(p1 , p2 , Pivot, p1tangent, p2tangent);

	return p1tangent > p2tangent;
}




void QuickSortPoints(Pont array[],int lower_border,int upper_border, char c) //az algoritmus növekvő, vagy csökkenő rendbe rendez a megkapott karaktertől függően (i = increase ; d = decrease)
{
	int i = lower_border,j = upper_border,n = (lower_border + upper_border) / 2;
	Pont x,helper;
	if (c == 'i')
		{
			if (upper_border <= 1) //nincs mit rendezni
				return;
		}
	else
	if (c == 'd')		
		{
			if (lower_border-1 == upper_border) //nincs mit rendezni
				return;
		}
	x = array[n];
	do{
		if (c == 'i')
		{
//Ebben keletkezik a szegmens hiba
			while (Smaller (array[i] , x , array[0]) && i < j) i++;
//Ebben keletkezik a szegmens hiba
			while (Greater (array[j] , x , array[0]) && i < j) j--;
		}
		else
		if (c == 'd')
		{
			while (Greater (array[i] , x , array[0]) && i < j) i++;
			while (Smaller (array[j] , x , array[0]) && i < j) j--;
		}

		if (i <= j)
		{
			helper = array[i];
			array[i] = array[j];
			array[j] = helper;
			i++;
			j--;
		}
			
	}while (i <= j);
		
	if (lower_border < j)
		QuickSortPoints(array,lower_border,j, c);
	if (i < upper_border)
		QuickSortPoints(array,i,upper_border, c);
}



	
void MaxSearch(Pont array[], int n)
	{
		Pont csere;
		for (int i=1 ; i < n ; i++)
			{
				if ( (array[i].y > array[0].y) || (array[i].y == array[0].y && array[i].x < array[0].x) )
					{
						csere = array[i];
						array[i] = array[0];
						array[0] = csere;
					}
					
			}
	}
	
template <class T>
void GrahamScan(Pont array[], ChainedList<T> &L, int n)
	{
		if (n <= 1) //ha egy vagy nulla pont van...
			{
				L.insertAfter(array[0]);
				return;
			}
// I. A leg alacsonyabban lévő pont kerül előre
		MaxSearch(array, n);
		int j,k;
		Pont csere;
//II. Előre rendezzük a P-től jobbra lévő pontokat (és így persze a tőle balra levők hátra kerülnek) Ez buborékrendezéshez hasonló algoritmus
		k = 0; //A k vált. mindig a legutóbbi olyan pont indexe, amit nem kell cserélni
		for ( int i = 1; i < n ;i++ )
		{
	
			j = 0;
			if ( array[i].x < array[0].x )
			{
				j = i+1;
				while (j < n) 
				{
					if ( array[j].x >= array[0].x )
					{
						csere = array[j];
						array[j] = array[i];
						array[i] = csere;
						break;
					}
					j++;
				} 


			}
			else
				k = i;
	
	
			if (j == n)
			{
				k = i-1;
				break;
			}
			else
				k = i;
		}

// III. és IV. rész: rendezés a P és adott pont által meghatározott vonal X tengellyel bezárt szöge szerint
		QuickSortPoints(array,1,k, 'i');
		QuickSortPoints(array,k+1,n-1, 'd');
//Itt kezdődik az igazi Graham scan
		//double direction;
		Pont p1 = array[0],p2 = array[1],p3;

		
		L.insertAfter(p1);
		L.insertAfter(p2);


		for (int i = 2 ; i < n ; i++ )
		{
			p3 = array[i];
			L.insertAfter(p3);

			while (Whatdirection(p1, p2, p3) <= 0)
			{
				L.removeAfter();
				L.insertAfter(p3);
				i++;
				p3 = array[i];
			}

			p1 = p2;
			p2 = p3;

		}	
	}
	
	
	int main(int argc, char *argv[])
	{
  
	
		int n;
		cin >> n;
		Pont array[n];
		for (int i = 0;i < n;i++)
		{
			cin >> array[i].x;
			cin >> array[i].y;
		}
		ChainedList<Pont> L;
		GrahamScan(array,L,n);
		
		while (L.notEmpty)
		{
			cout << "( " << L.Next().x << " ; " << L.Next().y << " )" << '\n';
			L.removeAfter();
			std::cout << L.notEmpty << '\n';
		}
	
	}
	
	
	

[kanesoban]

ChainedList.h :

#ifndef CHAINEDLIST_H
#define CHAINEDLIST_H

#include "Node.h"

template <class T>
class ChainedList
{
	private:

		Node<T> * Head;

	public:

		//Node<T> * Pointer;
		//T Element;
		bool notEmpty;
		ChainedList();
		Node<T> getNode ( int n );
		void insertAfter ( Node<T> &node, Node<T> &newNode );
		void insertAfter ( Node<T> &newNode );
		void insertAfter ( T _Data );
		void removeAfter ( Node<T> &node );
		void removeAfter();
		T Next();
		~ChainedList();

};

template <class T>
ChainedList<T>::ChainedList()
{
	Head = 0;
	notEmpty = 0;
	//Pointer = Head;
}

template <class T>
Node<T> ChainedList<T>::getNode ( int n )
{
	Node<T> node;
	Node<T>* pointer = Head;
	Node<T>* last;
	last = pointer;

//Hibakezelés: out of range  !!!!!
	for ( int i = 1;i < n;i++ )
	{
		pointer = ( *last ).Next;
		last = pointer;
	}
	node = *pointer;
	return node;
}


template <class T>
void ChainedList<T>::insertAfter ( Node<T> &node, Node<T> &newNode ) // newNode beszúrása node után
{
	newNode.Next = node.Next; // newNode rákövetkező cellája node eddigi rákövetkező cellája lesz
	node.Next = &newNode;   // node rákövetkező cellája mostantól newNode
	notEmpty = 1;
}
template <class T>
void ChainedList<T>::insertAfter ( Node<T> &newNode ) // newNode beszúrása a lista elejére
{
	newNode.Next = Head;    // newNode után következik a teljes eddigi lista
	Head = &newNode; // newNode a lista új feje
	notEmpty = 1;
}

template <class T>
void ChainedList<T>::insertAfter ( T _Data )
{
	Node<T> * newNode = new Node<T>;
	newNode->Data = _Data;
	newNode->Next = Head;
	Head = newNode;
	notEmpty = 1;
}

template <class T>
void ChainedList<T>::removeAfter ( Node<T> &node ) // a node után következő cella eltávolítása
{
	if ( Head == 0 )
		{
			notEmpty = 0;
			return;
		}
	Node<T> * nodeBeingRemoved = node.Next; // ezt a cellát akarjuk eltávolítani
	node.Next = ( *node.Next ).Next; // node rákövetkező eleme mostantól az eddig kettővel utána álló lesz
	delete nodeBeingRemoved;     // a törölt cella memóriaterületének felszabadítása
	if ( Head == 0 )
		notEmpty = 0;
}

template <class T>
void ChainedList<T>::removeAfter() // a node után következő cella törlése
{
	if ( Head == 0 )
		{
			notEmpty = 0;
			return;
		}
	Node<T> * nodeBeingRemoved = Head; // ezt a cellát akarjuk törölni
	Head = Head->Next;
	delete nodeBeingRemoved;     // a törölt cella memóriaterületének felszabadítása
	if ( Head == 0 )
		notEmpty = 0;
//std::cout << "Valami" << '\n';
}

template <class T>
ChainedList<T>::~ChainedList()
{

	Node<T>* p1;
	Node<T>* p2;
	p1 = Head;
	do
	{
		p2 = ( *p1 ).Next;
		( *p1 ).Next = 0;
		p1 = p2;
	}
	while ( ( *p1 ).Next != 0 );


}

template <class T>
T ChainedList<T>::Next()
{
	return Head->Data;
}

#endif 

[kanesoban]

Node.h :

#ifndef NODE_H
#define NODE_H
		template <class T>
		class Node
			{
				public:
				Node()
					{
						Next = 0;
					}
				Node(T _Data)
					{
						Data = _Data;
						Next = 0;
					}
				T Data;
				Node<T> * Next;
			};

#endif 

[kanesoban]

Pont.h :

class Pont
{
	public:
		double x,y;

		Pont()
		{
			x = 0;
			y = 0;
		}

		Pont(double _x, double _y)
		{
			x = _x;
			y = _y;
		}

};

[helios]

template <class T>
ChainedList<T>::~ChainedList()
{

	Node<T>* p1;
	Node<T>* p2;
	//This line is the one causing problems. You never check if this->Head==0...
	p1 = Head;
	do
	{
		//...so when you try to dereference this pointer, all hell breaks loose.
		p2 = ( *p1 ).Next;
		( *p1 ).Next = 0;
		p1 = p2;
	}
	while ( ( *p1 ).Next != 0 );


}