1 // Copyright (C) 2016 and later: Unicode, Inc. and others. 2 // License & terms of use: http://www.unicode.org/copyright.html 3 /* 4 ********************************************************************** 5 * Copyright (C) 1999-2011, International Business Machines 6 * Corporation and others. All Rights Reserved. 7 ********************************************************************** 8 */ 9 10 // 11 // UVector32 is a class implementing a vector of 32 bit integers. 12 // It is similar to UVector, but holds int32_t values rather than pointers. 13 // Most of the code is unchanged from UVector. 14 // 15 16 #ifndef UVECTOR32_H 17 #define UVECTOR32_H 18 19 #include "unicode/utypes.h" 20 #include "unicode/uobject.h" 21 #include "uhash.h" 22 #include "uassert.h" 23 24 U_NAMESPACE_BEGIN 25 26 27 28 /** 29 * <p>Ultralightweight C++ implementation of a <tt>void*</tt> vector 30 * that is (mostly) compatible with java.util.Vector. 31 * 32 * <p>This is a very simple implementation, written to satisfy an 33 * immediate porting need. As such, it is not completely fleshed out, 34 * and it aims for simplicity and conformity. Nonetheless, it serves 35 * its purpose (porting code from java that uses java.util.Vector) 36 * well, and it could be easily made into a more robust vector class. 37 * 38 * <p><b>Design notes</b> 39 * 40 * <p>There is index bounds checking, but little is done about it. If 41 * indices are out of bounds, either nothing happens, or zero is 42 * returned. We <em>do</em> avoid indexing off into the weeds. 43 * 44 * <p>There is detection of out of memory, but the handling is very 45 * coarse-grained -- similar to UnicodeString's protocol, but even 46 * coarser. The class contains <em>one static flag</em> that is set 47 * when any call to <tt>new</tt> returns zero. This allows the caller 48 * to use several vectors and make just one check at the end to see if 49 * a memory failure occurred. This is more efficient than making a 50 * check after each call on each vector when doing many operations on 51 * multiple vectors. The single static flag works best when memory 52 * failures are infrequent, and when recovery options are limited or 53 * nonexistent. 54 * 55 * <p><b>To do</b> 56 * 57 * <p>Improve the handling of index out of bounds errors. 58 * 59 * @author Alan Liu 60 */ 61 class U_COMMON_API UVector32 : public UObject { 62 private: 63 int32_t count; 64 65 int32_t capacity; 66 67 int32_t maxCapacity; // Limit beyond which capacity is not permitted to grow. 68 69 int32_t* elements; 70 71 public: 72 UVector32(UErrorCode &status); 73 74 UVector32(int32_t initialCapacity, UErrorCode &status); 75 76 virtual ~UVector32(); 77 78 /** 79 * Assign this object to another (make this a copy of 'other'). 80 * Use the 'assign' function to assign each element. 81 */ 82 void assign(const UVector32& other, UErrorCode &ec); 83 84 /** 85 * Compare this vector with another. They will be considered 86 * equal if they are of the same size and all elements are equal, 87 * as compared using this object's comparer. 88 */ 89 UBool operator==(const UVector32& other); 90 91 /** 92 * Equivalent to !operator==() 93 */ 94 inline UBool operator!=(const UVector32& other); 95 96 //------------------------------------------------------------ 97 // java.util.Vector API 98 //------------------------------------------------------------ 99 100 void addElement(int32_t elem, UErrorCode &status); 101 102 void setElementAt(int32_t elem, int32_t index); 103 104 void insertElementAt(int32_t elem, int32_t index, UErrorCode &status); 105 106 int32_t elementAti(int32_t index) const; 107 108 UBool equals(const UVector32 &other) const; 109 110 int32_t lastElementi(void) const; 111 112 int32_t indexOf(int32_t elem, int32_t startIndex = 0) const; 113 114 UBool contains(int32_t elem) const; 115 116 UBool containsAll(const UVector32& other) const; 117 118 UBool removeAll(const UVector32& other); 119 120 UBool retainAll(const UVector32& other); 121 122 void removeElementAt(int32_t index); 123 124 void removeAllElements(); 125 126 int32_t size(void) const; 127 128 UBool isEmpty(void) const; 129 130 // Inline. Use this one for speedy size check. 131 inline UBool ensureCapacity(int32_t minimumCapacity, UErrorCode &status); 132 133 // Out-of-line, handles actual growth. Called by ensureCapacity() when necessary. 134 UBool expandCapacity(int32_t minimumCapacity, UErrorCode &status); 135 136 /** 137 * Change the size of this vector as follows: If newSize is 138 * smaller, then truncate the array, possibly deleting held 139 * elements for i >= newSize. If newSize is larger, grow the 140 * array, filling in new slows with zero. 141 */ 142 void setSize(int32_t newSize); 143 144 //------------------------------------------------------------ 145 // New API 146 //------------------------------------------------------------ 147 148 /** 149 * Returns true if this vector contains none of the elements 150 * of the given vector. 151 * @param other vector to be checked for containment 152 * @return true if the test condition is met 153 */ 154 UBool containsNone(const UVector32& other) const; 155 156 157 /** 158 * Insert the given integer into this vector at its sorted position. 159 * The current elements are assumed to be sorted already. 160 */ 161 void sortedInsert(int32_t elem, UErrorCode& ec); 162 163 /** 164 * Returns a pointer to the internal array holding the vector. 165 */ 166 int32_t *getBuffer() const; 167 168 /** 169 * Set the maximum allowed buffer capacity for this vector/stack. 170 * Default with no limit set is unlimited, go until malloc() fails. 171 * A Limit of zero means unlimited capacity. 172 * Units are vector elements (32 bits each), not bytes. 173 */ 174 void setMaxCapacity(int32_t limit); 175 176 /** 177 * ICU "poor man's RTTI", returns a UClassID for this class. 178 */ 179 static UClassID U_EXPORT2 getStaticClassID(); 180 181 /** 182 * ICU "poor man's RTTI", returns a UClassID for the actual class. 183 */ 184 virtual UClassID getDynamicClassID() const; 185 186 private: 187 void _init(int32_t initialCapacity, UErrorCode &status); 188 189 // Disallow 190 UVector32(const UVector32&); 191 192 // Disallow 193 UVector32& operator=(const UVector32&); 194 195 196 // API Functions for Stack operations. 197 // In the original UVector, these were in a separate derived class, UStack. 198 // Here in UVector32, they are all together. 199 public: 200 UBool empty(void) const; // TODO: redundant, same as empty(). Remove it? 201 202 int32_t peeki(void) const; 203 204 int32_t popi(void); 205 206 int32_t push(int32_t i, UErrorCode &status); 207 208 int32_t *reserveBlock(int32_t size, UErrorCode &status); 209 int32_t *popFrame(int32_t size); 210 }; 211 212 213 // UVector32 inlines 214 215 inline UBool UVector32::ensureCapacity(int32_t minimumCapacity, UErrorCode &status) { 216 if ((minimumCapacity >= 0) && (capacity >= minimumCapacity)) { 217 return TRUE; 218 } else { 219 return expandCapacity(minimumCapacity, status); 220 } 221 } 222 223 inline int32_t UVector32::elementAti(int32_t index) const { 224 return (index >= 0 && count > 0 && count - index > 0) ? elements[index] : 0; 225 } 226 227 228 inline void UVector32::addElement(int32_t elem, UErrorCode &status) { 229 if (ensureCapacity(count + 1, status)) { 230 elements[count] = elem; 231 count++; 232 } 233 } 234 235 inline int32_t *UVector32::reserveBlock(int32_t size, UErrorCode &status) { 236 if (ensureCapacity(count+size, status) == FALSE) { 237 return NULL; 238 } 239 int32_t *rp = elements+count; 240 count += size; 241 return rp; 242 } 243 244 inline int32_t *UVector32::popFrame(int32_t size) { 245 U_ASSERT(count >= size); 246 count -= size; 247 if (count < 0) { 248 count = 0; 249 } 250 return elements+count-size; 251 } 252 253 254 255 inline int32_t UVector32::size(void) const { 256 return count; 257 } 258 259 inline UBool UVector32::isEmpty(void) const { 260 return count == 0; 261 } 262 263 inline UBool UVector32::contains(int32_t obj) const { 264 return indexOf(obj) >= 0; 265 } 266 267 inline int32_t UVector32::lastElementi(void) const { 268 return elementAti(count-1); 269 } 270 271 inline UBool UVector32::operator!=(const UVector32& other) { 272 return !operator==(other); 273 } 274 275 inline int32_t *UVector32::getBuffer() const { 276 return elements; 277 } 278 279 280 // UStack inlines 281 282 inline UBool UVector32::empty(void) const { 283 return isEmpty(); 284 } 285 286 inline int32_t UVector32::peeki(void) const { 287 return lastElementi(); 288 } 289 290 inline int32_t UVector32::push(int32_t i, UErrorCode &status) { 291 addElement(i, status); 292 return i; 293 } 294 295 inline int32_t UVector32::popi(void) { 296 int32_t result = 0; 297 if (count > 0) { 298 count--; 299 result = elements[count]; 300 } 301 return result; 302 } 303 304 U_NAMESPACE_END 305 306 #endif 307