# Reading a sequence of points and finding the closest one to the first

I was told this is the place to come for input/feedback on your programming. I am always looking to improve either by personal review or outside opinion/help. Would the community here be willing to provide positive criticism of my script below?

/********************************************************************
* Author: Mattew Hoggan
* Description: Write a client program that uses the data type point.
* Read a sequence of points (pairs of floating-point numbers) from
* standard input, and find the one that is closest to the first.
* *****************************************************************/

#include <math.h>
#include <iostream>
#include <vector>
#include <istream>
#include <iterator>
#include <algorithm>
#include <limits.h>

using namespace std;

typedef struct point {
float x;
float y;
} point;

float calc_distance( const point *a, const point *b ) {
return sqrt( pow( a->x-b->x, 2.0 ) + pow( a->y-b->y, 2.0 ) );
}

void print_point( point *a ) {
cout << "(" << a->x << ", " << a->y << ") ";
}

void delet_point( point *a ) {
delete a;
}

vector<point*>* form_pairs( vector<float> &num ) {
vector<point*> *points=NULL;
if( ( num.size( ) & 1 ) == 1 ) {
cerr << "ERROR: You input: " << num.size( )
<< " which is odd, failed to build vector "
<< endl;
return points;
} else {
cout << "Going to build points" << endl;
points = new vector<point*>;
for( vector<float>::iterator vit=num.begin( );
vit!=num.end( ); vit+=2 ) {
point *in = new point( );
in->x = *(vit);
in->y = *(vit+1);
points->push_back( in );
}
return points;
}
}

void pop_front( vector<point*> *pairs ) {
reverse( pairs->begin( ), pairs->end( ) );
pairs->pop_back( );
reverse( pairs->begin( ), pairs->end( ) );
}

void min_euclidean_distance( vector<point*> *pairs ) {
if( pairs->size( ) == 1 ) {
return;
}
point *first = pairs->front( );
pop_front( pairs );
point *second = pairs->front( );
pop_front( pairs );

for_each( pairs->begin( ),pairs->end( ),print_point );
cout << endl;

point *p_min = second;
float f_min = calc_distance( first,second );
for( vector<point*>::iterator pit = pairs->begin( );
pit != pairs->end( ); pit++ ) {
float tmp = calc_distance( first,(*pit) );
if( tmp < f_min ) {
f_min = tmp;
p_min = (*pit);
}
}

cout << "The closest node to "; print_point( first );
cout << " is "; print_point( p_min );
cout << " at " << f_min << " units away " << endl;
delete first;
delete second;
}

int main( int arc, char **arv ) {
vector<float> num;
cout << "Please, input even number of floats: ";
for( istream_iterator<float> iit (cin);
iit!=istream_iterator<float>( );iit++ ) {
num.push_back( (*iit) );
}

vector<point*>* pairs = form_pairs( num );
if( pairs ) {
min_euclidean_distance( pairs );
for_each( pairs->begin( ),pairs->end( ),delet_point );
delete pairs;
}
}

-
I learned something new today: pow(x, 2) performs the same as x * x with optimization on. –  200_success Nov 20 '13 at 19:03

1) Why is this a free standing function and not a member?

float calc_distance( const point *a, const point *b )


It access members that should potentially be private. Best to make it a member.
Also why are you passing by pointer. Best to pass by const reference.

2) You use pointers where you should use objects.

vector<point*>* form_pairs( vector<float> &num )


RAW pointers have no ownership semantics associated with them. Thus it is not clear who should clean them up. In this case you do clean then up, BUT not in an exception safe way. In C++ code it is generally a mistake to have any pointers in the code (pointers should be wrapped up in smart pointers or containers).

In this case you should just have a simple vector of objects and you should return a reference. I know it looks expensive to copy back a vector but RVO and NRVO will take care of that and usually the vector is constructed in place at the destination and no copy is required.

As the num vector is not changed. You should pass it by const reference.

std::vector<point>   form_pairs(vector<float> const& num)


3) What are you trying to acieve here?

if( ( num.size( ) & 1 ) == 1 )


You are trying to validate that the input has an even number of floats as input.
Why are you trying to make that fact cryptic. If you must do this then make a comment on you intent. Code is going to be in maintenance a lot longer than it takes to develop. Make sure you make it easy to understand.

