001/*
002 * $Id: RootUtil.java 4063 2012-07-27 13:05:07Z kredel $
003 */
004
005package edu.jas.root;
006
007
008import java.util.List;
009
010import org.apache.log4j.Logger;
011
012import edu.jas.arith.Rational;
013import edu.jas.poly.Complex;
014import edu.jas.structure.RingElem;
015import edu.jas.structure.RingFactory;
016
017
018/**
019 * Real root utilities. For example real root count.
020 * @author Heinz Kredel
021 */
022public 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> Interval<C> parseInterval(RingFactory<C> fac, String s) {
067        int r = s.length();
068        int el = s.indexOf("[");
069        if (el >= 0) {
070            int ri = s.indexOf("]");
071            if (ri > 0) {
072                r = ri;
073            }
074        } else {
075            el = -1;
076        }
077        //System.out.println("s  = " + s);
078        String iv = s.substring(el + 1, r).trim();
079        //System.out.println("iv = " + iv);
080        int k = iv.indexOf(",");
081        if (k < 0) {
082            k = s.indexOf(" ");
083        }
084        if (k < 0) {
085            C mid = fac.parse(iv);
086            return new Interval<C>(mid);
087        }
088        //System.out.println("k  = " + k + ", len = " + iv.length());
089        String ls = iv.substring(0, k).trim();
090        String rs = iv.substring(k + 1, iv.length()).trim();
091        //System.out.println("ls = " + ls + ", rs = " + rs);
092        C left = fac.parse(ls);
093        C right = fac.parse(rs);
094        if (debug) {
095            logger.debug("Interval: left = " + left + ", right = " + right);
096        }
097        return new Interval<C>(left, right);
098    }
099
100
101    /**
102     * Parse rectangle for a complex root from String.
103     * @param s String, syntax: [south-west, north-east] or [mid].
104     * @return Interval from s.
105     */
106    public static <C extends RingElem<C> & Rational> Rectangle<C> parseRectangle(RingFactory<Complex<C>> fac,
107                    String s) {
108        int r = s.length();
109        int el = s.indexOf("[");
110        if (el >= 0) {
111            int ri = s.indexOf("]");
112            if (ri > 0) {
113                r = ri;
114            }
115        } else {
116            el = -1;
117        }
118        //System.out.println("s  = " + s);
119        String iv = s.substring(el + 1, r).trim();
120        //System.out.println("iv = " + iv);
121        int k = iv.indexOf(",");
122        if (k < 0) {
123            k = s.indexOf(" ");
124        }
125        if (k < 0) {
126            Complex mid = fac.parse(iv);
127            return new Rectangle<C>(mid);
128        }
129        //System.out.println("k  = " + k + ", len = " + iv.length());
130        String ls = iv.substring(0, k).trim();
131        String rs = iv.substring(k + 1, iv.length()).trim();
132        //System.out.println("ls = " + ls + ", rs = " + rs);
133        Complex sw = fac.parse(ls);
134        Complex ne = fac.parse(rs);
135        if (debug) {
136            logger.debug("Rectangle: sw = " + sw + ", ne = " + ne);
137        }
138        return new Rectangle<C>(sw, ne);
139    }
140
141}