package Current.search.basic;

import java.util.TreeMap;
import java.util.Comparator;
import java.util.Iterator;
import java.util.Set;
import java.lang.Object;
import java.lang.Integer;


/** This class decides definitively whether a polynomial in
 * some double values is positive or negative. "Definitively" means
 * without the possibility of computer error.
 * <br><br>
 *
 * This may be useful, for example, in the field of computational geometry.
 * For my particular application, I need to know whether or not a triangle
 * with double coordinates has a positive or negative signed area.
 * <br><br>
 *
 * This is essentially an extremely unplesant problem. Let me give some examples:
 * <br><br>
 *
 * Suppose x is about 10^100 and y is about -10^100 and z is about 10^-100. So x and y are
 * huge and similar in magnitude, but z is miniscule. Decide the sign of x+y+z.
 * <br><br>
 * 
 * Now suppose x=a*b and y=c*d. Then because of round off error, when java runs it computes
 * y=-x. But, it is extremely unlikely that c*d=-a*b. The obvious computation of 
 * (x+y)+z will equal z. But the sign of (a*b+c*d)+z is much more likely to depend on
 * a*b and c*d. This class solves these annoying problems.
 * <br><br>
 *
 * This class implements some trivial case of arbitrary precision arithmetic. But,
 * you would not want to do this by simply storing a huge list of consequtive digits. 
 * This is because 2^1000 + 2^(-1000) would require storing 2000 binary digits.
 */
public class SignDecider {

    // Java can be extremely irritating some times. 
    // You can't get a reverse_iterator, so instead we order the integers from
    // greatest to smallest.
    private static class IntegerComparator implements Comparator {
	public IntegerComparator(){}
	public int compare(Object o1,
			   Object o2) {
	    return ((Integer)o2).compareTo((Integer)o1);
	}
    }

    /**
     * If v is non-zero return an integer exp, so that (0.5 <= |v|*2^(-exp) < 1).
     * this is analogous to the integer part of the return value of frexp in C.
     * If v is zero return 0.
     */
    public static int getExp(double v) {
	if (v==0)
	    return 0;
	return (int)((0x7ff0000000000000L & Double.doubleToLongBits(v))>>52)-1022;
    }

    static IntegerComparator comp=new IntegerComparator();
    TreeMap pos, neg;

    // these tree maps will be maps integer multiples of 62 
    // to longs
    // if val->exp then the key represents the number val*2^exp

    // the value of the SignDecider is the sup of all positive 
    // keys minus the sum of all negative keys

    /** Construct zero
     */
    public SignDecider(){
	pos=new TreeMap(comp);
	neg=new TreeMap(comp);
    }

    /** Converts a double into a SignDecider
     */
    public SignDecider(double v){
	pos=new TreeMap(comp);
	neg=new TreeMap(comp);

	if (v==0) 
	    return;

	// take the integral part
	long ip=(Double.doubleToLongBits(v) & 0x000fffffffffffffL) 
	    | 0x0010000000000000L;

	int exp=getExp(v)-53;
	// now |v| = ip*2^exp

	// set a to be the greatest multiple of 62 less than exp
	int a=62*((exp >= 0) ? (exp / 62) : ( (exp - 61 ) / 62 ));
	if (exp-a<10) {
	    if (v>=0) {
		pos.put(new Integer(a),
			new Long(ip<<(exp-a)));
	    } else {
		neg.put(new Integer(a),
			new Long(ip<<(exp-a)));
	    }
	} else {
	    if (v>0) {
		long first=((ip<<(exp-a)) & 0x3fffffffffffffffL);
		if (first != 0) {
		    pos.put(new Integer(a),
			    new Long(first));
		}
		pos.put(new Integer(62+a),
			new Long(ip>>(62+a-exp)));
	    } else {
		long first=((ip<<(exp-a)) & 0x3fffffffffffffffL);
		if (first != 0) {
		    neg.put(new Integer(a),
			    new Long(first));
		}
		neg.put(new Integer(62+a),
			new Long(ip>>(62+a-exp)));
	    }
	}
    }

