1 /* 2 ******************************************************************************* 3 * Copyright (C) 2010, International Business Machines 4 * Corporation and others. All Rights Reserved. 5 ******************************************************************************* 6 * file name: denseranges.cpp 7 * encoding: US-ASCII 8 * tab size: 8 (not used) 9 * indentation:4 10 * 11 * created on: 2010sep25 12 * created by: Markus W. Scherer 13 * 14 * Helper code for finding a small number of dense ranges. 15 */ 16 17 #include "unicode/utypes.h" 18 #include "denseranges.h" 19 20 // Definitions in the anonymous namespace are invisible outside this file. 21 namespace { 22 23 /** 24 * Collect up to 15 range gaps and sort them by ascending gap size. 25 */ 26 class LargestGaps { 27 public: 28 LargestGaps(int32_t max) : maxLength(max<=kCapacity ? max : kCapacity), length(0) {} 29 30 void add(int32_t gapStart, int64_t gapLength) { 31 int32_t i=length; 32 while(i>0 && gapLength>gapLengths[i-1]) { 33 --i; 34 } 35 if(i<maxLength) { 36 // The new gap is now one of the maxLength largest. 37 // Insert the new gap, moving up smaller ones of the previous 38 // length largest. 39 int32_t j= length<maxLength ? length++ : maxLength-1; 40 while(j>i) { 41 gapStarts[j]=gapStarts[j-1]; 42 gapLengths[j]=gapLengths[j-1]; 43 --j; 44 } 45 gapStarts[i]=gapStart; 46 gapLengths[i]=gapLength; 47 } 48 } 49 50 void truncate(int32_t newLength) { 51 if(newLength<length) { 52 length=newLength; 53 } 54 } 55 56 int32_t count() const { return length; } 57 int32_t gapStart(int32_t i) const { return gapStarts[i]; } 58 int64_t gapLength(int32_t i) const { return gapLengths[i]; } 59 60 int32_t firstAfter(int32_t value) const { 61 if(length==0) { 62 return -1; 63 } 64 int32_t minValue=0; 65 int32_t minIndex=-1; 66 for(int32_t i=0; i<length; ++i) { 67 if(value<gapStarts[i] && (minIndex<0 || gapStarts[i]<minValue)) { 68 minValue=gapStarts[i]; 69 minIndex=i; 70 } 71 } 72 return minIndex; 73 } 74 75 private: 76 static const int32_t kCapacity=15; 77 78 int32_t maxLength; 79 int32_t length; 80 int32_t gapStarts[kCapacity]; 81 int64_t gapLengths[kCapacity]; 82 }; 83 84 } // namespace 85 86 /** 87 * Does it make sense to write 1..capacity ranges? 88 * Returns 0 if not, otherwise the number of ranges. 89 * @param values Sorted array of signed-integer values. 90 * @param length Number of values. 91 * @param density Minimum average range density, in 256th. (0x100=100%=perfectly dense.) 92 * Should be 0x80..0x100, must be 1..0x100. 93 * @param ranges Output ranges array. 94 * @param capacity Maximum number of ranges. 95 * @return Minimum number of ranges (at most capacity) that have the desired density, 96 * or 0 if that density cannot be achieved. 97 */ 98 U_CAPI int32_t U_EXPORT2 99 uprv_makeDenseRanges(const int32_t values[], int32_t length, 100 int32_t density, 101 int32_t ranges[][2], int32_t capacity) { 102 if(length<=2) { 103 return 0; 104 } 105 int32_t minValue=values[0]; 106 int32_t maxValue=values[length-1]; // Assume minValue<=maxValue. 107 // Use int64_t variables for intermediate-value precision and to avoid 108 // signed-int32_t overflow of maxValue-minValue. 109 int64_t maxLength=(int64_t)maxValue-(int64_t)minValue+1; 110 if(length>=(density*maxLength)/0x100) { 111 // Use one range. 112 ranges[0][0]=minValue; 113 ranges[0][1]=maxValue; 114 return 1; 115 } 116 if(length<=4) { 117 return 0; 118 } 119 // See if we can split [minValue, maxValue] into 2..capacity ranges, 120 // divided by the 1..(capacity-1) largest gaps. 121 LargestGaps gaps(capacity-1); 122 int32_t i; 123 int32_t expectedValue=minValue; 124 for(i=1; i<length; ++i) { 125 ++expectedValue; 126 int32_t actualValue=values[i]; 127 if(expectedValue!=actualValue) { 128 gaps.add(expectedValue, (int64_t)actualValue-(int64_t)expectedValue); 129 expectedValue=actualValue; 130 } 131 } 132 // We know gaps.count()>=1 because we have fewer values (length) than 133 // the length of the [minValue..maxValue] range (maxLength). 134 // (Otherwise we would have returned with the one range above.) 135 int32_t num; 136 for(i=0, num=2;; ++i, ++num) { 137 if(i>=gaps.count()) { 138 // The values are too sparse for capacity or fewer ranges 139 // of the requested density. 140 return 0; 141 } 142 maxLength-=gaps.gapLength(i); 143 if(length>num*2 && length>=(density*maxLength)/0x100) { 144 break; 145 } 146 } 147 // Use the num ranges with the num-1 largest gaps. 148 gaps.truncate(num-1); 149 ranges[0][0]=minValue; 150 for(i=0; i<=num-2; ++i) { 151 int32_t gapIndex=gaps.firstAfter(minValue); 152 int32_t gapStart=gaps.gapStart(gapIndex); 153 ranges[i][1]=gapStart-1; 154 ranges[i+1][0]=minValue=(int32_t)(gapStart+gaps.gapLength(gapIndex)); 155 } 156 ranges[num-1][1]=maxValue; 157 return num; 158 } 159
