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