    /**
     * Multiplies this SignDecider by negative one. This changes your Signdecider (into its negative).
     * Then it is returned for convienience.
     */
    public SignDecider negate() {
	TreeMap temp=pos;
	pos=neg;
	neg=temp;
	return this;
    }

    private static void addToTree(Integer a, Long l, TreeMap tree) {
	if (l.longValue()==0L) {
	    return;
	}
	Object O=tree.get(a);
	if (O==null) {
	    tree.put(a,l);
	} else {
	    long sum=l.longValue()+((Long)O).longValue();
	    long sum2=sum & 0x3fffffffffffffffL;
	    if (sum==sum2) {
		tree.put(a,
			 new Long(sum2));
	    } else {
		if (sum2!=0) {
		    tree.put(a,
			     new Long(sum2));
		} else {
		    tree.remove(a);
		}
		// we need to carry a one.
		SignDecider.addToTree(new Integer(a.intValue()+62),
				      new Long(1L),
				      tree);
	    }
	}
    }

    /** add sd to this SignDecider. This will be changed into sd+this and then it will be
     * returned as well. This allows repeated calls like: sd.add(sd1).add(sd2);
     * Warning: you should never add a SignDecider to itself. This could be aranged, but
     * whats the point?
     */
    public SignDecider add(SignDecider sd){	
	Set sdset=sd.pos.keySet();
	Iterator it=sdset.iterator();
	Integer I;
	while (it.hasNext()){
	    I=(Integer)it.next();
	    SignDecider.addToTree(I,(Long)sd.pos.get(I),pos);
	}

	sdset=sd.neg.keySet();
	it=sdset.iterator();
	while (it.hasNext()){
	    I=(Integer)it.next();
	    SignDecider.addToTree(I,(Long)sd.neg.get(I),neg);
	}
    	return this;
    }

    public void outputDebugInfo() {
	Integer I;
	Long L;
	double sum1=0, sum2=0;

	System.out.println("Positive Part");
	Set sdset=pos.keySet();
	Iterator it=sdset.iterator();
	while (it.hasNext()){
	    I=(Integer)it.next();
	    L=(Long)pos.get(I);
	    sum1+=L.longValue()*Math.pow(2,I.intValue());
	    System.out.println("   Storing: "+
			       L.toString()+"*2^"+I.toString()+" = "+
			       (L.longValue()*Math.pow(2,I.intValue()))+ 
			       " _______ "+
			       Long.toHexString(L.longValue()));
	}
	System.out.println("---Total: "+sum1);

	System.out.println("Negative Part");
	sdset=neg.keySet();
	it=sdset.iterator();
	while (it.hasNext()){
	    I=(Integer)it.next();
	    L=(Long)neg.get(I);
	    sum2+=L.longValue()*Math.pow(2,I.intValue());
	    System.out.println("   Storing: "+
			       L.toString()+"*2^"+I.toString()+" = "+
			       (L.longValue()*Math.pow(2,I.intValue()))+ 
			       " _______ "+
			       Long.toHexString(L.longValue()));
	}
	System.out.println("---Total: "+sum2);
		
	System.out.println("Final Total: "+(sum1-sum2));
	int s=sign();
	if (s==1) {
	    System.out.println("POSITIVE");
	}
	if (s==-1) {
	    System.out.println("NEGATIVE");
	}
	if (s==0) {
	    System.out.println("ZERO");
	}
    }

    /** return the left 31 bits of this 62 bit long */
    private static long leftHalf(Long l) {
	return l.longValue() >> 31;
    }

    /** return the left 31 bits of this 62 bit long */
    private static long leftHalf(long l) {
	return l >> 31;
    }

    /** return the right 31 bits of this 62 bit long */
    private static long rightHalf(Long l) {
	return l.longValue() & 0x000000007fffffffL;
    }

