C++

Forum

 
Point Sorting with Vectors

LA101 (10)
Hey guys,

I'm trying to write a program which reads a sequence of pairs of coordinates from a text file and stores it in a vector of points.

Before reading the text file, I want it to read an additional point from the user, and at each iteration of the loop reading from file, to keep points in the vector sorted according to Manhattan distance from this point.

Instructions I've been given:

Create a function void ord_ins(vector<point>& v, point p, ...)
which takes as arguments a vector of points (passed by reference), one point p (and possible other arguments) and, assuming the vector is sorted, stores the point in right position in vector.

The algo to be used:
-Put new element at end of vector.
-Find position in vector where new element should be.
-Shift all elements, from that position on, towards the end of the vector.
-Place the new element in that position.

I may be wrong, but I think this is where the problem is. in bolds above


The problem is probably algorithm based.. the file reads well, but I get a wrong output when I test with 00 as ref. Any help?

Also,
int find_pos(const vector<point>& v, point p,...) returns position where point should be.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
 
  #include <iostream>
#include <vector>
#include <cmath>
#include <fstream>					
using namespace std;

struct point 
{
	double x;
	double y;
}ref;			
 
void print_vector(vector<point>&v)
{
	for (int i=0; i<v.size(); i++) 
	{
		cout << v[i].x << ", " << v[i].y << '\n';
	}
}

//To calculate the Manhattan Distance between 2 points: 
//point p1 and the reference point (point ref).
//double manhattan_distance(point p1, const point ref)
{
	double distance = (abs(p1.x - ref.x)) + (abs(p1.y - ref.y));
	return(distance);	
}

//To find position that the new point (point p) being read should be. 
//Point ref is the reference point inputed by the user. 
int find_pos(vector<point>&v, point p) //needs to be relative to starting point at 0;
{
	int position;
	double d = manhattan_distance(p, ref);					
	if(v.size()==1)
	{
		position = 0;
	}
	if(v.size()>1)
	{
	for (int i = 0; i<v.size(); i++)					
	{
		double d2 = manhattan_distance(v[i], ref);
		double d3 = manhattan_distance(v[i+1], ref);
		if(d==d2)								
		{
			position = i; 
			break;
		}
		if((d>d2)&&(d<d3))
		{
			position = i+1; 
			break;
		}
	}
	}	
	return(position);
}

//To insert the new point to the right position.
void ord_ins(vector<point>& v, point p)
{
	v.push_back(p);
	int position = find_pos(v,p);
	v.insert((v.begin()+position),p);
}




int main () 
{
	vector <point> pp1;
	point pp2;
	ifstream infile;
	infile.open("datainput.txt");
	
	cout << "Enter the reference point for the Manhattan distance: " <<'\n';
	cin >> ref.x >> ref.y;
		

	while(infile >> pp2.x >>pp2.y)
	{
		ord_ins(pp1, pp2);
	}
	
	print_vector(pp1);
	
	infile.close();
	
	
    return 0;
}
Cody0023 (336)
You are inserting the same object into the vector twice.
Last edited on
LA101 (10)
Yeah, because when I try to remove v.push_back(p); it gives me an access error.
keskiverto (10402)
Why is ref a global variable?

You obviously don't want to use standard library too much, but perhaps you could look up how the code below is supposed to work?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
 
struct point {
  double x;
  double y;
  double dist = 0.0;
};

bool pointless( const point & lhs, const point & rhs ) {
  return lhs.dist < rhs.dist;
}

// ...
vector <point> pp1;
point pp2;
point ref;
cin >> ref.x >> ref.y;
while(infile >> pp2.x >>pp2.y)
{
  pp2.dist = manhattan( ref, pp2 );
  auto pos = std::upper_bound( pp1.begin(), pp1.end(), pp2, pointless );
  if ( pp1.end() == pos ) {
    pp1.push_back( pp2 );
  } else {
    pp1.insert( pos, pp2 );
  }
}

LA101 (10)
Hi,

This code doesn't work, when I try to compile it, I geterror: ISO C++ forbids declaration of 'pos' with no type and error: cannot convert '__gnu_cxx::__normal_iterator<point*, std::vector<point, std::allocator<point> > >' to 'int' in initialization




Duthomhas (13206)
@keskiverto
He made ref global because find_pos() needs that information to sort properly. Also, the object is not to make the STL do it. The object is to do it himself. (Hence the instruction to make the 'where to insert' function.)

@LA101
The point that you are inserting the same data into your vector twice should not be ignored. Don't do that. (Get rid of line 63.)

The reason you are getting an access error is because of the following situation:

ref == (0,0);
vector == { (1,1), (2,2), (3,3) };
p == (5,5);

