// Program to create and manipulate Doubly Linked List under C++.
// Assignment-23
// dllucpp.cpp, Author - Krishna Kumar Khatri.

// Uncomment ONLY the following line if you are using Turbo/Borland compiler.
// #define TC
#ifdef TC
	#include <iostream.h>
#else
	#include <iostream>
	using namespace std;
#endif
#include <conio.h>  // For getch.
// Better not to use library's NULL.
const int null = 0;

// Forward class declaration and global head var.
class DoubLL;
DoubLL* head = null;

class DoubLL
{
		DoubLL* prev;
		int info;
		DoubLL* next;
	public:
		void insertion(const int&);    // Ordered insertion.
		void deletion(const char&);
		void display();
};

void DoubLL::insertion(const int& n)
{
	DoubLL* freshnode;
	DoubLL* temp;
	DoubLL* save;

	freshnode = new DoubLL;
	freshnode->info = n;

	if (head == null) {
		freshnode->prev = null;
		freshnode->next = null;
		head = freshnode;
	} else {
		save = temp = head;
		while (temp->next != null && temp->info <= n) {
			save = temp;
			temp = temp->next;
        }

		if (temp->next == null && temp->info <= n) {
            temp->next = freshnode;		
            freshnode->prev = temp;
            freshnode->next = null;
        } else {
            save->next = freshnode;
            freshnode->prev = save;
            freshnode->next = temp;
            temp->prev = freshnode;
        }
	}
}

void DoubLL::deletion(const char& oprmode)
{
	int inpt;
	int lstcnt = 0, i = 0;
	DoubLL* temp = new DoubLL;
	DoubLL* save;

	temp = head;
	while (temp != null) {
		lstcnt++;
		temp = temp->next;
	}

	if (oprmode == 'p') {
		do {
			cout << "\n\nEnter index position (1-" << lstcnt << "): ";
			cin >> inpt;
		} while (inpt < 1 || inpt > lstcnt);

		inpt--;   // For obtaining the index of deletion position.
		temp = head;
		while (i < inpt && temp != null) {
			i++;
			save = temp;
			temp = temp->next;
		}
		if (temp != null) {
			if (temp == head)
				head = temp->next;
			else
				save->next = temp->next;
			delete temp;
			cout << "Element deleted.";
		}
	} else {
		cout << "\n\nEnter element: "; cin >> inpt;

		temp = head;
		while (inpt != temp->info && temp != null) {
			save = temp;
			temp = temp->next;
		}

		if (temp != null) {
            if (temp == head)
				head = temp->next;
            else 
                save->next = temp->next;
            delete temp;
            cout << "Element deleted.";
  		} else
  		    cout << "Element not found in the list!";
	}
}

void DoubLL::display()
{
	DoubLL* temp = head;

	while (temp != null) {
		cout << temp->info << " ";
		temp = temp->next;
	}
}

int main()
{
	#ifdef TC
		clrscr();
	#endif
	DoubLL obj;
	int n;
	char choice;

	do {
		cout << "[i] Insert." << endl;
		cout << "[x] Delete." << endl;
		cout << endl << "What to do (i/x): ";
		choice = getche();
		switch (choice) {
			case 'i':
				cout << "\n\nWhat to insert: "; cin >> n;
				cout << "Inserting: " << n;
				obj.insertion(n);
				break;
			case 'x':
				if (head == null) {
					cout << endl << endl << "Doubly linked list empty.";
					cout << endl << "Cannot perform this operation.";
					break;
				}
				cout << endl << endl;
				cout << "Delete." << endl;
				cout << "[p] Position." << endl;
				cout << "[e] Element." << endl;
				cout << endl << "What will you specify (p/e): ";
				choice = getche();
				if (choice == 'p' || choice == 'e')
					obj.deletion(choice);
				else
					cout << "Invalid choice!";
				break;
		}
		cout << "\nUpdated list: ";
		obj.display();
		cout << endl << endl;
		cout << "Continue (y/n)... "; choice = getche();
		if (choice == 'y' || choice == 'Y') {
			cout << endl << endl;
		}
	} while (choice == 'y' ||
			 choice == 'Y');

	cout << endl << endl << "Program over. Press any key to exit...";
	getch();
	return 0; // Successful termination.
}