//My Linked List Toolkit



#include<cstdlib>	//Provides "EXIT_SUCCESS" and "system( )"
#include<string>	//Provides the "string" type qualifier
#include<iostream>	//Provides "cin" and "cout"
	
using namespace std;



/******* Linked List Function Prototypes *********/

void list_head_insert(node*& head_ptr, const node::double& entry);

void list_tail_insert(node*& head_ptr, const node::double& entry);

void list_insert(node* previous_ptr, const node::value_type& entry);

void list_remove(node* previous_ptr);

const node* list_search(const node* head_ptr, const node::value_type& target);

node* list_locate(node* head_ptr, int position);

void view_list(node* head_ptr);

int list_length(const node* head_ptr):

void list_copy(const node* source_ptr, node*& head_ptr, node*& tail_ptr);

void list_clear(node*& head_ptr);

void list_head_remove(node*& head_ptr);

/******* Other Functions *********/

void print_menu();

void exit_message();





//prototype for my list

struct node
{ 
     string employee_name;
     int    phone_number;

     node *next_ptr;
     node *previous_ptr;
}     




int main()
{

char choice = 'x';


	do
	{
	
	
		print_menu();
		cin >> choice;
		switch(choice)
		{
		
			case 1:	list_head_insert();
				break;

			case 2:	list_tail_insert();
				break;

			case 3:	void list_insert();
				break;
		
			case 4:	list_remove();
				break;

			case 5:	list_search();
				break;

			case 6:	list_locate();
				break;

			case 7:	view_list();
				break;

			case 8:	list_length();
				break;

			case 9:	list_copy();
				break;

			case 9:	list_clear();
				break;

			case 11	list_head_remove();
				break;

			case 12	exit_message();
				break;

		
			default: cout << "Invalid Entry.  Please Try Again.";
				

		}			
		

	}while (choice != 12);


	

return EXIT_SUCCESS;

}



/******************** Function Definitions ************************/

void print_menu()
{

	     cout	<< endl << endl 
			<< "\t\t*******************************************\n"
			<< "\t\t*               MAIN MENU                 *\n"
			<< "\t\t*******************************************\n"
			<< "\t\t*                                         *\n"
			<< "\t\t*  1-> ADD to the front of the list       *\n"
			<< "\t\t*  2-> ADD to the  back of the list       *\n"
			<< "\t\t*                                         *\n"
			<< "\t\t*  3-> INSERT a node                      *\n"
			<< "\t\t*  4-> DELETE a node                      *\n"
			<< "\t\t*                                         *\n"
			<< "\t\t*  5-> SEARCH                             *\n"
			<< "\t\t*                                         *\n"
			<< "\t\t*  6-> VIEW a specific node               *\n"
			<< "\t\t*  7-> VIEW entire list		          *\n" 
			<< "\t\t*  8-> VIEW list LENGTH                   *\n"
			<< "\t\t*                                         *\n"
			<< "\t\t*  9-> COPY the current list	          *\n"
			<< "\t\t* 10-> CLEAR the entire list              *\n"
			<< "\t\t*                                         *\n"
			<< "\t\t* 11-> Remove HEAD node                   *\n"
			<< "\t\t*                                         *\n"
			<< "\t\t* 12-> QUIT                               *\n"
			<< "\t\t*                                         *\n"
			<< "\t\t*******************************************\n"
			<< endl << endl;

}



void list_head_insert(node*& head_ptr, const node::double& entry)
{
	head_ptr = new node(entry, head_ptr);
}



void list_tail_insert(node*& head_ptr, const node::double& entry)
{
	tail_ptr = new node(entry, head_ptr);
}



void list_insert(node* previous_ptr, const node::value_type& entry)
{
	node *insert_ptr;

	insert_ptr = new node;

	insert_ptr->set_data(entry);

	insert_ptr->set_link(previous_ptr->link());		//Make the new node point to the node after insertion

	previous_ptr->set_link(insert_ptr);		        //Made the previous node point to the newly inserted node
}



void list_remove(node* previous_ptr)
{
	node *remove_ptr;

	remove_ptr = previous_ptr->link();

	previous_ptr->set_link(remove_ptr->link());

	delete remove_ptr;
}



