michael@0: /*
michael@0: *******************************************************************************
michael@0: *   Copyright (C) 2010, International Business Machines
michael@0: *   Corporation and others.  All Rights Reserved.
michael@0: *******************************************************************************
michael@0: *   file name:  denseranges.cpp
michael@0: *   encoding:   US-ASCII
michael@0: *   tab size:   8 (not used)
michael@0: *   indentation:4
michael@0: *
michael@0: *   created on: 2010sep25
michael@0: *   created by: Markus W. Scherer
michael@0: *
michael@0: * Helper code for finding a small number of dense ranges.
michael@0: */
michael@0: 
michael@0: #include "unicode/utypes.h"
michael@0: #include "denseranges.h"
michael@0: 
michael@0: // Definitions in the anonymous namespace are invisible outside this file.
michael@0: namespace {
michael@0: 
michael@0: /**
michael@0:  * Collect up to 15 range gaps and sort them by ascending gap size.
michael@0:  */
michael@0: class LargestGaps {
michael@0: public:
michael@0:     LargestGaps(int32_t max) : maxLength(max<=kCapacity ? max : kCapacity), length(0) {}
michael@0: 
michael@0:     void add(int32_t gapStart, int64_t gapLength) {
michael@0:         int32_t i=length;
michael@0:         while(i>0 && gapLength>gapLengths[i-1]) {
michael@0:             --i;
michael@0:         }
michael@0:         if(i<maxLength) {
michael@0:             // The new gap is now one of the maxLength largest.
michael@0:             // Insert the new gap, moving up smaller ones of the previous
michael@0:             // length largest.
michael@0:             int32_t j= length<maxLength ? length++ : maxLength-1;
michael@0:             while(j>i) {
michael@0:                 gapStarts[j]=gapStarts[j-1];
michael@0:                 gapLengths[j]=gapLengths[j-1];
michael@0:                 --j;
michael@0:             }
michael@0:             gapStarts[i]=gapStart;
michael@0:             gapLengths[i]=gapLength;
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     void truncate(int32_t newLength) {
michael@0:         if(newLength<length) {
michael@0:             length=newLength;
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     int32_t count() const { return length; }
michael@0:     int32_t gapStart(int32_t i) const { return gapStarts[i]; }
michael@0:     int64_t gapLength(int32_t i) const { return gapLengths[i]; }
michael@0: 
michael@0:     int32_t firstAfter(int32_t value) const {
michael@0:         if(length==0) {
michael@0:             return -1;
michael@0:         }
michael@0:         int32_t minValue=0;
michael@0:         int32_t minIndex=-1;
michael@0:         for(int32_t i=0; i<length; ++i) {
michael@0:             if(value<gapStarts[i] && (minIndex<0 || gapStarts[i]<minValue)) {
michael@0:                 minValue=gapStarts[i];
michael@0:                 minIndex=i;
michael@0:             }
michael@0:         }
michael@0:         return minIndex;
michael@0:     }
michael@0: 
michael@0: private:
michael@0:     static const int32_t kCapacity=15;
michael@0: 
michael@0:     int32_t maxLength;
michael@0:     int32_t length;
michael@0:     int32_t gapStarts[kCapacity];
michael@0:     int64_t gapLengths[kCapacity];
michael@0: };
michael@0: 
michael@0: }  // namespace
michael@0: 
michael@0: /**
michael@0:  * Does it make sense to write 1..capacity ranges?
michael@0:  * Returns 0 if not, otherwise the number of ranges.
michael@0:  * @param values Sorted array of signed-integer values.
michael@0:  * @param length Number of values.
michael@0:  * @param density Minimum average range density, in 256th. (0x100=100%=perfectly dense.)
michael@0:  *                Should be 0x80..0x100, must be 1..0x100.
michael@0:  * @param ranges Output ranges array.
michael@0:  * @param capacity Maximum number of ranges.
michael@0:  * @return Minimum number of ranges (at most capacity) that have the desired density,
michael@0:  *         or 0 if that density cannot be achieved.
michael@0:  */
michael@0: U_CAPI int32_t U_EXPORT2
michael@0: uprv_makeDenseRanges(const int32_t values[], int32_t length,
michael@0:                      int32_t density,
michael@0:                      int32_t ranges[][2], int32_t capacity) {
michael@0:     if(length<=2) {
michael@0:         return 0;
michael@0:     }
michael@0:     int32_t minValue=values[0];
michael@0:     int32_t maxValue=values[length-1];  // Assume minValue<=maxValue.
michael@0:     // Use int64_t variables for intermediate-value precision and to avoid
michael@0:     // signed-int32_t overflow of maxValue-minValue.
michael@0:     int64_t maxLength=(int64_t)maxValue-(int64_t)minValue+1;
michael@0:     if(length>=(density*maxLength)/0x100) {
michael@0:         // Use one range.
michael@0:         ranges[0][0]=minValue;
michael@0:         ranges[0][1]=maxValue;
michael@0:         return 1;
michael@0:     }
michael@0:     if(length<=4) {
michael@0:         return 0;
michael@0:     }
michael@0:     // See if we can split [minValue, maxValue] into 2..capacity ranges,
michael@0:     // divided by the 1..(capacity-1) largest gaps.
michael@0:     LargestGaps gaps(capacity-1);
michael@0:     int32_t i;
michael@0:     int32_t expectedValue=minValue;
michael@0:     for(i=1; i<length; ++i) {
michael@0:         ++expectedValue;
michael@0:         int32_t actualValue=values[i];
michael@0:         if(expectedValue!=actualValue) {
michael@0:             gaps.add(expectedValue, (int64_t)actualValue-(int64_t)expectedValue);
michael@0:             expectedValue=actualValue;
michael@0:         }
michael@0:     }
michael@0:     // We know gaps.count()>=1 because we have fewer values (length) than
michael@0:     // the length of the [minValue..maxValue] range (maxLength).
michael@0:     // (Otherwise we would have returned with the one range above.)
michael@0:     int32_t num;
michael@0:     for(i=0, num=2;; ++i, ++num) {
michael@0:         if(i>=gaps.count()) {
michael@0:             // The values are too sparse for capacity or fewer ranges
michael@0:             // of the requested density.
michael@0:             return 0;
michael@0:         }
michael@0:         maxLength-=gaps.gapLength(i);
michael@0:         if(length>num*2 && length>=(density*maxLength)/0x100) {
michael@0:             break;
michael@0:         }
michael@0:     }
michael@0:     // Use the num ranges with the num-1 largest gaps.
michael@0:     gaps.truncate(num-1);
michael@0:     ranges[0][0]=minValue;
michael@0:     for(i=0; i<=num-2; ++i) {
michael@0:         int32_t gapIndex=gaps.firstAfter(minValue);
michael@0:         int32_t gapStart=gaps.gapStart(gapIndex);
michael@0:         ranges[i][1]=gapStart-1;
michael@0:         ranges[i+1][0]=minValue=(int32_t)(gapStart+gaps.gapLength(gapIndex));
michael@0:     }
michael@0:     ranges[num-1][1]=maxValue;
michael@0:     return num;
michael@0: }