AW: libkdtree experiences and questions

[Sam Hayne]

Replied accidently directly to Paul... 2nd try. :)


Paul Harris wrote:

> Hi Sam,

> great email, lots of detail

Thx. If it helps you in any way I'm glad.
(Hope those issues weren't all caused by VS or my edits. :D )

> 3.1)
> > I always ended up with runtime errors using erase().  :(

> Could you please boil it down to a simple test case?  (eg look at
test_kdtree.cpp, just make up a new .cpp file that builds a tree and then >
somehow crashes or asserts).


Puhh... wasn't that easy to create an simple example (as in my case I got
the points out of a bitmap).
But here a bit lengthy one - it crashes deterministically each time.

In my case erase() failed to delete point (41, 189)... deleting some other
point instead.
Eventually resulting in this runtime error:
http://img359.imageshack.us/img359/4623/runtimeerrordz4.jpg


//=======
//Defs:
//========

struct duplet {
	typedef int value_type;

	inline value_type operator[](size_t const N) const { return d[N]; }
	inline bool operator==(duplet const& other) const 
	{
		return this->d[0] == other.d[0] && this->d[1] == other.d[1];

	}
	
	inline bool operator!=(duplet const& other) const
	{
		return this->d[0] != other.d[0] || this->d[1] != other.d[1];

	}

	value_type d[2];
	//typedef boost::shared_ptr<duplet> ptr; };

typedef KDTree::KDTree<2, duplet,
std::pointer_to_binary_function<duplet,int,double> > duplet_tree_type;

inline double return_dup( duplet d, int k ) { return d[k]; }




//=======
//main:
//========

	duplet_tree_type dupl_tree_test(std::ptr_fun(return_dup));
	std::vector<duplet> vDuplets;

	//srand(time(0));	
	int randy1 = 0;
	int randy2 = 0;
	for (int i=0; i<700; i++)
	{	
		//create coordinate for new duplet
		randy1+=2;
		randy1=randy1%255;
		randy2+=3;
		randy2=randy2%255;
		//randy1 = rand() % 255;
		//randy2 = rand() % 255;

		//new duplet
		duplet super_dupre = { {randy1, randy2} };

		//check if duplet with same coordinate already in
vector/tree. If not: insert in vector and tree
		duplet_tree_type::iterator pItr =
dupl_tree_test.find_nearest(super_dupre,std::numeric_limits<double>::max()).
first;
		if (*pItr!=super_dupre) 
		{
			dupl_tree_test.insert(super_dupre);
			vDuplets.push_back(super_dupre);
		}
		
	}
	
	dupl_tree_test.optimise();

	int elements;

	while (vDuplets.size()>0) //delete all duplets from tree which are
in the vector
	{
		elements = vDuplets.size();


		duplet element_to_erase = vDuplets.back();
		vDuplets.pop_back();

		dupl_tree_test.erase(element_to_erase); //erase() : will
probably erase wrong element sooner or later
		//dupl_tree_test.erase_exact(element_to_erase);
//erase_exact(): works
		
		
		//debug stuff:
		duplet_tree_type::iterator pItr =
dupl_tree_test.find_nearest(element_to_erase,std::numeric_limits<double>::ma
x()).first;
		duplet nearest_to_element = *pItr;
		if (nearest_to_element==element_to_erase)		
		{
			// element still in tree... wrong element must have
been erased
			int u = 7; //set breakpoint here
		}		
	}