//revised 96 01 07
// tasks
// to improve copy constructor of TList to avoid double transfer

#include <iostream.h>;


/////////////////// link clases //////////////////////////////////

class Link
{

public:
	Link ( Link* pNext )  : _pNext(pNext), _id(0) {}

	Link*   Next () const { return _pNext; }
	SetNext (Link* pNext) {  _pNext = pNext; }

	int id() 	          { return _id; }
	Setid(int id)         {  _id = id; }

private:
	Link*   _pNext;
	int _id;
};




template <class T>
class TLink : public Link
{
T data;
public:
TLink(Link* pNext, const T& a) : Link ( pNext ), data(a){}
//friend ostream& operator << ( ostream& stm, const TLink<T>& tlink );
friend ostream& operator << ( ostream& stm, const TLink& tlink );

const T* Data() const{ return &data;}

const T CpyData()
const{
	//T retdata(data);
	//return retdata;
     }


};




//////////////////////// base class of list clases ////////////////////////

class List
{
public:
int cu;
	List (): _pHead (0), cu(0) {}
	// ~List ();
	//void Add ();
	//const Link * Get();
	const Link* GetHead () const { return _pHead; }

//protected:
	Link* _pHead;


~List ()
{
	//cout<<endl<<" ~List() activated";
	// free the list
	while ( _pHead != 0 )
	{
		Link* pLink = _pHead;
		_pHead = _pHead->Next(); // unlink pLink

		//cout<<endl<<" deleting ";
		delete pLink;
	}
}






/*
void Add ()
{
	// add in front of the list
	Link* pLink = new Link ( _pHead );
	if(pLink != 0)
	{ _pHead = pLink; }
cu++;
}

*/


int LinkNum ()
{
   int count = 0;
   Link* pLink = _pHead;
	while ( pLink != 0 )
	 {
	  pLink = pLink->Next(); count++;
	 }
return count;
}




int RenumLink ()
{
   int count = 1;
   Link* pLink = _pHead;
	while ( pLink != 0 )
	 {
	  pLink->Setid(count);
	  pLink = pLink->Next(); count++;
	 }
return count;
}



const Link * Get()
{
return  GetHead();
}


};



////////////// not intrusive list class1 ////////////////////////////////////
////////////// not intrusive list class1 ////////////////////////////////////
////////////// not intrusive list class1 ////////////////////////////////////

template<class T>
class TList : public List
{

public:


void Add (const T& a, int ren = 0)
{
	// add in front of the list
	Link* pLink = new TLink<T> ( _pHead, a );
	if(pLink != 0)
	{ _pHead = pLink; }

if (ren == 0) { RenumLink(); }
}



int Remove (int n)
{
//cout<<endl<<"---remove() element ---"<<n;

//-----------------------
  if(n == 1)  //cut head of
    {
    Link* delLink =  _pHead;
    if(delLink==0){cout<<endl<<"empty list"; return 0;}
    _pHead=_pHead->Next();
    delete (TLink<T>*)delLink;
    RenumLink();
    return 1;
    }
//-----------------------

	Link* pLink =  _pHead;
	Link* preLink =  _pHead;
	for(int i=1;i<n;i++)
	{
	//cout<<endl<<i;
	preLink = pLink;
	pLink = pLink->Next();

	if(pLink == 0)
	{cout<<endl<<"overflow"; return 0;}

	}

TLink<T>* TpLink=(TLink<T>*)pLink;
TLink<T>* TpreLink=(TLink<T>*)preLink;
//cout<<endl<<" link to remove "<<(*TpLink);
//cout<<endl<<"pre link to remove "<<(*TpreLink);


      preLink -> SetNext(pLink->Next());
      pLink ->   SetNext(0);  // unlink pLink
      delete (TLink<T>*)pLink;
      RenumLink();
//-----------------------

}

// REWRITE IT without checking inequality !=
int Remove ( TLink<T> * pTLink)
{
/*
int count=1;

Link* pLink =  _pHead;

    while( ( *((TLink<T>*)pLink)->Data() != *p ) && (pLink != 0) )
         {
         pLink = pLink->Next();
         count++;
         }

if(pLink != 0){ Remove(count); }
*/

Remove(pTLink->id());


}






//******************************************


AddIfDiff (const T& t);

T * Get()   { return (T*)List::Get();}

TLink<T> * Get(int n);

TList() : List() {}


TList <T>::TList(const TList<T>& tlist);


~TList ()
{
	//cout<<endl<<" ~TList() activated";
	// free the list
	while ( _pHead != 0 )
	{
		Link* pLink = _pHead;
		_pHead = _pHead->Next(); // unlink pLink

		//cout<<endl<<" deleting ";
		delete ( (TLink<T>*)pLink);
	}
}

friend ostream& operator << ( ostream& stm, const TList& list );


friend
TList_Transfer(TList<T>& listDest, TList<T>& listSrc, int kind);


};


//******************************************
//------------------ stream operators -----------------


