icuSources/common/uvector.h

   1 /*
   2 **********************************************************************
   3 *   Copyright (C) 1999-2006, 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 slows with NULL.
 197      */
 198     void setSize(int32_t newSize);
 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      * ICU "poor man's RTTI", returns a UClassID for this class.
 250      */
 251     static UClassID U_EXPORT2 getStaticClassID();
 252
 253     /**
 254      * ICU "poor man's RTTI", returns a UClassID for the actual class.
 255      */
 256     virtual UClassID getDynamicClassID() const;
 257
 258 private:
 259     void _init(int32_t initialCapacity, UErrorCode &status);
 260
 261     int32_t indexOf(UHashTok key, int32_t startIndex = 0, int8_t hint = 0) const;
 262
 263     void sortedInsert(UHashTok tok, USortComparator *compare, UErrorCode& ec);
 264
 265     // Disallow
 266     UVector(const UVector&);
 267
 268     // Disallow
 269     UVector& operator=(const UVector&);
 270
 271 };
 272
 273
 274 /**
 275  * <p>Ultralightweight C++ implementation of a <tt>void*</tt> stack
 276  * that is (mostly) compatible with java.util.Stack.  As in java, this
 277  * is merely a paper thin layer around UVector.  See the UVector
 278  * documentation for further information.
 279  *
 280  * <p><b>Design notes</b>
 281  *
 282  * <p>The element at index <tt>n-1</tt> is (of course) the top of the
 283  * stack.
 284  *
 285  * <p>The poorly named <tt>empty()</tt> method doesn't empty the
 286  * stack; it determines if the stack is empty.
 287  *
 288  * @author Alan Liu
 289  */
 290 class U_COMMON_API UStack : public UVector {
 291 public:
 292     UStack(UErrorCode &status);
 293
 294     UStack(int32_t initialCapacity, UErrorCode &status);
 295
 296     UStack(UObjectDeleter *d, UKeyComparator *c, UErrorCode &status);
 297
 298     UStack(UObjectDeleter *d, UKeyComparator *c, int32_t initialCapacity, UErrorCode &status);
 299
 300     virtual ~UStack();
 301
 302     // It's okay not to have a virtual destructor (in UVector)
 303     // because UStack has no special cleanup to do.
 304
 305     UBool empty(void) const;
 306
 307     void* peek(void) const;
 308
 309     int32_t peeki(void) const;
 310
 311     void* pop(void);
 312
 313     int32_t popi(void);
 314
 315     void* push(void* obj, UErrorCode &status);
 316
 317     int32_t push(int32_t i, UErrorCode &status);
 318
 319     /*
 320     If the object o occurs as an item in this stack,
 321     this method returns the 1-based distance from the top of the stack.
 322     */
 323     int32_t search(void* obj) const;
 324
 325     /**
 326      * ICU "poor man's RTTI", returns a UClassID for this class.
 327      */
 328     static UClassID U_EXPORT2 getStaticClassID();
 329
 330     /**
 331      * ICU "poor man's RTTI", returns a UClassID for the actual class.
 332      */
 333     virtual UClassID getDynamicClassID() const;
 334
 335 private:
 336     // Disallow
 337     UStack(const UStack&);
 338
 339     // Disallow
 340     UStack& operator=(const UStack&);
 341 };
 342
 343
 344 // UVector inlines
 345
 346 inline int32_t UVector::size(void) const {
 347     return count;
 348 }
 349
 350 inline UBool UVector::isEmpty(void) const {
 351     return count == 0;
 352 }
 353
 354 inline UBool UVector::contains(void* obj) const {
 355     return indexOf(obj) >= 0;
 356 }
 357
 358 inline UBool UVector::contains(int32_t obj) const {
 359     return indexOf(obj) >= 0;
 360 }
 361
 362 inline void* UVector::firstElement(void) const {
 363     return elementAt(0);
 364 }
 365
 366 inline void* UVector::lastElement(void) const {
 367     return elementAt(count-1);
 368 }
 369
 370 inline int32_t UVector::lastElementi(void) const {
 371     return elementAti(count-1);
 372 }
 373
 374 inline void* UVector::operator[](int32_t index) const {
 375     return elementAt(index);
 376 }
 377
 378 inline UBool UVector::operator!=(const UVector& other) {
 379     return !operator==(other);
 380 }
 381
 382 // UStack inlines
 383
 384 inline UBool UStack::empty(void) const {
 385     return isEmpty();
 386 }
 387
 388 inline void* UStack::peek(void) const {
 389     return lastElement();
 390 }
 391
 392 inline int32_t UStack::peeki(void) const {
 393     return lastElementi();
 394 }
 395
 396 inline void* UStack::push(void* obj, UErrorCode &status) {
 397     addElement(obj, status);
 398     return obj;
 399 }
 400
 401 inline int32_t UStack::push(int32_t i, UErrorCode &status) {
 402     addElement(i, status);
 403     return i;
 404 }
 405
 406 U_NAMESPACE_END
 407
 408 #endif