Linked list of points

Hi guys,

I have a problem with my code. What I am doing is making a linked list of points (x,y). I want to ask the user for points (as many as they want to add) then add them into a linked list. I also want to sort the points by their x value. Finally I want to print the points in the list. So far I have the linked list code and the point code. What I need help with is using those to

1) Ask the user to enter as many points as they want
2) Add the points entered by the user into the linked list
3) Sort the list by x value
4) Display the points in the linked list

I have tried many things to get this to work, but I keep getting errors like no << operator for Point when I try to print the linked list. Also, I don't think I'm retrieving the list points from the user correctly, it seems to only be taking x values (not sure how to let the user enter points). Although I want to sort by x value I really want to just get the points into the linked list and displayed first then I think i can figure out how to sort them.

So please if anyone could take a look at my code and show me where I am going wrong and how to do what I am asking with my current code for the linked list and point classes. I really just need someone to show me how to ask the user for points then put them in the linked list and print it.

I've attached my four program files (linkedList.h, LinkedPoints.cpp, Point.h, and Point.cpp).

(1) linkedList.h is the linked list class and its methods.
(2) LinkedPoints.cpp is my main() where I have attempted to ask the user for points, enter the points into the linked list and print it, but it isn't done right.
(3) Point.h is my point class.
(4) Point.cpp has the methods and constructors for Point.h.

I really need specific code help with this because I understand what I have to do already, but I keep running into little problems with the actual code.

Thanks in advance for any help.

For those that don't want to download the files I'll post the code here, except for linkedList.h because it is pretty large, but also the most important. At the very bottom you can download linkedList.h and the others if you want.

Code:

---

// Point.h

#ifndef POINT_H
#define POINT_H

#include "windows.h"
#include <iostream>

using namespace std;

class Point
{
public:
        Point();
        Point(int x, int y);
        ~Point();
        void pointCoord(int x, int y);
        void pointDraw(int x, int y);
        int getX();
        int getY();
        void setX(int xVal);
        void setY(int yVal);
        void print(int x, int y);

protected:
        int x;
        int y;
};

#endif

---

Code:

---

// Point.cpp

#include "Point.h"

//default constructor
Point::Point()
{
        x = 0;
        y = 0;
}
//constructor
Point::Point(int x, int y)
{
        x = x;
        y = y;
}

Point::~Point()
{
}

//Find coordinates
void Point::pointCoord(int x, int y)
{
        HANDLE output_handle;
        COORD pos;

        output_handle = GetStdHandle(STD_OUTPUT_HANDLE);

        pos.X = x;
        pos.Y = y;

        SetConsoleCursorPosition(output_handle, pos);
}

//Draw at coordinates once found
void Point::pointDraw(int x, int y)
{
        pointCoord(x, y);
                cout << "<-Coord Is Here\n";
}

int Point::getX()
{
        return x;
}

int Point::getY()
{
        return y;
}

void Point::setX(int xVal)
{
        x = xVal;
}

void Point::setY(int yVal)
{
        y = yVal;
}

void Point::print(int x, int y)
{
        cout << x << "," << y << endl;
}

---

Code:

---

// LinkedPoints.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "linkedList.h"
#include "Point.h"

int _tmain(int argc, _TCHAR* argv[])
{
int x = 0;
int y = 0;

Point p1(x, y);

linkedListType<Point> list1;

        cout<<"1) Type two numbers to make a coordinate."
                "\n2) Use the format (XX YY) only spacing the numbers not using a comma."
                "\n3) Then press Enter to add the coordinate to the list."
                "\n4) When finished adding to the list type -9999 and press Enter."
                <<endl;
                cin >> x, y;

        while(x != -9999)//execution number for list creation
                {
                        list1.insertLast(p1);//insert info into the list as long as -9999 isn't entered
                        cin >> x, y;
                }

list1.print();

return 0;
}

---

>I keep getting errors like no << operator for Point when I try to print the linked list.
That's because you don't define an operator<< for your Point class. As it is, you need to use the getX and getY member functions and display it manually:

Code:

---

Point& current = // Get a point from the list

cout<< current.getX() <<','<< current.getY() <<'\n';

---

Alternatively, you can add an operator<< in your Point class:

Code:

---

