mergestate.java

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

    the position to the right of the rightmost equal element (if any).]
    
    "a" is a sorted vector with n elements, starting at a[0].  n must be > 0.
    
    "hint" is an index at which to begin the search, 0 <= hint < n.  The closer
    hint is to the final result, the faster this runs.
    
    The return value is the int k in 0..n such that
    
        a[k-1] < key <= a[k]
    
    pretending that *(a-1) is minus infinity and a[n] is plus infinity.  IOW,
    key belongs at index k; or, IOW, the first k elements of a should precede
    key, and the last n-k should follow key.

    Returns -1 on error.  See listsort.txt for info on the method.
    */

    private int gallop_left(PyObject key, PyObject[] data, int a, int n,
                            int hint)
    {
        //assert_(n > 0 && hint >= 0 && hint < n);
        a += hint;
        int ofs = 1;
        int lastofs = 0;
    
        if (iflt(data[a], key)) {
            /* a[hint] < key -- gallop right, until
             * a[hint + lastofs] < key <= a[hint + ofs]
             */
            int maxofs = n - hint; // data[a + n - 1] is highest
            while (ofs < maxofs) {
                if (iflt(data[a + ofs], key)) {
                    lastofs = ofs;
                    ofs = (ofs << 1) + 1;
                    if (ofs <= 0) // int overflow
                        ofs = maxofs;
                } else {
                    // key < data[a + hint + ofs]
                    break;
                }
            }
            if (ofs > maxofs)
                ofs = maxofs;
            // Translate back to offsets relative to a.
            lastofs += hint;
            ofs += hint;
        } else {
            /* key <= a[hint] -- gallop left, until
             * a[hint - ofs] < key <= a[hint - lastofs]
             */
            int maxofs = hint + 1; // data[a] is lowest
            while (ofs < maxofs) {
                if (iflt(data[a - ofs], key))
                    break;
                // key <= data[a + hint - ofs]
                lastofs = ofs;
                ofs = (ofs << 1) + 1;
                if (ofs <= 0) // int overflow
                    ofs = maxofs;
            }
            if (ofs > maxofs)
                ofs = maxofs;
            // Translate back to offsets relative to a.
            int k = lastofs;
            lastofs = hint - ofs;
            ofs = hint - k;
        }
        a -= hint;
        //assert_(-1 <= lastofs && lastofs < ofs && ofs <= n);
        /* Now a[lastofs] < key <= a[ofs], so key belongs somewhere to the
         * right of lastofs but no farther right than ofs.  Do a binary
         * search, with invariant a[lastofs-1] < key <= a[ofs].
         */
        ++lastofs;
        while (lastofs < ofs) {
            int m = lastofs + ((ofs - lastofs) >> 1);
            if (iflt(data[a + m], key))
                lastofs = m+1;  // data[a + m] < key
            else
                ofs = m;        // key <= data[a + m]
        }
        //assert_(lastofs == ofs); // so data[a + ofs -1] < key <= data[a+ofs]
        return ofs;
    }


    /*
    * Exactly like gallop_left(), except that if key already exists in a[0:n],
    * finds the position immediately to the right of the rightmost equal value.
    *  
    * The return value is the int k in 0..n such that
    *     a[k-1] <= key < a[k]
    * or -1 if error.
    *  
    * The code duplication is massive, but this is enough different given that
    * we're sticking to "<" comparisons that it's much harder to follow if
    * written as one routine with yet another "left or right?" flag.
    */

    private int gallop_right(PyObject key, PyObject[] data, int a, int n,
                             int hint)
    {
        //assert_(n > 0 && hint >= 0 && hint < n);
        a += hint;
        int lastofs = 0;
        int ofs = 1;

        if (iflt(key, data[a])) {
            /* key < a[hint] -- gallop left, until
             * a[hint - ofs] <= key < a[hint - lastofs]
             */
            int maxofs = hint + 1;    /* data[a] is lowest */
            while (ofs < maxofs) {
                if (iflt(key, data[a - ofs])) {
                    lastofs = ofs;
                    ofs = (ofs << 1) + 1;
                    if (ofs <= 0)  // int overflow
                        ofs = maxofs;
                } else {
                    /* a[hint - ofs] <= key */
                    break;
                }
            }
            if (ofs > maxofs)
                ofs = maxofs;
            /* Translate back to positive offsets relative to &a[0]. */
            int k = lastofs;
            lastofs = hint - ofs;
            ofs = hint - k;
        } else {
            /* a[hint] <= key -- gallop right, until
             * a[hint + lastofs] <= key < a[hint + ofs]
             */
            int maxofs = n - hint; /* data[a + n - 1] is highest */
            while (ofs < maxofs) {
                if (iflt(key, data[a + ofs]))
                    break;
                /* a[hint + ofs] <= key */
                lastofs = ofs;
                ofs = (ofs << 1) + 1;
                if (ofs <= 0) /* int overflow */
                    ofs = maxofs;
            }
            if (ofs > maxofs)
                ofs = maxofs;
            /* Translate back to offsets relative to &a[0]. */
            lastofs += hint;
            ofs += hint;
        }
        a -= hint;

        //assert_(-1 <= lastofs && lastofs < ofs && ofs <= n);
        
        /* Now a[lastofs] <= key < a[ofs], so key belongs somewhere to the
         * right of lastofs but no farther right than ofs.  Do a binary
         * search, with invariant a[lastofs-1] <= key < a[ofs].
         */
        ++lastofs;
        while (lastofs < ofs) {
            int m = lastofs + ((ofs - lastofs) >> 1);
            if (iflt(key, data[a + m]))
                ofs = m;        // key < data[a + m]
            else
                lastofs = m+1;  // data[a + m] <= key
        }
        //assert_(lastofs == ofs); // so data[a + ofs -1] <= key < data[a+ofs]
        return ofs;
    }


    void merge_at(int i) {
        //assert_(n >= 2);
        //assert_(i >= 0);
        //assert_(i == n - 2 || i == n - 3);

        int pa = base[i];
        int pb = base[i+1];
        int na = len[i];
        int nb = len[i+1];

        //assert_(na > 0 && nb > 0);
        //assert_(pa + na == pb);

        // Record the length of the combined runs; if i is the 3rd-last
        // run now, also slide over the last run (which isn't involved
        // in this merge).  The current run i+1 goes away in any case.
        if (i == n - 3) {
            len[i+1] = len[i+2];
            base[i+1] = base[i+2];
        }
        len[i] = na + nb;
        --n;

        // Where does b start in a?  Elements in a before that can be
        // ignored (already in place).
        int k = gallop_right(data[pb], data, pa, na, 0);
        pa += k;
        na -= k;
        if (na == 0)
            return;
        
        // Where does a end in b?  Elements in b after that can be
        // ignored (already in place).
        nb = gallop_left(data[pa + na - 1], data, pb, nb, nb-1);
        if (nb == 0)
            return;

        // Merge what remains of the runs, using a temp array with
        // min(na, nb) elements.
        if (na <= nb)
            merge_lo(pa, na, pb, nb);
        else
            merge_hi(pa, na, pb, nb);
    }


    /* Examine the stack of runs waiting to be merged, merging adjacent runs
     * until the stack invariants are re-established:
     *
     * 1. len[-3] > len[-2] + len[-1]
     * 2. len[-2] > len[-1]
     *
     * See listsort.txt for more info.
     */
    void merge_collapse() {
        while (this.n > 1) {
            int n = this.n - 2;
            if (n > 0 && len[n-1] <= len[n] + len[n+1]) {
                if (len[n-1] < len[n+1])
                    --n;
                merge_at(n);
            } else if (len[n] <= len[n+1]) {
                merge_at(n);
            } else {
                break;
            }
        }
    }


    /* Regardless of invariants, merge all runs on the stack until only one
     * remains.  This is used at the end of the mergesort.
     *
     * Returns 0 on success, -1 on error.
     */
    void merge_force_collapse() {
        while (this.n > 1) {
            int n = this.n - 2;
            if (n > 0 && len[n-1] < len[n+1])
                --n;
            merge_at(n);
        }
    }


    /* Compute a good value for the minimum run length; natural runs shorter
     * than this are boosted artificially via binary insertion.
     *
     * If n < 64, return n (it's too small to bother with fancy stuff).
     * Else if n is an exact power of 2, return 32.
     * Else return an int k, 32 <= k <= 64, such that n/k is close to, but
     * strictly less than, an exact power of 2.
     *
     * See listsort.txt for more info.
     */
    int merge_compute_minrun(int n) {
        int r = 0;  // becomes 1 if any 1 bits are shifted off

        //assert_(n >= 0);
        while (n >= 64) {
             r |= n & 1;
             n >>= 1;
        }
        return n + r;
    }


    void assert_(boolean expr) {
        if (!expr)
            throw new RuntimeException("assert");
    }


   private boolean iflt(PyObject x, PyObject y) {
        //assert_(x != null);
        //assert_(y != null);

        if (compare == null) {
            /* NOTE: we rely on the fact here that the sorting algorithm
               only ever checks whether k<0, i.e., whether x<y.  So we
               invoke the rich comparison function with _lt ('<'), and
               return -1 when it returns true and 0 when it returns
               false. */
            return x._lt(y).__nonzero__();
        }

        PyObject ret = compare.__call__(x, y);

        if (ret instanceof PyInteger) {
            int v = ((PyInteger)ret).getValue();
            return v < 0;
        }
        throw Py.TypeError("comparision function must return int");
    }            


    void reverse_slice(int lo, int hi) {
        --hi;
        while (lo < hi) {
            PyObject t = data[lo];
            data[lo] = data[hi];
            data[hi] = t;
            ++lo;
            --hi;
        }
    }



    /*
     * binarysort is the best method for sorting small arrays: it does
     * few compares, but can do data movement quadratic in the number of
     * elements.
     * [lo, hi) is a contiguous slice of a list, and is sorted via
     * binary insertion.  This sort is stable.
     * On entry, must have lo <= start <= hi, and that [lo, start) is already
     * sorted (pass start == lo if you don't know!).
     * If islt() complains return -1, else 0.
     * Even in case of error, the output slice will be some permutation of
     * the input (nothing is lost or duplicated).
     */
    void binarysort(int lo, int hi, int start) {
        //debug("binarysort: lo:" + lo + " hi:" + hi + " start:" + start);
        int p;

        //assert_(lo <= start && start <= hi);
        /* assert [lo, start) is sorted */
        if (lo == start)
                ++start;
        for (; start < hi; ++start) {
            /* set l to where *start belongs */
            int l = lo;
            int r = start;
            PyObject pivot = data[r];
            // Invariants:
            // pivot >= all in [lo, l).
            // pivot  < all in [r, start).
            // The second is vacuously true at the start.
            //assert_(l < r);
            do {
                p = l + ((r - l) >> 1);
                if (iflt(pivot, data[p]))
                    r = p;
                else
                    l = p+1;
            } while (l < r);
            //assert_(l == r);
            // The invariants still hold, so pivot >= all in [lo, l) and
            // pivot < all in [l, start), so pivot belongs at l.  Note
            // that if there are elements equal to pivot, l points to the
            // first slot after them -- that's why this sort is stable.
            // Slide over to make room.
            for (p = start; p > l; --p)
                data[p] = data[p - 1];
            data[l] = pivot;
        }
        //dump_data("binsort", lo, hi - lo);
    }


    private void dump_data(String txt, int lo, int n) {
/*
        System.out.print(txt + ":");
        for (int i = 0; i < n; i++)
            System.out.print(data[lo + i] + " ");
        System.out.println();
*/
    }

    private void debug(String str) {
        //System.out.println(str);
    }
}