impl/coll/CollationWeights.java

/*
*******************************************************************************
*
*   Copyright (C) 1999-2015, International Business Machines
*   Corporation and others.  All Rights Reserved.
*
*******************************************************************************
*   CollationWeights.java, ported from collationweights.h/.cpp
*
*   C++ version created on: 2001mar08 as ucol_wgt.h
*   created by: Markus W. Scherer
*/

package com.ibm.icu.impl.coll;

import java.util.Arrays;

/**
 * Allocates n collation element weights between two exclusive limits.
 * Used only internally by the collation tailoring builder.
 */
public final class CollationWeights {
    public CollationWeights() {}

    public void initForPrimary(boolean compressible) {
        middleLength=1;
        minBytes[1] = Collation.MERGE_SEPARATOR_BYTE + 1;
        maxBytes[1] = Collation.TRAIL_WEIGHT_BYTE;
        if(compressible) {
            minBytes[2] = Collation.PRIMARY_COMPRESSION_LOW_BYTE + 1;
            maxBytes[2] = Collation.PRIMARY_COMPRESSION_HIGH_BYTE - 1;
        } else {
            minBytes[2] = 2;
            maxBytes[2] = 0xff;
        }
        minBytes[3] = 2;
        maxBytes[3] = 0xff;
        minBytes[4] = 2;
        maxBytes[4] = 0xff;
    }

    public void initForSecondary() {
        // We use only the lower 16 bits for secondary weights.
        middleLength=3;
        minBytes[1] = 0;
        maxBytes[1] = 0;
        minBytes[2] = 0;
        maxBytes[2] = 0;
        minBytes[3] = Collation.LEVEL_SEPARATOR_BYTE + 1;
        maxBytes[3] = 0xff;
        minBytes[4] = 2;
        maxBytes[4] = 0xff;
    }

    public void initForTertiary() {
        // We use only the lower 16 bits for tertiary weights.
        middleLength=3;
        minBytes[1] = 0;
        maxBytes[1] = 0;
        minBytes[2] = 0;
        maxBytes[2] = 0;
        // We use only 6 bits per byte.
        // The other bits are used for case & quaternary weights.
        minBytes[3] = Collation.LEVEL_SEPARATOR_BYTE + 1;
        maxBytes[3] = 0x3f;
        minBytes[4] = 2;
        maxBytes[4] = 0x3f;
    }

    /**
     * Determine heuristically
     * what ranges to use for a given number of weights between (excluding)
     * two limits.
     *
     * @param lowerLimit A collation element weight; the ranges will be filled to cover
     *                   weights greater than this one.
     * @param upperLimit A collation element weight; the ranges will be filled to cover
     *                   weights less than this one.
     * @param n          The number of collation element weights w necessary such that
     *                   lowerLimit<w<upperLimit in lexical order.
     * @return true if it is possible to fit n elements between the limits
     */
    public boolean allocWeights(long lowerLimit, long upperLimit, int n) {
        // Call getWeightRanges() and then determine heuristically
        // which ranges to use for a given number of weights between (excluding)
        // two limits.
        // puts("");

        if(!getWeightRanges(lowerLimit, upperLimit)) {
            // printf("error: unable to get Weight ranges\n");
            return false;
        }

        /* try until we find suitably large ranges */
        for(;;) {
            /* get the smallest number of bytes in a range */
            int minLength=ranges[0].length;

            if(allocWeightsInShortRanges(n, minLength)) { break; }

            if(minLength == 4) {
                // printf("error: the maximum number of %ld weights is insufficient for n=%ld\n",
                //       minLengthCount, n);
                return false;
            }

            if(allocWeightsInMinLengthRanges(n, minLength)) { break; }

            /* no good match, lengthen all minLength ranges and iterate */
            // printf("lengthen the short ranges from %ld bytes to %ld and iterate\n", minLength, minLength+1);
            for(int i=0; ranges[i].length==minLength; ++i) {
                lengthenRange(ranges[i]);
            }
        }

        /* puts("final ranges:");
        for(int i=0; i<rangeCount; ++i) {
            printf("ranges[%ld] .start=0x%08lx .end=0x%08lx .length=%ld .count=%ld\n",
                  i, ranges[i].start, ranges[i].end, ranges[i].length, ranges[i].count);
        } */

        rangeIndex = 0;
        if(rangeCount < ranges.length) {
            ranges[rangeCount] = null;  // force a crash when going out of bounds
        }
        return true;
    }

