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 29 using namespace std; 30 31 32 // TODO: The implementation of _PointerList_ should be completely rewritten to 33 // use STL in a more efficent way! 34 35 struct comparator; 36 37 38 class AbstractPointerListHelper { 39 public: 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 66 private: 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 87 struct comparator : public binary_function<const void*, const void*, bool> 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 99 AbstractPointerListHelper::~AbstractPointerListHelper() 100 { 101 } 102 103 104 void 105 AbstractPointerListHelper::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 113 int32 114 AbstractPointerListHelper::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 123 void * 124 AbstractPointerListHelper::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 132 void 133 AbstractPointerListHelper::SortItems(BList *list) 134 { 135 void **items = static_cast<void**>(list->Items()); 136 QuickSort(items, 0, list->CountItems()-1); 137 } 138 139 140 void 141 AbstractPointerListHelper::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 154 void * 155 AbstractPointerListHelper::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 170 void 171 AbstractPointerListHelper::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 179 class PointerListHelper : public AbstractPointerListHelper { 180 public: 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 192 private: 193 _PointerList_::GenericCompareFunction fCompareFunc; 194 }; 195 196 197 class PointerListHelperWithState : public AbstractPointerListHelper 198 { 199 public: 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 214 private: 215 _PointerList_::GenericCompareFunctionWithState fCompareFunc; 216 void* fState; 217 }; 218 219 220 class PointerListHelperUsePredicate : public AbstractPointerListHelper 221 { 222 public: 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 236 private: 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 269 void * 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 285 void 286 _PointerList_::SortItems(GenericCompareFunction compareFunc) 287 { 288 PointerListHelper helper(compareFunc); 289 helper.SortItems(this); 290 } 291 292 293 void 294 _PointerList_::SortItems(GenericCompareFunctionWithState compareFunc, 295 void *state) 296 { 297 PointerListHelperWithState helper(compareFunc, state); 298 helper.SortItems(this); 299 } 300 301 302 void 303 _PointerList_::HSortItems(GenericCompareFunction compareFunc) 304 { 305 PointerListHelper helper(compareFunc); 306 helper.HSortItems(this); 307 } 308 309 310 void 311 _PointerList_::HSortItems(GenericCompareFunctionWithState compareFunc, 312 void *state) 313 { 314 PointerListHelperWithState helper(compareFunc, state); 315 helper.HSortItems(this); 316 } 317 318 319 void * 320 _PointerList_::BinarySearch(const void *key, 321 GenericCompareFunction compareFunc) const 322 { 323 PointerListHelper helper(compareFunc); 324 return helper.BinarySearch(key, this); 325 } 326 327 328 void * 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 337 int32 338 _PointerList_::BinarySearchIndex(const void *key, 339 GenericCompareFunction compareFunc) const 340 { 341 PointerListHelper helper(compareFunc); 342 return helper.BinarySearchIndex(key, this); 343 } 344 345 346 int32 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 355 int32 356 _PointerList_::BinarySearchIndexByPredicate(const void *key, 357 UnaryPredicateGlue predicate) const 358 { 359 PointerListHelperUsePredicate helper(predicate); 360 return helper.BinarySearchIndex(key, this); 361 } 362 363 bool 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 376 bool 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