# code critique

This topic is 4485 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Please let me know what you think of my kdtree code:


#include <conio.h>
#include <cstdlib>
#include <iostream>
#include <limits>
#include <time.h>
#include <vector>
#include <algorithm>
using namespace std;

// A few notes...
// Make sure all points are unique before inserting them into the Kdtree.
// The only functions you should call are the constructor and searchtree:
// Kdtree(const vector<Point> &P)
// vector<Point> searchtree(float x0, float y0, float x1, float y1)

struct Point {
float x, y;

bool operator==(const Point &p2)
{
return (x == p2.x && y == p2.y);
}

Point(float x, float y)
{
this->x = x;
this->y = y;
}

Point()
{
}

};

class Kdtree {

struct Node
{
Point p;
Node *left, *right;

Node(const Point &p)
{
this->p = p;
this->left = NULL;
this->right = NULL;
}

};

Node *root;

public:
Kdtree(const vector<Point> &P)
{
root = buildkdtreemain(P);
}

vector<Point> searchtree(float x0, float y0, float x1, float y1)
{
vector<Point> pointoutputvector;
searchkdtree(root, Range(x0, y0, x1, y1), pointoutputvector);
return pointoutputvector;
}

~Kdtree()
{
deleteallnodes(root);
}

private:

bool lessthanx(const Point &p1, const Point &p2)
{
if (p1.x != p2.x) return (p1.x < p2.x);
else return (p1.y < p2.y);
}

bool lessthany(Point &p1, Point &p2)
{
if (p1.y != p2.y) return (p1.y < p2.y);
else return (p1.x < p2.x);
}

struct PointSortX
{
bool operator () (const Point& p1, const Point &p2)
{

if (p1.x != p2.x) return (p1.x < p2.x);
else return (p1.y < p2.y);
}
};

struct PointSortY
{
bool operator () (const Point& p1, const Point &p2)
{
if (p1.y != p2.y) return (p1.y < p2.y);
else return (p1.x < p2.x);
}
};

struct Range {
float x0, y0;
float x1, y1;

Range(float x0, float y0, float x1, float y1)
{
this->x0 = x0;
this->y0 = y0;
this->x1 = x1;
this->y1 = y1;
}

Range(void)
{
}

};

// depth is 0 for an x level
// depth is 1 for a y level

Node* buildkdtree(vector<Point> &xsorted, vector<Point> &ysorted, int depth)
{

if (xsorted.size()==0) return NULL;
else if (xsorted.size()==1) return new Node(xsorted[0]);

int n = xsorted.size();
int medianindex = (n-1)/2;

if (!depth) {
Point L = xsorted[medianindex];
vector<Point> P1newxsorted(xsorted.begin(), xsorted.begin()+medianindex+1);
vector<Point> P2newxsorted(xsorted.begin()+medianindex+1, xsorted.end());
vector<Point> P1newysorted, P2newysorted;
vector<Point>::iterator i = ysorted.begin();
while (i != ysorted.end())
{
Point p = *i++;
if (lessthanx(p, L) || p == L) P1newysorted.push_back(p);
else P2newysorted.push_back(p);
}

Node *v = new Node(L);
v->left = buildkdtree(P1newxsorted, P1newysorted, !depth);
v->right = buildkdtree(P2newxsorted, P2newysorted, !depth);
return v;
}

else {
Point L = ysorted[medianindex];

vector<Point> P1newysorted(ysorted.begin(), ysorted.begin()+medianindex+1);
vector<Point> P2newysorted(ysorted.begin()+medianindex+1, ysorted.end());
vector<Point> P1newxsorted, P2newxsorted;

vector<Point>::iterator i = xsorted.begin();
while (i != xsorted.end())
{
Point p = *i++;
if (lessthany(p, L) || p == L) P1newxsorted.push_back(p);
else P2newxsorted.push_back(p);
}
Node *v = new Node(L);
v->left = buildkdtree(P1newxsorted, P1newysorted, !depth);
v->right = buildkdtree(P2newxsorted, P2newysorted, !depth);
return v;
}
}

Node* buildkdtreemain(const vector<Point> &P)
{
if (P.size()==0) return NULL;
else if (P.size()==1) return new Node(P[0]);
vector<Point> xsorted(P);
sort(xsorted.begin(), xsorted.end(), PointSortX());
vector<Point> ysorted(P);
sort(ysorted.begin(), ysorted.end(), PointSortY());
return buildkdtree(xsorted, ysorted, 0);
}

bool pointinregion(const Point &p, const Range &r)
{
if (
p.x >= r.x0
&& p.x <= r.x1
&& p.y >= r.y0
&& p.y <= r.y1) return true;
else return false;
}

bool isfullycontained(const Range &small, const Range &big)
{
if (small.x0 >= big.x0
&& small.y0 >= big.y0
&& small.x1 <= big.x1
&& small.y1 <= big.y1) return true;
else return false;
}

bool intersects(const Range &r0, const Range &r1)
{
if (r0.x0 > r1.x1) return false;
else if (r1.x0 > r0.x1) return false;
else if (r0.y0 > r1.y1) return false;
else if (r1.y0 > r0.y1) return false;
else return true;
}

void reportsubtree(Node *v, vector<Point> &pointoutputvector)
{
if (v == NULL) return;
reportsubtree(v->left, pointoutputvector);
reportsubtree(v->right, pointoutputvector);

if (!v->right && !v->left) pointoutputvector.push_back(v->p);
}

// depth will be 0 if we're at an x partition and 1 if we're at a y partition
void searchkdtree(Node *v, const Range &R, int depth, const Range ®ionv, vector<Point> &pointoutputvector)
{

if (!v->left && !v->right)
{
if (pointinregion(v->p, R)) pointoutputvector.push_back(v->p);
return;
}

Range leftregion = regionv;
if (!depth) leftregion.x1 = v->p.x;
else leftregion.y1 = v->p.y;

if (isfullycontained(leftregion, R)) reportsubtree(v->left, pointoutputvector);
else if (intersects(leftregion, R)) searchkdtree(v->left, R, !depth, leftregion, pointoutputvector);

Range rightregion = regionv;
if (!depth) rightregion.x0 = v->p.x;
else rightregion.y0 = v->p.y;

if (isfullycontained(rightregion, R)) reportsubtree(v->right, pointoutputvector);
else if (intersects(rightregion, R)) searchkdtree(v->right, R, !depth, rightregion, pointoutputvector);

}

void searchkdtree(Node *v, Range R, vector<Point> &pointoutputvector)
{

if (v == NULL) return;

Range regionv;
float infinity = std::numeric_limits< float >::infinity();

regionv.x0 = -infinity;
regionv.y0 = -infinity;
regionv.x1 = infinity;
regionv.y1 = infinity;

searchkdtree(v, R, 0, regionv, pointoutputvector);

}

void deleteallnodes(Node *root)
{
if (root == NULL) return;
deleteallnodes(root->left);
deleteallnodes(root->right);
delete root;
}

};


