mergestate.java

无线通信的主要编程软件,是无线通信工作人员的必备工具,关天相关教程我会在后续传上.

// Copyright 2002 Finn Bock

package org.python.core;

/**
 * The MergeState class is a java implementation of the sort created
 * Tim Peters and added to CPython2.3.
 *
 * The algorithm is described in details in the file
 * python/dist/src/Objects/listsort.txt in the CPython development CVS.
 */
class MergeState {
    /**
     * The maximum number of entries in a MergeState's pending-runs stack.
     * This is enough to sort arrays of size up to about
     *     32 * phi ** MAX_MERGE_PENDING
     * where phi ~= 1.618.  85 is ridiculously large enough, good for an
     * array with 2**64 elements.
     */
    static final int MAX_MERGE_PENDING = 85;

    /**
     * If a run wins MIN_GALLOP times in a row, we switch to galloping mode,
     * and stay there until both runs win less often than MIN_GALLOP
     * consecutive times.  See listsort.txt for more info.
     */
    static final int MIN_GALLOP = 8;

    /**
     * Initial temp array size
     */
    static final int MERGESTATE_TEMP_SIZE = 256;

    private PyObject[] a = new PyObject[MERGESTATE_TEMP_SIZE];

    private int[] base = new int[MAX_MERGE_PENDING];
    private int[] len = new int[MAX_MERGE_PENDING];

    private PyObject compare;
    private PyObject[] data;
    private int size;
    private int n;

    MergeState(PyObject[] data, int size, PyObject compare) {
        this.data = data;
        this.compare = compare;
        this.size = size;
        this.n = 0;
    }

    public void sort() {
        int nremaining = size;
        if (nremaining < 2) {
            return;
        }

        int lo = 0;
        int hi = nremaining;
        int minrun = merge_compute_minrun(nremaining);

        boolean[] descending = new boolean[1];
        do {
            /* Identify next run. */
            int n = count_run(lo, hi, descending);
            if (descending[0])
                reverse_slice(lo, lo + n);
            /* If short, extend to min(minrun, nremaining). */
            if (n < minrun) {
                int force = nremaining < minrun ?  nremaining : minrun;
                binarysort(lo, lo + force, lo + n);
                n = force;
            }
            /* Push run onto pending-runs stack, and maybe merge. */
            //ms.assert_(ms.n < ms.MAX_MERGE_PENDING);
            base[this.n] = lo;
            len[this.n] = n;
            ++this.n;
            merge_collapse();
            /* Advance to find next run */
            lo += n;
            nremaining -= n;
        } while (nremaining != 0);
        //assert_(lo == hi);

        merge_force_collapse();
        //assert_(ms.n == 1);
        //assert_(ms.base[0] == 0);
        //assert_(ms.len[0] == size);
    }

    public void getmem(int need) {
        if (need <= a.length)
            return;
        a = new PyObject[need];
    }

    int count_run(int lo, int hi, boolean[] descending) {
        //assert_(lo < hi);
        descending[0] = false;
        ++lo;
        if (lo == hi)
            return 1;
        int n = 2;
        if (iflt(data[lo], data[lo-1])) {
            descending[0] = true;
            for (lo = lo + 1; lo < hi; ++lo, ++n) {
                if (! iflt(data[lo], data[lo-1]))
                    break;
            }
        } else {
            for (lo = lo + 1; lo < hi; ++lo, ++n) {
                if (iflt(data[lo], data[lo-1]))
                    break;
            }
        }
        return n;
    }


    void merge_lo(int pa, int na, int pb, int nb) {
        //debug("merge_lo pa:" + pa + " na:" + na + " pb:" + pb + " nb:" + nb);
        int cnt = nb + na;
        int origpa = pa;
        //dump_data("padata", pa, na);
        //dump_data("pbdata", pb, nb);

        //assert_(na > 0 && nb > 0 && pa + na == pb);
        getmem(na);
        System.arraycopy(data, pa, a, 0, na);
        int dest = pa;
        pa = 0;

        data[dest++] = data[pb++];
        --nb;
        if (nb == 0)
            return;
        if (na == 1) {
            // CopyB;
            System.arraycopy(data, pb, data, dest, nb);
            data[dest + nb] = a[pa];
            return;
        }

        try {
            PyObject compare = this.compare;
            for (;;) {
                int acount = 0; /* # of time A won in a row */
                int bcount = 0; /* # of time B won in a row */

                /* Do the straightforward thing until (if ever) one run
                 * appears to win consistently.
                 */
                for (;;) {
                    boolean k = iflt(data[pb], a[pa]);
                    if (k) {
                        data[dest++] = data[pb++];
                        ++bcount;
                        acount = 0;
                        --nb;
                        if (nb == 0)
                            return;
                        if (bcount >= MIN_GALLOP)
                            break;
                    } else {
                        data[dest++] = a[pa++];
                        ++acount;
                        bcount = 0;
                        --na;
                        if (na == 1) {
                            // CopyB;
                            System.arraycopy(data, pb, data, dest, nb);
                            data[dest + nb] = a[pa];
                            na = 0;
                            return;
                        }
                        if (acount >= MIN_GALLOP)
                            break;
                    }
                }

                /* One run is winning so consistently that galloping may
                 * be a huge win. So try that, and continue galloping until
                 * (if ever) neither run appears to be winning consistently
                 * anymore.
                 */
                do {
                    int k = gallop_right(data[pb], a, pa, na, 0);
                    acount = k;
                    if (k != 0) {
                        System.arraycopy(a, pa, data, dest, k);
                        dest += k;
                        pa += k;
                        na -= k;
                        if (na == 1) {
                            // CopyB
                            System.arraycopy(data, pb, data, dest, nb);
                            data[dest + nb] = a[pa];
                            na = 0;
                            return;
                        }
                        /* na==0 is impossible now if the comparison
                         * function is consistent, but we can't assume
                         * that it is.
                         */
                        if (na == 0)
                            return;
                    }

                    data[dest++] = data[pb++];
                    --nb;
                    if (nb == 0)
                        return;

                    k = gallop_left(a[pa], data, pb, nb, 0);
                    bcount = k;
                    if (k != 0) {
                        System.arraycopy(data, pb, data, dest, k);
                        dest += k;
                        pb += k;
                        nb -= k;
                        if (nb == 0)
                            return;
                    }
                    data[dest++] = a[pa++];
                    --na;
                    if (na == 1) {
                        // CopyB;
                        System.arraycopy(data, pb, data, dest, nb);
                        data[dest + nb] = a[pa];
                        na = 0;
                        return;
                    }
                } while (acount >= MIN_GALLOP || bcount >= MIN_GALLOP);
            }
        } finally {
            if (na != 0)
                System.arraycopy(a, pa, data, dest, na);

            //dump_data("result", origpa, cnt);
        }
    }



