nativearray.java

java中比较著名的js引擎当属mozilla开源的rhino

     */
    private static Scriptable js_sort(Context cx, Scriptable scope,
                                      Scriptable thisObj, Object[] args)
    {
        long length = getLengthProperty(cx, thisObj);

        if (length <= 1) { return thisObj; }

        Object compare;
        Object[] cmpBuf;

        if (args.length > 0 && Undefined.instance != args[0]) {
            // sort with given compare function
            compare = args[0];
            cmpBuf = new Object[2]; // Buffer for cmp arguments
        } else {
            // sort with default compare
            compare = null;
            cmpBuf = null;
        }

        // Should we use the extended sort function, or the faster one?
        if (length >= Integer.MAX_VALUE) {
            heapsort_extended(cx, scope, thisObj, length, compare, cmpBuf);
        }
        else {
            int ilength = (int)length;
            // copy the JS array into a working array, so it can be
            // sorted cheaply.
            Object[] working = new Object[ilength];
            for (int i = 0; i != ilength; ++i) {
                working[i] = getElem(cx, thisObj, i);
            }

            heapsort(cx, scope, working, ilength, compare, cmpBuf);

            // copy the working array back into thisObj
            for (int i = 0; i != ilength; ++i) {
                setElem(cx, thisObj, i, working[i]);
            }
        }
        return thisObj;
    }

    // Return true only if x > y
    private static boolean isBigger(Context cx, Scriptable scope,
                                    Object x, Object y,
                                    Object cmp, Object[] cmpBuf)
    {
        if (cmp == null) {
            if (cmpBuf != null) Kit.codeBug();
        } else {
            if (cmpBuf == null || cmpBuf.length != 2) Kit.codeBug();
        }

        Object undef = Undefined.instance;

        // sort undefined to end
        if (undef == y) {
            return false; // x can not be bigger then undef
        } else if (undef == x) {
            return true; // y != undef here, so x > y
        }

        if (cmp == null) {
            // if no cmp function supplied, sort lexicographically
            String a = ScriptRuntime.toString(x);
            String b = ScriptRuntime.toString(y);
            return a.compareTo(b) > 0;
        }
        else {
            // assemble args and call supplied JS cmp function
            cmpBuf[0] = x;
            cmpBuf[1] = y;
            Callable fun = ScriptRuntime.getValueFunctionAndThis(cmp, cx);
            Scriptable funThis = ScriptRuntime.lastStoredScriptable(cx);

            Object ret = fun.call(cx, scope, funThis, cmpBuf);
            double d = ScriptRuntime.toNumber(ret);

            // XXX what to do when cmp function returns NaN?  ECMA states
            // that it's then not a 'consistent compararison function'... but
            // then what do we do?  Back out and start over with the generic
            // cmp function when we see a NaN?  Throw an error?

            // for now, just ignore it:

            return d > 0;
        }
    }

/** Heapsort implementation.
 * See "Introduction to Algorithms" by Cormen, Leiserson, Rivest for details.
 * Adjusted for zero based indexes.
 */
    private static void heapsort(Context cx, Scriptable scope,
                                 Object[] array, int length,
                                 Object cmp, Object[] cmpBuf)
    {
        if (length <= 1) Kit.codeBug();

        // Build heap
        for (int i = length / 2; i != 0;) {
            --i;
            Object pivot = array[i];
            heapify(cx, scope, pivot, array, i, length, cmp, cmpBuf);
        }

        // Sort heap
        for (int i = length; i != 1;) {
            --i;
            Object pivot = array[i];
            array[i] = array[0];
            heapify(cx, scope, pivot, array, 0, i, cmp, cmpBuf);
        }
    }

/** pivot and child heaps of i should be made into heap starting at i,
 * original array[i] is never used to have less array access during sorting.
 */
    private static void heapify(Context cx, Scriptable scope,
                                Object pivot, Object[] array, int i, int end,
                                Object cmp, Object[] cmpBuf)
    {
        for (;;) {
            int child = i * 2 + 1;
            if (child >= end) {
                break;
            }
            Object childVal = array[child];
            if (child + 1 < end) {
                Object nextVal = array[child + 1];
                if (isBigger(cx, scope, nextVal, childVal, cmp, cmpBuf)) {
                    ++child; childVal = nextVal;
                }
            }
            if (!isBigger(cx, scope, childVal, pivot, cmp, cmpBuf)) {
                break;
            }
            array[i] = childVal;
            i = child;
        }
        array[i] = pivot;
    }

