1b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru/* 2b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru****************************************************************************** 3b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho* Copyright (C) 1999-2011, International Business Machines Corporation and * 4b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru* others. All Rights Reserved. * 5b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru****************************************************************************** 6b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru* Date Name Description 7b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru* 10/22/99 alan Creation. 8b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru********************************************************************** 9b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru*/ 10b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 11b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru#include "uvector.h" 12b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru#include "cmemory.h" 13b0ac937921a2c196d8b9da665135bf6ba01a1ccfJean-Baptiste Queru#include "uarrsort.h" 14b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 15b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste QueruU_NAMESPACE_BEGIN 16b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 1727f654740f2a26ad62a5c155af9199af9e69b889claireho#define DEFAULT_CAPACITY 8 18b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 19b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru/* 20b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * Constants for hinting whether a key is an integer 21b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * or a pointer. If a hint bit is zero, then the associated 22b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * token is assumed to be an integer. This is needed for iSeries 23b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru */ 24b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru#define HINT_KEY_POINTER (1) 25b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru#define HINT_KEY_INTEGER (0) 26b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 27b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste QueruUOBJECT_DEFINE_RTTI_IMPLEMENTATION(UVector) 28b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 29b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste QueruUVector::UVector(UErrorCode &status) : 30b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru count(0), 31b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru capacity(0), 32b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru elements(0), 33b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru deleter(0), 34b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru comparer(0) 35b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru{ 3627f654740f2a26ad62a5c155af9199af9e69b889claireho _init(DEFAULT_CAPACITY, status); 37b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 38b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 39b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste QueruUVector::UVector(int32_t initialCapacity, UErrorCode &status) : 40b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru count(0), 41b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru capacity(0), 42b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru elements(0), 43b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru deleter(0), 44b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru comparer(0) 45b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru{ 46b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru _init(initialCapacity, status); 47b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 48b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 49b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste QueruUVector::UVector(UObjectDeleter *d, UKeyComparator *c, UErrorCode &status) : 50b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru count(0), 51b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru capacity(0), 52b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru elements(0), 53b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru deleter(d), 54b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru comparer(c) 55b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru{ 5627f654740f2a26ad62a5c155af9199af9e69b889claireho _init(DEFAULT_CAPACITY, status); 57b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 58b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 59b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste QueruUVector::UVector(UObjectDeleter *d, UKeyComparator *c, int32_t initialCapacity, UErrorCode &status) : 60b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru count(0), 61b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru capacity(0), 62b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru elements(0), 63b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru deleter(d), 64b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru comparer(c) 65b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru{ 66b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru _init(initialCapacity, status); 67b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 68b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 69b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queruvoid UVector::_init(int32_t initialCapacity, UErrorCode &status) { 70b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (U_FAILURE(status)) { 71b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return; 72b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 7327f654740f2a26ad62a5c155af9199af9e69b889claireho // Fix bogus initialCapacity values; avoid malloc(0) and integer overflow 7427f654740f2a26ad62a5c155af9199af9e69b889claireho if ((initialCapacity < 1) || (initialCapacity > (int32_t)(INT32_MAX / sizeof(UHashTok)))) { 7527f654740f2a26ad62a5c155af9199af9e69b889claireho initialCapacity = DEFAULT_CAPACITY; 76b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 77b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru elements = (UHashTok *)uprv_malloc(sizeof(UHashTok)*initialCapacity); 78b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (elements == 0) { 79b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru status = U_MEMORY_ALLOCATION_ERROR; 80b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } else { 81b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru capacity = initialCapacity; 82b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 83b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 84b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 85b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste QueruUVector::~UVector() { 86b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru removeAllElements(); 87b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru uprv_free(elements); 88b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru elements = 0; 89b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 90b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 91b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru/** 92b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * Assign this object to another (make this a copy of 'other'). 93b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * Use the 'assign' function to assign each element. 94b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru */ 95b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queruvoid UVector::assign(const UVector& other, UTokenAssigner *assign, UErrorCode &ec) { 96b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (ensureCapacity(other.count, ec)) { 97c69afcec261fc345fda8daf46f0ea6b4351dc777Jean-Baptiste Queru setSize(other.count, ec); 98c69afcec261fc345fda8daf46f0ea6b4351dc777Jean-Baptiste Queru if (U_SUCCESS(ec)) { 99c69afcec261fc345fda8daf46f0ea6b4351dc777Jean-Baptiste Queru for (int32_t i=0; i<other.count; ++i) { 100c69afcec261fc345fda8daf46f0ea6b4351dc777Jean-Baptiste Queru if (elements[i].pointer != 0 && deleter != 0) { 101c69afcec261fc345fda8daf46f0ea6b4351dc777Jean-Baptiste Queru (*deleter)(elements[i].pointer); 102c69afcec261fc345fda8daf46f0ea6b4351dc777Jean-Baptiste Queru } 103c69afcec261fc345fda8daf46f0ea6b4351dc777Jean-Baptiste Queru (*assign)(&elements[i], &other.elements[i]); 104b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 105b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 106b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 107b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 108b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 109b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru// This only does something sensible if this object has a non-null comparer 110b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste QueruUBool UVector::operator==(const UVector& other) { 111b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru int32_t i; 112b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (count != other.count) return FALSE; 113b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (comparer != NULL) { 114b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // Compare using this object's comparer 115b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru for (i=0; i<count; ++i) { 116b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (!(*comparer)(elements[i], other.elements[i])) { 117b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return FALSE; 118b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 119b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 120b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 121b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return TRUE; 122b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 123b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 124b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queruvoid UVector::addElement(void* obj, UErrorCode &status) { 125b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (ensureCapacity(count + 1, status)) { 126b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru elements[count++].pointer = obj; 127b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 128b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 129b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 130b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queruvoid UVector::addElement(int32_t elem, UErrorCode &status) { 131b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (ensureCapacity(count + 1, status)) { 132b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru elements[count].pointer = NULL; // Pointers may be bigger than ints. 133b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru elements[count].integer = elem; 134b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru count++; 135b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 136b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 137b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 138b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queruvoid UVector::setElementAt(void* obj, int32_t index) { 139b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (0 <= index && index < count) { 140b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (elements[index].pointer != 0 && deleter != 0) { 141b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru (*deleter)(elements[index].pointer); 142b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 143b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru elements[index].pointer = obj; 144b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 145b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru /* else index out of range */ 146b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 147b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 148b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queruvoid UVector::setElementAt(int32_t elem, int32_t index) { 149b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (0 <= index && index < count) { 150b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (elements[index].pointer != 0 && deleter != 0) { 151b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // TODO: this should be an error. mixing up ints and pointers. 152b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru (*deleter)(elements[index].pointer); 153b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 154b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru elements[index].pointer = NULL; 155b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru elements[index].integer = elem; 156b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 157b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru /* else index out of range */ 158b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 159b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 160b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queruvoid UVector::insertElementAt(void* obj, int32_t index, UErrorCode &status) { 161b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // must have 0 <= index <= count 162b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (0 <= index && index <= count && ensureCapacity(count + 1, status)) { 163b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru for (int32_t i=count; i>index; --i) { 164b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru elements[i] = elements[i-1]; 165b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 166b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru elements[index].pointer = obj; 167b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru ++count; 168b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 169b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru /* else index out of range */ 170b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 171b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 172b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queruvoid UVector::insertElementAt(int32_t elem, int32_t index, UErrorCode &status) { 173b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // must have 0 <= index <= count 174b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (0 <= index && index <= count && ensureCapacity(count + 1, status)) { 175b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru for (int32_t i=count; i>index; --i) { 176b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru elements[i] = elements[i-1]; 177b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 178b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru elements[index].pointer = NULL; 179b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru elements[index].integer = elem; 180b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru ++count; 181b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 182b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru /* else index out of range */ 183b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 184b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 185b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queruvoid* UVector::elementAt(int32_t index) const { 186b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return (0 <= index && index < count) ? elements[index].pointer : 0; 187b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 188b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 189b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queruint32_t UVector::elementAti(int32_t index) const { 190b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return (0 <= index && index < count) ? elements[index].integer : 0; 191b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 192b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 193b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste QueruUBool UVector::containsAll(const UVector& other) const { 194b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru for (int32_t i=0; i<other.size(); ++i) { 195b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (indexOf(other.elements[i]) < 0) { 196b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return FALSE; 197b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 198b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 199b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return TRUE; 200b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 201b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 202b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste QueruUBool UVector::containsNone(const UVector& other) const { 203b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru for (int32_t i=0; i<other.size(); ++i) { 204b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (indexOf(other.elements[i]) >= 0) { 205b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return FALSE; 206b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 207b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 208b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return TRUE; 209b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 210b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 211b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste QueruUBool UVector::removeAll(const UVector& other) { 212b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru UBool changed = FALSE; 213b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru for (int32_t i=0; i<other.size(); ++i) { 214b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru int32_t j = indexOf(other.elements[i]); 215b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (j >= 0) { 216b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru removeElementAt(j); 217b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru changed = TRUE; 218b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 219b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 220b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return changed; 221b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 222b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 223b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste QueruUBool UVector::retainAll(const UVector& other) { 224b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru UBool changed = FALSE; 225b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru for (int32_t j=size()-1; j>=0; --j) { 226b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru int32_t i = other.indexOf(elements[j]); 227b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (i < 0) { 228b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru removeElementAt(j); 229b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru changed = TRUE; 230b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 231b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 232b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return changed; 233b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 234b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 235b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queruvoid UVector::removeElementAt(int32_t index) { 236b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru void* e = orphanElementAt(index); 237b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (e != 0 && deleter != 0) { 238b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru (*deleter)(e); 239b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 240b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 241b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 242b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste QueruUBool UVector::removeElement(void* obj) { 243b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru int32_t i = indexOf(obj); 244b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (i >= 0) { 245b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru removeElementAt(i); 246b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return TRUE; 247b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 248b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return FALSE; 249b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 250b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 251b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queruvoid UVector::removeAllElements(void) { 252b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (deleter != 0) { 253b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru for (int32_t i=0; i<count; ++i) { 254b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (elements[i].pointer != 0) { 255b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru (*deleter)(elements[i].pointer); 256b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 257b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 258b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 259b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru count = 0; 260b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 261b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 262b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste QueruUBool UVector::equals(const UVector &other) const { 263b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru int i; 264b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 265b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (this->count != other.count) { 266b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return FALSE; 267b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 268b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (comparer == 0) { 269b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru for (i=0; i<count; i++) { 270b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (elements[i].pointer != other.elements[i].pointer) { 271b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return FALSE; 272b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 273b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 274b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } else { 275b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru UHashTok key; 276b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru for (i=0; i<count; i++) { 277b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru key.pointer = &other.elements[i]; 278b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (!(*comparer)(key, elements[i])) { 279b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return FALSE; 280b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 281b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 282b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 283b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return TRUE; 284b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 285b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 286b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 287b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 288b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queruint32_t UVector::indexOf(void* obj, int32_t startIndex) const { 289b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru UHashTok key; 290b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru key.pointer = obj; 291b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return indexOf(key, startIndex, HINT_KEY_POINTER); 292b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 293b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 294b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queruint32_t UVector::indexOf(int32_t obj, int32_t startIndex) const { 295b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru UHashTok key; 296b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru key.integer = obj; 297b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return indexOf(key, startIndex, HINT_KEY_INTEGER); 298b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 299b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 300b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru// This only works if this object has a non-null comparer 301b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queruint32_t UVector::indexOf(UHashTok key, int32_t startIndex, int8_t hint) const { 302b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru int32_t i; 303b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (comparer != 0) { 304b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru for (i=startIndex; i<count; ++i) { 305b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if ((*comparer)(key, elements[i])) { 306b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return i; 307b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 308b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 309b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } else { 310b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru for (i=startIndex; i<count; ++i) { 311b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru /* Pointers are not always the same size as ints so to perform 312b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * a valid comparision we need to know whether we are being 313b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * provided an int or a pointer. */ 314b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (hint & HINT_KEY_POINTER) { 315b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (key.pointer == elements[i].pointer) { 316b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return i; 317b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 318b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } else { 319b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (key.integer == elements[i].integer) { 320b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return i; 321b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 322b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 323b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 324b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 325b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return -1; 326b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 327b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 328b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste QueruUBool UVector::ensureCapacity(int32_t minimumCapacity, UErrorCode &status) { 32927f654740f2a26ad62a5c155af9199af9e69b889claireho if (minimumCapacity < 0) { 33027f654740f2a26ad62a5c155af9199af9e69b889claireho status = U_ILLEGAL_ARGUMENT_ERROR; 33127f654740f2a26ad62a5c155af9199af9e69b889claireho return FALSE; 33227f654740f2a26ad62a5c155af9199af9e69b889claireho } 333c69afcec261fc345fda8daf46f0ea6b4351dc777Jean-Baptiste Queru if (capacity < minimumCapacity) { 33427f654740f2a26ad62a5c155af9199af9e69b889claireho if (capacity > (INT32_MAX - 1) / 2) { // integer overflow check 33527f654740f2a26ad62a5c155af9199af9e69b889claireho status = U_ILLEGAL_ARGUMENT_ERROR; 33627f654740f2a26ad62a5c155af9199af9e69b889claireho return FALSE; 33727f654740f2a26ad62a5c155af9199af9e69b889claireho } 338b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru int32_t newCap = capacity * 2; 339b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (newCap < minimumCapacity) { 340b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru newCap = minimumCapacity; 341b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 34227f654740f2a26ad62a5c155af9199af9e69b889claireho if (newCap > (int32_t)(INT32_MAX / sizeof(UHashTok))) { // integer overflow check 34327f654740f2a26ad62a5c155af9199af9e69b889claireho // We keep the original memory contents on bad minimumCapacity. 34427f654740f2a26ad62a5c155af9199af9e69b889claireho status = U_ILLEGAL_ARGUMENT_ERROR; 34527f654740f2a26ad62a5c155af9199af9e69b889claireho return FALSE; 34627f654740f2a26ad62a5c155af9199af9e69b889claireho } 347c69afcec261fc345fda8daf46f0ea6b4351dc777Jean-Baptiste Queru UHashTok* newElems = (UHashTok *)uprv_realloc(elements, sizeof(UHashTok)*newCap); 348c69afcec261fc345fda8daf46f0ea6b4351dc777Jean-Baptiste Queru if (newElems == NULL) { 34927f654740f2a26ad62a5c155af9199af9e69b889claireho // We keep the original contents on the memory failure on realloc or bad minimumCapacity. 350b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru status = U_MEMORY_ALLOCATION_ERROR; 351b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return FALSE; 352b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 353b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru elements = newElems; 354b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru capacity = newCap; 355b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 356c69afcec261fc345fda8daf46f0ea6b4351dc777Jean-Baptiste Queru return TRUE; 357b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 358b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 359b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru/** 360b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * Change the size of this vector as follows: If newSize is smaller, 361b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * then truncate the array, possibly deleting held elements for i >= 362b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * newSize. If newSize is larger, grow the array, filling in new 363b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * slots with NULL. 364b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru */ 365c69afcec261fc345fda8daf46f0ea6b4351dc777Jean-Baptiste Queruvoid UVector::setSize(int32_t newSize, UErrorCode &status) { 366b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru int32_t i; 367b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (newSize < 0) { 368b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return; 369b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 370b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (newSize > count) { 371c69afcec261fc345fda8daf46f0ea6b4351dc777Jean-Baptiste Queru if (!ensureCapacity(newSize, status)) { 372b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return; 373b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 374b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru UHashTok empty; 375b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru empty.pointer = NULL; 376b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru empty.integer = 0; 377b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru for (i=count; i<newSize; ++i) { 378b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru elements[i] = empty; 379b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 380b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } else { 381b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru /* Most efficient to count down */ 382b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru for (i=count-1; i>=newSize; --i) { 383b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru removeElementAt(i); 384b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 385b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 386b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru count = newSize; 387b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 388b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 389b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru/** 390b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * Fill in the given array with all elements of this vector. 391b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru */ 392b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queruvoid** UVector::toArray(void** result) const { 393b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru void** a = result; 394b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru for (int i=0; i<count; ++i) { 395b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru *a++ = elements[i].pointer; 396b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 397b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return result; 398b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 399b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 400b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste QueruUObjectDeleter *UVector::setDeleter(UObjectDeleter *d) { 401b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru UObjectDeleter *old = deleter; 402b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru deleter = d; 403b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return old; 404b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 405b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 406b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste QueruUKeyComparator *UVector::setComparer(UKeyComparator *d) { 407b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru UKeyComparator *old = comparer; 408b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru comparer = d; 409b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return old; 410b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 411b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 412b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru/** 413b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * Removes the element at the given index from this vector and 414b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * transfer ownership of it to the caller. After this call, the 415b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * caller owns the result and must delete it and the vector entry 416b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * at 'index' is removed, shifting all subsequent entries back by 417b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * one index and shortening the size of the vector by one. If the 418b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * index is out of range or if there is no item at the given index 419b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * then 0 is returned and the vector is unchanged. 420b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru */ 421b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queruvoid* UVector::orphanElementAt(int32_t index) { 422b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru void* e = 0; 423b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (0 <= index && index < count) { 424b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru e = elements[index].pointer; 425b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru for (int32_t i=index; i<count-1; ++i) { 426b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru elements[i] = elements[i+1]; 427b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 428b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru --count; 429b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 430b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru /* else index out of range */ 431b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return e; 432b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 433b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 434b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru/** 435b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * Insert the given object into this vector at its sorted position 436b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * as defined by 'compare'. The current elements are assumed to 437b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * be sorted already. 438b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru */ 439b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queruvoid UVector::sortedInsert(void* obj, USortComparator *compare, UErrorCode& ec) { 440b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru UHashTok tok; 441b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru tok.pointer = obj; 442b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru sortedInsert(tok, compare, ec); 443b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 444b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 445b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru/** 446b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * Insert the given integer into this vector at its sorted position 447b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * as defined by 'compare'. The current elements are assumed to 448b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * be sorted already. 449b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru */ 450b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queruvoid UVector::sortedInsert(int32_t obj, USortComparator *compare, UErrorCode& ec) { 451b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru UHashTok tok; 452b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru tok.integer = obj; 453b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru sortedInsert(tok, compare, ec); 454b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 455b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 456b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru// ASSUME elements[] IS CURRENTLY SORTED 457b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queruvoid UVector::sortedInsert(UHashTok tok, USortComparator *compare, UErrorCode& ec) { 458b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // Perform a binary search for the location to insert tok at. Tok 459b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // will be inserted between two elements a and b such that a <= 460b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // tok && tok < b, where there is a 'virtual' elements[-1] always 461b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // less than tok and a 'virtual' elements[count] always greater 462b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // than tok. 463b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru int32_t min = 0, max = count; 464b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru while (min != max) { 465b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru int32_t probe = (min + max) / 2; 466b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru int8_t c = (*compare)(elements[probe], tok); 467b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (c > 0) { 468b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru max = probe; 469b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } else { 470b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // assert(c <= 0); 471b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru min = probe + 1; 472b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 473b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 474b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (ensureCapacity(count + 1, ec)) { 475b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru for (int32_t i=count; i>min; --i) { 476b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru elements[i] = elements[i-1]; 477b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 478b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru elements[min] = tok; 479b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru ++count; 480b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 481b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 482b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 483b0ac937921a2c196d8b9da665135bf6ba01a1ccfJean-Baptiste Queru/** 484b0ac937921a2c196d8b9da665135bf6ba01a1ccfJean-Baptiste Queru * Array sort comparator function. 485b0ac937921a2c196d8b9da665135bf6ba01a1ccfJean-Baptiste Queru * Used from UVector::sort() 486b0ac937921a2c196d8b9da665135bf6ba01a1ccfJean-Baptiste Queru * Conforms to function signature required for uprv_sortArray(). 487b0ac937921a2c196d8b9da665135bf6ba01a1ccfJean-Baptiste Queru * This function is essentially just a wrapper, to make a 488b0ac937921a2c196d8b9da665135bf6ba01a1ccfJean-Baptiste Queru * UVector style comparator function usable with uprv_sortArray(). 489b0ac937921a2c196d8b9da665135bf6ba01a1ccfJean-Baptiste Queru * 490b0ac937921a2c196d8b9da665135bf6ba01a1ccfJean-Baptiste Queru * The context pointer to this function is a pointer back 491b0ac937921a2c196d8b9da665135bf6ba01a1ccfJean-Baptiste Queru * (with some extra indirection) to the user supplied comparator. 492b0ac937921a2c196d8b9da665135bf6ba01a1ccfJean-Baptiste Queru * 493b0ac937921a2c196d8b9da665135bf6ba01a1ccfJean-Baptiste Queru */ 49450294ead5e5d23f5bbfed76e00e6b510bd41eee1clairehostatic int32_t U_CALLCONV 495b0ac937921a2c196d8b9da665135bf6ba01a1ccfJean-Baptiste QuerusortComparator(const void *context, const void *left, const void *right) { 496b0ac937921a2c196d8b9da665135bf6ba01a1ccfJean-Baptiste Queru USortComparator *compare = *static_cast<USortComparator * const *>(context); 497b0ac937921a2c196d8b9da665135bf6ba01a1ccfJean-Baptiste Queru UHashTok tok1 = *static_cast<const UHashTok *>(left); 498b0ac937921a2c196d8b9da665135bf6ba01a1ccfJean-Baptiste Queru UHashTok tok2 = *static_cast<const UHashTok *>(right); 499b0ac937921a2c196d8b9da665135bf6ba01a1ccfJean-Baptiste Queru int32_t result = (*compare)(tok1, tok2); 500b0ac937921a2c196d8b9da665135bf6ba01a1ccfJean-Baptiste Queru return result; 501b0ac937921a2c196d8b9da665135bf6ba01a1ccfJean-Baptiste Queru} 502b0ac937921a2c196d8b9da665135bf6ba01a1ccfJean-Baptiste Queru 503b0ac937921a2c196d8b9da665135bf6ba01a1ccfJean-Baptiste Queru 504b0ac937921a2c196d8b9da665135bf6ba01a1ccfJean-Baptiste Queru/** 505b0ac937921a2c196d8b9da665135bf6ba01a1ccfJean-Baptiste Queru * Array sort comparison function for use from UVector::sorti() 506b0ac937921a2c196d8b9da665135bf6ba01a1ccfJean-Baptiste Queru * Compares int32_t vector elements. 507b0ac937921a2c196d8b9da665135bf6ba01a1ccfJean-Baptiste Queru */ 50850294ead5e5d23f5bbfed76e00e6b510bd41eee1clairehostatic int32_t U_CALLCONV 509b0ac937921a2c196d8b9da665135bf6ba01a1ccfJean-Baptiste QuerusortiComparator(const void * /*context */, const void *left, const void *right) { 510b0ac937921a2c196d8b9da665135bf6ba01a1ccfJean-Baptiste Queru const UHashTok *tok1 = static_cast<const UHashTok *>(left); 511b0ac937921a2c196d8b9da665135bf6ba01a1ccfJean-Baptiste Queru const UHashTok *tok2 = static_cast<const UHashTok *>(right); 512b0ac937921a2c196d8b9da665135bf6ba01a1ccfJean-Baptiste Queru int32_t result = tok1->integer < tok2->integer? -1 : 513b0ac937921a2c196d8b9da665135bf6ba01a1ccfJean-Baptiste Queru tok1->integer == tok2->integer? 0 : 1; 514b0ac937921a2c196d8b9da665135bf6ba01a1ccfJean-Baptiste Queru return result; 515b0ac937921a2c196d8b9da665135bf6ba01a1ccfJean-Baptiste Queru} 516b0ac937921a2c196d8b9da665135bf6ba01a1ccfJean-Baptiste Queru 517b0ac937921a2c196d8b9da665135bf6ba01a1ccfJean-Baptiste Queru/** 518b0ac937921a2c196d8b9da665135bf6ba01a1ccfJean-Baptiste Queru * Sort the vector, assuming it constains ints. 519b0ac937921a2c196d8b9da665135bf6ba01a1ccfJean-Baptiste Queru * (A more general sort would take a comparison function, but it's 520b0ac937921a2c196d8b9da665135bf6ba01a1ccfJean-Baptiste Queru * not clear whether UVector's USortComparator or 521b0ac937921a2c196d8b9da665135bf6ba01a1ccfJean-Baptiste Queru * UComparator from uprv_sortAray would be more appropriate.) 522b0ac937921a2c196d8b9da665135bf6ba01a1ccfJean-Baptiste Queru */ 523b0ac937921a2c196d8b9da665135bf6ba01a1ccfJean-Baptiste Queruvoid UVector::sorti(UErrorCode &ec) { 524b0ac937921a2c196d8b9da665135bf6ba01a1ccfJean-Baptiste Queru if (U_SUCCESS(ec)) { 525b0ac937921a2c196d8b9da665135bf6ba01a1ccfJean-Baptiste Queru uprv_sortArray(elements, count, sizeof(UHashTok), 526b0ac937921a2c196d8b9da665135bf6ba01a1ccfJean-Baptiste Queru sortiComparator, NULL, FALSE, &ec); 527b0ac937921a2c196d8b9da665135bf6ba01a1ccfJean-Baptiste Queru } 528b0ac937921a2c196d8b9da665135bf6ba01a1ccfJean-Baptiste Queru} 529b0ac937921a2c196d8b9da665135bf6ba01a1ccfJean-Baptiste Queru 530b0ac937921a2c196d8b9da665135bf6ba01a1ccfJean-Baptiste Queru 531b0ac937921a2c196d8b9da665135bf6ba01a1ccfJean-Baptiste Queru/** 532b0ac937921a2c196d8b9da665135bf6ba01a1ccfJean-Baptiste Queru * Sort with a user supplied comparator. 533b0ac937921a2c196d8b9da665135bf6ba01a1ccfJean-Baptiste Queru * 534b0ac937921a2c196d8b9da665135bf6ba01a1ccfJean-Baptiste Queru * The comparator function handling is confusing because the function type 535b0ac937921a2c196d8b9da665135bf6ba01a1ccfJean-Baptiste Queru * for UVector (as defined for sortedInsert()) is different from the signature 536b0ac937921a2c196d8b9da665135bf6ba01a1ccfJean-Baptiste Queru * required by uprv_sortArray(). This is handled by passing the 537b0ac937921a2c196d8b9da665135bf6ba01a1ccfJean-Baptiste Queru * the UVector sort function pointer via the context pointer to a 538b0ac937921a2c196d8b9da665135bf6ba01a1ccfJean-Baptiste Queru * sortArray() comparator function, which can then call back to 539b0ac937921a2c196d8b9da665135bf6ba01a1ccfJean-Baptiste Queru * the original user functtion. 540b0ac937921a2c196d8b9da665135bf6ba01a1ccfJean-Baptiste Queru * 541b0ac937921a2c196d8b9da665135bf6ba01a1ccfJean-Baptiste Queru * An additional twist is that it's not safe to pass a pointer-to-function 542b0ac937921a2c196d8b9da665135bf6ba01a1ccfJean-Baptiste Queru * as a (void *) data pointer, so instead we pass a (data) pointer to a 543b0ac937921a2c196d8b9da665135bf6ba01a1ccfJean-Baptiste Queru * pointer-to-function variable. 544b0ac937921a2c196d8b9da665135bf6ba01a1ccfJean-Baptiste Queru */ 545b0ac937921a2c196d8b9da665135bf6ba01a1ccfJean-Baptiste Queruvoid UVector::sort(USortComparator *compare, UErrorCode &ec) { 546b0ac937921a2c196d8b9da665135bf6ba01a1ccfJean-Baptiste Queru if (U_SUCCESS(ec)) { 547b0ac937921a2c196d8b9da665135bf6ba01a1ccfJean-Baptiste Queru uprv_sortArray(elements, count, sizeof(UHashTok), 548b0ac937921a2c196d8b9da665135bf6ba01a1ccfJean-Baptiste Queru sortComparator, &compare, FALSE, &ec); 549b0ac937921a2c196d8b9da665135bf6ba01a1ccfJean-Baptiste Queru } 550b0ac937921a2c196d8b9da665135bf6ba01a1ccfJean-Baptiste Queru} 551b0ac937921a2c196d8b9da665135bf6ba01a1ccfJean-Baptiste Queru 552b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho 553b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho/** 554b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho * Sort with a user supplied comparator of type UComparator. 555b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho */ 556b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehovoid UVector::sortWithUComparator(UComparator *compare, const void *context, UErrorCode &ec) { 557b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if (U_SUCCESS(ec)) { 558b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho uprv_sortArray(elements, count, sizeof(UHashTok), 559b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho compare, context, FALSE, &ec); 560b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 561b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho} 562b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho 563b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste QueruU_NAMESPACE_END 564b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 565