From 488d42af6f3f61ea75656c994ad9722a6e8e6af9 Mon Sep 17 00:00:00 2001 From: Bryce McKinlay Date: Mon, 11 Dec 2000 03:47:48 +0000 Subject: Makefile.am: Add HashSet.java and java/lang/ref classes. * Makefile.am: Add HashSet.java and java/lang/ref classes. Remove BasicMapEntry.java and Bucket.java. * Makefile.in: Rebuilt. * java/util/HashMap.java: Rewritten. * java/util/HashSet.java: Imported from classpath. * java/util/WeakHashMap.java: Imported from classpath. * java/util/Hashtable.java: Rewritten based on new HashMap code. * java/util/Bucket.java: Deleted. * java/util/BasicMapEntry.java: Deleted. * java/util/Collections.java (search): Use a for-loop, not iterator hasNext(). (copy): Use a for-loop. Throw an IndexOutOfBoundsException if run out of elements in source. (max): Use a for-loop. (min): Ditto. (reverse): Keep track of positions instead of using Iterator's nextIndex() and previousIndex(). (shuffle(List)): Initialize defaultRandom if required using double-check thread safety idiom. Call two-argument shuffle method using defaultRandom. (defaultRandom): New field. (shuffle(List, Random)): Use a for-loop. Keep track of pos instead of using previousIndex() and nextIndex(). (singletonMap(iterator)): Use a HashMap.Entry, not BasicMapEntry. * java/util/AbstractCollection.java (toString): Use a StringBuffer. * java/util/AbstractMap.java (toString): Use StringBuffer. * java/lang/ref/PhantomReference.java: Imported from classpath. * java/lang/ref/SoftReference.java: Ditto. * java/lang/ref/Reference.java: Ditto. * java/lang/ref/WeakReference.java: Ditto. * java/lang/ref/ReferenceQueue.java: Ditto. From-SVN: r38183 --- libjava/java/util/Collections.java | 116 +++++++++++++++++++++++-------------- 1 file changed, 71 insertions(+), 45 deletions(-) (limited to 'libjava/java/util/Collections.java') diff --git a/libjava/java/util/Collections.java b/libjava/java/util/Collections.java index af90b45..9035e670 100644 --- a/libjava/java/util/Collections.java +++ b/libjava/java/util/Collections.java @@ -149,10 +149,10 @@ public class Collections // is sequential-access. if (l instanceof AbstractSequentialList) { - ListIterator i = l.listIterator(); - while (i.hasNext()) + ListIterator itr = l.listIterator(); + for (int i = l.size() - 1; i >= 0; --i) { - final int d = compare(key, i.next(), c); + final int d = compare(key, itr.next(), c); if (d == 0) { return pos; @@ -264,10 +264,18 @@ public class Collections { Iterator i1 = source.iterator(); ListIterator i2 = dest.listIterator(); - while (i1.hasNext()) + + try + { + for (int i = source.size() - 1; i >= 0; --i) + { + i2.next(); + i2.set(i1.next()); + } + } + catch (NoSuchElementException x) { - i2.next(); - i2.set(i1.next()); + throw new IndexOutOfBoundsException("Source doesn't fit in dest."); } } @@ -305,11 +313,11 @@ public class Collections */ public static void fill(List l, Object val) { - ListIterator i = l.listIterator(); - while (i.hasNext()) + ListIterator itr = l.listIterator(); + for (int i = l.size() - 1; i >= 0; --i) { - i.next(); - i.set(val); + itr.next(); + itr.set(val); } } @@ -326,11 +334,12 @@ public class Collections */ public static Object max(Collection c) { - Iterator i = c.iterator(); - Comparable max = (Comparable) i.next(); // throws NoSuchElementException - while (i.hasNext()) + Iterator itr = c.iterator(); + Comparable max = (Comparable) itr.next(); // throws NoSuchElementException + int csize = c.size(); + for (int i = 1; i < csize; i++) { - Object o = i.next(); + Object o = itr.next(); if (max.compareTo(o) < 0) { max = (Comparable) o; @@ -352,15 +361,14 @@ public class Collections */ public static Object max(Collection c, Comparator order) { - Iterator i = c.iterator(); - Object max = i.next(); // throws NoSuchElementException - while (i.hasNext()) + Iterator itr = c.iterator(); + Object max = itr.next(); // throws NoSuchElementException + int csize = c.size(); + for (int i = 1; i < csize; i++) { - Object o = i.next(); + Object o = itr.next(); if (order.compare(max, o) < 0) - { - max = o; - } + max = o; } return max; } @@ -378,15 +386,14 @@ public class Collections */ public static Object min(Collection c) { - Iterator i = c.iterator(); - Comparable min = (Comparable) i.next(); // throws NoSuchElementException - while (i.hasNext()) + Iterator itr = c.iterator(); + Comparable min = (Comparable) itr.next(); // throws NoSuchElementException + int csize = c.size(); + for (int i = 1; i < csize; i++) { - Object o = i.next(); + Object o = itr.next(); if (min.compareTo(o) > 0) - { - min = (Comparable) o; - } + min = (Comparable) o; } return min; } @@ -404,15 +411,14 @@ public class Collections */ public static Object min(Collection c, Comparator order) { - Iterator i = c.iterator(); - Object min = i.next(); // throws NoSuchElementExcception - while (i.hasNext()) + Iterator itr = c.iterator(); + Object min = itr.next(); // throws NoSuchElementExcception + int csize = c.size(); + for (int i = 1; i < csize; i++) { - Object o = i.next(); + Object o = itr.next(); if (order.compare(min, o) > 0) - { - min = o; - } + min = o; } return min; } @@ -468,12 +474,16 @@ public class Collections public static void reverse(List l) { ListIterator i1 = l.listIterator(); - ListIterator i2 = l.listIterator(l.size()); - while (i1.nextIndex() < i2.previousIndex()) + int pos1 = 0; + int pos2 = l.size(); + ListIterator i2 = l.listIterator(pos2); + while (pos1 < pos2) { Object o = i1.next(); i1.set(i2.previous()); i2.set(o); + ++pos1; + --pos2; } } @@ -513,9 +523,24 @@ public class Collections */ public static void shuffle(List l) { - shuffle(l, new Random()); + if (defaultRandom == null) + { + synchronized (Collections.class) + { + if (defaultRandom == null) + defaultRandom = new Random(); + } + } + shuffle(l, defaultRandom); } + /** Cache a single Random object for use by shuffle(List). This improves + * performance as well as ensuring that sequential calls to shuffle() will + * not result in the same shuffle order occuring: the resolution of + * System.currentTimeMillis() is not sufficient to guarantee a unique seed. + */ + private static Random defaultRandom = null; + /** * Shuffle a list according to a given source of randomness. The algorithm * used iterates backwards over the list, swapping each element with an @@ -541,20 +566,21 @@ public class Collections public static void shuffle(List l, Random r) { Object[] a = l.toArray(); // Dump l into an array - ListIterator i = l.listIterator(l.size()); + int lsize = l.size(); + ListIterator i = l.listIterator(lsize); // Iterate backwards over l - while (i.hasPrevious()) + for (int pos = lsize - 1; pos >= 0; --pos) { - // Obtain a random position to swap with. nextIndex is used so that the + // Obtain a random position to swap with. pos + 1 is used so that the // range of the random number includes the current position. - int swap = r.nextInt(i.nextIndex()); + int swap = r.nextInt(pos + 1); // Swap the swapth element of the array with the next element of the // list. Object o = a[swap]; - a[swap] = a[i.previousIndex()]; - a[i.previousIndex()] = o; + a[swap] = a[pos]; + a[pos] = o; // Set the element in the original list accordingly. i.previous(); @@ -658,7 +684,7 @@ public class Collections { public Set entrySet() { - return singleton(new BasicMapEntry(key, value)); + return singleton(new HashMap.Entry(key, value)); } }; } -- cgit v1.1