mike http://www.coolgroups.com/kdtree [Edited by - mike74 on August 30, 2005 6:13:27 AM]

##### Share on other sites
Replace <code> and </code> with [source] and [/source] respectively, more people will bother to read it if it's nicely formatted in a source box [smile]

##### Share on other sites
Hey,

1. 'using namespace std' is a bad idea. Just 'using' what you need when you need it.

2. For the constructor:

Point(float x, float y)
{
this->x = x;
this->y = y;
}

In your struct, initialise the variables in the initialisation list like this:

Point(float x, float y)
:
x(x), y(y)
{
}

3. Make sure all of the paths in your functions return. So where you have

if(...){...}
else return false;

make it:

if (...){...}

return;

4. Not a problem really but i can never get on with your the coding style of this:

class MyClass {

};

I much prefer reading and debugging code that looks like this:

class MyClass
{

};

This way it is easier to match up the scope brackets for quicker debugging.

4. Here you are returning a variable by value and in this case if the vector becomes huge then this will get slower.

vector<Point> searchtree(float x0, float y0, float x1, float y1)
{
vector<Point> pointoutputvector;
searchkdtree(root, Range(x0, y0, x1, y1), pointoutputvector);
return pointoutputvector;
}

I suggest passing a reference to the output vector as a parameter to the method.

5. On line 147 i would suggest rewriting this code with a for loop,

