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 37template<typename ITEM> 38class DefaultDefaultItemCreator { 39public: 40 static inline ITEM GetItem() { return ITEM(0); } 41}; 42 43/*! 44 \class List 45 \brief A generic list implementation. 46*/ 47template<typename ITEM, 48 typename DEFAULT_ITEM_SUPPLIER = DefaultDefaultItemCreator<ITEM> > 49class List { 50public: 51 typedef ITEM item_t; 52 typedef List list_t; 53 54private: 55 static item_t sDefaultItem; 56 static const size_t kDefaultChunkSize = 10; 57 static const size_t kMaximalChunkSize = 1024 * 1024; 58 59public: 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 91private: 92 inline static void _MoveItems(item_t* items, int32 offset, int32 count); 93 bool _Resize(size_t count); 94 95private: 96 size_t fCapacity; 97 size_t fChunkSize; 98 int32 fItemCount; 99 item_t *fItems; 100}; 101 102// sDefaultItem 103template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 104typename List<ITEM, DEFAULT_ITEM_SUPPLIER>::item_t 105 List<ITEM, DEFAULT_ITEM_SUPPLIER>::sDefaultItem( 106 DEFAULT_ITEM_SUPPLIER::GetItem()); 107 108// constructor 109template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 110List<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 122template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 123List<ITEM, DEFAULT_ITEM_SUPPLIER>::~List() 124{ 125 MakeEmpty(); 126 free(fItems); 127} 128 129// GetDefaultItem 130template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 131inline 132const typename List<ITEM, DEFAULT_ITEM_SUPPLIER>::item_t & 133List<ITEM, DEFAULT_ITEM_SUPPLIER>::GetDefaultItem() const 134{ 135 return sDefaultItem; 136} 137 138// GetDefaultItem 139template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 140inline 141typename List<ITEM, DEFAULT_ITEM_SUPPLIER>::item_t & 142List<ITEM, DEFAULT_ITEM_SUPPLIER>::GetDefaultItem() 143{ 144 return sDefaultItem; 145} 146 147// _MoveItems 148template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 149inline 150void 151List<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 158template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 159bool 160List<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 172template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 173bool 174List<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 190template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 191bool 192List<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 208template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 209bool 210List<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 227template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 228bool 229List<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 239template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 240bool 241List<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 253template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 254bool 255List<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 265template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 266bool 267List<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 286template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 287void 288List<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 296template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 297int32 298List<ITEM, DEFAULT_ITEM_SUPPLIER>::CountItems() const 299{ 300 return fItemCount; 301} 302 303// IsEmpty 304template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 305bool 306List<ITEM, DEFAULT_ITEM_SUPPLIER>::IsEmpty() const 307{ 308 return (fItemCount == 0); 309} 310 311// ItemAt 312template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 313const typename List<ITEM, DEFAULT_ITEM_SUPPLIER>::item_t & 314List<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 322template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 323typename List<ITEM, DEFAULT_ITEM_SUPPLIER>::item_t & 324List<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 332template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 333const typename List<ITEM, DEFAULT_ITEM_SUPPLIER>::item_t * 334List<ITEM, DEFAULT_ITEM_SUPPLIER>::Items() const 335{ 336 return fItems; 337} 338 339// IndexOf 340template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 341int32 342List<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 352template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 353bool 354List<ITEM, DEFAULT_ITEM_SUPPLIER>::HasItem(const item_t &item) const 355{ 356 return (IndexOf(item) >= 0); 357} 358 359// _Resize 360template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 361bool 362List<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