2 ******************************************************************************
3 * Copyright (C) 1999-2004, International Business Machines Corporation and *
4 * others. All Rights Reserved. *
5 ******************************************************************************
6 * Date Name Description
7 * 10/22/99 alan Creation.
8 **********************************************************************
16 #define DEFUALT_CAPACITY 8
19 * Constants for hinting whether a key is an integer
20 * or a pointer. If a hint bit is zero, then the associated
21 * token is assumed to be an integer. This is needed for iSeries
23 #define HINT_KEY_POINTER (1)
24 #define HINT_KEY_INTEGER (0)
26 UOBJECT_DEFINE_RTTI_IMPLEMENTATION(UVector
)
28 UVector::UVector(UErrorCode
&status
) :
35 _init(DEFUALT_CAPACITY
, status
);
38 UVector::UVector(int32_t initialCapacity
, UErrorCode
&status
) :
45 _init(initialCapacity
, status
);
48 UVector::UVector(UObjectDeleter
*d
, UKeyComparator
*c
, UErrorCode
&status
) :
55 _init(DEFUALT_CAPACITY
, status
);
58 UVector::UVector(UObjectDeleter
*d
, UKeyComparator
*c
, int32_t initialCapacity
, UErrorCode
&status
) :
65 _init(initialCapacity
, status
);
68 void UVector::_init(int32_t initialCapacity
, UErrorCode
&status
) {
69 if (U_FAILURE(status
)) {
72 // Fix bogus initialCapacity values; avoid malloc(0)
73 if (initialCapacity
< 1) {
74 initialCapacity
= DEFUALT_CAPACITY
;
76 elements
= (UHashTok
*)uprv_malloc(sizeof(UHashTok
)*initialCapacity
);
78 status
= U_MEMORY_ALLOCATION_ERROR
;
80 capacity
= initialCapacity
;
91 * Assign this object to another (make this a copy of 'other').
92 * Use the 'assign' function to assign each element.
94 void UVector::assign(const UVector
& other
, UTokenAssigner
*assign
, UErrorCode
&ec
) {
95 if (ensureCapacity(other
.count
, ec
)) {
96 setSize(other
.count
, ec
);
98 for (int32_t i
=0; i
<other
.count
; ++i
) {
99 if (elements
[i
].pointer
!= 0 && deleter
!= 0) {
100 (*deleter
)(elements
[i
].pointer
);
102 (*assign
)(&elements
[i
], &other
.elements
[i
]);
108 // This only does something sensible if this object has a non-null comparer
109 UBool
UVector::operator==(const UVector
& other
) {
111 if (count
!= other
.count
) return FALSE
;
112 if (comparer
!= NULL
) {
113 // Compare using this object's comparer
114 for (i
=0; i
<count
; ++i
) {
115 if (!(*comparer
)(elements
[i
], other
.elements
[i
])) {
123 void UVector::addElement(void* obj
, UErrorCode
&status
) {
124 if (ensureCapacity(count
+ 1, status
)) {
125 elements
[count
++].pointer
= obj
;
129 void UVector::addElement(int32_t elem
, UErrorCode
&status
) {
130 if (ensureCapacity(count
+ 1, status
)) {
131 elements
[count
].pointer
= NULL
; // Pointers may be bigger than ints.
132 elements
[count
].integer
= elem
;
137 void UVector::setElementAt(void* obj
, int32_t index
) {
138 if (0 <= index
&& index
< count
) {
139 if (elements
[index
].pointer
!= 0 && deleter
!= 0) {
140 (*deleter
)(elements
[index
].pointer
);
142 elements
[index
].pointer
= obj
;
144 /* else index out of range */
147 void UVector::setElementAt(int32_t elem
, int32_t index
) {
148 if (0 <= index
&& index
< count
) {
149 if (elements
[index
].pointer
!= 0 && deleter
!= 0) {
150 // TODO: this should be an error. mixing up ints and pointers.
151 (*deleter
)(elements
[index
].pointer
);
153 elements
[index
].pointer
= NULL
;
154 elements
[index
].integer
= elem
;
156 /* else index out of range */
159 void UVector::insertElementAt(void* obj
, int32_t index
, UErrorCode
&status
) {
160 // must have 0 <= index <= count
161 if (0 <= index
&& index
<= count
&& ensureCapacity(count
+ 1, status
)) {
162 for (int32_t i
=count
; i
>index
; --i
) {
163 elements
[i
] = elements
[i
-1];
165 elements
[index
].pointer
= obj
;
168 /* else index out of range */
171 void UVector::insertElementAt(int32_t elem
, int32_t index
, UErrorCode
&status
) {
172 // must have 0 <= index <= count
173 if (0 <= index
&& index
<= count
&& ensureCapacity(count
+ 1, status
)) {
174 for (int32_t i
=count
; i
>index
; --i
) {
175 elements
[i
] = elements
[i
-1];
177 elements
[index
].pointer
= NULL
;
178 elements
[index
].integer
= elem
;
181 /* else index out of range */
184 void* UVector::elementAt(int32_t index
) const {
185 return (0 <= index
&& index
< count
) ? elements
[index
].pointer
: 0;
188 int32_t UVector::elementAti(int32_t index
) const {
189 return (0 <= index
&& index
< count
) ? elements
[index
].integer
: 0;
192 UBool
UVector::containsAll(const UVector
& other
) const {
193 for (int32_t i
=0; i
<other
.size(); ++i
) {
194 if (indexOf(other
.elements
[i
]) < 0) {
201 UBool
UVector::containsNone(const UVector
& other
) const {
202 for (int32_t i
=0; i
<other
.size(); ++i
) {
203 if (indexOf(other
.elements
[i
]) >= 0) {
210 UBool
UVector::removeAll(const UVector
& other
) {
211 UBool changed
= FALSE
;
212 for (int32_t i
=0; i
<other
.size(); ++i
) {
213 int32_t j
= indexOf(other
.elements
[i
]);
222 UBool
UVector::retainAll(const UVector
& other
) {
223 UBool changed
= FALSE
;
224 for (int32_t j
=size()-1; j
>=0; --j
) {
225 int32_t i
= other
.indexOf(elements
[j
]);
234 void UVector::removeElementAt(int32_t index
) {
235 void* e
= orphanElementAt(index
);
236 if (e
!= 0 && deleter
!= 0) {
241 UBool
UVector::removeElement(void* obj
) {
242 int32_t i
= indexOf(obj
);
250 void UVector::removeAllElements(void) {
252 for (int32_t i
=0; i
<count
; ++i
) {
253 if (elements
[i
].pointer
!= 0) {
254 (*deleter
)(elements
[i
].pointer
);
261 UBool
UVector::equals(const UVector
&other
) const {
264 if (this->count
!= other
.count
) {
268 for (i
=0; i
<count
; i
++) {
269 if (elements
[i
].pointer
!= other
.elements
[i
].pointer
) {
275 for (i
=0; i
<count
; i
++) {
276 key
.pointer
= &other
.elements
[i
];
277 if (!(*comparer
)(key
, elements
[i
])) {
287 int32_t UVector::indexOf(void* obj
, int32_t startIndex
) const {
290 return indexOf(key
, startIndex
, HINT_KEY_POINTER
);
293 int32_t UVector::indexOf(int32_t obj
, int32_t startIndex
) const {
296 return indexOf(key
, startIndex
, HINT_KEY_INTEGER
);
299 // This only works if this object has a non-null comparer
300 int32_t UVector::indexOf(UHashTok key
, int32_t startIndex
, int8_t hint
) const {
303 for (i
=startIndex
; i
<count
; ++i
) {
304 if ((*comparer
)(key
, elements
[i
])) {
309 for (i
=startIndex
; i
<count
; ++i
) {
310 /* Pointers are not always the same size as ints so to perform
311 * a valid comparision we need to know whether we are being
312 * provided an int or a pointer. */
313 if (hint
& HINT_KEY_POINTER
) {
314 if (key
.pointer
== elements
[i
].pointer
) {
318 if (key
.integer
== elements
[i
].integer
) {
327 UBool
UVector::ensureCapacity(int32_t minimumCapacity
, UErrorCode
&status
) {
328 if (capacity
< minimumCapacity
) {
329 int32_t newCap
= capacity
* 2;
330 if (newCap
< minimumCapacity
) {
331 newCap
= minimumCapacity
;
333 UHashTok
* newElems
= (UHashTok
*)uprv_realloc(elements
, sizeof(UHashTok
)*newCap
);
334 if (newElems
== NULL
) {
335 // We keep the original contents on the memory failure on realloc.
336 status
= U_MEMORY_ALLOCATION_ERROR
;
346 * Change the size of this vector as follows: If newSize is smaller,
347 * then truncate the array, possibly deleting held elements for i >=
348 * newSize. If newSize is larger, grow the array, filling in new
351 void UVector::setSize(int32_t newSize
, UErrorCode
&status
) {
356 if (newSize
> count
) {
357 if (!ensureCapacity(newSize
, status
)) {
361 empty
.pointer
= NULL
;
363 for (i
=count
; i
<newSize
; ++i
) {
367 /* Most efficient to count down */
368 for (i
=count
-1; i
>=newSize
; --i
) {
376 * Fill in the given array with all elements of this vector.
378 void** UVector::toArray(void** result
) const {
380 for (int i
=0; i
<count
; ++i
) {
381 *a
++ = elements
[i
].pointer
;
386 UObjectDeleter
*UVector::setDeleter(UObjectDeleter
*d
) {
387 UObjectDeleter
*old
= deleter
;
392 UKeyComparator
*UVector::setComparer(UKeyComparator
*d
) {
393 UKeyComparator
*old
= comparer
;
399 * Removes the element at the given index from this vector and
400 * transfer ownership of it to the caller. After this call, the
401 * caller owns the result and must delete it and the vector entry
402 * at 'index' is removed, shifting all subsequent entries back by
403 * one index and shortening the size of the vector by one. If the
404 * index is out of range or if there is no item at the given index
405 * then 0 is returned and the vector is unchanged.
407 void* UVector::orphanElementAt(int32_t index
) {
409 if (0 <= index
&& index
< count
) {
410 e
= elements
[index
].pointer
;
411 for (int32_t i
=index
; i
<count
-1; ++i
) {
412 elements
[i
] = elements
[i
+1];
416 /* else index out of range */
421 * Insert the given object into this vector at its sorted position
422 * as defined by 'compare'. The current elements are assumed to
425 void UVector::sortedInsert(void* obj
, USortComparator
*compare
, UErrorCode
& ec
) {
428 sortedInsert(tok
, compare
, ec
);
432 * Insert the given integer into this vector at its sorted position
433 * as defined by 'compare'. The current elements are assumed to
436 void UVector::sortedInsert(int32_t obj
, USortComparator
*compare
, UErrorCode
& ec
) {
439 sortedInsert(tok
, compare
, ec
);
442 // ASSUME elements[] IS CURRENTLY SORTED
443 void UVector::sortedInsert(UHashTok tok
, USortComparator
*compare
, UErrorCode
& ec
) {
444 // Perform a binary search for the location to insert tok at. Tok
445 // will be inserted between two elements a and b such that a <=
446 // tok && tok < b, where there is a 'virtual' elements[-1] always
447 // less than tok and a 'virtual' elements[count] always greater
449 int32_t min
= 0, max
= count
;
451 int32_t probe
= (min
+ max
) / 2;
452 int8_t c
= (*compare
)(elements
[probe
], tok
);
460 if (ensureCapacity(count
+ 1, ec
)) {
461 for (int32_t i
=count
; i
>min
; --i
) {
462 elements
[i
] = elements
[i
-1];