icuSources/common/uvector.h

   1 /*
   2 **********************************************************************
   3 *   Copyright (C) 1999-2016, International Business Machines
   4 *   Corporation and others.  All Rights Reserved.
   5 **********************************************************************
   6 *   Date        Name        Description
   7 *   10/22/99    alan        Creation.  This is an internal header.
   8 *                           It should not be exported.
   9 **********************************************************************
  10 */
  11
  12 #ifndef UVECTOR_H
  13 #define UVECTOR_H
  14
  15 #include "unicode/utypes.h"
  16 #include "unicode/uobject.h"
  17 #include "cmemory.h"
  18 #include "uarrsort.h"
  19 #include "uelement.h"
  20
  21 U_NAMESPACE_BEGIN
  22
  23 /**
  24  * <p>Ultralightweight C++ implementation of a <tt>void*</tt> vector
  25  * that is (mostly) compatible with java.util.Vector.
  26  *
  27  * <p>This is a very simple implementation, written to satisfy an
  28  * immediate porting need.  As such, it is not completely fleshed out,
  29  * and it aims for simplicity and conformity.  Nonetheless, it serves
  30  * its purpose (porting code from java that uses java.util.Vector)
  31  * well, and it could be easily made into a more robust vector class.
  32  *
  33  * <p><b>Design notes</b>
  34  *
  35  * <p>There is index bounds checking, but little is done about it.  If
  36  * indices are out of bounds, either nothing happens, or zero is
  37  * returned.  We <em>do</em> avoid indexing off into the weeds.
  38  *
  39  * <p>There is detection of out of memory, but the handling is very
  40  * coarse-grained -- similar to UnicodeString's protocol, but even
  41  * coarser.  The class contains <em>one static flag</em> that is set
  42  * when any call to <tt>new</tt> returns zero.  This allows the caller
  43  * to use several vectors and make just one check at the end to see if
  44  * a memory failure occurred.  This is more efficient than making a
  45  * check after each call on each vector when doing many operations on
  46  * multiple vectors.  The single static flag works best when memory
  47  * failures are infrequent, and when recovery options are limited or
  48  * nonexistent.
  49  *
  50  * <p>Since we don't have garbage collection, UVector was given the
  51  * option to <em>own</em>its contents.  To employ this, set a deleter
  52  * function.  The deleter is called on a void* pointer when that
  53  * pointer is released by the vector, either when the vector itself is
  54  * destructed, or when a call to setElementAt() overwrites an element,
  55  * or when a call to remove() or one of its variants explicitly
  56  * removes an element.  If no deleter is set, or the deleter is set to
  57  * zero, then it is assumed that the caller will delete elements as
  58  * needed.
  59  *
  60  * <p>In order to implement methods such as contains() and indexOf(),
  61  * UVector needs a way to compare objects for equality.  To do so, it
  62  * uses a comparison function, or "comparer."  If the comparer is not
  63  * set, or is set to zero, then all such methods will act as if the
  64  * vector contains no element.  That is, indexOf() will always return
  65  * -1, contains() will always return FALSE, etc.
  66  *
  67  * <p><b>To do</b>
  68  *
  69  * <p>Improve the handling of index out of bounds errors.
  70  *
  71  * @author Alan Liu
  72  */
  73 class U_COMMON_API UVector : public UObject {
  74     // NOTE: UVector uses the UHashKey (union of void* and int32_t) as
  75     // its basic storage type.  It uses UElementsAreEqual as its
  76     // comparison function.  It uses UObjectDeleter as its deleter
  77     // function.  These are named for hashtables, but used here as-is
  78     // rather than duplicating the type.  This allows sharing of
  79     // support functions.
  80
  81 private:
  82     int32_t count;
  83
  84     int32_t capacity;
  85
  86     UElement* elements;
  87
  88     UObjectDeleter *deleter;
  89
  90     UElementsAreEqual *comparer;
  91
  92 public:
  93     UVector(UErrorCode &status);
  94
  95     UVector(int32_t initialCapacity, UErrorCode &status);
  96
  97     UVector(UObjectDeleter *d, UElementsAreEqual *c, UErrorCode &status);
  98
  99     UVector(UObjectDeleter *d, UElementsAreEqual *c, int32_t initialCapacity, UErrorCode &status);
 100
 101     virtual ~UVector();
 102
 103     /**
 104      * Assign this object to another (make this a copy of 'other').
 105      * Use the 'assign' function to assign each element.
 106      */
 107     void assign(const UVector& other, UElementAssigner *assign, UErrorCode &ec);
 108
 109     /**
 110      * Compare this vector with another.  They will be considered
 111      * equal if they are of the same size and all elements are equal,
 112      * as compared using this object's comparer.
 113      */
 114     UBool operator==(const UVector& other);
 115
 116     /**
 117      * Equivalent to !operator==()
 118      */
 119     inline UBool operator!=(const UVector& other);
 120
 121     //------------------------------------------------------------
 122     // java.util.Vector API
 123     //------------------------------------------------------------
 124
 125     void addElement(void* obj, UErrorCode &status);
 126
 127     void addElement(int32_t elem, UErrorCode &status);
 128
 129     void setElementAt(void* obj, int32_t index);
 130
 131     void setElementAt(int32_t elem, int32_t index);
 132
 133     void insertElementAt(void* obj, int32_t index, UErrorCode &status);
 134
 135     void insertElementAt(int32_t elem, int32_t index, UErrorCode &status);
 136
 137     void* elementAt(int32_t index) const;
 138
 139     int32_t elementAti(int32_t index) const;
 140
 141     UBool equals(const UVector &other) const;
 142
 143     void* firstElement(void) const;
 144
 145     void* lastElement(void) const;
 146
 147     int32_t lastElementi(void) const;
 148
 149     int32_t indexOf(void* obj, int32_t startIndex = 0) const;
 150
 151     int32_t indexOf(int32_t obj, int32_t startIndex = 0) const;
 152
 153     UBool contains(void* obj) const;
 154
 155     UBool contains(int32_t obj) const;
 156
 157     UBool containsAll(const UVector& other) const;
 158
 159     UBool removeAll(const UVector& other);
 160
 161     UBool retainAll(const UVector& other);
 162
 163     void removeElementAt(int32_t index);
 164
 165     UBool removeElement(void* obj);
 166
 167     void removeAllElements();
 168
 169     int32_t size(void) const;
 170
 171     UBool isEmpty(void) const;
 172
 173     UBool ensureCapacity(int32_t minimumCapacity, UErrorCode &status);
 174
 175     /**
 176      * Change the size of this vector as follows: If newSize is
 177      * smaller, then truncate the array, possibly deleting held
 178      * elements for i >= newSize.  If newSize is larger, grow the
 179      * array, filling in new slots with NULL.
 180      */
 181     void setSize(int32_t newSize, UErrorCode &status);
 182
 183     /**
 184      * Fill in the given array with all elements of this vector.
 185      */
 186     void** toArray(void** result) const;
 187
 188     //------------------------------------------------------------
 189     // New API
 190     //------------------------------------------------------------
 191
 192     UObjectDeleter *setDeleter(UObjectDeleter *d);
 193
 194     UElementsAreEqual *setComparer(UElementsAreEqual *c);
 195
 196     void* operator[](int32_t index) const;
 197
 198     /**
 199      * Removes the element at the given index from this vector and
 200      * transfer ownership of it to the caller.  After this call, the
 201      * caller owns the result and must delete it and the vector entry
 202      * at 'index' is removed, shifting all subsequent entries back by
 203      * one index and shortening the size of the vector by one.  If the
 204      * index is out of range or if there is no item at the given index
 205      * then 0 is returned and the vector is unchanged.
 206      */
 207     void* orphanElementAt(int32_t index);
 208
 209     /**
 210      * Returns true if this vector contains none of the elements
 211      * of the given vector.
 212      * @param other vector to be checked for containment
 213      * @return true if the test condition is met
 214      */
 215     UBool containsNone(const UVector& other) const;
 216
 217     /**
 218      * Insert the given object into this vector at its sorted position
 219      * as defined by 'compare'.  The current elements are assumed to
 220      * be sorted already.
 221      */
 222     void sortedInsert(void* obj, UElementComparator *compare, UErrorCode& ec);
 223
 224     /**
 225      * Insert the given integer into this vector at its sorted position
 226      * as defined by 'compare'.  The current elements are assumed to
 227      * be sorted already.
 228      */
 229     void sortedInsert(int32_t obj, UElementComparator *compare, UErrorCode& ec);
 230
 231     /**
 232      * Sort the contents of the vector, assuming that the contents of the
 233      * vector are of type int32_t.
 234      */
 235     void sorti(UErrorCode &ec);
 236
 237     /**
 238       * Sort the contents of this vector, using a caller-supplied function
 239       * to do the comparisons.  (It's confusing that
 240       *  UVector's UElementComparator function is different from the
 241       *  UComparator function type defined in uarrsort.h)
 242       */
 243     void sort(UElementComparator *compare, UErrorCode &ec);
 244
 245     /**
 246      * Stable sort the contents of this vector using a caller-supplied function
 247      * of type UComparator to do the comparison.  Provides more flexibility
 248      * than UVector::sort() because an additional user parameter can be passed to
 249      * the comparison function.
 250      */
 251     void sortWithUComparator(UComparator *compare, const void *context, UErrorCode &ec);
 252
 253     /**
 254      * ICU "poor man's RTTI", returns a UClassID for this class.
 255      */
 256     static UClassID U_EXPORT2 getStaticClassID();
 257
 258     /**
 259      * ICU "poor man's RTTI", returns a UClassID for the actual class.
 260      */
 261     virtual UClassID getDynamicClassID() const;
 262
 263 private:
 264     void _init(int32_t initialCapacity, UErrorCode &status);
 265
 266     int32_t indexOf(UElement key, int32_t startIndex = 0, int8_t hint = 0) const;
 267
 268     void sortedInsert(UElement e, UElementComparator *compare, UErrorCode& ec);
 269
 270     // Disallow
 271     UVector(const UVector&);
 272
 273     // Disallow
 274     UVector& operator=(const UVector&);
 275
 276 };
 277
 278
 279 /**
 280  * <p>Ultralightweight C++ implementation of a <tt>void*</tt> stack
 281  * that is (mostly) compatible with java.util.Stack.  As in java, this
 282  * is merely a paper thin layer around UVector.  See the UVector
 283  * documentation for further information.
 284  *
 285  * <p><b>Design notes</b>
 286  *
 287  * <p>The element at index <tt>n-1</tt> is (of course) the top of the
 288  * stack.
 289  *
 290  * <p>The poorly named <tt>empty()</tt> method doesn't empty the
 291  * stack; it determines if the stack is empty.
 292  *
 293  * @author Alan Liu
 294  */
 295 class U_COMMON_API UStack : public UVector {
 296 public:
 297     UStack(UErrorCode &status);
 298
 299     UStack(int32_t initialCapacity, UErrorCode &status);
 300
 301     UStack(UObjectDeleter *d, UElementsAreEqual *c, UErrorCode &status);
 302
 303     UStack(UObjectDeleter *d, UElementsAreEqual *c, int32_t initialCapacity, UErrorCode &status);
 304
 305     virtual ~UStack();
 306
 307     // It's okay not to have a virtual destructor (in UVector)
 308     // because UStack has no special cleanup to do.
 309
 310     UBool empty(void) const;
 311
 312     void* peek(void) const;
 313
 314     int32_t peeki(void) const;
 315
 316     void* pop(void);
 317
 318     int32_t popi(void);
 319
 320     void* push(void* obj, UErrorCode &status);
 321
 322     int32_t push(int32_t i, UErrorCode &status);
 323
 324     /*
 325     If the object o occurs as an item in this stack,
 326     this method returns the 1-based distance from the top of the stack.
 327     */
 328     int32_t search(void* obj) const;
 329
 330     /**
 331      * ICU "poor man's RTTI", returns a UClassID for this class.
 332      */
 333     static UClassID U_EXPORT2 getStaticClassID();
 334
 335     /**
 336      * ICU "poor man's RTTI", returns a UClassID for the actual class.
 337      */
 338     virtual UClassID getDynamicClassID() const;
 339
 340 private:
 341     // Disallow
 342     UStack(const UStack&);
 343
 344     // Disallow
 345     UStack& operator=(const UStack&);
 346 };
 347
 348
 349 // UVector inlines
 350
 351 inline int32_t UVector::size(void) const {
 352     return count;
 353 }
 354
 355 inline UBool UVector::isEmpty(void) const {
 356     return count == 0;
 357 }
 358
 359 inline UBool UVector::contains(void* obj) const {
 360     return indexOf(obj) >= 0;
 361 }
 362
 363 inline UBool UVector::contains(int32_t obj) const {
 364     return indexOf(obj) >= 0;
 365 }
 366
 367 inline void* UVector::firstElement(void) const {
 368     return elementAt(0);
 369 }
 370
 371 inline void* UVector::lastElement(void) const {
 372     return elementAt(count-1);
 373 }
 374
 375 inline int32_t UVector::lastElementi(void) const {
 376     return elementAti(count-1);
 377 }
 378
 379 inline void* UVector::operator[](int32_t index) const {
 380     return elementAt(index);
 381 }
 382
 383 inline UBool UVector::operator!=(const UVector& other) {
 384     return !operator==(other);
 385 }
 386
 387 // UStack inlines
 388
 389 inline UBool UStack::empty(void) const {
 390     return isEmpty();
 391 }
 392
 393 inline void* UStack::peek(void) const {
 394     return lastElement();
 395 }
 396
 397 inline int32_t UStack::peeki(void) const {
 398     return lastElementi();
 399 }
 400
 401 inline void* UStack::push(void* obj, UErrorCode &status) {
 402     addElement(obj, status);
 403     return obj;
 404 }
 405
 406 inline int32_t UStack::push(int32_t i, UErrorCode &status) {
 407     addElement(i, status);
 408     return i;
 409 }
 410
 411 U_NAMESPACE_END
 412
 413 #endif