src/kits/support/PointerList.cpp

   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 Haiku 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