#ifndef BETTER_LINKEDLIST_H
#define BETTER_LINKEDLIST_H

#include<iostream>

template<class T>
class list {
	struct ll_node {
		T contents;
		ll_node *next;
	};

	class sl_iterator {
		ll_node *place;
	public:
		sl_iterator(ll_node *p) : place(p) {}
		sl_iterator& operator++(){
			place = place->next;
			return *this;
		}
		bool operator!=(const sl_iterator &other) const {
			return place != other.place;
		}
		T& operator*(){
			return place->contents;
		}
	};

	ll_node *start = 0;
public:
	list() {
		std::cout << "default constructor called\n";
	}
	list(list &other){
		std::cout << "copy constructor called\n";
		size_t pos = 0;
		for(auto i : other)
			insert(i, pos++);
	}
	void push(T new_item){ //  O(1)
		ll_node *new_node = new ll_node;
		new_node->contents = new_item;
		new_node->next = start;
		start = new_node;
	}
	bool empty(){
		return start == 0;
	}
	T pop(){ // O(1)
		T result = start->contents;
		ll_node *tofree = start;
		start = start->next;
		delete tofree;
		return result;
	}
	void enqueue(T new_item){
		push(new_item); // O(1)
	}
	T dequeue(){ // O(n)
		if(!start->next){ // There's only one item
			T retval = start->contents;
			delete start;
			start = 0;
			return retval;
		}
		ll_node *spot = start;
		for(; spot->next->next; spot = spot->next);
		T retval = spot->next->contents;
		delete spot->next;
		spot->next = 0;
		return retval;
	}
	void insert(T new_item, size_t idx){
		if(!idx){
			push(new_item);
			return;
		}	
		ll_node *spot = start;
		for(; idx - 1; idx--)
			spot = spot->next;
		ll_node *new_node = new ll_node;
		new_node->contents = new_item;
		new_node->next = spot->next;
		spot->next = new_node;
	}
	void remove(size_t idx){
		if(!idx) {
			pop();
			return;
		}
		ll_node *spot = start;
		for(; idx - 1; idx--)
			spot = spot->next;
		ll_node *tofree = spot->next;
		spot->next = spot->next->next;
		delete tofree;
	}
	T& operator[](size_t idx){ // O(n)
		ll_node *spot = start;
		for(; idx; idx--)
			spot = spot->next;
		return spot->contents;
	}
	sl_iterator begin() {
		return sl_iterator(start);	
	}
	sl_iterator end() {
		return sl_iterator(0);
	}
	~list(){
		std::cout << "Destructor was called\n";
		while(start)
			pop();
	}
};

template<class T>
std::ostream& operator<<(std::ostream& out, list<T> &lst){
	out << "[";
	for(auto i : lst) 
		out << i << ", ";
	out << "\b\b]";
	return out;
}

#endif