Line data Source code
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-2011, International Business Machines
6 : * Corporation and others. All Rights Reserved.
7 : **********************************************************************
8 : */
9 :
10 : //
11 : // UVector32 is a class implementing a vector of 32 bit integers.
12 : // It is similar to UVector, but holds int32_t values rather than pointers.
13 : // Most of the code is unchanged from UVector.
14 : //
15 :
16 : #ifndef UVECTOR32_H
17 : #define UVECTOR32_H
18 :
19 : #include "unicode/utypes.h"
20 : #include "unicode/uobject.h"
21 : #include "uhash.h"
22 : #include "uassert.h"
23 :
24 : U_NAMESPACE_BEGIN
25 :
26 :
27 :
28 : /**
29 : * <p>Ultralightweight C++ implementation of a <tt>void*</tt> vector
30 : * that is (mostly) compatible with java.util.Vector.
31 : *
32 : * <p>This is a very simple implementation, written to satisfy an
33 : * immediate porting need. As such, it is not completely fleshed out,
34 : * and it aims for simplicity and conformity. Nonetheless, it serves
35 : * its purpose (porting code from java that uses java.util.Vector)
36 : * well, and it could be easily made into a more robust vector class.
37 : *
38 : * <p><b>Design notes</b>
39 : *
40 : * <p>There is index bounds checking, but little is done about it. If
41 : * indices are out of bounds, either nothing happens, or zero is
42 : * returned. We <em>do</em> avoid indexing off into the weeds.
43 : *
44 : * <p>There is detection of out of memory, but the handling is very
45 : * coarse-grained -- similar to UnicodeString's protocol, but even
46 : * coarser. The class contains <em>one static flag</em> that is set
47 : * when any call to <tt>new</tt> returns zero. This allows the caller
48 : * to use several vectors and make just one check at the end to see if
49 : * a memory failure occurred. This is more efficient than making a
50 : * check after each call on each vector when doing many operations on
51 : * multiple vectors. The single static flag works best when memory
52 : * failures are infrequent, and when recovery options are limited or
53 : * nonexistent.
54 : *
55 : * <p><b>To do</b>
56 : *
57 : * <p>Improve the handling of index out of bounds errors.
58 : *
59 : * @author Alan Liu
60 : */
61 : class U_COMMON_API UVector32 : public UObject {
62 : private:
63 : int32_t count;
64 :
65 : int32_t capacity;
66 :
67 : int32_t maxCapacity; // Limit beyond which capacity is not permitted to grow.
68 :
69 : int32_t* elements;
70 :
71 : public:
72 : UVector32(UErrorCode &status);
73 :
74 : UVector32(int32_t initialCapacity, UErrorCode &status);
75 :
76 : virtual ~UVector32();
77 :
78 : /**
79 : * Assign this object to another (make this a copy of 'other').
80 : * Use the 'assign' function to assign each element.
81 : */
82 : void assign(const UVector32& other, UErrorCode &ec);
83 :
84 : /**
85 : * Compare this vector with another. They will be considered
86 : * equal if they are of the same size and all elements are equal,
87 : * as compared using this object's comparer.
88 : */
89 : UBool operator==(const UVector32& other);
90 :
91 : /**
92 : * Equivalent to !operator==()
93 : */
94 : inline UBool operator!=(const UVector32& other);
95 :
96 : //------------------------------------------------------------
97 : // java.util.Vector API
98 : //------------------------------------------------------------
99 :
100 : void addElement(int32_t elem, UErrorCode &status);
101 :
102 : void setElementAt(int32_t elem, int32_t index);
103 :
104 : void insertElementAt(int32_t elem, int32_t index, UErrorCode &status);
105 :
106 : int32_t elementAti(int32_t index) const;
107 :
108 : UBool equals(const UVector32 &other) const;
109 :
110 : int32_t lastElementi(void) const;
111 :
112 : int32_t indexOf(int32_t elem, int32_t startIndex = 0) const;
113 :
114 : UBool contains(int32_t elem) const;
115 :
116 : UBool containsAll(const UVector32& other) const;
117 :
118 : UBool removeAll(const UVector32& other);
119 :
120 : UBool retainAll(const UVector32& other);
121 :
122 : void removeElementAt(int32_t index);
123 :
124 : void removeAllElements();
125 :
126 : int32_t size(void) const;
127 :
128 : UBool isEmpty(void) const;
129 :
130 : // Inline. Use this one for speedy size check.
131 : inline UBool ensureCapacity(int32_t minimumCapacity, UErrorCode &status);
132 :
133 : // Out-of-line, handles actual growth. Called by ensureCapacity() when necessary.
134 : UBool expandCapacity(int32_t minimumCapacity, UErrorCode &status);
135 :
136 : /**
137 : * Change the size of this vector as follows: If newSize is
138 : * smaller, then truncate the array, possibly deleting held
139 : * elements for i >= newSize. If newSize is larger, grow the
140 : * array, filling in new slows with zero.
141 : */
142 : void setSize(int32_t newSize);
143 :
144 : //------------------------------------------------------------
145 : // New API
146 : //------------------------------------------------------------
147 :
148 : /**
149 : * Returns true if this vector contains none of the elements
150 : * of the given vector.
151 : * @param other vector to be checked for containment
152 : * @return true if the test condition is met
153 : */
154 : UBool containsNone(const UVector32& other) const;
155 :
156 :
157 : /**
158 : * Insert the given integer into this vector at its sorted position.
159 : * The current elements are assumed to be sorted already.
160 : */
161 : void sortedInsert(int32_t elem, UErrorCode& ec);
162 :
163 : /**
164 : * Returns a pointer to the internal array holding the vector.
165 : */
166 : int32_t *getBuffer() const;
167 :
168 : /**
169 : * Set the maximum allowed buffer capacity for this vector/stack.
170 : * Default with no limit set is unlimited, go until malloc() fails.
171 : * A Limit of zero means unlimited capacity.
172 : * Units are vector elements (32 bits each), not bytes.
173 : */
174 : void setMaxCapacity(int32_t limit);
175 :
176 : /**
177 : * ICU "poor man's RTTI", returns a UClassID for this class.
178 : */
179 : static UClassID U_EXPORT2 getStaticClassID();
180 :
181 : /**
182 : * ICU "poor man's RTTI", returns a UClassID for the actual class.
183 : */
184 : virtual UClassID getDynamicClassID() const;
185 :
186 : private:
187 : void _init(int32_t initialCapacity, UErrorCode &status);
188 :
189 : // Disallow
190 : UVector32(const UVector32&);
191 :
192 : // Disallow
193 : UVector32& operator=(const UVector32&);
194 :
195 :
196 : // API Functions for Stack operations.
197 : // In the original UVector, these were in a separate derived class, UStack.
198 : // Here in UVector32, they are all together.
199 : public:
200 : UBool empty(void) const; // TODO: redundant, same as empty(). Remove it?
201 :
202 : int32_t peeki(void) const;
203 :
204 : int32_t popi(void);
205 :
206 : int32_t push(int32_t i, UErrorCode &status);
207 :
208 : int32_t *reserveBlock(int32_t size, UErrorCode &status);
209 : int32_t *popFrame(int32_t size);
210 : };
211 :
212 :
213 : // UVector32 inlines
214 :
215 0 : inline UBool UVector32::ensureCapacity(int32_t minimumCapacity, UErrorCode &status) {
216 0 : if ((minimumCapacity >= 0) && (capacity >= minimumCapacity)) {
217 0 : return TRUE;
218 : } else {
219 0 : return expandCapacity(minimumCapacity, status);
220 : }
221 : }
222 :
223 0 : inline int32_t UVector32::elementAti(int32_t index) const {
224 0 : return (index >= 0 && count > 0 && count - index > 0) ? elements[index] : 0;
225 : }
226 :
227 :
228 0 : inline void UVector32::addElement(int32_t elem, UErrorCode &status) {
229 0 : if (ensureCapacity(count + 1, status)) {
230 0 : elements[count] = elem;
231 0 : count++;
232 : }
233 0 : }
234 :
235 : inline int32_t *UVector32::reserveBlock(int32_t size, UErrorCode &status) {
236 : if (ensureCapacity(count+size, status) == FALSE) {
237 : return NULL;
238 : }
239 : int32_t *rp = elements+count;
240 : count += size;
241 : return rp;
242 : }
243 :
244 : inline int32_t *UVector32::popFrame(int32_t size) {
245 : U_ASSERT(count >= size);
246 : count -= size;
247 : if (count < 0) {
248 : count = 0;
249 : }
250 : return elements+count-size;
251 : }
252 :
253 :
254 :
255 0 : inline int32_t UVector32::size(void) const {
256 0 : return count;
257 : }
258 :
259 0 : inline UBool UVector32::isEmpty(void) const {
260 0 : return count == 0;
261 : }
262 :
263 : inline UBool UVector32::contains(int32_t obj) const {
264 : return indexOf(obj) >= 0;
265 : }
266 :
267 : inline int32_t UVector32::lastElementi(void) const {
268 : return elementAti(count-1);
269 : }
270 :
271 : inline UBool UVector32::operator!=(const UVector32& other) {
272 : return !operator==(other);
273 : }
274 :
275 0 : inline int32_t *UVector32::getBuffer() const {
276 0 : return elements;
277 : }
278 :
279 :
280 : // UStack inlines
281 :
282 : inline UBool UVector32::empty(void) const {
283 : return isEmpty();
284 : }
285 :
286 : inline int32_t UVector32::peeki(void) const {
287 : return lastElementi();
288 : }
289 :
290 : inline int32_t UVector32::push(int32_t i, UErrorCode &status) {
291 : addElement(i, status);
292 : return i;
293 : }
294 :
295 : inline int32_t UVector32::popi(void) {
296 : int32_t result = 0;
297 : if (count > 0) {
298 : count--;
299 : result = elements[count];
300 : }
301 : return result;
302 : }
303 :
304 : U_NAMESPACE_END
305 :
306 : #endif
|
