#include "stdafx.h"
#include <iostream>
#include <string>
#include <exception>

using namespace std;

//The node that we are going to use in both of our data structures
template <typename T>
struct Node
{
    T data;
    Node* next;
};

template <typename T>
class Stack{

private:
    Node<T>* head = NULL;
    int stackSize;

public:
    Stack(){
        stackSize = 0;
    }

    //We push and pop the elements from the head in order for the push/pop to be in a constant time O(1)

    void push(T n){
        Node<T>* newNode = new Node<T>();
        newNode->data = n;
        newNode->next = head;
        head = newNode;
        stackSize++;
    }


    void pop(){
        if (head == NULL) throw out_of_range("Stack Underflow");
        Node<T>* temp = head;
        head = head->next;
        delete temp;
        stackSize--;
    }

    bool isEmpty(){
        if (head == NULL) return true;
        else return false;
    }

    T top(){
        return head->data;
    }

    int size(){
        return stackSize;
    }

    void print(){
        Node<T>* temp = head;
        while (temp != NULL){
            cout << temp->data << " ";
            temp = temp->next;
        }
        cout << endl;
    }

};


template <typename T>
class SortedList{
private:
    Node<T>* head;
    int sizeOfList;

public:
    SortedList(){
        head = NULL;
        sizeOfList = 0;
    }

    void Insert(T num){
        Node<T>* newNode = new Node<T>();
        newNode->data = num;

        //If the list is empty
        if (head == NULL){
            newNode->next = NULL;
            head = newNode;
            sizeOfList++;
            return;
        }

        Node<T>* temp = head;

        while (temp->data < num && temp->next != NULL){
            temp = temp->next;
        }

        //If temp is still equal to head then it means that we haven't entered the while loop
        //and we need to insert at the head

        if (head == temp){
            if (newNode->data < temp->data){
                newNode->next = temp;
                head = newNode;
            }
            else{
                newNode->next = temp->next;
                temp->next = newNode;
            }
        }

        //Insert anywhere but the head
        else{
            newNode->next = temp->next;
            temp->next = newNode;
        }

        sizeOfList++;
    }

    void Delete(T num){
        Node<int>* temp = head;
        Node<int>* prev = temp;

        //Looking for the number that we need to delete
        while (num != temp->data){
            prev = temp;
            temp = temp->next;
        }

        //If the prev == temp that means that we didn't enter the while loop A.K.A we need to insert at the head
        if (prev == temp){
            head = temp->next;
            delete temp;
        }

        //Insert at the tail or in a position other than the head
        else{
            prev->next = temp->next;
            delete temp;
        }

        sizeOfList--;
    }

    int size(){
        return sizeOfList;
    }

    bool isEmpty(){
        return head == NULL ? true : false;
    }

    void print(){
        Node<T>* temp = head;

        while (temp != NULL){
            cout << temp->data << " ";
            temp = temp->next;
        }

        cout << endl;
    }

};


int main(){
    //Testing

    Stack<int>* s = new Stack<int>();
    cout << "The Stack: " << endl;

    s->push(13);
    s->push(5);
    s->print();
    s->pop();
    s->print();

    cout << endl;

    SortedList<int>* l = new SortedList<int>();

    cout << "The Sorted List: " << endl;

    l->Insert(13);
    l->Insert(12);
    l->Insert(14);
    l->Insert(4);
    l->Insert(44);
    l->Insert(55);
    l->Insert(1);
    l->Insert(13);


    l->print();

    l->Delete(1);
    l->print();

    l->Delete(55);
    l->print();

    l->Delete(13);
    l->print();

    cout << "The list size is: " << l->size() << endl;

}