[^_^physicist]

Hi everyone, my apologizes if the title isn't specific enough, but hopefully I can explain the problem a little better here. I am writing a kd-tree, which is practically a binary tree with different conditions at even and odd depths; at even depths, the program finds the median of the data set based on the x-coordinates of a data set then splits the data set, left pointer to below the median and right pointer to above the median, at odd it repeats the same but uses checks y-coordinates.

Currently, my problem is that at even depths (besides the zeroth) the program seems to ignore the matching condition for the median and sets the median as values outside of the data set. Below is my code and some sample output, the first section of the output is a repeat of the input data (testing to see if it is taken in correctly). Here is the code:

 #include <fstream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#define _USE_MATH_DEFINES
#include <math.h>
#include <time.h>
#include <vector>
#include <algorithm>
using namespace std;
//Point Type
typedef struct{
	float xvar;
	float yvar;
	}coor;
//Tree Structure
struct treeNode{
struct treeNode *leftPtr;
struct treeNode *rightPtr;
vector<coor> data;
coor nodecoor;
int depth;
//int size;
};
void searchNode(struct treeNode *&, coor, int );
void insertNode(struct treeNode *, vector<coor>, int depth);
void deleteNode(struct treeNode *&, coor);
//tree printing
void postOrder(struct treeNode* treePtr);
//Functions
vector<coor> readdata(float *a_hilines, char* filename);
float median(vector<coor> data, int on);
float dist(coor, coor);

//program begin
int main(int argc, char* argv[]){
  float *a_hlines;
  treeNode* rootPtr=NULL;
  vector<coor> data = readdata(a_hlines,argv[1]); 
  data.pop_back();
coor testvalue=data[1];
//now build tree      
insertNode(rootPtr,data,0);
searchNode(rootPtr,testvalue,0);
postOrder(rootPtr);
return 0;
}
//function definations

//load data:
vector<coor> readdata(float *a_hilines, char* filename){
	ifstream infile;
	infile.open(filename);
	char var[30];
	vector<coor> inputs;
	coor temp;
	while(!infile.eof()){
		infile>>var;
		temp.xvar = atof(var);
		infile>>var;
		temp.yvar = atof(var);
		inputs.push_back(temp);
	} 
	return inputs;
}
//Median Finding function
float median(vector<coor> raw, int on){
  float medi;
  vector<float> temp;
  if(on%2==0){
   for(int i=0; i<(raw.size());i++){
      temp.push_back(raw[i].xvar);
      }
     }
  if(on%2!=0){
   for(int i=0; i<(raw.size());i++){
      temp.push_back(raw[i].yvar);
      }
     }
    sort(temp.begin(),temp.end());
//   if(temp.size()%2==1){
     medi=temp[(raw.size())/2];
//     }//else{
      //medi=(temp[temp.size()/2]+temp[(temp.size()/2-1)])/2;
      //}
    temp.clear();
    raw.clear();
return medi;
}
//Search Tree
void searchNode(treeNode *&treePtr, coor value, int flip){	
     if(treePtr !=NULL){ 
      coor test;
      test=treePtr->nodecoor;
      if(test.xvar==value.xvar && test.yvar==value.yvar){
	cout << "found" << " {" << value.xvar << ", " << value.yvar << "} " << "\n";		
	}
	else{
      if(flip==0){
	if(value.xvar < treePtr->nodecoor.xvar){
	 searchNode((treePtr->leftPtr),value,1);
	cout << "testing" << "\n"; 
	}
	else{
	 searchNode((treePtr->rightPtr),value,1);
	 }
        }
      if(flip==1){
	if(value.yvar < treePtr->nodecoor.yvar){
	 searchNode((treePtr->leftPtr),value,0);
	}
	else{
	 searchNode((treePtr->rightPtr),value,0);
	 }
	}
      }
     }
   if(treePtr==NULL){
	cout << "not_found {" << value.xvar << ", "<< value.yvar << "}" << "\n";    }
  }
void postOrder(treeNode *treePtr){
	coor data={0,0};
	if(treePtr != NULL){
	postOrder(treePtr->leftPtr);
	postOrder(treePtr->rightPtr);
	data=treePtr->nodecoor;
	cout << data.xvar << data.yvar << "\n";
	//cout << "( " << data.xvar << data.yvar ",) \n";
	}
    }	 
