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