/*
вопрос № 178253
Написать программу, реализующую двухсвязный список, который хранит
элементы произвольного типа (Программа заранее не знает, данные какого
типа будут хранится в элементах списка). Реализовать полный набор
операций (создание списка, вставка эл-та, удаление эл-та).

Вариант с избыточным использованием шаблонов.
*/
#include <stdlib.h>
#include <stdio.h>

template <class T> struct t_DoubleListItem
{
	t_DoubleListItem<T>( T val ) { data = val; }

	t_DoubleListItem<T>* next;
	t_DoubleListItem<T>* prev;
	T	data;
};

template <class T> class t_DoubleList
{
public:
			t_DoubleList();
	virtual ~t_DoubleList();

	virtual void freeItem( t_DoubleListItem<T>* pItem );

			void clear();
			void add( t_DoubleListItem<T>* pItem );
			bool insertAfter( const t_DoubleListItem<T>* pAfter, t_DoubleListItem<T>* pItem );
			bool removeItem( t_DoubleListItem<T>* pItem );
			bool deleteItem( t_DoubleListItem<T>* pItem );
			void forEach( void (*func)( t_DoubleListItem<T>* ) );

protected:
	t_DoubleListItem<T>* m_pHead;	// указатель на первый добавленный элемент
	t_DoubleListItem<T>* m_pTail;	// указатель на последний добавленный элемент
};


// создание пустого списка
template <class T> 
inline t_DoubleList<T>::t_DoubleList() : m_pHead(0), m_pTail(0)
{
}

// уничтожение списка
template <class T>
t_DoubleList<T>::~t_DoubleList()
{
	clear();
}

//--------------------------------------------------------------
// Функция очищает список. Все элементы также уничтожаются.
//--------------------------------------------------------------
template <class T>
void t_DoubleList<T>::clear()
{
	t_DoubleListItem<T>* p = m_pHead;
	while( p ) {
		t_DoubleListItem<T>* pNext = p->next;
		freeItem( p );	// удаляем элемент
		p = pNext;			// переходим к следующему
	}
	m_pHead = 0; m_pTail = 0;
}

//--------------------------------------------------------------
// Виртуальная функция - удаление элемента в предположении, что
// память для него выделена посредством new. Если это не так, то
// функция должна быть перекрыта в производном классе.
//--------------------------------------------------------------
template <class T> 
void t_DoubleList<T>::freeItem( t_DoubleListItem<T>* pItem )
{
	delete pItem;
}

//--------------------------------------------------------------
// Функция вставляет новый элемент в конец списка
//--------------------------------------------------------------
template <class T> 
void t_DoubleList<T>::add( t_DoubleListItem<T>* pItem )
{
	pItem->prev = m_pTail;	// предыдущий элемент - прежний конец списка
	pItem->next = NULL;		// следующего элемента пока нет
	if( !m_pHead )			// если первый элемент в списке,
		m_pHead = pItem;	// ... то инициализируем указатель на начало
	else					// иначе добавляем в конец
		m_pTail->next = pItem;

	m_pTail = pItem;		// новый конец списка
}


//--------------------------------------------------------------
// Вставляем новый элемент после элемента pInsertAfter.
// Если pInsertAfter == NULL, то вставляем в начало списка.
// Функция возвращает true, если элемент вставлен в список,
// false - если элемент pInsertAfter не найден.
//--------------------------------------------------------------
template <class T>
bool t_DoubleList<T>::insertAfter( const t_DoubleListItem<T>* pInsertAfter, t_DoubleListItem<T>* pItem )
{
	t_DoubleListItem<T>* p = m_pHead;
	if( !pInsertAfter ) {		// вставляем в начало списка
		pItem->next = p;		// следующий элемент - прежнее начало списка
		pItem->prev = NULL;		// предыдущего элемента нет - это новое начало списка
		if( !p )				// если первый элемент в списке,
			m_pHead = pItem;	// ... то инициализируем указатель на начало
		else
			p->prev = pItem;

		m_pHead = pItem;		// новое начало списка
		return true;
	}
	while( p ) {
		// ищем элемент, после которого нужно вставлять
		if( p == pInsertAfter ) {
			t_DoubleListItem<T>* pNext = p->next;
			if( pNext )
				pNext->prev = pItem;
			else	// pInsertAfter == m_pTail, причем здесь m_pTail != 0
				m_pTail = pItem;		// новый конец списка

			pItem->prev = p;

			pItem->next = pNext;
			p->next = pItem;
			return true;
		}
		p = p->next;	// переходим к следующему
	}
	return false;
}