5) You are doing too much work here:

    for( vector<float>::iterator vit=num.begin( );
vit!=num.end( ); vit+=2 )


Here you could have used a standard algorithm. I would have used std::copy(). Also by using += 2 you are limiting yourself to random access iterators ie vectors. You are code should try and be neutral on the type of container. Thus limit yourself to the ++ operator.

6) Dynamically allocating the pointer.

        point *in = new point( );


a) Why not have a constructor that takes the two parameters to do the initialization.
b) Who owns the object. The owner is the person responsible for deleting the object.
c) If you had stored normal point objects in the vector this would not have been an issue.

7) This is just a tad nit picky:

int main( int arc, char **arv )


Technically argv should be declared char* argv[].

8) Again too much work:

vector<float> num;
for( istream_iterator<float> iit (cin);
iit!=istream_iterator<float>( );iit++ ) {
num.push_back( (*iit) );
}


This can be achieved with:

std::copy(std::istream_iterator<float>(std::cin),
std::istream_iterator<float>(),
std::back_inserter(num));


I would write it like this:
Simplicity is key!

#include <iostream>
#include <fstream>
#include <cmath>

class Point
{
public:
float   distance(Point const& rhs) const
{
float dx    = x - rhs.x;
float dy    = y - rhs.y;

return sqrt( dx * dx + dy * dy);
}
private:
float   x;
float   y;
friend std::istream& operator>>(std::istream& stream, Point& point);
friend std::ostream& operator<<(std::ostream& stream, Point const& point);
};


### Edit

// This function reads a point from a stream
// It returns the stream object thus allowing chaining.
//     std::cin >> p1 >> p2 >> p3 >> etc;
//
// The side affect of returning the stream is that it can also
// be used in conditionals. The stream will auto covert into a tyep
// that can be used in a boolean context which is true if the stream
// is still in a good state and false if the read failed.
//      while(std::cin >> point)
//      {
//           // Successfully read a point from the stream.
//      }
//
std::istream& operator>>(std::istream& stream, Point& point)
{
return stream >> point.x >> point.y;
}

// This function writes a point to a stream
// This just returns the stream object
std::ostream& operator<<(std::ostream& stream, Point const& point)
{
return stream << point.x << " " << point.y << " ";

// The above is just a shorthand way of writting this:
stream << point.x << " " << point.y << " ";
return stream;

// This is because the result of the operator >> and operator <<
// Is always the stream passed as the first parameter.
// Or historically this is what you are supposed to return to prevent confusion.
}


This makes the main loop very easy to write:

int main()
{
std::ifstream       data("Plop");

// Trying to find the closest point to this.
Point   first;
data >> first;

// The next point is the closest until we find a better one
Point   closest;
data >> closest;

float   bestDistance = first.distance(closest);

Point   next;
while(data >> next)  // read a point. If if fails loop not entered.
{
float nextDistance  = first.distance(next);
if (nextDistance < bestDistance)
{
bestDistance    = nextDistance;
closest         = next;
}
}

std::cout << "First(" << first << ") Closest(" << closest << ")\n";
}

-
could you please explain the friend member functions. I don't really understand the return type. What is being returned exactly? –  Matthew Hoggan Jul 31 '11 at 6:10
One good idea is to have a distance_squared function that doesn't take the square root. Note that sqrt(a * a) > sqrt(b * b) is true if and only if a > b, so you can avoid the (expensive) sqrt call if you only need to see which one is largest. –  Martin Vilcans Jul 31 '11 at 12:04
@Matthew: I have moved the friend functions to a more traditional location outside the class and written comments. Defining them inside the class is a little trick that I sometimes use when writing simple applications. –  Loki Astari Jul 31 '11 at 17:00
@Martin: Your expertise and willingness to share it is greatly appreciated. Thank you so much for your time. –  Matthew Hoggan Jul 31 '11 at 21:29
@Xploit: Its probably overemphasis as char** is just as valid. But argv is an array of pointers. Declaring it as such helps others read it correctly. Using char** is just a pointer to a pointer it does not convey the semantics of an array. Thus the idea of using char* argv[] is to pass as much information to the reader of the code as possible. –  Loki Astari Jan 13 '13 at 19:05
show 1 more comment