#ifndef LINKEDLIST_H
#define LINKEDLIST_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;
}


#endif