//--------------------------------------------------------------
// Удаляем элемент pItem из списка, сам элемент не меняется.
// Функция возвращает true, если элемент удален из списка,
// false - если элемент pItem не найден.
//--------------------------------------------------------------
template <class T>
bool t_DoubleList<T>::removeItem( t_DoubleListItem<T>* pItem )
{
	t_DoubleListItem<T>* p = m_pHead;
	while( p ) {
		// ищем удаляемый элемент
		if( p == pItem ) {
			if( p->prev )
				p->prev->next = p->next;
			else	// удаляется начало списка
				m_pHead = p->next;

			if( p->next )
				p->next->prev = p->prev;
			else	// удаляется конец списка
				m_pTail = p->prev;
			return true;
		}
		p = p->next;	// переходим к следующему
	}
	return false;
}

//--------------------------------------------------------------
// Удаляем элемент pItem из списка, затем уничтожаем сам элемент.
// Функция возвращает true, если элемент удален из списка,
// false - если элемент pItem не найден, в этом случае элемент
// не меняется.
//--------------------------------------------------------------
template <class T>
bool t_DoubleList<T>::deleteItem( t_DoubleListItem<T>* pItem )
{
	if( removeItem(pItem) ) {
		freeItem( pItem );
		return true;
	}
	return false;
}


//--------------------------------------------------------------
// Выполняет функцию func для каждого элемента списка
//--------------------------------------------------------------
template <class T>
void t_DoubleList<T>::forEach( void (*func)( t_DoubleListItem<T>* ) )
{
	if( !func ) return;

	t_DoubleListItem<T>* p = m_pHead;
	while( p ) {
		func( p );
		p = p->next;
	}
}

//==============================================================
// Проверка некоторых функций списка
//==============================================================


void printValue( t_DoubleListItem<int>* p )
{
	printf( "%4d\n", p->data );
}

void main()
{
	// при использовании класса указываем нужный нам тип
	t_DoubleList<int>* pListInt = new t_DoubleList<int>();

	t_DoubleListItem<int>* a[10];
	for( int i = 0; i < 10; ++i ) {
		t_DoubleListItem<int>* p = new t_DoubleListItem<int>( i );
		a[i] = p;
		pListInt->add( p );
	}
	pListInt->insertAfter( 0, new t_DoubleListItem<int>(-1));		// вставка в начало
	pListInt->insertAfter( a[5], new t_DoubleListItem<int>(-5));	// вставка в середину
	pListInt->insertAfter( a[9], new t_DoubleListItem<int>(50));	// добавление в конец
	pListInt->add( new t_DoubleListItem<int>(100) );				// добавление в конец
	pListInt->deleteItem( a[7] );		// удаление элемента
	pListInt->forEach( printValue );	// распечатываем список
	delete pListInt;
}

/*
вопрос № 178253
Написать программу, реализующую двухсвязный список, который хранит
элементы произвольного типа (Программа заранее не знает, данные какого
типа будут хранится в элементах списка). Реализовать полный набор
операций (создание списка, вставка эл-та, удаление эл-та).
Вариант с использованием шаблонов.
*/
#include <stdlib.h>
#include <stdio.h>

// Эта структура напрямую используется только в классе t_DoubleList
// Пользовательские типы данных следует объявлять с использованием шаблона
struct __t_DoubleListItem
{
	__t_DoubleListItem* next;
	__t_DoubleListItem* prev;
};

// шаблон для объявления пользовательских типов данных
template <class T> struct t_DoubleListItem : __t_DoubleListItem
{
	t_DoubleListItem<T>( T val ) { data = val; }
	T	data;
};

class t_DoubleList
{
public:
			t_DoubleList();
	virtual ~t_DoubleList();

	virtual void freeItem( __t_DoubleListItem* pItem );

			void clear();
			void add( __t_DoubleListItem* pItem );
			bool insertAfter( const __t_DoubleListItem* pAfter, __t_DoubleListItem* pItem );
			bool removeItem( __t_DoubleListItem* pItem );
			bool deleteItem( __t_DoubleListItem* pItem );
			void forEach( void (*func)( __t_DoubleListItem* ) );

protected:
	__t_DoubleListItem* m_pHead;	// указатель на первый добавленный элемент
	__t_DoubleListItem* m_pTail;	// указатель на последний добавленный элемент
};


// создание пустого списка
inline t_DoubleList::t_DoubleList() : m_pHead(0), m_pTail(0)
{
}

// уничтожение списка
t_DoubleList::~t_DoubleList()
{
	clear();
}

//--------------------------------------------------------------
// Функция очищает список. Все элементы также уничтожаются.
//--------------------------------------------------------------
void t_DoubleList::clear()
{
	__t_DoubleListItem* p = m_pHead;
	while( p ) {
		__t_DoubleListItem* pNext = p->next;
		freeItem( p );	// удаляем элемент
		p = pNext;			// переходим к следующему
	}
	m_pHead = 0; m_pTail = 0;
}

//--------------------------------------------------------------
// Виртуальная функция - удаление элемента в предположении, что
// память для него выделена посредством new. Если это не так, то
// функция должна быть перекрыта в производном классе.
//--------------------------------------------------------------
void t_DoubleList::freeItem( __t_DoubleListItem* pItem )
{
	delete pItem;
}