class Point
{
public:
        Point();
        Point(int x, int y);
        ~Point();
        void pointCoord(int x, int y);
        void pointDraw(int x, int y);
        int getX();
        int getY();
        void setX(int xVal);
        void setY(int yVal);
        void print(int x, int y);
        friend ostream& operator<<(ostream& out, const Point& point)
        {
                return out<< x <<','<< y;
        }

protected:
        int x;
        int y;
};

---

Then you can use Point objects with cout:

Code:

---

cout<< mypoint <<'\n';

---

>So far I have the linked list code
Are you being forced to use it? Chances are good that you'll have a much easier time with the standard vector class.

Code:

---

protected:
        int x;
        int y;

---

That's a very bad idea. Data members should be private, and if you want to provide an interface to child classes, you create protected member functions that access them.

>cin >> x, y;
This doesn't do what you think it does.

Thanks,

I tried what you put:

Code:

---

        friend ostream& operator<<(ostream& out, const Point& point)
        {
                return out<< x <<','<< y;
        }

---

and kept getting "illegal reference to non-static member 'Point::x" error.

I changed it to

Code:

---

        friend ostream& operator<<(ostream& out, const Point& point)
        {
                return out<< point.x <<','<< point.y;
        }

---

and put this in LinkedPoints.cpp

Code:

---

        cout << p1 << endl;

---

and it compiles, but it displays some large number on output that isn't what was entered.

When I try

Code:

---

Point& current = // Get a point from the list

cout<< current.getX() <<','<< current.getY() <<'\n';

---

I get a cannot convert error.

Also yea I do need to use linkedList.h.

How do I deal with these to get it to do what I am trying to do.

Code:

---

protected:
        int x;
        int y;

---

and

Code:

---

cin >> x, y;

---

How can i get this line working:

Code:

---

list1.print();

---

Isn't that the best way to print out the list with ostream operators in linkedList.h?

What would you do to get this entire block of code working like I said above? Because I know I'm doing something wrong with the cin>>x, y; and way I'm asking for points, but I'm not sure how to populate the linked list with points then print the points out everything I try doesn't work. I have no problem doing a linked list with simple data types like int and printing it back and manipulating it however I want. The problem lies with just using my point class instead of int as nodes in the list.

Code:

---

// LinkedPoints.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "linkedList.h"
#include "Point.h"

int _tmain(int argc, _TCHAR* argv[])
{
        int x = 0;
        int y = 0;

Point p1(x, y);

linkedListType<Point> list1;

        cout<<"1) Type two numbers to make a coordinate."
                "\n2) Use the format (XX YY) only spacing the numbers not using a comma."
                "\n3) Then press Enter to add the coordinate to the list."
                "\n4) When finished adding to the list type -9999 and press Enter."
                <<endl;
                cin >> x, y;

        while(x != -9999)//execution number for list creation
                {
                        list1.insertLast(p1);//insert info into the list as long as -9999 isn't entered
                        cin >> x, y;
                }

        cout << p1 << endl;

return 0;
}

---

I have this in linkedList.h

Code:

---

        friend ostream& operator <<(ostream&, const linkedListType<Type>&);


                //Overloading the stream insertion operator
template<class Type>
ostream& operator<<(ostream& osObject, const linkedListType<Type>& list)
{
        nodeType<Type> *current; //pointer to traverse the list

        current = list.first;  //set current so that it points to
                                          //the first node
        while(current != NULL) //while more data to print
        {
          osObject<<current->info<<" ";
          current = current->link;
        }

        return osObject;
}

---

Is there some way to use that to print a linked list with the nodes as points. It works when used with basic data types like int, but says no operator << present when I try to use it to print a linked list of my points.

This is due Sunday and I've been working on it all week with no luck. Thanks again.

>and kept getting "illegal reference to non-static member 'Point::x" error.
That's one of my more common mistakes. Fortunately, it's easy to notice and quick to fix. ;)

>but it displays some large number on output that isn't what was entered
That's because your definition of Point's constructor is wrong. When the parameter names match the member names, you need to be specific about what you're assigning to:

Code:

---

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

---

Then for your insertion loop, you need a new Point each time. It's also easier to break on end-of-file, so something like this would work:

Code:

---

int main()
{
  int x = 0;
  int y = 0;

  linkedListType<Point> list1;

  cout<<"1) Type two numbers to make a coordinate."
    "\n2) Use the format (XX YY) only spacing the numbers not using a comma."
    "\n3) Then press Enter to add the coordinate to the list."
    "\n4) When finished adding to the list type Ctrl+Z.\n";

  while(cin>> x >> y)
    list1.insertLast(Point(x, y));

  list1.print();

  return 0;
}