//Tree Insert Node
void insertNode(treeNode *treePtr, vector<coor> value, int depth){    
 float condition;
 coor holder;
 coor data;
 vector<coor> temp1;
 vector<coor> temp2;
if(depth==0){
condition=median(value, depth);
depth++;
   for(int i=0; i<value.size();i++){
     cout << i << " {" << value[i].xvar << ", " << value[i].yvar << "} \n";   
      if(value[i].xvar==condition){
        treePtr=new treeNode;
        treePtr->nodecoor=value[i];
	holder=value[i];
//        value.erase(value.begin()+(i-1)); 
      }
     else{
       if(value[i].xvar<condition){
                temp1.push_back(value[i]);
        }
        if(value[i].xvar>condition){ 
         temp2.push_back(value[i]);
         }
        }
       }
//	value.clear();
      cout << "condition " << condition <<  " {" << holder.xvar << ", " << holder.yvar << "} " <<" left size " << temp1.size() << " right size " << temp2.size()<<"\n";
	if(temp1.size()>0){
         insertNode((treePtr->leftPtr),temp1,depth);
         temp1.clear();
         }
        if(temp2.size()>0){
         insertNode((treePtr->rightPtr),temp2,depth);
         temp2.clear();
         }
       }	

// condition=median(value, initial);
   if((depth%2)==0 && depth>0){
      condition=median(value, depth);
      depth++;
     for(int i=0;i<i++;i<value.size()){
//check median-xvar, if equal set to node value, and delete from vector, else if less left else right
      if(value[i].xvar==condition){
	 treePtr=new treeNode;
	 treePtr->nodecoor=value[i];
	 cout << condition << " " << value[i].xvar;
//	 value.erase(value.begin()+(i-1));		
      }
     else{
       if(value[i].xvar<condition){
		temp1.push_back(value[i]);
	}
	if(value[i].xvar>condition){ 
	 temp2.push_back(value[i]);
	 }
	}
       }
//	value.clear();
        cout << "condition " << condition << " {" << holder.xvar << ", " << holder.yvar << "} " <<" left size " << temp1.size() << " right size " << temp2.size()<<"\n";
	if(temp1.size()>0){
	 insertNode((treePtr->leftPtr),temp1,depth);
	 temp1.clear();
	 }
	 if(temp2.size()){
	 insertNode((treePtr->rightPtr),temp2,depth);
	 temp2.clear();
	 }
       }

if((depth%2)!=0 && depth>0){
   condition=median(value, depth);
   depth++;
  for(int i=0; i<value.size();i++){
       if(value[i].yvar==condition){
        treePtr=new treeNode;
        treePtr->nodecoor=value[i];
	holder=value[i];
      }
     else{
       if(value[i].yvar<condition){
                temp1.push_back(value[i]);
        }
        if(value[i].yvar>condition){ 
         temp2.push_back(value[i]);
         }
        }
       }
//	value.clear();
      cout << "condition " << condition << " {" << holder.xvar << ", " << holder.yvar << "} " <<" left size " << temp1.size() << " right size " << temp2.size()<<"\n";
	if(temp1.size()>0){
	 insertNode((treePtr->leftPtr),temp1,depth);
	 temp1.clear();
	 }
	 if(temp2.size()>0){
	 insertNode((treePtr->rightPtr),temp2,depth);
	 temp2.clear();
	 }
       }
    }

Here is the test input file:

 1	 10
8	.01
88	.44
33	551
1893	782
.0001	787
433	11
7806	97895
543678	.0000000001

And the sample output:

