/**		ins.cpp		**/

/** For CES 490A - another solution to HW#1 problem 3 **/

#include <iostream.h>

// Node represents an element in the linked list.
class Node {
        private:
	        int   data;
                Node *next;
	public:
	        Node();
		Node(int);
		int hasNext();
                void setNext(Node *);
		int Data();
		Node* Next();
};

// List represents a linked list.
class List{
        private:
	        Node *head;
	public:
	        List();
		void insert(int);
		void print();
};

//Constructor
Node::Node(int value) {
        data= value;
	next= NULL;
}

//Constructor
Node::Node() {
        Node(0);
}

// return true if there are more nodes
int Node::hasNext() {
        return next != NULL;
}

// set the next pointer
void Node::setNext(Node *newNext) {
        next= newNext;
}

// accessor for data
int Node::Data() {
        return data;
}

// accessor for the next pointer
Node* Node::Next() {
        return next;
}

// Constructor
List::List() {
        head= NULL;
}

// Insert an int into the list
void List::insert(int newValue) {
    Node *curr;
    Node *prev;
    Node *element = new Node(newValue);
    curr= head;
    prev= NULL;
    while (curr != NULL) {
        if (curr->Data() < element->Data()) {
	    prev= curr;
	    curr= curr->Next();
	}
	else {
	    curr= NULL;
	}
    }
    if (prev == NULL) {
        element->setNext(head);
	head= element;
    }
    else {
        element->setNext(prev->Next());
        prev->setNext(element);
    }
}

// Print the list to stdout
void List::print() {
    Node *curr= head;
    cout << "List contains:" << endl;
    while (curr != NULL) {
        cout << curr->Data() << endl;
	curr= curr->Next();
    }
}


// Main program to exercise the List class.
int main()
{
    List theList;
    theList.print();

    theList.insert(13);
    theList.print();

    theList.insert(34);
    theList.print();

    theList.insert(27);
    theList.print();

    theList.insert(5);
    theList.print();

    theList.insert(7);
    theList.print();

    theList.insert(31);
    theList.print();

    theList.insert(99);
    theList.print();

    return 0;
}