icuSources/common/uvectr32.cpp

   1 /*
   2 ******************************************************************************
   3 * Copyright (C) 1999-2003, International Business Machines Corporation and   *
   4 * others. All Rights Reserved.                                               *
   5 ******************************************************************************
   6 *   Date        Name        Description
   7 *   10/22/99    alan        Creation.
   8 **********************************************************************
   9 */
  10
  11 #include "uvectr32.h"
  12 #include "cmemory.h"
  13
  14 U_NAMESPACE_BEGIN
  15
  16 #define DEFUALT_CAPACITY 8
  17
  18 /*
  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
  22  */
  23
  24 UOBJECT_DEFINE_RTTI_IMPLEMENTATION(UVector32)
  25
  26 UVector32::UVector32(UErrorCode &status) :
  27     count(0),
  28     capacity(0),
  29     elements(NULL)
  30 {
  31     _init(DEFUALT_CAPACITY, status);
  32 }
  33
  34 UVector32::UVector32(int32_t initialCapacity, UErrorCode &status) :
  35     count(0),
  36     capacity(0),
  37     elements(0)
  38 {
  39     _init(initialCapacity, status);
  40 }
  41
  42
  43
  44 void UVector32::_init(int32_t initialCapacity, UErrorCode &status) {
  45     // Fix bogus initialCapacity values; avoid malloc(0)
  46     if (initialCapacity < 1) {
  47         initialCapacity = DEFUALT_CAPACITY;
  48     }
  49     elements = (int32_t *)uprv_malloc(sizeof(int32_t)*initialCapacity);
  50     if (elements == 0) {
  51         status = U_MEMORY_ALLOCATION_ERROR;
  52     } else {
  53         capacity = initialCapacity;
  54     }
  55 }
  56
  57 UVector32::~UVector32() {
  58     uprv_free(elements);
  59     elements = 0;
  60 }
  61
  62 /**
  63  * Assign this object to another (make this a copy of 'other').
  64  */
  65 void UVector32::assign(const UVector32& other, UErrorCode &ec) {
  66     if (ensureCapacity(other.count, ec)) {
  67         setSize(other.count);
  68         for (int32_t i=0; i<other.count; ++i) {
  69             elements[i] = other.elements[i];
  70         }
  71     }
  72 }
  73
  74
  75 UBool UVector32::operator==(const UVector32& other) {
  76     int32_t i;
  77     if (count != other.count) return FALSE;
  78     for (i=0; i<count; ++i) {
  79         if (elements[i] != other.elements[i]) {
  80             return FALSE;
  81         }
  82     }
  83     return TRUE;
  84 }
  85
  86
  87 void UVector32::setElementAt(int32_t elem, int32_t index) {
  88     if (0 <= index && index < count) {
  89         elements[index] = elem;
  90     }
  91     /* else index out of range */
  92 }
  93
  94 void UVector32::insertElementAt(int32_t elem, int32_t index, UErrorCode &status) {
  95     // must have 0 <= index <= count
  96     if (0 <= index && index <= count && ensureCapacity(count + 1, status)) {
  97         for (int32_t i=count; i>index; --i) {
  98             elements[i] = elements[i-1];
  99         }
 100         elements[index] = elem;
 101         ++count;
 102     }
 103     /* else index out of range */
 104 }
 105
 106 UBool UVector32::containsAll(const UVector32& other) const {
 107     for (int32_t i=0; i<other.size(); ++i) {
 108         if (indexOf(other.elements[i]) < 0) {
 109             return FALSE;
 110         }
 111     }
 112     return TRUE;
 113 }
 114
 115 UBool UVector32::containsNone(const UVector32& other) const {
 116     for (int32_t i=0; i<other.size(); ++i) {
 117         if (indexOf(other.elements[i]) >= 0) {
 118             return FALSE;
 119         }
 120     }
 121     return TRUE;
 122 }
 123
 124 UBool UVector32::removeAll(const UVector32& other) {
 125     UBool changed = FALSE;
 126     for (int32_t i=0; i<other.size(); ++i) {
 127         int32_t j = indexOf(other.elements[i]);
 128         if (j >= 0) {
 129             removeElementAt(j);
 130             changed = TRUE;
 131         }
 132     }
 133     return changed;
 134 }
 135
 136 UBool UVector32::retainAll(const UVector32& other) {
 137     UBool changed = FALSE;
 138     for (int32_t j=size()-1; j>=0; --j) {
 139         int32_t i = other.indexOf(elements[j]);
 140         if (i < 0) {
 141             removeElementAt(j);
 142             changed = TRUE;
 143         }
 144     }
 145     return changed;
 146 }
 147
 148 void UVector32::removeElementAt(int32_t index) {
 149     if (index >= 0) {
 150         for (int32_t i=index; i<count-1; ++i) {
 151             elements[i] = elements[i+1];
 152         }
 153         --count;
 154     }
 155 }
 156
 157 void UVector32::removeAllElements(void) {
 158     count = 0;
 159 }
 160
 161 UBool   UVector32::equals(const UVector32 &other) const {
 162     int      i;
 163
 164     if (this->count != other.count) {
 165         return FALSE;
 166     }
 167     for (i=0; i<count; i++) {
 168         if (elements[i] != other.elements[i]) {
 169             return FALSE;
 170         }
 171     }
 172     return TRUE;
 173 }
 174
 175
 176
 177
 178 int32_t UVector32::indexOf(int32_t key, int32_t startIndex) const {
 179     int32_t i;
 180     for (i=startIndex; i<count; ++i) {
 181         if (key == elements[i]) {
 182             return i;
 183         }
 184     }
 185     return -1;
 186 }
 187
 188
 189 UBool UVector32::expandCapacity(int32_t minimumCapacity, UErrorCode &status) {
 190     if (capacity >= minimumCapacity) {
 191         return TRUE;
 192     } else {
 193         int32_t newCap = capacity * 2;
 194         if (newCap < minimumCapacity) {
 195             newCap = minimumCapacity;
 196         }
 197         int32_t* newElems = (int32_t *)uprv_malloc(sizeof(int32_t)*newCap);
 198         if (newElems == 0) {
 199             status = U_MEMORY_ALLOCATION_ERROR;
 200             return FALSE;
 201         }
 202         uprv_memcpy(newElems, elements, sizeof(elements[0]) * count);
 203         uprv_free(elements);
 204         elements = newElems;
 205         capacity = newCap;
 206         return TRUE;
 207     }
 208 }
 209
 210 /**
 211  * Change the size of this vector as follows: If newSize is smaller,
 212  * then truncate the array, possibly deleting held elements for i >=
 213  * newSize.  If newSize is larger, grow the array, filling in new
 214  * slots with NULL.
 215  */
 216 void UVector32::setSize(int32_t newSize) {
 217     int32_t i;
 218     if (newSize < 0) {
 219         return;
 220     }
 221     if (newSize > count) {
 222         UErrorCode ec = U_ZERO_ERROR;
 223         if (!ensureCapacity(newSize, ec)) {
 224             return;
 225         }
 226         for (i=count; i<newSize; ++i) {
 227             elements[i] = 0;
 228         }
 229     }
 230     count = newSize;
 231 }
 232
 233
 234
 235
 236 /**
 237  * Insert the given integer into this vector at its sorted position
 238  * as defined by 'compare'.  The current elements are assumed to
 239  * be sorted already.
 240  */
 241 void UVector32::sortedInsert(int32_t tok, UErrorCode& ec) {
 242     // Perform a binary search for the location to insert tok at.  Tok
 243     // will be inserted between two elements a and b such that a <=
 244     // tok && tok < b, where there is a 'virtual' elements[-1] always
 245     // less than tok and a 'virtual' elements[count] always greater
 246     // than tok.
 247     int32_t min = 0, max = count;
 248     while (min != max) {
 249         int32_t probe = (min + max) / 2;
 250         //int8_t c = (*compare)(elements[probe], tok);
 251         //if (c > 0) {
 252         if (elements[probe] > tok) {
 253             max = probe;
 254         } else {
 255             // assert(c <= 0);
 256             min = probe + 1;
 257         }
 258     }
 259     if (ensureCapacity(count + 1, ec)) {
 260         for (int32_t i=count; i>min; --i) {
 261             elements[i] = elements[i-1];
 262         }
 263         elements[min] = tok;
 264         ++count;
 265     }
 266 }
 267
 268
 269
 270
 271
 272 U_NAMESPACE_END
 273