/*______________________________________________________________________________
 * 
 * net.innig.util.IntegerRadix
 * 
 *______________________________________________________________________________
 * 
 * Copyright 2002 Paul Cantrell
 * 
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * (1) Redistributions of source code must retain the above copyright
 *     notice, this list of conditions and the following disclaimer.
 *
 * (2) Redistributions in binary form must reproduce the above copyright
 *     notice, this list of conditions and the following disclaimer in
 *     the documentation and/or other materials provided with the
 *     distribution. 
 *
 * (3) The name of the author may not be used to endorse or promote
 *     products derived from this software without specific prior
 *     written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT,
 * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
 * OF THE POSSIBILITY OF SUCH DAMAGE.
 *_______________________________________________________________________________
 */

package net.innig.collect;

import java.util.*;

/**
    A radix which supports Byte, Short, Integer, and Long.
    
    <p align="center">
    <table cellpadding=4 cellspacing=2 border=0 bgcolor="#338833" width="90%"><tr><td bgcolor="#EEEEEE">
        <b>Maturity:</b>
        All the radix utilities in innig-util are completely experimental.  They mostly
        work, but perform poorly.  They may stay; they may improve; they may go away.
    </td></tr><tr><td bgcolor="#EEEEEE">
        <b>Plans:</b>
        Experiment.
    </td></tr></table>

    @see Radix
*/
public class IntegralRadix
    implements Radix, java.io.Serializable
    {
    /** Returns the number of bits necessary to represent n.
     */
    static public int bitsNeeded(long n, boolean signed)
        {
        int numberBits = 1;
        if(signed && n < 0)
            {
            n = -n;
            numberBits = 2;
            }
        while((n >>>= 1) != 0)
            numberBits++;
        return numberBits;
        }
    
    /** Returns a base-256 radix which handles numbers of the given type in their
     *  natural form (signed, and all bits used).
     *  @param numberType the class Byte, Short, Integer, or Long.
     *  @throws IllegalArgumentException if numberType is not one of these classes.
     */
    static public Radix forType(Class numberType)
        {
        synchronized(Radix.class)
            {
            if(defaultRadices == null)
                {
                defaultRadices = new HashMap();
                defaultRadices.put(   Byte.class, new IntegralRadix( 8, 8, true));
                defaultRadices.put(  Short.class, new IntegralRadix(16, 8, true));
                defaultRadices.put(Integer.class, new IntegralRadix(32, 8, true));
                defaultRadices.put(   Long.class, new IntegralRadix(64, 8, true));
                }
            }
        Radix radix = (Radix) defaultRadices.get(numberType);
        if(radix != null)
            return radix;
        else
            throw new IllegalArgumentException(numberType + " must be Byte, Short, Integer, or Long");
        }
    static private Map defaultRadices;
    
    /** Creates a new radix for <i>n</i>-bit integers.
     *  @param numberBits
     *		the number of bits in the integers this radix handles.
     * 		Although the standard integral types come in powers of two (e.g. 8 for Byte,
     *		16 for Short), any number of bits between 1 and 64 is legal.
     *	@param digitBits
     *		the number of bits in each digit of the radix.  This parameter
     *		allows you to split large integers into several digits, which keeps
     *		bucket-based radix algorithms reasonable.  This parameter must divide
     *		numberBits, and must be <= 30.
     *	@param signed
     *		if true, the radix treats numbers as signed, and gives the
     *		digits of the two's complement representation.
     */
    public IntegralRadix(int numberBits, int digitBits, boolean signed)
        {
        if(numberBits < 1 || numberBits > 64)
            throw new IllegalArgumentException("invalid numberBits (" + numberBits + ")");
        if(digitBits > 30)
            throw new IllegalArgumentException("invalid digitBits (" + digitBits + " > 30)");
        if(numberBits % digitBits != 0)
            throw new IllegalArgumentException("digitBits=" + digitBits + " does not divide numberBits=" + numberBits);
        this.numberBits = numberBits;
        this.digitBits = digitBits;
        this.signed = signed;
        base = 1 << digitBits;
        maxDigits = numberBits / digitBits;
        signCorrection     =  signed ? 1L << (numberBits-1) : 0;
        signAntiCorrection = !signed ? 1L << (numberBits-1) : 0;
        }

    /** Returns the base (the number of digit values) in this radix.
     */
    public int getBase()
        { return base; }
    
    /** Returns the digits of the radix representation of the given number.
     *  Lower positions are less significant digits.
     *  @param	o a Byte, Short, Integer, or Long object.
     *  @param	pos a digit position within <tt>o</tt>.
     *  @return a digit <i>d</i>, with -1 &lt;= <i>x</i> &lt; getBase().
     *  	A variable-length radix uses the digit -1 signifies that the position
     *		is beyond the end of the object's representation.
     *  @throws ClassCastException if o is not a {@link Number}.
     */
    public int digit(Object o, int pos)
        {
        return pos < 0
            ? -1
            : (int) ((((Number) o).longValue() ^ signCorrection) >>> (pos * digitBits)) & (base-1);
        }
    
    /** Returns the position of the most significant digit for this radix.
     */
    public int getMaxPosition(Object o)
         { return maxDigits-1; }

    /** Returns zero.
     */
    public int getMinPosition(Object o)
         { return 0; }

    /** Returns the position of the most significant digit for this radix.
     */
    public int getMaxPositionForAll(Collection values)
         { return maxDigits-1; }

    /** Returns zero.
     */
    public int getMinPositionForAll(Collection values)
         { return 0; }

    /** Constructs a number from the given digits.
     *
     *  @throws IllegalArgumentException if the digits don't represent a valid number.
     */
    public Object objectFromDigits(int[] digits)
        { return objectFromDigits(digits, 0, digits.length); }
        
    /** Constructs a number from the given digits.
     *
     *  @throws IllegalArgumentException if the digits don't represent a valid number.
     */
    public Object objectFromDigits(int[] digits, int offset, int len)
        {
        // Should fix this to strip -1s from the front ...
        if(len > maxDigits)
            throw new IllegalArgumentException("too many digits (" + len + " > " + maxDigits + ")");
        long value = (signed && (digits[offset+len-1] & (base >> 1)) != 0) // check sign bit
            ? -1 : 0;
        for(int n = offset + len - 1; n >= offset; n--)
            value = (value << digitBits) + digits[n];
        if(numberBits <= 8)
            return new Byte((byte) value);
        else if(numberBits <= 16)
            return new Short((short) value);
        else if(numberBits <= 32)
            return new Integer((int) value);
        else
            return new Long((long) value);
        }
    
    public int compare(Object aObj, Object bObj)
        {
        long
            a = normalizeForCompare(((Number) aObj).longValue()),
            b = normalizeForCompare(((Number) bObj).longValue());
        return (a == b) ? 0 : (a < b) ? -1 : 1;
        }

    private long normalizeForCompare(long x)
        {
        return (x ^ signAntiCorrection)
            << (64 - numberBits)
            >> (64 - numberBits);
        }
        
    public boolean equals(Object that)
        {
        if(this == that)
            return true;
        if(that == null || this.getClass() != that.getClass())
            return false;
        IntegralRadix thatIR = (IntegralRadix) that;
        return numberBits == thatIR.numberBits
            && digitBits  == thatIR.digitBits
            && signed     == thatIR.signed;
        }

    public int hashCode()
        {
        return ((getClass().hashCode() * 17
            + numberBits) * 23
            + digitBits) * 29
            + (signed ? 1 : 0);
        }
    
    public String toString()
        {
        return "IntegralRadix[numberBits=" + numberBits + ", digitBits=" + digitBits
            + ", " + (signed ? "" : "un") + "signed]";
        }
    
    private final int numberBits, digitBits, base, maxDigits;
    private final boolean signed;
    private final long signCorrection, signAntiCorrection;
    }