---

Oh man, Prelude you're great this works exactly like what I was trying to do. I can't believe I was trying to get x and y with cin >> x, y. The second I saw cin >> x >> y; I was like oh man I'm stupid.

Also about the this->x = x and this->y = y was exactly correct. I knew something was wrong with how I was handling x and y and suspected it was in the Point class, but I didn't know you had to do that if the parameter names matched. Thanks for that I'll remember.

I'm going to start figuring out how to sort it by x value. If you have any tips feel free to post them.

I put my insertion sort in linkedList.h

Code:

---

        void linkedInsertionSort();
        //Function to sort by using insertion sort algorithm



template<class Type>
void linkedListType<Type>::linkedInsertionSort()
{
        nodeType<Type> *lastInOrder;
        nodeType<Type> *firstOutOfOrder;
        nodeType<Type> *current;
        nodeType<Type> *trailCurrent;

        lastInOrder = first;

        if (first == NULL)
                cout << "Cannot sort an empty list" << endl;
        else
                if (first->link == NULL)
                        cout << "List is of length 1.  Already in order" << endl;
                else
                        while (lastInOrder->link != NULL)
                        {
                                firstOutOfOrder = lastInOrder->link;
                                if (firstOutOfOrder->info < first->info)
                                {
                                        lastInOrder->link = firstOutOfOrder->link;
                                        firstOutOfOrder->link = first;
                                        first = firstOutOfOrder;
                                }
                                else
                                {
                                        trailCurrent = first;
                                        current = first->link;

                                        while (current->info < firstOutOfOrder->info)
                                        {
                                                trailCurrent = current;
                                                current = current->link;
                                        }

                                        if (current != firstOutOfOrder)
                                        {
                                                lastInOrder->link = firstOutOfOrder->link;
                                                firstOutOfOrder->link = current;
                                                trailCurrent->link = firstOutOfOrder;
                                        }
                                        else
                                                lastInOrder = lastInOrder->link;
                                }
                        }//end while
}//end linkedInsertionSort

---

When I try to use it in the program I get the errors:

"could not deduce template argument for 'const std::reverse_iterator<_RanIt> &' from 'Point'
c:\program files\microsoft visual studio 8\vc\include\xutility(1842) : see declaration of 'std:: operator <'"

and

"binary '<' : 'Point' does not define this operator or a conversion to a type acceptable to the predefined operator"

Code:

---

// LinkedPoints.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "linkedList.h"
#include "Point.h"

int _tmain(int argc, _TCHAR* argv[])
{
        int x = 0;
        int y = 0;

linkedListType<Point> list1;

        cout<<"1) Type two numbers to make a coordinate."
                "\n2) Use the format (XX YY) only spacing the numbers not using a comma."
                "\n3) Then press Enter to add the coordinate to the list."
                "\n4) When finished adding to the list press Ctrl+Z and press Enter."
                <<endl;

        while(cin >> x >> y)//execution number for list creation
        {
                        list1.insertLast(Point(x, y));
        }

system("cls");

list1.linkedInsertionSort();

        cout << "Your list of coordinates looks like this: \n" << endl;
  list1.print();


return 0;
}

---

I tried doing a similar overloading of the operator like for ostream but using "<" in my Point.h, but it didn't work at all. I think that is the problem?

Also not sure how to get it to just look at x and only compare x not y. Because it is supposed to sort by x only least to highest. Is there a better sorting algorithm to use than insertion sort for this instance?

K, I think I'm pretty close now. Here is what I added. It compiles okay, but when I run it and it reaches the list1.linkedInsertionSort() and it doesn't print the list anymore.

Well anyway here is what I added.

In Point.h I added:

Code:

---

friend bool operator < (const Point& x, const Point& y);
friend bool operator > (const Point& x, const Point& y);

---

In Point.cpp I added:

Code:

---

bool operator < (const Point& x, const Point& y)
// post: return true iff lhs < rhs
{
return x < y;
}

bool operator > (const Point& x, const Point& y)
// post: return true iff lhs < rhs
{
return x > y;
}

---

Here is my new LinkedPoints.cpp:

Code:

---

// LinkedPoints.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "linkedList.h"
#include "Point.h"

