icuSources/common/uvector.cpp

   1 /*
   2 ******************************************************************************
   3 * Copyright (C) 1999-2004, International Business Machines Corporation and   *
   4 * others. All Rights Reserved.                                               *
   5 ******************************************************************************
   6 *   Date        Name        Description
   7 *   10/22/99    alan        Creation.
   8 **********************************************************************
   9 */
  10
  11 #include "uvector.h"
  12 #include "cmemory.h"
  13
  14 U_NAMESPACE_BEGIN
  15
  16 #define DEFUALT_CAPACITY 8
  17
  18 /*
  19  * Constants for hinting whether a key is an integer
  20  * or a pointer.  If a hint bit is zero, then the associated
  21  * token is assumed to be an integer. This is needed for iSeries
  22  */
  23 #define HINT_KEY_POINTER   (1)
  24 #define HINT_KEY_INTEGER   (0)
  25
  26 UOBJECT_DEFINE_RTTI_IMPLEMENTATION(UVector)
  27
  28 UVector::UVector(UErrorCode &status) :
  29     count(0),
  30     capacity(0),
  31     elements(0),
  32     deleter(0),
  33     comparer(0)
  34 {
  35     _init(DEFUALT_CAPACITY, status);
  36 }
  37
  38 UVector::UVector(int32_t initialCapacity, UErrorCode &status) :
  39     count(0),
  40     capacity(0),
  41     elements(0),
  42     deleter(0),
  43     comparer(0)
  44 {
  45     _init(initialCapacity, status);
  46 }
  47
  48 UVector::UVector(UObjectDeleter *d, UKeyComparator *c, UErrorCode &status) :
  49     count(0),
  50     capacity(0),
  51     elements(0),
  52     deleter(d),
  53     comparer(c)
  54 {
  55     _init(DEFUALT_CAPACITY, status);
  56 }
  57
  58 UVector::UVector(UObjectDeleter *d, UKeyComparator *c, int32_t initialCapacity, UErrorCode &status) :
  59     count(0),
  60     capacity(0),
  61     elements(0),
  62     deleter(d),
  63     comparer(c)
  64 {
  65     _init(initialCapacity, status);
  66 }
  67
  68 void UVector::_init(int32_t initialCapacity, UErrorCode &status) {
  69     if (U_FAILURE(status)) {
  70         return;
  71     }
  72     // Fix bogus initialCapacity values; avoid malloc(0)
  73     if (initialCapacity < 1) {
  74         initialCapacity = DEFUALT_CAPACITY;
  75     }
  76     elements = (UHashTok *)uprv_malloc(sizeof(UHashTok)*initialCapacity);
  77     if (elements == 0) {
  78         status = U_MEMORY_ALLOCATION_ERROR;
  79     } else {
  80         capacity = initialCapacity;
  81     }
  82 }
  83
  84 UVector::~UVector() {
  85     removeAllElements();
  86     uprv_free(elements);
  87     elements = 0;
  88 }
  89
  90 /**
  91  * Assign this object to another (make this a copy of 'other').
  92  * Use the 'assign' function to assign each element.
  93  */
  94 void UVector::assign(const UVector& other, UTokenAssigner *assign, UErrorCode &ec) {
  95     if (ensureCapacity(other.count, ec)) {
  96         setSize(other.count);
  97         for (int32_t i=0; i<other.count; ++i) {
  98             if (elements[i].pointer != 0 && deleter != 0) {
  99                 (*deleter)(elements[i].pointer);
 100             }
 101             (*assign)(&elements[i], &other.elements[i]);
 102         }
 103     }
 104 }
 105
 106 // This only does something sensible if this object has a non-null comparer
 107 UBool UVector::operator==(const UVector& other) {
 108     int32_t i;
 109     if (count != other.count) return FALSE;
 110     if (comparer != NULL) {
 111         // Compare using this object's comparer
 112         for (i=0; i<count; ++i) {
 113             if (!(*comparer)(elements[i], other.elements[i])) {
 114                 return FALSE;
 115             }
 116         }
 117     }
 118     return TRUE;
 119 }
 120
 121 void UVector::addElement(void* obj, UErrorCode &status) {
 122     if (ensureCapacity(count + 1, status)) {
 123         elements[count++].pointer = obj;
 124     }
 125 }
 126
 127 void UVector::addElement(int32_t elem, UErrorCode &status) {
 128     if (ensureCapacity(count + 1, status)) {
 129         elements[count].pointer = NULL;     // Pointers may be bigger than ints.
 130         elements[count].integer = elem;
 131         count++;
 132     }
 133 }
 134
 135 void UVector::setElementAt(void* obj, int32_t index) {
 136     if (0 <= index && index < count) {
 137         if (elements[index].pointer != 0 && deleter != 0) {
 138             (*deleter)(elements[index].pointer);
 139         }
 140         elements[index].pointer = obj;
 141     }
 142     /* else index out of range */
 143 }
 144
 145 void UVector::setElementAt(int32_t elem, int32_t index) {
 146     if (0 <= index && index < count) {
 147         if (elements[index].pointer != 0 && deleter != 0) {
 148             // TODO:  this should be an error.  mixing up ints and pointers.
 149             (*deleter)(elements[index].pointer);
 150         }
 151         elements[index].pointer = NULL;
 152         elements[index].integer = elem;
 153     }
 154     /* else index out of range */
 155 }
 156
 157 void UVector::insertElementAt(void* obj, int32_t index, UErrorCode &status) {
 158     // must have 0 <= index <= count
 159     if (0 <= index && index <= count && ensureCapacity(count + 1, status)) {
 160         for (int32_t i=count; i>index; --i) {
 161             elements[i] = elements[i-1];
 162         }
 163         elements[index].pointer = obj;
 164         ++count;
 165     }
 166     /* else index out of range */
 167 }
 168
 169 void UVector::insertElementAt(int32_t elem, int32_t index, UErrorCode &status) {
 170     // must have 0 <= index <= count
 171     if (0 <= index && index <= count && ensureCapacity(count + 1, status)) {
 172         for (int32_t i=count; i>index; --i) {
 173             elements[i] = elements[i-1];
 174         }
 175         elements[index].pointer = NULL;
 176         elements[index].integer = elem;
 177         ++count;
 178     }
 179     /* else index out of range */
 180 }
 181
 182 void* UVector::elementAt(int32_t index) const {
 183     return (0 <= index && index < count) ? elements[index].pointer : 0;
 184 }
 185
 186 int32_t UVector::elementAti(int32_t index) const {
 187     return (0 <= index && index < count) ? elements[index].integer : 0;
 188 }
 189
 190 UBool UVector::containsAll(const UVector& other) const {
 191     for (int32_t i=0; i<other.size(); ++i) {
 192         if (indexOf(other.elements[i]) < 0) {
 193             return FALSE;
 194         }
 195     }
 196     return TRUE;
 197 }
 198
 199 UBool UVector::containsNone(const UVector& other) const {
 200     for (int32_t i=0; i<other.size(); ++i) {
 201         if (indexOf(other.elements[i]) >= 0) {
 202             return FALSE;
 203         }
 204     }
 205     return TRUE;
 206 }
 207
 208 UBool UVector::removeAll(const UVector& other) {
 209     UBool changed = FALSE;
 210     for (int32_t i=0; i<other.size(); ++i) {
 211         int32_t j = indexOf(other.elements[i]);
 212         if (j >= 0) {
 213             removeElementAt(j);
 214             changed = TRUE;
 215         }
 216     }
 217     return changed;
 218 }
 219
 220 UBool UVector::retainAll(const UVector& other) {
 221     UBool changed = FALSE;
 222     for (int32_t j=size()-1; j>=0; --j) {
 223         int32_t i = other.indexOf(elements[j]);
 224         if (i < 0) {
 225             removeElementAt(j);
 226             changed = TRUE;
 227         }
 228     }
 229     return changed;
 230 }
 231
 232 void UVector::removeElementAt(int32_t index) {
 233     void* e = orphanElementAt(index);
 234     if (e != 0 && deleter != 0) {
 235         (*deleter)(e);
 236     }
 237 }
 238
 239 UBool UVector::removeElement(void* obj) {
 240     int32_t i = indexOf(obj);
 241     if (i >= 0) {
 242         removeElementAt(i);
 243         return TRUE;
 244     }
 245     return FALSE;
 246 }
 247
 248 void UVector::removeAllElements(void) {
 249     if (deleter != 0) {
 250         for (int32_t i=0; i<count; ++i) {
 251             if (elements[i].pointer != 0) {
 252                 (*deleter)(elements[i].pointer);
 253             }
 254         }
 255     }
 256     count = 0;
 257 }
 258
 259 UBool   UVector::equals(const UVector &other) const {
 260     int      i;
 261
 262     if (this->count != other.count) {
 263         return FALSE;
 264     }
 265     if (comparer == 0) {
 266         for (i=0; i<count; i++) {
 267             if (elements[i].pointer != other.elements[i].pointer) {
 268                 return FALSE;
 269             }
 270         }
 271     } else {
 272         UHashTok key;
 273         for (i=0; i<count; i++) {
 274             key.pointer = &other.elements[i];
 275             if (!(*comparer)(key, elements[i])) {
 276                 return FALSE;
 277             }
 278         }
 279     }
 280     return TRUE;
 281 }
 282
 283
 284
 285 int32_t UVector::indexOf(void* obj, int32_t startIndex) const {
 286     UHashTok key;
 287     key.pointer = obj;
 288     return indexOf(key, startIndex, HINT_KEY_POINTER);
 289 }
 290
 291 int32_t UVector::indexOf(int32_t obj, int32_t startIndex) const {
 292     UHashTok key;
 293     key.integer = obj;
 294     return indexOf(key, startIndex, HINT_KEY_INTEGER);
 295 }
 296
 297 // This only works if this object has a non-null comparer
 298 int32_t UVector::indexOf(UHashTok key, int32_t startIndex, int8_t hint) const {
 299     int32_t i;
 300     if (comparer != 0) {
 301         for (i=startIndex; i<count; ++i) {
 302             if ((*comparer)(key, elements[i])) {
 303                 return i;
 304             }
 305         }
 306     } else {
 307         for (i=startIndex; i<count; ++i) {
 308             /* Pointers are not always the same size as ints so to perform
 309              * a valid comparision we need to know whether we are being
 310              * provided an int or a pointer. */
 311             if (hint & HINT_KEY_POINTER) {
 312                 if (key.pointer == elements[i].pointer) {
 313                     return i;
 314                 }
 315             } else {
 316                 if (key.integer == elements[i].integer) {
 317                     return i;
 318                 }
 319             }
 320         }
 321     }
 322     return -1;
 323 }
 324
 325 UBool UVector::ensureCapacity(int32_t minimumCapacity, UErrorCode &status) {
 326     if (capacity >= minimumCapacity) {
 327         return TRUE;
 328     } else {
 329         int32_t newCap = capacity * 2;
 330         if (newCap < minimumCapacity) {
 331             newCap = minimumCapacity;
 332         }
 333         UHashTok* newElems = (UHashTok *)uprv_malloc(sizeof(UHashTok)*newCap);
 334         if (newElems == 0) {
 335             status = U_MEMORY_ALLOCATION_ERROR;
 336             return FALSE;
 337         }
 338         uprv_memcpy(newElems, elements, sizeof(elements[0]) * count);
 339         uprv_free(elements);
 340         elements = newElems;
 341         capacity = newCap;
 342         return TRUE;
 343     }
 344 }
 345
 346 /**
 347  * Change the size of this vector as follows: If newSize is smaller,
 348  * then truncate the array, possibly deleting held elements for i >=
 349  * newSize.  If newSize is larger, grow the array, filling in new
 350  * slots with NULL.
 351  */
 352 void UVector::setSize(int32_t newSize) {
 353     int32_t i;
 354     if (newSize < 0) {
 355         return;
 356     }
 357     if (newSize > count) {
 358         UErrorCode ec = U_ZERO_ERROR;
 359         if (!ensureCapacity(newSize, ec)) {
 360             return;
 361         }
 362         UHashTok empty;
 363         empty.pointer = NULL;
 364         empty.integer = 0;
 365         for (i=count; i<newSize; ++i) {
 366             elements[i] = empty;
 367         }
 368     } else {
 369         /* Most efficient to count down */
 370         for (i=count-1; i>=newSize; --i) {
 371             removeElementAt(i);
 372         }
 373     }
 374     count = newSize;
 375 }
 376
 377 /**
 378  * Fill in the given array with all elements of this vector.
 379  */
 380 void** UVector::toArray(void** result) const {
 381     void** a = result;
 382     for (int i=0; i<count; ++i) {
 383         *a++ = elements[i].pointer;
 384     }
 385     return result;
 386 }
 387
 388 UObjectDeleter *UVector::setDeleter(UObjectDeleter *d) {
 389     UObjectDeleter *old = deleter;
 390     deleter = d;
 391     return old;
 392 }
 393
 394 UKeyComparator *UVector::setComparer(UKeyComparator *d) {
 395     UKeyComparator *old = comparer;
 396     comparer = d;
 397     return old;
 398 }
 399
 400 /**
 401  * Removes the element at the given index from this vector and
 402  * transfer ownership of it to the caller.  After this call, the
 403  * caller owns the result and must delete it and the vector entry
 404  * at 'index' is removed, shifting all subsequent entries back by
 405  * one index and shortening the size of the vector by one.  If the
 406  * index is out of range or if there is no item at the given index
 407  * then 0 is returned and the vector is unchanged.
 408  */
 409 void* UVector::orphanElementAt(int32_t index) {
 410     void* e = 0;
 411     if (0 <= index && index < count) {
 412         e = elements[index].pointer;
 413         for (int32_t i=index; i<count-1; ++i) {
 414             elements[i] = elements[i+1];
 415         }
 416         --count;
 417     }
 418     /* else index out of range */
 419     return e;
 420 }
 421
 422 /**
 423  * Insert the given object into this vector at its sorted position
 424  * as defined by 'compare'.  The current elements are assumed to
 425  * be sorted already.
 426  */
 427 void UVector::sortedInsert(void* obj, USortComparator *compare, UErrorCode& ec) {
 428     UHashTok tok;
 429     tok.pointer = obj;
 430     sortedInsert(tok, compare, ec);
 431 }
 432
 433 /**
 434  * Insert the given integer into this vector at its sorted position
 435  * as defined by 'compare'.  The current elements are assumed to
 436  * be sorted already.
 437  */
 438 void UVector::sortedInsert(int32_t obj, USortComparator *compare, UErrorCode& ec) {
 439     UHashTok tok;
 440     tok.integer = obj;
 441     sortedInsert(tok, compare, ec);
 442 }
 443
 444 // ASSUME elements[] IS CURRENTLY SORTED
 445 void UVector::sortedInsert(UHashTok tok, USortComparator *compare, UErrorCode& ec) {
 446     // Perform a binary search for the location to insert tok at.  Tok
 447     // will be inserted between two elements a and b such that a <=
 448     // tok && tok < b, where there is a 'virtual' elements[-1] always
 449     // less than tok and a 'virtual' elements[count] always greater
 450     // than tok.
 451     int32_t min = 0, max = count;
 452     while (min != max) {
 453         int32_t probe = (min + max) / 2;
 454         int8_t c = (*compare)(elements[probe], tok);
 455         if (c > 0) {
 456             max = probe;
 457         } else {
 458             // assert(c <= 0);
 459             min = probe + 1;
 460         }
 461     }
 462     if (ensureCapacity(count + 1, ec)) {
 463         for (int32_t i=count; i>min; --i) {
 464             elements[i] = elements[i-1];
 465         }
 466         elements[min] = tok;
 467         ++count;
 468     }
 469 }
 470
 471 UStack::UStack(UErrorCode &status) :
 472     UVector(status)
 473 {
 474 }
 475
 476 UStack::UStack(int32_t initialCapacity, UErrorCode &status) :
 477     UVector(initialCapacity, status)
 478 {
 479 }
 480
 481 UStack::UStack(UObjectDeleter *d, UKeyComparator *c, UErrorCode &status) :
 482     UVector(d, c, status)
 483 {
 484 }
 485
 486 UStack::UStack(UObjectDeleter *d, UKeyComparator *c, int32_t initialCapacity, UErrorCode &status) :
 487     UVector(d, c, initialCapacity, status)
 488 {
 489 }
 490
 491 UStack::~UStack() {}
 492
 493 void* UStack::pop(void) {
 494     int32_t n = size() - 1;
 495     void* result = 0;
 496     if (n >= 0) {
 497         result = elementAt(n);
 498         removeElementAt(n);
 499     }
 500     return result;
 501 }
 502
 503 int32_t UStack::popi(void) {
 504     int32_t n = size() - 1;
 505     int32_t result = 0;
 506     if (n >= 0) {
 507         result = elementAti(n);
 508         removeElementAt(n);
 509     }
 510     return result;
 511 }
 512
 513 int32_t UStack::search(void* obj) const {
 514     int32_t i = indexOf(obj);
 515     return (i >= 0) ? size() - i : i;
 516 }
 517
 518 U_NAMESPACE_END
 519