#include <iostream>
#include <string.h>

class doubled 
{
private:
    class sublink 
	{
	private:
		char data[30];
		sublink *next_ptr;
		sublink *previous_ptr;
		friend doubled;
	};

public:
	sublink *first_ptr;
	doubled(){first_ptr = NULL;};
	void add_item(char *item);
	void rm_item(char *item);
};

void doubled::add_item(char *item)
{
	sublink *new_data;
	new_data = new sublink;

	strcpy(new_data->data, item);

	// empty list case
	if(first_ptr == NULL)
	{
		// Only item in the list, I have no next or previous element
		new_data->previous_ptr = NULL;
		new_data->next_ptr = NULL;

		// Make the list point to this element
		first_ptr = new_data;
	} 
	else 
	{
		sublink* iter;
		iter = first_ptr;

		// 1 element list
		if(iter->next_ptr == NULL)
		{
			// I'm after the first and only node
			if(strcmp(iter->data, new_data->data) <= 0)
			{
				iter->next_ptr = new_data;
				new_data->previous_ptr = iter;
				new_data->next_ptr = NULL;
			}
			// I'm before the first and only node and thefore I become the new first
			else
			{
				iter->previous_ptr = new_data;
				new_data->next_ptr = iter;
				first_ptr = iter;
			}
		}
		// 2+ element list
		else
		{
			// this is never null the first time because empty list case is take care of above
			while(iter != NULL)
			{
				// Should I be inserted before the current node?
				if(strcmp(iter->data, new_data->data) >= 0)
				{
					// first node case
					if(iter->previous_ptr == NULL)
					{
						new_data->previous_ptr = NULL;
						new_data->next_ptr = iter;
						iter->previous_ptr = new_data;
						first_ptr = new_data;
						
					}
					// intermediate node case
					else if(iter->next_ptr != NULL)
					{
						iter->previous_ptr->next_ptr = new_data;
						new_data->previous_ptr = iter->previous_ptr;
						new_data->next_ptr = iter;
						iter->previous_ptr = new_data;
					}
					// last node case
					else
					{
						iter->next_ptr = new_data;
						new_data->previous_ptr = iter;
						new_data->next_ptr = NULL;
					}

					break;
				}

				// Move to next node
				iter = iter->next_ptr;
			}
		}
	}

	// Print the list
	std::cout << "List: " << std::endl;
	sublink* printer = first_ptr;
	while(printer != NULL)
	{
		std::cout << '\t' << printer->data << std::endl;

		printer = printer->next_ptr;
	}
	std::cout << std::endl;
}

int main(int argc, char* argv[])
{
	doubled d;

	char item[30] = "bla bla bla\0";
	char item2[30] = "meh\0";
	char item3[30] = "ahhhhhhhh\0";
	char item4[30] = "dayummmmm\0";
	d.add_item(item);
	d.add_item(item2);
	d.add_item(item3);
	d.add_item(item4);
	
	std::cin.get();
	return 0;
}