    /**
     * Given a set of ranges calculated by allocWeights(),
     * iterate through the weights.
     * The ranges are modified to keep the current iteration state.
     *
     * @return The next weight in the ranges, or 0xffffffff if there is none left.
     */
    public long nextWeight() {
        if(rangeIndex >= rangeCount) {
            return 0xffffffffL;
        } else {
            /* get the next weight */
            WeightRange range = ranges[rangeIndex];
            long weight = range.start;
            if(--range.count == 0) {
                /* this range is finished */
                ++rangeIndex;
            } else {
                /* increment the weight for the next value */
                range.start = incWeight(weight, range.length);
                assert(range.start <= range.end);
            }

            return weight;
        }
    }

    /** @internal */
    private static final class WeightRange implements Comparable<WeightRange> {
        long start, end;
        int length, count;

        // Java 6: @Override
        public int compareTo(WeightRange other) {
            long l=start;
            long r=other.start;
            if(l<r) {
                return -1;
            } else if(l>r) {
                return 1;
            } else {
                return 0;
            }
        }
    }

    /* helper functions for CE weights */

    public static int lengthOfWeight(long weight) {
        if((weight&0xffffff)==0) {
            return 1;
        } else if((weight&0xffff)==0) {
            return 2;
        } else if((weight&0xff)==0) {
            return 3;
        } else {
            return 4;
        }
    }

    private static int getWeightTrail(long weight, int length) {
        return (int)(weight>>(8*(4-length)))&0xff;
    }

    private static long setWeightTrail(long weight, int length, int trail) {
        length=8*(4-length);
        return (weight&(0xffffff00L<<length))|((long)trail<<length);
    }

    private static int getWeightByte(long weight, int idx) {
        return getWeightTrail(weight, idx); /* same calculation */
    }

    private static long setWeightByte(long weight, int idx, int b) {
        long mask; /* 0xffffffff except a 00 "hole" for the index-th byte */

        idx*=8;
        if(idx<32) {
            mask=0xffffffffL>>idx;
        } else {
            // Do not use int>>32 because on some platforms that does not shift at all
            // while we need it to become 0.
            // PowerPC: 0xffffffff>>32 = 0           (wanted)
            // x86:     0xffffffff>>32 = 0xffffffff  (not wanted)
            //
            // ANSI C99 6.5.7 Bitwise shift operators:
            // "If the value of the right operand is negative
            // or is greater than or equal to the width of the promoted left operand,
            // the behavior is undefined."
            mask=0;
        }
        idx=32-idx;
        mask|=0xffffff00L<<idx;
        return (weight&mask)|((long)b<<idx);
    }

    private static long truncateWeight(long weight, int length) {
        return weight&(0xffffffffL<<(8*(4-length)));
    }

    private static long incWeightTrail(long weight, int length) {
        return weight+(1L<<(8*(4-length)));
    }

    private static long decWeightTrail(long weight, int length) {
        return weight-(1L<<(8*(4-length)));
    }

    /** @return number of usable byte values for byte idx */
    private int countBytes(int idx) {
        return maxBytes[idx] - minBytes[idx] + 1;
    }

