#include<iostream>


class string_list {
	struct ll_node {
		std::string 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;
		}
		std::string& operator*(){
			return place->contents;
		}
	};

	ll_node *start = 0;
public:
	void push(std::string new_string){
		ll_node *new_node = new ll_node;
		new_node->contents = new_string;
		new_node->next = start;
		start = new_node;
	}
	bool empty(){
		return start == 0;
	}
	std::string pop(){
		std::string result = start->contents;
		ll_node *tofree = start;
		start = start->next;
		delete tofree;
		return result;
	}
	void insert(std::string new_string, size_t idx){
		if(!idx){
			push(new_string);
			return;
		}	
		ll_node *spot = start;
		for(; idx - 1; idx--)
			spot = spot->next;
		ll_node *new_node = new ll_node;
		new_node->contents = new_string;
		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;
	}
	std::string& 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);
	}
};

std::ostream& operator<<(std::ostream& out, string_list &lst){
	out << "[";
	for(auto i : lst) 
		out << i << ", ";
	out << "\b\b]";
	return out;
}

using namespace std;
int main(){
	string_list test_list;
	test_list.push("fox");
	test_list.push("wolf");
	test_list.push("dingo");
	test_list.push("coyote");
	// print in order
	for(int i = 3; i >= 0; i--) // O(n^2) runtime for this!
		cout << test_list[i] << endl;
	test_list[1] = "grey wolf";
	for(auto i : test_list)
		cout << i << endl;
	
	cout << "**\n";
	for(auto i = test_list.begin(); i != test_list.end(); ++i)
		cout << *i << endl;
	cout << "**\n";

	test_list.insert("other fox", 2);
	test_list.insert("extra fox", 5);
	cout << "Using operator <<:  " << test_list << endl;

	test_list.remove(2);
	test_list.remove(4);
	cout << "After remove:  " << test_list << endl;

	// pop everything off
	while(!test_list.empty())
		cout << test_list.pop() << endl;

	return 0;
}