core/sourcehook/sh_vector.h
author David Anderson <dvander@alliedmods.net>
Fri Nov 14 04:04:02 2008 -0600 (2008-11-14)
changeset 539 db914129ae01
parent 523 sourcehook/sh_vector.h@6f1630519b81
child 747 9563de0165f7
permissions -rwxr-xr-x
Some reorganization.
     1 /* ======== SourceMM ========
     2 * Copyright (C) 2004-2008 Metamod:Source Development Team
     3 * No warranties of any kind
     4 *
     5 * License: zlib/libpng
     6 *
     7 * Author(s): Pavol "PM OnoTo" Marko
     8 * ============================
     9 */
    10 
    11 #ifndef __CVECTOR_H__
    12 #define __CVECTOR_H__
    13 
    14 #include <assert.h>
    15 
    16 //This file originally from AMX Mod X
    17 namespace SourceHook
    18 {
    19 // Vector
    20 template <class T> class CVector
    21 {
    22 	bool Grow(size_t amount)
    23 	{
    24 		// automatic grow
    25 		size_t newSize = m_Size * 2;
    26 
    27 		if (newSize == 0)
    28 		{
    29 			newSize = 8;
    30 		}
    31 
    32 		while (m_CurrentUsedSize + amount > newSize)
    33 		{
    34 			newSize *= 2;
    35 		}
    36 
    37 		T *newData = new T[newSize];
    38 
    39 		if (m_Data)
    40 		{
    41 			for (size_t i=0; i<m_CurrentUsedSize; i++)
    42 			{
    43 				newData[i] = m_Data[i];
    44 			}
    45 
    46 			delete [] m_Data;
    47 		}
    48 
    49 		m_Data = newData;
    50 		m_Size = newSize;
    51 
    52 		return true;
    53 	}
    54 
    55 	bool GrowIfNeeded(size_t amount)
    56 	{
    57 		if (m_CurrentUsedSize + amount >= m_Size)
    58 		{
    59 			return Grow(amount);
    60 		}
    61 		else
    62 		{
    63 			return true;
    64 		}
    65 	}
    66 
    67 	bool ChangeSize(size_t size)
    68 	{
    69 		// change size
    70 		if (size == m_Size)
    71 		{
    72 			return true;
    73 		}
    74 
    75 		if (!size)
    76 		{
    77 			if (m_Data)
    78 			{
    79 				delete [] m_Data;
    80 				m_Data = NULL;
    81 				m_Size = 0;
    82 			}
    83 			return true;
    84 		}
    85 
    86 		T *newData = new T[size];
    87 
    88 		if (m_Data)
    89 		{
    90 			size_t end = (m_CurrentUsedSize < size) ? (m_CurrentUsedSize) : size;
    91 			for (size_t i=0; i<end; i++)
    92 			{
    93 				newData[i] = m_Data[i];
    94 			}
    95 
    96 			delete [] m_Data;
    97 		}
    98 		m_Data = newData;
    99 		m_Size = size;
   100 
   101 		if (m_CurrentUsedSize > m_Size)
   102 		{
   103 			m_CurrentUsedSize = m_Size;
   104 		}
   105 
   106 		return true;
   107 	}
   108 
   109 	void FreeMemIfPossible()
   110 	{
   111 		if (!m_Data)
   112 		{
   113 			return;
   114 		}
   115 
   116 		if (!m_CurrentUsedSize)
   117 		{
   118 			ChangeSize(0);
   119 			return;
   120 		}
   121 
   122 		size_t newSize = m_Size;
   123 		while (m_CurrentUsedSize <= newSize / 2)
   124 		{
   125 			newSize /= 2;
   126 		}
   127 
   128 		if (newSize != m_Size)
   129 		{
   130 			ChangeSize(newSize);
   131 		}
   132 	}
   133 protected:
   134 	T *m_Data;
   135 	size_t m_Size;
   136 	size_t m_CurrentUsedSize;
   137 public:
   138 	class iterator
   139 	{
   140 	protected:
   141 		T *m_Ptr;
   142 	public:
   143 		// constructors / destructors
   144 		iterator()
   145 		{
   146 			m_Ptr = NULL;
   147 		}
   148 
   149 		iterator(T * ptr)
   150 		{
   151 			m_Ptr = ptr;
   152 		}
   153 
   154 		// member functions
   155 		T * base()
   156 		{
   157 			return m_Ptr;
   158 		}
   159 
   160 		const T * base() const
   161 		{
   162 			return m_Ptr;
   163 		}
   164 
   165 		// operators
   166 		T & operator*()
   167 		{
   168 			return *m_Ptr;
   169 		}
   170 
   171 		T * operator->()
   172 		{
   173 			return m_Ptr;
   174 		}
   175 
   176 		iterator & operator++()		// preincrement
   177 		{
   178 			++m_Ptr;
   179 			return (*this);
   180 		}
   181 
   182 		iterator operator++(int)	// postincrement
   183 		{
   184 			iterator tmp = *this;
   185 			++m_Ptr;
   186 			return tmp;
   187 		}
   188 
   189 		iterator & operator--()		// predecrement
   190 		{
   191 			--m_Ptr;
   192 			return (*this);
   193 		}
   194 
   195 		iterator operator--(int)	// postdecrememnt
   196 		{
   197 			iterator tmp = *this;
   198 			--m_Ptr;
   199 			return tmp;
   200 		}
   201 
   202 		bool operator==(T * right) const
   203 		{
   204 			return (m_Ptr == right);
   205 		}
   206 
   207 		bool operator==(const iterator & right) const
   208 		{
   209 			return (m_Ptr == right.m_Ptr);
   210 		}
   211 
   212 		bool operator!=(T * right) const
   213 		{
   214 			return (m_Ptr != right);
   215 		}
   216 
   217 		bool operator!=(const iterator & right) const
   218 		{
   219 			return (m_Ptr != right.m_Ptr);
   220 		}
   221 
   222 		iterator & operator+=(size_t offset)
   223 		{
   224 			m_Ptr += offset;
   225 			return (*this);
   226 		}
   227 
   228 		iterator & operator-=(size_t offset)
   229 		{
   230 			m_Ptr -= offset;
   231 			return (*this);
   232 		}
   233 
   234 		iterator operator+(size_t offset) const
   235 		{
   236 			iterator tmp(*this);
   237 			tmp.m_Ptr += offset;
   238 			return tmp;
   239 		}
   240 
   241 		iterator operator-(size_t offset) const
   242 		{
   243 			iterator tmp(*this);
   244 			tmp.m_Ptr -= offset;
   245 			return tmp;
   246 		}
   247 
   248 		T & operator[](size_t offset)
   249 		{
   250 			return (*(*this + offset));
   251 		}
   252 
   253 		const T & operator[](size_t offset) const
   254 		{
   255 			return (*(*this + offset));
   256 		}
   257 
   258 		bool operator<(const iterator & right) const
   259 		{
   260 			return m_Ptr < right.m_Ptr;
   261 		}
   262 
   263 		bool operator>(const iterator & right) const
   264 		{
   265 			return m_Ptr > right.m_Ptr;
   266 		}
   267 
   268 		bool operator<=(const iterator & right) const
   269 		{
   270 			return m_Ptr <= right.m_Ptr;
   271 		}
   272 
   273 		bool operator>=(const iterator & right) const
   274 		{
   275 			return m_Ptr >= right.m_Ptr;
   276 		}
   277 
   278 		size_t operator-(const iterator & right) const
   279 		{
   280 			return m_Ptr - right.m_Ptr;
   281 		}
   282 	};
   283 
   284 	// constructors / destructors
   285 	CVector<T>()
   286 	{
   287 		m_Size = 0;
   288 		m_CurrentUsedSize = 0;
   289 		m_Data = NULL;
   290 	}
   291 
   292 	CVector<T>(const CVector<T> & other)
   293 	{
   294 		// copy data
   295 		m_Data = new T [other.m_CurrentUsedSize];
   296 		m_Size = other.m_CurrentUsedSize;
   297 		m_CurrentUsedSize = other.m_CurrentUsedSize;
   298 		for (size_t i=0; i<other.m_CurrentUsedSize; i++)
   299 			m_Data[i] = other.m_Data[i];
   300 	}
   301 
   302 	~CVector<T>()
   303 	{
   304 		clear();
   305 	}
   306 
   307 	CVector & operator =(const CVector<T> & other)
   308 	{
   309 		clear();
   310 		ChangeSize(other.size());
   311 		m_CurrentUsedSize = other.size();
   312 		for (size_t i=0; i<other.size(); i++)
   313 			m_Data[i] = other.at(i);
   314 		return *this;
   315 	}
   316 
   317 	// interface
   318 	size_t size() const
   319 	{
   320 		return m_CurrentUsedSize;
   321 	}
   322 
   323 	size_t capacity() const
   324 	{
   325 		return m_Size;
   326 	}
   327 
   328 	iterator begin() const
   329 	{
   330 		return iterator(m_Data);
   331 	}
   332 
   333 	iterator end() const
   334 	{
   335 		return iterator(m_Data + m_CurrentUsedSize);
   336 	}
   337 
   338 	iterator iterAt(size_t pos)
   339 	{
   340 		if (pos > m_CurrentUsedSize)
   341 			assert(0);
   342 		return iterator(m_Data + pos);
   343 	}
   344 
   345 	bool reserve(size_t newSize)
   346 	{
   347 		if (newSize > m_Size)
   348 			return ChangeSize(newSize);
   349 		return true;
   350 	}
   351 
   352 	bool push_back(const T & elem)
   353 	{
   354 		if (!GrowIfNeeded(1))
   355 		{
   356 			return false;
   357 		}
   358 
   359 		m_Data[m_CurrentUsedSize++] = elem;
   360 
   361 		return true;
   362 	}
   363 
   364 	void pop_back()
   365 	{
   366 		--m_CurrentUsedSize;
   367 		if (m_CurrentUsedSize < 0)
   368 			m_CurrentUsedSize = 0;
   369 
   370 		FreeMemIfPossible();
   371 	}
   372 
   373 	bool resize(size_t newSize)
   374 	{
   375 		return resize(newSize, T());
   376 	}
   377 
   378 	bool resize(size_t newSize, T defval)
   379 	{
   380 		if (!ChangeSize(newSize))
   381 			return false;
   382 		for (size_t i = m_CurrentUsedSize; i < newSize; ++i)
   383 			m_Data[i] = defval;
   384 		m_CurrentUsedSize = newSize;
   385 		return true;
   386 	}
   387 
   388 	bool empty() const
   389 	{
   390 		return (m_CurrentUsedSize == 0);
   391 	}
   392 
   393 	T & at(size_t pos)
   394 	{
   395 		if (pos > m_CurrentUsedSize)
   396 		{
   397 			assert(0);
   398 		}
   399 		return m_Data[pos];
   400 	}
   401 
   402 	const  T & at(size_t pos) const
   403 	{
   404 		if (pos > m_CurrentUsedSize)
   405 		{
   406 			assert(0);
   407 		}
   408 		return m_Data[pos];
   409 	}
   410 
   411 	T & operator[](size_t pos)
   412 	{
   413 		return at(pos);
   414 	}
   415 
   416 	const T & operator[](size_t pos) const
   417 	{
   418 		return at(pos);
   419 	}
   420 
   421 	T & front()
   422 	{
   423 		if (m_CurrentUsedSize < 1)
   424 		{
   425 			assert(0);
   426 		}
   427 		return m_Data[0];
   428 	}
   429 
   430 	const T & front() const
   431 	{
   432 		if (m_CurrentUsedSize < 1)
   433 		{
   434 			assert(0);
   435 		}
   436 		return m_Data[0];
   437 	}
   438 
   439 	T & back()
   440 	{
   441 		if (m_CurrentUsedSize < 1)
   442 		{
   443 			assert(0);
   444 		}
   445 		return m_Data[m_CurrentUsedSize - 1];
   446 	}
   447 
   448 	const T & back() const
   449 	{
   450 		if (m_CurrentUsedSize < 1)
   451 		{
   452 			assert(0);
   453 		}
   454 		return m_Data[m_CurrentUsedSize - 1];
   455 	}
   456 
   457 	iterator insert(iterator where, const T & value)
   458 	{
   459 		// validate iter
   460 		if (where < m_Data || where > (m_Data + m_CurrentUsedSize))
   461 			return iterator(0);
   462 
   463 		size_t ofs = where - begin();
   464 
   465 		if (!GrowIfNeeded(1))
   466 		{
   467 			return false;
   468 		}
   469 
   470 		++m_CurrentUsedSize;
   471 
   472 		where = begin() + ofs;
   473 
   474 		// Move subsequent entries
   475 		for (T *ptr = m_Data + m_CurrentUsedSize - 2; ptr >= where.base(); --ptr)
   476 			*(ptr + 1) = *ptr;
   477 
   478 		*where.base() = value;
   479 
   480 		return where;
   481 	}
   482 
   483 	iterator erase(iterator where)
   484 	{
   485 		// validate iter
   486 		if (where < m_Data || where >= (m_Data + m_CurrentUsedSize))
   487 			return iterator(0);
   488 
   489 		size_t ofs = where - begin();
   490 
   491 		if (m_CurrentUsedSize > 1)
   492 		{
   493 			// move
   494 			T *theend = m_Data + m_CurrentUsedSize;
   495 			for (T *ptr = where.base() + 1; ptr < theend; ++ptr)
   496 				*(ptr - 1) = *ptr;
   497 		}
   498 
   499 		--m_CurrentUsedSize;
   500 
   501 		FreeMemIfPossible();
   502 
   503 		return begin() + ofs;
   504 	}
   505 
   506 	void clear()
   507 	{
   508 		m_Size = 0;
   509 		m_CurrentUsedSize = 0;
   510 		if (m_Data)
   511 		{
   512 			delete [] m_Data;
   513 			m_Data = NULL;
   514 		}
   515 	}
   516 };
   517 };	//namespace SourceHook
   518 
   519 #endif // __CVECTOR_H__