const node* list_search(const node* head_ptr, const node::value_type& target)
{
	const node *cursor;

	for (cursor = head_ptr; cursor != NULL; cursor = cursor->link())

		if (target == cursor->data())

			return cursor;
	
	return NULL;
}




node* list_locate(node* head_ptr, int position)
{
	const node* cursor;

	cursor = head_ptr;

	for (int i = 1; (i < position) && (cursor != NULL): ++i)

		cursor = cursor->link();

	return cursor;
}




void view_list(node* head_ptr)
{
	const node *cursor;

	for (cursor = head_ptr; cursor != NULL; cursor = cursor->link())

		cout << cursor->get_data(entry);	//or just "cout << entry" perhaps?
}



int list_length(const node* head_ptr)
{
	const node *cursor;
	
	int answer = 0;

	for (cursor = head_ptr; cursor != NULL; cursor = cursor->link())
		
		++answer;

	return answer;
}


//I would like the copy of the linked list to be displayed next to the original list when view_list() is called

void list_copy(const node* source_ptr, node*& head_ptr, node*& tail_ptr)
{
	head_ptr = NULL;
	tail_ptr = NULL;

	//Handle the case of the empty list
	if (source_ptr == NULL)
		return;

	//Make the head node for the newly created list and put data in it.
	list_head_insert(head_ptr, source_ptr->data());
	tail_ptr = head_ptr;

	//Copy the reast of the nodes one at a time, adding at the tail of the new list
	source_ptr = source_ptr->link();
	while (source_ptr != NULL)
	{
		list_insert(tail_ptr, source_ptr->data());
		tail_ptr = tail_ptr->link();
		source_ptr = source_ptr->link();
	}
}


void list_clear(node*& head_ptr)
{
	while (head_ptr != NULL)

		list_head_remove(head_ptr);
}



void list_head_remove(node*& head_ptr)
{
	node *remove_ptr;

	remove_ptr = head_ptr;
	
	head_ptr = head_ptr->link();
	
	delete remove_ptr;
}


void exit_message()

{
	cout << "\n\tProgram will now terminate " << endl;
}

#include <iostream>
#include <string>

using namespace std;

struct node {
  string  data;
  node   *prev;
  node   *next;
public:
  node(const string& init, node *p, node *n)
    : data(init)
    , prev(p)
    , next(n)
  {}
};

struct list {
  node   *head;
public:
  list()
    : head(0)
  {}
};

void push_front(list& l, const string& data);
void push_back(list& l, const string& data);
void pop_front(list& l);
void pop_back(list& l);
void insert_after(list& l, node* it, const string& data);
void remove_this(list& l, node* it);
void show_list(list& l);

int main()
{
  list l;

  push_front(l, "test1");
  show_list(l);
  push_front(l, "test2");
  show_list(l);
  push_back(l, "test3");
  show_list(l);
  push_back(l, "test4");
  show_list(l);
  pop_front(l);
  show_list(l);
  pop_back(l);
  show_list(l);
  insert_after(l, l.head->next, "test5");
  show_list(l);
  remove_this(l, l.head->next);
  show_list(l);
}

void push_front(list& l, const string& data)
{
  if (!l.head) {
    l.head = new node(data, 0, 0);
  }
  else {
    node *new_node = new node(data, l.head->prev, l.head);
    l.head->prev = new_node;
    l.head = new_node;
  }
}

void push_back(list& l, const string& data)
{
  if (!l.head) {
    push_front(l, data);
  }
  else {
    node *it = l.head;
    while (it->next) {
      it = it->next;
    }
    node *new_node = new node(data, it, it->next);
    it->next = new_node;
  }
}

void pop_front(list& l)
{
  if (!l.head) {
    return;
  }
  else {
    node *old_node = l.head;
    l.head = l.head->next;
    if (l.head) {
      l.head->prev = 0;
    }
    delete old_node;
  }
}

void pop_back(list& l)
{
  if (!l.head) {
    return;
  }
  else {
    node *it = l.head;
    while (it->next) {
      it = it->next;
    }
    node *old_node = it;
    if (it->prev) {
      it->prev->next = it->next;
    }
    delete old_node;
  }
}

