/*
template CSimpleList

	by: Shawn A. Van Ness
	rev: 2001.11.13

Using CSimpleList<T> requires T to have a meaningful default-ctor, copy-
ctor, and assignment-operator. The Sort method requires T::operator<, and the 
Find and RemoveDups methods require T::operator==.

///todo: nail down exact requirements (ie: verify the above statement)

Usage:

   ATLX::CSimpleList<CMyClass> list1;
   ATLX::CSimpleList<float> list2; 
*/

#pragma once 

namespace ATLX 
{

template<class T>
class CSimpleList
{
	struct node
	{
		T t;
		node* pPrev;
		node* pNext;

		node() { pPrev = pNext = 0; }
	};

	int m_nCount;
	node* m_pHead;
	node* m_pTail;

public:

	// Initializers

	CSimpleList()
	{ m_nCount = 0;
	m_pHead = m_pTail = 0; }

	CSimpleList(const CSimpleList<T>& src)
	{ m_nCount = 0;
	m_pHead = m_pTail = 0;
	(*this) = src; }

	CSimpleList& operator=(const CSimpleList<T>& src)
	{ RemoveAll();
	Append(src);
	return (*this); }

	~CSimpleList()
	{ RemoveAll(); }

	// Accessors

	int Count() const
	{ return m_nCount; }

	bool IsEmpty() const
	{ return (m_nCount==0); }

	struct iterator
	{
		node* ptr;

		iterator() 
		{ ptr = 0; }

		iterator(node* p) 
		{ ptr = p; }

		iterator(const iterator& x) 
		{ ptr = x.ptr; }

		T& operator*() 
		{ ATLASSERT(ptr); 
		return (ptr->t); }

		T* operator->() // hack to avoid T::operator& -- t must be first member in struct node
		{ ATLASSERT(ptr); 
		return reinterpret_cast<T*>(ptr); }

		iterator& operator++() 
		{ ATLASSERT(ptr); 
		ptr = ptr->pNext; 
		return (*this); }

		iterator& operator--() 
		{ ATLASSERT(ptr); 
		ptr = ptr->pPrev; 
		return (*this); }

		iterator operator++(int) 
		{ ATLASSERT(ptr); 
		iterator old = ptr; 
		ptr = ptr->pNext; 
		return old; }

		iterator operator--(int) 
		{ ATLASSERT(ptr); 
		iterator old = ptr; 
		ptr = ptr->pPrev; 
		return old; }

		bool operator==(const iterator& x) const 
		{ return (ptr==x.ptr) ? (true) : (false); }

		bool operator!=(const iterator& x) const 
		{ return (ptr==x.ptr) ? (false) : (true); }
	};

	iterator Head() const
	{ return iterator(m_pHead); }

	iterator Tail() const
	{ return iterator(m_pTail); }

	iterator Begin() const
	{ return iterator(m_pHead); }

	iterator End() const
	{ return iterator(0); }

	iterator Find(const T& t) const
	{
		for(iterator p = Begin(); p != End(); ++p)
			if (*p == t) // requires meaningful T::operator==
				return p;

		return 0;
	}

	// Operations

	void Add(const T& t)
	{
		InsertAt(End(),t);
	}

	void InsertAt(const iterator& p, const T& t)
	{
		// Insert "t" in front of "p" (between pX and pY)
		node* pX = (p.ptr) ? (p.ptr->pPrev) : (m_pTail);
		node* pY = p.ptr;

		m_nCount++;
		node* pNew = new node;
		ATLASSERT(pNew);

		pNew->t = t;
		pNew->pPrev = pX;
		pNew->pNext = pY;

		if (pX)
			pX->pNext = pNew;

		if (pY) 
			pY->pPrev = pNew;

		if (!m_pHead || !pX) 
			m_pHead = pNew;

		if (!m_pTail || !pY) 
			m_pTail = pNew;
	}

	void Append(const CSimpleList<T>& src)
	{
		for(iterator p = src.Begin(); p != src.End(); ++p)
			Add(*p);
	}

	void RemoveAt(const iterator& p)
	{
		node* pn = p.ptr;
		if (!pn) return;

		if (pn->pPrev) pn->pPrev->pNext = pn->pNext;
		else m_pHead = pn->pNext;

		if (pn->pNext) pn->pNext->pPrev = pn->pPrev;
		else m_pTail = pn->pPrev;

		delete pn;
		m_nCount--;
	}

	void RemoveAll()
	{ 
		while (!IsEmpty()) 
			RemoveAt(Tail()); 
	}

	///todo: test!
	void RemoveDuplicates()
	{
		// Remove duplicate entries (as determined by T::operator==)
		for(iterator p = Begin(); p != End(); ++p)
		{
			iterator p2 = p;
			while (++p2 != End())
			{
				if (*p2 == *p)
				{ RemoveAt(p2); p2 = p; }
			}
		}
	}

	void Swap(const iterator& p1, const iterator& p2)
	{
		node* pn1 = p1.ptr;
		node* pn2 = p2.ptr;
		if (!pn1 || !pn2) return;

		T* pt = (T*)_alloca(sizeof(T));

		::CopyMemory(pt,&pn1->t,sizeof(T));
		::CopyMemory(&pn1->t,&pn2->t,sizeof(T));
		::CopyMemory(&pn2->t,pt,sizeof(T));
	}

	void Sort()
	{
		// Non-destructive swap-sort (as deterined by T::operator<)
		bool bDone = false;
		while (!bDone)
		{
			bDone = true;
			for(iterator p = Begin(); p != End(); ++p)
			{
				iterator p2 = p; ++p2;
				if (p2 == End()) break;

				if (*p2 < *p) 
				{
					Swap(p,p2);
					bDone = false;
				}
			}
		}
	}

};

} // namespace




w e b c p p
web c plus plus