00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020 #ifndef COIN_SBLIST_H
00021 #define COIN_SBLIST_H
00022
00023 #include <Inventor/SbBasic.h>
00024 #include <assert.h>
00025 #include <stddef.h>
00026
00027
00028
00029
00030
00031
00032
00033 template <class Type>
00034 class COIN_DLL_API SbList {
00035
00036
00037
00038 enum { DEFAULTSIZE = 4 };
00039
00040 public:
00041
00042 SbList(const int sizehint = DEFAULTSIZE)
00043 : itembuffersize(DEFAULTSIZE), numitems(0), itembuffer(builtinbuffer) {
00044 if (sizehint > DEFAULTSIZE) this->grow(sizehint);
00045 }
00046
00047 SbList(const SbList<Type> & l)
00048 : itembuffersize(DEFAULTSIZE), numitems(0), itembuffer(builtinbuffer) {
00049 this->copy(l);
00050 }
00051
00052 ~SbList() {
00053 if (this->itembuffer != builtinbuffer) delete[] this->itembuffer;
00054 }
00055
00056 void copy(const SbList<Type> & l) {
00057 if (this == &l) return;
00058 const int n = l.numitems;
00059 this->expand(n);
00060 for (int i = 0; i < n; i++) this->itembuffer[i] = l.itembuffer[i];
00061 }
00062
00063 SbList <Type> & operator=(const SbList<Type> & l) {
00064 this->copy(l);
00065 return *this;
00066 }
00067
00068 void fit(void) {
00069 const int items = this->numitems;
00070
00071 if (items < this->itembuffersize) {
00072 Type * newitembuffer = this->builtinbuffer;
00073 if (items > DEFAULTSIZE) newitembuffer = new Type[items];
00074
00075 if (newitembuffer != this->itembuffer) {
00076 for (int i = 0; i < items; i++) newitembuffer[i] = this->itembuffer[i];
00077 }
00078
00079 if (this->itembuffer != this->builtinbuffer) delete[] this->itembuffer;
00080 this->itembuffer = newitembuffer;
00081 this->itembuffersize = items > DEFAULTSIZE ? items : DEFAULTSIZE;
00082 }
00083 }
00084
00085 void append(const Type item) {
00086 if (this->numitems == this->itembuffersize) this->grow();
00087 this->itembuffer[this->numitems++] = item;
00088 }
00089
00090 int find(const Type item) const {
00091 for (int i = 0; i < this->numitems; i++)
00092 if (this->itembuffer[i] == item) return i;
00093 return -1;
00094 }
00095
00096 void insert(const Type item, const int insertbefore) {
00097 #ifdef COIN_EXTRA_DEBUG
00098 assert(insertbefore >= 0 && insertbefore <= this->numitems);
00099 #endif // COIN_EXTRA_DEBUG
00100 if (this->numitems == this->itembuffersize) this->grow();
00101
00102 for (int i = this->numitems; i > insertbefore; i--)
00103 this->itembuffer[i] = this->itembuffer[i-1];
00104 this->itembuffer[insertbefore] = item;
00105 this->numitems++;
00106 }
00107
00108 void removeItem(const Type item) {
00109 int idx = this->find(item);
00110 #ifdef COIN_EXTRA_DEBUG
00111 assert(idx != -1);
00112 #endif // COIN_EXTRA_DEBUG
00113 this->remove(idx);
00114 }
00115
00116 void remove(const int index) {
00117 #ifdef COIN_EXTRA_DEBUG
00118 assert(index >= 0 && index < this->numitems);
00119 #endif // COIN_EXTRA_DEBUG
00120 this->numitems--;
00121 for (int i = index; i < this->numitems; i++)
00122 this->itembuffer[i] = this->itembuffer[i + 1];
00123 }
00124
00125 void removeFast(const int index) {
00126 #ifdef COIN_EXTRA_DEBUG
00127 assert(index >= 0 && index < this->numitems);
00128 #endif // COIN_EXTRA_DEBUG
00129 this->itembuffer[index] = this->itembuffer[--this->numitems];
00130 }
00131
00132 int getLength(void) const {
00133 return this->numitems;
00134 }
00135
00136 void truncate(const int length, const int fit = 0) {
00137 #ifdef COIN_EXTRA_DEBUG
00138 assert(length <= this->numitems);
00139 #endif // COIN_EXTRA_DEBUG
00140 this->numitems = length;
00141 if (fit) this->fit();
00142 }
00143
00144 void push(const Type item) {
00145 this->append(item);
00146 }
00147
00148 Type pop(void) {
00149 #ifdef COIN_EXTRA_DEBUG
00150 assert(this->numitems > 0);
00151 #endif // COIN_EXTRA_DEBUG
00152 return this->itembuffer[--this->numitems];
00153 }
00154
00155 const Type * getArrayPtr(const int start = 0) const {
00156 return &this->itembuffer[start];
00157 }
00158
00159 Type operator[](const int index) const {
00160 #ifdef COIN_EXTRA_DEBUG
00161 assert(index >= 0 && index < this->numitems);
00162 #endif // COIN_EXTRA_DEBUG
00163 return this->itembuffer[index];
00164 }
00165
00166 Type & operator[](const int index) {
00167 #ifdef COIN_EXTRA_DEBUG
00168 assert(index >= 0 && index < this->numitems);
00169 #endif // COIN_EXTRA_DEBUG
00170 return this->itembuffer[index];
00171 }
00172
00173 int operator==(const SbList<Type> & l) const {
00174 if (this == &l) return TRUE;
00175 if (this->numitems != l.numitems) return FALSE;
00176 for (int i = 0; i < this->numitems; i++)
00177 if (this->itembuffer[i] != l.itembuffer[i]) return FALSE;
00178 return TRUE;
00179 }
00180
00181 int operator!=(const SbList<Type> & l) const {
00182 return !(*this == l);
00183 }
00184
00185 protected:
00186
00187 void expand(const int size) {
00188 this->grow(size);
00189 this->numitems = size;
00190 }
00191
00192 int getArraySize(void) const {
00193 return this->itembuffersize;
00194 }
00195
00196 private:
00197 void grow(const int size = -1) {
00198
00199 if (size == -1) this->itembuffersize <<= 1;
00200 else if (size <= this->itembuffersize) return;
00201 else { this->itembuffersize = size; }
00202
00203 Type * newbuffer = new Type[this->itembuffersize];
00204 const int n = this->numitems;
00205 for (int i = 0; i < n; i++) newbuffer[i] = this->itembuffer[i];
00206 if (this->itembuffer != this->builtinbuffer) delete[] this->itembuffer;
00207 this->itembuffer = newbuffer;
00208 }
00209
00210 int itembuffersize;
00211 int numitems;
00212 Type * itembuffer;
00213 Type builtinbuffer[DEFAULTSIZE];
00214 };
00215
00216 #endif // !COIN_SBLIST_H