001: /*=============================================================================
002: * Copyright Texas Instruments 2000-2004. All Rights Reserved.
003: *
004: * This program is free software; you can redistribute it and/or
005: * modify it under the terms of the GNU Lesser General Public
006: * License as published by the Free Software Foundation; either
007: * version 2 of the License, or (at your option) any later version.
008: *
009: * This program is distributed in the hope that it will be useful,
010: * but WITHOUT ANY WARRANTY; without even the implied warranty of
011: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
012: * Lesser General Public License for more details.
013: *
014: * You should have received a copy of the GNU Lesser General Public
015: * License along with this library; if not, write to the Free Software
016: * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
017: *
018: * $ProjectHeader: OSCRIPT 0.155 Fri, 20 Dec 2002 18:34:22 -0800 rclark $
019: */
020:
021: package oscript.data;
022:
023: import oscript.exceptions.*;
024: import oscript.util.StackFrame;
025: import oscript.util.MemberTable;
026:
027: /**
028: * An array instance.
029: *
030: * @author Rob Clark (rob@ti.com)
031: */
032: public class OArray extends OObject implements java.io.Externalizable,
033: MemberTable {
034: /*=======================================================================*/
035: // members:
036: // (I was using java.util.Vector, but it became easier to just do it myself)
037: private Reference[] arr;
038: private int size = 0;
039:
040: /**
041: * Derived class that implements {@link java.io.Externalizable} must
042: * call this if it overrides it. It should override it to save/restore
043: * it's own state.
044: */
045: public void readExternal(java.io.ObjectInput in)
046: throws java.io.IOException, ClassNotFoundException {
047: size = in.readInt();
048: arr = new Reference[size];
049: for (int i = 0; i < size; i++)
050: arr[i] = (Reference) (in.readObject());
051: }
052:
053: /**
054: * Derived class that implements {@link java.io.Externalizable} must
055: * call this if it overrides it. It should override it to save/restore
056: * it's own state.
057: */
058: public void writeExternal(java.io.ObjectOutput out)
059: throws java.io.IOException {
060: out.writeInt(size);
061: for (int i = 0; i < size; i++)
062: out.writeObject(arr[i]);
063: }
064:
065: /*=======================================================================*/
066:
067: /**
068: * The type object for an instance of Array.
069: */
070: public final static Value TYPE = BuiltinType
071: .makeBuiltinType("oscript.data.OArray");
072: public final static String PARENT_TYPE_NAME = "oscript.data.OObject";
073: public final static String TYPE_NAME = "Array";
074: public final static String[] MEMBER_NAMES = new String[] {
075: "castToString", "castToJavaObject", "length", "elementAt",
076: "elementsAt", "iterator", "concat", "join", "slice",
077: "splice", "pop", "push", "shift", "unshift", "reverse",
078: "sort", "every", "some", "filter", "map", "forEach" };
079:
080: /*=======================================================================*/
081: /**
082: */
083: public final static OArray makeArray(final Object arrObject) {
084: return new OJavaArray(arrObject);
085: }
086:
087: public static class OJavaArray extends OArray {
088: private final int len;
089: private final Object arrObject;
090:
091: OJavaArray(Object arrObject) {
092: this .arrObject = arrObject;
093: this .len = java.lang.reflect.Array.getLength(arrObject);
094: }
095:
096: public Object castToJavaObject() {
097: return arrObject;
098: }
099:
100: public int length() {
101: return len;
102: }
103:
104: public synchronized Value elementAt(final int idx)
105: throws PackagedScriptObjectException {
106: if ((idx < 0) || (idx >= length()))
107: throw PackagedScriptObjectException
108: .makeExceptionWrapper(new OIllegalArgumentException(
109: "invalid array index: " + idx));
110:
111: return new AbstractReference() {
112:
113: public void opAssign(Value val)
114: throws PackagedScriptObjectException {
115: Object obj = JavaBridge.convertToJavaObject(val,
116: arrObject.getClass().getComponentType());
117:
118: java.lang.reflect.Array.set(arrObject, idx, obj);
119: }
120:
121: protected Value get() {
122: return JavaBridge
123: .convertToScriptObject(java.lang.reflect.Array
124: .get(arrObject, idx));
125: }
126:
127: };
128: }
129: }
130:
131: /*=======================================================================*/
132: /**
133: * Class Constructor.
134: */
135: public OArray() {
136: this (2);
137: }
138:
139: /**
140: * private constructor, used internally and by compiler...
141: * initialLength == -1 is used to create arrays
142: * that wrap native java arrays, rather than having to do a copy when
143: * an array is passed from java to script. For java arrays, arr should
144: * equal null, so methods that don't work for java arrays know to throw
145: * an exception... ugly, but it works
146: */
147: public OArray(int initialLength) {
148: super ();
149: if (initialLength >= 0)
150: arr = new Reference[initialLength];
151: }
152:
153: /*=======================================================================*/
154: /**
155: * Class Constructor. This constructor is not intended for public
156: * consumption... it is just used by StackFrame$StackFrameArray for
157: * quickly making a safe-copy when already copied out of the stack
158: */
159: public OArray(Reference[] arr, int size) {
160: super ();
161: this .arr = arr;
162: this .size = size;
163: }
164:
165: /*=======================================================================*/
166: /**
167: * Class Constructor. This is the constructor that is called via a
168: * <code>BuiltinType</code> instance.
169: *
170: * @param args arguments to this constructor
171: * @throws PackagedScriptObjectException(Exception) if wrong number of args
172: */
173: public OArray(oscript.util.MemberTable args) {
174: this (args.length());
175:
176: int alen = args.length();
177:
178: for (int i = 0; i < alen; i++)
179: referenceAt(i).reset(args.referenceAt(i));
180: }
181:
182: /*=======================================================================*/
183: /**
184: * Class Constructor. This is the constructor that is called via a
185: * <code>BuiltinType</code> instance.
186: *
187: * @param args arguments to this constructor
188: * @throws PackagedScriptObjectException(Exception) if wrong number of args
189: */
190: public OArray(Value[] args) {
191: this (args.length);
192: int alen = args.length;
193: ensureCapacity(alen - 1);
194: for (int i = 0; i < alen; i++)
195: referenceAt(i).reset(args[i]);
196: }
197:
198: /*=======================================================================*/
199: /**
200: * Get the type of this object. The returned type doesn't have to take
201: * into account the possibility of a script type extending a built-in
202: * type, since that is handled by {@link #getType}.
203: *
204: * @return the object's type
205: */
206: protected Value getTypeImpl() {
207: return TYPE;
208: }
209:
210: /*=======================================================================*/
211: /**
212: * Convert this object to a native java <code>String</code> value.
213: *
214: * @return a String value
215: * @throws PackagedScriptObjectException(NoSuchMethodException)
216: */
217: public String castToString() throws PackagedScriptObjectException {
218: StringBuffer sb = new StringBuffer();
219:
220: sb.append('[');
221:
222: for (int i = 0; i < length(); i++) {
223: if (i != 0)
224: sb.append(", ");
225:
226: sb.append(elementAt(i).castToString());
227: }
228:
229: sb.append(']');
230:
231: return sb.toString();
232: }
233:
234: /*=======================================================================*/
235: /**
236: * Convert this object to a native java <code>Object</code> value.
237: *
238: * @return a java object
239: * @throws PackagedScriptObjectException(NoSuchMemberException)
240: */
241: public Object castToJavaObject()
242: throws PackagedScriptObjectException {
243: Object[] obj = new Object[length()];
244:
245: for (int i = 0; i < obj.length; i++)
246: obj[i] = elementAt(i).castToJavaObject();
247:
248: return obj;
249: }
250:
251: /*=======================================================================*/
252: /**
253: * For types that implement <code>elementAt</code>, this returns the
254: * number of elements. This is the same as the <i>length</i> property
255: * of an object.
256: *
257: * @return an integer length
258: * @throws PackagedScriptObjectException(NoSuchMethodException)
259: * @see #elementAt
260: */
261: public int length() throws PackagedScriptObjectException {
262: return size;
263: }
264:
265: /*=======================================================================*/
266: /**
267: * Get the specified index of this object, if this object is an array. If
268: * needed, the array is grown to the appropriate size.
269: *
270: * @param idx the index to get
271: * @return a reference to the member
272: * @throws PackagedScriptObjectException(NoSuchMethodException)
273: * @see #length
274: */
275: public Value elementAt(Value idx)
276: throws PackagedScriptObjectException {
277: return elementAt((int) (idx.castToExactNumber()));
278: }
279:
280: public synchronized Value elementAt(int idx) {
281: if (idx < 0)
282: throw PackagedScriptObjectException
283: .makeExceptionWrapper(new OIllegalArgumentException(
284: "invalid array index: " + idx));
285: ensureCapacity(idx);
286: return referenceAt(idx, 0);
287: }
288:
289: public final Reference referenceAt(int idx) {
290: return referenceAt(idx, Reference.ATTR_INVALID);
291: }
292:
293: public final Reference referenceAt(int idx, int attr) {
294: if (arr[idx] == null) {
295: arr[idx] = new Reference(attr);
296:
297: if (idx >= size)
298: size = idx + 1;
299: }
300:
301: return arr[idx];
302: }
303:
304: public final void ensureCapacity(int sz) {
305: if (sz >= arr.length) {
306: // grow to fit
307: int newSize = arr.length * 2;
308:
309: if (sz >= newSize)
310: newSize = sz + 1;
311:
312: Reference[] newArr = new Reference[newSize];
313: System.arraycopy(arr, 0, newArr, 0, size);
314: arr = newArr;
315: }
316: }
317:
318: /*=======================================================================*/
319: /**
320: * Get the specified range of this object, if this object is an array.
321: * This returns a copy of a range of the array.
322: *
323: * @param idx1 the index index of the beginning of the range, inclusive
324: * @param idx2 the index of the end of the range, inclusive
325: * @return a copy of the specified range of this array
326: * @throws PackagedScriptObjectException(NoSuchMemberException)
327: * @see #length
328: * @see #elementAt
329: */
330: public Value elementsAt(Value idx1, Value idx2)
331: throws PackagedScriptObjectException {
332: return elementsAt((int) (idx1.castToExactNumber()), (int) (idx2
333: .castToExactNumber()));
334: }
335:
336: public Value elementsAt(int idx1, int idx2) {
337: if ((idx1 < 0) || (idx2 < 0) || (idx2 < idx1))
338: throw PackagedScriptObjectException
339: .makeExceptionWrapper(new OIllegalArgumentException(
340: "invalid array index: " + idx1 + ", "
341: + idx2));
342:
343: OArray arr = new OArray(idx2 - idx1 + 1);
344:
345: for (int i = idx1; i <= idx2; i++)
346: arr.elementAt(i - idx1).opAssign(elementAt(i));
347:
348: return arr;
349: }
350:
351: /*=======================================================================*/
352: /**
353: * Get an iterator of all the elements of this array. This makes arrays
354: * useful in the "for( var item : set )" syntx.
355: *
356: * @return an iterator of elements of the array
357: */
358: public java.util.Iterator iterator() {
359: return new java.util.Iterator() {
360:
361: private int idx = 0;
362:
363: public boolean hasNext() {
364: return idx < length();
365: }
366:
367: public void remove() {
368: throw new UnsupportedOperationException("remove");
369: }
370:
371: public Object next() {
372: Value val = elementAt(idx);
373: idx++;
374: return val;
375: }
376:
377: };
378: }
379:
380: /*=======================================================================*/
381: /**
382: * Join this array object with one or more additional arrays. This
383: * performs a shallow copy, so the original arrays are unmodified, but
384: * for mutable objects there may be side effects.
385: */
386: public final Value concat = new VarArgFunction("concat") {
387:
388: public Value callAsFunction(StackFrame sf, MemberTable args) {
389: if (args == null)
390: return OArray.this ;
391: Value tmp;
392: int alen = args.length();
393: int len = OArray.this .length();
394: for (int i = 0; i < alen; i++)
395: len += args.referenceAt(i).length();
396: OArray result = new OArray(len);
397: int i0 = 0;
398: for (int i1 = 0; i1 < OArray.this .length(); i1++)
399: result.elementAt(i0++).opAssign(
400: OArray.this .elementAt(i1));
401: for (int i = 0; i < alen; i++)
402: if ((tmp = args.referenceAt(i)) instanceof OArray)
403: for (int i1 = 0; i1 < tmp.length(); i1++)
404: result.elementAt(i0++).opAssign(
405: ((OArray) tmp).elementAt(i1));
406: else
407: for (int i1 = 0; i1 < tmp.length(); i1++)
408: result.elementAt(i0++).opAssign(
409: tmp.elementAt(JavaBridge
410: .convertToScriptObject(i1)));
411: return result;
412: }
413:
414: };
415:
416: /*=======================================================================*/
417: /**
418: * Join all elements in the array into a single string, separated by
419: * commas
420: *
421: * @return the resulting string
422: */
423: public Value join() {
424: return join(JavaBridge.convertToScriptObject(","));
425: }
426:
427: /*=======================================================================*/
428: /**
429: * Join all elements in the array into a single string, separated by the
430: * specified separator.
431: *
432: * @param separator the separator string
433: * @return the resulting string
434: */
435: public Value join(Value separator) {
436: String str = "";
437: String sep = separator.castToString();
438:
439: if (length() > 0) {
440: str = elementAt(0).castToString();
441:
442: for (int i = 1; i < length(); i++)
443: str += sep + elementAt(i).castToString();
444: }
445:
446: return JavaBridge.convertToScriptObject(str);
447: }
448:
449: /*=======================================================================*/
450: /**
451: * Slice out a section of the array. This works like <code>arr[begin..
452: * arr.length()-1]</code>. The index can be negative, in which case it
453: * will count from the end of the array.
454: *
455: * @param begin the begin index, inclusive
456: * @return the resulting array
457: */
458: public Value slice(Value begin) {
459: int a = getAbsoluteIndex(begin);
460: int b = length();
461: return elementsAt(a, b - 1);
462: }
463:
464: /*=======================================================================*/
465: /**
466: * Slice out a section of the array. This works like <code>arr[begin..
467: * end-1]</code>. Either index can be negative, in which case it
468: * will count from the end of the array.
469: *
470: * @param begin the begin index, inclusive
471: * @param end the end index, exclusive
472: * @return the resulting array
473: */
474: public Value slice(Value begin, Value end) {
475: int a = getAbsoluteIndex(begin);
476: int b = getAbsoluteIndex(end);
477: return elementsAt(a, b - 1);
478: }
479:
480: /*=======================================================================*/
481: /**
482: * Add and remove elements from an array
483: *
484: * @param idx the index to begin removing from
485: * @param num the number of elements to remove (optional, defaults to
486: * everything after <code>idx</code>)
487: * @param args... optional additional arguments to replace the removed
488: * elements
489: * @return the removed elements
490: */
491: public final Value splice = new VarArgFunction("splice") {
492:
493: public Value callAsFunction(StackFrame sf, MemberTable args) {
494: int alen = (args == null) ? 0 : args.length();
495:
496: if (arr == null)
497: throw PackagedScriptObjectException
498: .makeExceptionWrapper(new OUnsupportedOperationException(
499: "unsupported operation for java array!")); // XXX
500:
501: if (alen < 2)
502: throw PackagedScriptObjectException
503: .makeExceptionWrapper(new OIllegalArgumentException(
504: "wrong number of args!"));
505:
506: synchronized (OArray.this ) {
507: int len = OArray.this .length();
508: int begin = getAbsoluteIndex(args.referenceAt(0));
509: int end = (int) (args.referenceAt(1)
510: .castToExactNumber())
511: + begin;
512:
513: Value result = OArray.this .elementsAt(begin, end - 1);
514:
515: int delta = begin - end + Math.max(0, alen - 2);
516:
517: if (delta > 0)
518: for (int i = len - 1; i >= end; i--)
519: OArray.this .elementAt(i + delta).opAssign(
520: OArray.this .elementAt(i));
521: else if (delta < 0)
522: for (int i = end; i < len; i++)
523: OArray.this .elementAt(i + delta).opAssign(
524: OArray.this .elementAt(i));
525:
526: for (int i = 2; i < alen; i++)
527: OArray.this .elementAt(i - 2 + begin).opAssign(
528: args.referenceAt(i));
529:
530: for (int i = len + delta; i < size; i++)
531: arr[i] = null;
532: size = len + delta;
533:
534: return result;
535: }
536: }
537: };
538:
539: /*=======================================================================*/
540: /**
541: * Remove and return the last element of the array.
542: */
543: public synchronized Value pop() {
544: if (arr == null)
545: throw PackagedScriptObjectException
546: .makeExceptionWrapper(new OUnsupportedOperationException(
547: "unsupported operation for java array!")); // XXX
548: int idx = size - 1;
549: Value result = elementAt(idx); // elementAt throws exception if idx is invalid
550: size--;
551: arr[idx] = null;
552: return result;
553: }
554:
555: /*=======================================================================*/
556: /**
557: * Add one or more elements to the end of the array, returning the new
558: * length.
559: */
560: public final Value push = new VarArgFunction("push") {
561:
562: public Value callAsFunction(StackFrame sf, MemberTable args) {
563: int alen = (args == null) ? 0 : args.length();
564: int idx = OArray.this .length();
565: for (int i = 0; i < alen; i++)
566: OArray.this .elementAt(idx++).opAssign(
567: args.referenceAt(i));
568: return JavaBridge.convertToScriptObject(idx);
569: }
570:
571: };
572:
573: /*=======================================================================*/
574: /**
575: * Remove and return the first element of the array.
576: */
577: public synchronized Value shift() {
578: if (arr == null)
579: throw PackagedScriptObjectException
580: .makeExceptionWrapper(new OUnsupportedOperationException(
581: "unsupported operation for java array!")); // XXX
582:
583: Value result = elementAt(0); // elementAt throws exception if idx is invalid
584: System.arraycopy(arr, 1, arr, 0, size - 1);
585: arr[size - 1] = null;
586: size--;
587: return result;
588: }
589:
590: /*=======================================================================*/
591: /**
592: * Add one or more elements to the beginning of the array, returning the
593: * new length.
594: */
595: public final Value unshift = new VarArgFunction("unshift") {
596:
597: public Value callAsFunction(StackFrame sf, MemberTable args) {
598: synchronized (OArray.this ) {
599: int alen = (args == null) ? 0 : args.length();
600: if (alen > 0)
601: for (int i = OArray.this .length() - 1; i >= 0; i--)
602: OArray.this .elementAt(i + alen).opAssign(
603: OArray.this .elementAt(i));
604: for (int i = 0; i < alen; i++)
605: OArray.this .elementAt(i).opAssign(
606: args.referenceAt(i));
607: return JavaBridge.convertToScriptObject(OArray.this
608: .length());
609: }
610: }
611:
612: };
613:
614: /*=======================================================================*/
615: /**
616: * Reverse the order of elements in this array, returning this array. The
617: * array is reversed in order.
618: *
619: * @return this array object itself
620: */
621: public synchronized Value reverse() {
622: if (arr == null)
623: throw PackagedScriptObjectException
624: .makeExceptionWrapper(new OUnsupportedOperationException(
625: "unsupported operation for java array!")); // XXX
626:
627: for (int i0 = 0;; i0++) {
628: int i1 = arr.length - 1 - i0;
629: if (i1 <= i0)
630: break;
631: Reference tmp = arr[i0];
632: arr[i0] = arr[i1];
633: arr[i1] = tmp;
634: }
635: return this ;
636: }
637:
638: /*=======================================================================*/
639: /**
640: * Executes the provided function <code>fxn</code> once for each element
641: * present in the array until it finds one where callback returns
642: * <code>false</code>. If such an element is found, the test aborts and
643: * <code>false</code> is returned, otherwise (callback returned
644: * <code>true</code> for each of the elements) every will return
645: * <code>true</code>. This array is not mutated.
646: *
647: * @param fxn invoked with three arguments: the value of the element,
648: * the index of the element, and the array object containing the
649: * element; should return <code>true</code> or <code>false</code>
650: * @return <code>true</code> if every element passes the test, otherwise
651: * <code>false</code>
652: */
653: public Value every(Value fxn) {
654: int len = length();
655: Value[] args = new Value[] { null, null, this };
656: for (int i = 0; i < len; i++) {
657: args[0] = elementAt(i);
658: args[1] = OExactNumber.makeExactNumber(i);
659: if (!fxn.callAsFunction(args).castToBoolean())
660: return OBoolean.FALSE;
661: }
662: return OBoolean.TRUE;
663: }
664:
665: /*=======================================================================*/
666: /**
667: * Tests whether some element in the array passes the test implemented by
668: * the provided function. Executes the provided function once for each
669: * element present in the array until it finds one where callback returns
670: * <code>true</code>. If such an element is found, the test aborts and
671: * <code>true</code> is returned, otherwise (callback returned
672: * <code>false</code> for each of the elements) return <code>false</code>.
673: *
674: * @param fxn invoked with three arguments: the value of the element,
675: * the index of the element, and the array object containing the
676: * element; should return <code>true</code> or <code>false</code>
677: * @return <code>true</code> if some element passes the test, otherwise
678: * <code>false</code>
679: */
680: public Value some(Value fxn) {
681: int len = length();
682: Value[] args = new Value[] { null, null, this };
683: for (int i = 0; i < len; i++) {
684: args[0] = elementAt(i);
685: args[1] = OExactNumber.makeExactNumber(i);
686: if (fxn.callAsFunction(args).castToBoolean())
687: return OBoolean.TRUE;
688: }
689: return OBoolean.FALSE;
690: }
691:
692: /*=======================================================================*/
693: /**
694: * Create a new array with all elements that pass the test implemented
695: * by the provided function. The provided callback is invoked for each
696: * element in the array, and a new array is constructed containing (in
697: * the same order) the elements for which the callback returned
698: * <code>true</code>. Elements for which the callback returns
699: * <code>false</code> are skipped. This array is not mutated.
700: *
701: * @param fxn invoked with three arguments: the value of the element,
702: * the index of the element, and the array object containing the
703: * element; should return <code>true</code> or <code>false</code>
704: * @return the filtered array.
705: */
706: public Value filter(Value fxn) {
707: OArray arr = new OArray(0);
708: int len = length();
709: Value[] args = new Value[] { null, null, this };
710: for (int i = 0; i < len; i++) {
711: args[0] = elementAt(i);
712: args[1] = OExactNumber.makeExactNumber(i);
713: if (fxn.callAsFunction(args).castToBoolean())
714: arr.push1(elementAt(i));
715: }
716: return arr;
717: }
718:
719: /*=======================================================================*/
720: /**
721: * Creates a new array with the results of calling a provided function
722: * on every element in this array. This array is not mutated.
723: *
724: * @param fxn invoked with three arguments: the value of the element,
725: * the index of the element, and the array object containing the
726: * element
727: * @return the new array
728: */
729: public Value map(Value fxn) {
730: OArray arr = new OArray(length());
731: int len = length();
732: Value[] args = new Value[] { null, null, this };
733: for (int i = 0; i < len; i++) {
734: args[0] = elementAt(i);
735: args[1] = OExactNumber.makeExactNumber(i);
736: arr.push1(fxn.callAsFunction(args));
737: }
738: return arr;
739: }
740:
741: /*=======================================================================*/
742: /**
743: * Executes a provided function once per array element. This array is
744: * not mutated.
745: *
746: * @param fxn invoked with three arguments: the value of the element,
747: * the index of the element, and the array object containing the
748: * element
749: */
750: public void forEach(Value fxn) {
751: int len = length();
752: Value[] args = new Value[] { null, null, this };
753: for (int i = 0; i < len; i++) {
754: args[0] = elementAt(i);
755: args[1] = OExactNumber.makeExactNumber(i);
756: fxn.callAsFunction(args);
757: }
758: }
759:
760: /*=======================================================================*/
761: /**
762: * Sort the elements in the array, by converting each element to string,
763: * and sorting in ascending order. The array is sorted in place.
764: *
765: * @return this array object itself
766: */
767: public Value sort() {
768: return sort(oscript.OscriptInterpreter.DEFAULT_ARRAY_SORT_COMPARISION_FXN);
769: }
770:
771: /*=======================================================================*/
772: /**
773: * Sort the elements in the array, by using the specified comparision
774: * function. The comparision <code>function(a,b)</code> should return
775: * less than zero if <tt>a</tt> is less than <tt>b</tt>, zero if they
776: * are equal, and greater than zero if <tt>a</tt> is greater than
777: * <tt>b</tt>. The array is sorted in place.
778: *
779: * @param fxn the comparasion function
780: * @return this array object itself
781: */
782: public synchronized Value sort(Value fxn) {
783: if (arr == null)
784: throw PackagedScriptObjectException
785: .makeExceptionWrapper(new OUnsupportedOperationException(
786: "unsupported operation for java array!")); // XXX
787: _qsort(fxn, arr, 0, size - 1);
788: return this ;
789: }
790:
791: private static final void _qsort(Value fxn, Reference[] arr,
792: int lo, int hi) {
793: if (lo >= hi)
794: return;
795:
796: // short cut for sequential elements:
797: if (hi == (lo + 1)) {
798: if (_compare(fxn, arr[lo], arr[hi]) > 0)
799: _swap(arr, hi, lo);
800: return;
801: }
802:
803: int pivot = (lo + hi) / 2;
804:
805: _swap(arr, pivot, hi);
806:
807: int bot = lo;
808: int top = hi - 1;
809:
810: while (bot < top) {
811: while ((bot <= top)
812: && (_compare(fxn, arr[bot], arr[hi]) <= 0))
813: bot++;
814: while ((bot <= top)
815: && (_compare(fxn, arr[top], arr[hi]) >= 0))
816: top--;
817:
818: if (bot < top)
819: _swap(arr, top, bot);
820: }
821:
822: _swap(arr, bot, hi);
823:
824: _qsort(fxn, arr, lo, bot - 1);
825: _qsort(fxn, arr, bot + 1, hi);
826:
827: // XXX double check generated code to verify that arr[hi] (the pivot) gets hoisted
828: }
829:
830: private static final int _compare(Value fxn, Reference a,
831: Reference b) {
832: return (int) (fxn.callAsFunction(new Value[] { a.unhand(),
833: b.unhand() }).castToExactNumber());
834: }
835:
836: private static final void _swap(Reference[] arr, int a, int b) {
837: Reference tmp = arr[a];
838: arr[a] = arr[b];
839: arr[b] = tmp;
840: }
841:
842: /*=======================================================================*/
843: /**
844: * Helper function to convert a relative index to an absolute index
845: */
846: private int getAbsoluteIndex(Value idx) {
847: int i = (int) (idx.castToExactNumber());
848: if (i < 0)
849: i = length() + i;
850: return i;
851: }
852:
853: /*=======================================================================*/
854: // hmm, move this?
855: private static class VarArgFunction extends Value {
856: private final int id;
857:
858: VarArgFunction(String name) {
859: super ();
860: this .id = Symbol.getSymbol(name).getId();
861: }
862:
863: protected Value getTypeImpl() {
864: return Function.TYPE;
865: }
866:
867: public Value getName() {
868: return Symbol.getSymbol(id);
869: }
870:
871: public String castToString() {
872: return "[function: " + getName() + "]";
873: }
874: }
875:
876: /*=======================================================================*/
877:
878: public MemberTable safeCopy() {
879: // no-op... OArray is always safe
880: return this ;
881: }
882:
883: public void push1(Value val) {
884: int idx = length();
885: ensureCapacity(idx);
886: referenceAt(idx).reset(val);
887: }
888:
889: public void push2(Value val1, Value val2) {
890: push1(val1);
891: push1(val2);
892: }
893:
894: public void push3(Value val1, Value val2, Value val3) {
895: push1(val1);
896: push1(val2);
897: push1(val3);
898: }
899:
900: public void push4(Value val1, Value val2, Value val3, Value val4) {
901: push1(val1);
902: push1(val2);
903: push1(val3);
904: push1(val4);
905: }
906:
907: public void reset() {
908: for (int i = length() - 1; i >= 0; i--)
909: referenceAt(i).reset();
910: }
911:
912: public void free() {
913: // no-op
914: }
915:
916: /*=======================================================================*/
917: public static void fillByteArray(byte[] arr) {
918: for (int i = 0; i < arr.length; i++)
919: arr[i] = (byte) i;
920: }
921:
922: public static void fillCharacterArray(char[] arr) {
923: for (int i = 0; i < arr.length; i++)
924: arr[i] = (char) i;
925: }
926:
927: public static void fillShortArray(short[] arr) {
928: for (int i = 0; i < arr.length; i++)
929: arr[i] = (short) i;
930: }
931:
932: public static void fillIntegerArray(int[] arr) {
933: for (int i = 0; i < arr.length; i++)
934: arr[i] = i;
935: }
936:
937: public static void fillLongArray(long[] arr) {
938: for (int i = 0; i < arr.length; i++)
939: arr[i] = i;
940: }
941:
942: public static void fillFloatArray(float[] arr) {
943: for (int i = 0; i < arr.length; i++)
944: arr[i] = i;
945: }
946:
947: public static void fillDoubleArray(double[] arr) {
948: for (int i = 0; i < arr.length; i++)
949: arr[i] = i;
950: }
951:
952: }
953:
954: /*
955: * Local Variables:
956: * tab-width: 2
957: * indent-tabs-mode: nil
958: * mode: java
959: * c-indentation-style: java
960: * c-basic-offset: 2
961: * eval: (c-set-offset 'substatement-open '0)
962: * eval: (c-set-offset 'case-label '+)
963: * eval: (c-set-offset 'inclass '+)
964: * eval: (c-set-offset 'inline-open '0)
965: * End:
966: */
|