Im supposed to implement a quad tree that will input cities into a fixed format. when the user asks for a particular city, all cities within a certain range will be displayed. i think i have the right method's in place, but for some reason or another, the program wont run. any help would be appreciated. thanks!
this is my def.h file

#include<string>
#include <iostream>
#include <list>
#include <cmath>
using namespace std;


class city
{
public:
	string name;
	double x;
	double y;
};


class quadtree
{
private:

	class node

	{
	public:

		city nodecity;
		node * NorthEast;
		node * NorthWest;
		node * SouthEast;
		node * SoutWest;
	};
	//insert thru recursion
	void recInsert(double x,double y,string name, node * & p);

	//traverse thru recursion
	void recTraverse(node * h);

	node * head;

	void recRange (double x, double y, double radius, node *p, list<city>&CityList);
	bool inRange (double X, double X1,double Y, double Y1, double radius);
	city nearestCity( double x, double y )   //this should return the city closest to city point (x, y).
	city recNearestcity(double x, double y, node *& p, city previous);
    city minimumDistance(double x, double y, city current, city previous);
	list<city>*inrange(double x, double y, double radius);


public:
	quadtree();
	void insert( double x, double y, string name); //insert function
	void traverse(); //traverse function


};


quadtree::quadtree()
{
	head=NULL;
}
//definition of the insert function
void quadtree::insert(double x, double y,string name)
{

	recInsert(x, y,name,head);

}
//definition of the traverse function
void quadtree::traverse()
{

	recTraverse(head);
}

//definition of the recusive insert function.
void quadtree::recInsert(double x,double y,string name,node  * & p)
{
	if (p==NULL)
	{
		p=new node;
		p->NorhtEast=NULL;
		p->NorthWest=NULL;
		p->SouthEast=NULL;
		p->SouthWest=NULL;
		p->nodecity.name=name;
		p->nodecity.x=x;
		p->nodecity.y=y;

	}
	else 
		if(( x >= p->nodecity.x) &&( y > p->nodecity.y))
		{  //NE direction
			recInsert(x, y, name,p->NorthEast);
		}

		else 
			if( x < p->nodecity.x && y >= p->nodecity.y)
			{ // NW direction
				recInsert(x, y, name,p->NorthWest);
			}

			else 
				if( x > p->nodecity.x && y <= p->nodecity.y)
				{ // SE direction
					recInsert( x, y, name,p->SouthEast);
				}
				else 
					if( x <= p->nodecity.x && y < p->nodecity.y)
					{ // SW direction
						recInsert(x, y, name, p->SouthWest);
					}
}


void quadtree::recTraverse(node  * p)
{
	if(p==NULL)
		return;
	else 
	{
		recTraverse(p->NorthWest);
		recTraverse(p->NorthEast);
		recTraverse(p->SouthWest);
		recTraverse(p->SouthEast);
		//cout the name of the city
		cout<<p->nodecity.name<<"  ("<<p->nodecity.x<<","<<p->nodecity.y<<") "<<endl;
	}
}
//this will verify whether its inside the range or not.
bool quadtree::inRange(double X, double X1,double Y, double Y1, double radius)
{
	//distance formula
	double dis = sqrt( pow(X - X1,2.0)+ pow(Y - Y1,2.0));

	//check with the radius if greater than or equal to the distance;
	//if so return true
	if (radius >= dis)
		return true;

	//else return false
	else 
		return false;
}

