/*
 * Main.java
 *
 * Created on February 6, 2008, 1:57 PM
 *
 *
 * There is a version w/o ..._AR in package LIST_AR_purge with classnames
 * LIST_purge, LIST, and POSITION
 *
 * To change this template, choose Tools | Template Manager
 * and open the template in the editor.
 */

package list_ar_purge;

/**
 *
 * @author suchenek
 */
//Copyright Dr. Marek A. Suchenek, 2005, 2006, 2007, 2008 - 2025

public class LIST_AR_purge {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here

        int R = 10;
        LIST_AR L = new LIST_AR(R); // R% multiplicative increment for resizing
        Object x;

        // The code below creates a list
        // of N consecutive numbers
        // with duplicity W repeated M times

        int length = 0;
        int K = 10;//100;//120; //number of different values (size of output)
        int M = 10;//1000;//84; //degree of duplicity - macro
        int W = 10;//1;//1; //degree of duplicity - micro

        cnt.clr(); //cost of LIST operations
        cnt2.clr(); //cost of LIST resizing
        cnt3.clr(); //cost of POSITION operations

        for (int k = 0; k < M; k++) {
            for (int i = 0; i < K; i++) {
                x = new Integer(i);
                for (int u = 0; u < W; u++) {
                    L.Insert(L.End(), x);
                    length++;
                }
            }
        }
        int N = length;

        System.out.println("N = " + N);
        cnt.outln("Cost of LIST operations for creation of the list = ");
        cnt2.outln("Cost of LIST resizing = for creation of the list ");
        System.out.println("Theoretic approximation of cost of resizing R("
                + N + ") = " + costResizeBound(N, R));
        // 2 factors inject error: cost of resizing may be accounted as part
        // of the cost of insertion and deletion, and
        // if the resizing factor is not integer, the theoretic formula is not exact
        System.out.println("Total cost of creation of the list = "
                + (cnt.get()+cnt2.get()));
        System.out.println("Total cost per element of creation of the list = "
                + 1.0*(cnt.get()+cnt2.get())/N);
        cnt3.outln("Cost of POSITION manipulations for creation of the list = ");


        // End of "The code below ..."

        cnt.clr(); //cost of LIST operations
        cnt2.clr(); //cost of LIST resizing
        cnt3.clr(); //cost of POSITION operations


        for (POSITION_AR p = L.First(); !p.isEqual(L.End()); p = L.Next(p)) {
            System.out.print(((Integer) L.Select(p)) + " ");
        }
        System.out.println();

        System.out.println("Total cost of traversing the list = "
                + (cnt.get()+cnt2.get()));
        System.out.println("Total cost per element of creation of the list = "
                + 1.0*(cnt.get()+cnt2.get())/N);
        cnt3.outln("Cost of POSITION manipulations for traversing of the list = ");

                cnt.clr();
                LIST_AR C = L.clone();
                cnt.out("Clonning toook ", " steps");
                System.out.println(" N + 1 = " + (N+1));

                LIST_AR D = L;

        cnt.clr(); //cost of LIST operations
        cnt2.clr(); //cost of LIST resizing
        cnt3.clr(); //cost of POSITION operations


        System.out.println("Purge it!");
        LIST_AR_purge.Purge(L);

        cnt.outln("Cost of LIST operations for purging of the list = ");
        cnt2.outln("Cost of LIST resizing = for purging of the list ");
        System.out.println("Total cost of purging of the list = " + (cnt.get()+cnt2.get()));
        System.out.print("Experimantal bounds: lower 1.5*N^2/6 = " + ((long)(N) * (N) * 15 / 60));
        System.out.println(" upper 1.5*N^2 = " + ((long)(N) * (N) * 15 / 10));


        cnt3.outln("Cost of POSITION manipulations for purging of the list = ");

        System.out.println("Purged list");

        for (POSITION_AR p = L.First(); !p.isEqual(L.End()); p = L.Next(p)) {
            System.out.print(((Integer) L.Select(p)) + " ");
        }
        System.out.println();

        System.out.println("Same, in the reverse order");
        for (POSITION_AR p = L.End(); !p.isEqual(L.First()); p = L.Previous(p)) {
            System.out.print(((Integer) L.Select(L.Previous(p))) + " ");
        }
        System.out.println();

        System.out.println("Copied list:");
		for (POSITION_AR p = D.First(); !p.isEqual(D.End()); p = D.Next(p))
				System.out.print(((Integer)D.Select(p)) + " ");
        System.out.println();
        System.out.println("Cloned list:");
		for (POSITION_AR p = C.First(); !p.isEqual(C.End()); p = C.Next(p))
				System.out.print(((Integer)C.Select(p)) + " ");
        System.out.println();
        Purge(C);
        System.out.println("Purged cloned list:");
		for (POSITION_AR p = C.First(); !p.isEqual(C.End()); p = C.Next(p))
				System.out.print(((Integer)C.Select(p)) + " ");
        System.out.println();


    }

    public static void Purge(LIST_AR L) {

        for (POSITION_AR p = L.First(); !p.isEqual(L.End()); p = L.Next(p)) {
            Object x = L.Select(p);
            POSITION_AR q = L.Next(p);
            while (!q.isEqual(L.End())) {
                Object y = L.Select(q);
                if (LIST_AR_purge.isEqual(x, y)) {
                    L.Delete(q);
                } else {
                    q = L.Next(q);
                }
            }
        }
    }

    public static boolean isEqual(Object x, Object y) {
        return (((Integer)x).intValue() == ((Integer)y).intValue());
    }


    public static int costResizeBound(int N, int R)
    {
        // 2 factors inject error: cost of resizing may be accounted as part
        // of the cost of insertion and deletion, and
        // if the resizing factor is not integer, the theoretic formula is not exact

        double r = R/100.; //resizing increment as a fraction
        double d = r + 1; //resizing factor
        double logd = Math.log(N/10)/Math.log(d); // log base d of N/10
        double ceil = Math.ceil(logd); // ceiling of log base d of N/10
        double expc = Math.exp(ceil*Math.log(d)); // 10 to power ceiling of log base d of N/10
        double dcostResize = 10*(expc - 1)/r; // an upper bound on cost of resizing
        int costResize = (int)Math.ceil(dcostResize); // an integer upper bound on cost of resizing
//        System.out.println("*** N = " + N + " R = " + R);
//        System.out.println("r = " + r);
//        System.out.println("d = " + d);
//        System.out.println("logd = " + logd);
//        System.out.println("ceil = " + ceil);
//        System.out.println("expc = " + expc);
//        System.out.println("dcostResize = " + dcostResize);
//        System.out.println("costResize = " + costResize);
        return costResize;
    }
}