list

使用stl技术,(还没看,是听说的)

// ---------------------------------------------------------------------------------------------------------------------------------
//  _ _     _
// | (_)   | |
// | |_ ___| |_
// | | / __| __|
// | | \__ \ |_
// |_|_|___/\__|
//
// Description:
//
//   Doubly-linked list
//
// Notes:
//
//   Best viewed with 8-character tabs and (at least) 132 columns
//
// History:
//
//   04/13/2001 by Paul Nettle: Original creation
//
// Restrictions & freedoms pertaining to usage and redistribution of this software:
//
//   This software is 100% free. If you use this software (in part or in whole) you must credit the author. This software may not be
//   re-distributed (in part or in whole) in a modified form without clear documentation on how to obtain a copy of the original
//   work. You may not use this software to directly or indirectly cause harm to others. This software is provided as-is and without
//   warrantee -- Use at your own risk. For more information, visit HTTP://www.FluidStudios.com/
//
// Copyright 2001, Fluid Studios, Inc., all rights reserved.
// ---------------------------------------------------------------------------------------------------------------------------------

#ifndef	_FSTL_LIST
#define _FSTL_LIST

// ---------------------------------------------------------------------------------------------------------------------------------
// Module setup (required includes, macros, etc.)
// ---------------------------------------------------------------------------------------------------------------------------------

#include "common"

FSTL_NAMESPACE_BEGIN

// ---------------------------------------------------------------------------------------------------------------------------------

template <class T, unsigned int G = 2>
class	list
{
public:
	class	node
	{
	friend	list<T,G>;
	public:
		// Construction/Destruction
	
	inline			node() : _next(static_cast<node *>(0)), _prev(static_cast<node *>(0)) {}
	inline			node(const T & data) : _next(static_cast<node *>(0)), _prev(static_cast<node *>(0)), _data(data) {}
	inline			~node() {}
	
		// Implementation
	
	inline		void	remove()
				{
					if (prev()) prev()->_next = next();
					if (next()) next()->_prev = prev();
				}
	
	inline		void	insertBefore(node * n)
				{
					_prev = n->prev();
					_next = n;
					n->_prev = this;
					if (prev()) prev()->_next = this;
				}
	
	inline		void	insertAfter(node * n)
				{
					_prev = n;
					_next = n->next();
					n->_next = this;
					if (next()) next()->_prev = this;
				}
	
		// Accessors
	
	inline		node *	next() const {return _next;}
	inline		node *	prev() const {return _prev;}
	inline	const	T &	data() const {return _data;}
	inline		T &	data()       {return _data;}
	
	private:
		// Data members
	
			node *	_next;
			node *	_prev;
			T	_data;
	
		// Explicitly disallowed calls (they appear here, because if we don't do this, the compiler will generate them for us)
	
				node(const node & rhs);
	inline		node &	operator =(const node & rhs);
	};

	// Construction/Destruction

inline				list()
				{
					setzero();
				}

inline				list(const list &rhs)
				{
					setzero();
					*this = rhs;
				}

inline				~list()
				{
					erase();
					compact();
				}

	// Operators

				// The infamous operator=()

inline		list &		operator =(const list &rhs)
				{
					if (this == &rhs) return *this;

					// Wipe myself out

					erase();
					compact();

					// Allocate enough room for the new list

					reserve(rhs.size());
					
					// Insert the list into myself

					insert(rhs);

					return *this;
				}

				// Concat two lists
				
inline		list		operator +(const list& rhs)
				{
					list	result = *this;
					return result += rhs;
				}

				// Append a list onto the end of the list
				
inline		list &		operator +=(const list& rhs)
				{
					insert(rhs);
					return *this;
				}

				// Add an element to the end
				
inline		list		operator +(const T& rhs)
				{
					list	result = *this;
					return result += rhs;
				}

				// Append an element onto the end of the list
				
inline		list &		operator +=(const T& rhs)
				{
					insert(rhs);
					return *this;
				}

				// Invert the order of all elements in the list
				
inline		void		invert()
				{
					node *	h = head();
					node *	t = tail();
					unsigned int	c = size();
					while(h && t && c > 1)
					{
						swap(h->data(), t->data());
						h = h->next();
						t = t->prev();
						c -= 2;
					}
				}

				// Subset of the list
				
inline		list		operator ()(const unsigned int start, unsigned int count) const
				{
					list		result;
					const node *	n = (*this)[start];
					while(n && count)
					{
						result += n->data();
						--count;
					}
					return result;
				}

				// Index into the list
				
inline		node *		operator [](unsigned int rhs)
				{
					node *	ptr = head();
					while(ptr && rhs)
					{
						ptr = ptr->next();
						--rhs;
					}

					return ptr;
				}

inline	const	node *		operator [](unsigned int rhs) const
				{
					node *	ptr = head();
					while(ptr && rhs)
					{
						ptr = ptr->next();
						--rhs;
					}

					return ptr;
				}

				// Compare if two lists are equal
				
inline		bool		operator ==(const list& rhs) const
				{
					if (size() != rhs.size()) return false;
					if (size())
					{
						const node *	src1 = rhs.head();
						const node *	src2 = head();
						while(src1 && src2)
						{
							if (src1->data() != src2->data()) return false;
							src1 = src1->next();
							src2 = src2->next();
						}
					}

					return true;
				}

				// Compare if two lists are not equal
				
inline		bool		operator !=(const list& rhs) const
				{
					return !(operator==(rhs));
				}

	// Implementation

				// Indexed lookup

inline		node *		at(unsigned int index)
				{
					return (*this)[index];
				}

				// Indexed lookup

inline	const	node *		at(unsigned int index) const
				{
					return (*this)[index];
				}

				// Swap two elements

inline		void		swap(node* lhs, node* rhs)
				{
					if (lhs.next()) lhs->_next->_prev = rhs;
					if (lhs.prev()) lhs->_prev->_next = rhs;
					if (rhs.next()) rhs->_next->_prev = lhs;
					if (rhs.prev()) rhs->_prev->_next = lhs;
					fstl::swap(lhs._next, rhs._next);
					fstl::swap(lhs._prev, rhs._prev);
				}

				// Sort the list -- This just a bubble sort, so use with discretion

inline		void		sort()
				{
					if (!size()) return;
					for (unsigned int i = 0; i < size() - 1; ++i)
					{
						for (unsigned int j = i+1; j < size(); ++j)
						{
							if (at(i) > at(j)) swap(i, j);
						}
					}
				}

				// Sort the list [reverse] -- This just a bubble sort, so use with discretion

inline		void		rsort()
				{
					if (!size()) return;
					for (unsigned int i = 0; i < size() - 1; ++i)
					{
						for (unsigned int j = i+1; j < size(); ++j)
						{
							if (at(i) < at(j)) swap(i, j);
						}
					}
				}

				// Remove neighboring duplicates

inline		void		unique()
				{
					if (!size()) return;
					for (unsigned int i = 0; i < size(); ++i)
					{
						for (unsigned int j = i+1; j < size(); ++j)
						{
							if (at(i) == at(j))
							{
								erase(j, 1);
								j--;
							}
							else
							{
								break;
							}