Ultralightweight C++ implementation of a void* vector sl@0: * that is (mostly) compatible with java.util.Vector. sl@0: * sl@0: *
This is a very simple implementation, written to satisfy an sl@0: * immediate porting need. As such, it is not completely fleshed out, sl@0: * and it aims for simplicity and conformity. Nonetheless, it serves sl@0: * its purpose (porting code from java that uses java.util.Vector) sl@0: * well, and it could be easily made into a more robust vector class. sl@0: * sl@0: *
Design notes sl@0: * sl@0: *
There is index bounds checking, but little is done about it. If sl@0: * indices are out of bounds, either nothing happens, or zero is sl@0: * returned. We do avoid indexing off into the weeds. sl@0: * sl@0: *
There is detection of out of memory, but the handling is very sl@0: * coarse-grained -- similar to UnicodeString's protocol, but even sl@0: * coarser. The class contains one static flag that is set sl@0: * when any call to new returns zero. This allows the caller sl@0: * to use several vectors and make just one check at the end to see if sl@0: * a memory failure occurred. This is more efficient than making a sl@0: * check after each call on each vector when doing many operations on sl@0: * multiple vectors. The single static flag works best when memory sl@0: * failures are infrequent, and when recovery options are limited or sl@0: * nonexistent. sl@0: * sl@0: *
Since we don't have garbage collection, UVector was given the sl@0: * option to ownits contents. To employ this, set a deleter sl@0: * function. The deleter is called on a void* pointer when that sl@0: * pointer is released by the vector, either when the vector itself is sl@0: * destructed, or when a call to setElementAt() overwrites an element, sl@0: * or when a call to remove() or one of its variants explicitly sl@0: * removes an element. If no deleter is set, or the deleter is set to sl@0: * zero, then it is assumed that the caller will delete elements as sl@0: * needed. sl@0: * sl@0: *
In order to implement methods such as contains() and indexOf(), sl@0: * UVector needs a way to compare objects for equality. To do so, it sl@0: * uses a comparison frunction, or "comparer." If the comparer is not sl@0: * set, or is set to zero, then all such methods will act as if the sl@0: * vector contains no element. That is, indexOf() will always return sl@0: * -1, contains() will always return FALSE, etc. sl@0: * sl@0: *
To do sl@0: * sl@0: *
Improve the handling of index out of bounds errors. sl@0: * sl@0: * @author Alan Liu sl@0: */ sl@0: class U_COMMON_API UVector : public UObject { sl@0: // NOTE: UVector uses the UHashKey (union of void* and int32_t) as sl@0: // its basic storage type. It uses UKeyComparator as its sl@0: // comparison function. It uses UObjectDeleter as its deleter sl@0: // function. These are named for hashtables, but used here as-is sl@0: // rather than duplicating the type. This allows sharing of sl@0: // support functions. sl@0: sl@0: private: sl@0: int32_t count; sl@0: sl@0: int32_t capacity; sl@0: sl@0: UHashTok* elements; sl@0: sl@0: UObjectDeleter *deleter; sl@0: sl@0: UKeyComparator *comparer; sl@0: sl@0: public: sl@0: UVector(UErrorCode &status); sl@0: sl@0: UVector(int32_t initialCapacity, UErrorCode &status); sl@0: sl@0: UVector(UObjectDeleter *d, UKeyComparator *c, UErrorCode &status); sl@0: sl@0: UVector(UObjectDeleter *d, UKeyComparator *c, int32_t initialCapacity, UErrorCode &status); sl@0: sl@0: virtual ~UVector(); sl@0: sl@0: /** sl@0: * Assign this object to another (make this a copy of 'other'). sl@0: * Use the 'assign' function to assign each element. sl@0: */ sl@0: void assign(const UVector& other, UTokenAssigner *assign, UErrorCode &ec); sl@0: sl@0: /** sl@0: * Compare this vector with another. They will be considered sl@0: * equal if they are of the same size and all elements are equal, sl@0: * as compared using this object's comparer. sl@0: */ sl@0: UBool operator==(const UVector& other); sl@0: sl@0: /** sl@0: * Equivalent to !operator==() sl@0: */ sl@0: inline UBool operator!=(const UVector& other); sl@0: sl@0: //------------------------------------------------------------ sl@0: // java.util.Vector API sl@0: //------------------------------------------------------------ sl@0: sl@0: void addElement(void* obj, UErrorCode &status); sl@0: sl@0: void addElement(int32_t elem, UErrorCode &status); sl@0: sl@0: void setElementAt(void* obj, int32_t index); sl@0: sl@0: void setElementAt(int32_t elem, int32_t index); sl@0: sl@0: void insertElementAt(void* obj, int32_t index, UErrorCode &status); sl@0: sl@0: void insertElementAt(int32_t elem, int32_t index, UErrorCode &status); sl@0: sl@0: void* elementAt(int32_t index) const; sl@0: sl@0: int32_t elementAti(int32_t index) const; sl@0: sl@0: UBool equals(const UVector &other) const; sl@0: sl@0: void* firstElement(void) const; sl@0: sl@0: void* lastElement(void) const; sl@0: sl@0: int32_t lastElementi(void) const; sl@0: sl@0: int32_t indexOf(void* obj, int32_t startIndex = 0) const; sl@0: sl@0: int32_t indexOf(int32_t obj, int32_t startIndex = 0) const; sl@0: sl@0: UBool contains(void* obj) const; sl@0: sl@0: UBool contains(int32_t obj) const; sl@0: sl@0: UBool containsAll(const UVector& other) const; sl@0: sl@0: UBool removeAll(const UVector& other); sl@0: sl@0: UBool retainAll(const UVector& other); sl@0: sl@0: void removeElementAt(int32_t index); sl@0: sl@0: UBool removeElement(void* obj); sl@0: sl@0: void removeAllElements(); sl@0: sl@0: int32_t size(void) const; sl@0: sl@0: UBool isEmpty(void) const; sl@0: sl@0: UBool ensureCapacity(int32_t minimumCapacity, UErrorCode &status); sl@0: sl@0: /** sl@0: * Change the size of this vector as follows: If newSize is sl@0: * smaller, then truncate the array, possibly deleting held sl@0: * elements for i >= newSize. If newSize is larger, grow the sl@0: * array, filling in new slows with NULL. sl@0: */ sl@0: void setSize(int32_t newSize); sl@0: sl@0: /** sl@0: * Fill in the given array with all elements of this vector. sl@0: */ sl@0: void** toArray(void** result) const; sl@0: sl@0: //------------------------------------------------------------ sl@0: // New API sl@0: //------------------------------------------------------------ sl@0: sl@0: UObjectDeleter *setDeleter(UObjectDeleter *d); sl@0: sl@0: UKeyComparator *setComparer(UKeyComparator *c); sl@0: sl@0: void* operator[](int32_t index) const; sl@0: sl@0: /** sl@0: * Removes the element at the given index from this vector and sl@0: * transfer ownership of it to the caller. After this call, the sl@0: * caller owns the result and must delete it and the vector entry sl@0: * at 'index' is removed, shifting all subsequent entries back by sl@0: * one index and shortening the size of the vector by one. If the sl@0: * index is out of range or if there is no item at the given index sl@0: * then 0 is returned and the vector is unchanged. sl@0: */ sl@0: void* orphanElementAt(int32_t index); sl@0: sl@0: /** sl@0: * Returns true if this vector contains none of the elements sl@0: * of the given vector. sl@0: * @param other vector to be checked for containment sl@0: * @return true if the test condition is met sl@0: */ sl@0: UBool containsNone(const UVector& other) const; sl@0: sl@0: /** sl@0: * Insert the given object into this vector at its sorted position sl@0: * as defined by 'compare'. The current elements are assumed to sl@0: * be sorted already. sl@0: */ sl@0: void sortedInsert(void* obj, USortComparator *compare, UErrorCode& ec); sl@0: sl@0: /** sl@0: * Insert the given integer into this vector at its sorted position sl@0: * as defined by 'compare'. The current elements are assumed to sl@0: * be sorted already. sl@0: */ sl@0: void sortedInsert(int32_t obj, USortComparator *compare, UErrorCode& ec); sl@0: sl@0: /** sl@0: * ICU "poor man's RTTI", returns a UClassID for this class. sl@0: * sl@0: * @draft ICU 2.2 sl@0: */ sl@0: static UClassID U_EXPORT2 getStaticClassID(); sl@0: sl@0: /** sl@0: * ICU "poor man's RTTI", returns a UClassID for the actual class. sl@0: * sl@0: * @draft ICU 2.2 sl@0: */ sl@0: virtual UClassID getDynamicClassID() const; sl@0: sl@0: private: sl@0: void _init(int32_t initialCapacity, UErrorCode &status); sl@0: sl@0: int32_t indexOf(UHashTok key, int32_t startIndex = 0, int8_t hint = 0) const; sl@0: sl@0: void sortedInsert(UHashTok tok, USortComparator *compare, UErrorCode& ec); sl@0: sl@0: // Disallow sl@0: UVector(const UVector&); sl@0: sl@0: // Disallow sl@0: UVector& operator=(const UVector&); sl@0: sl@0: }; sl@0: sl@0: sl@0: /** sl@0: *
Ultralightweight C++ implementation of a void* stack sl@0: * that is (mostly) compatible with java.util.Stack. As in java, this sl@0: * is merely a paper thin layer around UVector. See the UVector sl@0: * documentation for further information. sl@0: * sl@0: *
Design notes sl@0: * sl@0: *
The element at index n-1 is (of course) the top of the sl@0: * stack. sl@0: * sl@0: *
The poorly named empty() method doesn't empty the sl@0: * stack; it determines if the stack is empty. sl@0: * sl@0: * @author Alan Liu sl@0: */ sl@0: class U_COMMON_API UStack : public UVector { sl@0: public: sl@0: UStack(UErrorCode &status); sl@0: sl@0: UStack(int32_t initialCapacity, UErrorCode &status); sl@0: sl@0: UStack(UObjectDeleter *d, UKeyComparator *c, UErrorCode &status); sl@0: sl@0: UStack(UObjectDeleter *d, UKeyComparator *c, int32_t initialCapacity, UErrorCode &status); sl@0: sl@0: virtual ~UStack(); sl@0: sl@0: // It's okay not to have a virtual destructor (in UVector) sl@0: // because UStack has no special cleanup to do. sl@0: sl@0: UBool empty(void) const; sl@0: sl@0: void* peek(void) const; sl@0: sl@0: int32_t peeki(void) const; sl@0: sl@0: void* pop(void); sl@0: sl@0: int32_t popi(void); sl@0: sl@0: void* push(void* obj, UErrorCode &status); sl@0: sl@0: int32_t push(int32_t i, UErrorCode &status); sl@0: sl@0: /* sl@0: If the object o occurs as an item in this stack, sl@0: this method returns the 1-based distance from the top of the stack. sl@0: */ sl@0: int32_t search(void* obj) const; sl@0: sl@0: /** sl@0: * ICU "poor man's RTTI", returns a UClassID for this class. sl@0: * sl@0: * @draft ICU 2.2 sl@0: */ sl@0: static UClassID U_EXPORT2 getStaticClassID(); sl@0: sl@0: /** sl@0: * ICU "poor man's RTTI", returns a UClassID for the actual class. sl@0: * sl@0: * @draft ICU 2.2 sl@0: */ sl@0: virtual UClassID getDynamicClassID() const; sl@0: sl@0: private: sl@0: // Disallow sl@0: UStack(const UStack&); sl@0: sl@0: // Disallow sl@0: UStack& operator=(const UStack&); sl@0: }; sl@0: sl@0: sl@0: // UVector inlines sl@0: sl@0: inline int32_t UVector::size(void) const { sl@0: return count; sl@0: } sl@0: sl@0: inline UBool UVector::isEmpty(void) const { sl@0: return count == 0; sl@0: } sl@0: sl@0: inline UBool UVector::contains(void* obj) const { sl@0: return indexOf(obj) >= 0; sl@0: } sl@0: sl@0: inline UBool UVector::contains(int32_t obj) const { sl@0: return indexOf(obj) >= 0; sl@0: } sl@0: sl@0: inline void* UVector::firstElement(void) const { sl@0: return elementAt(0); sl@0: } sl@0: sl@0: inline void* UVector::lastElement(void) const { sl@0: return elementAt(count-1); sl@0: } sl@0: sl@0: inline int32_t UVector::lastElementi(void) const { sl@0: return elementAti(count-1); sl@0: } sl@0: sl@0: inline void* UVector::operator[](int32_t index) const { sl@0: return elementAt(index); sl@0: } sl@0: sl@0: inline UBool UVector::operator!=(const UVector& other) { sl@0: return !operator==(other); sl@0: } sl@0: sl@0: // UStack inlines sl@0: sl@0: inline UBool UStack::empty(void) const { sl@0: return isEmpty(); sl@0: } sl@0: sl@0: inline void* UStack::peek(void) const { sl@0: return lastElement(); sl@0: } sl@0: sl@0: inline int32_t UStack::peeki(void) const { sl@0: return lastElementi(); sl@0: } sl@0: sl@0: inline void* UStack::push(void* obj, UErrorCode &status) { sl@0: addElement(obj, status); sl@0: return obj; sl@0: } sl@0: sl@0: inline int32_t UStack::push(int32_t i, UErrorCode &status) { sl@0: addElement(i, status); sl@0: return i; sl@0: } sl@0: sl@0: U_NAMESPACE_END sl@0: sl@0: #endif