    private long incWeight(long weight, int length) {
        for(;;) {
            int b=getWeightByte(weight, length);
            if(b<maxBytes[length]) {
                return setWeightByte(weight, length, b+1);
            } else {
                // Roll over, set this byte to the minimum and increment the previous one.
                weight=setWeightByte(weight, length, minBytes[length]);
                --length;
                assert(length > 0);
            }
        }
    }

    private long incWeightByOffset(long weight, int length, int offset) {
        for(;;) {
            offset += getWeightByte(weight, length);
            if(offset <= maxBytes[length]) {
                return setWeightByte(weight, length, offset);
            } else {
                // Split the offset between this byte and the previous one.
                offset -= minBytes[length];
                weight = setWeightByte(weight, length, minBytes[length] + offset % countBytes(length));
                offset /= countBytes(length);
                --length;
                assert(length > 0);
            }
        }
    }

    private void lengthenRange(WeightRange range) {
        int length=range.length+1;
        range.start=setWeightTrail(range.start, length, minBytes[length]);
        range.end=setWeightTrail(range.end, length, maxBytes[length]);
        range.count*=countBytes(length);
        range.length=length;
    }

    /**
     * Takes two CE weights and calculates the
     * possible ranges of weights between the two limits, excluding them.
     * For weights with up to 4 bytes there are up to 2*4-1=7 ranges.
     */
    private boolean getWeightRanges(long lowerLimit, long upperLimit) {
        assert(lowerLimit != 0);
        assert(upperLimit != 0);

        /* get the lengths of the limits */
        int lowerLength=lengthOfWeight(lowerLimit);
        int upperLength=lengthOfWeight(upperLimit);

        // printf("length of lower limit 0x%08lx is %ld\n", lowerLimit, lowerLength);
        // printf("length of upper limit 0x%08lx is %ld\n", upperLimit, upperLength);
        assert(lowerLength>=middleLength);
        // Permit upperLength<middleLength: The upper limit for secondaries is 0x10000.

        if(lowerLimit>=upperLimit) {
            // printf("error: no space between lower & upper limits\n");
            return false;
        }

        /* check that neither is a prefix of the other */
        if(lowerLength<upperLength) {
            if(lowerLimit==truncateWeight(upperLimit, lowerLength)) {
                // printf("error: lower limit 0x%08lx is a prefix of upper limit 0x%08lx\n", lowerLimit, upperLimit);
                return false;
            }
        }
        /* if the upper limit is a prefix of the lower limit then the earlier test lowerLimit>=upperLimit has caught it */

        WeightRange[] lower = new WeightRange[5]; /* [0] and [1] are not used - this simplifies indexing */
        WeightRange middle = new WeightRange();
        WeightRange[] upper = new WeightRange[5];

        /*
         * With the limit lengths of 1..4, there are up to 7 ranges for allocation:
         * range     minimum length
         * lower[4]  4
         * lower[3]  3
         * lower[2]  2
         * middle    1
         * upper[2]  2
         * upper[3]  3
         * upper[4]  4
         *
         * We are now going to calculate up to 7 ranges.
         * Some of them will typically overlap, so we will then have to merge and eliminate ranges.
         */
        long weight=lowerLimit;
        for(int length=lowerLength; length>middleLength; --length) {
            int trail=getWeightTrail(weight, length);
            if(trail<maxBytes[length]) {
                lower[length] = new WeightRange();
                lower[length].start=incWeightTrail(weight, length);
                lower[length].end=setWeightTrail(weight, length, maxBytes[length]);
                lower[length].length=length;
                lower[length].count=maxBytes[length]-trail;
            }
            weight=truncateWeight(weight, length-1);
        }
        if(weight<0xff000000L) {
            middle.start=incWeightTrail(weight, middleLength);
        } else {
            // Prevent overflow for primary lead byte FF
            // which would yield a middle range starting at 0.
            middle.start=0xffffffffL;  // no middle range
        }

        weight=upperLimit;
        for(int length=upperLength; length>middleLength; --length) {
            int trail=getWeightTrail(weight, length);
            if(trail>minBytes[length]) {
                upper[length] = new WeightRange();
                upper[length].start=setWeightTrail(weight, length, minBytes[length]);
                upper[length].end=decWeightTrail(weight, length);
                upper[length].length=length;
                upper[length].count=trail-minBytes[length];
            }
            weight=truncateWeight(weight, length-1);
        }
        middle.end=decWeightTrail(weight, middleLength);

        /* set the middle range */
        middle.length=middleLength;
        if(middle.end>=middle.start) {
            middle.count=(int)((middle.end-middle.start)>>(8*(4-middleLength)))+1;
        } else {
            /* no middle range, eliminate overlaps */
            for(int length=4; length>middleLength; --length) {
                if(lower[length] != null && upper[length] != null &&
                        lower[length].count>0 && upper[length].count>0) {
                    // Note: The lowerEnd and upperStart weights are versions of
                    // lowerLimit and upperLimit (which are lowerLimit<upperLimit),
                    // truncated (still less-or-equal)
                    // and then with their last bytes changed to the
                    // maxByte (for lowerEnd) or minByte (for upperStart).
                    final long lowerEnd=lower[length].end;
                    final long upperStart=upper[length].start;
                    boolean merged=false;

                    if(lowerEnd>upperStart) {
                        // These two lower and upper ranges collide.
                        // Since lowerLimit<upperLimit and lowerEnd and upperStart
                        // are versions with only their last bytes modified
                        // (and following ones removed/reset to 0),
                        // lowerEnd>upperStart is only possible
                        // if the leading bytes are equal
                        // and lastByte(lowerEnd)>lastByte(upperStart).
                        assert(truncateWeight(lowerEnd, length-1)==
                                truncateWeight(upperStart, length-1));
                        // Intersect these two ranges.
                        lower[length].end=upper[length].end;
                        lower[length].count=
                                getWeightTrail(lower[length].end, length)-
                                getWeightTrail(lower[length].start, length)+1;
                        // count might be <=0 in which case there is no room,
                        // and the range-collecting code below will ignore this range.
                        merged=true;
                    } else if(lowerEnd==upperStart) {
                        // Not possible, unless minByte==maxByte which is not allowed.
                        assert(minBytes[length]<maxBytes[length]);
                    } else /* lowerEnd<upperStart */ {
                        if(incWeight(lowerEnd, length)==upperStart) {
                            // Merge adjacent ranges.
                            lower[length].end=upper[length].end;
                            lower[length].count+=upper[length].count;  // might be >countBytes
                            merged=true;
                        }
                    }
                    if(merged) {
                        // Remove all shorter ranges.
                        // There was no room available for them between the ranges we just merged.
                        upper[length].count=0;
                        while(--length>middleLength) {
                            lower[length]=upper[length]=null;
                        }
                        break;
                    }
                }
            }
        }

        /* print ranges
        for(int length=4; length>=2; --length) {
            if(lower[length].count>0) {
                printf("lower[%ld] .start=0x%08lx .end=0x%08lx .count=%ld\n", length, lower[length].start, lower[length].end, lower[length].count);
            }
        }
        if(middle.count>0) {
            printf("middle   .start=0x%08lx .end=0x%08lx .count=%ld\n", middle.start, middle.end, middle.count);
        }
        for(int length=2; length<=4; ++length) {
            if(upper[length].count>0) {
                printf("upper[%ld] .start=0x%08lx .end=0x%08lx .count=%ld\n", length, upper[length].start, upper[length].end, upper[length].count);
            }
        } */

        /* copy the ranges, shortest first, into the result array */
        rangeCount=0;
        if(middle.count>0) {
            ranges[0] = middle;
            rangeCount=1;
        }
        for(int length=middleLength+1; length<=4; ++length) {
            /* copy upper first so that later the middle range is more likely the first one to use */
            if(upper[length] != null && upper[length].count>0) {
                ranges[rangeCount++]=upper[length];
            }
            if(lower[length] != null && lower[length].count>0) {
                ranges[rangeCount++]=lower[length];
            }
        }
        return rangeCount>0;
    }

