//Syed Rais Ahmad
//CIS 610: Dyna Lists
//Assign # 5 Ques # 5

#include<iostream.h>


class llistItem
{
public:
	char item;
	llistItem * nxtItem;
};


class lList
{
private:
	llistItem * head;
public:
	lList(); 
	lList(lList&);
	~lList() {delete head;}; 
	void Add(char);
	char Get(int nth);
	int printAll();
	int getItemCount(void);

};


//create head and put NULL values in it.
lList::lList()
{
	head = new llistItem; 
	head->nxtItem=NULL;
	head->item=NULL;
}


//Copy constructor
lList::lList(lList& lli)
{
	head=new llistItem;
	int i=0,count;	
	head->nxtItem=NULL;
	count=lli.getItemCount();
	while(++i<count) Add(lli.Get(i));
}



//Add to the tail of link list
void lList::Add(char ch)
{
	llistItem * ptr=head; //a temporary listitem pointer holds head address of link list.

	while(ptr->nxtItem) 
		ptr=ptr->nxtItem; //reach the item whose nextitem points to NULL address

	ptr->nxtItem=new llistItem; //Add a new list item
	ptr=ptr->nxtItem; // temporary pointer holds new item's address
	ptr->item=ch; // Add a value to new item
	ptr->nxtItem=NULL; //make next item of new item point to NULL
}


//print all items in the link list.
int lList::printAll()
{
	llistItem * ptr=head; //ptr gets the head value
		while (ptr=(ptr->nxtItem)) //while ptr points to not NULL value
			cout << ptr->item << "\n";

	return NULL;
}


//get the nth item in Link List.
char lList::Get(int nth)
{
	if (nth<1) return -1;
	
	if (head->nxtItem)
	{
		int current=0;
		llistItem * ptr=head; //ptr gets the head value
		while(ptr->nxtItem) 
			{ 
				current++; 
				ptr=ptr->nxtItem;
				if (current==nth) {return ptr->item;}
			}

	}
	return -1;
}
//return total number of items in list
int lList::getItemCount(void)
{
	llistItem * ptr=head;
	int total=0;
	while (ptr=ptr->nxtItem) total++;
	return total;
}


//String Class
class String
{
public:
	char * value;
	String(char*);
	int Length(void); 
	lList Strcnvcl(void);
	int Strpsl(lList,lList);
	String();

};



String::String()
{
	value = new char[256];
	value[0]=NULL;
}

//Constructor if string is given
String::String(char* str)
{
	int i=-1;
	value = new char[256];
	while(str[++i]) value[i]=str[i];
	value[i]=NULL;
}


int String::Length(void)
{ 
	int len=0; 
	for(;*(value+len);len++); 
	return len;
}

//convert string to a link list
lList  String::Strcnvcl()
{
	lList ll;
	int i=-1;
	while(value[i++]) ll.Add(value[i]);
	return ll;
}

//returns position in l1, where l2 starts.
int String::Strpsl(lList l1,lList l2)
{
	int pos=0,count1,count2,temp=0;
	count1=l1.getItemCount();
	count2=l2.getItemCount();

	while(++pos<count1)
	{
		if ( (l1.Get(pos))==l2.Get(1) )
		{
			temp=1;
			if (count2==1) return pos;
			while(++temp<=count2) 
			{
				if (l1.Get(pos+temp-1)!=l2.Get(temp)) break; 
				if (temp==count2) return pos;
			}
		}
	}

	return -1;
}


//------- Program's main flow starts ---------------------------


main()
{
	
	String s1("HelloWorld"),s2("loW");
	lList l1=s1.Strcnvcl(),l2=s2.Strcnvcl();
	
	cout << "loW in HelloWorld exits at position: " << s1.Strpsl(l1,l2) << '\n';

	return 0;

}