001    /*
002     * $Id: RootUtil.java 3652 2011-06-02 18:17:04Z kredel $
003     */
004    
005    package edu.jas.root;
006    
007    
008    import java.util.List;
009    
010    import org.apache.log4j.Logger;
011    
012    import edu.jas.structure.RingElem;
013    import edu.jas.structure.RingFactory;
014    import edu.jas.arith.Rational;
015    import edu.jas.poly.Complex;
016    
017    
018    /**
019     * Real root utilities. For example real root count.
020     * @author Heinz Kredel
021     */
022    public class RootUtil {
023    
024    
025        private static final Logger logger = Logger.getLogger(RootUtil.class);
026    
027    
028        private static boolean debug = logger.isDebugEnabled();
029    
030    
031        /**
032         * Count changes in sign.
033         * @param <C> coefficient type.
034         * @param L list of coefficients.
035         * @return number of sign changes in L.
036         */
037        public static <C extends RingElem<C>> long signVar(List<C> L) {
038            long v = 0;
039            if (L == null || L.isEmpty()) {
040                return v;
041            }
042            C A = L.get(0);
043            for (int i = 1; i < L.size(); i++) {
044                C B = L.get(i);
045                while (B == null || B.signum() == 0) {
046                    i++;
047                    if (i >= L.size()) {
048                        return v;
049                    }
050                    B = L.get(i);
051                }
052                if (A.signum() * B.signum() < 0) {
053                    v++;
054                }
055                A = B;
056            }
057            return v;
058        }
059    
060    
061        /**
062         * Parse interval for a real root from String.
063         * @param s String, syntax: [left, right] or [mid].
064         * @return Interval from s.
065         */
066        public static <C extends RingElem<C> & Rational> 
067          Interval<C> parseInterval(RingFactory<C> fac, String s) {
068            int r = s.length();
069            int el = s.indexOf("[");
070            if ( el >= 0 ) {
071                int ri = s.indexOf("]");
072                if ( ri > 0 ) {
073                    r = ri;
074                }
075            } else {
076                el = -1;
077            }
078            //System.out.println("s  = " + s);
079            String iv = s.substring(el+1,r).trim();
080            //System.out.println("iv = " + iv);
081            int k = iv.indexOf(",");
082            if ( k < 0 ) {
083                k = s.indexOf(" ");
084            }
085            if ( k < 0 ) {
086                C mid = fac.parse(iv);
087                return new Interval<C>(mid);
088            }
089            //System.out.println("k  = " + k + ", len = " + iv.length());
090            String ls = iv.substring(0,k).trim();
091            String rs = iv.substring(k+1,iv.length()).trim();
092            //System.out.println("ls = " + ls + ", rs = " + rs);
093            C left = fac.parse(ls);;
094            C right = fac.parse(rs);;
095            //System.out.println("left = " + left + ", right = " + right);
096            return new Interval<C>(left,right);
097        }
098    
099    
100        /**
101         * Parse rectangle for a complex root from String.
102         * @param s String, syntax: [south-west, north-east] or [mid].
103         * @return Interval from s.
104         */
105        public static <C extends RingElem<C> & Rational> 
106          Rectangle<C> parseRectangle(RingFactory<Complex<C>> fac, String s) {
107            int r = s.length();
108            int el = s.indexOf("[");
109            if ( el >= 0 ) {
110                int ri = s.indexOf("]");
111                if ( ri > 0 ) {
112                    r = ri;
113                }
114            } else {
115                el = -1;
116            }
117            //System.out.println("s  = " + s);
118            String iv = s.substring(el+1,r).trim();
119            //System.out.println("iv = " + iv);
120            int k = iv.indexOf(",");
121            if ( k < 0 ) {
122                k = s.indexOf(" ");
123            }
124            if ( k < 0 ) {
125                Complex mid = fac.parse(iv);
126                return new Rectangle<C>(mid);
127            }
128            //System.out.println("k  = " + k + ", len = " + iv.length());
129            String ls = iv.substring(0,k).trim();
130            String rs = iv.substring(k+1,iv.length()).trim();
131            //System.out.println("ls = " + ls + ", rs = " + rs);
132            Complex sw = fac.parse(ls);;
133            Complex ne = fac.parse(rs);;
134            //System.out.println("left = " + left + ", right = " + right);
135            return new Rectangle<C>(sw,ne);
136        }
137    
138    }