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 14template<typename ITEM> 15class DefaultDefaultItemCreator { 16public: 17 static inline ITEM GetItem() { return ITEM(0); } 18}; 19 20/*! 21 \class List 22 \brief A generic list implementation. 23*/ 24template<typename ITEM, 25 typename DEFAULT_ITEM_SUPPLIER = DefaultDefaultItemCreator<ITEM> > 26class List { 27public: 28 typedef ITEM item_t; 29 typedef List list_t; 30 31private: 32 static item_t sDefaultItem; 33 static const size_t kDefaultChunkSize = 10; 34 static const size_t kMaximalChunkSize = 1024 * 1024; 35 36public: 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 68private: 69 inline static void _MoveItems(item_t* items, int32 offset, int32 count); 70 bool _Resize(size_t count); 71 72private: 73 size_t fCapacity; 74 size_t fChunkSize; 75 int32 fItemCount; 76 item_t *fItems; 77}; 78 79// sDefaultItem 80template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 81typename List<ITEM, DEFAULT_ITEM_SUPPLIER>::item_t 82 List<ITEM, DEFAULT_ITEM_SUPPLIER>::sDefaultItem( 83 DEFAULT_ITEM_SUPPLIER::GetItem()); 84 85// constructor 86template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 87List<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 99template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 100List<ITEM, DEFAULT_ITEM_SUPPLIER>::~List() 101{ 102 MakeEmpty(); 103 free(fItems); 104} 105 106// GetDefaultItem 107template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 108inline 109const typename List<ITEM, DEFAULT_ITEM_SUPPLIER>::item_t & 110List<ITEM, DEFAULT_ITEM_SUPPLIER>::GetDefaultItem() const 111{ 112 return sDefaultItem; 113} 114 115// GetDefaultItem 116template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 117inline 118typename List<ITEM, DEFAULT_ITEM_SUPPLIER>::item_t & 119List<ITEM, DEFAULT_ITEM_SUPPLIER>::GetDefaultItem() 120{ 121 return sDefaultItem; 122} 123 124// _MoveItems 125template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 126inline 127void 128List<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 135template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 136bool 137List<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 149template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 150bool 151List<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 167template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 168bool 169List<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 185template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 186bool 187List<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 204template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 205bool 206List<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 216template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 217bool 218List<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 230template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 231bool 232List<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 242template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 243bool 244List<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 263template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 264void 265List<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 273template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 274int32 275List<ITEM, DEFAULT_ITEM_SUPPLIER>::CountItems() const 276{ 277 return fItemCount; 278} 279 280// IsEmpty 281template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 282bool 283List<ITEM, DEFAULT_ITEM_SUPPLIER>::IsEmpty() const 284{ 285 return (fItemCount == 0); 286} 287 288// ItemAt 289template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 290const typename List<ITEM, DEFAULT_ITEM_SUPPLIER>::item_t & 291List<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 299template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 300typename List<ITEM, DEFAULT_ITEM_SUPPLIER>::item_t & 301List<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 309template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 310const typename List<ITEM, DEFAULT_ITEM_SUPPLIER>::item_t * 311List<ITEM, DEFAULT_ITEM_SUPPLIER>::Items() const 312{ 313 return fItems; 314} 315 316// IndexOf 317template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 318int32 319List<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 329template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 330bool 331List<ITEM, DEFAULT_ITEM_SUPPLIER>::HasItem(const item_t &item) const 332{ 333 return (IndexOf(item) >= 0); 334} 335 336// _Resize 337template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 338bool 339List<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