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