NumericUtils.cs

Go to the documentation of this file.

/* 
 * Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to You under the Apache License, Version 2.0
 * (the "License"); you may not use this file except in compliance with
 * the License.  You may obtain a copy of the License at
 * 
 * http://www.apache.org/licenses/LICENSE-2.0
 * 
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

using System;
using Lucene.Net.Documents;
using Lucene.Net.Search;
using Lucene.Net.Support;
using NumericTokenStream = Lucene.Net.Analysis.NumericTokenStream;

namespace Lucene.Net.Util
{
    
    /// <summary> This is a helper class to generate prefix-encoded representations for numerical values
    /// and supplies converters to represent float/double values as sortable integers/longs.
    /// 
    /// <p/>To quickly execute range queries in Apache Lucene, a range is divided recursively
    /// into multiple intervals for searching: The center of the range is searched only with
    /// the lowest possible precision in the trie, while the boundaries are matched
    /// more exactly. This reduces the number of terms dramatically.
    /// 
    /// <p/>This class generates terms to achive this: First the numerical integer values need to
    /// be converted to strings. For that integer values (32 bit or 64 bit) are made unsigned
    /// and the bits are converted to ASCII chars with each 7 bit. The resulting string is
    /// sortable like the original integer value. Each value is also prefixed
    /// (in the first char) by the <c>shift</c> value (number of bits removed) used
    /// during encoding.
    /// 
    /// <p/>To also index floating point numbers, this class supplies two methods to convert them
    /// to integer values by changing their bit layout: <see cref="DoubleToSortableLong" />,
    /// <see cref="FloatToSortableInt" />. You will have no precision loss by
    /// converting floating point numbers to integers and back (only that the integer form
    /// is not usable). Other data types like dates can easily converted to longs or ints (e.g.
    /// date to long: <see cref="DateTime" />).
    /// 
    /// <p/>For easy usage, the trie algorithm is implemented for indexing inside
    /// <see cref="NumericTokenStream" /> that can index <c>int</c>, <c>long</c>,
    /// <c>float</c>, and <c>double</c>. For querying,
    /// <see cref="NumericRangeQuery{T}" /> and <see cref="NumericRangeFilter{T}" /> implement the query part
    /// for the same data types.
    /// 
    /// <p/>This class can also be used, to generate lexicographically sortable (according
    /// <see cref="String.CompareTo(String)" />) representations of numeric data types for other
    /// usages (e.g. sorting).
    /// 
    /// <p/><font color="red"><b>NOTE:</b> This API is experimental and
    /// might change in incompatible ways in the next release.</font>
    /// 
    /// </summary>
    /// <since> 2.9
    /// </since>
    public sealed class NumericUtils
    {
        
        private NumericUtils()
        {
        } // no instance!
        
        /// <summary> The default precision step used by <see cref="NumericField" />, <see cref="NumericTokenStream" />,
        /// <see cref="NumericRangeQuery{T}" />, and <see cref="NumericRangeFilter{T}" /> as default
        /// </summary>
        public const int PRECISION_STEP_DEFAULT = 4;
        
        /// <summary> Expert: Longs are stored at lower precision by shifting off lower bits. The shift count is
        /// stored as <c>SHIFT_START_LONG+shift</c> in the first character
        /// </summary>
        public static char SHIFT_START_LONG = (char) 0x20;
        
        /// <summary> Expert: The maximum term length (used for <c>char[]</c> buffer size)
        /// for encoding <c>long</c> values.
        /// </summary>
        /// <seealso cref="LongToPrefixCoded(long,int,char[])">
        /// </seealso>
        public const int BUF_SIZE_LONG = 63 / 7 + 2;
        
        /// <summary> Expert: Integers are stored at lower precision by shifting off lower bits. The shift count is
        /// stored as <c>SHIFT_START_INT+shift</c> in the first character
        /// </summary>
        public static char SHIFT_START_INT = (char) 0x60;
        
        /// <summary> Expert: The maximum term length (used for <c>char[]</c> buffer size)
        /// for encoding <c>int</c> values.
        /// </summary>
        /// <seealso cref="IntToPrefixCoded(int,int,char[])">
        /// </seealso>
        public const int BUF_SIZE_INT = 31 / 7 + 2;
        
        /// <summary> Expert: Returns prefix coded bits after reducing the precision by <c>shift</c> bits.
        /// This is method is used by <see cref="NumericTokenStream" />.
        /// </summary>
        /// <param name="val">the numeric value
        /// </param>
        /// <param name="shift">how many bits to strip from the right
        /// </param>
        /// <param name="buffer">that will contain the encoded chars, must be at least of <see cref="BUF_SIZE_LONG" />
        /// length
        /// </param>
        /// <returns> number of chars written to buffer
        /// </returns>
        public static int LongToPrefixCoded(long val, int shift, char[] buffer)
        {
            if (shift > 63 || shift < 0)
                throw new System.ArgumentException("Illegal shift value, must be 0..63");
            int nChars = (63 - shift) / 7 + 1, len = nChars + 1;
            buffer[0] = (char) (SHIFT_START_LONG + shift);
            ulong sortableBits = BitConverter.ToUInt64(BitConverter.GetBytes(val), 0) ^ 0x8000000000000000L;
            sortableBits = sortableBits >> shift;
            while (nChars >= 1)
            {
                // Store 7 bits per character for good efficiency when UTF-8 encoding.
                // The whole number is right-justified so that lucene can prefix-encode
                // the terms more efficiently.
                buffer[nChars--] = (char) (sortableBits & 0x7f);
                sortableBits = sortableBits >> 7;
            }
            return len;
        }
        
        /// <summary> Expert: Returns prefix coded bits after reducing the precision by <c>shift</c> bits.
        /// This is method is used by <see cref="LongRangeBuilder" />.
        /// </summary>
        /// <param name="val">the numeric value
        /// </param>
        /// <param name="shift">how many bits to strip from the right
        /// </param>
        public static System.String LongToPrefixCoded(long val, int shift)
        {
            char[] buffer = new char[BUF_SIZE_LONG];
            int len = LongToPrefixCoded(val, shift, buffer);
            return new System.String(buffer, 0, len);
        }
        
        /// <summary> This is a convenience method, that returns prefix coded bits of a long without
        /// reducing the precision. It can be used to store the full precision value as a
        /// stored field in index.
        /// <p/>To decode, use <see cref="PrefixCodedToLong" />.
        /// </summary>
        public static System.String LongToPrefixCoded(long val)
        {
            return LongToPrefixCoded(val, 0);
        }
        
        /// <summary> Expert: Returns prefix coded bits after reducing the precision by <c>shift</c> bits.
        /// This is method is used by <see cref="NumericTokenStream" />.
        /// </summary>
        /// <param name="val">the numeric value
        /// </param>
        /// <param name="shift">how many bits to strip from the right
        /// </param>
        /// <param name="buffer">that will contain the encoded chars, must be at least of <see cref="BUF_SIZE_INT" />
        /// length
        /// </param>
        /// <returns> number of chars written to buffer
        /// </returns>
        public static int IntToPrefixCoded(int val, int shift, char[] buffer)
        {
            if (shift > 31 || shift < 0)
                throw new System.ArgumentException("Illegal shift value, must be 0..31");
            int nChars = (31 - shift) / 7 + 1, len = nChars + 1;
            buffer[0] = (char) (SHIFT_START_INT + shift);
            int sortableBits = val ^ unchecked((int) 0x80000000);
            sortableBits = Number.URShift(sortableBits, shift);
            while (nChars >= 1)
            {
                // Store 7 bits per character for good efficiency when UTF-8 encoding.
                // The whole number is right-justified so that lucene can prefix-encode
                // the terms more efficiently.
                buffer[nChars--] = (char) (sortableBits & 0x7f);
                sortableBits = Number.URShift(sortableBits, 7);
            }
            return len;
        }
        
        /// <summary> Expert: Returns prefix coded bits after reducing the precision by <c>shift</c> bits.
        /// This is method is used by <see cref="IntRangeBuilder" />.
        /// </summary>
        /// <param name="val">the numeric value
        /// </param>
        /// <param name="shift">how many bits to strip from the right
        /// </param>
        public static System.String IntToPrefixCoded(int val, int shift)
        {
            char[] buffer = new char[BUF_SIZE_INT];
            int len = IntToPrefixCoded(val, shift, buffer);
            return new System.String(buffer, 0, len);
        }
        
        /// <summary> This is a convenience method, that returns prefix coded bits of an int without
        /// reducing the precision. It can be used to store the full precision value as a
        /// stored field in index.
        /// <p/>To decode, use <see cref="PrefixCodedToInt" />.
        /// </summary>
        public static System.String IntToPrefixCoded(int val)
        {
            return IntToPrefixCoded(val, 0);
        }
        
        /// <summary> Returns a long from prefixCoded characters.
        /// Rightmost bits will be zero for lower precision codes.
        /// This method can be used to decode e.g. a stored field.
        /// </summary>
        /// <throws>  NumberFormatException if the supplied string is </throws>
        /// <summary> not correctly prefix encoded.
        /// </summary>
        /// <seealso cref="LongToPrefixCoded(long)">
        /// </seealso>
        public static long PrefixCodedToLong(System.String prefixCoded)
        {
            int shift = prefixCoded[0] - SHIFT_START_LONG;
            if (shift > 63 || shift < 0)
                throw new System.FormatException("Invalid shift value in prefixCoded string (is encoded value really a LONG?)");
            ulong sortableBits = 0UL;
            for (int i = 1, len = prefixCoded.Length; i < len; i++)
            {
                sortableBits <<= 7;
                char ch = prefixCoded[i];
                if (ch > 0x7f)
                {
                    throw new System.FormatException("Invalid prefixCoded numerical value representation (char " + System.Convert.ToString((int) ch, 16) + " at position " + i + " is invalid)");
                }
                sortableBits |= (ulong) ch;
            }
            return BitConverter.ToInt64(BitConverter.GetBytes((sortableBits << shift) ^ 0x8000000000000000L), 0);
        }
        
        /// <summary> Returns an int from prefixCoded characters.
        /// Rightmost bits will be zero for lower precision codes.
        /// This method can be used to decode e.g. a stored field.
        /// </summary>
        /// <throws>  NumberFormatException if the supplied string is </throws>
        /// <summary> not correctly prefix encoded.
        /// </summary>
        /// <seealso cref="IntToPrefixCoded(int)">
        /// </seealso>
        public static int PrefixCodedToInt(System.String prefixCoded)
        {
            int shift = prefixCoded[0] - SHIFT_START_INT;
            if (shift > 31 || shift < 0)
                throw new System.FormatException("Invalid shift value in prefixCoded string (is encoded value really an INT?)");
            int sortableBits = 0;
            for (int i = 1, len = prefixCoded.Length; i < len; i++)
            {
                sortableBits <<= 7;
                char ch = prefixCoded[i];
                if (ch > 0x7f)
                {
                    throw new System.FormatException("Invalid prefixCoded numerical value representation (char " + System.Convert.ToString((int) ch, 16) + " at position " + i + " is invalid)");
                }
                sortableBits |= (int) ch;
            }
            return (sortableBits << shift) ^ unchecked((int) 0x80000000);
        }
        
        /// <summary> Converts a <c>double</c> value to a sortable signed <c>long</c>.
        /// The value is converted by getting their IEEE 754 floating-point &quot;double format&quot;
        /// bit layout and then some bits are swapped, to be able to compare the result as long.
        /// By this the precision is not reduced, but the value can easily used as a long.
        /// </summary>
        /// <seealso cref="SortableLongToDouble">
        /// </seealso>
        public static long DoubleToSortableLong(double val)
        {
            long f = BitConverter.DoubleToInt64Bits(val);   // {{Aroush-2.9}} will this work the same as 'java.lang.Double.doubleToRawLongBits()'?
            if (f < 0)
                f ^= 0x7fffffffffffffffL;
            return f;
        }
        
        /// <summary> Convenience method: this just returns:
        /// longToPrefixCoded(doubleToSortableLong(val))
        /// </summary>
        public static System.String DoubleToPrefixCoded(double val)
        {
            return LongToPrefixCoded(DoubleToSortableLong(val));
        }
        
        /// <summary> Converts a sortable <c>long</c> back to a <c>double</c>.</summary>
        /// <seealso cref="DoubleToSortableLong">
        /// </seealso>
        public static double SortableLongToDouble(long val)
        {
            if (val < 0)
                val ^= 0x7fffffffffffffffL;
            return BitConverter.Int64BitsToDouble(val);
        }
        
        /// <summary> Convenience method: this just returns:
        /// sortableLongToDouble(prefixCodedToLong(val))
        /// </summary>
        public static double PrefixCodedToDouble(System.String val)
        {
            return SortableLongToDouble(PrefixCodedToLong(val));
        }
        
        /// <summary> Converts a <c>float</c> value to a sortable signed <c>int</c>.
        /// The value is converted by getting their IEEE 754 floating-point &quot;float format&quot;
        /// bit layout and then some bits are swapped, to be able to compare the result as int.
        /// By this the precision is not reduced, but the value can easily used as an int.
        /// </summary>
        /// <seealso cref="SortableIntToFloat">
        /// </seealso>
        public static int FloatToSortableInt(float val)
        {
            int f = BitConverter.ToInt32(BitConverter.GetBytes(val), 0);
            if (f < 0)
                f ^= 0x7fffffff;
            return f;
        }
        
        /// <summary> Convenience method: this just returns:
        /// intToPrefixCoded(floatToSortableInt(val))
        /// </summary>
        public static System.String FloatToPrefixCoded(float val)
        {
            return IntToPrefixCoded(FloatToSortableInt(val));
        }
        
        /// <summary> Converts a sortable <c>int</c> back to a <c>float</c>.</summary>
        /// <seealso cref="FloatToSortableInt">
        /// </seealso>
        public static float SortableIntToFloat(int val)
        {
            if (val < 0)
                val ^= 0x7fffffff;
            return BitConverter.ToSingle(BitConverter.GetBytes(val), 0);
        }
        
        /// <summary> Convenience method: this just returns:
        /// sortableIntToFloat(prefixCodedToInt(val))
        /// </summary>
        public static float PrefixCodedToFloat(System.String val)
        {
            return SortableIntToFloat(PrefixCodedToInt(val));
        }
        
        /// <summary> Expert: Splits a long range recursively.
        /// You may implement a builder that adds clauses to a
        /// <see cref="Lucene.Net.Search.BooleanQuery" /> for each call to its
        /// <see cref="LongRangeBuilder.AddRange(String,String)" />
        /// method.
        /// <p/>This method is used by <see cref="NumericRangeQuery{T}" />.
        /// </summary>
        public static void  SplitLongRange(LongRangeBuilder builder, int precisionStep, long minBound, long maxBound)
        {
            SplitRange(builder, 64, precisionStep, minBound, maxBound);
        }
        
        /// <summary> Expert: Splits an int range recursively.
        /// You may implement a builder that adds clauses to a
        /// <see cref="Lucene.Net.Search.BooleanQuery" /> for each call to its
        /// <see cref="IntRangeBuilder.AddRange(String,String)" />
        /// method.
        /// <p/>This method is used by <see cref="NumericRangeQuery{T}" />.
        /// </summary>
        public static void  SplitIntRange(IntRangeBuilder builder, int precisionStep, int minBound, int maxBound)
        {
            SplitRange(builder, 32, precisionStep, (long) minBound, (long) maxBound);
        }
        
        /// <summary>This helper does the splitting for both 32 and 64 bit. </summary>
        private static void  SplitRange(System.Object builder, int valSize, int precisionStep, long minBound, long maxBound)
        {
            if (precisionStep < 1)
                throw new System.ArgumentException("precisionStep must be >=1");
            if (minBound > maxBound)
                return ;
            for (int shift = 0; ; shift += precisionStep)
            {
                // calculate new bounds for inner precision
                long diff = 1L << (shift + precisionStep);
                long mask = ((1L << precisionStep) - 1L) << shift;
                bool hasLower = (minBound & mask) != 0L;
                bool hasUpper = (maxBound & mask) != mask;
                long nextMinBound = (hasLower?(minBound + diff):minBound) & ~ mask;
                long nextMaxBound = (hasUpper?(maxBound - diff):maxBound) & ~ mask;
                bool lowerWrapped = nextMinBound < minBound,
                     upperWrapped = nextMaxBound > maxBound;
      
                if (shift+precisionStep>=valSize || nextMinBound>nextMaxBound || lowerWrapped || upperWrapped) 
                {
                    // We are in the lowest precision or the next precision is not available.
                    AddRange(builder, valSize, minBound, maxBound, shift);
                    // exit the split recursion loop
                    break;
                }
                
                if (hasLower)
                    AddRange(builder, valSize, minBound, minBound | mask, shift);
                if (hasUpper)
                    AddRange(builder, valSize, maxBound & ~ mask, maxBound, shift);
                
                // recurse to next precision
                minBound = nextMinBound;
                maxBound = nextMaxBound;
            }
        }
        
        /// <summary>Helper that delegates to correct range builder </summary>
        private static void  AddRange(System.Object builder, int valSize, long minBound, long maxBound, int shift)
        {
            // for the max bound set all lower bits (that were shifted away):
            // this is important for testing or other usages of the splitted range
            // (e.g. to reconstruct the full range). The prefixEncoding will remove
            // the bits anyway, so they do not hurt!
            maxBound |= (1L << shift) - 1L;
            // delegate to correct range builder
            switch (valSize)
            {
                
                case 64: 
                    ((LongRangeBuilder) builder).AddRange(minBound, maxBound, shift);
                    break;
                
                case 32: 
                    ((IntRangeBuilder) builder).AddRange((int) minBound, (int) maxBound, shift);
                    break;
                
                default: 
                    // Should not happen!
                    throw new System.ArgumentException("valSize must be 32 or 64.");
                
            }
        }
        
        /// <summary> Expert: Callback for <see cref="SplitLongRange" />.
        /// You need to overwrite only one of the methods.
        /// <p/><font color="red"><b>NOTE:</b> This is a very low-level interface,
        /// the method signatures may change in later versions.</font>
        /// </summary>
        public abstract class LongRangeBuilder
        {
            
            /// <summary> Overwrite this method, if you like to receive the already prefix encoded range bounds.
            /// You can directly build classical (inclusive) range queries from them.
            /// </summary>
            public virtual void  AddRange(System.String minPrefixCoded, System.String maxPrefixCoded)
            {
                throw new System.NotSupportedException();
            }
            
            /// <summary> Overwrite this method, if you like to receive the raw long range bounds.
            /// You can use this for e.g. debugging purposes (print out range bounds).
            /// </summary>
            public virtual void  AddRange(long min, long max, int shift)
            {
                AddRange(Lucene.Net.Util.NumericUtils.LongToPrefixCoded(min, shift), Lucene.Net.Util.NumericUtils.LongToPrefixCoded(max, shift));
            }
        }
        
        /// <summary> Expert: Callback for <see cref="SplitIntRange" />.
        /// You need to overwrite only one of the methods.
        /// <p/><font color="red"><b>NOTE:</b> This is a very low-level interface,
        /// the method signatures may change in later versions.</font>
        /// </summary>
        public abstract class IntRangeBuilder
        {
            
            /// <summary> Overwrite this method, if you like to receive the already prefix encoded range bounds.
            /// You can directly build classical range (inclusive) queries from them.
            /// </summary>
            public virtual void  AddRange(System.String minPrefixCoded, System.String maxPrefixCoded)
            {
                throw new System.NotSupportedException();
            }
            
            /// <summary> Overwrite this method, if you like to receive the raw int range bounds.
            /// You can use this for e.g. debugging purposes (print out range bounds).
            /// </summary>
            public virtual void  AddRange(int min, int max, int shift)
            {
                AddRange(Lucene.Net.Util.NumericUtils.IntToPrefixCoded(min, shift), Lucene.Net.Util.NumericUtils.IntToPrefixCoded(max, shift));
            }
        }
    }
}