1 /* 2 OpenLieroX 3 4 fast fixed vector class 5 6 created 27-05-2008 by Albert Zeyer 7 code under LGPL 8 */ 9 10 #ifndef __FASTVECTOR_H__ 11 #define __FASTVECTOR_H__ 12 13 #include "Iterator.h" 14 #include "Event.h" 15 #include "MathLib.h" 16 17 18 /* 19 _Obj has to provide these functions: 20 bool isUsed() const; 21 void setUnused(); 22 Event<> onInvalidation; 23 24 also, FastVector only works correct if all new objects are requested from it, 25 so you should not call operator delete on getNewObj() return value or some other stupid thing 26 */ 27 template < typename _Obj, int SIZE > 28 class FastVector { 29 protected: 30 _Obj m_objects[SIZE]; 31 int m_firstUnused; 32 int m_lastUsed; 33 findNewFirstUnused()34 void findNewFirstUnused() { 35 while(true) { 36 m_firstUnused++; 37 if(m_firstUnused > m_lastUsed) break; 38 if(m_firstUnused >= SIZE) break; 39 if(!isUsed(m_firstUnused)) break; 40 } 41 } 42 findNewLastUsed()43 void findNewLastUsed() { 44 while(true) { 45 m_lastUsed--; 46 if(m_lastUsed < 0) break; 47 if(m_lastUsed < m_firstUnused) break; 48 if(isUsed(m_lastUsed)) break; 49 } 50 } 51 init()52 void init() { 53 for(int i = 0; i < SIZE; i++) { 54 m_objects[i].setUnused(); 55 m_objects[i].onInvalidation.handler() = getEventHandler(this, &FastVector::onObjectInvalidation); 56 } 57 } 58 onObjectInvalidation(EventData data)59 void onObjectInvalidation(EventData data) { 60 int i = (int)((_Obj*)data.owner - &m_objects[0]); 61 refreshObj(i); 62 } 63 64 public: FastVector()65 FastVector() : m_firstUnused(0), m_lastUsed(-1) { init(); } 66 firstUnused()67 int firstUnused() { return m_firstUnused; } lastUsed()68 int lastUsed() { return m_lastUsed; } isUsed(int index)69 bool isUsed(int index) const { return m_objects[index].isUsed(); } 70 _Obj& operator[](int index) { return m_objects[index]; } 71 clear()72 void clear() { 73 for(int i = 0; i <= m_lastUsed; i++) 74 m_objects[i].setUnused(); 75 m_firstUnused = 0; 76 m_lastUsed = -1; 77 } 78 size()79 size_t size() { 80 size_t c = 0; 81 for(int i = 0; i <= m_lastUsed; i++) 82 if(m_objects[i].isUsed()) c++; 83 return c; 84 } 85 86 // this function assumes, that the returned object is used after getNewObj()87 _Obj* getNewObj() { 88 if(m_firstUnused >= SIZE) return NULL; 89 90 int newObj = m_firstUnused; 91 if(newObj > m_lastUsed) m_lastUsed = newObj; 92 findNewFirstUnused(); 93 return &m_objects[newObj]; 94 } 95 96 // call this when you manually have setUnused() an obj refreshObj(int index)97 void refreshObj(int index) { 98 if(!isUsed(index)) { 99 if(index < m_firstUnused) m_firstUnused = index; 100 if(index >= m_lastUsed) findNewLastUsed(); 101 } 102 } 103 104 class Iterator : public ::Iterator<_Obj*> { 105 private: 106 int m_index; 107 FastVector& m_parent; 108 public: m_parent(parent)109 Iterator(FastVector& parent, int index = 0) : m_parent(parent) { 110 m_index = CLAMP(index, 0, SIZE) - 1; 111 next(); 112 } copy()113 Iterator* copy() const { return new Iterator(m_parent, m_index); } 114 next()115 void next() { 116 ++m_index; 117 while (m_index < SIZE) { 118 if(m_parent.isUsed(m_index)) 119 break; 120 121 ++m_index; 122 123 if(m_index > m_parent.m_lastUsed) 124 m_index = SIZE; 125 } 126 } 127 bool operator==(const ::Iterator<_Obj*>& other) const { return m_index == ((Iterator*)&other)->m_index; } 128 isValid()129 bool isValid() { return m_index < SIZE; } get()130 _Obj* get() { return &m_parent[m_index]; } 131 }; 132 begin()133 typename ::Iterator<_Obj*>::Ref begin() { return new Iterator(*this, 0); } 134 135 FastVector & operator = ( const FastVector & v ) { 136 // Fast copy routine ( _Obj should provide sane operator= ) 137 for(int i = 0; i < SIZE; i++) 138 { 139 if( v.m_objects[i].isUsed() ) 140 { 141 m_objects[i] = v.m_objects[i]; 142 m_objects[i].onInvalidation.handler() = getEventHandler(this, &FastVector::onObjectInvalidation); 143 } 144 else 145 m_objects[i].setUnused(); 146 } 147 m_firstUnused = v.m_firstUnused; 148 m_lastUsed = v.m_lastUsed; 149 return *this; 150 } 151 }; 152 153 #endif 154