1/* 2** Copyright 2003-2004, Stefano Ceccherini (burton666@libero.it). All rights reserved. 3** 2004, Michael Pfeiffer (laplace@users.sourceforge.net). 4** Distributed under the terms of the MIT License. 5** 6** History 7** 2003-2004 Initial implementation by Stefano Ceccerini. 8** 2004/08/03 Testing, bug fixing and implementation of quick sort, refactoring 9** by Michael Pfeiffer. 10*/ 11 12// TODO: 13// - Rewrite to use STL 14// - Include ObjectList.h 15// - Test if building with jam works 16 17// Note: Method Owning() is inlined in header file ObjectList.h 18 19#include <ObjectList.h> 20 21#include <algorithm> 22#include <assert.h> 23#include <functional> 24#include <string.h> 25 26#include <List.h> 27 28 29using namespace std; 30 31 32// TODO: The implementation of _PointerList_ should be completely rewritten to 33// use STL in a more efficent way! 34 35struct comparator; 36 37 38class AbstractPointerListHelper { 39public: 40 AbstractPointerListHelper() {}; 41 virtual ~AbstractPointerListHelper(); 42 43 /** 44 Returns the index of the item that matches key or 45 a negative number. Then -(index+1) is the insert position 46 of the item not in list. 47 */ 48 int32 BinarySearchIndex(const void *key, const BList *list); 49 /** 50 Returns the item that matches key or NULL if the item could 51 not be found in the list. 52 */ 53 void* BinarySearch(const void *key, const BList *list); 54 /** 55 Sorts the items in list. 56 */ 57 void SortItems(BList *list); 58 /** 59 Removes the first item in list and appends it at the bottom of 60 the list and sorts all items but the last item. 61 */ 62 void HSortItems(BList *list); 63 64 friend struct comparator; 65 66private: 67 enum { 68 // Use insertion sort if number of elements in list is less than 69 // kQuickSortThreshold. 70 kQuickSortThreshold = 11, 71 // Use simple pivot element computation if number of elements in 72 // list is less than kPivotThreshold. 73 kPivotThreshold = 5, 74 }; 75 76 // Methods that do the actual work: 77 inline void Swap(void **items, int32 i, int32 j); 78 79 void* BinarySearch(const void *key, const void **items, int32 numItems, 80 int32 &index); 81 void QuickSort(void **items, int32 low, int32 high); 82 83 // Method to be implemented by sub classes 84 int virtual Compare(const void *key, const void* item) = 0; 85}; 86 87struct comparator 88{ 89 comparator(AbstractPointerListHelper* helper) : helper(helper) {} 90 91 bool operator()(const void* a, const void* b) { 92 return helper->Compare(b, a) > 0; 93 } 94 95 AbstractPointerListHelper* helper; 96}; 97 98 99AbstractPointerListHelper::~AbstractPointerListHelper() 100{ 101} 102 103 104void 105AbstractPointerListHelper::Swap(void **items, int32 i, int32 j) 106{ 107 void *swap = items[i]; 108 items[i] = items[j]; 109 items[j] = swap; 110} 111 112 113int32 114AbstractPointerListHelper::BinarySearchIndex(const void *key, const BList *list) 115{ 116 int32 index; 117 const void **items = static_cast<const void**>(list->Items()); 118 BinarySearch(key, items, list->CountItems(), index); 119 return index; 120} 121 122 123void * 124AbstractPointerListHelper::BinarySearch(const void *key, const BList *list) 125{ 126 int32 index; 127 const void **items = static_cast<const void**>(list->Items()); 128 return BinarySearch(key, items, list->CountItems(), index); 129} 130 131 132void 133AbstractPointerListHelper::SortItems(BList *list) 134{ 135 void **items = static_cast<void**>(list->Items()); 136 QuickSort(items, 0, list->CountItems()-1); 137} 138 139 140void 141AbstractPointerListHelper::HSortItems(BList *list) 142{ 143 void **items = static_cast<void**>(list->Items()); 144 int32 numItems = list->CountItems(); 145 if (numItems > 1) { 146 // swap last with first item 147 Swap(items, 0, numItems-1); 148 } 149 // sort all items but last item 150 QuickSort(items, 0, numItems-2); 151} 152 153 154void * 155AbstractPointerListHelper::BinarySearch(const void *key, const void **items, 156 int32 numItems, int32 &index) 157{ 158 const void** end = &items[numItems]; 159 const void** found = lower_bound(items, end, key, comparator(this)); 160 index = found - items; 161 if (index != numItems && Compare(key, *found) == 0) { 162 return const_cast<void*>(*found); 163 } else { 164 index = -(index + 1); 165 return NULL; 166 } 167} 168 169 170void 171AbstractPointerListHelper::QuickSort(void **items, int32 low, int32 high) 172{ 173 if (low <= high) { 174 sort(&items[low], &items[high+1], comparator(this)); 175 } 176} 177 178 179class PointerListHelper : public AbstractPointerListHelper { 180public: 181 PointerListHelper(_PointerList_::GenericCompareFunction compareFunc) 182 : fCompareFunc(compareFunc) 183 { 184 // nothing to do 185 } 186 187 int Compare(const void *a, const void *b) 188 { 189 return fCompareFunc(a, b); 190 } 191 192private: 193 _PointerList_::GenericCompareFunction fCompareFunc; 194}; 195 196 197class PointerListHelperWithState : public AbstractPointerListHelper 198{ 199public: 200 PointerListHelperWithState( 201 _PointerList_::GenericCompareFunctionWithState compareFunc, 202 void* state) 203 : fCompareFunc(compareFunc) 204 , fState(state) 205 { 206 // nothing to do 207 } 208 209 int Compare(const void *a, const void *b) 210 { 211 return fCompareFunc(a, b, fState); 212 } 213 214private: 215 _PointerList_::GenericCompareFunctionWithState fCompareFunc; 216 void* fState; 217}; 218 219 220class PointerListHelperUsePredicate : public AbstractPointerListHelper 221{ 222public: 223 PointerListHelperUsePredicate( 224 _PointerList_::UnaryPredicateGlue predicate) 225 : fPredicate(predicate) 226 { 227 // nothing to do 228 } 229 230 int Compare(const void *arg, const void *item) 231 { 232 // need to adapt arguments and return value 233 return -fPredicate(item, const_cast<void *>(arg)); 234 } 235 236private: 237 _PointerList_::UnaryPredicateGlue fPredicate; 238}; 239 240 241// Implementation of class _PointerList_ 242 243_PointerList_::_PointerList_(int32 itemsPerBlock, bool own) 244 : 245 BList(itemsPerBlock), 246 owning(own) 247{ 248 249} 250 251 252_PointerList_::_PointerList_(const _PointerList_ &list) 253 : 254 BList(list), 255 owning(list.owning) 256{ 257} 258 259 260_PointerList_::~_PointerList_() 261{ 262 // This is empty by design, the "owning" variable 263 // is used by the BObjectList subclass 264} 265 266 267// Note: function pointers must not be NULL!!! 268 269void * 270_PointerList_::EachElement(GenericEachFunction function, void *arg) 271{ 272 int32 numItems = CountItems(); 273 void *result = NULL; 274 275 for (int32 index = 0; index < numItems; index++) { 276 result = function(ItemAtFast(index), arg); 277 if (result != NULL) 278 break; 279 } 280 281 return result; 282} 283 284 285void 286_PointerList_::SortItems(GenericCompareFunction compareFunc) 287{ 288 PointerListHelper helper(compareFunc); 289 helper.SortItems(this); 290} 291 292 293void 294_PointerList_::SortItems(GenericCompareFunctionWithState compareFunc, 295 void *state) 296{ 297 PointerListHelperWithState helper(compareFunc, state); 298 helper.SortItems(this); 299} 300 301 302void 303_PointerList_::HSortItems(GenericCompareFunction compareFunc) 304{ 305 PointerListHelper helper(compareFunc); 306 helper.HSortItems(this); 307} 308 309 310void 311_PointerList_::HSortItems(GenericCompareFunctionWithState compareFunc, 312 void *state) 313{ 314 PointerListHelperWithState helper(compareFunc, state); 315 helper.HSortItems(this); 316} 317 318 319void * 320_PointerList_::BinarySearch(const void *key, 321 GenericCompareFunction compareFunc) const 322{ 323 PointerListHelper helper(compareFunc); 324 return helper.BinarySearch(key, this); 325} 326 327 328void * 329_PointerList_::BinarySearch(const void *key, 330 GenericCompareFunctionWithState compareFunc, void *state) const 331{ 332 PointerListHelperWithState helper(compareFunc, state); 333 return helper.BinarySearch(key, this); 334} 335 336 337int32 338_PointerList_::BinarySearchIndex(const void *key, 339 GenericCompareFunction compareFunc) const 340{ 341 PointerListHelper helper(compareFunc); 342 return helper.BinarySearchIndex(key, this); 343} 344 345 346int32 347_PointerList_::BinarySearchIndex(const void *key, 348 GenericCompareFunctionWithState compareFunc, void *state) const 349{ 350 PointerListHelperWithState helper(compareFunc, state); 351 return helper.BinarySearchIndex(key, this); 352} 353 354 355int32 356_PointerList_::BinarySearchIndexByPredicate(const void *key, 357 UnaryPredicateGlue predicate) const 358{ 359 PointerListHelperUsePredicate helper(predicate); 360 return helper.BinarySearchIndex(key, this); 361} 362 363bool 364_PointerList_::ReplaceItem(int32 index, void *newItem) 365{ 366 if (index < 0 || index >= CountItems()) 367 return false; 368 369 void **items = static_cast<void **>(Items()); 370 items[index] = newItem; 371 372 return true; 373} 374 375 376bool 377_PointerList_::MoveItem(int32 from, int32 to) 378{ 379 if (from == to) 380 return true; 381 382 void* fromItem = ItemAt(from); 383 void* toItem = ItemAt(to); 384 if (fromItem == NULL || toItem == NULL) 385 return false; 386 387 void** items = static_cast<void**>(Items()); 388 if (from < to) 389 memmove(items + from, items + from + 1, (to - from) * sizeof(void*)); 390 else 391 memmove(items + to + 1, items + to, (from - to) * sizeof(void*)); 392 393 items[to] = fromItem; 394 return true; 395} 396 397 398