/*
 * $Id$
 */

package edu.jas.application;


import java.io.Serializable;
import java.util.ArrayList;
import java.util.BitSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.SortedMap;
import java.util.TreeMap;

import org.apache.log4j.Logger;

import edu.jas.poly.ExpVector;
import edu.jas.poly.GenPolynomial;
import edu.jas.poly.GenPolynomialRing;
import edu.jas.poly.GenSolvablePolynomialRing;
import edu.jas.structure.GcdRingElem;
import edu.jas.structure.RingFactory;


/**
 * Pair list management. Implemented for ColorPolynomials using TreeMap and
 * BitSet.
 * @author Heinz Kredel
 */

public class OrderedCPairlist> implements Serializable {


    private static final Logger logger = Logger.getLogger(OrderedCPairlist.class);


    protected final GenPolynomialRing> ring;


    protected final List> P;


    protected final SortedMap>> pairlist;


    protected final List red;


    protected final CReductionSeq reduction;


    protected boolean oneInGB = false;


    protected boolean useCriterion4 = false; // unused


    protected int putCount;


    protected int remCount;


    protected final int moduleVars; // unused


    /**
     * Constructor for OrderedPairlist.
     * @param r polynomial factory.
     */
    public OrderedCPairlist(GenPolynomialRing> r) {
        this(0, r);
    }


    /**
     * Constructor for OrderedPairlist.
     * @param m number of module variables.
     * @param r polynomial factory.
     */
    public OrderedCPairlist(int m, GenPolynomialRing> r) {
        moduleVars = m;
        ring = r;
        P = new ArrayList>();
        pairlist = new TreeMap>>(ring.tord.getAscendComparator());
        // pairlist = new TreeMap( to.getSugarComparator() );
        red = new ArrayList();
        putCount = 0;
        remCount = 0;
        if (ring instanceof GenSolvablePolynomialRing) {
            useCriterion4 = false;
        }
        RingFactory> rf = ring.coFac;
        GenPolynomialRing cf = (GenPolynomialRing) rf;
        reduction = new CReductionSeq(cf.coFac);
    }


    /**
     * Internal constructor for OrderedPairlist. Used to clone this pair list.
     * @param m number of module variables.
     * @param r polynomial factory.
     */
    private OrderedCPairlist(int m, GenPolynomialRing> ring, List> P,
                    SortedMap>> pl, List red, CReductionSeq cred,
                    int pc, int rc) {
        moduleVars = m;
        this.ring = ring;
        this.P = P;
        pairlist = pl;
        this.red = red;
        reduction = cred;
        putCount = pc;
        remCount = rc;
    }


    /**
     * Clone this OrderedPairlist.
     * @return a 2 level clone of this.
     */
    public synchronized OrderedCPairlist copy() {
        return new OrderedCPairlist(moduleVars, ring, new ArrayList>(P),
                        clonePairlist(), cloneBitSet(), reduction, putCount, remCount);
    }


    /**
     * Clone this pairlist.
     * @return a 2 level clone of this pairlist.
     */
    private SortedMap>> clonePairlist() {
        SortedMap>> pl = new TreeMap>>(
                        ring.tord.getAscendComparator());
        for (Map.Entry>> m : pairlist.entrySet()) {
            ExpVector e = m.getKey();
            LinkedList> l = m.getValue();
            l = new LinkedList>(l);
            pl.put(e, l);
        }
        return pl;
    }


    /**
     * Count remaining Pairs.
     * @return number of pairs remaining in this pairlist.
     */
    public int pairCount() {
        int c = 0;
        for (Map.Entry>> m : pairlist.entrySet()) {
            LinkedList> l = m.getValue();
            c += l.size();
        }
        return c;
    }


    /**
     * Clone this reduction BitSet.
     * @return a 2 level clone of this reduction BitSet.
     */
    private List cloneBitSet() {
        List r = new ArrayList(this.red.size());
        for (BitSet b : red) {
            BitSet n = (BitSet) b.clone();
            r.add(n);
        }
        return r;
    }


    /**
     * bitCount.
     * @return number of bits set in this bitset.
     */
    public int bitCount() {
        int c = 0;
        for (BitSet b : red) {
            c += b.cardinality();
        }
        return c;
    }


    /**
     * toString.
     * @return counters of this.
     */
    @Override
    public String toString() {
        int p = pairCount();
        int b = bitCount();
        if (p != b) {
            return "OrderedCPairlist( pairCount=" + p + ", bitCount=" + b + ", putCount=" + putCount
                            + ", remCount=" + remCount + " )";
        }
        return "OrderedCPairlist( pairCount=" + p + ", putCount=" + putCount + ", remCount=" + remCount
                        + " )";
    }


    /**
     * Equals.
     * @param ob an Object.
     * @return true if this is equal to o, else false.
     */
    @Override
    @SuppressWarnings("unchecked")
    public boolean equals(Object ob) {
        OrderedCPairlist c = null;
        try {
            c = (OrderedCPairlist) ob;
        } catch (ClassCastException e) {
            return false;
        }
        if (c == null) {
            return false;
        }
        boolean t = getList().equals(c.getList());
        if (!t) {
            return t;
        }
        t = pairCount() == c.pairCount();
        if (!t) {
            return t;
        }
        return true;
    }


    /**
     * Hash code for this pair list.
     * @see java.lang.Object#hashCode()
     */
    @Override
    public int hashCode() {
        int h;
        h = getList().hashCode();
        h = h << 7;
        h += pairCount(); // findbugs
        return h;
    }