//this should return a list with all the cities with the given radius
void quadtree::recRange (double x, double y, double radius, node *p, list<city>&CityList)
{
	//since the base case if p=NULL therefore we can start on the general solution
	if (p!=NULL)
	{
		if (p->NorthWest !=NULL)
		{
			if (inRange(x, p->NorthWest->nodecity.x, y, p->NorthWest->nodecity.y,radius))
			{
				//if its inside the range, insert to list
				{
					CityList.push_front(p->NorthEast->nodecity);  //insert city unto list

					recRange(x, y, radius, p->NorthEast->NorthWest, CityList); //Check the 4 coordinates
					recRange(x, y, radius, p->NorthEast->NorthEast, CityList); //of that city
					recRange(x, y, radius, p->NorthEast->SouthWest, CityList);
					recRange(x, y, radius, p->NorthEast->SouthEast, CityList);
				}
			}
			//if is not in range :
			else
			{
				recRange(x, y, radius, p->NorthEast->NorthWest, CityList);  //since the citty is not in
				recRange(x, y, radius, p->NorthEast->SouthWest, CityList);  //range, just check the 3 nearest
				recRange(x, y, radius, p->NorthEast->SouthEast, CityList);  //subtrees of that city
			}

		}
		//while NW is not pointing to NULL check all cities in NW direction
		if(p->NorthWest!= NULL)
		{
			//this checks if the city on the NW is inside the range
			if (inRange (x, p->NorthWest->nodecity.x, y, p->NorthWest->nodecity.y, radius))
			{
				CityList.push_front(p->NorthWest->nodecity);

				recRange(x, y, radius, p->NorthWest->NorthWest, CityList);
				recRange(x, y, radius, p->NorthWeset->NorthEast, CityList);
				recRange(x, y, radius, p->NorthWest->SouthWest, CityList);
				recRange(x, y, radius, p->NorthWest->SouthEast, CityList);
			}
			//if is not in range :
			else
			{
				recRange(x, y, radius, p->NorthWest->NorthEast, CityList);
				recRange(x, y, radius, p->NorthWest->SouthWest, CityList);
				recRange(x, y, radius, p->NorthWest->SouthEast, CityList);
			}

		}
		//while SE is not pointing to NULL check all cities in SE direction
		if(p->SouthEast!= NULL)
		{
			//this checks if the city on the SE is inside the range
			if (inRange (x, p->SouthEast->nodecity.x, y, p->SouthEast->nodecity.y, radius))
			{
				CityList.push_front(p->SouthEast->nodecity);   //insert city unto list

				recRange(x, y, radius, p->SouthEast->NorthWest, CityList);  //check the 4 coordinates
				recRange(x, y, radius, p->SouthEast->NorthEast, CityList);  //of the subtrees of the
				recRange(x, y, radius, p->SouthEast->SouthWest, CityList);  //city
				recRange(x, y, radius, p->SouthEast->SouthEast, CityList);
			}
			//if is not in range :
			else
			{
				recRange(x, y, radius, p->SouthEast->NorthWest, CityList);  //since that city is not
				recRange(x, y, radius, p->SouthEast->SouthWest, CityList);  //in range, just check the
				recRange(x, y, radius, p->SouthEast->NorthEast, CityList);  //nearest tree subtrees of the city
			}

		}
		//while SW is not pointing to NULL check all cities in SW direction
		if(p->SouthWest!= NULL)
		{
			//this if checks if the city on the NE is inside the range
			if (inRange (x, p->SouthWest->nodecity.x, y, p->SouthWest->nodecity.y, radius))
			{
				CityList.push_front(p->SouthWest->nodecity);

				recRange(x, y, radius, p->SouthWest->NorthWest, CityList);
				recRange(x, y, radius, p->SouthWest->NorthEast, CityList);
				recRange(x, y, radius, p->SouthWest->SouthWest, CityList);
				recRange(x, y, radius, p->SouthWest->SouthEast, CityList);
			}
			//if is not in range :
			else
			{
				recRange(x, y, radius, p->SouthWest->NorthWest, CityList);
				recRange(x, y, radius, p->SouthWest->NorthEast, CityList);
				recRange(x, y, radius, p->SouthWest->SouthEast, CityList);
			}

		}

	}

}