template <class T>
ostream& operator << ( ostream& stm, const TLink<T>& tlink )
{
stm<<endl<<"_id = "<<tlink.id();
//stm<<"data = "<<tlink.data;
stm<<tlink.data;
return stm;
}



template <class T>
ostream& operator << ( ostream& stm, const TList<T>& list )
{
//stm<<endl<<"------------ list ----------------";
const Link* pLink = list.GetHead(); //_pHead;
while ( pLink != 0 )
 {
 TLink<T>* tpLink = (TLink<T>*)pLink;
 stm<<endl<<(*tpLink);
 pLink = pLink->Next();
 }
//stm<<endl<<"------------ *** ----------------";
return stm;
}



////////////////iterators  //////////////////////////


class List_iterator
{
const Link * curLink;
List * curList;
public:

	List_iterator(List& list)
	{
	curList = &list;
	curLink = list.GetHead();
	}


	const Link * operator++();


	Reset(){curLink = curList->GetHead();}


//~List_iterator()
//{
//cout<<endl<<" ~List_iterator() activated";
//}


};


const Link * List_iterator::operator++()
	{
	if(curLink==0){ return 0; }
	const Link * retLink = curLink;
	curLink = curLink->Next();
	return retLink;
	}





template<class T>
class TList_iterator  : public List_iterator
{
public:
TList_iterator(TList<T>& list) : List_iterator(list){}


//~TList_iterator()
//{
//cout<<endl<<" ~TList_iterator() activated";
//}


TLink<T> * operator++();

};



template<class T>
TLink<T> * TList_iterator<T>::operator++()
 {
  return (TLink<T>*)List_iterator::operator++();
 }


////////////////////////////////////////////////////
////////////////////////////////////////////////////
////////////////////////////////////////////////////
/////////////////////////////////////////////////////
//Transaction only diffrent kind
//------------------------------

#define  TR_DIFFRENTADD 	0
#define  TR_ALLADD 		1
#define  TR_MOVE		2

template <class T>
TList_Transfer(TList<T>& listDest, TList<T>& listSrc, int kind)
{

	switch(kind)
	{
	case  TR_DIFFRENTADD:
		{
		TList_iterator<T> SrcTiter(listSrc);
		const TLink<T> * srcTLink;
		while( srcTLink=SrcTiter++ )
		{
		listDest.AddIfDiff( *(srcTLink->Data()) );
		}
		}
	break;

	case  TR_ALLADD:
		{
		TList_iterator<T> SrcTiter(listSrc);
		const TLink<T> * srcTLink;
		while( srcTLink=SrcTiter++ )
		{
		listDest.Add( *(srcTLink->Data()) );
		}
		}
	break;


	case  TR_MOVE:
		{
		listDest.TList<T>::~TList();
		listDest._pHead = listSrc._pHead;
		listSrc._pHead=0;
		}
	break;



	}
}



////////////////////////////////////////////////////

// add only diffrent element in front of the list
template <class T>

int TList<T>::AddIfDiff (const T& t)
{

	Link* pLink = _pHead;

	while ( pLink != 0 )
	 {

	 TLink<T>* pTLink = (TLink<T>*)pLink;

	 //T tt( *(pTLink->Data()) );
	 //T tt( pTLink->CpyData() );

	 //if( !(tt != t)  ) { return 0; }

	  pLink = pLink->Next();
	 }

Add (t);
return 1;
}

///////////////////////////////////////////////////

template <class T>

TList <T>::TList(const TList<T>& tlist)
//TList <T>::TList(TList<T>& tlist)
{

//cout<<endl<<"********copy constructor of TList******";

TList<T> tmpList;
//tmpList._pHead=0;
Link* tmpLink = tlist._pHead;

	while ( tmpLink != 0 )
	{
	TLink<T>* tmpTLink = (TLink<T>*)tmpLink;
	tmpList.Add( *(tmpTLink->Data()), 1 );
	//Add( *(tmpTLink->Data()), 1 );
	//pLink->Setid(pLink->id());
	tmpLink=tmpLink->Next();
	}


//cout<<endl<<"**************";
//cout<<endl<<"tmpList"<<tmpList;
//cout<<endl<<"**************";



_pHead=0;

//Link* pLink = tlist._pHead;
Link* pLink = tmpList._pHead;
	while ( pLink != 0 )
	{

	TLink<T>* pTLink = (TLink<T>*)pLink;
	Add( *(pTLink->Data()), 1 );
	//Add( *(pTLink->Data()), 1 );
	//pLink->Setid(pLink->id());

	pLink=pLink->Next();


	}


      RenumLink();
}


template <class T>
TLink<T>* TList <T>::Get(int n)
{

	if(n < 1)
	  {cout<<endl<<"underflow"; return 0;}

	Link* pLink =  _pHead;
	for(int i=1;i<n;i++)
	  {
	  pLink = pLink->Next();
	  if(pLink == 0)
	    {cout<<endl<<"overflow"; return 0;}
	  }

TLink<T>* tpLink = (TLink<T>*)pLink;
return tpLink;

}


char pizda='p';