    private boolean allocWeightsInShortRanges(int n, int minLength) {
        // See if the first few minLength and minLength+1 ranges have enough weights.
        for(int i = 0; i < rangeCount && ranges[i].length <= (minLength + 1); ++i) {
            if(n <= ranges[i].count) {
                // Use the first few minLength and minLength+1 ranges.
                if(ranges[i].length > minLength) {
                    // Reduce the number of weights from the last minLength+1 range
                    // which might sort before some minLength ranges,
                    // so that we use all weights in the minLength ranges.
                    ranges[i].count = n;
                }
                rangeCount = i + 1;
                // printf("take first %ld ranges\n", rangeCount);

                if(rangeCount>1) {
                    /* sort the ranges by weight values */
                    Arrays.sort(ranges, 0, rangeCount);
                }
                return true;
            }
            n -= ranges[i].count;  // still >0
        }
        return false;
    }

    private boolean allocWeightsInMinLengthRanges(int n, int minLength) {
        // See if the minLength ranges have enough weights
        // when we split one and lengthen the following ones.
        int count = 0;
        int minLengthRangeCount;
        for(minLengthRangeCount = 0;
                minLengthRangeCount < rangeCount &&
                    ranges[minLengthRangeCount].length == minLength;
                ++minLengthRangeCount) {
            count += ranges[minLengthRangeCount].count;
        }

        int nextCountBytes = countBytes(minLength + 1);
        if(n > count * nextCountBytes) { return false; }

        // Use the minLength ranges. Merge them, and then split again as necessary.
        long start = ranges[0].start;
        long end = ranges[0].end;
        for(int i = 1; i < minLengthRangeCount; ++i) {
            if(ranges[i].start < start) { start = ranges[i].start; }
            if(ranges[i].end > end) { end = ranges[i].end; }
        }

        // Calculate how to split the range between minLength (count1) and minLength+1 (count2).
        // Goal:
        //   count1 + count2 * nextCountBytes = n
        //   count1 + count2 = count
        // These turn into
        //   (count - count2) + count2 * nextCountBytes = n
        // and then into the following count1 & count2 computations.
        int count2 = (n - count) / (nextCountBytes - 1);  // number of weights to be lengthened
        int count1 = count - count2;  // number of minLength weights
        if(count2 == 0 || (count1 + count2 * nextCountBytes) < n) {
            // round up
            ++count2;
            --count1;
            assert((count1 + count2 * nextCountBytes) >= n);
        }

        ranges[0].start = start;

        if(count1 == 0) {
            // Make one long range.
            ranges[0].end = end;
            ranges[0].count = count;
            lengthenRange(ranges[0]);
            rangeCount = 1;
        } else {
            // Split the range, lengthen the second part.
            // printf("split the range number %ld (out of %ld minLength ranges) by %ld:%ld\n",
            //       splitRange, rangeCount, count1, count2);

            // Next start = start + count1. First end = 1 before that.
            ranges[0].end = incWeightByOffset(start, minLength, count1 - 1);
            ranges[0].count = count1;

            if(ranges[1] == null) {
                ranges[1] = new WeightRange();
            }
            ranges[1].start = incWeight(ranges[0].end, minLength);
            ranges[1].end = end;
            ranges[1].length = minLength;  // +1 when lengthened
            ranges[1].count = count2;  // *countBytes when lengthened
            lengthenRange(ranges[1]);
            rangeCount = 2;
        }
        return true;
    }

    private int middleLength;
    private int[] minBytes = new int[5];  // for byte 1, 2, 3, 4
    private int[] maxBytes = new int[5];
    private WeightRange[] ranges = new WeightRange[7];
    private int rangeIndex;
    private int rangeCount;
}