annotate modules/javafx.web/src/main/native/Source/ThirdParty/icu/source/tools/toolutil/denseranges.cpp @ 11038:20a8447c71c6

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