    /**
     * Put one Polynomial to the pairlist and reduction matrix.
     * @param p polynomial.
     * @return the index of the added polynomial.
     */
    public synchronized int put(ColorPolynomial p) {
        putCount++;
        if (oneInGB) {
            return P.size() - 1;
        }
        ExpVector e = p.leadingExpVector();
        // System.out.println("p = " + p);
        int l = P.size();
        for (int j = 0; j < l; j++) {
            ColorPolynomial pj = P.get(j);
            // System.out.println("pj = " + pj);
            ExpVector f = pj.leadingExpVector();
            if (moduleVars > 0) {
                if (e.invLexCompareTo(f, 0, moduleVars) != 0) {
                    continue; // skip pair
                }
            }
            // System.out.println("e = " + e + ", f = " + f);
            ExpVector g = e.lcm(f); // EVLCM( e, f );
            CPair pair = new CPair(pj, p, j, l);
            // redi = (BitSet)red.get(j);
            // /if ( j < l ) redi.set( l );
            // System.out.println("bitset."+j+" = " + redi );

            // multiple pairs under same keys -> list of pairs
            LinkedList> xl = pairlist.get(g);
            if (xl == null) {
                xl = new LinkedList>();
            }
            // xl.addLast( pair ); // first or last ?
            xl.addFirst(pair); // first or last ? better for d- e-GBs
            pairlist.put(g, xl);
        }
        // System.out.println("pairlist.keys@put = " + pairlist.keySet() );
        P.add(p);
        BitSet redi = new BitSet();
        redi.set(0, l); // jdk 1.4
        red.add(redi);
        return P.size() - 1;
    }


    /**
     * Remove the next required pair from the pairlist and reduction matrix.
     * Appy the criterions 3 and 4 to see if the S-polynomial is required.
     * @return the next pair if one exists, otherwise null.
     */
    public synchronized CPair removeNext() {
        if (oneInGB) {
            return null;
        }
        Iterator>>> ip = pairlist.entrySet().iterator();

        CPair pair = null;
        boolean c = false;
        int i, j;

        while (!c && ip.hasNext()) {
            Map.Entry>> me = ip.next();
            ExpVector g = me.getKey();
            LinkedList> xl = me.getValue();
            if (logger.isInfoEnabled())
                logger.info("g  = " + g);
            pair = null;
            while (!c && xl.size() > 0) {
                pair = xl.removeFirst();
                // xl is also modified in pairlist
                i = pair.i;
                j = pair.j;
                // System.out.println("pair(" + j + "," +i+") ");
                //if (useCriterion4) {
                    // c = reduction.criterion4( pair.pi, pair.pj, g );
                //    c = true;
                //}
                c = true; 
                // System.out.println("c4 = " + c);
                //if (c) {
                    // c = criterion3( i, j, g );
                    // System.out.println("c3 = " + c);
                //}
                red.get(j).clear(i); // set(i,false) jdk1.4
            }
            if (xl.size() == 0)
                ip.remove();
            // = pairlist.remove( g );
        }
        if (!c) {
            pair = null;
        } else {
            remCount++; // count only real pairs
        }
        return pair;
    }


    /**
     * Test if there is possibly a pair in the list.
     * @return true if a next pair could exist, otherwise false.
     */
    public synchronized boolean hasNext() {
        return pairlist.size() > 0;
    }


    /**
     * Get the list of polynomials.
     * @return the polynomial list.
     */
    public List> getList() {
        return P;
    }


    /**
     * Get the number of polynomials put to the pairlist.
     * @return the number of calls to put.
     */
    public synchronized int putCount() {
        return putCount;
    }


    /**
     * Get the number of required pairs removed from the pairlist.
     * @return the number of non null pairs delivered.
     */
    public synchronized int remCount() {
        return remCount;
    }


    /**
     * Put to ONE-Polynomial to the pairlist.
     * @param one polynomial. (no more required)
     * @return the index of the last polynomial.
     */
    public synchronized int putOne(ColorPolynomial one) {
        putCount++;
        if (one == null) {
            return P.size() - 1;
        }
        if (!one.isONE()) {
            return P.size() - 1;
        }
        oneInGB = true;
        pairlist.clear();
        P.clear();
        P.add(one);
        red.clear();
        return P.size() - 1;
    }


    /**
     * GB criterium 3.
     * @return true if the S-polynomial(i,j) is required.
     */
    public boolean criterion3(int i, int j, ExpVector eij) {
        // assert i < j;
        boolean s = red.get(j).get(i);
        if (!s) {
            logger.warn("c3.s false for " + j + " " + i);
            return s;
        }
        // now s = true;
        for (int k = 0; k < P.size(); k++) {
            if (i != k && j != k) {
                ColorPolynomial A = P.get(k);
                ExpVector ek = A.leadingExpVector();
                boolean m = eij.multipleOf(ek); // EVMT(eij,ek);
                if (m) {
                    if (k < i) {
                        // System.out.println("k < i "+k+" "+i);
                        s = red.get(i).get(k) || red.get(j).get(k);
                    } else if (i < k && k < j) {
                        // System.out.println("i < k < j "+i+" "+k+" "+j);
                        s = red.get(k).get(i) || red.get(j).get(k);
                    } else if (j < k) {
                        // System.out.println("j < k "+j+" "+k);
                        s = red.get(k).get(i) || red.get(k).get(j);
                    }
                    // System.out.println("s."+k+" = " + s);
                    if (!s) {
                        return s;
                    }
                }
            }
        }
        return true;
    }
}