Sign in to follow this  
mike74

code critique

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 this post


Link to post
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;

This makes for easier reading.

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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites
Quote:
Original post by ace_lovegrove
Even 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 this post


Link to post
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 this post


Link to post
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).

Instead of:

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 this post


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

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

Share this post


Link to post
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 this post


Link to post
Share on other sites
Quote:
Original post by mike74
Ready4dis, how can MSVC++ generate identical code for ++i and i++?

mike
http://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 this post


Link to post
Share on other sites
Quote:
Original post by mike74
Ready4dis, how can MSVC++ generate identical code for ++i and i++?

mike
http://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]
add ax, 1
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 this post


Link to post
Share on other sites
Quote:
Original post by Ready4Dis
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 ;).


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 this post


Link to post
Share on other sites
Quote:
Original post by CTar
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.


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 this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this