0 {1, 10} 
1 {8, 0.01} 
2 {88, 0.44} 
3 {33, 551} 
4 {1893, 782} 
5 {0.0001, 787} 
6 {433, 11} 
7 {7806, 97895} 
8 {543678, 1e-10} 
condition 88 {88, 0.44}  left size 4 right size 4
condition 551 {33, 551}  left size 2 right size 1
condition 8 {-2.99787e+38, 4.59163e-41}  left size 0 right size 0
condition 10 {1, 10}  left size 1 right size 0
condition 8 {-2.99777e+38, 4.59163e-41}  left size 0 right size 0
condition 0.01 {8, 0.01}  left size 0 right size 0
condition 0.0001 {-2.99787e+38, 4.59163e-41}  left size 0 right size 0
condition 787 {0.0001, 787}  left size 0 right size 0
condition 782 {1893, 782}  left size 2 right size 1
condition 543678 {-2.99787e+38, 4.59163e-41}  left size 0 right size 0
condition 11 {433, 11}  left size 1 right size 0
condition 543678 {-2.99777e+38, 4.59163e-41}  left size 0 right size 0
condition 1e-10 {543678, 1e-10}  left size 0 right size 0
condition 7806 {-2.99787e+38, 4.59163e-41}  left size 0 right size 0
condition 97895 {7806, 97895}  left size 0 right size 0
condition 11 {433, 11}  left size 4 right size 4
condition 88 {-2.99797e+38, 4.59163e-41}  left size 0 right size 0
condition 0.44 {88, 0.44}  left size 2 right size 1
condition 543678 {-2.99787e+38, 4.59163e-41}  left size 0 right size 0
condition 0.01 {8, 0.01}  left size 1 right size 0
condition 543678 {-2.99777e+38, 4.59163e-41}  left size 0 right size 0
condition 1e-10 {543678, 1e-10}  left size 0 right size 0
condition 1 {-2.99787e+38, 4.59163e-41}  left size 0 right size 0
condition 10 {1, 10}  left size 0 right size 0
condition 1893 {-2.99797e+38, 4.59163e-41}  left size 0 right size 0
condition 787 {0.0001, 787}  left size 2 right size 1
condition 1893 {-2.99787e+38, 4.59163e-41}  left size 0 right size 0
condition 782 {1893, 782}  left size 1 right size 0
condition 33 {-2.99777e+38, 4.59163e-41}  left size 0 right size 0
condition 551 {33, 551}  left size 0 right size 0
condition 7806 {-2.99787e+38, 4.59163e-41}  left size 0 right size 0
condition 97895 {7806, 97895}  left size 0 right size 0
not_found {8, 0.01}

Thanks for your help.

[jimblumberg]

The first thing you need to do is find an indentation style you like and use it consistently. This will make you program much easier to read.

Next when I compile your code I get the following warning messages:

Quote

main.cpp|37|warning: unused parameter ‘argc’ [-Wunused-parameter]|
main.cpp|52|warning: unused parameter ‘a_hilines’ [-Wunused-parameter]|
main.cpp||In function ‘float median(std::vector<coor>, int)’:|
main.cpp|72|warning: comparison between signed and unsigned integer expressions [-Wsign-compare]|
main.cpp|77|warning: comparison between signed and unsigned integer expressions [-Wsign-compare]|
main.cpp||In function ‘void searchNode(treeNode*&, coor, int)’:|
main.cpp|96|warning: comparing floating point with == or != is unsafe [-Wfloat-equal]|
main.cpp|96|warning: comparing floating point with == or != is unsafe [-Wfloat-equal]|
main.cpp||In function ‘void insertNode(treeNode*, std::vector<coor>, int)’:|
main.cpp|142|warning: comparison between signed and unsigned integer expressions [-Wsign-compare]|
main.cpp|144|warning: comparing floating point with == or != is unsafe [-Wfloat-equal]|
main.cpp|175|warning: operation on ‘i’ may be undefined [-Wsequence-point]|
main.cpp|175|warning: comparison between signed and unsigned integer expressions [-Wsign-compare]|
main.cpp|175|warning: value computed is not used [-Wunused-value]|
main.cpp|177|warning: comparing floating point with == or != is unsafe [-Wfloat-equal]|
main.cpp|207|warning: comparison between signed and unsigned integer expressions [-Wsign-compare]|
main.cpp|208|warning: comparing floating point with == or != is unsafe [-Wfloat-equal]|
main.cpp|136|warning: unused variable ‘data’ [-Wunused-variable]|
main.cpp||In function ‘int main(int, char**)’:|
main.cpp|40|warning: ‘a_hlines’ is used uninitialized in this function [-Wuninitialized]|
||=== Build finished: 0 errors, 16 warnings ===|

If you aren't getting any warnings I suggest that you check your compiler settings and insure the warning level is set to the highest possible value. If you are getting warnings, you need to fix them, never ignore warnings they usually indicate serious problems with your code.

Next since you are using C++ you should be using the C++ equivalents of the C standard headers. For example in C++ the <string.h> header is replaced with <cstring>. Notice the lack of a file extension and the addition of the leading 'c'. There are small differences between the C and C++ standard headers and you should select the proper header for the language.