/** Version of heapsort that call getElem/setElem on target to query/assign
 * array elements instead of Java array access
 */
    private static void heapsort_extended(Context cx, Scriptable scope,
                                          Scriptable target, long length,
                                          Object cmp, Object[] cmpBuf)
    {
        if (length <= 1) Kit.codeBug();

        // Build heap
        for (long i = length / 2; i != 0;) {
            --i;
            Object pivot = getElem(cx, target, i);
            heapify_extended(cx, scope, pivot, target, i, length, cmp, cmpBuf);
        }

        // Sort heap
        for (long i = length; i != 1;) {
            --i;
            Object pivot = getElem(cx, target, i);
            setElem(cx, target, i, getElem(cx, target, 0));
            heapify_extended(cx, scope, pivot, target, 0, i, cmp, cmpBuf);
        }
    }

    private static void heapify_extended(Context cx, Scriptable scope,
                                         Object pivot, Scriptable target,
                                         long i, long end,
                                         Object cmp, Object[] cmpBuf)
    {
        for (;;) {
            long child = i * 2 + 1;
            if (child >= end) {
                break;
            }
            Object childVal = getElem(cx, target, child);
            if (child + 1 < end) {
                Object nextVal = getElem(cx, target, child + 1);
                if (isBigger(cx, scope, nextVal, childVal, cmp, cmpBuf)) {
                    ++child; childVal = nextVal;
                }
            }
            if (!isBigger(cx, scope, childVal, pivot, cmp, cmpBuf)) {
                break;
            }
            setElem(cx, target, i, childVal);
            i = child;
        }
        setElem(cx, target, i, pivot);
    }

    /**
     * Non-ECMA methods.
     */

    private static Object js_push(Context cx, Scriptable thisObj,
                                  Object[] args)
    {
        long length = getLengthProperty(cx, thisObj);
        for (int i = 0; i < args.length; i++) {
            setElem(cx, thisObj, length + i, args[i]);
        }

        length += args.length;
        Object lengthObj = setLengthProperty(cx, thisObj, length);

        /*
         * If JS1.2, follow Perl4 by returning the last thing pushed.
         * Otherwise, return the new array length.
         */
        if (cx.getLanguageVersion() == Context.VERSION_1_2)
            // if JS1.2 && no arguments, return undefined.
            return args.length == 0
                ? Undefined.instance
                : args[args.length - 1];

        else
            return lengthObj;
    }

    private static Object js_pop(Context cx, Scriptable thisObj,
                                 Object[] args)
    {
        Object result;
        long length = getLengthProperty(cx, thisObj);
        if (length > 0) {
            length--;

            // Get the to-be-deleted property's value.
            result = getElem(cx, thisObj, length);

            // We don't need to delete the last property, because
            // setLength does that for us.
        } else {
            result = Undefined.instance;
        }
        // necessary to match js even when length < 0; js pop will give a
        // length property to any target it is called on.
        setLengthProperty(cx, thisObj, length);

        return result;
    }

    private static Object js_shift(Context cx, Scriptable thisObj,
                                   Object[] args)
    {
        Object result;
        long length = getLengthProperty(cx, thisObj);
        if (length > 0) {
            long i = 0;
            length--;

            // Get the to-be-deleted property's value.
            result = getElem(cx, thisObj, i);

            /*
             * Slide down the array above the first element.  Leave i
             * set to point to the last element.
             */
            if (length > 0) {
                for (i = 1; i <= length; i++) {
                    Object temp = getElem(cx, thisObj, i);
                    setElem(cx, thisObj, i - 1, temp);
                }
            }
            // We don't need to delete the last property, because
            // setLength does that for us.
        } else {
            result = Undefined.instance;
        }
        setLengthProperty(cx, thisObj, length);
        return result;
    }

    private static Object js_unshift(Context cx, Scriptable thisObj,
                                     Object[] args)
    {
        Object result;
        long length = getLengthProperty(cx, thisObj);
        int argc = args.length;

        if (args.length > 0) {
            /*  Slide up the array to make room for args at the bottom */
            if (length > 0) {
                for (long last = length - 1; last >= 0; last--) {
                    Object temp = getElem(cx, thisObj, last);
                    setElem(cx, thisObj, last + argc, temp);
                }
            }

            /* Copy from argv to the bottom of the array. */
            for (int i = 0; i < args.length; i++) {
                setElem(cx, thisObj, i, args[i]);
            }

            /* Follow Perl by returning the new array length. */
            length += args.length;
            return setLengthProperty(cx, thisObj, length);
        }
        return ScriptRuntime.wrapNumber(length);
    }

    private static Object js_splice(Context cx, Scriptable scope,
                                    Scriptable thisObj, Object[] args)
    {
        /* create an empty Array to return. */
        scope = getTopLevelScope(scope);
        Object result = ScriptRuntime.newObject(cx, scope, "Array", null);
        int argc = args.length;
        if (argc == 0)
            return result;
        long length = getLengthProperty(cx, thisObj);

        /* Convert the first argument into a starting index. */
        long begin = toSliceIndex(ScriptRuntime.toInteger(args[0]), length);
        argc--;

        /* Convert the second argument into count */
        long count;
        if (args.length == 1) {
            count = length - begin;
        } else {
            double dcount = ScriptRuntime.toInteger(args[1]);
            if (dcount < 0) {
                count = 0;
            } else if (dcount > (length - begin)) {
                count = length - begin;
            } else {
                count = (long)dcount;
            }