#include <iostream>
#include <string>
#include <cmath>

using namespace std;

struct Node {
    double data;
    Node *next;
};

void add2front(Node *&list, double value);
void printList(Node *list);
int length(Node *list);
Node* findMatchingNode(Node *list, double key);
void  add2back(Node * &list, double newVal);
void deleteFirstNode (Node * &list);

void addInOrder(Node *&list, double data);

void deleteWholeList(Node *list) {
	// keep deleting while list is not empty
	while (list != 0) {
		deleteFirstNode(list);
	}
}

int main() {
    // make an empty list
    Node *list;
    list = 0;

	cout << "Length is " << length(list) << endl;

    // add some things to list
    addInOrder(list, 32532);
    addInOrder(list, -55555);
    addInOrder(list, 222222);
    addInOrder(list, -133465345);
	
	addInOrder(list, 3565);	

	//deleteFirstNode(list);

    // print the list
    printList(list);
    cout << "Length is " << length(list) << endl;

    return 0;
}


bool isBefore(double val1, double val2) {
	return fabs(val1) < fabs(val2);

}

void addInOrder(Node *&list, double data) 
{
	if (list != 0 && isBefore(list->data, data) )  {
		// recursive step -- pass buck 
		addInOrder(list->next, data);
	}
	else {
		// base case -- if list is null OR I'm at the right spot -- add now
		add2front(list, data);
	}


}


// Add new 'data', in ordered location in the list
void old_addInOrder(Node *&list, double data) 
{
	// Make new node for the new data
	Node *temp = new Node;
	temp->data = data;

	if (list == 0) {
		// list is empty!
		list = temp;
		temp->next = 0;
	}
	else if (data < list->data)  
	{
		// special case if inserting into front
		temp->next = list;
		list       = temp;
	}
	else {
		Node *ptr = list;

		// Keep going so long as 'next' node is still less than our new data
		// When finished, ptr points to node BEFORE we want to insert new data
		while ( (ptr->next != 0)  && (ptr->next->data < data) )
		{
			ptr = ptr->next;
		}

		// Set new node to point to REMAINDER of old list
		temp->next = ptr->next;

		// connect new node to old list
		ptr->next = temp;
	}
}

void deleteFirstNode (Node * &list) 
{
	Node *temp;
	temp = list;   // remember first node
	list = list->next;   // bypass first node
	delete temp;         // delete first node

}


// Recursive function to print the list
void printList(Node* p) {
    if (p!=0){
        cout << p ->data << endl;
        printList(p->next);
    }
}


// returns the length of the list, 0 if empty
int length(Node *list) {
	// base case
	if (list == NULL) {
		return 0;
	}

	// recursive step
	int length_of_rest = length(list->next);
	int total  = 1 + length_of_rest;
	cout << "right now,  length is : " << total << endl;
	return total;
}

// returns the length of the list, 0 if empty
int length_iterative(Node *list) {
    int count =0;
	while (list != NULL) 
	{
		count++;         // count this node
		list = list->next; // bump to next

	}
	return count;
}

// inserts 'value' at front of the list (head of list)
void add2front(Node *&list, double value)
{
    // create new node
	Node *temp = new Node;
	temp->data = value;

	// point new node to the old list
	temp->next = list;

	// update list to point to new node
	list = temp;
}




Node* findMatchingNode(Node *list, double key) 
{
	Node *ptr = list;
	for ( ; ptr != 0; ptr = ptr->next ) 
	{
		if (ptr->data == key ) {
			return ptr;
		}
	}

	return 0;
}



// Prints all the data in the list
void older_printList(Node *list)
{
    Node *ptr;

	for (ptr = list;  ptr != 0 ;  ptr = ptr->next ) {
		cout << ptr->data << endl;  // print	
	}
}


// Prints all the data in the list
void old_printList(Node *list)
{
   Node *ptr;
   ptr = list;
   while (ptr != 0)  
   {
		cout << ptr->data << endl;  // print
		ptr = ptr->next;   // bounce to next
   }
}

// Returns the sum of all elements in the list
int calcSum(Node *list) 
{
	int sum = 0;
	Node *ptr = list;
	while (ptr != 0) {
		sum = sum + ptr->data;
		ptr = ptr->next;
	}
	return sum;
}


// Returns the minimum value in the list
// Assumes list is not empty!
double findMin(Node *list) 
{
	if (list == 0)
		return 0;
	double min = list->data;
	Node *ptr;
	for ( ptr = list  ; ptr != 0; ptr = ptr->next) 
	{
		if (ptr->data < min) 
		{
			min = ptr->data;
		}
	}

	return min;
}