1 /* 2 * Copyright 2003, Ingo Weinhold, ingo_weinhold@gmx.de. 3 * All rights reserved. Distributed under the terms of the MIT license. 4 */ 5 #ifndef LIST_H 6 #define LIST_H 7 8 #include <new> 9 #include <stdlib.h> 10 #include <string.h> 11 12 #include <SupportDefs.h> 13 14 template<typename ITEM> 15 class DefaultDefaultItemCreator { 16 public: 17 static inline ITEM GetItem() { return ITEM(0); } 18 }; 19 20 /*! 21 \class List 22 \brief A generic list implementation. 23 */ 24 template<typename ITEM, 25 typename DEFAULT_ITEM_SUPPLIER = DefaultDefaultItemCreator<ITEM> > 26 class List { 27 public: 28 typedef ITEM item_t; 29 typedef List list_t; 30 31 private: 32 static item_t sDefaultItem; 33 static const size_t kDefaultChunkSize = 10; 34 static const size_t kMaximalChunkSize = 1024 * 1024; 35 36 public: 37 List(size_t chunkSize = kDefaultChunkSize); 38 ~List(); 39 40 inline const item_t &GetDefaultItem() const; 41 inline item_t &GetDefaultItem(); 42 43 bool AddItem(const item_t &item, int32 index); 44 bool AddItem(const item_t &item); 45 // bool AddList(list_t *list, int32 index); 46 // bool AddList(list_t *list); 47 48 bool RemoveItem(const item_t &item); 49 bool RemoveItem(int32 index); 50 51 bool ReplaceItem(int32 index, const item_t &item); 52 53 bool MoveItem(int32 oldIndex, int32 newIndex); 54 55 void MakeEmpty(); 56 57 int32 CountItems() const; 58 bool IsEmpty() const; 59 const item_t &ItemAt(int32 index) const; 60 item_t &ItemAt(int32 index); 61 const item_t *Items() const; 62 int32 IndexOf(const item_t &item) const; 63 bool HasItem(const item_t &item) const; 64 65 // debugging 66 int32 GetCapacity() const { return fCapacity; } 67 68 private: 69 inline static void _MoveItems(item_t* items, int32 offset, int32 count); 70 bool _Resize(size_t count); 71 72 private: 73 size_t fCapacity; 74 size_t fChunkSize; 75 int32 fItemCount; 76 item_t *fItems; 77 }; 78 79 // sDefaultItem 80 template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 81 typename List<ITEM, DEFAULT_ITEM_SUPPLIER>::item_t 82 List<ITEM, DEFAULT_ITEM_SUPPLIER>::sDefaultItem( 83 DEFAULT_ITEM_SUPPLIER::GetItem()); 84 85 // constructor 86 template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 87 List<ITEM, DEFAULT_ITEM_SUPPLIER>::List(size_t chunkSize) 88 : fCapacity(0), 89 fChunkSize(chunkSize), 90 fItemCount(0), 91 fItems(NULL) 92 { 93 if (fChunkSize == 0 || fChunkSize > kMaximalChunkSize) 94 fChunkSize = kDefaultChunkSize; 95 _Resize(0); 96 } 97 98 // destructor 99 template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 100 List<ITEM, DEFAULT_ITEM_SUPPLIER>::~List() 101 { 102 MakeEmpty(); 103 free(fItems); 104 } 105 106 // GetDefaultItem 107 template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 108 inline 109 const typename List<ITEM, DEFAULT_ITEM_SUPPLIER>::item_t & 110 List<ITEM, DEFAULT_ITEM_SUPPLIER>::GetDefaultItem() const 111 { 112 return sDefaultItem; 113 } 114 115 // GetDefaultItem 116 template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 117 inline 118 typename List<ITEM, DEFAULT_ITEM_SUPPLIER>::item_t & 119 List<ITEM, DEFAULT_ITEM_SUPPLIER>::GetDefaultItem() 120 { 121 return sDefaultItem; 122 } 123 124 // _MoveItems 125 template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 126 inline 127 void 128 List<ITEM, DEFAULT_ITEM_SUPPLIER>::_MoveItems(item_t* items, int32 offset, int32 count) 129 { 130 if (count > 0 && offset != 0) 131 memmove(items + offset, items, count * sizeof(item_t)); 132 } 133 134 // AddItem 135 template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 136 bool 137 List<ITEM, DEFAULT_ITEM_SUPPLIER>::AddItem(const item_t &item, int32 index) 138 { 139 bool result = (index >= 0 && index <= fItemCount 140 && _Resize(fItemCount + 1)); 141 if (result) { 142 _MoveItems(fItems + index, 1, fItemCount - index - 1); 143 new(fItems + index) item_t(item); 144 } 145 return result; 146 } 147 148 // AddItem 149 template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 150 bool 151 List<ITEM, DEFAULT_ITEM_SUPPLIER>::AddItem(const item_t &item) 152 { 153 bool result = true; 154 if ((int32)fCapacity > fItemCount) { 155 new(fItems + fItemCount) item_t(item); 156 fItemCount++; 157 } else { 158 if ((result = _Resize(fItemCount + 1))) 159 new(fItems + (fItemCount - 1)) item_t(item); 160 } 161 return result; 162 } 163 164 // These don't use the copy constructor! 165 /* 166 // AddList 167 template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 168 bool 169 List<ITEM, DEFAULT_ITEM_SUPPLIER>::AddList(list_t *list, int32 index) 170 { 171 bool result = (list && index >= 0 && index <= fItemCount); 172 if (result && list->fItemCount > 0) { 173 int32 count = list->fItemCount; 174 result = _Resize(fItemCount + count); 175 if (result) { 176 _MoveItems(fItems + index, count, fItemCount - index - count); 177 memcpy(fItems + index, list->fItems, 178 list->fItemCount * sizeof(item_t)); 179 } 180 } 181 return result; 182 } 183 184 // AddList 185 template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 186 bool 187 List<ITEM, DEFAULT_ITEM_SUPPLIER>::AddList(list_t *list) 188 { 189 bool result = (list); 190 if (result && list->fItemCount > 0) { 191 int32 index = fItemCount; 192 int32 count = list->fItemCount; 193 result = _Resize(fItemCount + count); 194 if (result) { 195 memcpy(fItems + index, list->fItems, 196 list->fItemCount * sizeof(item_t)); 197 } 198 } 199 return result; 200 } 201 */ 202 203 // RemoveItem 204 template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 205 bool 206 List<ITEM, DEFAULT_ITEM_SUPPLIER>::RemoveItem(const item_t &item) 207 { 208 int32 index = IndexOf(item); 209 bool result = (index >= 0); 210 if (result) 211 RemoveItem(index); 212 return result; 213 } 214 215 // RemoveItem 216 template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 217 bool 218 List<ITEM, DEFAULT_ITEM_SUPPLIER>::RemoveItem(int32 index) 219 { 220 if (index >= 0 && index < fItemCount) { 221 fItems[index].~item_t(); 222 _MoveItems(fItems + index + 1, -1, fItemCount - index - 1); 223 _Resize(fItemCount - 1); 224 return true; 225 } 226 return false; 227 } 228 229 // ReplaceItem 230 template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 231 bool 232 List<ITEM, DEFAULT_ITEM_SUPPLIER>::ReplaceItem(int32 index, const item_t &item) 233 { 234 if (index >= 0 && index < fItemCount) { 235 fItems[index] = item; 236 return true; 237 } 238 return false; 239 } 240 241 // MoveItem 242 template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 243 bool 244 List<ITEM, DEFAULT_ITEM_SUPPLIER>::MoveItem(int32 oldIndex, int32 newIndex) 245 { 246 if (oldIndex >= 0 && oldIndex < fItemCount 247 && newIndex >= 0 && newIndex <= fItemCount) { 248 if (oldIndex < newIndex - 1) { 249 item_t item = fItems[oldIndex]; 250 _MoveItems(fItems + oldIndex + 1, -1, newIndex - oldIndex - 1); 251 fItems[newIndex] = item; 252 } else if (oldIndex > newIndex) { 253 item_t item = fItems[oldIndex]; 254 _MoveItems(fItems + newIndex, 1, oldIndex - newIndex); 255 fItems[newIndex] = item; 256 } 257 return true; 258 } 259 return false; 260 } 261 262 // MakeEmpty 263 template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 264 void 265 List<ITEM, DEFAULT_ITEM_SUPPLIER>::MakeEmpty() 266 { 267 for (int32 i = 0; i < fItemCount; i++) 268 fItems[i].~item_t(); 269 _Resize(0); 270 } 271 272 // CountItems 273 template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 274 int32 275 List<ITEM, DEFAULT_ITEM_SUPPLIER>::CountItems() const 276 { 277 return fItemCount; 278 } 279 280 // IsEmpty 281 template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 282 bool 283 List<ITEM, DEFAULT_ITEM_SUPPLIER>::IsEmpty() const 284 { 285 return (fItemCount == 0); 286 } 287 288 // ItemAt 289 template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 290 const typename List<ITEM, DEFAULT_ITEM_SUPPLIER>::item_t & 291 List<ITEM, DEFAULT_ITEM_SUPPLIER>::ItemAt(int32 index) const 292 { 293 if (index >= 0 && index < fItemCount) 294 return fItems[index]; 295 return sDefaultItem; 296 } 297 298 // ItemAt 299 template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 300 typename List<ITEM, DEFAULT_ITEM_SUPPLIER>::item_t & 301 List<ITEM, DEFAULT_ITEM_SUPPLIER>::ItemAt(int32 index) 302 { 303 if (index >= 0 && index < fItemCount) 304 return fItems[index]; 305 return sDefaultItem; 306 } 307 308 // Items 309 template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 310 const typename List<ITEM, DEFAULT_ITEM_SUPPLIER>::item_t * 311 List<ITEM, DEFAULT_ITEM_SUPPLIER>::Items() const 312 { 313 return fItems; 314 } 315 316 // IndexOf 317 template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 318 int32 319 List<ITEM, DEFAULT_ITEM_SUPPLIER>::IndexOf(const item_t &item) const 320 { 321 for (int32 i = 0; i < fItemCount; i++) { 322 if (fItems[i] == item) 323 return i; 324 } 325 return -1; 326 } 327 328 // HasItem 329 template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 330 bool 331 List<ITEM, DEFAULT_ITEM_SUPPLIER>::HasItem(const item_t &item) const 332 { 333 return (IndexOf(item) >= 0); 334 } 335 336 // _Resize 337 template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 338 bool 339 List<ITEM, DEFAULT_ITEM_SUPPLIER>::_Resize(size_t count) 340 { 341 bool result = true; 342 // calculate the new capacity 343 int32 newSize = count; 344 if (newSize <= 0) 345 newSize = 1; 346 newSize = ((newSize - 1) / fChunkSize + 1) * fChunkSize; 347 // resize if necessary 348 if ((size_t)newSize != fCapacity) { 349 item_t* newItems 350 = (item_t*)realloc(fItems, newSize * sizeof(item_t)); 351 if (newItems) { 352 fItems = newItems; 353 fCapacity = newSize; 354 } else 355 result = false; 356 } 357 if (result) 358 fItemCount = count; 359 return result; 360 } 361 362 #endif // LIST_H 363