Where does p go? At the end, of course.

But your loop (line 41) is not terminated with a valid value for position when it gets to line 57. The return value, then, is garbage, and may be anything, like -1 or 5000012. These are, of course, invalid values to access your vector, and as a result, throw an invalid access error and terminate your program.

Fix it by changing line 33: int position = v.size(); -- meaning, should a proper insert position not be found by the loop (and a value assigned to position before quitting the loop), then the proper place to "insert" is at the end (since that was the value of position before the loop began).


The next problem you have is the logic inside the loop to terminate. (It's wrong.) The trick is to go through the elements, one by one, and ask: is the Manhatten distance to p still less than the Manhatten distance to the current element?. If it is not, then you have found your insert position. That's it!


Your compiler should be complaining about comparing signed and unsigned values. Use size_t as your index into a vector.

for (size_t i = 0; i < v.size(); i++)

This isn't big, however, and you need not worry about it. (Particularly as your assignment does specifically say to return an int for an index.)


Finally, about the global. For your schoolwork, it is fine. But your assignment gives you the ability to gain points for passing it as a reference:

31
32
33
 
int find_pos(vector<point>&v, point p, point ref)
{
	...
61
62
63
64
65
 
void ord_ins(vector<point>& v, point p, point ref)
{
	int position = find_pos(v,p,ref);
	v.insert((v.begin()+position),p);
}

Hope this helps.
keskiverto (10402)
@LA101:
Its C++11 syntax. If you are using GCC, then you have to tell that you use the new standard. However,

@Duoas:
I said "look up". I.e. read the reference documentation for the functions that I did use. Get ideas from it. Then adapt. For example, I pass predicate function to upper_bound, but LA101 can (and had) inline the predicate into find_pos.

The question about global was a thought-provoker. Yes, it gets the job done, but is that a good practice to learn in the beginning, particularly when the assignment has the "optional parameters" hint?
LA101 (10)
@keskiverto :

Thanks very much! I'm using Xcode, and after Googling, don't really know how to update the gcc. I have tried editing compiler flags, but that didn't work either.

However, as you've suggested, I've done my homework and researched the upper_bound function ( at http://www.cplusplus.com/reference/algorithm/upper_bound/ ) and the method you've used (it's helped me with my next assignment, as I was lead to read on the similar sort() function and how it can be used for vectors of strings). From the site, I have now used their type description for upper_bound which is std::vector<int>::iterator and it's still not working. This is the new code I've come up with based on your suggestions:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
 
#include <iostream>
#include <vector>
#include <cmath>
#include <fstream>					
using namespace std;

struct point 
{
	double x;
	double y;
	double dst;
};			


bool pointless(const point &lhs, const point &rhs)
{
	return lhs.dst < rhs.dst;
}


void print_vector(vector<point>&v)
{
	for (int i=0; i<v.size(); i++) 
	{
		cout << v[i].x << ", " << v[i].y << '\n';
	}
}

//To calculate the Manhattan Distance between 2 points: 
//point p1 and the reference point (point ref).
double manhattan_distance(point p1, const point ref)
{
	double distance = (abs(p1.x - ref.x)) + (abs(p1.y - ref.y));
	return(distance);	
}

//To find position that the new point (point p) being read should be. 
//Point ref is the reference point inputed by the user. 
std::vector<point>::iterator find_pos(vector<point>&v, point p, point ref) 
//needs to be relative to starting point at 0;
{
	p.dst = manhattan_distance(p, ref);
std::vector<point>::iterator pos = std::upper_bound( v.begin(), v.end(), p, pointless );
	
	return(pos);
}

//To insert the new point to the right position.
void ord_ins(vector<point>& v, point p, point ref)
{
	std::vector<point>::iterator pos = find_pos(v, p, ref);
	if (v.end() == pos ) {
		v.push_back( p );
	} else {
		v.insert( pos, p );
	}
}




int main () 
{
	vector <point> pp1;
	point pp2;
	point ref;
	ifstream infile;
	infile.open("datainput.txt");
	cin >> ref.x >> ref.y;
	while(infile >> pp2.x >>pp2.y)
	{
		ord_ins(pp1, pp2, ref);
	}	
	print_vector(pp1);
	
	infile.close();
	
	
    return 0;
}

The code just exits immediately I enter my ref point.



LA101 (10)
@Duoas

Thanks for your response as well! I have also followed what you've said, and have
come up with this for the loop logic:


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 
{
	int position = v.size();
	double d = manhattan_distance(p, ref);		
	if(v.size()==1)
	{
		position = 0;
	}
	if(v.size()>1)
	{
		for (size_t i = 0; i<v.size(); i++)								
		{
			double d2 = manhattan_distance(v[i], ref);
			if(d>=d2)
			{
				position = i; 
			}
		}
	}	
	return(position);
}



The full code is now:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
 
#include <iostream>
#include <vector>
#include <cmath>
#include <fstream>					
using namespace std;

struct point 
{
	double x;
	double y;
};			

void print_vector(vector<point>&v)
{
	for (int i=0; i<v.size(); i++) 
	{
		cout << v[i].x << ", " << v[i].y << '\n';
	}
}

//To calculate the Manhattan Distance between 2 points: 
//point p1 and the reference point (point ref).
double manhattan_distance(point p1, const point ref)
{
	double distance = (abs(p1.x - ref.x)) + (abs(p1.y - ref.y));
	return(distance);	
}

//To find position that the new point (point p) being read should be. 
//Point ref is the reference point inputed by the user. 
int find_pos(vector<point>&v, point p, point ref) 
//needs to be relative to starting point at 0;
{
	int position = v.size();
	double d = manhattan_distance(p, ref);				
	if(v.size()==1)
	{
		position = 0;
	}
	if(v.size()>1)
	{
		for (size_t i = 0; i<v.size(); i++)								
		{
			double d2 = manhattan_distance(v[i], ref);
			if(d>=d2)
			{
				position = i; 
			}
		}
	}	
	return(position);
}

//To insert the new point to the right position.
void ord_ins(vector<point>& v, point p, point ref)
{
	int position = find_pos(v,p, ref);
	v.insert((v.begin()+position),p);
}




int main () 
{
	vector <point> pp1;
	point pp2;
	ifstream infile;
	infile.open("datainput.txt");
	point ref;
	
	cout << "Enter point for the Manhattan distance: " <<'\n';
	cin >> ref.x >> ref.y;
	
	
	while(infile >> pp2.x >>pp2.y)
	{
		ord_ins(pp1, pp2, ref);
	}
	
	print_vector(pp1);
	
	infile.close();
	
	
    return 0;
}
Last edited on
keskiverto (10402)
If size is 1, then you set position 0 (aka insert to front), but what if that existing point should be before the new? You don't need that special case.

Lets have one element in the vector. Your loop checks for d>=d2.
If that is true (old point is closer) you set position to 0 (insert front).
If that is false (new point is closer) position remains size() (insert back).
That does not sound right, assuming that you want ascending order.

The basic idea of the find is that once you reach the position to insert to, you will store the info and break the loop.

In the other version you had point::dst, but you never did set it for the points that are in the vector. Therefore, the upper_bound was comparing undefined values. That, however, does not explain sudden exit. I would add printout commands within the functions in order to see what they are doing. (Alternatively use debugger to watch the execution step by step.)

(You did set the p.dst in the find_pos, but p is a by value parameter and thus only a copy of the p in ord_ins that will be added to vector.)
Last edited on
LA101 (10)
Hi @keskiverto,

So I've tweaked the first loop's algorithm with the break and everything and the code is now functional.

However, for the other version, I have passed p by reference and as you've said, it's not making much of a difference. When I debug, this is what I get:

1
2
3
4
5
6
7
8
9
10
 
bfd_mach_o_scan_read_symtab_symbol: symbol "_bzero" is unsupported 'indirect' reference: setting to undefined
bfd_mach_o_scan_read_symtab_symbol: symbol "_memccpy" is unsupported 'indirect' reference: setting to undefined
bfd_mach_o_scan_read_symtab_symbol: symbol "_memchr" is unsupported 'indirect' reference: setting to undefined
bfd_mach_o_scan_read_symtab_symbol: symbol "_memcmp" is unsupported 'indirect' reference: setting to undefined
bfd_mach_o_scan_read_symtab_symbol: symbol "_memcpy" is unsupported 'indirect' reference: setting to undefined
bfd_mach_o_scan_read_symtab_symbol: symbol "_memmove" is unsupported 'indirect' reference: setting to undefined
bfd_mach_o_scan_read_symtab_symbol: symbol "_memset" is unsupported 'indirect' reference: setting to undefined
bfd_mach_o_scan_read_symtab_symbol: symbol "_strchr" is unsupported 'indirect' reference: setting to undefined
bfd_mach_o_scan_read_symtab_symbol: symbol "_strcmp" is unsupported 'indirect' reference: setting to undefined
bfd_mach_o_scan_read_symtab_symbol: symbol "_strncmp" is unsupported 'indirect' reference: setting to undefined


As I've said, I use Xcode, so it might have to do with some technical compiler error..
Topic archived. No new replies allowed.