//--------------------------------------------------------------
// Функция вставляет новый элемент в конец списка
//--------------------------------------------------------------
void t_DoubleList::add( __t_DoubleListItem* pItem )
{
	pItem->prev = m_pTail;	// предыдущий элемент - прежний конец списка
	pItem->next = NULL;		// следующего элемента пока нет
	if( !m_pHead )			// если первый элемент в списке,
		m_pHead = pItem;	// ... то инициализируем указатель на начало
	else					// иначе добавляем в конец
		m_pTail->next = pItem;

	m_pTail = pItem;		// новый конец списка
}


//--------------------------------------------------------------
// Вставляем новый элемент после элемента pInsertAfter.
// Если pInsertAfter == NULL, то вставляем в начало списка.
// Функция возвращает true, если элемент вставлен в список,
// false - если элемент pInsertAfter не найден.
//--------------------------------------------------------------
bool t_DoubleList::insertAfter( const __t_DoubleListItem* pInsertAfter, __t_DoubleListItem* pItem )
{
	__t_DoubleListItem* p = m_pHead;
	if( !pInsertAfter ) {		// вставляем в начало списка
		pItem->next = p;		// следующий элемент - прежнее начало списка
		pItem->prev = NULL;		// предыдущего элемента нет - это новое начало списка
		if( !p )				// если первый элемент в списке,
			m_pHead = pItem;	// ... то инициализируем указатель на начало
		else
			p->prev = pItem;

		m_pHead = pItem;		// новое начало списка
		return true;
	}
	while( p ) {
		// ищем элемент, после которого нужно вставлять
		if( p == pInsertAfter ) {
			__t_DoubleListItem* pNext = p->next;
			if( pNext )
				pNext->prev = pItem;
			else	// pInsertAfter == m_pTail, причем здесь m_pTail != 0
				m_pTail = pItem;		// новый конец списка

			pItem->prev = p;

			pItem->next = pNext;
			p->next = pItem;
			return true;
		}
		p = p->next;	// переходим к следующему
	}
	return false;
}

//--------------------------------------------------------------
// Удаляем элемент pItem из списка, сам элемент не меняется.
// Функция возвращает true, если элемент удален из списка,
// false - если элемент pItem не найден.
//--------------------------------------------------------------
bool t_DoubleList::removeItem( __t_DoubleListItem* pItem )
{
	__t_DoubleListItem* p = m_pHead;
	while( p ) {
		// ищем удаляемый элемент
		if( p == pItem ) {
			if( p->prev )
				p->prev->next = p->next;
			else	// удаляется начало списка
				m_pHead = p->next;

			if( p->next )
				p->next->prev = p->prev;
			else	// удаляется конец списка
				m_pTail = p->prev;
			return true;
		}
		p = p->next;	// переходим к следующему
	}
	return false;
}

//--------------------------------------------------------------
// Удаляем элемент pItem из списка, затем уничтожаем сам элемент.
// Функция возвращает true, если элемент удален из списка,
// false - если элемент pItem не найден, в этом случае элемент
// не меняется.
//--------------------------------------------------------------
bool t_DoubleList::deleteItem( __t_DoubleListItem* pItem )
{
	if( removeItem(pItem) ) {
		freeItem( pItem );
		return true;
	}
	return false;
}


//--------------------------------------------------------------
// Выполняет функцию func для каждого элемента списка
//--------------------------------------------------------------
void t_DoubleList::forEach( void (*func)( __t_DoubleListItem* ) )
{
	if( !func ) return;

	__t_DoubleListItem* p = m_pHead;
	while( p ) {
		func( p );
		p = p->next;
	}
}

//==============================================================
// Проверка некоторых функций списка
//==============================================================

void printValue( __t_DoubleListItem* p )
{
	printf( "%4d\n", ((t_DoubleListItem<int>*)p)->data );
}

void main()
{
	t_DoubleList* pListInt = new t_DoubleList();

	// при использовании класса указываем нужный нам тип элементов
	t_DoubleListItem<int>* a[10];
	for( int i = 0; i < 10; ++i ) {
		t_DoubleListItem<int>* p = new t_DoubleListItem<int>( i );
		a[i] = p;
		pListInt->add( p );
	}
	pListInt->insertAfter( 0, new t_DoubleListItem<int>(-1));		// вставка в начало
	pListInt->insertAfter( a[5], new t_DoubleListItem<int>(-5));	// вставка в середину
	pListInt->insertAfter( a[9], new t_DoubleListItem<int>(50));	// добавление в конец
	pListInt->add( new t_DoubleListItem<int>(100) );				// добавление в конец
	pListInt->deleteItem( a[7] );		// удаление элемента
	pListInt->forEach( printValue );	// распечатываем список
	delete pListInt;
}