#inc
 
lude <iostream>
#include <sstream>
#include <cstdio>
#include <iterator>
#include <type_traits>



template < class T > class linearList{
public:
	virtual ~linearList( void ) {};
	virtual bool empty( void ) const = 0;
	virtual std::size_t size( void ) const = 0;
	virtual T& get( int theIndex ) const = 0;
	virtual int indexOf( const T& theElement ) const = 0;
	virtual void erase( int theIndex ) = 0;
	virtual void insert( int theIndex, const T& theElement ) = 0;
	virtual void output( std::ostream& os ) const = 0;
};

template < class T > class extendedLinearList
: public linearList< T >
{
public:
	virtual ~extendedLinearList( void ){ }
	virtual void clear( void ) = 0;
	virtual void push_back( const T& theElement ) = 0;
};


template < class T> struct chainNode{
	T element;
	chainNode< T > *next { nullptr };
	
	chainNode( void ) {}
	chainNode( const T& element )
		:element( element )
		{}
	chainNode( const T& element, const chainNode< T > *next )
		:chainNode( element )
		{ this->next = next;}
};

template < typename T > class chain;
template < typename T >
std::ostream& operator<<( std::ostream& os, const chain< T >& x){
	x.output( os );
	return os;
}


template < class T > class chain : public linearList< T >{
class iterator{
	public:
		typedef std::forward_iterator_tag iterator_category;
		typedef T value_type;
		typedef chainNode< value_type >* pointer;
		typedef chainNode< value_type >& reference;

		iterator( pointer theNode = nullptr) : node( theNode ) {}

		reference operator*( void ) const { return &node->element; }
		pointer operator->( void ) const { return node->element; }

		iterator& operator++( void ) {
			node = node->next;
			return *this;
		}
		iterator operator++( int dummy ){
			iterator tmp = *this;
			node = node->next;
			return tmp;
		}

		bool operator!=( const iterator rhs ) const{
			return node != rhs.node;
		}
		bool operator==( const iterator rhs ) const{
					return node == rhs.node;
		}
	protected:
		pointer node;
};
public:
	chain( const chain< T >& );
	~chain( void );
	
	virtual bool empty( void ) const { return listSize == 0; }
	virtual std::size_t size( void ) const { return listSize; }
	
	virtual T& get( int theIndex ) const;
	virtual int indexOf( const T& theElement ) const;
	virtual void erase( int theIndex );
	virtual void insert( int theIndex, const T& theElement );
	virtual void output( std::ostream& os ) const;
	
	iterator begin( void ){ return iterator( firstNode ); }
	iterator end( void ){ return iterator(); }
	
protected:
	void checkIndex( int theIndex ) const;
	chainNode< T > *firstNode { nullptr };
	std::size_t listSize { 0 };
};
template < class  T >
chain< T >::chain( const chain< T >& theList)
:listSize( theList.listSize )
{
	if( !listSize ) return;
	chainNode< T > *sourceNode = theList.firstNode;
	firstNode = new chainNode< T >( sourceNode->element );
	chainNode< T > *targetNode = firstNode;
	while( sourceNode ){
		targetNode->next = new chainNode< T >( sourceNode->element );
		targetNode = targetNode->next;
		sourceNode = sourceNode->next;
	}
}

template < class T >
void chain< T >::checkIndex( int theIndex ) const{
	if( theIndex < 0 || theIndex >= listSize ){
		std::ostringstream oss;
		char buf[ 64 ];
		sprintf( buf, "given index = %d; size = %d", theIndex, listSize );
		oss << buf;
		throw std::invalid_argument( oss.str() );
	}
	return;
}

template < class T >
T& chain< T >::get( int theIndex ) const{
	checkIndex( theIndex );
	chainNode< T > *currentNode = firstNode;
	for( register int i { 0 }; i < theIndex; ++i)
		currentNode = currentNode->next;
	return currentNode->element;
}

template < class T >
int chain< T >::indexOf( const T& theElement ) const{
	chainNode< T > *currentNode = firstNode;
	int index = 0;
	while( currentNode && !( currentNode->element == theElement ) ){
		currentNode = currentNode->next;
		++index;
	}
	return currentNode ? index : -1;
}

template < class T >
void chain< T >::erase( int theIndex ){
	checkIndex( theIndex );
	chainNode< T > *deleteNode;
	if( !theIndex ){
		deleteNode = firstNode;
		firstNode = firstNode->next;
	}else{
		chainNode< T > *p =firstNode;
		for( register int i { 0 }; i < theIndex; ++i )
			p = p->next;
		deleteNode = p->next;
		p->next = p->next->next;
	}
	listSize--;
	delete deleteNode;
}

template < class T >
void chain<T>::insert( int theIndex, const T& theElement ){
	checkIndex( theIndex );
	if( !theIndex ) firstNode = new chainNode< T >( theElement, firstNode );
	else{
		chainNode< T > *p = firstNode;
		for( register int i { 0 }; i < theIndex; ++i )
			p = p->next;
		p->next = new chainNode< T >( theElement, p->next );
	}
	listSize++;
}

template < class T >
void chain< T >::output( std::ostream& os ) const{
	for( chainNode< T > *currentNode = firstNode;
		 currentNode;
		 currentNode = currentNode->next)
			os << currentNode->element << '	';
}

int main( void ){

	return 0;
}