src/third_party/icu/source/common/uvector.h

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