//
//  list.cpp
//  CC215
//
//  Created by Manal Helal on 14/10/2014.
//  Copyright (c) 2014 AASTMT. All rights reserved.
//

//#include<iostream.h>
//#include<conio.h>
#include<stdio.h>
#include<stdlib.h>


class list
{
	struct node
	{
		int data;
		node *link;
	}*p;
public:
	void inslast(int);
	void insbeg(int);
	void insnext(int,int);
	void delelement(int);
	void delbeg();
	void dellast();
	void disp();
	int seek(int);
    int intseek(int value);
	list(){p=NULL;}
	~list();
};

void list::inslast(int value)
{
	node *q,*t;
	if(p==NULL)
	{
		p=new node;
		p->data=value;
		p->link=NULL;
	}
	else
	{
		q=p;
		while(q->link!=NULL)
			q=q->link;
		t=new node;
		t->data=value;
		t->link=NULL;
		q->link=t;
	}
	printf("Inserted successfully at the end..\n");
	disp();
}

void list::insbeg(int value)
{
	node *q;
	q=p;
	p=new node;
	p->data=value;
	p->link=q;
	printf("Inserted successfully at the begining..\n");
	disp();
}

void list::insnext(int value,int position)
{
    
    node *q,*t;
    int i = 0;
	if(p==NULL) {
		p=new node;
		p->data=value;
		p->link=NULL;
	}
    else if (position ==1) {
        this->insbeg(value);
    }
	else {
		q=p;
        for( i=0;((i<position-2)&&(q->link!=NULL)) ;i++)
			q=q->link;
		t=new node;
		t->data=value;
		t->link=q->link;
		q->link=t;
	}
	printf("Inserted successfully at position %d ..\n", (i+1));
	disp();
    
}


void list::delelement(int x)
{
	node *q,*r;
	q=p;
	if(q->data==x)
	{
		p=q->link;
		delete q;
		return;
	}
	r=q;
	while(q!=NULL)
	{
		if(q->data==x)
		{
			r->link=q->link;
			delete q;
			return;
		}
		r=q;
		q=q->link;
	}
	printf("Element u entered   %d    is not found..\n", x);
}

void list::delbeg()
{
	printf("The list before deletion:\n");
	disp();
	node *q;
	q=p;
	if(q==NULL)
	{
		printf("No data is present..\n");
		return;
	}
	p=q->link;
	delete q;
	return;
}


void list::dellast()
{
	printf("The list before deletion:\n");
	disp();
	node *q;
	q=p;
	if(q==NULL)
	{
		printf("There is no data in the list..\n");
		return;
	}
	if(q->link==NULL)
	{
		p=q->link;
		delete q;
		return;
	}
    
	while(q->link->link!=NULL)
		q=q->link;
	q->link=NULL;
	return;
}

list::~list()
{
	node *q;
	if(p==NULL) return;
	while(p!=NULL)
	{
		q=p->link;
		delete p;
		p=q;
	}
}

void list::disp()
{
	node *q;
	q=p;
	if(q==NULL)
	{
		printf("No data is in the list..\n");
		return;
	}
	printf("The items present in the list are :\n");
	while(q!=NULL)
	{
		printf("	%d", q->data);
		q=q->link;
	}
    printf("\n");
}


int list::seek(int value)
{
	node *temp;
	temp=p;
	int position=0;
	while(temp!=NULL)
	{
		if(temp->data==value)
			return position+1;
		else
		{
			temp=temp->link;
			position=position+1;
		}
	}
	printf("Element %d not found\n", value);
	return 0;
}


int list::intseek(int value)
{
	node *temp;
	temp=p;
	int position=0;
	while(temp!=NULL)
	{
		if(temp->data==value)
			return position+1;
		else
		{
			temp=temp->link;
			position=position+1;
		}
	}
	printf("Element %d not found\n", value);
	return 0;
}


int main()
{
    list l;
    int ch,v,p,ps;
    do
    {
        printf("Operations on List.. \n");
        printf("1.Insertion \n2.Deletion \n3.Display \n4.Seek \n5.Exit\n");
        printf("Enter ur choice:\n");
        scanf("%d", &ch);
        
        switch(ch)
        {
            case 1:
                printf("1.Insertion at begining \n2.Insertion at the end \n");
                printf("3.Insertion after the mentioned position\n");
                printf("Enter ur choice:\n");
                scanf("%d", &ps);
                printf("Enter the value to insert:\n");
                scanf("%d", &v);
                switch(ps)
            {
                case 1:
                    l.insbeg(v);
                    break;
                case 2:
                    l.inslast(v);
                    break;
                case 3:
                    printf("Enter the position to insert the value:\n");
                    scanf("%d", &p);
                    l.insnext(v,p);
                    break;
                    
                default:
                    printf("The choice is invalid\n");
                    return 0;
            }
                break;
                
            case 2:
                printf("1.Delete the first element \n2.Delete the last element\n");
                printf("3.Enter the element to delete from the list \n");
                printf("Enter ur choice:\n");
                scanf("%d", &ps);
                switch(ps)
            {
                case 1:
                    l.delbeg();
                    printf("The list after deletion: \n");
                    l.disp();
                    break;
                case 2:
                    l.dellast();
                    printf("The list after deletion: \n");
                    l.disp();
                    break;
                case 3:
                    l.disp();
                    printf("Enter the element to delete :\n");
                    scanf("%d", &v);
                    l.delelement(v);
                    printf("The list after deletion: \n");
                    l.disp();
                    break;
                    
                default:
                    printf("The option is invalid...\n");
                    break;
            }
                break;
                
            case 3:
                l.disp();
                break;
                
            case 4:
                l.disp();
                printf("Enter the element to search: \n");
                scanf("%d", &v);
                printf("The position of the element %d  is %d\n", v, l.seek(v));
                getchar();
                break;
                
            case 5:
                exit(1);
                
            default:
                printf("The option is invalid...\n");
                return 0;
        }
        getchar();
    } while(ch!=5);
    getchar();
    return 0;
}