- Main Page
- Modules
- Namespaces
- Classes
- Files
- Related Pages

- File List
- File Members

# FMath/FMArray.h

Go to the documentation of this file.

    00001 /*
    00002     Copyright (C) 2005-2007 Feeling Software Inc.
    00003     Portions of the code are:
    00004     Copyright (C) 2005-2007 Sony Computer Entertainment America
    00005
    00006     MIT License: http://www.opensource.org/licenses/mit-license.php
    00007 */
    00008
    00014 #ifndef _FM_ARRAY_H_
    00015 #define _FM_ARRAY_H_
    00016
    00017 #ifndef _FM_ALLOCATOR_H_
    00018 #include "FMath/FMAllocator.h"
    00019 #endif // _FM_ALLOCATOR_H_
    00020 #ifndef _FM_SORT_H_
    00021 #include "FMath/FMSort.h"
    00022 #endif // _FM_SORT_H_
    00023
    00024 #ifdef WIN32
    00025 #pragma warning(disable:4127)
    00026 #endif //WIN32
    00027
    00029 namespace fm
    00030 {
    00042     template <class T, bool PRIMITIVE=false>
    00043     class vector
    00044     {
    00045     protected:
    00046         size_t reserved;
    00047         size_t sized;
    00048         T* heapBuffer;
    00050     public:
    00052         typedef T* iterator;
    00053
    00055         typedef const T* const_iterator;
    00056
    00057     public:
    00059         vector() : reserved(0), sized(0), heapBuffer(NULL) {}
    00060
    00063         vector(size_t size) : reserved(0), sized(0), heapBuffer(NULL)
    00064         {
    00065             resize(size);
    00066         }
    00067
    00071         vector(size_t size, const T& defaultValue) : reserved(0), sized(0), heapBuffer(NULL)
    00072         {
    00073             resize(size, defaultValue);
    00074         }
    00075
    00078         vector(const fm::vector<T,PRIMITIVE>& copy) : reserved(0), sized(0), heapBuffer(NULL)
    00079         {
    00080             insert(heapBuffer, copy.begin(), copy.size());
    00081         }
    00082
    00086         vector(const T* values, size_t count) : reserved(0), sized(0), heapBuffer(NULL)
    00087         {
    00088             insert(heapBuffer, values, count);
    00089         }
    00090
    00092         ~vector()
    00093         {
    00094             if (!PRIMITIVE)
    00095             {
    00096                 for (intptr_t i = sized - 1; i >= 0; --i)
    00097                 {
    00098                     heapBuffer[i].~T();
    00099                 }
    00100             }
    00101             if (heapBuffer != NULL)
    00102             {
    00103                 fm::Release(heapBuffer);
    00104             }
    00105         }
    00106
    00110         inline T** GetDataPtr() { return &heapBuffer; }
    00111         inline const T** GetDataPtr() const { return (const T**) &heapBuffer; }
    00117         template <class Type2> iterator find(const Type2& value)
    00118         {
    00119             T* i = begin(),* e = end();
    00120             for (; i != e; ++i) if ((*i) == value) break;
    00121             return i;
    00122         }
    00123         template <class Type2> const_iterator find(const Type2& value) const
    00124         {
    00125             const T* i = begin(),* e = end();
    00126             for (; i != e; ++i) if ((*i) == value) break;
    00127             return i;
    00128         }
    00131         inline void sort()
    00132         {
    00133             comparator<T> comp;
    00134             comp.sort(heapBuffer, sized);
    00135         }
    00136
    00139         inline void sort(comparator<T>& comp)
    00140         {
    00141             comp.sort(heapBuffer, sized);
    00142         }
    00143
    00146         iterator erase(iterator it)
    00147         {
    00148             FUAssert(it >= begin() && it < end(), return it);
    00149             if (!PRIMITIVE) (*it).~T();
    00150             if (end() - it - 1 > 0) memmove(it, it+1, (end() - it - 1) * sizeof(T));
    00151             --sized;
    00152             return it;
    00153         }
    00154
    00160         void erase(iterator first, iterator last)
    00161         {
    00162             FUAssert(first >= begin() && first < end(), return);
    00163             FUAssert(last > begin() && last <= end(), return);
    00164             if (!PRIMITIVE) for (iterator it = first; it != last; ++it) (*it).~T();
    00165             if (end() - last > 0) memmove(first, last, (end() - last) * sizeof(T));
    00166             sized -= last - first;
    00167         }
    00168
    00172         inline void erase(size_t first, size_t last) { erase(begin() + first, begin() + last); }
    00173
    00177         inline bool erase(const T& value) { iterator it = find(value); if (it != end()) { erase(it); return true; } return false; }
    00178
    00181         inline void erase(size_t index) { erase(begin() + index); }
    00182
    00186         inline bool contains(const T& value) const { const_iterator it = find(value); return it != end(); }
    00187
    00193         template <class V2, class V3>
    00194         inline void replace(const V2& oldValue, const V3& newValue)
    00195         {
    00196             for (iterator start = begin(), stop = end(); start != stop; ++start)
    00197             {
    00198                 if (*start == (T) oldValue) *start = newValue;
    00199             }
    00200         }
    00201
    00208         template <class V2, class V3>
    00209         inline void replace(iterator start, iterator end, const V2& oldValue, const V3& newValue)
    00210         {
    00211             while (start != end)
    00212             {
    00213                 if (*start == (T) oldValue) *start = newValue;
    00214                 ++start;
    00215             }
    00216         }
    00217
    00220         inline size_t size() const { return sized; }
    00221
    00223         inline bool empty() const { return sized == 0; }
    00224
    00227         void resize(size_t count)
    00228         {
    00229             reserve(count);
    00230
    00231             if (!PRIMITIVE)
    00232             {
    00233                 T* it = end();
    00234                 for (; sized < count; ++sized)
    00235                 {
    00236                     // For non-primitive types, make sure we call the constructors of all the values.
    00237                     fm::Construct(it++);
    00238                 }
    00239             }
    00240             else
    00241             {
    00242                 sized = reserved;
    00243             }
    00244         }
    00245
    00249         void resize(size_t count, const T& value)
    00250         {
    00251             reserve(count);
    00252             T* it = end();
    00253
    00254             for (; sized < count; ++sized)
    00255             {
    00256                 // For non-primitive types, make sure we call the constructors of all the values.
    00257                 if (!PRIMITIVE)
    00258                 {
    00259                     fm::Construct(it++, value);
    00260                 }
    00261                 else
    00262                 {
    00263                     *(it++) = value;
    00264                 }
    00265             }
    00266         }
    00267
    00269         inline void clear() { reserve(0); }
    00270
    00275         void reserve(size_t count)
    00276         {
    00277             // Basic check for stupidly large allocations;
    00278             // basically all this is for is to catch (size_t)-1 calls
    00279             // in debug mode. Ensure release will optimize out this call!
    00280             FUAssert(count < INT_MAX, ;);
    00281             if (reserved != count)
    00282             {
    00283                 // For non-primitives, make sure we destroy all the values individually.
    00284                 if (PRIMITIVE)
    00285                 {
    00286                     if (sized > count) sized = count;
    00287                 }
    00288                 else
    00289                 {
    00290                     while (sized > count) pop_back();
    00291                 }
    00292
    00293                 // If we are reserving data, re-allocate a new buffer.
    00294                 T* newValues;
    00295                 if (count > 0)
    00296                 {
    00297                     newValues = (T*) fm::Allocate(count * sizeof(T));
    00298                     if (sized > 0)
    00299                     {
    00300                         memcpy(newValues, heapBuffer, sized * sizeof(T));
    00301                     }
    00302                 }
    00303                 else newValues = NULL;
    00304
    00305                 // Free the old buffer.
    00306                 if (heapBuffer != NULL)
    00307                 {
    00308                     fm::Release(heapBuffer);
    00309                 }
    00310                 heapBuffer = newValues;
    00311                 reserved = count;
    00312             }
    00313         }
    00314
    00318         inline size_t capacity() { return reserved; }
    00319         inline size_t capacity() const { return reserved; }
    00323         inline iterator begin() { return heapBuffer; }
    00324         inline const_iterator begin() const { return heapBuffer; }
    00328         inline iterator end() { return heapBuffer + sized; }
    00329         inline const_iterator end() const { return heapBuffer + sized; }
    00335         iterator insert(iterator it, const T& item)
    00336         {
    00337             FUAssert(it >= begin() && it <= end(), return it);
    00338             if (sized == reserved)
    00339             {
    00340                 size_t offset = it - begin();
    00341                 reserve(sized + (sized > 31 ? 32 : (sized+1)));
    00342                 it = begin() + offset;
    00343             }
    00344             if (it < end())
    00345             {
    00346                 memmove(it + 1, it, (end() - it) * sizeof(T));
    00347             }
    00348             if (!PRIMITIVE)
    00349             {
    00350                 fm::Construct(it, item);
    00351             }
    00352             else
    00353             {
    00354                 *it = item;
    00355             }
    00356             ++sized;
    00357             return it;
    00358         }
    00359
    00363         inline void insert(size_t index, const T& item) { insert(begin() + index, item); }
    00364
    00367         inline void push_back(const T& item) { insert(end(), item); }
    00368
    00373         inline void push_front(const T& item) { insert(begin(), item); }
    00374
    00376         void pop_back()
    00377         {
    00378             FUAssert(sized > 0, return);
    00379             if (!PRIMITIVE) (*(heapBuffer + sized - 1)).~T();
    00380             --sized;
    00381         }
    00382
    00386         inline void pop_front()
    00387         {
    00388             erase(begin());
    00389         }
    00390
    00395         template <typename _IT> inline void insert(iterator it, _IT first, _IT last)
    00396         {
    00397             size_t count = last - first;
    00398             insert(it, first, count);
    00399         }
    00400
    00405         inline void insert(iterator it, size_t count, const T& item, bool noInit=false)
    00406         {
    00407             if (count > 0)
    00408             {
    00409                 FUAssert(it >= begin() && it <= end(), return);
    00410                 if (sized + count > reserved)
    00411                 {
    00412                     size_t offset = it - begin();
    00413                     reserve(sized + count);
    00414                     it = begin() + offset;
    00415                 }
    00416                 if (it < end())
    00417                 {
    00418                     memmove(it + count, it, (end() - it) * sizeof(T));
    00419                 }
    00420                 sized += count;
    00421
    00422                 if (!noInit)
    00423                 {
    00424                     if (!PRIMITIVE)
    00425                     {
    00426                         do
    00427                         {
    00428                             fm::Construct(it++, item);
    00429                         }
    00430                         while (--count > 0);
    00431                     }
    00432                     else
    00433                     {
    00434                         do
    00435                         {
    00436                             *(it++) = item;
    00437                         }
    00438                         while (--count > 0);
    00439                     }
    00440                 }
    00441             }
    00442         }
    00443
    00448         inline void insert(size_t index, size_t count, const T& value) { insert(begin() + index, count, value); }
    00449
    00456         void insert(iterator it, const T* first, size_t count)
    00457         {
    00458             if (count > 0)
    00459             {
    00460                 FUAssert(it >= begin() && it <= end(), return);
    00461                 if (sized + count > reserved)
    00462                 {
    00463                     size_t offset = it - begin();
    00464                     reserve((sized + count - reserved) > 32 ? (sized + count) : (reserved + 32));
    00465                     it = begin() + offset;
    00466                 }
    00467                 if (it < end())
    00468                 {
    00469                     memmove(it + count, it, (end() - it) * sizeof(T));
    00470                 }
    00471                 sized += count;
    00472                 if (!PRIMITIVE)
    00473                 {
    00474                     do
    00475                     {
    00476                         fm::Construct(it++, (*first++));
    00477                     }
    00478                     while (--count > 0);
    00479                 }
    00480                 else
    00481                 {
    00482                     memcpy(it, first, count * sizeof(T));
    00483                 }
    00484             }
    00485         }
    00486
    00491         inline void insert(size_t index, const T* values, size_t count) { insert(begin() + index, values, count); }
    00492
    00495         T& front() { FUAssert(sized > 0,); return (*heapBuffer); }
    00496         const T& front() const { FUAssert(sized > 0,); return (*heapBuffer); }
    00500         T& back() { FUAssert(sized > 0,); return *(heapBuffer + sized - 1); }
    00501         const T& back() const { FUAssert(sized > 0,); return *(heapBuffer + sized - 1); }
    00506         T& at(size_t index) { FUAssert(index < sized,); return heapBuffer[index]; }
    00507         const T& at(size_t index) const { FUAssert(index < sized,); return heapBuffer[index]; }
    00508         template <class INTEGER> inline T& operator[](INTEGER index) { FUAssert((size_t) index < sized,); return heapBuffer[index]; }
    00509         template <class INTEGER> inline const T& operator[](INTEGER index) const { FUAssert((size_t) index < sized,); return heapBuffer[index]; }
    00514         bool operator==(const fm::vector<T,PRIMITIVE>& other) const
    00515         {
    00516             bool equals = sized == other.size();
    00517             const T* e = end();
    00518             for (const T* it = begin(),* it2 = other.begin(); it != e && equals; ++it, ++it2)
    00519             {
    00520                 equals = (*it) == (*it2);
    00521             }
    00522             return equals;
    00523         }
    00524
    00528         vector<T,PRIMITIVE>& operator =(const fm::vector<T,PRIMITIVE>& rhs)
    00529         {
    00530             if (this != &rhs)
    00531             {
    00532                 if (PRIMITIVE)
    00533                 {
    00534                     resize(rhs.size());
    00535                     memcpy(begin(), rhs.begin(), sizeof(T) * rhs.size());
    00536                 }
    00537                 else
    00538                 {
    00539                     reserve(rhs.size());
    00540                     clear();
    00541                     for (const_iterator it = rhs.begin(); it != rhs.end(); ++it)
    00542                     {
    00543                         push_back(*it);
    00544                     }
    00545                 }
    00546             }
    00547             return *this;
    00548         }
    00549     };
    00550 };
    00551
    00557 template <class T, bool PRIMITIVE>
    00558 inline bool IsEquivalent(const fm::vector<T,PRIMITIVE>& dl, const T* cl, size_t count)
    00559 {
    00560     if (dl.size() != count) return false;
    00561     bool equivalent = true;
    00562     for (size_t i = 0; i < count && equivalent; ++i)
    00563     {
    00564          equivalent = IsEquivalent(dl.at(i), cl[i]);
    00565     }
    00566     return equivalent;
    00567 }
    00568
    00575 template <class T>
    00576 inline bool IsEquivalent(const T* al, size_t acount, const T* bl, size_t bcount)
    00577 {
    00578     if (acount != bcount) return false;
    00579     bool equivalent = true;
    00580     for (size_t i = 0; i < acount && equivalent; ++i)
    00581     {
    00582          equivalent = IsEquivalent(al[i], bl[i]);
    00583     }
    00584     return equivalent;
    00585 }
    00586
    00587 #ifdef WIN32
    00588 #pragma warning(default:4127)
    00589 #endif //WIN32
    00590 #endif // _FM_ARRAY_H_