sourcehook/sh_vector.h
author Pavol Marko <pavolmarko@gmail.com>
Sat Sep 24 15:27:03 2005 +0000 (2005-09-24)
changeset 112 0260e74b4a5d
parent 99 bfbb04d6683f
child 154 083cb82d97df
permissions -rwxr-xr-x
Hello.
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@99
   277
	// interface
dvander@99
   278
	size_t size() const
dvander@99
   279
	{
dvander@99
   280
		return m_CurrentUsedSize;
dvander@99
   281
	}
dvander@99
   282
dvander@99
   283
	size_t capacity() const
dvander@99
   284
	{
dvander@99
   285
		return m_Size;
dvander@99
   286
	}
dvander@99
   287
dvander@99
   288
	iterator begin() const
dvander@99
   289
	{
dvander@99
   290
		return iterator(m_Data);
dvander@99
   291
	}
dvander@99
   292
dvander@99
   293
	iterator end() const
dvander@99
   294
	{
dvander@99
   295
		return iterator(m_Data + m_CurrentUsedSize);
dvander@99
   296
	}
dvander@99
   297
dvander@99
   298
	iterator iterAt(size_t pos)
dvander@99
   299
	{
dvander@99
   300
		if (pos > m_CurrentUsedSize)
dvander@99
   301
			assert(0);
dvander@99
   302
		return iterator(m_Data + pos);
dvander@99
   303
	}
dvander@99
   304
dvander@99
   305
	bool reserve(size_t newSize)
dvander@99
   306
	{
dvander@99
   307
		if (newSize > m_Size)
dvander@99
   308
			return ChangeSize(newSize);
dvander@99
   309
		return true;
dvander@99
   310
	}
dvander@99
   311
dvander@99
   312
	bool push_back(const T & elem)
dvander@99
   313
	{
dvander@99
   314
		++m_CurrentUsedSize;
dvander@99
   315
		if (!GrowIfNeeded())
dvander@99
   316
		{
dvander@99
   317
			--m_CurrentUsedSize;
dvander@99
   318
			return false;
dvander@99
   319
		}
dvander@99
   320
dvander@99
   321
		m_Data[m_CurrentUsedSize - 1] = elem;
dvander@99
   322
		return true;
dvander@99
   323
	}
dvander@99
   324
dvander@99
   325
	void pop_back()
dvander@99
   326
	{
dvander@99
   327
		--m_CurrentUsedSize;
dvander@99
   328
		if (m_CurrentUsedSize < 0)
dvander@99
   329
			m_CurrentUsedSize = 0;
dvander@99
   330
dvander@99
   331
		FreeMemIfPossible();
dvander@99
   332
	}
dvander@99
   333
dvander@99
   334
	bool resize(size_t newSize)
dvander@99
   335
	{
dvander@99
   336
		if (!ChangeSize(newSize))
dvander@99
   337
			return false;
dvander@99
   338
		m_CurrentUsedSize = newSize;
dvander@99
   339
		return true;
dvander@99
   340
	}
dvander@99
   341
dvander@99
   342
	bool empty() const
dvander@99
   343
	{
dvander@99
   344
		return (m_CurrentUsedSize == 0);
dvander@99
   345
	}
dvander@99
   346
dvander@99
   347
	T & at(size_t pos)
dvander@99
   348
	{
dvander@99
   349
		if (pos > m_CurrentUsedSize)
dvander@99
   350
		{
dvander@99
   351
			assert(0);
dvander@99
   352
		}
dvander@99
   353
		return m_Data[pos];
dvander@99
   354
	}
dvander@99
   355
dvander@99
   356
	const  T & at(size_t pos) const
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
	T & operator[](size_t pos)
dvander@99
   366
	{
dvander@99
   367
		return at(pos);
dvander@99
   368
	}
dvander@99
   369
dvander@99
   370
	const T & operator[](size_t pos) const
dvander@99
   371
	{
dvander@99
   372
		return at(pos);
dvander@99
   373
	}
dvander@99
   374
dvander@99
   375
	T & front()
dvander@99
   376
	{
dvander@99
   377
		if (m_CurrentUsedSize < 1)
dvander@99
   378
		{
dvander@99
   379
			assert(0);
dvander@99
   380
		}
dvander@99
   381
		return m_Data[0];
dvander@99
   382
	}
dvander@99
   383
dvander@99
   384
	const T & front() const
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
	T & back()
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[m_CurrentUsedSize - 1];
dvander@99
   400
	}
dvander@99
   401
dvander@99
   402
	const T & back() const
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
	iterator insert(iterator where, const T & value)
dvander@99
   412
	{
dvander@99
   413
		// validate iter
dvander@99
   414
		if (where < m_Data || where > (m_Data + m_CurrentUsedSize))
dvander@99
   415
			return iterator(0);
dvander@99
   416
dvander@99
   417
		size_t ofs = where - begin();
dvander@99
   418
dvander@99
   419
		++m_CurrentUsedSize;
dvander@99
   420
		if (!GrowIfNeeded())
dvander@99
   421
		{
dvander@99
   422
			--m_CurrentUsedSize;
dvander@99
   423
			return false;
dvander@99
   424
		}
dvander@99
   425
dvander@99
   426
		where = begin() + ofs;
dvander@99
   427
dvander@99
   428
		// Move subsequent entries
dvander@99
   429
		for (T *ptr = m_Data + m_CurrentUsedSize - 2; ptr >= where.base(); --ptr)
dvander@99
   430
			*(ptr + 1) = *ptr;
dvander@99
   431
dvander@99
   432
		*where.base() = value;
dvander@99
   433
dvander@99
   434
		return where;
dvander@99
   435
	}
dvander@99
   436
dvander@99
   437
	iterator erase(iterator where)
dvander@99
   438
	{
dvander@99
   439
		// validate iter
dvander@99
   440
		if (where < m_Data || where >= (m_Data + m_CurrentUsedSize))
dvander@99
   441
			return iterator(0);
dvander@99
   442
dvander@99
   443
		size_t ofs = where - begin();
dvander@99
   444
dvander@99
   445
		if (m_CurrentUsedSize > 1)
dvander@99
   446
		{
dvander@99
   447
			// move
dvander@99
   448
			T *theend = m_Data + m_CurrentUsedSize;
dvander@99
   449
			for (T *ptr = where.base() + 1; ptr < theend; ++ptr)
dvander@99
   450
				*(ptr - 1) = *ptr;
dvander@99
   451
		}
dvander@99
   452
dvander@99
   453
		--m_CurrentUsedSize;
dvander@99
   454
dvander@99
   455
		FreeMemIfPossible();
dvander@99
   456
dvander@99
   457
		return begin() + ofs;
dvander@99
   458
	}
dvander@99
   459
dvander@99
   460
	void clear()
dvander@99
   461
	{
dvander@99
   462
		m_Size = 0;
dvander@99
   463
		m_CurrentUsedSize = 0;
dvander@99
   464
		if (m_Data)
dvander@99
   465
		{
dvander@99
   466
			delete [] m_Data;
dvander@99
   467
			m_Data = NULL;
dvander@99
   468
		}
dvander@99
   469
	}
dvander@99
   470
};
dvander@99
   471
};	//namespace SourceHook
dvander@99
   472
dvander@99
   473
#endif // __CVECTOR_H__
dvander@99
   474