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