int _tmain(int argc, _TCHAR* argv[])
{
        int x = 0;
        int y = 0;

linkedListType<Point> list1;

        cout<<"#####  Follow The Steps Below To Add Points To The Linked List  #####\n"
                "\n1) Type two numbers to make a point(x, y)."
                "\n2) Use the format (XX YY) only spacing the numbers, not using a comma."
                "\n3) Then press Enter to add the coordinate to the list."
                "\n4) When finished adding to the list press Ctrl+Z then press Enter.\n"
                <<endl;

        while(cin >> x >> y)//execution number for list creation
        {
                        list1.insertLast(Point(x, y));
        }

system("cls");

list1.linkedInsertionSort();

        cout << "Your linked list of points looks like this: \n" << endl;
  list1.print();


return 0;
}

---

It compiles successfuly, but the list1.linkedInsertionSort() isn't working like I expected.

Reason I added the above Point.h and Point.cpp code is because I was getting these errors when I tried to run list1.linkedInsertionSort()


"could not deduce template argument for 'const std::reverse_iterator<_RanIt> &' from 'Point'
c:\program files\microsoft visual studio 8\vc\include\xutility(1842) : see declaration of 'std:: operator <'"

and

"binary '<' : 'Point' does not define this operator or a conversion to a type acceptable to the predefined operator"


Was I right in thinking that what I added is the solution? Did I just do it wrong? I'm almost there just need a little more help. Thanks again. I appreciate all your help.

Hey guys I finally got it. For this part of the code:

Code:

---

bool operator < (const Point& x, const Point& y)
{
return x < y;
}

bool operator > (const Point& x, const Point& y)
{
return x > y;
}

---

I had to change it to this:

Code:

---

bool operator < (const Point& x, const Point& y)
{
return x.x < y.y;
}

bool operator > (const Point& x, const Point& y)
{
return x.x > y.y;
}

---

I'd like to thank you for your help along the way Prelude.

Well, turns out something went wrong. The sorting isn't working right. It seems to only be sorting the linked list when both x and y are equal values.

For instance if I enter 50 50 40 40 30 30 20 20 10 10 it'll sort it out like it is supposed to by x value to
(10, 10)
(20, 20)
(30, 30)
(40, 40)
(50, 50)

but if I change the x and y values a little so they aren't equal on each point it doesn't sort right.

Here is my insertion sort algorithm. I think it is okay, but the problem is singling out x in the Point(x,y).

How can I single out the X value only to be sorted, but still display (x, y)?

Code:

---

template<class Type>
void linkedListType<Type>::linkedInsertionSort()
{
        nodeType<Type> *lastInOrder;
        nodeType<Type> *firstOutOfOrder;
        nodeType<Type> *current;
        nodeType<Type> *trailCurrent;

        lastInOrder = first;

        if (first == NULL)
                cout << "Cannot sort an empty list" << endl;
        else
                if (first->link == NULL)
                        cout << "List is of length 1.  Already in order" << endl;
                else
                        while (lastInOrder->link != NULL)
                        {
                                firstOutOfOrder = lastInOrder->link;
                                if (firstOutOfOrder->info < first->info)
                                {
                                        lastInOrder->link = firstOutOfOrder->link;
                                        firstOutOfOrder->link = first;
                                        first = firstOutOfOrder;
                                }
                                else
                                {
                                        trailCurrent = first;
                                        current = first->link;

                                        while (current->info < firstOutOfOrder->info)
                                        {
                                                trailCurrent = current;
                                                current = current->link;
                                        }

                                        if (current != firstOutOfOrder)
                                        {
                                                lastInOrder->link = firstOutOfOrder->link;
                                                firstOutOfOrder->link = current;
                                                trailCurrent->link = firstOutOfOrder;
                                        }
                                        else
                                                lastInOrder = lastInOrder->link;
                                }
                        }//end while
}//end linkedInsertionSort

---

Here is where I am trying to implement the x, y retrieval and sorting.

Code:

---

        cout << "\nEnter Coordinates (integers) - Use format X Y: ";

        while(cin >> x >> y)
        {
                cout << "Enter Coordinates (integers) - Use format X Y: ";
                        list1.insertLast(Point(x, y));

        }//end while

system("cls");

        cout << "Your linked list of points (sorted by x value) looks like this: \n" << endl;

        //sort linked list
        list1.linkedInsertionSort();

        //print the sorted linked list of points
        list1.print();

---

Thanks for the help so far I appreciate it. If anyone could help me with this final problem that would be great. Thanks again.

Well I can't figure out how to sort by only x. Any final tips?