1 // List.h 2 // 3 // Copyright (c) 2003, Ingo Weinhold (bonefish@cs.tu-berlin.de) 4 // 5 // Permission is hereby granted, free of charge, to any person obtaining a 6 // copy of this software and associated documentation files (the "Software"), 7 // to deal in the Software without restriction, including without limitation 8 // the rights to use, copy, modify, merge, publish, distribute, sublicense, 9 // and/or sell copies of the Software, and to permit persons to whom the 10 // Software is furnished to do so, subject to the following conditions: 11 // 12 // The above copyright notice and this permission notice shall be included in 13 // all copies or substantial portions of the Software. 14 // 15 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 16 // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 17 // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL 18 // THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 19 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING 20 // FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER 21 // DEALINGS IN THE SOFTWARE. 22 // 23 // Except as contained in this notice, the name of a copyright holder shall 24 // not be used in advertising or otherwise to promote the sale, use or other 25 // dealings in this Software without prior written authorization of the 26 // copyright holder. 27 28 #ifndef LIST_H 29 #define LIST_H 30 31 #include <new> 32 #include <stdlib.h> 33 #include <string.h> 34 35 #include <SupportDefs.h> 36 37 template<typename ITEM> 38 class DefaultDefaultItemCreator { 39 public: 40 static inline ITEM GetItem() { return ITEM(0); } 41 }; 42 43 /*! 44 \class List 45 \brief A generic list implementation. 46 */ 47 template<typename ITEM, 48 typename DEFAULT_ITEM_SUPPLIER = DefaultDefaultItemCreator<ITEM> > 49 class List { 50 public: 51 typedef ITEM item_t; 52 typedef List list_t; 53 54 private: 55 static item_t sDefaultItem; 56 static const size_t kDefaultChunkSize = 10; 57 static const size_t kMaximalChunkSize = 1024 * 1024; 58 59 public: 60 List(size_t chunkSize = kDefaultChunkSize); 61 ~List(); 62 63 inline const item_t &GetDefaultItem() const; 64 inline item_t &GetDefaultItem(); 65 66 bool AddItem(const item_t &item, int32 index); 67 bool AddItem(const item_t &item); 68 // bool AddList(list_t *list, int32 index); 69 // bool AddList(list_t *list); 70 71 bool RemoveItem(const item_t &item); 72 bool RemoveItem(int32 index); 73 74 bool ReplaceItem(int32 index, const item_t &item); 75 76 bool MoveItem(int32 oldIndex, int32 newIndex); 77 78 void MakeEmpty(); 79 80 int32 CountItems() const; 81 bool IsEmpty() const; 82 const item_t &ItemAt(int32 index) const; 83 item_t &ItemAt(int32 index); 84 const item_t *Items() const; 85 int32 IndexOf(const item_t &item) const; 86 bool HasItem(const item_t &item) const; 87 88 // debugging 89 int32 GetCapacity() const { return fCapacity; } 90 91 private: 92 inline static void _MoveItems(item_t* items, int32 offset, int32 count); 93 bool _Resize(size_t count); 94 95 private: 96 size_t fCapacity; 97 size_t fChunkSize; 98 int32 fItemCount; 99 item_t *fItems; 100 }; 101 102 // sDefaultItem 103 template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 104 typename List<ITEM, DEFAULT_ITEM_SUPPLIER>::item_t 105 List<ITEM, DEFAULT_ITEM_SUPPLIER>::sDefaultItem( 106 DEFAULT_ITEM_SUPPLIER::GetItem()); 107 108 // constructor 109 template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 110 List<ITEM, DEFAULT_ITEM_SUPPLIER>::List(size_t chunkSize) 111 : fCapacity(0), 112 fChunkSize(chunkSize), 113 fItemCount(0), 114 fItems(NULL) 115 { 116 if (fChunkSize == 0 || fChunkSize > kMaximalChunkSize) 117 fChunkSize = kDefaultChunkSize; 118 _Resize(0); 119 } 120 121 // destructor 122 template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 123 List<ITEM, DEFAULT_ITEM_SUPPLIER>::~List() 124 { 125 MakeEmpty(); 126 free(fItems); 127 } 128 129 // GetDefaultItem 130 template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 131 inline 132 const typename List<ITEM, DEFAULT_ITEM_SUPPLIER>::item_t & 133 List<ITEM, DEFAULT_ITEM_SUPPLIER>::GetDefaultItem() const 134 { 135 return sDefaultItem; 136 } 137 138 // GetDefaultItem 139 template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 140 inline 141 typename List<ITEM, DEFAULT_ITEM_SUPPLIER>::item_t & 142 List<ITEM, DEFAULT_ITEM_SUPPLIER>::GetDefaultItem() 143 { 144 return sDefaultItem; 145 } 146 147 // _MoveItems 148 template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 149 inline 150 void 151 List<ITEM, DEFAULT_ITEM_SUPPLIER>::_MoveItems(item_t* items, int32 offset, int32 count) 152 { 153 if (count > 0 && offset != 0) 154 memmove(items + offset, items, count * sizeof(item_t)); 155 } 156 157 // AddItem 158 template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 159 bool 160 List<ITEM, DEFAULT_ITEM_SUPPLIER>::AddItem(const item_t &item, int32 index) 161 { 162 bool result = (index >= 0 && index <= fItemCount 163 && _Resize(fItemCount + 1)); 164 if (result) { 165 _MoveItems(fItems + index, 1, fItemCount - index - 1); 166 new(fItems + index) item_t(item); 167 } 168 return result; 169 } 170 171 // AddItem 172 template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 173 bool 174 List<ITEM, DEFAULT_ITEM_SUPPLIER>::AddItem(const item_t &item) 175 { 176 bool result = true; 177 if ((int32)fCapacity > fItemCount) { 178 new(fItems + fItemCount) item_t(item); 179 fItemCount++; 180 } else { 181 if ((result = _Resize(fItemCount + 1))) 182 new(fItems + (fItemCount - 1)) item_t(item); 183 } 184 return result; 185 } 186 187 // These don't use the copy constructor! 188 /* 189 // AddList 190 template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 191 bool 192 List<ITEM, DEFAULT_ITEM_SUPPLIER>::AddList(list_t *list, int32 index) 193 { 194 bool result = (list && index >= 0 && index <= fItemCount); 195 if (result && list->fItemCount > 0) { 196 int32 count = list->fItemCount; 197 result = _Resize(fItemCount + count); 198 if (result) { 199 _MoveItems(fItems + index, count, fItemCount - index - count); 200 memcpy(fItems + index, list->fItems, 201 list->fItemCount * sizeof(item_t)); 202 } 203 } 204 return result; 205 } 206 207 // AddList 208 template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 209 bool 210 List<ITEM, DEFAULT_ITEM_SUPPLIER>::AddList(list_t *list) 211 { 212 bool result = (list); 213 if (result && list->fItemCount > 0) { 214 int32 index = fItemCount; 215 int32 count = list->fItemCount; 216 result = _Resize(fItemCount + count); 217 if (result) { 218 memcpy(fItems + index, list->fItems, 219 list->fItemCount * sizeof(item_t)); 220 } 221 } 222 return result; 223 } 224 */ 225 226 // RemoveItem 227 template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 228 bool 229 List<ITEM, DEFAULT_ITEM_SUPPLIER>::RemoveItem(const item_t &item) 230 { 231 int32 index = IndexOf(item); 232 bool result = (index >= 0); 233 if (result) 234 RemoveItem(index); 235 return result; 236 } 237 238 // RemoveItem 239 template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 240 bool 241 List<ITEM, DEFAULT_ITEM_SUPPLIER>::RemoveItem(int32 index) 242 { 243 if (index >= 0 && index < fItemCount) { 244 fItems[index].~item_t(); 245 _MoveItems(fItems + index + 1, -1, fItemCount - index - 1); 246 _Resize(fItemCount - 1); 247 return true; 248 } 249 return false; 250 } 251 252 // ReplaceItem 253 template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 254 bool 255 List<ITEM, DEFAULT_ITEM_SUPPLIER>::ReplaceItem(int32 index, const item_t &item) 256 { 257 if (index >= 0 && index < fItemCount) { 258 fItems[index] = item; 259 return true; 260 } 261 return false; 262 } 263 264 // MoveItem 265 template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 266 bool 267 List<ITEM, DEFAULT_ITEM_SUPPLIER>::MoveItem(int32 oldIndex, int32 newIndex) 268 { 269 if (oldIndex >= 0 && oldIndex < fItemCount 270 && newIndex >= 0 && newIndex <= fItemCount) { 271 if (oldIndex < newIndex - 1) { 272 item_t item = fItems[oldIndex]; 273 _MoveItems(fItems + oldIndex + 1, -1, newIndex - oldIndex - 1); 274 fItems[newIndex] = item; 275 } else if (oldIndex > newIndex) { 276 item_t item = fItems[oldIndex]; 277 _MoveItems(fItems + newIndex, 1, oldIndex - newIndex); 278 fItems[newIndex] = item; 279 } 280 return true; 281 } 282 return false; 283 } 284 285 // MakeEmpty 286 template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 287 void 288 List<ITEM, DEFAULT_ITEM_SUPPLIER>::MakeEmpty() 289 { 290 for (int32 i = 0; i < fItemCount; i++) 291 fItems[i].~item_t(); 292 _Resize(0); 293 } 294 295 // CountItems 296 template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 297 int32 298 List<ITEM, DEFAULT_ITEM_SUPPLIER>::CountItems() const 299 { 300 return fItemCount; 301 } 302 303 // IsEmpty 304 template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 305 bool 306 List<ITEM, DEFAULT_ITEM_SUPPLIER>::IsEmpty() const 307 { 308 return (fItemCount == 0); 309 } 310 311 // ItemAt 312 template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 313 const typename List<ITEM, DEFAULT_ITEM_SUPPLIER>::item_t & 314 List<ITEM, DEFAULT_ITEM_SUPPLIER>::ItemAt(int32 index) const 315 { 316 if (index >= 0 && index < fItemCount) 317 return fItems[index]; 318 return sDefaultItem; 319 } 320 321 // ItemAt 322 template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 323 typename List<ITEM, DEFAULT_ITEM_SUPPLIER>::item_t & 324 List<ITEM, DEFAULT_ITEM_SUPPLIER>::ItemAt(int32 index) 325 { 326 if (index >= 0 && index < fItemCount) 327 return fItems[index]; 328 return sDefaultItem; 329 } 330 331 // Items 332 template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 333 const typename List<ITEM, DEFAULT_ITEM_SUPPLIER>::item_t * 334 List<ITEM, DEFAULT_ITEM_SUPPLIER>::Items() const 335 { 336 return fItems; 337 } 338 339 // IndexOf 340 template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 341 int32 342 List<ITEM, DEFAULT_ITEM_SUPPLIER>::IndexOf(const item_t &item) const 343 { 344 for (int32 i = 0; i < fItemCount; i++) { 345 if (fItems[i] == item) 346 return i; 347 } 348 return -1; 349 } 350 351 // HasItem 352 template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 353 bool 354 List<ITEM, DEFAULT_ITEM_SUPPLIER>::HasItem(const item_t &item) const 355 { 356 return (IndexOf(item) >= 0); 357 } 358 359 // _Resize 360 template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 361 bool 362 List<ITEM, DEFAULT_ITEM_SUPPLIER>::_Resize(size_t count) 363 { 364 bool result = true; 365 // calculate the new capacity 366 int32 newSize = count; 367 if (newSize <= 0) 368 newSize = 1; 369 newSize = ((newSize - 1) / fChunkSize + 1) * fChunkSize; 370 // resize if necessary 371 if ((size_t)newSize != fCapacity) { 372 item_t* newItems 373 = (item_t*)realloc(fItems, newSize * sizeof(item_t)); 374 if (newItems) { 375 fItems = newItems; 376 fCapacity = newSize; 377 } else 378 result = false; 379 } 380 if (result) 381 fItemCount = count; 382 return result; 383 } 384 385 #endif // LIST_H 386