1 /* 2 * Copyright 2006 Sony Computer Entertainment Inc. 3 * 4 * Licensed under the MIT Open Source License, for details please see license.txt or the website 5 * http://www.opensource.org/licenses/mit-license.php 6 * 7 */ 8 9 #ifndef __DAE_ARRAY_H__ 10 #define __DAE_ARRAY_H__ 11 #include <new> 12 #include <dae/daeMemorySystem.h> 13 14 class daeAtomicType; 15 16 /** 17 * COLLADA C++ class that implements storage for resizable array containers. 18 */ 19 class daeArray 20 { 21 protected: 22 size_t _count; 23 size_t _capacity; 24 daeMemoryRef _data; 25 size_t _elementSize; 26 daeAtomicType* _type; 27 public: 28 /** 29 * Constructor 30 */ 31 DLLSPEC daeArray(); 32 /** 33 * Destructor 34 */ 35 virtual DLLSPEC ~daeArray(); 36 /** 37 * Clears the contents of the array. Do not use this function if the array contains @c daeSmartRef objects and the 38 * @c dom* class the array belongs to has a @c _contents member. 39 * 40 * Many @c dom* objects have a @c _contents member that stores the original creation order of the @c daeElements 41 * that are their children. If you use @c clear() on a @c daeArray of @c daeSmartRef derived objects, these 42 * objects will not be removed from @c _contents, which can cause problems when you 43 * save the data. We recommended that @c clear() not be used on arrays that are part of a @c dom* object. 44 */ 45 virtual DLLSPEC void clear() = 0; 46 /** 47 * Sets the size of an element in the array. This clears and reinitializes the array. 48 * @param elementSize Size of an element in the array. 49 */ 50 DLLSPEC void setElementSize(size_t elementSize); 51 /** 52 * Gets the size of an element in this array. 53 * @return Returns the size of an element in this array. 54 */ 55 size_t getElementSize() const {return _elementSize;} 56 /** 57 * Grows the array to the specified size and sets the @c daeArray to that size. 58 * @param cnt Size to grow the array to. 59 */ 60 virtual void setCount(size_t cnt) = 0; 61 /** 62 * Gets the number of items stored in this @c daeArray. 63 * @return Returns the number of items stored in this @c daeArray. 64 */ 65 size_t getCount() const {return _count;} 66 /** 67 * Increases the capacity of the @c daeArray. 68 * @param minCapacity The minimum array capacity (the actual resulting capacity may be higher). 69 */ 70 virtual void grow(size_t minCapacity) = 0; 71 /** 72 * Gets the current capacity of the array, the biggest it can get without incurring a realloc. 73 * @return Returns the capacity of the array. 74 */ 75 size_t getCapacity() const {return _capacity;} 76 /** 77 * Gets a pointer to the raw memory of a particular element. 78 * @return Returns a pointer to the memory for the raw data. 79 */ 80 daeMemoryRef getRaw(size_t index) const {return _data + index*_elementSize;} 81 /** 82 * Removes an item at a specific index in the @c daeArray. 83 * @param index Index number of the item to delete. 84 * @return Returns DAE_OK if success, a negative value defined in daeError.h otherwise. 85 * @note The @c daeElement objects sometimes list 86 * objects in two places, the class member and the <i> @c _contents </i> array, when you remove something from the 87 * dom, you must remove it from both places. 88 */ 89 virtual daeInt removeIndex(size_t index) = 0; 90 91 // Provided for backward compatibility only. Don't use these. 92 void setRawCount(size_t cnt) { setCount(cnt); } // Use setCount instead 93 daeMemoryRef getRawData() const {return _data;} // Use getRaw instead 94 }; 95 96 /** 97 * COLLADA C++ templated version of @c daeArray for storing items of various types. 98 */ 99 template <class T> 100 class daeTArray : public daeArray 101 { 102 protected: 103 T* prototype; 104 public: 105 /** 106 * Constructor. 107 */ 108 daeTArray() { 109 _elementSize = sizeof( T ); 110 prototype = NULL; 111 } 112 /** 113 * Constructor. 114 */ 115 explicit daeTArray(T* prototype) : prototype(prototype) { 116 _elementSize = sizeof( T ); 117 } 118 /** 119 * Copy Constructor 120 */ 121 daeTArray( const daeTArray<T> &cpy ) : daeArray() { 122 prototype = NULL; 123 *this = cpy; 124 } 125 /** 126 * Constructor that takes one element and turns into an array 127 */ 128 explicit daeTArray( const T &el ) { 129 _elementSize = sizeof(T); 130 prototype = NULL; 131 append( el ); 132 } 133 /** 134 * Destructor. 135 */ 136 virtual ~daeTArray() { 137 clear(); 138 delete prototype; 139 } 140 /** 141 * Frees the memory in this array and resets it to it's initial state. 142 */ 143 virtual void clear() 144 { 145 for(size_t i=0;i<_count;i++) 146 ((T*)_data + i)->~T(); 147 free(_data); 148 _count = 0; 149 _capacity = 0; 150 _data = NULL; 151 } 152 153 /** 154 * Increases the capacity of the @c daeArray. 155 * @param minCapacity The minimum array capacity (the actual resulting capacity may be higher). 156 */ 157 void grow(size_t minCapacity) { 158 if (minCapacity <= _capacity) 159 return; 160 161 size_t newCapacity = _capacity == 0 ? 1 : _capacity; 162 while(newCapacity < minCapacity) 163 newCapacity *= 2; 164 165 T* newData = (T*)malloc(newCapacity*_elementSize); 166 for (size_t i = 0; i < _count; i++) { 167 new (&newData[i]) T(get(i)); 168 ((T*)_data + i)->~T(); 169 } 170 171 if (_data != NULL) 172 free(_data); 173 174 _data = (daeMemoryRef)newData; 175 _capacity = newCapacity; 176 } 177 178 /** 179 * Removes an item at a specific index in the @c daeArray. 180 * @param index Index number of the item to delete. 181 * @return Returns DAE_OK if success, a negative value defined in daeError.h otherwise. 182 * @note The @c daeElement objects sometimes list 183 * objects in two places, the class member and the <i> @c _contents </i> array, when you remove something from the 184 * dom, you must remove it from both places. 185 */ 186 virtual daeInt removeIndex(size_t index) 187 { 188 if (index >= _count) 189 return(DAE_ERR_INVALID_CALL); 190 191 for (size_t i = index; i < _count-1; i++) 192 *((T*)_data+i) = *((T*)_data+i+1); 193 ((T*)_data+(_count-1))->~T(); 194 _count--; 195 return DAE_OK; 196 } 197 198 /** 199 * Resets the number of elements in the array. If the array increases in size, the new 200 * elements will be initialized to the specified value. 201 * @param nElements The new size of the array. 202 * @param value The value new elements will be initialized to. 203 * @note Shrinking the array does NOT free up memory. 204 */ 205 void setCount(size_t nElements, const T& value) 206 { 207 grow(nElements); 208 // Destruct the elements that are being chopped off 209 for (size_t i = nElements; i < _count; i++) 210 ((T*)_data+i)->~T(); 211 // Use value to initialize the new elements 212 for (size_t i = _count; i < nElements; i++) 213 new ((void*)((T*)_data+i)) T(value); 214 _count = nElements; 215 } 216 217 /** 218 * Resets the number of elements in the array. If the array increases in size, the new 219 * elements will be initialized with a default constructor. 220 * @param nElements The new size of the array. 221 * @note Shrinking the array does NOT free up memory. 222 */ 223 virtual void setCount(size_t nElements) { 224 if (prototype) 225 setCount(nElements, *prototype); 226 else 227 setCount(nElements, T()); 228 } 229 230 /** 231 * Sets a specific index in the @c daeArray, growing the array if necessary. 232 * @param index Index of the object to set, asserts if the index is out of bounds. 233 * @param value Value to store at index in the array. 234 */ 235 void set(size_t index, const T& value) { 236 if (index >= _count) 237 setCount(index+1); 238 ((T*)_data)[index] = value; 239 } 240 241 /** 242 * Gets the object at a specific index in the @c daeArray. 243 * @param index Index of the object to get, asserts if the index is out of bounds. 244 * @return Returns the object at index. 245 */ 246 T& get(size_t index) { 247 assert(index < _count); 248 return ((T*)_data)[index]; } 249 /** 250 * Gets the object at a specific index in the @c daeArray. 251 * @param index Index of the object to get, asserts if the index is out of bounds. 252 * @return Returns the object at index. 253 */ 254 const T& get(size_t index) const { 255 assert(index < _count); 256 return ((T*)_data)[index]; } 257 258 /** 259 * Appends a new object to the end of the @c daeArray. 260 * @param value Value of the object to append. 261 * @return Returns the index of the new object. 262 */ 263 size_t append(const T& value) { 264 set(_count, value); 265 return _count-1; 266 } 267 268 /** 269 * Appends a unique object to the end of the @c daeArray. 270 * Functions the same as @c append(), but does nothing if the value is already in the @c daeArray. 271 * @param value Value of the object to append. 272 * @return Returns the index where this value was appended. If the value already exists in the array, 273 * returns the index in this array where the value was found. 274 */ 275 size_t appendUnique(const T& value) { 276 size_t ret; 277 if (find(value,ret) != DAE_OK) 278 return append(value); 279 else 280 return ret; 281 } 282 283 /** 284 * Adds a new item to the front of the @c daeArray. 285 * @param value Item to be added. 286 */ 287 void prepend(const T& value) { 288 insertAt(0, value); 289 } 290 291 /** 292 * Removes an item from the @c daeArray. 293 * @param value A reference to the item to delete. 294 * @return Returns DAE_OK if success, a negative value defined in daeError.h otherwise. 295 * @note The @c daeElement objects sometimes list 296 * objects in two places, the class member and the <i> @c _contents </i> array, when you remove something from the 297 * do, you must remove it from both places. 298 */ 299 daeInt remove(const T& value, size_t *idx = NULL ) 300 { 301 size_t index; 302 if(find(value,index) == DAE_OK) 303 { 304 if ( idx != NULL ) { 305 *idx = index; 306 } 307 return(removeIndex( index )); 308 } 309 else 310 { 311 return(DAE_ERR_INVALID_CALL); 312 } 313 } 314 /** 315 * Finds an item from the @c daeArray. 316 * @param value A reference to the item to find. 317 * @param index If the function returns DAE_OK, this is set to the index where the value appears in the array. 318 * @return Returns DAE_OK if no error or DAE_ERR_QUERY_NO_MATCH if the value was not found. 319 */ 320 daeInt find(const T& value, size_t &index) const 321 { 322 size_t i; 323 for(i=0;i<_count;i++) 324 { 325 if (((T*)_data)[i] == value) 326 { 327 index = i; 328 return DAE_OK; 329 } 330 } 331 332 return DAE_ERR_QUERY_NO_MATCH; 333 } 334 /** 335 * Just like the previous function, but has a more reasonable interface. 336 * @param value The value to find. 337 * @return Returns a pointer to the value if found, null otherwise. 338 */ 339 T* find(const T& value) const { 340 size_t i; 341 if (find(value, i) == DAE_OK) 342 return get(i); 343 return NULL; 344 } 345 /** 346 * Gets the object at a specific index in the @c daeArray. 347 * @param index Index of the object to get, asserts if the index is out of bounds. 348 * @return Returns the object at @c index. 349 */ 350 T& operator[](size_t index) { 351 assert(index < _count); 352 return ((T*)_data)[index]; } 353 /** 354 * Gets the object at a specific index in the @c daeArray. 355 * @param index Index of the object to get, asserts if the index is out of bounds. 356 * @return Returns the object at @c index. 357 */ 358 const T& operator[](size_t index) const { 359 assert(index < _count); 360 return ((T*)_data)[index]; } 361 362 /** 363 * Inserts the specified number of elements at a specific location in the array. 364 * @param index Index into the array where the elements will be inserted 365 * @param n The number of elements to insert 366 * @param val The value to insert 367 */ 368 void insert(size_t index, size_t n, const T& val = T()) { 369 if (index >= _count) { 370 // Append to the end of the array 371 size_t oldCount = _count; 372 setCount(index + n); 373 for (size_t i = oldCount; i < _count; i++) 374 get(i) = val; 375 } 376 else { 377 setCount(_count + n); 378 for (size_t i = _count-1; i >= index+n; i--) 379 get(i) = get(i-n); 380 for (size_t i = index; i < index+n; i++) 381 get(i) = val; 382 } 383 } 384 385 /** 386 * Inserts an object at a specific index in the daeArray, growing the array if neccessary 387 * @param index Index into the array for where to place the object 388 * @param value The object to append 389 */ 390 void insertAt(size_t index, const T& value) { 391 insert(index, 1); 392 get(index) = value; 393 } 394 395 /** 396 * Overloaded assignment operator. 397 * @param other A reference to the array to copy 398 * @return A reference to this object. 399 */ 400 daeTArray<T> &operator=( const daeTArray<T> &other ) { 401 if (this != &other) { 402 clear(); 403 _elementSize = other._elementSize; 404 _type = other._type; 405 grow(other._count); 406 for(size_t i=0;i<other._count;i++) 407 append(other[i]); 408 } 409 410 return *this; 411 } 412 413 /** 414 * Overloaded equality operator 415 * @param other A reference to the other array. 416 * @return true if the arrays are equal, false otherwise. 417 */ 418 bool operator==(const daeTArray<T>& other) { 419 if (getCount() != other.getCount()) 420 return false; 421 for (size_t i = 0; i < getCount(); i++) 422 if (get(i) != other.get(i)) 423 return false; 424 return true; 425 } 426 427 //some helpers 428 /** 429 * Sets the array to the contain the two values specified. 430 * @param one The first value. 431 * @param two The second value. 432 */ 433 void set2( const T &one, const T &two ) 434 { 435 setCount( 2 ); 436 set( 0, one ); 437 set( 1, two ); 438 } 439 /** 440 * Sets the array to the contain the three values specified. 441 * @param one The first value. 442 * @param two The second value. 443 * @param three The third value. 444 */ 445 void set3( const T &one, const T &two, const T &three ) 446 { 447 setCount( 3 ); 448 set( 0, one ); 449 set( 1, two ); 450 set( 2, three ); 451 } 452 /** 453 * Sets the array to the contain the four values specified. 454 * @param one The first value. 455 * @param two The second value. 456 * @param three The third value. 457 * @param four The fourth value. 458 */ 459 void set4( const T &one, const T &two, const T &three, const T &four ) 460 { 461 setCount( 4 ); 462 set( 0, one ); 463 set( 1, two ); 464 set( 2, three ); 465 set( 3, four ); 466 } 467 468 /** 469 * Sets the values in the array at the specified location to the contain the two 470 * values specified. This function will grow the array if needed. 471 * @param index The position in the array to start setting. 472 * @param one The first value. 473 * @param two The second value. 474 */ 475 void set2at( size_t index, const T &one, const T &two ) 476 { 477 set( index, one ); 478 set( index+1, two ); 479 } 480 /** 481 * Sets the values in the array at the specified location to the contain the three 482 * values specified. This function will grow the array if needed. 483 * @param index The position in the array to start setting. 484 * @param one The first value. 485 * @param two The second value. 486 * @param three The third value. 487 */ 488 void set3at( size_t index, const T &one, const T &two, const T &three ) 489 { 490 set( index, one ); 491 set( index+1, two ); 492 set( index+2, three ); 493 } 494 /** 495 * Sets the values in the array at the specified location to the contain the four 496 * values specified. This function will grow the array if needed. 497 * @param index The position in the array to start setting. 498 * @param one The first value. 499 * @param two The second value. 500 * @param three The third value. 501 * @param four The fourth value. 502 */ 503 void set4at( size_t index, const T &one, const T &two, const T &three, const T &four ) 504 { 505 set( index, one ); 506 set( index+1, two ); 507 set( index+2, three ); 508 set( index+3, four ); 509 } 510 511 /** 512 * Appends two values to the array. 513 * @param one The first value. 514 * @param two The second value. 515 */ 516 void append2( const T &one, const T &two ) 517 { 518 append( one ); 519 append( two ); 520 } 521 /** 522 * Appends three values to the array. 523 * @param one The first value. 524 * @param two The second value. 525 * @param three The third value. 526 */ 527 void append3( const T &one, const T &two, const T &three ) 528 { 529 append( one ); 530 append( two ); 531 append( three ); 532 } 533 /** 534 * Appends four values to the array. 535 * @param one The first value. 536 * @param two The second value. 537 * @param three The third value. 538 * @param four The fourth value. 539 */ 540 void append4( const T &one, const T &two, const T &three, const T &four ) 541 { 542 append( one ); 543 append( two ); 544 append( three ); 545 append( four ); 546 } 547 548 /** 549 * Inserts two values into the array at the specified location. 550 * @param index The position in the array to start inserting. 551 * @param one The first value. 552 * @param two The second value. 553 */ 554 void insert2at( size_t index, const T &one, const T &two ) 555 { 556 insert(index, 2); 557 set(index, one); 558 set(index+1, two); 559 } 560 /** 561 * Inserts three values into the array at the specified location. 562 * @param index The position in the array to start inserting. 563 * @param one The first value. 564 * @param two The second value. 565 * @param three The third value. 566 */ 567 void insert3at( size_t index, const T &one, const T &two, const T &three ) 568 { 569 insert(index, 3); 570 set( index, one ); 571 set( index+1, two ); 572 set( index+2, three ); 573 } 574 /** 575 * Inserts four values into the array at the specified location. 576 * @param index The position in the array to start inserting. 577 * @param one The first value. 578 * @param two The second value. 579 * @param three The third value. 580 * @param four The fourth value. 581 */ 582 void insert4at( size_t index, const T &one, const T &two, const T &three, const T &four ) 583 { 584 insert(index, 4); 585 set( index, one ); 586 set( index+1, two ); 587 set( index+2, three ); 588 set( index+4, four ); 589 } 590 591 /** 592 * Gets two values from the array at the specified location. 593 * @param index The position in the array to start getting. 594 * @param one Variable to store the first value. 595 * @param two Variable to store the second value. 596 * @return Returns The number of elements retrieved. 597 */ 598 daeInt get2at( size_t index, T &one, T &two ) 599 { 600 daeInt retVal = 0; 601 if ( index < _count ) 602 { 603 one = get(index); 604 retVal++; 605 } 606 if ( index+1 < _count ) 607 { 608 two = get(index+1); 609 retVal++; 610 } 611 return retVal; 612 } 613 /** 614 * Gets three values from the array at the specified location. 615 * @param index The position in the array to start getting. 616 * @param one Variable to store the first value. 617 * @param two Variable to store the second value. 618 * @param three Variable to store the third value. 619 * @return Returns The number of elements retrieved. 620 */ 621 daeInt get3at( size_t index, T &one, T &two, T &three ) 622 { 623 daeInt retVal = 0; 624 if ( index < _count ) 625 { 626 one = get(index); 627 retVal++; 628 } 629 if ( index+1 < _count ) 630 { 631 two = get(index+1); 632 retVal++; 633 } 634 if ( index+2 < _count ) 635 { 636 three = get(index+2); 637 retVal++; 638 } 639 return retVal; 640 } 641 /** 642 * Gets four values from the array at the specified location. 643 * @param index The position in the array to start getting. 644 * @param one Variable to store the first value. 645 * @param two Variable to store the second value. 646 * @param three Variable to store the third value. 647 * @param four Variable to store the fourth value. 648 * @return Returns The number of elements retrieved. 649 */ 650 daeInt get4at( size_t index, T &one, T &two, T &three, T &four ) 651 { 652 daeInt retVal = 0; 653 if ( index < _count ) 654 { 655 one = get(index); 656 retVal++; 657 } 658 if ( index+1 < _count ) 659 { 660 two = get(index+1); 661 retVal++; 662 } 663 if ( index+2 < _count ) 664 { 665 three = get(index+2); 666 retVal++; 667 } 668 if ( index+3 < _count ) 669 { 670 four = get(index+3); 671 retVal++; 672 } 673 return retVal; 674 } 675 676 /** 677 * Appends a number of elements to this array from a C native array. 678 * @param num The number of elements to append. 679 * @param array The C native array that contains the values to append. 680 */ 681 void appendArray( size_t num, T *array ) 682 { 683 if ( array == NULL ) 684 return; 685 686 for ( size_t i = 0; i < num; i++ ) 687 append( array[i] ); 688 } 689 /** 690 * Appends a number of elements to this array from another daeTArray. 691 * @param array The daeTArray that contains the values to append. 692 */ 693 void appendArray( const daeTArray<T> &array ){ 694 size_t num = array.getCount(); 695 for ( size_t i = 0; i < num; i++ ) 696 append( array[i] ); 697 } 698 }; 699 700 701 #endif //__DAE_ARRAY_H__ 702