Next you need to refactor your code to remove the global variables, they are a bad habit in C but in C++ even more so. Also in C++ there is no reason to typedef structures. Structures in C++ are already considered types.

Jim

[^_^physicist]

Hi Jim,

What compiler are you using? When I compile with g++ and I only get the following warnings:

newtree_stilllooking.cpp: In function ‘void insertNode(treeNode*, std::vector<coor>, int)’:
newtree_stilllooking.cpp:142:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
newtree_stilllooking.cpp:175:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
newtree_stilllooking.cpp:207:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
newtree_stilllooking.cpp: In function ‘int main(int, char**)’:
newtree_stilllooking.cpp:40:48: warning: ‘a_hlines’ is used uninitialized in this function [-Wuninitialized]

Also, I noticed I hadn't highlighted where I think the problem is in the code: the insertNode function, with something to do with the operations under the if(depth%2==0){ } branch.

Thanks again

[jimblumberg]

I use g++ 4.7.0 with the following flags:

Quote

-Wshadow
-Winit-self
-Wredundant-decls
-Wcast-align
-Wundef
-Wfloat-equal
-Winline
-Wunreachable-code
-Wmissing-declarations
-Wmissing-include-dirs
-Wswitch-enum
-Wswitch-default
-Wmain
-pedantic-errors
-pedantic
-Wextra
-Wall
-ansi
-g
-std=c++11

I also don't recommend ignoring warnings. You have several, what have you done to fix them?

Quote

Also, I noticed I hadn't highlighted where I think the problem is in the code: the insertNode function, with something to do with the operations under the if(depth%2==0){ } branch.

You need to look closely at these warnings:

Quote

main.cpp|175|warning: operation on ‘i’ may be undefined [-Wsequence-point]|
main.cpp|175|warning: comparison between signed and unsigned integer expressions [-Wsign-compare]|
main.cpp|175|warning: value computed is not used [-Wunused-value]|

