#include <iostream> //for cout, endl
using namespace std;

#include "DLList_Problems.h"

//Pre: out is not errored and head is a valid list.
//
//Post: Prints a representation of head to out.
//For example, if head is the list (1 2 3),
//printList(head, out) prints (1 2 3) on out.
//For example, if head is the empty list,
//printList(head, out) prints ().
//
//Modifies: out
void printList(DLNode* head, ostream& out)
{
    out << "(";
    for (DLNode* current = head; current != NULL;
                        current = current->next) {
        //If current is not the first element of the list,
        //then it needs a space before it.
        if (current != head) {
            out << " ";
        }
        out << current->data;
    }
    out << ")";
}

//Problem 1

//Pre: last is the last element of a valid list.
//Post: Returns the number of nodes in the list
//with a value equal to last's data.
int countEqualsLast(DLNode* last)
{
    int count = 0;
    DLNode* current = last;
    while (current != NULL) {
        if (current->data == last->data) {
            ++count;
        }
        current = current->previous;
    }
    return count;
}

//Problem 2

//Pre: last is the last element of a valid list.
//Post: Deletes all the elements of the list.
void reverseDelete(DLNode* last)
{
    DLNode* current = last;
    while (current != NULL) {
        DLNode* previous = current->previous;
        delete current;
        current = previous;
    }
}

//Problem 3

//Pre: last is the last element of a valid list.
//Post: Returns true if every element of the list
//if >= 0.
bool allPositive(DLNode* last)
{
    if (last == NULL) {
        return true;
    }
    else {
        return last->data >= 0 && allPositive(last->previous);
    }
}

//Problem 4

//Pre: head is the first element of a valid list
//and last is the last element of a valid list.
//Post: Returns true if one list is the reverse
//of the other.
bool areReverses(DLNode* head, DLNode* last)
{
    if (head == NULL) {
        if (last != NULL) {
            return false;
        }
        else {
            return true;
        }
    }
    else if (last == NULL) {
        return false;
    }
    else {
        return head->data == last->data
                && areReverses(head->next, last->previous);
    }
}

//Problem 5

//Post: Creates the list of the integers from
//low up to high inclusive and stores the list's head
//in the parameter head and its last element in
//the parameter last.
//If low > high, sets head and last to NULL,
//the empty list.
//For example, createRange(1, 5, h, t) creates the list
//(1 2 3 4 5) and sets h to the node for 1 and t to
//the node for 5.
//For example, createRange(3, 2, h, t) sets
//h and t to NULL.
//
//Modifies: head and last
void createRange(int low, int high, DLNode*& head, DLNode*& last)
{
    head = NULL;
    last = NULL;
    for (int i = low; i <= high; i++) {
        DLNode* next = new DLNode;
        next->data = i;
        next->previous = last;
        if (head == NULL) {
            head = next;
        }
        else {
            last->next = next;
        }
        last = next;
        last->next = NULL;
    }
}

int main() {
    DLNode* head1;
    DLNode* tail1;
    
    createRange(1, 4, head1, tail1);
    printList(head1, cout);
    cout << endl;
    
    cout << "Number equal to last: " << countEqualsLast(tail1) << endl;
    cout << "All positive?" << allPositive(tail1) << endl << endl;
    
    DLNode* head2;
    DLNode* tail2;
    createRange(1, 1, head2, tail2);
    printList(head2, cout);
    cout << " is its own reverse? " << areReverses(head2, tail2) << endl;
    
    reverseDelete(tail1);
    reverseDelete(tail2);
    
    return 0;
}