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