list

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

						}
					}
				}

				// Erase an element or group of elements

inline		void		erase(node* start = static_cast<node *>(0), unsigned int count = 0xffffffff)
				{
					// Clamp the start

					if (!start) start = _head;

					// Erase the elements

					while(start && count && size())
					{
						// Correct for removing the head/tail

						if (start == head()) _head = head()->next();
						if (start == tail()) _tail = tail()->prev();

						// Remove it from the list

						node *	next = start->next();
						start->remove();

						// Destruct this element

						destruct(start);

						// Add it to the free list

						if (freeList) start->_next = freeList;
						freeList = start;

						// Next!

						start = next;
						--count;
						--_size;
					}
				}

				// Insert an element

inline		node *		insert(const T& el, node* start = static_cast<node *>(0))
				{
					// Make room if we need to

					if (extraReserved() < 1) reserve(size() + granularity());

					// Pluck one from the free list

					node *	newNode = freeList;
					freeList = newNode->next();

					// Construct it in place (i.e. 'new placement')

					construct(newNode, el);

					// Append it to the end?

					if (!start)
					{
						if (_tail)
						{
							newNode->insertAfter(_tail);
							_tail = newNode;
						}
						else
						{
							_head = _tail = newNode;
						}
					}
					else
					{
						newNode->insertBefore(start);
						if (head() == start) _head = newNode;
					}

					++_size;
					return newNode;
				}

				// Insert a list

inline		node *		insert(const list& l, node* start = static_cast<node *>(0))
				{
					node *	ptr = l.head();
					node *	first = start;
					while(ptr)
					{
						first = insert(ptr->data(), first)->next();
						ptr = ptr->next();
					}
					return first;
				}

				// Find

inline		node *		find(const T& element, node* start = static_cast<node *>(0)) const
				{
					if (!start) start = head();
					while(start)
					{
						if (start->data() == element) return start;
						start = start->next();
					}
					return static_cast<node *>(0);
				}

				// Reverse find

inline		node *		rfind(const T& element, node* start = static_cast<node *>(0)) const
				{
					if (!start) start = tail();
					while(start)
					{
						if (start->data() == element) return start;
						start = start->prev();
					}
					return static_cast<node *>(0);
				}

				// Fill a region of the list with a fill element

inline		void		fill(const T& filler, node* start = static_cast<node *>(0), unsigned int count = 0xffffffff)
				{
					if (!start) start = head();
					while(start && count)
					{
						start->data() = filler;
						start = start->next();
						--count;
					}
				}

				// Populate a list with a bunch of default elements
				
inline		void		populate(const T& filler, unsigned int count)
				{
					reserve(size() + count);
					for (unsigned int i = 0; i < count; ++i)
					{
						*this += filler;
					}
				}

				// Removes unused (but reserved) elements at the end of the list, including any leftover granularity

inline		void		compact()
				{
					// Don't do this if we don't need to

					if (!reservoirList) return;

					// Create a new, temporary list

					list	temp;
					temp.reserve(size());

					// Insert all of my entries into the new list

					const node *	ptr = head();
					while(ptr)
					{
						temp.insert(ptr->data());
						ptr = ptr->next();
					}

					// Erase everthing from my own list

					cleanup();

					// Copy over the data from the temporary list

					_head = temp._head;
					_tail = temp._tail;
					_size = temp._size;
					_reserved = temp._reserved;
					freeList = temp.freeList;
					reservoirCount = temp.reservoirCount;
					reservoirList = temp.reservoirList;

					// Zero out 'temp' (this prevents its destructor from doing anything terrible to the
					// memory we just stole from it)

					temp.setzero();
				}

				// Grow the reserved memory until it reaches 'len' list elements

inline		void		reserve(const unsigned int len)
				{
					// NOP if they're asking to shrink the list

					if (len <= reserved()) return;

					// Allocate another reservoir for the extra they asked for

					addReservoir(len - reserved());
				}

	// Accessors

inline		node *		head() const {return _head;}
inline		node *		tail() const {return _tail;}
inline	const	unsigned int	size() const {return _size;}
inline	const	unsigned int	reserved() const {return _reserved;}
inline	const	unsigned int	extraReserved() const {return reserved() - size();}
inline	const	unsigned int	granularity() const {return G;}

private:
	// List management data members

		node *		_head;
		node *		_tail;
		unsigned int	_size;
		unsigned int	_reserved;

	// Node reservoir data members

		node *		freeList;
		unsigned int	reservoirCount;
		node * *	reservoirList;

	// Implementation (private)

inline		void		cleanup()
				{
					// Destruct all of the used nodes

					node *	ptr = _head;
					while(ptr)
					{
						node *	next = ptr->next();
						destruct(ptr);
						ptr = next;
					}

					// Deallocate all of the reservoirs

					for (unsigned int i = 0; i < reservoirCount; ++i)
					{
						deallocate(reservoirList[i]);
					}

					// Free the reservoir list

					deallocate(reservoirList);

					// Reset to a known state

					setzero();
				}

inline		void		setzero()
				{
					_head = static_cast<node *>(0);
					_tail = static_cast<node *>(0);
					_size = 0;
					_reserved = 0;
					freeList = static_cast<node *>(0);
					reservoirList = static_cast<node * *>(0);
					reservoirCount = 0;
				}

inline		void		addReservoir(unsigned int gran = 0)
				{
					// How many elements for the reservoir?

					if (!gran) gran = granularity();

					// Allocate a new reservoir

					node *	newReservoir = allocate<node >(gran);

					// Grow the size of the reservoir list

					node * *	newReservoirList = allocate<node *>(reservoirCount+1);

					// Move the list over

					moveElements(newReservoirList, reservoirList, reservoirCount);
					deallocate(reservoirList);

					// Append the new reservoir to the end of the reservoirList

					reservoirList = newReservoirList;
					reservoirList[reservoirCount] = newReservoir;

					// Link the new reservoir into a contiguous list for the free list
					// Note that the free list doesn't require a doubly-linked list, so we'll
					// only track the 'next' pointers, not the 'prev' pointers.

					for (unsigned int i = 0; i < gran - 1; ++i)
					{
						newReservoir[i]._next = &newReservoir[i+1];
					}

					// Add the new reservoir to the free list

					newReservoir[gran - 1]._next = freeList;
					freeList = newReservoir;

					// Increment our counts

					++reservoirCount;
					_reserved += gran;
				}
};

// ---------------------------------------------------------------------------------------------------------------------------------
// These are handy...
// ---------------------------------------------------------------------------------------------------------------------------------

typedef	list<bool>		boolList;
typedef	list<int>		intList;
typedef	list<unsigned int>	uintList;
typedef	list<char>		charList;
typedef	list<unsigned char>	ucharList;
typedef	list<short>		shortList;
typedef	list<unsigned short>	ushortList;
typedef	list<float>		floatList;
typedef	list<double>		doubleList;

FSTL_NAMESPACE_END
#endif // _FSTL_LIST
// ---------------------------------------------------------------------------------------------------------------------------------
// list - End of file
// ---------------------------------------------------------------------------------------------------------------------------------