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