    /** return the right 31 bits of this 62 bit long */
    private static long rightHalf(long l) {
	return l & 0x000000007fffffffL;
    }

    /** Add sd1*sd2 to sd3 */
    private static void addProductToTree(TreeMap sd1, 
					 TreeMap sd2, 
					 TreeMap sd3) {
	Set set1=sd1.keySet(),
	    set2=sd2.keySet();
	Iterator it1, it2;
	Integer I1,I2;
	int exp;
	Long L1,L2;
	long ls1,ls2,rs1,rs2, temp;

	it1=set1.iterator();
	while (it1.hasNext()){
	    I1=(Integer)it1.next();
	    L1=(Long)sd1.get(I1);
	    ls1=leftHalf(L1);
	    rs1=rightHalf(L1);
	    
	    it2=set2.iterator();
	    while (it2.hasNext()){
		I2=(Integer)it2.next();
		L2=(Long)sd2.get(I2);
		ls2=leftHalf(L2);
		rs2=rightHalf(L2);
		
		exp=I1.intValue()+I2.intValue();
		
		addToTree(new Integer(exp),
			  new Long(rs1*rs2),
			  sd3);
		addToTree(new Integer(exp+62),
			  new Long(ls1*ls2),
			  sd3);
		temp=rs1*ls2;
		addToTree(new Integer(exp),
			  new Long(rightHalf(temp) << 31),
			  sd3);
		addToTree(new Integer(exp+62),
			  new Long(leftHalf(temp)),
			  sd3);
		temp=ls1*rs2;
		addToTree(new Integer(exp),
			  new Long(rightHalf(temp) << 31),
			  sd3);
		addToTree(new Integer(exp+62),
			  new Long(leftHalf(temp)),
			  sd3);
	    }
	}
    }

    /** Adds the product of sd1 and sd2 to this SignDecider. This is modified.
     * @return this storing (this + sd1*sd2)
     */
    public SignDecider addProductTo( SignDecider sd1,
				     SignDecider sd2 ) {
	addProductToTree(sd1.pos, sd2.pos, pos);
	addProductToTree(sd1.pos, sd2.neg, neg);
	addProductToTree(sd1.neg, sd2.pos, neg);
	addProductToTree(sd1.neg, sd2.neg, pos);
	return this;
    }

    /** Subtracts the product of sd1 and sd2 from this SignDecider. This is modified.
     * @return this storing (this - sd1*sd2)
     */
    public SignDecider subtractProductFrom( SignDecider sd1,
					    SignDecider sd2 ) {
	addProductToTree(sd1.pos, sd2.pos, neg);
	addProductToTree(sd1.pos, sd2.neg, pos);
	addProductToTree(sd1.neg, sd2.pos, pos);
	addProductToTree(sd1.neg, sd2.neg, neg);
	return this;
    }
   
				       
    /** At long last: Definatively return the sign of the represented number
     * @return -1 if negative, 1 if positive, 0 if zero
     */
    public int sign() {
	Iterator 
	    pos_it=pos.keySet().iterator(),
	    neg_it=neg.keySet().iterator();
	int pos_i,neg_i;
	long pos_l, neg_l;
	while (true) {
	    if (!(pos_it.hasNext())) {
		if (!(neg_it.hasNext())) 
		    return 0;
		return -1;
	    }
	    if (!(neg_it.hasNext())) 
		return 1;
	    // both iterators have a next
	    pos_i=((Integer)pos_it.next()).intValue();
	    neg_i=((Integer)neg_it.next()).intValue();
	    if (pos_i > neg_i)
		return 1;
	    if (pos_i < neg_i)
		return -1;
	    // otherwise   pos_i == neg_i
	    pos_l=((Long)pos.get(new Integer(pos_i))).longValue();
	    neg_l=((Long)neg.get(new Integer(neg_i))).longValue();
	    if (pos_l > neg_l)
		return 1;
	    if (pos_l < neg_l)
		return -1;
	}
    }
}