1/*
2**********************************************************************
3*   Copyright (C) 1999-2009, International Business Machines
4*   Corporation and others.  All Rights Reserved.
5**********************************************************************
6*   Date        Name        Description
7*   10/22/99    alan        Creation.  This is an internal header.
8*                           It should not be exported.
9**********************************************************************
10*/
11
12#ifndef UVECTOR_H
13#define UVECTOR_H
14
15#include "unicode/utypes.h"
16#include "unicode/uobject.h"
17#include "uhash.h"
18
19U_NAMESPACE_BEGIN
20
21/**
22 * A token comparison function.
23 * @param tok1 A token (object or integer)
24 * @param tok2 A token (object or integer)
25 * @return 0 if the two tokens are equal, -1 if tok1 is < tok2, or
26 * +1 if tok1 is > tok2.
27 */
28typedef int8_t U_CALLCONV USortComparator(UHashTok tok1,
29                                          UHashTok tok2);
30
31/**
32 * A token assignment function.  It may copy an integer, copy
33 * a pointer, or clone a pointer, as appropriate.
34 * @param dst The token to be assigned to
35 * @param src The token to assign from
36 */
37typedef void U_CALLCONV UTokenAssigner(UHashTok *dst,
38                                       UHashTok *src);
39
40/**
41 * <p>Ultralightweight C++ implementation of a <tt>void*</tt> vector
42 * that is (mostly) compatible with java.util.Vector.
43 *
44 * <p>This is a very simple implementation, written to satisfy an
45 * immediate porting need.  As such, it is not completely fleshed out,
46 * and it aims for simplicity and conformity.  Nonetheless, it serves
47 * its purpose (porting code from java that uses java.util.Vector)
48 * well, and it could be easily made into a more robust vector class.
49 *
50 * <p><b>Design notes</b>
51 *
52 * <p>There is index bounds checking, but little is done about it.  If
53 * indices are out of bounds, either nothing happens, or zero is
54 * returned.  We <em>do</em> avoid indexing off into the weeds.
55 *
56 * <p>There is detection of out of memory, but the handling is very
57 * coarse-grained -- similar to UnicodeString's protocol, but even
58 * coarser.  The class contains <em>one static flag</em> that is set
59 * when any call to <tt>new</tt> returns zero.  This allows the caller
60 * to use several vectors and make just one check at the end to see if
61 * a memory failure occurred.  This is more efficient than making a
62 * check after each call on each vector when doing many operations on
63 * multiple vectors.  The single static flag works best when memory
64 * failures are infrequent, and when recovery options are limited or
65 * nonexistent.
66 *
67 * <p>Since we don't have garbage collection, UVector was given the
68 * option to <em>own</em>its contents.  To employ this, set a deleter
69 * function.  The deleter is called on a void* pointer when that
70 * pointer is released by the vector, either when the vector itself is
71 * destructed, or when a call to setElementAt() overwrites an element,
72 * or when a call to remove() or one of its variants explicitly
73 * removes an element.  If no deleter is set, or the deleter is set to
74 * zero, then it is assumed that the caller will delete elements as
75 * needed.
76 *
77 * <p>In order to implement methods such as contains() and indexOf(),
78 * UVector needs a way to compare objects for equality.  To do so, it
79 * uses a comparison frunction, or "comparer."  If the comparer is not
80 * set, or is set to zero, then all such methods will act as if the
81 * vector contains no element.  That is, indexOf() will always return
82 * -1, contains() will always return FALSE, etc.
83 *
84 * <p><b>To do</b>
85 *
86 * <p>Improve the handling of index out of bounds errors.
87 *
88 * @author Alan Liu
89 */
90class U_COMMON_API UVector : public UObject {
91    // NOTE: UVector uses the UHashKey (union of void* and int32_t) as
92    // its basic storage type.  It uses UKeyComparator as its
93    // comparison function.  It uses UObjectDeleter as its deleter
94    // function.  These are named for hashtables, but used here as-is
95    // rather than duplicating the type.  This allows sharing of
96    // support functions.
97
98private:
99    int32_t count;
100
101    int32_t capacity;
102
103    UHashTok* elements;
104
105    UObjectDeleter *deleter;
106
107    UKeyComparator *comparer;
108
109public:
110    UVector(UErrorCode &status);
111
112    UVector(int32_t initialCapacity, UErrorCode &status);
113
114    UVector(UObjectDeleter *d, UKeyComparator *c, UErrorCode &status);
115
116    UVector(UObjectDeleter *d, UKeyComparator *c, int32_t initialCapacity, UErrorCode &status);
117
118    virtual ~UVector();
119
120    /**
121     * Assign this object to another (make this a copy of 'other').
122     * Use the 'assign' function to assign each element.
123     */
124    void assign(const UVector& other, UTokenAssigner *assign, UErrorCode &ec);
125
126    /**
127     * Compare this vector with another.  They will be considered
128     * equal if they are of the same size and all elements are equal,
129     * as compared using this object's comparer.
130     */
131    UBool operator==(const UVector& other);
132
133    /**
134     * Equivalent to !operator==()
135     */
136    inline UBool operator!=(const UVector& other);
137
138    //------------------------------------------------------------
139    // java.util.Vector API
140    //------------------------------------------------------------
141
142    void addElement(void* obj, UErrorCode &status);
143
144    void addElement(int32_t elem, UErrorCode &status);
145
146    void setElementAt(void* obj, int32_t index);
147
148    void setElementAt(int32_t elem, int32_t index);
149
150    void insertElementAt(void* obj, int32_t index, UErrorCode &status);
151
152    void insertElementAt(int32_t elem, int32_t index, UErrorCode &status);
153
154    void* elementAt(int32_t index) const;
155
156    int32_t elementAti(int32_t index) const;
157
158    UBool equals(const UVector &other) const;
159
160    void* firstElement(void) const;
161
162    void* lastElement(void) const;
163
164    int32_t lastElementi(void) const;
165
166    int32_t indexOf(void* obj, int32_t startIndex = 0) const;
167
168    int32_t indexOf(int32_t obj, int32_t startIndex = 0) const;
169
170    UBool contains(void* obj) const;
171
172    UBool contains(int32_t obj) const;
173
174    UBool containsAll(const UVector& other) const;
175
176    UBool removeAll(const UVector& other);
177
178    UBool retainAll(const UVector& other);
179
180    void removeElementAt(int32_t index);
181
182    UBool removeElement(void* obj);
183
184    void removeAllElements();
185
186    int32_t size(void) const;
187
188    UBool isEmpty(void) const;
189
190    UBool ensureCapacity(int32_t minimumCapacity, UErrorCode &status);
191
192    /**
193     * Change the size of this vector as follows: If newSize is
194     * smaller, then truncate the array, possibly deleting held
195     * elements for i >= newSize.  If newSize is larger, grow the
196     * array, filling in new slots with NULL.
197     */
198    void setSize(int32_t newSize, UErrorCode &status);
199
200    /**
201     * Fill in the given array with all elements of this vector.
202     */
203    void** toArray(void** result) const;
204
205    //------------------------------------------------------------
206    // New API
207    //------------------------------------------------------------
208
209    UObjectDeleter *setDeleter(UObjectDeleter *d);
210
211    UKeyComparator *setComparer(UKeyComparator *c);
212
213    void* operator[](int32_t index) const;
214
215    /**
216     * Removes the element at the given index from this vector and
217     * transfer ownership of it to the caller.  After this call, the
218     * caller owns the result and must delete it and the vector entry
219     * at 'index' is removed, shifting all subsequent entries back by
220     * one index and shortening the size of the vector by one.  If the
221     * index is out of range or if there is no item at the given index
222     * then 0 is returned and the vector is unchanged.
223     */
224    void* orphanElementAt(int32_t index);
225
226    /**
227     * Returns true if this vector contains none of the elements
228     * of the given vector.
229     * @param other vector to be checked for containment
230     * @return true if the test condition is met
231     */
232    UBool containsNone(const UVector& other) const;
233
234    /**
235     * Insert the given object into this vector at its sorted position
236     * as defined by 'compare'.  The current elements are assumed to
237     * be sorted already.
238     */
239    void sortedInsert(void* obj, USortComparator *compare, UErrorCode& ec);
240
241    /**
242     * Insert the given integer into this vector at its sorted position
243     * as defined by 'compare'.  The current elements are assumed to
244     * be sorted already.
245     */
246    void sortedInsert(int32_t obj, USortComparator *compare, UErrorCode& ec);
247
248    /**
249     * Sort the contents of the vector, assuming that the contents of the
250     * vector are of type int32_t.
251     */
252    void sorti(UErrorCode &ec);
253
254    /**
255      * Sort the contents of this vector, using a caller-supplied function
256      * to do the comparisons.  (It's confusing that
257      *  UVector's USortComparator function is different from the
258      *  UComparator function type defined in uarrsort.h)
259      */
260    void sort(USortComparator *compare, UErrorCode &ec);
261
262    /**
263     * ICU "poor man's RTTI", returns a UClassID for this class.
264     */
265    static UClassID U_EXPORT2 getStaticClassID();
266
267    /**
268     * ICU "poor man's RTTI", returns a UClassID for the actual class.
269     */
270    virtual UClassID getDynamicClassID() const;
271
272private:
273    void _init(int32_t initialCapacity, UErrorCode &status);
274
275    int32_t indexOf(UHashTok key, int32_t startIndex = 0, int8_t hint = 0) const;
276
277    void sortedInsert(UHashTok tok, USortComparator *compare, UErrorCode& ec);
278
279    // Disallow
280    UVector(const UVector&);
281
282    // Disallow
283    UVector& operator=(const UVector&);
284
285};
286
287
288/**
289 * <p>Ultralightweight C++ implementation of a <tt>void*</tt> stack
290 * that is (mostly) compatible with java.util.Stack.  As in java, this
291 * is merely a paper thin layer around UVector.  See the UVector
292 * documentation for further information.
293 *
294 * <p><b>Design notes</b>
295 *
296 * <p>The element at index <tt>n-1</tt> is (of course) the top of the
297 * stack.
298 *
299 * <p>The poorly named <tt>empty()</tt> method doesn't empty the
300 * stack; it determines if the stack is empty.
301 *
302 * @author Alan Liu
303 */
304class U_COMMON_API UStack : public UVector {
305public:
306    UStack(UErrorCode &status);
307
308    UStack(int32_t initialCapacity, UErrorCode &status);
309
310    UStack(UObjectDeleter *d, UKeyComparator *c, UErrorCode &status);
311
312    UStack(UObjectDeleter *d, UKeyComparator *c, int32_t initialCapacity, UErrorCode &status);
313
314    virtual ~UStack();
315
316    // It's okay not to have a virtual destructor (in UVector)
317    // because UStack has no special cleanup to do.
318
319    UBool empty(void) const;
320
321    void* peek(void) const;
322
323    int32_t peeki(void) const;
324
325    void* pop(void);
326
327    int32_t popi(void);
328
329    void* push(void* obj, UErrorCode &status);
330
331    int32_t push(int32_t i, UErrorCode &status);
332
333    /*
334    If the object o occurs as an item in this stack,
335    this method returns the 1-based distance from the top of the stack.
336    */
337    int32_t search(void* obj) const;
338
339    /**
340     * ICU "poor man's RTTI", returns a UClassID for this class.
341     */
342    static UClassID U_EXPORT2 getStaticClassID();
343
344    /**
345     * ICU "poor man's RTTI", returns a UClassID for the actual class.
346     */
347    virtual UClassID getDynamicClassID() const;
348
349private:
350    // Disallow
351    UStack(const UStack&);
352
353    // Disallow
354    UStack& operator=(const UStack&);
355};
356
357
358// UVector inlines
359
360inline int32_t UVector::size(void) const {
361    return count;
362}
363
364inline UBool UVector::isEmpty(void) const {
365    return count == 0;
366}
367
368inline UBool UVector::contains(void* obj) const {
369    return indexOf(obj) >= 0;
370}
371
372inline UBool UVector::contains(int32_t obj) const {
373    return indexOf(obj) >= 0;
374}
375
376inline void* UVector::firstElement(void) const {
377    return elementAt(0);
378}
379
380inline void* UVector::lastElement(void) const {
381    return elementAt(count-1);
382}
383
384inline int32_t UVector::lastElementi(void) const {
385    return elementAti(count-1);
386}
387
388inline void* UVector::operator[](int32_t index) const {
389    return elementAt(index);
390}
391
392inline UBool UVector::operator!=(const UVector& other) {
393    return !operator==(other);
394}
395
396// UStack inlines
397
398inline UBool UStack::empty(void) const {
399    return isEmpty();
400}
401
402inline void* UStack::peek(void) const {
403    return lastElement();
404}
405
406inline int32_t UStack::peeki(void) const {
407    return lastElementi();
408}
409
410inline void* UStack::push(void* obj, UErrorCode &status) {
411    addElement(obj, status);
412    return obj;
413}
414
415inline int32_t UStack::push(int32_t i, UErrorCode &status) {
416    addElement(i, status);
417    return i;
418}
419
420U_NAMESPACE_END
421
422#endif
423