1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/intl/icu/source/common/uvector.h Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,413 @@
1.4 +/*
1.5 +**********************************************************************
1.6 +* Copyright (C) 1999-2013, International Business Machines
1.7 +* Corporation and others. All Rights Reserved.
1.8 +**********************************************************************
1.9 +* Date Name Description
1.10 +* 10/22/99 alan Creation. This is an internal header.
1.11 +* It should not be exported.
1.12 +**********************************************************************
1.13 +*/
1.14 +
1.15 +#ifndef UVECTOR_H
1.16 +#define UVECTOR_H
1.17 +
1.18 +#include "unicode/utypes.h"
1.19 +#include "unicode/uobject.h"
1.20 +#include "cmemory.h"
1.21 +#include "uarrsort.h"
1.22 +#include "uelement.h"
1.23 +
1.24 +U_NAMESPACE_BEGIN
1.25 +
1.26 +/**
1.27 + * <p>Ultralightweight C++ implementation of a <tt>void*</tt> vector
1.28 + * that is (mostly) compatible with java.util.Vector.
1.29 + *
1.30 + * <p>This is a very simple implementation, written to satisfy an
1.31 + * immediate porting need. As such, it is not completely fleshed out,
1.32 + * and it aims for simplicity and conformity. Nonetheless, it serves
1.33 + * its purpose (porting code from java that uses java.util.Vector)
1.34 + * well, and it could be easily made into a more robust vector class.
1.35 + *
1.36 + * <p><b>Design notes</b>
1.37 + *
1.38 + * <p>There is index bounds checking, but little is done about it. If
1.39 + * indices are out of bounds, either nothing happens, or zero is
1.40 + * returned. We <em>do</em> avoid indexing off into the weeds.
1.41 + *
1.42 + * <p>There is detection of out of memory, but the handling is very
1.43 + * coarse-grained -- similar to UnicodeString's protocol, but even
1.44 + * coarser. The class contains <em>one static flag</em> that is set
1.45 + * when any call to <tt>new</tt> returns zero. This allows the caller
1.46 + * to use several vectors and make just one check at the end to see if
1.47 + * a memory failure occurred. This is more efficient than making a
1.48 + * check after each call on each vector when doing many operations on
1.49 + * multiple vectors. The single static flag works best when memory
1.50 + * failures are infrequent, and when recovery options are limited or
1.51 + * nonexistent.
1.52 + *
1.53 + * <p>Since we don't have garbage collection, UVector was given the
1.54 + * option to <em>own</em>its contents. To employ this, set a deleter
1.55 + * function. The deleter is called on a void* pointer when that
1.56 + * pointer is released by the vector, either when the vector itself is
1.57 + * destructed, or when a call to setElementAt() overwrites an element,
1.58 + * or when a call to remove() or one of its variants explicitly
1.59 + * removes an element. If no deleter is set, or the deleter is set to
1.60 + * zero, then it is assumed that the caller will delete elements as
1.61 + * needed.
1.62 + *
1.63 + * <p>In order to implement methods such as contains() and indexOf(),
1.64 + * UVector needs a way to compare objects for equality. To do so, it
1.65 + * uses a comparison frunction, or "comparer." If the comparer is not
1.66 + * set, or is set to zero, then all such methods will act as if the
1.67 + * vector contains no element. That is, indexOf() will always return
1.68 + * -1, contains() will always return FALSE, etc.
1.69 + *
1.70 + * <p><b>To do</b>
1.71 + *
1.72 + * <p>Improve the handling of index out of bounds errors.
1.73 + *
1.74 + * @author Alan Liu
1.75 + */
1.76 +class U_COMMON_API UVector : public UObject {
1.77 + // NOTE: UVector uses the UHashKey (union of void* and int32_t) as
1.78 + // its basic storage type. It uses UElementsAreEqual as its
1.79 + // comparison function. It uses UObjectDeleter as its deleter
1.80 + // function. These are named for hashtables, but used here as-is
1.81 + // rather than duplicating the type. This allows sharing of
1.82 + // support functions.
1.83 +
1.84 +private:
1.85 + int32_t count;
1.86 +
1.87 + int32_t capacity;
1.88 +
1.89 + UElement* elements;
1.90 +
1.91 + UObjectDeleter *deleter;
1.92 +
1.93 + UElementsAreEqual *comparer;
1.94 +
1.95 +public:
1.96 + UVector(UErrorCode &status);
1.97 +
1.98 + UVector(int32_t initialCapacity, UErrorCode &status);
1.99 +
1.100 + UVector(UObjectDeleter *d, UElementsAreEqual *c, UErrorCode &status);
1.101 +
1.102 + UVector(UObjectDeleter *d, UElementsAreEqual *c, int32_t initialCapacity, UErrorCode &status);
1.103 +
1.104 + virtual ~UVector();
1.105 +
1.106 + /**
1.107 + * Assign this object to another (make this a copy of 'other').
1.108 + * Use the 'assign' function to assign each element.
1.109 + */
1.110 + void assign(const UVector& other, UElementAssigner *assign, UErrorCode &ec);
1.111 +
1.112 + /**
1.113 + * Compare this vector with another. They will be considered
1.114 + * equal if they are of the same size and all elements are equal,
1.115 + * as compared using this object's comparer.
1.116 + */
1.117 + UBool operator==(const UVector& other);
1.118 +
1.119 + /**
1.120 + * Equivalent to !operator==()
1.121 + */
1.122 + inline UBool operator!=(const UVector& other);
1.123 +
1.124 + //------------------------------------------------------------
1.125 + // java.util.Vector API
1.126 + //------------------------------------------------------------
1.127 +
1.128 + void addElement(void* obj, UErrorCode &status);
1.129 +
1.130 + void addElement(int32_t elem, UErrorCode &status);
1.131 +
1.132 + void setElementAt(void* obj, int32_t index);
1.133 +
1.134 + void setElementAt(int32_t elem, int32_t index);
1.135 +
1.136 + void insertElementAt(void* obj, int32_t index, UErrorCode &status);
1.137 +
1.138 + void insertElementAt(int32_t elem, int32_t index, UErrorCode &status);
1.139 +
1.140 + void* elementAt(int32_t index) const;
1.141 +
1.142 + int32_t elementAti(int32_t index) const;
1.143 +
1.144 + UBool equals(const UVector &other) const;
1.145 +
1.146 + void* firstElement(void) const;
1.147 +
1.148 + void* lastElement(void) const;
1.149 +
1.150 + int32_t lastElementi(void) const;
1.151 +
1.152 + int32_t indexOf(void* obj, int32_t startIndex = 0) const;
1.153 +
1.154 + int32_t indexOf(int32_t obj, int32_t startIndex = 0) const;
1.155 +
1.156 + UBool contains(void* obj) const;
1.157 +
1.158 + UBool contains(int32_t obj) const;
1.159 +
1.160 + UBool containsAll(const UVector& other) const;
1.161 +
1.162 + UBool removeAll(const UVector& other);
1.163 +
1.164 + UBool retainAll(const UVector& other);
1.165 +
1.166 + void removeElementAt(int32_t index);
1.167 +
1.168 + UBool removeElement(void* obj);
1.169 +
1.170 + void removeAllElements();
1.171 +
1.172 + int32_t size(void) const;
1.173 +
1.174 + UBool isEmpty(void) const;
1.175 +
1.176 + UBool ensureCapacity(int32_t minimumCapacity, UErrorCode &status);
1.177 +
1.178 + /**
1.179 + * Change the size of this vector as follows: If newSize is
1.180 + * smaller, then truncate the array, possibly deleting held
1.181 + * elements for i >= newSize. If newSize is larger, grow the
1.182 + * array, filling in new slots with NULL.
1.183 + */
1.184 + void setSize(int32_t newSize, UErrorCode &status);
1.185 +
1.186 + /**
1.187 + * Fill in the given array with all elements of this vector.
1.188 + */
1.189 + void** toArray(void** result) const;
1.190 +
1.191 + //------------------------------------------------------------
1.192 + // New API
1.193 + //------------------------------------------------------------
1.194 +
1.195 + UObjectDeleter *setDeleter(UObjectDeleter *d);
1.196 +
1.197 + UElementsAreEqual *setComparer(UElementsAreEqual *c);
1.198 +
1.199 + void* operator[](int32_t index) const;
1.200 +
1.201 + /**
1.202 + * Removes the element at the given index from this vector and
1.203 + * transfer ownership of it to the caller. After this call, the
1.204 + * caller owns the result and must delete it and the vector entry
1.205 + * at 'index' is removed, shifting all subsequent entries back by
1.206 + * one index and shortening the size of the vector by one. If the
1.207 + * index is out of range or if there is no item at the given index
1.208 + * then 0 is returned and the vector is unchanged.
1.209 + */
1.210 + void* orphanElementAt(int32_t index);
1.211 +
1.212 + /**
1.213 + * Returns true if this vector contains none of the elements
1.214 + * of the given vector.
1.215 + * @param other vector to be checked for containment
1.216 + * @return true if the test condition is met
1.217 + */
1.218 + UBool containsNone(const UVector& other) const;
1.219 +
1.220 + /**
1.221 + * Insert the given object into this vector at its sorted position
1.222 + * as defined by 'compare'. The current elements are assumed to
1.223 + * be sorted already.
1.224 + */
1.225 + void sortedInsert(void* obj, UElementComparator *compare, UErrorCode& ec);
1.226 +
1.227 + /**
1.228 + * Insert the given integer into this vector at its sorted position
1.229 + * as defined by 'compare'. The current elements are assumed to
1.230 + * be sorted already.
1.231 + */
1.232 + void sortedInsert(int32_t obj, UElementComparator *compare, UErrorCode& ec);
1.233 +
1.234 + /**
1.235 + * Sort the contents of the vector, assuming that the contents of the
1.236 + * vector are of type int32_t.
1.237 + */
1.238 + void sorti(UErrorCode &ec);
1.239 +
1.240 + /**
1.241 + * Sort the contents of this vector, using a caller-supplied function
1.242 + * to do the comparisons. (It's confusing that
1.243 + * UVector's UElementComparator function is different from the
1.244 + * UComparator function type defined in uarrsort.h)
1.245 + */
1.246 + void sort(UElementComparator *compare, UErrorCode &ec);
1.247 +
1.248 + /**
1.249 + * Stable sort the contents of this vector using a caller-supplied function
1.250 + * of type UComparator to do the comparison. Provides more flexibility
1.251 + * than UVector::sort() because an additional user parameter can be passed to
1.252 + * the comparison function.
1.253 + */
1.254 + void sortWithUComparator(UComparator *compare, const void *context, UErrorCode &ec);
1.255 +
1.256 + /**
1.257 + * ICU "poor man's RTTI", returns a UClassID for this class.
1.258 + */
1.259 + static UClassID U_EXPORT2 getStaticClassID();
1.260 +
1.261 + /**
1.262 + * ICU "poor man's RTTI", returns a UClassID for the actual class.
1.263 + */
1.264 + virtual UClassID getDynamicClassID() const;
1.265 +
1.266 +private:
1.267 + void _init(int32_t initialCapacity, UErrorCode &status);
1.268 +
1.269 + int32_t indexOf(UElement key, int32_t startIndex = 0, int8_t hint = 0) const;
1.270 +
1.271 + void sortedInsert(UElement e, UElementComparator *compare, UErrorCode& ec);
1.272 +
1.273 + // Disallow
1.274 + UVector(const UVector&);
1.275 +
1.276 + // Disallow
1.277 + UVector& operator=(const UVector&);
1.278 +
1.279 +};
1.280 +
1.281 +
1.282 +/**
1.283 + * <p>Ultralightweight C++ implementation of a <tt>void*</tt> stack
1.284 + * that is (mostly) compatible with java.util.Stack. As in java, this
1.285 + * is merely a paper thin layer around UVector. See the UVector
1.286 + * documentation for further information.
1.287 + *
1.288 + * <p><b>Design notes</b>
1.289 + *
1.290 + * <p>The element at index <tt>n-1</tt> is (of course) the top of the
1.291 + * stack.
1.292 + *
1.293 + * <p>The poorly named <tt>empty()</tt> method doesn't empty the
1.294 + * stack; it determines if the stack is empty.
1.295 + *
1.296 + * @author Alan Liu
1.297 + */
1.298 +class U_COMMON_API UStack : public UVector {
1.299 +public:
1.300 + UStack(UErrorCode &status);
1.301 +
1.302 + UStack(int32_t initialCapacity, UErrorCode &status);
1.303 +
1.304 + UStack(UObjectDeleter *d, UElementsAreEqual *c, UErrorCode &status);
1.305 +
1.306 + UStack(UObjectDeleter *d, UElementsAreEqual *c, int32_t initialCapacity, UErrorCode &status);
1.307 +
1.308 + virtual ~UStack();
1.309 +
1.310 + // It's okay not to have a virtual destructor (in UVector)
1.311 + // because UStack has no special cleanup to do.
1.312 +
1.313 + UBool empty(void) const;
1.314 +
1.315 + void* peek(void) const;
1.316 +
1.317 + int32_t peeki(void) const;
1.318 +
1.319 + void* pop(void);
1.320 +
1.321 + int32_t popi(void);
1.322 +
1.323 + void* push(void* obj, UErrorCode &status);
1.324 +
1.325 + int32_t push(int32_t i, UErrorCode &status);
1.326 +
1.327 + /*
1.328 + If the object o occurs as an item in this stack,
1.329 + this method returns the 1-based distance from the top of the stack.
1.330 + */
1.331 + int32_t search(void* obj) const;
1.332 +
1.333 + /**
1.334 + * ICU "poor man's RTTI", returns a UClassID for this class.
1.335 + */
1.336 + static UClassID U_EXPORT2 getStaticClassID();
1.337 +
1.338 + /**
1.339 + * ICU "poor man's RTTI", returns a UClassID for the actual class.
1.340 + */
1.341 + virtual UClassID getDynamicClassID() const;
1.342 +
1.343 +private:
1.344 + // Disallow
1.345 + UStack(const UStack&);
1.346 +
1.347 + // Disallow
1.348 + UStack& operator=(const UStack&);
1.349 +};
1.350 +
1.351 +
1.352 +// UVector inlines
1.353 +
1.354 +inline int32_t UVector::size(void) const {
1.355 + return count;
1.356 +}
1.357 +
1.358 +inline UBool UVector::isEmpty(void) const {
1.359 + return count == 0;
1.360 +}
1.361 +
1.362 +inline UBool UVector::contains(void* obj) const {
1.363 + return indexOf(obj) >= 0;
1.364 +}
1.365 +
1.366 +inline UBool UVector::contains(int32_t obj) const {
1.367 + return indexOf(obj) >= 0;
1.368 +}
1.369 +
1.370 +inline void* UVector::firstElement(void) const {
1.371 + return elementAt(0);
1.372 +}
1.373 +
1.374 +inline void* UVector::lastElement(void) const {
1.375 + return elementAt(count-1);
1.376 +}
1.377 +
1.378 +inline int32_t UVector::lastElementi(void) const {
1.379 + return elementAti(count-1);
1.380 +}
1.381 +
1.382 +inline void* UVector::operator[](int32_t index) const {
1.383 + return elementAt(index);
1.384 +}
1.385 +
1.386 +inline UBool UVector::operator!=(const UVector& other) {
1.387 + return !operator==(other);
1.388 +}
1.389 +
1.390 +// UStack inlines
1.391 +
1.392 +inline UBool UStack::empty(void) const {
1.393 + return isEmpty();
1.394 +}
1.395 +
1.396 +inline void* UStack::peek(void) const {
1.397 + return lastElement();
1.398 +}
1.399 +
1.400 +inline int32_t UStack::peeki(void) const {
1.401 + return lastElementi();
1.402 +}
1.403 +
1.404 +inline void* UStack::push(void* obj, UErrorCode &status) {
1.405 + addElement(obj, status);
1.406 + return obj;
1.407 +}
1.408 +
1.409 +inline int32_t UStack::push(int32_t i, UErrorCode &status) {
1.410 + addElement(i, status);
1.411 + return i;
1.412 +}
1.413 +
1.414 +U_NAMESPACE_END
1.415 +
1.416 +#endif
