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