while (i != ysorted.end())
{
Point p = *i++;
if (lessthanx(p, L) || p == L) P1newysorted.push_back(p);
else P2newysorted.push_back(p);
}

to:

for ( i = ysorted.begin();
i != ysorted.end();
++i )
{
...
}

It is important to note that i am using ++i here rather than i++ it is faster.

Hope these points help,

ace

##### Share on other sites
Thanks for the comments. Can you explain why ++i is faster than i++ and maybe point me to a confirmation? I haven't heard of that, and I don't really see why.

mike
http://www.coolgroups.com/kdtree

##### Share on other sites
The reason that ++i is faster is because of the implementation of the increment and what it returns.

The code for i++

const T operator++(T)
{
T temp(*this); // EDIT: Added '*this'

++(*this);

return temp;
}

and the code for ++i

T& operator++(T)
{
(*this) += 1;

return *this;
}

Not entirely sure about the second.

The first is called post increment and the second is called preincrement. As you can see from the implementation of post increment it creates a temporary variable, this is slower that preincrement and should be avoided as good practice. Imagine having your own complicated class where you have overloaded the ++ operator, the creation of another huge class object might well be slow.

It is covered in Exceptional C++ by Herb Sutter (great book) [smile]

ace

[Edited by - ace_lovegrove on August 30, 2005 4:48:40 AM]

##### Share on other sites
Interesting. So, this is just true for most iterators? Is it true for any other objects in general? I'm guessing it's not the case for incrementing integers.

mike
http://www.coolgroups.com/

##### Share on other sites
Even for incementing integers it is slower. But on todays computers the difference is negligable on standard types. I would suggest getting into the habit though, its a good one to maintain, and knowing the difference is a good one to know at job interviews.

I would suggest doing it for iterators of the standard containers as well.

[smile]

ace

EDIT: Edited the code for post and pre increment operators posted above.

##### Share on other sites
One more thing. For the following function, do you think I need to check if the node v is NULL? It seems like it is on VERY rare occasions, and I'm not sure if that means I did something else wrong.

// depth will be 0 if we're at an x partition and 1 if we're at a y partition
void searchkdtree(Node *v, const Range &R, int depth, const Range ®ionv, vector<Point> &pointoutputvector)
{
if (!v->left && !v->right)
{
if (pointinregion(v->p, R)) pointoutputvector.push_back(v->p);
return;
}

Range leftregion = regionv;
if (!depth) leftregion.x1 = v->p.x;
else leftregion.y1 = v->p.y;

if (isfullycontained(leftregion, R)) reportsubtree(v->left, pointoutputvector);
else if (intersects(leftregion, R)) searchkdtree(v->left, R, !depth, leftregion, pointoutputvector);

Range rightregion = regionv;
if (!depth) rightregion.x0 = v->p.x;
else rightregion.y0 = v->p.y;

if (isfullycontained(rightregion, R)) reportsubtree(v->right, pointoutputvector);
else if (intersects(rightregion, R)) searchkdtree(v->right, R, !depth, rightregion, pointoutputvector);

}

mike
http://www.coolgroups.com/kdtree

##### Share on other sites
It is good practice to always confirm the validity of pointers passed as parameters to functions. You can then exit gracefully if the user provides corrupt information to the function.

ace

##### Share on other sites
Quote:
 Original post by ace_lovegroveEven for incementing integers it is slower. But on todays computers the difference is negligable on standard types.

That's funny, I actually wrote a benchmark a long time back in Turbo C/c++ and did an assembly output and it WAS true that the i++ uses a temporary and the ++i didn't, HOWEVER if you do an assembly output via msvc 6, or similar recent compiler it generates identical code in both cases. The moral of the story, for general cases it makes no difference whatsoever, but a few cases it is still true. That being said, I still prefer to use the pre-increment/decrement just so I am in the habbit for when it could actually be useful, and the fact that I use some not-so-up-to-date compilers for PIC programming, etc, it is still faster in some cases.

##### Share on other sites

>Can you explain why ++i is faster than i++ and maybe point me to a
I think ++i writes to memory directly and i++ first reads it into a
register, modifies & writes back.

I remember a funny experiment which gives that ++i is atomic and i++ not:

Write a simple program with two threads accessing a global variable i.
- thread A will loop 1000 times and do i++
- thread B will loop 1000 times and do i--
Check the value of i when both threads have finished.

Do the same with --i and ++i

##### Share on other sites
General:
Don't use using directives at the top leel of header files (i.e. outside of a scope). This introduces everything in std:: into the global namespace for everything that includes that header.

Using this-> inside of a class/struct is redundant

Try to seperate the definitions and implementations of your classes. The way you have it now, verything is implicitly declared inline. The point struct's implementation can be moved to a .cpp file. The tree classes can be moved outside of the class (but as it's a template it should be kept in the header).

if(blah1 && blah2){return true;}else{return false;}

You can just write:
return blah1 && blah2;

You're using new style library headers everywhere, except for <time.h> (replaced by <ctime>

It would be better to use an initializer list in your constructors, rather than assigning each of the variables. Although this makes no speed difference in the case of built-ins, it is good practice and will be quicker for user defined types.

For struct point it would be better to have default constructor set x and y to 0.0f.

Don't hesitate to ask for clarifications/explantions.

##### Share on other sites
Ready4dis, how can MSVC++ generate identical code for ++i and i++?

mike
http://www.coolgroups.com/kdtree

##### Share on other sites
It would just be a compiler optimisation. It would be able to recognise whether you are making good use of i++. For example:

int a = t++;

Here it is important that t++ is implemented because it is critical that the value a is a certain value. Where as when increasing an iterator in a for loop, like this:

for( unsigned int t;
t < 10;
t++ )
{
}

It isnt necessary to post increment, so the compile optimises this out.

ace

##### Share on other sites
Quote:
 Original post by mike74Ready4dis, how can MSVC++ generate identical code for ++i and i++?mikehttp://www.coolgroups.com/kdtree

If I'm not wrong, VC++ will know that the result of using ++i and i++ in a certain circumstance will be the same so it will optimize the code to use ++i.

##### Share on other sites
Quote:
 Original post by mike74Ready4dis, how can MSVC++ generate identical code for ++i and i++?mikehttp://www.coolgroups.com/kdtree

Because it's smart :). Seriously though, if you have a single line like so:

i++;
++b;

Each will be tranlsated into a single inc bp[x] assembly call. In borland turbo c/c++ the i++ was converted into:

mov ax, bp[x]
mov bp[x], ax

while the ++b was converted as so:
inc bp[x]

As you can see, this was a big difference! But, nowadays compilers are smart enough to simply make them both into the same call, they just have to remember which order to put the increment depending on which side the ++ is on ;).

##### Share on other sites
Quote:
 Original post by Ready4DisAs you can see, this was a big difference! But, nowadays compilers are smart enough to simply make them both into the same call, they just have to remember which order to put the increment depending on which side the ++ is on ;).

One thing to keep in mind is that on build-in types they'll probably result in the same assembly code, but for a custom type it wont be able to change post-increment to pre-increment.

const T operator++(T){T temp(*this);(*this) = 42;return temp;}T& operator++(T){(*this) += 1;return *this;}

This is legal C++ code, even though it is not a good idea to write. Note that even if post-increment and pre-increment result in the same the C++ compiler wont change a post-increment to pre-increment since it has no way of checking that it always result in the same code. So with custom types you should always use pre-increment when you can.

##### Share on other sites
Quote:
 Original post by CTarNote that even if post-increment and pre-increment result in the same the C++ compiler wont change a post-increment to pre-increment since it has no way of checking that it always result in the same code. So with custom types you should always use pre-increment when you can.

However, they may both compile into the same assembly if you've got a smart compiler (since it will be able to tell that a given member isn't reused until after the temporary is gone anyways).

But you'll be laughed at by your peers for using postincrement when you "should" be using preincrement. And you may not be using a smart compiler. And even if you are right now, someday you might have to work with one that isn't. And god kills a kitten every time you use one. Say no to needless postponing of incrementation! Save the kittens!

##### Share on other sites

This topic is 4485 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Create an account

Register a new account

• ### Forum Statistics

• Total Topics
628641
• Total Posts
2983981

• 10
• 18
• 20
• 13
• 9