//Answers to Problems 1 of Working With Linked Lists.

#include <cctype> //for isspace
#include <cstdlib> //for NULL
#include <iostream> //for ostream, istream, cin, cout, endl
using namespace std;

struct Node {

//The data for this node.
int data;

//A link to the next node in the list,
//NULL if there isn't one.
Node* link;
};

//Pre: If next is given, it is a valid linked list.
//Post: Returns a new Node with its data equal to value and
//its link equal to next or NULL if next isn't given. The
//caller is responsible for deleting the memory of the new Node.
Node* createNode(int value, Node* next = NULL)
{
    Node* newNode = new Node;
    newNode->data = value;
    newNode->link = next;
    return newNode;
}

//Pre: out is not errored and head is a valid linked list.
//Post: head has been printed to out. For example, if head
//is the list (1 2 3), (1 2 3) is printed on out.
//If head is NULL, the empty list, () is printed.
void printList1(Node* head, ostream& out)
{
    out << "(";
    for (Node* current = head; current != NULL; current = current->link) {
        if (current != head) {
             out << " ";
        }
        out << current->data;
    }
    out << ")";
}

//Pre: head is a valid link list.
//Post: The memory of the linked list has
//been deleted.
void deleteList(Node* head)
{
    if (head == NULL) {
    }
    else {
        deleteList(head->link);
        delete head;
    }
}

//Problem 1

//Declarations:

//Post: Returns a list containing the numbers from 0 up to
//and including the given number. Return the empty list
//if the 0 > number.
Node* countUp(int number);

//Post: Returns a list containing the numbers from count up to
//and including number. Returns the empty list
//if count > number.
Node* countUp(int number, int count);

//Implementations:

//Post: Returns a list containing the numbers from 0 up to
//and including the given number. Return the empty list
//if the 0 > number.
Node* countUp(int number)
{
    return countUp(number, 0);
}

//Post: Returns a list containing the numbers from count up to
//and including number. Returns the empty list
//if count > number.
Node* countUp(int number, int count)
{
    if (count > number) {
        return NULL;
    }
    else {
        return createNode(count, countUp(number, count + 1));
    }
}

//Problem 2

//Pre: head is a valid linked list.
//Post: Returns a list of all the values in head
//equal to value.
Node* collectMatches(Node* head, int value)
{
    if (head == NULL) {
        return NULL;
    }
    else if (head->data == value) {
        return createNode(value, collectMatches(head->link, value));
    }
    else {
        return collectMatches(head->link, value);
    }
}


//Problem 3

//Declarations:

//Pre: in is not errored and has a valid list description
//ready to be read.
//Post: Returns the list corresponding to that that was on in.
Node* readList(istream& in);

//Pre: in is not errored.
//Post: Any leading spaces on in have been read.
void skipSpaces(istream& in);

//Pre: in is not errored and contains the portion
//of a list description following the opening parenthesis.
//Post: Returns the list corresponding to what
//remains on in.
Node* readRestOfList(istream& in);

//Implementations:

//Pre: in is not errored and has a valid list description
//ready to be read.
//Post: Returns the list corresponding to that that was on in.
Node* readList(istream& in)
{
    char left;
    in >> left;
    return readRestOfList(in);
}

//Pre: in is not errored.
//Post: Any leading spaces on in have been read.
void skipSpaces(istream& in)
{
    while (isspace(in.peek())) {
        in.get();
    }
}

//Pre: in is not errored and contains the portion
//of a list description following the opening parenthesis.
//Post: Returns the list corresponding to what
//remains on in.
Node* readRestOfList(istream& in)
{
    skipSpaces(in);
    if (in.peek() == ')') {
        return NULL;
    }
    else {
        int next;
        in >> next;
        return createNode(next, readRestOfList(in));
    }
}

int main()
{
    int n;
    cout << "Enter a number: ";
    cin >> n;

    Node* zeroToN = countUp(n);
    cout << endl << "countUp(" << n << ") is the list ";
    printList1(zeroToN, cout);
    cout << endl << endl;

    Node* matches = collectMatches(zeroToN, 3);
    cout << "collectMatches(countUp(" << n << "), 3) is the list ";
    printList1(matches, cout);
    cout << endl << endl;
    
    cout << "Enter a list: ";
    Node* aList = readList(cin);
    cout << endl << "You entered the list: ";
    printList1(aList, cout);
    cout << endl;
    
    deleteList(zeroToN);
    deleteList(matches);
    deleteList(aList);
    
    return 0;
}