Line 175 should be:

      for(int i=0; i<i++; i<value.size()) {

This for statement is seriously flawed. You should probably review your documentation for these loops.

Jim

[^_^physicist]

Good catch at line 175, That seemed to resolve some of the problems.

I fixed the int compared with unsigned int warning, by defining the un-unsigned int variables as unsigned int variable. And to avoid the problems of finding equivalent floats, I changed the condition to be if(fabs((value[i]-condition)<1e-12)){ }.

I seem to be still having problems on the even iterations.

Here is the updated code:

#include <fstream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#define _USE_MATH_DEFINES
#include <math.h>
#include <time.h>
#include <vector>
#include <algorithm>
using namespace std;
//Point Type
typedef struct{
	float xvar;
	float yvar;
	}coor;
//Tree Structure
struct treeNode{
  struct treeNode *leftPtr;
  struct treeNode *rightPtr;
  vector<coor> data;
  coor nodecoor;
  int depth;
//int size; 
 };
void searchNode(struct treeNode *&, coor, int );
void insertNode(struct treeNode *, vector<coor>, int depth);
void deleteNode(struct treeNode *&, coor);
//tree printing
void postOrder(struct treeNode* treePtr);
//Functions
vector<coor> readdata(float *a_hilines, char* filename);
float median(vector<coor> data, int on);
float dist(coor, coor);

//program begin
int main(int argc, char* argv[]){
  float *a_hlines=NULL;
  treeNode* rootPtr=NULL;
  vector<coor> data = readdata(a_hlines,argv[1]); 
  data.pop_back();
  coor testvalue;
  testvalue.xvar=88;
  testvalue.yvar=0.44;

//now build tree      
  insertNode(rootPtr,data,0);
//searchNode(rootPtr,testvalue,0);
  postOrder(rootPtr);
  return 0;
}
//function definations

//load data:
vector<coor> readdata(float *a_hilines, char* filename){
	ifstream infile;
	infile.open(filename);
	char var[30];
	vector<coor> inputs;
	coor temp;
	while(!infile.eof()){
		infile>>var;
		temp.xvar = atof(var);
		infile>>var;
		temp.yvar = atof(var);
		inputs.push_back(temp);
	} 
	return inputs;
}
//Median Finding function
float median(vector<coor> raw, int on){
  float medi;
  vector<float> temp;
  if(on%2==0){
   for(int i=0; i<(raw.size());i++){
      temp.push_back(raw[i].xvar);
      }
     }
  if(on%2!=0){
   for(int i=0; i<(raw.size());i++){
      temp.push_back(raw[i].yvar);
      }
     }
    sort(temp.begin(),temp.end());
//   if(temp.size()%2==1){
     medi=temp[(raw.size())/2];
//     }//else{
      //medi=(temp[temp.size()/2]+temp[(temp.size()/2-1)])/2;
      //}
    temp.clear();
    raw.clear();
return medi;
}
//Search Tree
void searchNode(treeNode *&treePtr, coor value, int flip){	
     if(treePtr !=NULL){ 
      coor test;
      test=treePtr->nodecoor;
      if(test.xvar==value.xvar && test.yvar==value.yvar){
	cout << "found" << " {" << value.xvar << ", " << value.yvar << "} " << "\n";		
	}
	else{
      if(flip==0){
	if(value.xvar < treePtr->nodecoor.xvar){
	 searchNode((treePtr->leftPtr),value,1);
	cout << "testing" << "\n"; 
	}
	else{
	 searchNode((treePtr->rightPtr),value,1);
	 }
        }
      if(flip==1){
	if(value.yvar < treePtr->nodecoor.yvar){
	 searchNode((treePtr->leftPtr),value,0);
	}
	else{
	 searchNode((treePtr->rightPtr),value,0);
	 }
	}
      }
     }
   if(treePtr==NULL){
	cout << "not_found {" << value.xvar << ", "<< value.yvar << "}" << "\n";    }
  }
void postOrder(treeNode *treePtr){
	coor data={0,0};
	if(treePtr != NULL){
	postOrder(treePtr->leftPtr);
	postOrder(treePtr->rightPtr);
	data=treePtr->nodecoor;
	cout << data.xvar << data.yvar << "\n";
	}
    }	 
//Tree Insert Node
void insertNode(treeNode *treePtr, vector<coor> value, int depth){    
  float condition;
  coor holder;
  coor data;
  vector<coor> temp1;
  vector<coor> temp2;
  if(depth==0){
    condition=median(value, depth);
    depth++;
    for(unsigned int i=0; i<value.size();i++){
      cout << i << " {" << value[i].xvar << ", " << value[i].yvar << "} \n";   
      if(fabs((value[i].xvar-condition))<0.0000000000001){
        treePtr=new treeNode;
        treePtr->nodecoor=value[i];
	holder=value[i];
//        value.erase(value.begin()+(i-1)); 
	}
      else{
	if(value[i].xvar<condition){
                temp1.push_back(value[i]);
        }
        if(value[i].xvar>condition){ 
         temp2.push_back(value[i]);
         }
        }
       }
//	value.clear();
      cout << "condition " << condition <<  " {" << holder.xvar << ", " << holder.yvar << "} " <<" left size " << temp1.size() << " right size " << temp2.size()<<"\n";
	if(temp1.size()>0){
         insertNode((treePtr->leftPtr),temp1,depth);
         temp1.clear();
         }
        if(temp2.size()>0){
         insertNode((treePtr->rightPtr),temp2,depth);
         temp2.clear();
         }
       }	

// condition=median(value, initial);
 if((depth%2)==0 && depth>0){
   condition=median(value, depth);
   depth++;
    for(unsigned int i=0;i<value.size();i++){
//check median-xvar, if equal set to node value, and delete from vector, else if less left else right
     if(fabs((value[i].xvar-condition))<0.0000000000001){
      treePtr=new treeNode;
      treePtr->nodecoor=value[i];
      holder=value[i];
//	 value.erase(value.begin()+(i-1));		
      }
     else{
       if(value[i].xvar<condition){
		temp1.push_back(value[i]);
	}
	if(value[i].xvar>condition){ 
	 temp2.push_back(value[i]);
	 }
	}
       }
//	value.clear();
        cout << "condition " << condition << " {" << holder.xvar << ", " << holder.yvar << "} " <<" left size " << temp1.size() << " right size " << temp2.size()<<"\n";
	if(temp1.size()>0){
	 insertNode((treePtr->leftPtr),temp1,depth);
	 temp1.clear();
	 }
	 if(temp2.size()){
	 insertNode((treePtr->rightPtr),temp2,depth);
	 temp2.clear();
	 }
       }
  if((depth%2)!=0 && depth>0){
    condition=median(value, depth);
    depth++;
    for(unsigned int i=0; i<value.size();i++){
       if(fabs((value[i].yvar-condition))<0.0000000000001){
        treePtr=new treeNode;
        treePtr->nodecoor=value[i];
	holder=value[i];
//	value.erase(value.begin()+(i-1));		
      }
     else{
       if(value[i].yvar<condition){
                temp1.push_back(value[i]);
        }
        if(value[i].yvar>condition){ 
         temp2.push_back(value[i]);
         }
        }
       }
//	value.clear();
      cout << "condition " << condition << " {" << holder.xvar << ", " << holder.yvar << "} " <<" left size " << temp1.size() << " right size " << temp2.size()<<"\n";
	if(temp1.size()>0){
	 insertNode((treePtr->leftPtr),temp1,depth);
	 temp1.clear();
	 }
	 if(temp2.size()>0){
	 insertNode((treePtr->rightPtr),temp2,depth);
	 temp2.clear();
	 }
       }
    }

And the new output

0 {1, 10} 
1 {8, 0.01} 
2 {88, 0.44} 
3 {33, 551} 
4 {1893, 782} 
5 {0.0001, 787} 
6 {433, 11} 
7 {7806, 97895} 
8 {543678, 1e-10} 
condition 88 {88, 0.44}  left size 4 right size 4
condition 551 {33, 551}  left size 2 right size 1
condition 8 {8, 0.01}  left size 1 right size 0
condition 10 {1, 10}  left size 0 right size 0
condition 10 {1, 10}  left size 1 right size 0
condition 8 {8, 0.01}  left size 0 right size 0
condition 0.01 {8, 0.01}  left size 0 right size 0
condition 0.0001 {0.0001, 787}  left size 0 right size 0
condition 787 {0.0001, 787}  left size 0 right size 0
condition 782 {1893, 782}  left size 2 right size 1
condition 543678 {543678, 1e-10}  left size 1 right size 0
condition 11 {433, 11}  left size 0 right size 0
condition 11 {433, 11}  left size 1 right size 0
condition 543678 {543678, 1e-10}  left size 0 right size 0
condition 1e-10 {543678, 1e-10}  left size 0 right size 0
condition 7806 {7806, 97895}  left size 0 right size 0
condition 97895 {7806, 97895}  left size 0 right size 0
condition 11 {433, 11}  left size 4 right size 4
condition 88 {88, 0.44}  left size 2 right size 1
condition 10 {1, 10}  left size 1 right size 0
condition 8 {8, 0.01}  left size 0 right size 0
condition 0.01 {8, 0.01}  left size 0 right size 0
condition 1e-10 {543678, 1e-10}  left size 0 right size 0
condition 0.44 {88, 0.44}  left size 2 right size 1
condition 543678 {543678, 1e-10}  left size 1 right size 0
condition 0.01 {8, 0.01}  left size 0 right size 0
condition 0.01 {8, 0.01}  left size 1 right size 0
condition 543678 {543678, 1e-10}  left size 0 right size 0
condition 1e-10 {543678, 1e-10}  left size 0 right size 0
condition 1 {1, 10}  left size 0 right size 0
condition 10 {1, 10}  left size 0 right size 0
condition 1893 {1893, 782}  left size 2 right size 1
condition 787 {0.0001, 787}  left size 1 right size 0
condition 33 {33, 551}  left size 0 right size 0
condition 551 {33, 551}  left size 0 right size 0
condition 97895 {7806, 97895}  left size 0 right size 0
condition 787 {0.0001, 787}  left size 2 right size 1
condition 1893 {1893, 782}  left size 1 right size 0
condition 551 {33, 551}  left size 0 right size 0
condition 782 {1893, 782}  left size 1 right size 0
condition 33 {33, 551}  left size 0 right size 0
condition 551 {33, 551}  left size 0 right size 0
condition 7806 {7806, 97895}  left size 0 right size 0
condition 97895 {7806, 97895}  left size 0 right size 0

And here are the remaining compile time warnings, though they are for sections of the code I am not yet using.

newtree_stilllooking.cpp: In function ‘int main(int, char**)’:
newtree_stilllooking.cpp:42:8: warning: variable ‘testvalue’ set but not used [-Wunused-but-set-variable]
newtree_stilllooking.cpp: At global scope:
newtree_stilllooking.cpp:37:5: warning: unused parameter ‘argc’ [-Wunused-parameter]
newtree_stilllooking.cpp:55:14: warning: unused parameter ‘a_hilines’ [-Wunused-parameter]
newtree_stilllooking.cpp: In function ‘void searchNode(treeNode*&, coor, int)’:
newtree_stilllooking.cpp:99:27: warning: comparing floating point with == or != is unsafe [-Wfloat-equal]
newtree_stilllooking.cpp:99:52: warning: comparing floating point with == or != is unsafe [-Wfloat-equal]
newtree_stilllooking.cpp: In function ‘void insertNode(treeNode*, std::vector<coor>, int)’:
newtree_stilllooking.cpp:138:8: warning: unused variable ‘data’ [-Wunused-variable]

[jimblumberg]

Quote

I seem to be still having problems on the even iterations.

What exactly is the problem with your even iterations? You show us what output your program is producing, maybe you could show us what it should be producing.

Jim

[^_^physicist]

jimblumberg, on 14 July 2012 - 05:00 PM, said:

Quote

I seem to be still having problems on the even iterations.

What exactly is the problem with your even iterations? You show us what output your program is producing, maybe you could show us what it should be producing.

Jim

Good point, so here is an example of what I expect the output to given the following input:

[quote]
1 10
8 .01
88 .44
33 551
1893 782
.0001 787
433 11
7806 97895
543678 .0000000001
[/code]

output should be:
[quote]
depth 0 condition 88 {88, 0.44} left size 4 right size 4
depth 1 condition 551 {33, 551} left size 2 right size 1
depth 2 condition 1 {1, 10} left 0
depth 2 condition 8 {1, 0.01} left size 0 right size 0

[^_^physicist]

jimblumberg, on 14 July 2012 - 05:00 PM, said:

Quote

I seem to be still having problems on the even iterations.

What exactly is the problem with your even iterations? You show us what output your program is producing, maybe you could show us what it should be producing.

Jim

Good point, so here is an example of what I expect the output to given the following input:

Quote

1 10
8 .01
88 .44
33 551
1893 782
.0001 787
433 11
7806 97895
543678 .0000000001

output should be:

Quote

depth 0 condition 88 {88, 0.44} left size 4 right size 4
depth 1 condition 551 {33, 551} left size 2 right size 1
depth 2 condition 8 {8, 0.01} left size 0 right size 0
depth 3 condition 1 {1, 10} left size 0 right size 0
depth 2 condition 787 {0.0001, 787} left size 0 right size 0
depth 1 condition 782 {1893, 782} left size 2 right size 1
depth 2 condition 7806 {7806, 97895} left size 0 right size 0
depth 3 condition 433 {443, 11} left size 0 right 0
depth 2 condition 543678 { 543678, 1e-10} left 0 right 0

it should be making a tree of the shape:

{88,0.44}
/ \
{33,551} {1893,782}
/ \ / \
/ \ / \
/ \ / \
{8,0.01} {0.0001,787} {7806,97895} {543678,1e-10}
/ /
{1,10} {443,11}

This is what I am looking for...well and then implement a nearest neighbor search, but that is for another day.

[jimblumberg]

In my opinion your insertNode() function needs to be simplified. To me there is entirely too much recursion happening in this one function. I may be biased on the recursion issue however since I personally hate recursion. I normally try to find an iterative solution. But I still recommend that you need to simplify this function to make trouble shooting easier.

At this point the only functions you are actually using are main(), median(), readData() and insertNode(). With insertNode doing most of the actual work.

Also your readData function can be greatly simplified. There is no need to retrieve the data into a character array then use atof() to convert this character string into a number. Just use the extraction operator to place the item into the proper variable type. I would also pass the vector into the function as a parameter instead of returning the vector.

bool readdata(vector<coor>& inputs, char* filename);
//program begin
int main(int argc, char* argv[]) {
   vector<coor> data;
   if(!readdata(data, argv[1]))
   { // File read failed. 
      cout << "Error reading input file." << endl;
      return(1);
   }
....

bool readdata(vector<coor>& inputs, char* filename)
{
   ifstream infile(filename);
   if(!infile) // Insure input file opened correctly.
      return(false);

   coor temp;
   // Read the input file. Stops when reading fails, or eof() is true.
   while(infile >> temp.xvar >> temp.yvar)
   { // This reads the input file and places the information in the structure variables. 
      inputs.push_back(temp);
   }
   return true;
}

Jim

This post has been edited by jimblumberg: 15 July 2012 - 07:19 AM