1 /*!**************************************************************************** 2 3 @file PVRTArray.h 4 @copyright Copyright (c) Imagination Technologies Limited. 5 @brief Expanding array template class. Allows appending and direct 6 access. Mixing access methods should be approached with caution. 7 8 ******************************************************************************/ 9 #ifndef __PVRTARRAY_H__ 10 #define __PVRTARRAY_H__ 11 12 #include "PVRTGlobal.h" 13 #include "PVRTError.h" 14 15 /****************************************************************************** 16 ** Classes 17 ******************************************************************************/ 18 19 /*!*************************************************************************** 20 @class CPVRTArray 21 @brief Expanding array template class. 22 *****************************************************************************/ 23 template<typename T> 24 class CPVRTArray 25 { 26 public: 27 /*!*************************************************************************** 28 @brief Blank constructor. Makes a default sized array. 29 *****************************************************************************/ 30 CPVRTArray() : m_uiSize(0), m_uiCapacity(GetDefaultSize()) 31 { 32 m_pArray = new T[m_uiCapacity]; 33 } 34 35 /*!*************************************************************************** 36 @brief Constructor taking initial size of array in elements. 37 @param[in] uiSize intial size of array 38 *****************************************************************************/ 39 CPVRTArray(const unsigned int uiSize) : m_uiSize(0), m_uiCapacity(uiSize) 40 { 41 _ASSERT(uiSize != 0); 42 m_pArray = new T[uiSize]; 43 } 44 45 /*!*************************************************************************** 46 @brief Copy constructor. 47 @param[in] original the other dynamic array 48 *****************************************************************************/ 49 CPVRTArray(const CPVRTArray& original) : m_uiSize(original.m_uiSize), 50 m_uiCapacity(original.m_uiCapacity) 51 { 52 m_pArray = new T[m_uiCapacity]; 53 for(unsigned int i=0;i<m_uiSize;i++) 54 { 55 m_pArray[i]=original.m_pArray[i]; 56 } 57 } 58 59 /*!*************************************************************************** 60 @brief constructor from ordinary array. 61 @param[in] pArray an ordinary array 62 @param[in] uiSize number of elements passed 63 *****************************************************************************/ 64 CPVRTArray(const T* const pArray, const unsigned int uiSize) : m_uiSize(uiSize), 65 m_uiCapacity(uiSize) 66 { 67 _ASSERT(uiSize != 0); 68 m_pArray = new T[uiSize]; 69 for(unsigned int i=0;i<m_uiSize;i++) 70 { 71 m_pArray[i]=pArray[i]; 72 } 73 } 74 75 /*!*************************************************************************** 76 @brief constructor from a capacity and initial value. 77 @param[in] uiSize initial capacity 78 @param[in] val value to populate with 79 *****************************************************************************/ 80 CPVRTArray(const unsigned int uiSize, const T& val) : m_uiSize(uiSize), 81 m_uiCapacity(uiSize) 82 { 83 _ASSERT(uiSize != 0); 84 m_pArray = new T[uiSize]; 85 for(unsigned int uiIndex = 0; uiIndex < m_uiSize; ++uiIndex) 86 { 87 m_pArray[uiIndex] = val; 88 } 89 } 90 91 /*!*************************************************************************** 92 @brief Destructor. 93 *****************************************************************************/ 94 virtual ~CPVRTArray() 95 { 96 if(m_pArray) 97 delete [] m_pArray; 98 } 99 100 /*!*************************************************************************** 101 @brief Inserts an element into the array, expanding it 102 if necessary. 103 @param[in] pos The position to insert the new element at 104 @param[in] addT The element to insert 105 @return The index of the new item or -1 on failure. 106 *****************************************************************************/ 107 int Insert(const unsigned int pos, const T& addT) 108 { 109 unsigned int uiIndex = pos; 110 111 if(pos >= m_uiSize) // Are we adding to the end 112 uiIndex = Append(addT); 113 else 114 { 115 unsigned int uiNewCapacity = 0; 116 T* pArray = m_pArray; 117 118 if(m_uiSize > m_uiCapacity) 119 { 120 uiNewCapacity = m_uiCapacity + 10; // Expand the array by 10. 121 122 pArray = new T[uiNewCapacity]; // New Array 123 124 if(!pArray) 125 return -1; // Failed to allocate memory! 126 127 // Copy the first half to the new array 128 for(unsigned int i = 0; i < pos; ++i) 129 { 130 pArray[i] = m_pArray[i]; 131 } 132 } 133 134 // Copy last half to the new array 135 for(unsigned int i = m_uiSize; i > pos; --i) 136 { 137 pArray[i] = m_pArray[i - 1]; 138 } 139 140 // Insert our new element 141 pArray[pos] = addT; 142 uiIndex = pos; 143 144 // Increase our size 145 ++m_uiSize; 146 147 // Switch pointers and free memory if needed 148 if(pArray != m_pArray) 149 { 150 m_uiCapacity = uiNewCapacity; 151 delete[] m_pArray; 152 m_pArray = pArray; 153 } 154 } 155 156 return uiIndex; 157 } 158 159 /*!*************************************************************************** 160 @brief Appends an element to the end of the array, expanding it 161 if necessary. 162 @param[in] addT The element to append 163 @return The index of the new item. 164 *****************************************************************************/ 165 unsigned int Append(const T& addT) 166 { 167 unsigned int uiIndex = Append(); 168 m_pArray[uiIndex] = addT; 169 return uiIndex; 170 } 171 172 /*!*************************************************************************** 173 @brief Creates space for a new item, but doesn't add. Instead 174 returns the index of the new item. 175 @return The index of the new item. 176 *****************************************************************************/ 177 unsigned int Append() 178 { 179 unsigned int uiIndex = m_uiSize; 180 SetCapacity(m_uiSize+1); 181 m_uiSize++; 182 183 return uiIndex; 184 } 185 186 /*!*************************************************************************** 187 @brief Clears the array. 188 *****************************************************************************/ 189 void Clear() 190 { 191 m_uiSize = 0U; 192 } 193 194 /*!*************************************************************************** 195 @brief Changes the array to the new size 196 @param[in] uiSize New size of array 197 *****************************************************************************/ 198 EPVRTError Resize(const unsigned int uiSize) 199 { 200 EPVRTError err = SetCapacity(uiSize); 201 202 if(err != PVR_SUCCESS) 203 return err; 204 205 m_uiSize = uiSize; 206 return PVR_SUCCESS; 207 } 208 209 /*!*************************************************************************** 210 @brief Expands array to new capacity 211 @param[in] uiSize New capacity of array 212 *****************************************************************************/ 213 EPVRTError SetCapacity(const unsigned int uiSize) 214 { 215 if(uiSize <= m_uiCapacity) 216 return PVR_SUCCESS; // nothing to be done 217 218 unsigned int uiNewCapacity; 219 if(uiSize < m_uiCapacity*2) 220 { 221 uiNewCapacity = m_uiCapacity*2; // Ignore the new size. Expand to twice the previous size. 222 } 223 else 224 { 225 uiNewCapacity = uiSize; 226 } 227 228 T* pNewArray = new T[uiNewCapacity]; // New Array 229 if(!pNewArray) 230 return PVR_FAIL; // Failed to allocate memory! 231 232 // Copy source data to new array 233 for(unsigned int i = 0; i < m_uiSize; ++i) 234 { 235 pNewArray[i] = m_pArray[i]; 236 } 237 238 // Switch pointers and free memory 239 m_uiCapacity = uiNewCapacity; 240 T* pOldArray = m_pArray; 241 m_pArray = pNewArray; 242 delete [] pOldArray; 243 return PVR_SUCCESS; 244 } 245 246 /*!*************************************************************************** 247 @fn Copy 248 @brief A copy function. Will attempt to copy from other CPVRTArrays 249 if this is possible. 250 @param[in] other The CPVRTArray needing copied 251 *****************************************************************************/ 252 template<typename T2> 253 void Copy(const CPVRTArray<T2>& other) 254 { 255 T* pNewArray = new T[other.GetCapacity()]; 256 if(pNewArray) 257 { 258 // Copy data 259 for(unsigned int i = 0; i < other.GetSize(); i++) 260 { 261 pNewArray[i] = other[i]; 262 } 263 264 // Free current array 265 if(m_pArray) 266 delete [] m_pArray; 267 268 // Swap pointers 269 m_pArray = pNewArray; 270 271 m_uiCapacity = other.GetCapacity(); 272 m_uiSize = other.GetSize(); 273 } 274 } 275 276 /*!*************************************************************************** 277 @brief assignment operator. 278 @param[in] other The CPVRTArray needing copied 279 *****************************************************************************/ 280 CPVRTArray& operator=(const CPVRTArray<T>& other) 281 { 282 if(&other != this) 283 Copy(other); 284 285 return *this; 286 } 287 288 /*!*************************************************************************** 289 @brief appends an existing CPVRTArray on to this one. 290 @param[in] other the array to append. 291 *****************************************************************************/ 292 CPVRTArray& operator+=(const CPVRTArray<T>& other) 293 { 294 if(&other != this) 295 { 296 for(unsigned int uiIndex = 0; uiIndex < other.GetSize(); ++uiIndex) 297 { 298 Append(other[uiIndex]); 299 } 300 } 301 302 return *this; 303 } 304 305 /*!*************************************************************************** 306 @brief Indexed access into array. Note that this has no error 307 checking whatsoever 308 @param[in] uiIndex index of element in array 309 @return the element indexed 310 *****************************************************************************/ 311 T& operator[](const unsigned int uiIndex) 312 { 313 _ASSERT(uiIndex < m_uiCapacity); 314 return m_pArray[uiIndex]; 315 } 316 317 /*!*************************************************************************** 318 @brief Indexed access into array. Note that this has no error checking whatsoever 319 @param[in] uiIndex index of element in array 320 @return The element indexed 321 *****************************************************************************/ 322 const T& operator[](const unsigned int uiIndex) const 323 { 324 _ASSERT(uiIndex < m_uiCapacity); 325 return m_pArray[uiIndex]; 326 } 327 328 /*!*************************************************************************** 329 @return Size of array 330 @brief Gives current size of array/number of elements 331 *****************************************************************************/ 332 unsigned int GetSize() const 333 { 334 return m_uiSize; 335 } 336 337 /*!*************************************************************************** 338 @brief Gives the default size of array/number of elements 339 @return Default size of array 340 *****************************************************************************/ 341 static unsigned int GetDefaultSize() 342 { 343 return 16U; 344 } 345 346 /*!*************************************************************************** 347 @brief Gives current allocated size of array/number of elements 348 @return Capacity of array 349 *****************************************************************************/ 350 unsigned int GetCapacity() const 351 { 352 return m_uiCapacity; 353 } 354 355 /*!*************************************************************************** 356 @brief Indicates whether the given object resides inside the array. 357 @param[in] object The object to check in the array 358 @return true if object is contained in this array. 359 *****************************************************************************/ 360 bool Contains(const T& object) const 361 { 362 for(unsigned int uiIndex = 0; uiIndex < m_uiSize; ++uiIndex) 363 { 364 if(m_pArray[uiIndex] == object) 365 return true; 366 } 367 return false; 368 } 369 370 /*!*************************************************************************** 371 @brief Attempts to find the object in the array and returns a 372 pointer if it is found, or NULL if not found. The time 373 taken is O(N). 374 @param[in] object The object to check in the array 375 @return Pointer to the found object or NULL. 376 *****************************************************************************/ 377 T* Find(const T& object) const 378 { 379 for(unsigned int uiIndex = 0; uiIndex < m_uiSize; ++uiIndex) 380 { 381 if(m_pArray[uiIndex] == object) 382 return &m_pArray[uiIndex]; 383 } 384 return NULL; 385 } 386 387 /*!*************************************************************************** 388 @brief Simple bubble-sort of the array. Pred should be an object that 389 defines a bool operator(). 390 @param[in] predicate The object which defines "bool operator()" 391 *****************************************************************************/ 392 template<class Pred> 393 void Sort(Pred predicate) 394 { 395 bool bSwap; 396 for(unsigned int i=0; i < m_uiSize; ++i) 397 { 398 bSwap = false; 399 for(unsigned int j=0; j < m_uiSize-1; ++j) 400 { 401 if(predicate(m_pArray[j], m_pArray[j+1])) 402 { 403 PVRTswap(m_pArray[j], m_pArray[j+1]); 404 bSwap = true; 405 } 406 } 407 408 if(!bSwap) 409 return; 410 } 411 } 412 413 /*!*************************************************************************** 414 @brief Removes an element from the array. 415 @param[in] uiIndex The index to remove 416 @return success or failure 417 *****************************************************************************/ 418 virtual EPVRTError Remove(unsigned int uiIndex) 419 { 420 _ASSERT(uiIndex < m_uiSize); 421 if(m_uiSize == 0) 422 return PVR_FAIL; 423 424 if(uiIndex == m_uiSize-1) 425 { 426 return RemoveLast(); 427 } 428 429 m_uiSize--; 430 // Copy the data. memmove will only work for built-in types. 431 for(unsigned int uiNewIdx = uiIndex; uiNewIdx < m_uiSize; ++uiNewIdx) 432 { 433 m_pArray[uiNewIdx] = m_pArray[uiNewIdx+1]; 434 } 435 436 return PVR_SUCCESS; 437 } 438 439 /*!*************************************************************************** 440 @brief Removes the last element. Simply decrements the size value 441 @return success or failure 442 *****************************************************************************/ 443 virtual EPVRTError RemoveLast() 444 { 445 if(m_uiSize > 0) 446 { 447 m_uiSize--; 448 return PVR_SUCCESS; 449 } 450 else 451 { 452 return PVR_FAIL; 453 } 454 } 455 456 protected: 457 unsigned int m_uiSize; /*!< Current size of contents of array */ 458 unsigned int m_uiCapacity; /*!< Currently allocated size of array */ 459 T *m_pArray; /*!< The actual array itself */ 460 }; 461 462 // note "this" is required for ISO standard, C++ and gcc complains otherwise 463 // http://lists.apple.com/archives/Xcode-users//2005/Dec/msg00644.html 464 465 /*!*************************************************************************** 466 @class CPVRTArrayManagedPointers 467 @brief Maintains an array of managed pointers. 468 *****************************************************************************/ 469 template<typename T> 470 class CPVRTArrayManagedPointers : public CPVRTArray<T*> 471 { 472 public: 473 /*!*************************************************************************** 474 @brief Destructor. 475 *****************************************************************************/ 476 virtual ~CPVRTArrayManagedPointers() 477 { 478 if(this->m_pArray) 479 { 480 for(unsigned int i=0;i<this->m_uiSize;i++) 481 { 482 delete(this->m_pArray[i]); 483 } 484 } 485 } 486 487 /*!*************************************************************************** 488 @brief Removes an element from the array. 489 @param[in] uiIndex The index to remove. 490 @return success or failure 491 *****************************************************************************/ 492 virtual EPVRTError Remove(unsigned int uiIndex) 493 { 494 _ASSERT(uiIndex < this->m_uiSize); 495 if(this->m_uiSize == 0) 496 return PVR_FAIL; 497 498 if(uiIndex == this->m_uiSize-1) 499 { 500 return this->RemoveLast(); 501 } 502 503 unsigned int uiSize = (this->m_uiSize - (uiIndex+1)) * sizeof(T*); 504 505 delete this->m_pArray[uiIndex]; 506 memmove(this->m_pArray + uiIndex, this->m_pArray + (uiIndex+1), uiSize); 507 508 this->m_uiSize--; 509 return PVR_SUCCESS; 510 } 511 512 /*!*************************************************************************** 513 @brief Removes the last element. Simply decrements the size value 514 @return success or failure 515 *****************************************************************************/ 516 virtual EPVRTError RemoveLast() 517 { 518 if(this->m_uiSize > 0 && this->m_pArray) 519 { 520 delete this->m_pArray[this->m_uiSize-1]; 521 this->m_uiSize--; 522 return PVR_SUCCESS; 523 } 524 else 525 { 526 return PVR_FAIL; 527 } 528 } 529 }; 530 531 #endif // __PVRTARRAY_H__ 532 533 /***************************************************************************** 534 End of file (PVRTArray.h) 535 *****************************************************************************/ 536 537