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