// Calling the function range which checks if the root is inside the range
list<city> quadtree::inRange(double x, double y, double radius)
{
	list<city> List;

	if (head!=NULL)
	{
		if (inRange (x, head->nodecity.x, y, head->nodecity.y, radius))
		{
			List.push_front(head->nodecity);

		}
		recRange(x,y,radius, head, listname);

	}
	return List;   // to return the list with the names of the cities that 
	// are within the given range

}
city quadtree::nearestCity(double x, double y));   //this should return the city closest to city point (x, y).
{
	city previous;
	previous.name = "empty";
	previous.x = 83720478;
	previous.y = 63829631;

	city city;
	city nearestCity;

	if (head== NULL)
		return previous;
	else
	{
		if (x >=head->nodecity.x && y >= head->nodecity.y)
		{
			previous = head->nodecity;
			 city = recNearestcity(x, y, head->NorthEast, previous);
		}
		else if (x < head->nodecity.x && y >= head->nodecity.y)
		{
			previous = head->nodecity;
			 city = recNearestcity(x, y, head->NorthWest, previous);
		}
		else if (x >=head->nodecity.x && y < head->nodecity.y)
		{
			previous = head->nodecity;
			 city = recNearestcity(x, y, head->SouthEast, previous);
		}
		else //if (x < ptr->data.x && y < ptr->data.y)
		{
			previous = head->nodecity;
			 city = recNearestcity(x, y, head->SouthWest, previous);
		}

		 nearestCity = minimumDistance(x, y, current, previous);
		
		return nearestCity;
	}
}

city quadtree::recNearestcity(double x, double y, node *& p, city previous)
{
	city city;
	city nearestCity;

	if (p == NULL)
		return previous;
	else
	{
		if (x >= p->nodecity.x && y >= p->nodecity.y)
		{
			previous = p->nodecity;
			 city= recNearestcity(x, y, p->NorthEast, previous);
		}
		else if (x < p->nodecity.x && y >= p->nodecity.y)
		{
			previous = p->nodecity;
		 city = recNearestcity(x, y, p->NorthWest, previous);
		}
		else if (x >= p->nodecity.x && y < p->nodecity.y)
		{
			previous = p->nodecity;
			city = recNearestcity(x, y, p->SouthEast, previous);
		}
		else 
		{
			previous = p->nodecity;
			city = recNearestcity(x, y, p->SouthWest, previous);
		}

	    nearest = minimumDistance(x, y, current, previous);
		return nearestCity;
	}
}

and this would be the quad implementaion.

#include <iostream>
#include<string>
#include "def.h"

using namespace std;


void

print_citylist (std::list<city> * plist, std::string message)

{

    //std::cout << "" << std::endl;

    std::cout << "--------- " << message << " BEGIN ---------" << std::endl;

    for (std::list<city>::iterator it = plist->begin(); it != plist->end(); it ++) {

        std::cout << "City: '" << (*it).name << "'\t(x=" << (*it).x << ", y=" << (*it).y << ")" << std::endl;

    }

    std::cout << "--------- " << message << " END ---------" << std::endl;

}

int main()

{

    pointquadtree citytree;


    citytree.insert ( 100, 100, "Chicago");

    citytree.insert ( 25, 125, "McAllen");

    citytree.insert ( 50, 150, "Los Angeles");

    citytree.insert ( 75, 130, "Detroit");

    citytree.insert ( 150,  50, "New York");

    citytree.insert ( 10,  40, "Austin");


    city closestCity = citytree.nearestCity (63, 84);

    cout << "The closest city is " << closestCity.name << endl;

    double x = 50;

    double y = 95;

    double r = 100;

    std::list<city> * closeCities = citytree.in_range (x, y, r);

    if (NULL == closeCities) {

        return;

    }

    print_citylist (closecities, "city list");

    delete closecities;

    return 0;
}

any help would be very much appreciated!! thanks!!

Define "won't run"

400 lines of code with no idea what we're looking for nor why is not going to happen easily.

This article has been dead for over six months. Start a new discussion instead.