pylist.java

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

     * return smallest index where an element in the list equals
     * the argument.
     *
     * @param o the argument to test for. Testing is done with
     *          the <code>==</code> operator.
     */
    public int index(PyObject o) {
        return _index(o, "list.index(x): x not in list");
    }

    private int _index(PyObject o, String message) {
        int n = length;
        PyObject[] list = this.list;
        int i=0;
        for (; i<n; i++) {
            if (list[i].equals(o))
                break;
        }
        if (i == n)
            throw Py.ValueError(message);
        return i;
    }

    /**
     * Insert the argument element into the list at the specified
     * index.
     * <br>
     * Same as <code>s[index:index] = [o] if index &gt;= 0</code>.
     *
     * @param index the position where the element will be inserted.
     * @param o     the element to insert.
     */
    public void insert(int index, PyObject o) {
        if (index < 0)
            index = 0;
        if (index > length)
            index = length;
        resize(length+1);
        System.arraycopy(list, index, list, index+1, length-index-1);
        list[index] = o;
    }

    /**
     * Remove the first occurence of the argument from the list.
     * The elements arecompared with the <code>==</code> operator.
     * <br>
     * Same as <code>del s[s.index(x)]</code>
     *
     * @param o     the element to search for and remove.
     */
    public void remove(PyObject o) {
        del(_index(o, "list.remove(x): x not in list"));
    }

    /**
     * Reverses the items of s in place.
     * The reverse() methods modify the list in place for economy
     * of space when reversing a large list. It doesn't return the
     * reversed list to remind you of this side effect.
     */
    public void reverse() {
        PyObject tmp;
        int n = length;
        PyObject[] list = this.list;
        int j = n-1;
        for (int i=0; i<n/2; i++, j--) {
            tmp = list[i];
            list[i] = list[j];
            list[j] = tmp;
        }
    }

    /**
     * Removes and return the last element in the list.
     */
    public PyObject pop() {
        return pop(-1);
    }

    /**
     * Removes and return the <code>n</code> indexed element in the
     * list.
     *
     * @param n the index of the element to remove and return.
     */
    public PyObject pop(int n) {
        if (length==0) {
            throw Py.IndexError("pop from empty list");
        }
        if (n < 0)
            n += length;
        if (n < 0 || n >= length)
            throw Py.IndexError("pop index out of range");
        PyObject v = list[n];

        setslice(n, n+1, 1, Py.EmptyTuple);
        return v;
    }


    /**
     * Append the elements in the argument sequence to the end of the list.
     * <br>
     * Same as <code>s[len(s):len(s)] = o</code>.
     *
     * @param o the sequence of items to append to the list.
     */
    public void extend(PyObject o) {
        setslice(length, length, 1, o);
    }

    public PyObject __iadd__(PyObject o) {
        extend(fastSequence(o, "argument to += must be a sequence"));
        return this;
    }

    /* Implementation is taken from Python 1.5 as written by Guido van
     * Rossum Port to Java is by Jim Hugunin.  This function will almost
     * certainly go away with the builtin sorting provided by JDK 1.2
     */

    /* New quicksort implementation for arrays of object pointers.  Thanks
     * to discussions with Tim Peters.
     */

    /* Comparison function.  Takes care of calling a user-supplied
     * comparison function (any callable Python object).  Calls the
     * standard comparison function, cmpobject(), if the user-supplied
     * function is NULL.
     */
    private static int docompare(PyObject x, PyObject y,
                                 PyObject compare, String cmpop) {
        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. */
            if (cmpop == "<")
                return x._lt(y).__nonzero__() ? -1 : 0;
            if (cmpop == "<=")
                return x._le(y).__nonzero__() ? -1 : 1;
        }

        PyObject ret = compare.__call__(new PyObject[] {x, y});

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

    /* Straight insertion sort.  More efficient for sorting small arrays. */
    private static void insertionsort(PyObject[] array, int off, int size,
                                      PyObject compare)
    {
        int end = off+size;
        for (int i=off+1; i<end; i++) {
            PyObject key = array[i];
            int j = i;
            while (--j >= off) {
                PyObject q = array[j];
                if (docompare(q, key, compare, "<=") <= 0)
                    break;
                array[j+1] = q;
                array[j] = key;
            }
        }
    }

    /* MINSIZE is the smallest array we care to partition; smaller arrays
     * are sorted using a straight insertion sort (above).  It must be at
     * least 2 for the quicksort implementation to work.  Assuming that
     * comparisons are more expensive than everything else (and this is a
     * good assumption for Python), it should be 10, which is the cutoff
     * point: quicksort requires more comparisons than insertion sort for
     * smaller arrays.
     */
    private static final int MINSIZE = 10;

    /* STACKSIZE is the size of our work stack.  A rough estimate is that
     * this allows us to sort arrays of MINSIZE * 2**STACKSIZE, or large
     * enough.  (Because of the way we push the biggest partition first,
     * the worst case occurs when all subarrays are always partitioned
     * exactly in two.)
     */
    private static final int STACKSIZE = 64;

    /* Quicksort algorithm.  If an exception occurred; in this
     * case we leave the array partly sorted but otherwise in good health
     * (i.e. no items have been removed or duplicated).
     */
    private static void quicksort(PyObject[] array, int off, int size,
                                  PyObject compare)
    {
        PyObject tmp, pivot, left, right;
        int lo, hi, l, r;
        int top, k, n, n2;
        int[] lostack = new int[STACKSIZE];
        int[] histack = new int[STACKSIZE];

        /* Start out with the whole array on the work stack */
        lostack[0] = off;
        histack[0] = off+size;
        top = 1;

        /* Repeat until the work stack is empty */
        while (--top >= 0) {
            lo = lostack[top];
            hi = histack[top];

            /* If it's a small one, use straight insertion sort */
            n = hi - lo;
            if (n < MINSIZE) {
                /*
                 * skip it.  The insertion sort at the end will catch these
                 */
                continue;
            }

            /* Choose median of first, middle and last item as pivot */
            l = lo + (n>>1);                 /* Middle */
            r = hi - 1;                      /* Last */

            left = array[l]; right = array[lo];
            if (docompare(left, right, compare, "<") < 0) {
                array[lo] = left; array[l] = right;
            }

            left = array[r]; right = array[l];
            if (docompare(left, right, compare, "<") < 0) {
                array[r] = left; array[l] = right;
            }

            left = array[l]; right = array[lo];
            if (docompare(left, right, compare, "<") < 0) {
                array[lo] = left; array[l] = right;
            }
            pivot = array[l];

            /* Partition the array */
            l = lo+1;
            r = hi-2;
            for (;;) {
                /* Move left index to element > pivot */
                while (l < hi) {
                    if (docompare(array[l], pivot, compare, "<") >= 0)
                        break;
                    l++;
                }
                /* Move right index to element < pivot */
                while (r >= lo) {
                    if (docompare(pivot, array[r], compare, "<") >= 0)
                        break;
                    r--;
                }

                /* If they met, we're through */
                if (l < r) {
                    /* Swap elements and continue */
                    tmp = array[l]; array[l] = array[r]; array[r] = tmp;
                    l++; r--;
                }
                else if (l == r) {
                    l++; r--;
                    break;
                }

                if (l > r)
                    break;
            }

            /* We have now reached the following conditions:
               lo <= r < l <= hi
               all x in [lo,r) are <= pivot
               all x in [r,l)  are == pivot
               all x in [l,hi) are >= pivot
               The partitions are [lo,r) and [l,hi)
            */

            /* Push biggest partition first */
            n = r - lo;
            n2 = hi - l;
            if (n > n2) {
                /* First one is bigger */
                if (n > MINSIZE) {
                    lostack[top] = lo;
                    histack[top++] = r;
                    if (n2 > MINSIZE) {
                        lostack[top] = l;
                        histack[top++] = hi;
                    }
                }
            } else {
                /* Second one is bigger */
                if (n2 > MINSIZE) {
                    lostack[top] = l;
                    histack[top++] = hi;
                    if (n > MINSIZE) {
                        lostack[top] = lo;
                        histack[top++] = r;
                    }
                }
            }
            /* Should assert top < STACKSIZE-1 */
        }

        /* Ouch - even if I screwed up the quicksort above, the
         * insertionsort below will cover up the problem - just a
         * performance hit would be noticable.
         */

        /* insertionsort is pretty fast on the partially sorted list */
        insertionsort(array, off, size, compare);
    }

    /**
     * Sort the items of the list in place. The compare argument is a
     * function of two arguments (list items) which should return
     * -1, 0 or 1 depending on whether the first argument is
     * considered smaller than, equal to, or larger than the second
     * argument. Note that this slows the sorting process down
     * considerably; e.g. to sort a list in reverse order it is much
     * faster to use calls to the methods sort() and reverse() than
     * to use the built-in function sort() with a comparison function
     * that reverses the ordering of the elements.
     *
     * @param compare the comparison function.
     */
    public synchronized void sort(PyObject compare) {
        MergeState ms = new MergeState(list, length, compare);
        ms.sort();
    }

    /**
     * Sort the items of the list in place. Items is compared with the
     * normal relative comparison operators.
     */
    public void sort() {
        sort(null);
    }

    // __class__ boilerplate -- see PyObject for details
    public static PyClass __class__;

    protected PyClass getPyClass() {
        return __class__;
    }

    public int hashCode() {
        throw Py.TypeError("unhashable type");
    }
}