void insert_after(list& l, node* it, const string& data)
{
  if (!l.head) {
    push_front(l, data);
  }
  else {
    node *new_node = new node(data, it, it->next);
    if (it->next && it->next->prev) {
      it->next->prev = new_node;
    }
    it->next = new_node;
  }
}

void remove_this(list& l, node* it)
{
  if (!it) {
    return;
  }
  else if (it == l.head) {
    pop_front(l);
  }
  else {
    if (it->prev) {
      it->prev->next = it->next;
    }
    if (it->next) {
      it->next->prev = it->prev;
    }
    delete it;
  }
}

void show_list(list& l)
{
  node *it;

  cout<<"Forward: ";
  for (it = l.head; it->next; it = it->next) {
    cout<< it->data <<"->";
  }
  cout<< it->data <<endl;
  cout<<"Reverse: ";
  for (; it->prev; it = it->prev) {
    cout<< it->data <<"->";
  }
  cout<< it->data <<endl;
}

#include<iostream>
using namespace std;

struct StackFrame
{
	char data;

	StackFrame *link;
};


typedef StackFrame* StackFramePtr;



class Stack
{

public:

	Stack();

	Stack(const Stack& a_stack);

	~Stack();

	void push(char the_symbol);

	char pop();

	bool empty() const;

private:

	StackFramePtr top;

};



int main()
{

	Stack s;
	
	char next, ans;


	do
	{

		cout << "Enter a word: ";
		
		cin.get(next);

		while (next != '\n')
		{

			s.push(next);

			cin.get(next);

		}

	    cout << "Written backward that is: ";
		
		while ( ! s.empty() )
			cout << s.pop();

		cout << endl;


		cout << "Again? (y/n): ";

		cin >> ans;

		cin.ignore(10000, '\n');

	}while (ans != 'n' && ans != 'N');


	return 0;

}


//Function Definitions

Stack::Stack() : top(NULL)
{ }


Stack::Stack(const Stack& a_stack)
{

	if (a_stack.top == NULL)
		top = NULL;

	
	else
	{

		StackFramePtr temp = a_stack.top;  //temp moves through the nodes from top to bottom of a_stack

		StackFramePtr end;  //Points to end of the new stack;

		
		end = new StackFrame;

		end->data = temp->data;

		top = end;
		//First node crated and filled with data.
		//New nodes are now added AFTER this first node.


		temp = temp->link;

		while (temp != NULL)
		{

			end->link = new StackFrame;

			end = end->link;

			end->data = temp->data;

			temp = temp->link;
		}

		end->link = NULL;
	}

}



Stack::~Stack()
{
	char next;

	while (! empty() )
		next = pop();  //pop calls delete.

}



bool Stack::empty() const
{
	return (top == NULL);
}


void Stack::push(char the_symbol)
{

	StackFramePtr temp_ptr;

	temp_ptr = new StackFrame;



	temp_ptr->data = the_symbol;



	temp_ptr->link = top;

	top = temp_ptr;

}


char Stack::pop()
{
	
	if (empty())
	{
		
		cout << "Error: popping an empty stack.\n";
		exit(1);

	}

	char result = top->data;


	StackFramePtr temp_ptr;

	temp_ptr = top;

	top = top->link;


	delete temp_ptr;


	return result;

}

Stack::Stack() : top(NULL)
{ }

top = NULL;

//copy constructor

Stack::Stack(const Stack& a_stack)
{

	if (a_stack.top == NULL)
		top = NULL;

	
	else
	{

		StackFramePtr temp = a_stack.top;  //temp moves through the nodes from top to bottom of a_stack

		StackFramePtr end;  //Points to end of the new stack;

		
		end = new StackFrame;

		end->data = temp->data;

		top = end;
		//First node crated and filled with data.
		//New nodes are now added AFTER this first node.


		temp = temp->link;

		while (temp != NULL)
		{

			end->link = new StackFrame;

			end = end->link;

			end->data = temp->data;

			temp = temp->link;
		}

		end->link = NULL;
	}

}