array

赫赫大名的 OGRE 游戏引擎

						if (start == size())
						{
							// Construct the new element into "uncharted territory"
							
							construct(&_buf[start], el);
						}

						// Need to shift stuff around						

						else
						{
							// Copy/construct the last element to be moved
							
							construct(&_buf[size()], _buf[size()-1]);
							
							// Move everything else forward by one
							
							moveElements(&_buf[start+1], &_buf[start], size() - start - 1);
							
							// Move the new element into place
							
							_buf[start] = el;
						}
						
						// Use the copy constructor to put this entry into the list
						
						++_size;
						return;
					}
					
					// We need to grow the array
					
					unsigned int	newSize = size() + 1;
					unsigned int	newReserved = newSize + granularity();
					T*	newBuf = allocate<T>(newReserved);
					copyElements(newBuf, _buf, start);
					construct(&newBuf[start], el);
					copyElements(newBuf+start+1, _buf+start, size() - start);
					
					// Out with the old...
					
					erase();
					compact();
					
					// ...in with the new
					
					_buf = newBuf;
					_size = newSize;
					_reserved = newReserved;
				}

				// Insert an array
				
inline		void		insert(const array& ar, unsigned int start = 0xffffffff)
				{
					// Our start should point at the element where the new entry goes. Any existing element
					// (and all elements following that one) will get shifted out of the way
					
					if (start > size()) start = size();

					// Do we have enough room for the new array?
					
					if (reserved() >= size() + ar.size())
					{
						// Look at the insert() routine (above) for insight as to what might be going
						// on here... then consider that we're inserting a list and also need to deal
						// with the inserted array inserting past the end of the initial array... which
						// confuses things even more... ASCII diagrams below should help...

						// Inserting at the end?
						
						if (start == size())
						{
							// Construct the new element into "uncharted territory"
						
							copyElements(_buf+start, ar._buf, ar.size());	
						}

						// Need to shift stuff around						

						else
						{
							// Case 1:
							//
							//     ABCDEF
							//     V
							//    abcdefghijklm
							//    |___________|...
							//
							// results in:
							//
							//    aABCDEFbcdefghijklm
							//    |___________|...
							//
							// Three steps to do it. They are:
							//
							//    abcdefg      hijklm
							//    |___________|...
							//
							//    a      bcdefghijklm
							//    |___________|...
							//
							//    aABCDEFbcdefghijklm
							//    |___________|...
							
							if (start+ar.size() < size())
							{
								copyElements(_buf+size(), _buf+size()-ar.size(), ar.size());
								moveElements(_buf+start+ar.size(), _buf+start, ar.size());
								moveElements(_buf+start, ar._buf, ar.size());
							}

							// Case 2:
							//
							//             ABCDEF
							//             V
							//    abcdefghijklm
							//    |___________|...
							//
							// results in:
							//
							//    abcdefghiABCDEFjklm
							//    |___________|...
							//
							// Three steps to do it. They are:
							//
							//    abcdefghi      jklm
							//    |___________|...
							//
							//    abcdefghi    EFjklm
							//    |___________|...
							//
							//    abcdefghiABCDEFjklm
							//    |___________|...
							
							else
							{
								unsigned int	 half1 = size() - start;
								unsigned int	 half2 = ar.size() - half1;
								copyElements(_buf+start+ar.size(), _buf+start, half1);
								copyElements(_buf+size(), ar._buf+half1, half2);
								moveElements(_buf+start, ar._buf, half1);
							}
						}
						
						_size += ar.size();
						return;
					}
					
					// We need to grow the array
					
					unsigned int	newSize = size() + ar.size();
					unsigned int	newReserved = newSize + granularity();
					T*	newBuf = allocate<T>(newReserved);
					copyElements(newBuf, _buf, start);
					copyElements(newBuf+start, ar._buf, ar.size());
					copyElements(newBuf+start+ar.size(), _buf+start, size() - start);
					
					// Out with the old...
					
					erase();
					compact();
					
					// ...in with the new
					
					_buf = newBuf;
					_size = newSize;
					_reserved = newReserved;
				}

				// Find
				
inline		int		find(const T& element, const unsigned int start = 0) const
				{
					for (unsigned int i = start; i < size(); ++i)
					{
						if (_buf[i] == element) return i;
					}

					return -1;
				}

				// Reverse find
				
inline		int		rfind(const T& element, unsigned int start = 0xffffffff) const
				{
					if (start >= size()) start = size() - 1;

					for (unsigned int i = start; i >= 0; --i)
					{
						if (_buf[i] == element) return i;
					}

					return -1;
				}

				// Fill a region of the array with a fill element
				
inline		void		fill(const T& filler, unsigned int start = 0, unsigned int count = 0xffffffff)
				{
					if (start >= size()) return;
					fillElements(&_buf[start], filler, clampCount(start, count));
				}

				// Populate an array 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;
					}
				}

	// Accessors

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

inline		void		compact()
				{
					// Is the array empty?
					
					if (!size())
					{
						deallocate(_buf);
						_buf = static_cast<T*>(0);
						_reserved = 0;
						return;
					}
					
					// Our array has some stuff in it, so reallocate a new array just big enough for size() elements

					T*	newBuf = allocate<T>(size());
					
					// Copy everything over, using the copy ctor

					copyElements(newBuf, _buf, size());
					
					// Destruct the elements in our current array
					
					destructElements(_buf, size());
					deallocate(_buf);
					
					// New buffer
					
					_buf = newBuf;
					_reserved = size();
				}

				// Reallocs the array, adding 'len' entries to the array's allocation pool
				
inline		void		reserve(const unsigned int len)
				{
					// NOP if they're asking to shrink the array
					
					if (len <= reserved()) return;
					
					// Allocate a new array
					
					T*	newBuf = allocate<T>(len);
					
					// Copy everything over, using the copy ctor
					
					copyElements(newBuf, _buf, size());
					
					// Destruct the elements in our current array
					
					destructElements(_buf, size());
					deallocate(_buf);
					_buf = newBuf;
					_reserved = len;
				}

	// Accessors

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:

inline		unsigned int	clampCount(const int unsigned start, unsigned int count) const
				{
					// If we're starting past the end, count should be 0
					
					if (start >= size()) return 0;
					
					// If count extends past end, clamp it
					
					if (start + count > size()) count = size() - start;
					
					// Return count
					
					return count;
				}

	// Data members

		T *		_buf;
		unsigned int	_size;
		unsigned int	_reserved;
};

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

typedef	array<bool>		boolArray;
typedef	array<int>		intArray;
typedef	array<unsigned int>	uintArray;
typedef	array<char>		charArray;
typedef	array<unsigned char>	ucharArray;
typedef	array<short>		shortArray;
typedef	array<unsigned short>	ushortArray;
typedef	array<float>		floatArray;
typedef	array<double>		doubleArray;

FSTL_NAMESPACE_END
#endif // _FSTL_ARRAY
// ---------------------------------------------------------------------------------------------------------------------------------
// array - End of file
// ---------------------------------------------------------------------------------------------------------------------------------