#include<iostream>
using namespace std;

#include "Squirrel.h"

template<class T>
struct LinkedListNode {
	T data;
	LinkedListNode* next;
};

template <class T>
class LLIterator {
	LinkedListNode<T> *curr;
public:
	LLIterator(LinkedListNode<T> *s) : curr(s) {}  // O(1)
	LLIterator operator++(){  // O(1)
		curr = curr->next;
		return *this;
	}
	bool operator!=(const LLIterator& other){  // O(1)
		return curr != other.curr;
	}
	T& operator*(){  // O(1)
		return (curr->data);
	}
};

template<class T>
class LinkedList {
	LinkedListNode<T> *start = 0;
public:
	void push_beginning(T data){
		LinkedListNode<T> *new_one = new LinkedListNode<T>;
		new_one->next = start;
		new_one->data = data;
		start = new_one;
	}
	LLIterator<T> begin(){
		return LLIterator<T>(start);
	}
	LLIterator<T> end(){
		return LLIterator<T>(0); 
	}
	void add_inorder(T data){
		LinkedListNode<T> *new_one = new LinkedListNode<T>;
		new_one->next = start;
		new_one->data = data;
		if(!start || start->data > data){
			start = new_one;
			return;
		}
		for(LinkedListNode<T> *place = start; place; place = place->next){
			if(!place->next || place->data < data){
				new_one->next = place->next;
				place->next = new_one;
				break;
			}
		}
		
	}
	T index(size_t idx){
		LinkedListNode<T> *place = start;
		for(int i = 0; i < idx; i++){ // Runs once per list item, O(n) where n is the number of list items
			place = place->next;
		}
		return place->data;
	}
	void print(){
		if(!start){
			cout << "[]\n";
			return;
		}
		cout << "[";
		LinkedListNode<T> *place = start;
		while(place){
			cout << place->data << ", ";
			place = place->next;
		}
		cout << "\b\b]\n";
	}
	~LinkedList(){
		LinkedListNode<T> *place = start;
		while(place){
			LinkedListNode<T> *todel = place;
			place = place->next;
			delete todel;
		}
	}

	template<class U>
	friend ostream& operator<<(ostream& output, LinkedList<U> &list);
	
};

template<class U>
ostream& operator<<(ostream& output, LinkedList<U> &list){
	list.print();
	return output;
}

int main(){
	LinkedList<int> int_list;
//	LinkedList<Squirrel> squirrel_list;  // Not unless we include our squirrel class!

	int_list.print();
	int_list.add_inorder(500);
	int_list.add_inorder(55);
	int_list.add_inorder(67);
	int_list.add_inorder(20);
	int_list.print();

	cout << int_list;

	LinkedList<string> word_list;
	word_list.push_beginning("bitcoin");
	word_list.push_beginning("dogecoin");
	cout << word_list;

	LinkedList<Squirrel> squirrels;
	{
		Squirrel a;
		Squirrel temp_squirrel = Squirrel("Speedy", 20, 15);
		a = temp_squirrel;
		squirrels.add_inorder(temp_squirrel);
	}
	squirrels.add_inorder(Squirrel("Fuzzy", 12, 8));
	squirrels.add_inorder(Squirrel("Trudy", 15, 8));
	squirrels.add_inorder(Squirrel("Nutty", 14, 10));
	cout << squirrels;

	LinkedList<Squirrel*> ref_squirrels;
	ref_squirrels.add_inorder(new Squirrel("Patch", 8, 7));
	ref_squirrels.add_inorder(new Squirrel("Bobcat", 8, 7));
	ref_squirrels.add_inorder(new Squirrel("Nog", 8, 7));
	for(int i = 0; i < 3; i++)  // We're going to run this loop n times
		cout << *(ref_squirrels.index(i)) << endl; // This is O(n)
	// This printing method is O(n^2)
	
	for(auto i : ref_squirrels) // This one is O(n)
		cout << *i << endl;

	for(auto i : ref_squirrels)
		delete i;

	return 0;
}