array

赫赫大名的 OGRE 游戏引擎

// ---------------------------------------------------------------------------------------------------------------------------------
//   __ _ _ __ _ __  __ _ _   _
//  / _` | '__| '__|/ _` | | | |
// | (_| | |  | |  | (_| | |_| |
//  \__,_|_|  |_|   \__,_|\__, |
//                         __/ |
//                        |___/
//
// Description:
//
//   Dynamic array
//
// 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_ARRAY
#define _FSTL_ARRAY

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

#include "common"
#include "util"

FSTL_NAMESPACE_BEGIN

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

template<class T, unsigned int G = 2>
class	array
{
public:
	// Construction/Destruction

inline				array()
				:_buf(static_cast<T *>(0)), _size(0), _reserved(0)
				{
				}

inline				array(const array &ar)
				:_buf(static_cast<T *>(0)), _size(0), _reserved(0)
				{
					(*this) = ar;
				}

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

	// Operators

				// The infamous operator=()
				
inline		array &		operator =(const array& rhs)
				{
					if (this == &rhs) return *this;

					// Wipe myself out

					erase();
					compact();
					
					// Allocate a whole new list large enough for 'rhs' plus the granularity
					
					_size = rhs.size();
					_reserved = size() + granularity();
					_buf = allocate<T>(reserved());

					// Copy everything over, using the copy ctor

					copyElements(_buf, rhs._buf, size());

					return *this;
				}

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

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

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

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

				// Invert the order of all elements in the array
				
inline		void		invert()
				{
					invertElements(_buf, size());
				}

				// Subset of the array
				
inline		array		operator ()(const unsigned int start, const unsigned int count) const
				{
					array	result;

					// Clamp the count and put it into the new array's size

					result._size = clampCount(start, count);
                                        if (!result._size) return result;
					
					// Allocate the resulting list
					
					result._reserved = result.size() + granularity();
					result._buf = allocate<T>(result.reserved());
					
					// Copy everything over, using the copy ctor
					
					copyElements(result._buf, _buf + start, count);
					
					return result;
				}

				// Index into the array
				
		T &		operator [](const int index)
				{
					return _buf[index];
				}

	const	T &		operator [](const int index) const
				{
					return _buf[index];
				}

				// Compare if two arrays are equal
				
inline		bool		operator ==(const array& rhs) const
				{
					if (!_buf) return _buf == rhs._buf;
					if (size() != rhs.size()) return false;
					for (unsigned int i = 0; i < size(); ++i)
					{
						if (!(_buf[i] == rhs._buf[i])) return false;
					}
					return true;
				}

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

	// Implementation

				// Indexed lookup

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

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

				// Swap two elements

inline		void		swap(const unsigned int lhs, const unsigned int rhs)
				{
					fstl::swap(at(lhs), at(rhs));
				}

				// Sort the array -- 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 array [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;
							}
						}
					}
				}

				// Erase an element or group of elements
				
inline		void		erase(const unsigned int start = 0, unsigned int count = 0xffffffff)
				{
					// Clamp the count to within range

					count = clampCount(start, count);
					if (!count) return;
					
					// 'Shift' the array down
					
					moveElements(&_buf[start], &_buf[start+count], size() - (start + count));

					// Destruct the dangling elements

					destructElements(&_buf[size()-count], count);
					
					// Adjust our size
					
					_size -= count;
				}

				// Insert an element
				
inline		void		insert(const T& el, 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 element?
					
					if (reserved() >= size() + 1)
					{
						// This is actually a little trickier than it seems, so read this:
						//
						// Given an array [a, c, d, e, f, g] if we want to insert 'b' so that the
						// resulting array is [a, b, c, d, e, f, g] then we need to move elements 'c' thru
						// 'g' forward to make room for 'b'. Sound simple? Nope.
						//
						// Remember that our array specifically does not construct any of the elements
						// that are not in use. And if an element is removed, we shift the array down
						// and destruct the one that's left dangling on the end. So it's safe to assume
						// that if an array element is unused, it is also not constructed.
						//
						// Given that, what happens when we shift elements 'c' through 'g' forward? Well,
						// this works except that when we move 'g' forward by one, it ends up occupying
						// a non-constructed piece of memory (past the end of the initial array). So in that
						// case, we need to copy-construct 'g' into its new home. However, moving elements
						// 'c' through 'f' forward can be done with the operator=(), because those elements
						// actually exist and have been constructed.
						//
						// That's not all.. just to make things more confusing, if the new element is
						// being inserted past the end, none of this matters, we simply copy-construct
						// the new element into the array, just past the end (into the buffer zone).
						//
						// However, if the new element is being inserted into the array somplace in
						// the middle, we'll have to use the operator=() on it, because it has already
						// been constructed.
						//
						// Hopefully that's not too confusing, because you've reached the end of my
						// explanation. :)

						// Inserting at the end?