    void merge_hi(int pa, int na, int pb, int nb) {
        //debug("merge_hi pa:" + pa + " na:" + na + " pb:" + pb + " nb:" + nb);
        int cnt = nb + na;
        int origpa = pa;
        //dump_data("padata", pa, na);
        //dump_data("pbdata", pb, nb);

        //assert_(na > 0 && nb > 0 && pa + na == pb);
        getmem(nb);
        int dest = pb + nb - 1;
        int basea = pa;
        System.arraycopy(data, pb, a, 0, nb);

        pb = nb - 1;
        pa += na - 1;

        data[dest--] = data[pa--];
        --na;
        if (na == 0)
            return;
        if (nb == 1) {
            // CopyA;
            dest -= na;
            pa -= na;
            System.arraycopy(data, pa+1, data, dest+1, na);
            data[dest] = a[pb];
            nb = 0;
            return;
        }

        try {
            PyObject compare = this.compare;
            for (;;) {
                int acount = 0; /* # of time A won in a row */
                int bcount = 0; /* # of time B won in a row */

                /* Do the straightforward thing until (if ever) one run
                 * appears to win consistently.
                 */
                for (;;) {
                    boolean k = iflt(a[pb], data[pa]);
                    if (k) {
                        data[dest--] = data[pa--];
                        ++acount;
                        bcount = 0;
                        --na;
                        if (na == 0)
                            return;
                        if (acount >= MIN_GALLOP)
                            break;
                    } else {
                        data[dest--] = a[pb--];
                        ++bcount;
                        acount = 0;
                        --nb;
                        if (nb == 1) {
                            // CopyA
                            dest -= na;
                            pa -= na;
                            System.arraycopy(data, pa+1, data, dest+1, na);
                            data[dest] = a[pb];
                            nb = 0;
                            return;
                        }
                        if (bcount >= MIN_GALLOP)
                            break;
                    }
                }

                /* One run is winning so consistently that galloping may
                 * be a huge win. So try that, and continue galloping until
                 * (if ever) neither run appears to be winning consistently
                 * anymore.
                 */
                do {
                    int k = gallop_right(a[pb], data, basea, na, na-1);
                    acount = k = na - k;
                    if (k != 0) {
                        dest -= k;
                        pa -= k;
                        System.arraycopy(data, pa+1, data, dest+1, k);
                        na -= k;
                        if (na == 0)
                            return;
                    }

                    data[dest--] = a[pb--];
                    --nb;
                    if (nb == 1) {
                        // CopyA
                        dest -= na;
                        pa -= na;
                        System.arraycopy(data, pa+1, data, dest+1, na);
                        data[dest] = a[pb];
                        nb = 0;
                        return;
                    }

                    k = gallop_left(data[pa], a, 0, nb, nb-1);
                    bcount = k = nb - k;
                    if (k != 0) {
                        dest -= k;
                        pb -= k;
                        System.arraycopy(a, pb+1, data, dest+1, k);
                        nb -= k;
                        if (nb == 1) {
                            // CopyA
                            dest -= na;
                            pa -= na;
                            System.arraycopy(data, pa+1, data, dest+1, na);
                            data[dest] = a[pb];
                            nb = 0;
                            return;
                        }
                        /* nb==0 is impossible now if the comparison
                         * function is consistent, but we can't assume
                         * that it is.
                         */
                        if (nb == 0)
                            return;
                    }
                    data[dest--] = data[pa--];
                    --na;
                    if (na == 0)
                        return;
                } while (acount >= MIN_GALLOP || bcount >= MIN_GALLOP);
            }
        } finally {
            if (nb != 0)
                System.arraycopy(a, 0, data, dest-(nb-1), nb);

            //dump_data("result", origpa, cnt);
        }
    }        



   /*
    Locate the proper position of key in a sorted vector; if the vector contains
    an element equal to key, return the position immediately to the left of
    the leftmost equal element.  [gallop_right() does the same except returns