You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@harmony.apache.org by ge...@apache.org on 2005/12/01 07:04:00 UTC
svn commit: r350181 [122/198] - in
/incubator/harmony/enhanced/trunk/sandbox/contribs/ibm_core: ./ depends/
depends/files/ depends/jars/ depends/libs/ depends/libs/linux.IA32/
depends/libs/win.IA32/ depends/oss/ depends/oss/linux.IA32/
depends/oss/win....
Added: incubator/harmony/enhanced/trunk/sandbox/contribs/ibm_core/java-src/luni/src/java/util/TimerTask.java
URL: http://svn.apache.org/viewcvs/incubator/harmony/enhanced/trunk/sandbox/contribs/ibm_core/java-src/luni/src/java/util/TimerTask.java?rev=350181&view=auto
==============================================================================
--- incubator/harmony/enhanced/trunk/sandbox/contribs/ibm_core/java-src/luni/src/java/util/TimerTask.java (added)
+++ incubator/harmony/enhanced/trunk/sandbox/contribs/ibm_core/java-src/luni/src/java/util/TimerTask.java Wed Nov 30 21:29:27 2005
@@ -0,0 +1,110 @@
+/* Copyright 2000, 2004 The Apache Software Foundation or its licensors, as applicable
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package java.util;
+
+
+/**
+ * The TimerTask class is represents a task to run at specified time. The task
+ * may be run onces or repeatedly.
+ *
+ * @see Timer
+ * @see java.lang.Object#wait(long)
+ */
+public abstract class TimerTask implements Runnable {
+
+ /* The timer object which launches this task */
+ private Timer timer = null;
+
+ /* If timer was cancelled */
+ private boolean cancelled = false;
+
+ /* Slots used by Timer */
+ long when;
+
+ long period;
+
+ boolean fixedRate;
+
+ /*
+ * The time when task will be executed, or the time when task was launched
+ * if this is task in progress.
+ */
+ private long scheduledTime = 0;
+
+ /*
+ * Method called from the Timer object when scheduling an event
+ * @param time
+ */
+ void setScheduledTime(long time) {
+ scheduledTime = time;
+ }
+
+ /*
+ * Is TimerTask scheduled into any timer?
+ *
+ * @return <code>true</code> if the timer task is scheduled,
+ * <code>false</code> otherwise.
+ */
+ boolean isScheduled() {
+ return when > 0 || scheduledTime > 0;
+ }
+
+ /*
+ * Is TimerTask cancelled?
+ *
+ * @return <code>true</code> if the timer task is cancelled,
+ * <code>false</code> otherwise.
+ */
+ boolean isCancelled() {
+ return cancelled;
+ }
+
+ protected TimerTask() {
+ super();
+ }
+
+ /**
+ * Cancels the Task and removes it from the Timer's queue. Generally, it
+ * returns false if the call did not prevent a TimerTask from running at
+ * least once. Subsequent calls have no effect.
+ *
+ * @return <code>true</code> if the call prevented a scheduled execution
+ * from taking place, <code>false</code> otherwise.
+ */
+ public boolean cancel() {
+ boolean willRun = !cancelled && when > 0;
+ cancelled = true;
+ return willRun;
+ }
+
+ /**
+ * Returns the scheduled execution time. If the task execution is in
+ * progress returns the execution time of ongoing task. Tasks which have not
+ * yet run return an undefined value.
+ *
+ * @return the most recent execution time.
+ */
+ public long scheduledExecutionTime() {
+ return scheduledTime;
+ }
+
+ /**
+ * The task to run should be specified in the implemenation of the run()
+ * method.
+ */
+ public abstract void run();
+
+}
Added: incubator/harmony/enhanced/trunk/sandbox/contribs/ibm_core/java-src/luni/src/java/util/TooManyListenersException.java
URL: http://svn.apache.org/viewcvs/incubator/harmony/enhanced/trunk/sandbox/contribs/ibm_core/java-src/luni/src/java/util/TooManyListenersException.java?rev=350181&view=auto
==============================================================================
--- incubator/harmony/enhanced/trunk/sandbox/contribs/ibm_core/java-src/luni/src/java/util/TooManyListenersException.java (added)
+++ incubator/harmony/enhanced/trunk/sandbox/contribs/ibm_core/java-src/luni/src/java/util/TooManyListenersException.java Wed Nov 30 21:29:27 2005
@@ -0,0 +1,48 @@
+/* Copyright 1998, 2002 The Apache Software Foundation or its licensors, as applicable
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package java.util;
+
+
+/**
+ * This exception is thrown when an attempt is made to add more than one
+ * listener to an event source which only supports a single listener. It is also
+ * thrown when the same listener is added more than once.
+ *
+ * @see java.lang.Exception
+ */
+public class TooManyListenersException extends Exception {
+
+ static final long serialVersionUID = 5074640544770687831L;
+
+ /**
+ * Constructs a new instance of this class with its walkback filled in.
+ */
+ public TooManyListenersException() {
+ super();
+ }
+
+ /**
+ * Constructs a new instance of this class with its walkback and message
+ * filled in.
+ *
+ * @param detailMessage
+ * String The detail message for the exception.
+ */
+ public TooManyListenersException(String detailMessage) {
+ super(detailMessage);
+ }
+
+}
Added: incubator/harmony/enhanced/trunk/sandbox/contribs/ibm_core/java-src/luni/src/java/util/TreeMap.java
URL: http://svn.apache.org/viewcvs/incubator/harmony/enhanced/trunk/sandbox/contribs/ibm_core/java-src/luni/src/java/util/TreeMap.java?rev=350181&view=auto
==============================================================================
--- incubator/harmony/enhanced/trunk/sandbox/contribs/ibm_core/java-src/luni/src/java/util/TreeMap.java (added)
+++ incubator/harmony/enhanced/trunk/sandbox/contribs/ibm_core/java-src/luni/src/java/util/TreeMap.java Wed Nov 30 21:29:27 2005
@@ -0,0 +1,1172 @@
+/* Copyright 1998, 2005 The Apache Software Foundation or its licensors, as applicable
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package java.util;
+
+
+import java.io.IOException;
+import java.io.ObjectInputStream;
+import java.io.ObjectOutputStream;
+import java.io.Serializable;
+
+/**
+ * TreeMap is an implementation of SortedMap. All optional operations are
+ * supported, adding and removing. The values can be any objects. The keys can
+ * be any objects which are comparable to each other either using their natural
+ * order or a specified Comparator.
+ *
+ */
+
+public class TreeMap extends AbstractMap implements SortedMap, Cloneable,
+ Serializable {
+ static final long serialVersionUID = 919286545866124006L;
+
+ transient int size = 0;
+
+ transient TreeMapEntry root;
+
+ private Comparator comparator;
+
+ transient int modCount = 0;
+
+ private static final class TreeMapIterator implements Iterator {
+ private TreeMap backingMap;
+
+ private int expectedModCount;
+
+ private MapEntry.Type type;
+
+ private boolean hasEnd = false;
+
+ private TreeMapEntry node, lastNode;
+
+ private Object endKey;
+
+ TreeMapIterator(TreeMap map, MapEntry.Type value) {
+ backingMap = map;
+ type = value;
+ expectedModCount = map.modCount;
+ if (map.root != null)
+ node = TreeMap.minimum(map.root);
+ }
+
+ TreeMapIterator(TreeMap map, MapEntry.Type value,
+ TreeMapEntry startNode, boolean checkEnd, Object end) {
+ backingMap = map;
+ type = value;
+ expectedModCount = map.modCount;
+ node = startNode;
+ hasEnd = checkEnd;
+ endKey = end;
+ }
+
+ public boolean hasNext() {
+ return node != null;
+ }
+
+ public Object next() {
+ if (expectedModCount == backingMap.modCount) {
+ if (node != null) {
+ lastNode = node;
+ node = TreeMap.successor(node);
+ if (hasEnd && node != null) {
+ Comparator c = backingMap.comparator();
+ if (c == null) {
+ if (((Comparable) endKey).compareTo(node.key) <= 0)
+ node = null;
+ } else {
+ if (c.compare(endKey, node.key) <= 0)
+ node = null;
+ }
+ }
+ return type.get(lastNode);
+ } else
+ throw new NoSuchElementException();
+ } else
+ throw new ConcurrentModificationException();
+ }
+
+ public void remove() {
+ if (expectedModCount == backingMap.modCount) {
+ if (lastNode != null) {
+ backingMap.rbDelete(lastNode);
+ lastNode = null;
+ expectedModCount++;
+ } else
+ throw new IllegalStateException();
+ } else
+ throw new ConcurrentModificationException();
+ }
+ }
+
+ static final class SubMap extends AbstractMap implements SortedMap {
+ private TreeMap backingMap;
+
+ private boolean hasStart, hasEnd;
+
+ private Object startKey, endKey;
+
+ static class SubMapSet extends AbstractSet implements Set {
+ TreeMap backingMap;
+
+ boolean hasStart, hasEnd;
+
+ Object startKey, endKey;
+
+ MapEntry.Type type;
+
+ SubMapSet() {
+ /*empty*/
+ }
+
+ SubMapSet(boolean starting, Object start, TreeMap map,
+ boolean ending, Object end, MapEntry.Type theType) {
+ backingMap = map;
+ hasStart = starting;
+ startKey = start;
+ hasEnd = ending;
+ endKey = end;
+ type = theType;
+ }
+
+ void checkRange(Object key) {
+ if (backingMap.comparator() == null) {
+ Comparable object = (Comparable) key;
+ if (hasStart && object.compareTo(startKey) < 0)
+ throw new IllegalArgumentException();
+ if (hasEnd && object.compareTo(endKey) >= 0)
+ throw new IllegalArgumentException();
+ } else {
+ if (hasStart
+ && backingMap.comparator().compare(key, startKey) < 0)
+ throw new IllegalArgumentException();
+ if (hasEnd
+ && backingMap.comparator().compare(key, endKey) >= 0)
+ throw new IllegalArgumentException();
+ }
+ }
+
+ boolean checkRange(Object key, boolean start, boolean end) {
+ if (backingMap.comparator() == null) {
+ Comparable object = (Comparable) key;
+ if (start && object.compareTo(startKey) < 0)
+ return false;
+ if (end && object.compareTo(endKey) >= 0)
+ return false;
+ } else {
+ if (start
+ && backingMap.comparator().compare(key, startKey) < 0)
+ return false;
+ if (end
+ && backingMap.comparator().compare(key, endKey) >= 0)
+ return false;
+ }
+ return true;
+ }
+
+ public boolean isEmpty() {
+ if (hasStart) {
+ TreeMapEntry node = backingMap.findAfter(startKey);
+ return node == null || !checkRange(node.key, false, hasEnd);
+ }
+ return backingMap.findBefore(endKey) == null;
+ }
+
+ public Iterator iterator() {
+ TreeMapEntry startNode;
+ if (hasStart) {
+ startNode = backingMap.findAfter(startKey);
+ if (startNode != null
+ && !checkRange(startNode.key, false, hasEnd))
+ startNode = null;
+ } else {
+ startNode = backingMap.findBefore(endKey);
+ if (startNode != null)
+ startNode = minimum(backingMap.root);
+ }
+ return new TreeMapIterator(backingMap, type, startNode, hasEnd,
+ endKey);
+ }
+
+ public int size() {
+ int size = 0;
+ Iterator it = iterator();
+ while (it.hasNext()) {
+ size++;
+ it.next();
+ }
+ return size;
+ }
+ }
+
+ SubMap(Object start, TreeMap map) {
+ backingMap = map;
+ hasStart = true;
+ startKey = start;
+ }
+
+ SubMap(Object start, TreeMap map, Object end) {
+ backingMap = map;
+ hasStart = hasEnd = true;
+ startKey = start;
+ endKey = end;
+ }
+
+ SubMap(TreeMap map, Object end) {
+ backingMap = map;
+ hasEnd = true;
+ endKey = end;
+ }
+
+ private void checkRange(Object key) {
+ if (backingMap.comparator() == null) {
+ Comparable object = (Comparable) key;
+ if (hasStart && object.compareTo(startKey) < 0)
+ throw new IllegalArgumentException();
+ if (hasEnd && object.compareTo(endKey) >= 0)
+ throw new IllegalArgumentException();
+ } else {
+ if (hasStart
+ && backingMap.comparator().compare(key, startKey) < 0)
+ throw new IllegalArgumentException();
+ if (hasEnd && backingMap.comparator().compare(key, endKey) >= 0)
+ throw new IllegalArgumentException();
+ }
+ }
+
+ private boolean checkRange(Object key, boolean start, boolean end) {
+ if (backingMap.comparator() == null) {
+ Comparable object = (Comparable) key;
+ if (start && object.compareTo(startKey) < 0)
+ return false;
+ if (end && object.compareTo(endKey) >= 0)
+ return false;
+ } else {
+ if (start && backingMap.comparator().compare(key, startKey) < 0)
+ return false;
+ if (end && backingMap.comparator().compare(key, endKey) >= 0)
+ return false;
+ }
+ return true;
+ }
+
+ public Comparator comparator() {
+ return backingMap.comparator();
+ }
+
+ public boolean containsKey(Object key) {
+ if (checkRange(key, hasStart, hasEnd))
+ return backingMap.containsKey(key);
+ return false;
+ }
+
+ public Set entrySet() {
+ return new SubMapSet(hasStart, startKey, backingMap, hasEnd,
+ endKey, new MapEntry.Type() {
+ public Object get(MapEntry entry) {
+ return entry;
+ }
+ }) {
+ public boolean contains(Object object) {
+ if (object instanceof Map.Entry) {
+ Map.Entry entry = (Map.Entry) object;
+ Object v1 = get(entry.getKey()), v2 = entry.getValue();
+ return v1 == null ? v2 == null : v1.equals(v2);
+ }
+ return false;
+ }
+ };
+ }
+
+ public Object firstKey() {
+ if (!hasStart)
+ return backingMap.firstKey();
+ TreeMapEntry node = backingMap.findAfter(startKey);
+ if (node != null && checkRange(node.key, false, hasEnd))
+ return node.key;
+ throw new NoSuchElementException();
+ }
+
+ public Object get(Object key) {
+ if (checkRange(key, hasStart, hasEnd))
+ return backingMap.get(key);
+ return null;
+ }
+
+ public SortedMap headMap(Object endKey) {
+ checkRange(endKey);
+ if (hasStart)
+ return new SubMap(startKey, backingMap, endKey);
+ return new SubMap(backingMap, endKey);
+ }
+
+ public boolean isEmpty() {
+ if (hasStart) {
+ TreeMapEntry node = backingMap.findAfter(startKey);
+ return node == null || !checkRange(node.key, false, hasEnd);
+ }
+ return backingMap.findBefore(endKey) == null;
+ }
+
+ public Set keySet() {
+ if (keySet == null) {
+ keySet = new SubMapSet(hasStart, startKey, backingMap, hasEnd,
+ endKey, new MapEntry.Type() {
+ public Object get(MapEntry entry) {
+ return entry.key;
+ }
+ }) {
+ public boolean contains(Object object) {
+ return containsKey(object);
+ }
+ };
+ }
+ return keySet;
+ }
+
+ public Object lastKey() {
+ if (!hasEnd)
+ return backingMap.lastKey();
+ TreeMapEntry node = backingMap.findBefore(endKey);
+ if (node != null && checkRange(node.key, hasStart, false))
+ return node.key;
+ throw new NoSuchElementException();
+ }
+
+ public Object put(Object key, Object value) {
+ if (checkRange(key, hasStart, hasEnd))
+ return backingMap.put(key, value);
+ throw new IllegalArgumentException();
+ }
+
+ public Object remove(Object key) {
+ if (checkRange(key, hasStart, hasEnd))
+ return backingMap.remove(key);
+ return null;
+ }
+
+ public SortedMap subMap(Object startKey, Object endKey) {
+ checkRange(startKey);
+ checkRange(endKey);
+ Comparator c = backingMap.comparator();
+ if (c == null) {
+ if (((Comparable) startKey).compareTo(endKey) <= 0)
+ return new SubMap(startKey, backingMap, endKey);
+ } else {
+ if (c.compare(startKey, endKey) <= 0)
+ return new SubMap(startKey, backingMap, endKey);
+ }
+ throw new IllegalArgumentException();
+ }
+
+ public SortedMap tailMap(Object startKey) {
+ checkRange(startKey);
+ if (hasEnd)
+ return new SubMap(startKey, backingMap, endKey);
+ return new SubMap(startKey, backingMap);
+ }
+
+ public Collection values() {
+ return new SubMapSet(hasStart, startKey, backingMap, hasEnd,
+ endKey, new MapEntry.Type() {
+ public Object get(MapEntry entry) {
+ return entry.value;
+ }
+ });
+ }
+ }
+
+ /**
+ * Contructs a new empty instance of TreeMap.
+ *
+ */
+ public TreeMap() {
+ /*empty*/
+ }
+
+ /**
+ * Contructs a new empty instance of TreeMap which uses the specified
+ * Comparator.
+ *
+ * @param comparator
+ * the Comparator
+ */
+ public TreeMap(Comparator comparator) {
+ this.comparator = comparator;
+ }
+
+ /**
+ * Constructs a new instance of TreeMap containing the mappings from the
+ * specified Map and using the natural ordering.
+ *
+ * @param map
+ * the mappings to add
+ *
+ * @exception ClassCastException
+ * when a key in the Map does not implement the Comparable
+ * interface, or they keys in the Map cannot be compared
+ */
+ public TreeMap(Map map) {
+ this();
+ putAll(map);
+ }
+
+ /**
+ * Constructs a new instance of TreeMap containing the mappings from the
+ * specified SortedMap and using the same Comparator.
+ *
+ * @param map
+ * the mappings to add
+ */
+ public TreeMap(SortedMap map) {
+ this(map.comparator());
+ Iterator it = map.entrySet().iterator();
+ if (it.hasNext()) {
+ Map.Entry entry = (Map.Entry) it.next();
+ TreeMapEntry last = new TreeMapEntry(entry.getKey(), entry
+ .getValue());
+ root = last;
+ size = 1;
+ while (it.hasNext()) {
+ entry = (Map.Entry) it.next();
+ TreeMapEntry x = new TreeMapEntry(entry.getKey(), entry
+ .getValue());
+ x.parent = last;
+ last.right = x;
+ size++;
+ balance(x);
+ last = x;
+ }
+ }
+ }
+
+ void balance(TreeMapEntry x) {
+ TreeMapEntry y;
+ x.color = true;
+ while (x != root && x.parent.color) {
+ if (x.parent == x.parent.parent.left) {
+ y = x.parent.parent.right;
+ if (y != null && y.color) {
+ x.parent.color = false;
+ y.color = false;
+ x.parent.parent.color = true;
+ x = x.parent.parent;
+ } else {
+ if (x == x.parent.right) {
+ x = x.parent;
+ leftRotate(x);
+ }
+ x.parent.color = false;
+ x.parent.parent.color = true;
+ rightRotate(x.parent.parent);
+ }
+ } else {
+ y = x.parent.parent.left;
+ if (y != null && y.color) {
+ x.parent.color = false;
+ y.color = false;
+ x.parent.parent.color = true;
+ x = x.parent.parent;
+ } else {
+ if (x == x.parent.left) {
+ x = x.parent;
+ rightRotate(x);
+ }
+ x.parent.color = false;
+ x.parent.parent.color = true;
+ leftRotate(x.parent.parent);
+ }
+ }
+ }
+ root.color = false;
+ }
+
+ /**
+ * Removes all mappings from this TreeMap, leaving it empty.
+ *
+ * @see Map#isEmpty
+ * @see #size
+ */
+ public void clear() {
+ root = null;
+ size = 0;
+ modCount++;
+ }
+
+ /**
+ * Answers a new TreeMap with the same mappings, size and comparator as this
+ * TreeMap.
+ *
+ * @return a shallow copy of this TreeMap
+ *
+ * @see java.lang.Cloneable
+ */
+ public Object clone() {
+ try {
+ TreeMap clone = (TreeMap) super.clone();
+ if (root != null)
+ clone.root = root.clone(null);
+ return clone;
+ } catch (CloneNotSupportedException e) {
+ return null;
+ }
+ }
+
+ /**
+ * Answers the Comparator used to compare elements in this TreeMap.
+ *
+ * @return a Comparator or null if the natural ordering is used
+ */
+ public Comparator comparator() {
+ return comparator;
+ }
+
+ /**
+ * Searches this TreeMap for the specified key.
+ *
+ * @param key
+ * the object to search for
+ * @return true if <code>key</code> is a key of this TreeMap, false
+ * otherwise
+ *
+ * @exception ClassCastException
+ * when the key cannot be compared with the keys in this
+ * TreeMap
+ * @exception NullPointerException
+ * when the key is null and the comparator cannot handle null
+ */
+ public boolean containsKey(Object key) {
+ return find(key) != null;
+ }
+
+ /**
+ * Searches this TreeMap for the specified value.
+ *
+ * @param value
+ * the object to search for
+ * @return true if <code>value</code> is a value of this TreeMap, false
+ * otherwise
+ */
+ public boolean containsValue(Object value) {
+ if (root != null)
+ return containsValue(root, value);
+ return false;
+ }
+
+ private boolean containsValue(TreeMapEntry node, Object value) {
+ if (value == null ? node.value == null : value.equals(node.value))
+ return true;
+ if (node.left != null)
+ if (containsValue(node.left, value))
+ return true;
+ if (node.right != null)
+ if (containsValue(node.right, value))
+ return true;
+ return false;
+ }
+
+ /**
+ * Answers a Set of the mappings contained in this TreeMap. Each element in
+ * the set is a Map.Entry. The set is backed by this TreeMap so changes to
+ * one are relected by the other. The set does not support adding.
+ *
+ * @return a Set of the mappings
+ */
+ public Set entrySet() {
+ return new AbstractSet() {
+ public int size() {
+ return size;
+ }
+
+ public void clear() {
+ TreeMap.this.clear();
+ }
+
+ public boolean contains(Object object) {
+ if (object instanceof Map.Entry) {
+ Map.Entry entry = (Map.Entry) object;
+ Object v1 = get(entry.getKey()), v2 = entry.getValue();
+ return v1 == null ? v2 == null : v1.equals(v2);
+ }
+ return false;
+ }
+
+ public Iterator iterator() {
+ return new TreeMapIterator(TreeMap.this, new MapEntry.Type() {
+ public Object get(MapEntry entry) {
+ return entry;
+ }
+ });
+ }
+ };
+ }
+
+ private TreeMapEntry find(Object key) {
+ int result;
+ Comparable object = null;
+ if (comparator == null)
+ object = (Comparable) key;
+ TreeMapEntry x = root;
+ while (x != null) {
+ result = object != null ? object.compareTo(x.key) : comparator
+ .compare(key, x.key);
+ if (result == 0)
+ return x;
+ x = result < 0 ? x.left : x.right;
+ }
+ return null;
+ }
+
+ TreeMapEntry findAfter(Object key) {
+ int result;
+ Comparable object = null;
+ if (comparator == null)
+ object = (Comparable) key;
+ TreeMapEntry x = root, last = null;
+ while (x != null) {
+ result = object != null ? object.compareTo(x.key) : comparator
+ .compare(key, x.key);
+ if (result == 0)
+ return x;
+ if (result < 0) {
+ last = x;
+ x = x.left;
+ } else
+ x = x.right;
+ }
+ return last;
+ }
+
+ TreeMapEntry findBefore(Object key) {
+ int result;
+ Comparable object = null;
+ if (comparator == null)
+ object = (Comparable) key;
+ TreeMapEntry x = root, last = null;
+ while (x != null) {
+ result = object != null ? object.compareTo(x.key) : comparator
+ .compare(key, x.key);
+ if (result <= 0)
+ x = x.left;
+ else {
+ last = x;
+ x = x.right;
+ }
+ }
+ return last;
+ }
+
+ /**
+ * Answer the first sorted key in this TreeMap.
+ *
+ * @return the first sorted key
+ *
+ * @exception NoSuchElementException
+ * when this TreeMap is empty
+ */
+ public Object firstKey() {
+ if (root != null)
+ return minimum(root).key;
+ throw new NoSuchElementException();
+ }
+
+ private void fixup(TreeMapEntry x) {
+ TreeMapEntry w;
+ while (x != root && !x.color) {
+ if (x == x.parent.left) {
+ w = x.parent.right;
+ if (w == null) {
+ x = x.parent;
+ continue;
+ }
+ if (w.color) {
+ w.color = false;
+ x.parent.color = true;
+ leftRotate(x.parent);
+ w = x.parent.right;
+ if (w == null) {
+ x = x.parent;
+ continue;
+ }
+ }
+ if ((w.left == null || !w.left.color)
+ && (w.right == null || !w.right.color)) {
+ w.color = true;
+ x = x.parent;
+ } else {
+ if (w.right == null || !w.right.color) {
+ w.left.color = false;
+ w.color = true;
+ rightRotate(w);
+ w = x.parent.right;
+ }
+ w.color = x.parent.color;
+ x.parent.color = false;
+ w.right.color = false;
+ leftRotate(x.parent);
+ x = root;
+ }
+ } else {
+ w = x.parent.left;
+ if (w == null) {
+ x = x.parent;
+ continue;
+ }
+ if (w.color) {
+ w.color = false;
+ x.parent.color = true;
+ rightRotate(x.parent);
+ w = x.parent.left;
+ if (w == null) {
+ x = x.parent;
+ continue;
+ }
+ }
+ if ((w.left == null || !w.left.color)
+ && (w.right == null || !w.right.color)) {
+ w.color = true;
+ x = x.parent;
+ } else {
+ if (w.left == null || !w.left.color) {
+ w.right.color = false;
+ w.color = true;
+ leftRotate(w);
+ w = x.parent.left;
+ }
+ w.color = x.parent.color;
+ x.parent.color = false;
+ w.left.color = false;
+ rightRotate(x.parent);
+ x = root;
+ }
+ }
+ }
+ x.color = false;
+ }
+
+ /**
+ * Answers the value of the mapping with the specified key.
+ *
+ * @param key
+ * the key
+ * @return the value of the mapping with the specified key
+ *
+ * @exception ClassCastException
+ * when the key cannot be compared with the keys in this
+ * TreeMap
+ * @exception NullPointerException
+ * when the key is null and the comparator cannot handle null
+ */
+ public Object get(Object key) {
+ TreeMapEntry node = find(key);
+ if (node != null)
+ return node.value;
+ return null;
+ }
+
+ /**
+ * Answers a SortedMap of the specified portion of this TreeMap which
+ * contains keys less than the end key. The returned SortedMap is backed by
+ * this TreeMap so changes to one are reflected by the other.
+ *
+ * @param endKey
+ * the end key
+ * @return a submap where the keys are less than <code>endKey</code>
+ *
+ * @exception ClassCastException
+ * when the end key cannot be compared with the keys in this
+ * TreeMap
+ * @exception NullPointerException
+ * when the end key is null and the comparator cannot handle
+ * null
+ */
+ public SortedMap headMap(Object endKey) {
+ // Check for errors
+ if (comparator == null)
+ ((Comparable) endKey).compareTo(endKey);
+ else
+ comparator.compare(endKey, endKey);
+ return new SubMap(this, endKey);
+ }
+
+ /**
+ * Answers a Set of the keys contained in this TreeMap. The set is backed by
+ * this TreeMap so changes to one are relected by the other. The set does
+ * not support adding.
+ *
+ * @return a Set of the keys
+ */
+ public Set keySet() {
+ if (keySet == null) {
+ keySet = new AbstractSet() {
+ public boolean contains(Object object) {
+ return containsKey(object);
+ }
+
+ public int size() {
+ return size;
+ }
+
+ public void clear() {
+ TreeMap.this.clear();
+ }
+
+ public Iterator iterator() {
+ return new TreeMapIterator(TreeMap.this,
+ new MapEntry.Type() {
+ public Object get(MapEntry entry) {
+ return entry.key;
+ }
+ });
+ }
+ };
+ }
+ return keySet;
+ }
+
+ /**
+ * Answer the last sorted key in this TreeMap.
+ *
+ * @return the last sorted key
+ *
+ * @exception NoSuchElementException
+ * when this TreeMap is empty
+ */
+ public Object lastKey() {
+ if (root != null)
+ return maximum(root).key;
+ throw new NoSuchElementException();
+ }
+
+ private void leftRotate(TreeMapEntry x) {
+ TreeMapEntry y = x.right;
+ x.right = y.left;
+ if (y.left != null)
+ y.left.parent = x;
+ y.parent = x.parent;
+ if (x.parent == null) {
+ root = y;
+ } else {
+ if (x == x.parent.left)
+ x.parent.left = y;
+ else
+ x.parent.right = y;
+ }
+ y.left = x;
+ x.parent = y;
+ }
+
+ static TreeMapEntry maximum(TreeMapEntry x) {
+ while (x.right != null)
+ x = x.right;
+ return x;
+ }
+
+ static TreeMapEntry minimum(TreeMapEntry x) {
+ while (x.left != null)
+ x = x.left;
+ return x;
+ }
+
+ static TreeMapEntry predecessor(TreeMapEntry x) {
+ if (x.left != null)
+ return maximum(x.left);
+ TreeMapEntry y = x.parent;
+ while (y != null && x == y.left) {
+ x = y;
+ y = y.parent;
+ }
+ return y;
+ }
+
+ /**
+ * Maps the specified key to the specified value.
+ *
+ * @param key
+ * the key
+ * @param value
+ * the value
+ * @return the value of any previous mapping with the specified key or null
+ * if there was no mapping
+ *
+ * @exception ClassCastException
+ * when the key cannot be compared with the keys in this
+ * TreeMap
+ * @exception NullPointerException
+ * when the key is null and the comparator cannot handle null
+ */
+ public Object put(Object key, Object value) {
+ MapEntry entry = rbInsert(key);
+ Object result = entry.value;
+ entry.value = value;
+ return result;
+ }
+
+ /**
+ * Copies every mapping in the specified Map to this TreeMap.
+ *
+ * @param map
+ * the Map to copy mappings from
+ *
+ * @exception ClassCastException
+ * when a key in the Map cannot be compared with the keys in
+ * this TreeMap
+ * @exception NullPointerException
+ * when a key in the Map is null and the comparator cannot
+ * handle null
+ */
+ public void putAll(Map map) {
+ super.putAll(map);
+ }
+
+ void rbDelete(TreeMapEntry z) {
+ TreeMapEntry y = z.left == null || z.right == null ? z : successor(z);
+ TreeMapEntry x = y.left != null ? y.left : y.right;
+ if (x != null)
+ x.parent = y.parent;
+ if (y.parent == null)
+ root = x;
+ else if (y == y.parent.left)
+ y.parent.left = x;
+ else
+ y.parent.right = x;
+ modCount++;
+ if (y != z) {
+ z.key = y.key;
+ z.value = y.value;
+ }
+ if (!y.color && root != null) {
+ if (x == null)
+ fixup(y.parent);
+ else
+ fixup(x);
+ }
+ size--;
+ }
+
+ private TreeMapEntry rbInsert(Object object) {
+ int result = 0;
+ Comparable key = null;
+ if (comparator == null)
+ key = (Comparable) object;
+ TreeMapEntry y = null, x = root;
+ while (x != null) {
+ y = x;
+ result = key != null ? key.compareTo(x.key) : comparator.compare(
+ object, x.key);
+ if (result == 0)
+ return x;
+ x = result < 0 ? x.left : x.right;
+ }
+
+ size++;
+ modCount++;
+ TreeMapEntry z = new TreeMapEntry(object);
+ if (y == null)
+ return root = z;
+ z.parent = y;
+ if (result < 0)
+ y.left = z;
+ else
+ y.right = z;
+ balance(z);
+ return z;
+ }
+
+ /**
+ * Removes a mapping with the specified key from this TreeMap.
+ *
+ * @param key
+ * the key of the mapping to remove
+ * @return the value of the removed mapping or null if key is not a key in
+ * this TreeMap
+ *
+ * @exception ClassCastException
+ * when the key cannot be compared with the keys in this
+ * TreeMap
+ * @exception NullPointerException
+ * when the key is null and the comparator cannot handle null
+ */
+ public Object remove(Object key) {
+ TreeMapEntry node = find(key);
+ if (node == null)
+ return null;
+ Object result = node.value;
+ rbDelete(node);
+ return result;
+ }
+
+ private void rightRotate(TreeMapEntry x) {
+ TreeMapEntry y = x.left;
+ x.left = y.right;
+ if (y.right != null)
+ y.right.parent = x;
+ y.parent = x.parent;
+ if (x.parent == null) {
+ root = y;
+ } else {
+ if (x == x.parent.right)
+ x.parent.right = y;
+ else
+ x.parent.left = y;
+ }
+ y.right = x;
+ x.parent = y;
+ }
+
+ /**
+ * Answers the number of mappings in this TreeMap.
+ *
+ * @return the number of mappings in this TreeMap
+ */
+ public int size() {
+ return size;
+ }
+
+ /**
+ * Answers a SortedMap of the specified portion of this TreeMap which
+ * contains keys greater or equal to the start key but less than the end
+ * key. The returned SortedMap is backed by this TreeMap so changes to one
+ * are reflected by the other.
+ *
+ * @param startKey
+ * the start key
+ * @param endKey
+ * the end key
+ * @return a submap where the keys are greater or equal to
+ * <code>startKey</code> and less than <code>endKey</code>
+ *
+ * @exception ClassCastException
+ * when the start or end key cannot be compared with the keys
+ * in this TreeMap
+ * @exception NullPointerException
+ * when the start or end key is null and the comparator
+ * cannot handle null
+ */
+ public SortedMap subMap(Object startKey, Object endKey) {
+ if (comparator == null) {
+ if (((Comparable) startKey).compareTo(endKey) <= 0)
+ return new SubMap(startKey, this, endKey);
+ } else {
+ if (comparator.compare(startKey, endKey) <= 0)
+ return new SubMap(startKey, this, endKey);
+ }
+ throw new IllegalArgumentException();
+ }
+
+ static TreeMapEntry successor(TreeMapEntry x) {
+ if (x.right != null)
+ return minimum(x.right);
+ TreeMapEntry y = x.parent;
+ while (y != null && x == y.right) {
+ x = y;
+ y = y.parent;
+ }
+ return y;
+ }
+
+ /**
+ * Answers a SortedMap of the specified portion of this TreeMap which
+ * contains keys greater or equal to the start key. The returned SortedMap
+ * is backed by this TreeMap so changes to one are reflected by the other.
+ *
+ * @param startKey
+ * the start key
+ * @return a submap where the keys are greater or equal to
+ * <code>startKey</code>
+ *
+ * @exception ClassCastException
+ * when the start key cannot be compared with the keys in
+ * this TreeMap
+ * @exception NullPointerException
+ * when the start key is null and the comparator cannot
+ * handle null
+ */
+ public SortedMap tailMap(Object startKey) {
+ // Check for errors
+ if (comparator == null)
+ ((Comparable) startKey).compareTo(startKey);
+ else
+ comparator.compare(startKey, startKey);
+ return new SubMap(startKey, this);
+ }
+
+ /**
+ * Answers a Collection of the values contained in this TreeMap. The
+ * collection is backed by this TreeMap so changes to one are relected by
+ * the other. The collection does not support adding.
+ *
+ * @return a Collection of the values
+ */
+ public Collection values() {
+ if (valuesCollection == null) {
+ valuesCollection = new AbstractCollection() {
+ public boolean contains(Object object) {
+ return containsValue(object);
+ }
+
+ public int size() {
+ return size;
+ }
+
+ public void clear() {
+ TreeMap.this.clear();
+ }
+
+ public Iterator iterator() {
+ return new TreeMapIterator(TreeMap.this,
+ new MapEntry.Type() {
+ public Object get(MapEntry entry) {
+ return entry.value;
+ }
+ });
+ }
+ };
+ }
+ return valuesCollection;
+ }
+
+ private void writeObject(ObjectOutputStream stream) throws IOException {
+ stream.defaultWriteObject();
+ stream.writeInt(size);
+ if (size > 0) {
+ TreeMapEntry node = minimum(root);
+ while (node != null) {
+ stream.writeObject(node.key);
+ stream.writeObject(node.value);
+ node = successor(node);
+ }
+ }
+ }
+
+ private void readObject(ObjectInputStream stream) throws IOException,
+ ClassNotFoundException {
+ stream.defaultReadObject();
+ size = stream.readInt();
+ TreeMapEntry last = null;
+ for (int i = size; --i >= 0;) {
+ TreeMapEntry node = new TreeMapEntry(stream.readObject());
+ node.value = stream.readObject();
+ if (last == null)
+ root = node;
+ else {
+ node.parent = last;
+ last.right = node;
+ balance(node);
+ }
+ last = node;
+ }
+ }
+}
Added: incubator/harmony/enhanced/trunk/sandbox/contribs/ibm_core/java-src/luni/src/java/util/TreeMapEntry.java
URL: http://svn.apache.org/viewcvs/incubator/harmony/enhanced/trunk/sandbox/contribs/ibm_core/java-src/luni/src/java/util/TreeMapEntry.java?rev=350181&view=auto
==============================================================================
--- incubator/harmony/enhanced/trunk/sandbox/contribs/ibm_core/java-src/luni/src/java/util/TreeMapEntry.java (added)
+++ incubator/harmony/enhanced/trunk/sandbox/contribs/ibm_core/java-src/luni/src/java/util/TreeMapEntry.java Wed Nov 30 21:29:27 2005
@@ -0,0 +1,48 @@
+/* Copyright 1998, 2002 The Apache Software Foundation or its licensors, as applicable
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package java.util;
+
+
+/**
+ * TreeMapEntry is an internal class which is used to hold the entries of a
+ * TreeMap.
+ */
+class TreeMapEntry extends MapEntry {
+
+ TreeMapEntry parent, left, right;
+
+ boolean color;
+
+ TreeMapEntry(Object key) {
+ super(key);
+ }
+
+ TreeMapEntry(Object key, Object value) {
+ super(key, value);
+ }
+
+ TreeMapEntry clone(TreeMapEntry parentEntry) {
+ TreeMapEntry clone = (TreeMapEntry) super.clone();
+ clone.parent = parentEntry;
+ if (left != null) {
+ clone.left = left.clone(clone);
+ }
+ if (right != null) {
+ clone.right = right.clone(clone);
+ }
+ return clone;
+ }
+}
Added: incubator/harmony/enhanced/trunk/sandbox/contribs/ibm_core/java-src/luni/src/java/util/TreeSet.java
URL: http://svn.apache.org/viewcvs/incubator/harmony/enhanced/trunk/sandbox/contribs/ibm_core/java-src/luni/src/java/util/TreeSet.java?rev=350181&view=auto
==============================================================================
--- incubator/harmony/enhanced/trunk/sandbox/contribs/ibm_core/java-src/luni/src/java/util/TreeSet.java (added)
+++ incubator/harmony/enhanced/trunk/sandbox/contribs/ibm_core/java-src/luni/src/java/util/TreeSet.java Wed Nov 30 21:29:27 2005
@@ -0,0 +1,484 @@
+/* Copyright 1998, 2002 The Apache Software Foundation or its licensors, as applicable
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package java.util;
+
+
+import java.io.IOException;
+import java.io.ObjectInputStream;
+import java.io.ObjectOutputStream;
+import java.io.Serializable;
+
+/**
+ * TreeSet is an implementation of SortedSet. All optional operations are
+ * supported, adding and removing. The elements can be any objects which are
+ * comparable to each other either using their natural order or a specified
+ * Comparator.
+ */
+public class TreeSet extends AbstractSet implements SortedSet, Cloneable,
+ Serializable {
+
+ static final long serialVersionUID = -2479143000061671589L;
+
+ private transient TreeMap backingMap;
+
+ private static final class SubSet extends TreeMap.SubMap.SubMapSet
+ implements SortedSet {
+ SubSet() {
+ type = new MapEntry.Type() {
+ public Object get(MapEntry entry) {
+ return entry.key;
+ }
+ };
+ }
+
+ private SubSet(Object start, TreeMap map) {
+ this();
+ this.backingMap = map;
+ hasStart = true;
+ startKey = start;
+ }
+
+ private SubSet(Object start, TreeMap map, Object end) {
+ this();
+ this.backingMap = map;
+ hasStart = hasEnd = true;
+ startKey = start;
+ endKey = end;
+ }
+
+ private SubSet(TreeMap map, Object end) {
+ this();
+ this.backingMap = map;
+ hasEnd = true;
+ endKey = end;
+ }
+
+ public boolean add(Object object) {
+ checkRange(object);
+ return this.backingMap.put(object, object) != null;
+ }
+
+ public Comparator comparator() {
+ return this.backingMap.comparator();
+ }
+
+ public boolean contains(Object object) {
+ if (checkRange(object, hasStart, hasEnd))
+ return this.backingMap.containsKey(object);
+ return false;
+ }
+
+ public Object first() {
+ if (!hasStart)
+ return this.backingMap.firstKey();
+ TreeMapEntry node = this.backingMap.findAfter(startKey);
+ if (node != null && checkRange(node.key, false, hasEnd))
+ return node.key;
+ throw new NoSuchElementException();
+ }
+
+ public SortedSet headSet(Object end) {
+ checkRange(end);
+ if (hasStart)
+ return new SubSet(startKey, this.backingMap, end);
+ return new SubSet(this.backingMap, end);
+ }
+
+ public Object last() {
+ if (!hasEnd)
+ return this.backingMap.lastKey();
+ TreeMapEntry node = this.backingMap.findBefore(endKey);
+ if (node != null && checkRange(node.key, hasStart, false))
+ return node.key;
+ throw new NoSuchElementException();
+ }
+
+ public boolean remove(Object object) {
+ if (checkRange(object, hasStart, hasEnd))
+ return this.backingMap.remove(object) != null;
+ return false;
+ }
+
+ public SortedSet subSet(Object start, Object end) {
+ checkRange(start);
+ checkRange(end);
+ Comparator c = this.backingMap.comparator();
+ if (c == null) {
+ if (((Comparable) startKey).compareTo(endKey) <= 0)
+ return new SubSet(start, this.backingMap, end);
+ } else {
+ if (c.compare(startKey, endKey) <= 0)
+ return new SubSet(start, this.backingMap, end);
+ }
+ throw new IllegalArgumentException();
+ }
+
+ public SortedSet tailSet(Object start) {
+ checkRange(start);
+ if (hasEnd)
+ return new SubSet(start, this.backingMap, endKey);
+ return new SubSet(start, this.backingMap);
+ }
+ }
+
+ /**
+ * Contructs a new empty instance of TreeSet which uses natural ordering.
+ *
+ */
+ public TreeSet() {
+ backingMap = new TreeMap();
+ }
+
+ /**
+ * Constructs a new instance of TreeSet which uses natural ordering and
+ * containing the unique elements in the specified collection.
+ *
+ * @param collection
+ * the collection of elements to add
+ *
+ * @exception ClassCastException
+ * when an element in the Collection does not implement the
+ * Comparable interface, or the elements in the Collection
+ * cannot be compared
+ */
+ public TreeSet(Collection collection) {
+ this();
+ addAll(collection);
+ }
+
+ /**
+ * Contructs a new empty instance of TreeSet which uses the specified
+ * Comparator.
+ *
+ * @param comparator
+ * the Comparator
+ */
+ public TreeSet(Comparator comparator) {
+ backingMap = new TreeMap(comparator);
+ }
+
+ /**
+ * Constructs a new instance of TreeSet containing the elements in the
+ * specified SortedSet and using the same Comparator.
+ *
+ * @param set
+ * the SortedSet of elements to add
+ */
+ public TreeSet(SortedSet set) {
+ this(set.comparator());
+ Iterator it = set.iterator();
+ if (it.hasNext()) {
+ Object object = it.next();
+ TreeMapEntry last = new TreeMapEntry(object, object);
+ backingMap.root = last;
+ backingMap.size = 1;
+ while (it.hasNext()) {
+ object = it.next();
+ TreeMapEntry x = new TreeMapEntry(object, object);
+ x.parent = last;
+ last.right = x;
+ backingMap.size++;
+ backingMap.balance(x);
+ last = x;
+ }
+ }
+ }
+
+ /**
+ * Adds the specified object to this TreeSet.
+ *
+ * @param object
+ * the object to add
+ * @return true when this TreeSet did not already contain the object, false
+ * otherwise
+ *
+ * @exception ClassCastException
+ * when the object cannot be compared with the elements in
+ * this TreeSet
+ * @exception NullPointerException
+ * when the object is null and the comparator cannot handle
+ * null
+ */
+ public boolean add(Object object) {
+ return backingMap.put(object, object) == null;
+ }
+
+ /**
+ * Adds the objects in the specified Collection to this TreeSet.
+ *
+ * @param collection
+ * the Collection of objects
+ * @return true if this TreeSet is modified, false otherwise
+ *
+ * @exception ClassCastException
+ * when an object in the Collection cannot be compared with
+ * the elements in this TreeSet
+ * @exception NullPointerException
+ * when an object in the Collection is null and the
+ * comparator cannot handle null
+ */
+ public boolean addAll(Collection collection) {
+ return super.addAll(collection);
+ }
+
+ /**
+ * Removes all elements from this TreeSet, leaving it empty.
+ *
+ * @see #isEmpty
+ * @see #size
+ */
+ public void clear() {
+ backingMap.clear();
+ }
+
+ /**
+ * Answers a new TreeSet with the same elements, size and comparator as this
+ * TreeSet.
+ *
+ * @return a shallow copy of this TreeSet
+ *
+ * @see java.lang.Cloneable
+ */
+ public Object clone() {
+ try {
+ TreeSet clone = (TreeSet) super.clone();
+ clone.backingMap = (TreeMap) backingMap.clone();
+ return clone;
+ } catch (CloneNotSupportedException e) {
+ return null;
+ }
+ }
+
+ /**
+ * Answers the Comparator used to compare elements in this TreeSet.
+ *
+ * @return a Comparator or null if the natural ordering is used
+ */
+ public Comparator comparator() {
+ return backingMap.comparator();
+ }
+
+ /**
+ * Searches this TreeSet for the specified object.
+ *
+ * @param object
+ * the object to search for
+ * @return true if <code>object</code> is an element of this TreeSet,
+ * false otherwise
+ *
+ * @exception ClassCastException
+ * when the object cannot be compared with the elements in
+ * this TreeSet
+ * @exception NullPointerException
+ * when the object is null and the comparator cannot handle
+ * null
+ */
+ public boolean contains(Object object) {
+ return backingMap.containsKey(object);
+ }
+
+ /**
+ * Answers the first element in this TreeSet.
+ *
+ * @return the first element
+ *
+ * @exception NoSuchElementException
+ * when this TreeSet is empty
+ */
+ public Object first() {
+ return backingMap.firstKey();
+ }
+
+ /**
+ * Answers a SortedSet of the specified portion of this TreeSet which
+ * contains elements less than the end element. The returned SortedSet is
+ * backed by this TreeSet so changes to one are reflected by the other.
+ *
+ * @param end
+ * the end element
+ * @return a subset where the elements are less than <code>end</code>
+ *
+ * @exception ClassCastException
+ * when the end object cannot be compared with the elements
+ * in this TreeSet
+ * @exception NullPointerException
+ * when the end object is null and the comparator cannot
+ * handle null
+ */
+ public SortedSet headSet(Object end) {
+ // Check for errors
+ Comparator c = backingMap.comparator();
+ if (c == null)
+ ((Comparable) end).compareTo(end);
+ else
+ c.compare(end, end);
+ return new SubSet(backingMap, end);
+ }
+
+ /**
+ * Answers if this TreeSet has no elements, a size of zero.
+ *
+ * @return true if this TreeSet has no elements, false otherwise
+ *
+ * @see #size
+ */
+ public boolean isEmpty() {
+ return backingMap.isEmpty();
+ }
+
+ /**
+ * Answers an Iterator on the elements of this TreeSet.
+ *
+ * @return an Iterator on the elements of this TreeSet
+ *
+ * @see Iterator
+ */
+ public Iterator iterator() {
+ return backingMap.keySet().iterator();
+ }
+
+ /**
+ * Answers the last element in this TreeSet.
+ *
+ * @return the last element
+ *
+ * @exception NoSuchElementException
+ * when this TreeSet is empty
+ */
+ public Object last() {
+ return backingMap.lastKey();
+ }
+
+ /**
+ * Removes an occurrence of the specified object from this TreeSet.
+ *
+ * @param object
+ * the object to remove
+ * @return true if this TreeSet is modified, false otherwise
+ *
+ * @exception ClassCastException
+ * when the object cannot be compared with the elements in
+ * this TreeSet
+ * @exception NullPointerException
+ * when the object is null and the comparator cannot handle
+ * null
+ */
+ public boolean remove(Object object) {
+ return backingMap.remove(object) != null;
+ }
+
+ /**
+ * Answers the number of elements in this TreeSet.
+ *
+ * @return the number of elements in this TreeSet
+ */
+ public int size() {
+ return backingMap.size();
+ }
+
+ /**
+ * Answers a SortedSet of the specified portion of this TreeSet which
+ * contains elements greater or equal to the start element but less than the
+ * end element. The returned SortedSet is backed by this TreeSet so changes
+ * to one are reflected by the other.
+ *
+ * @param start
+ * the start element
+ * @param end
+ * the end element
+ * @return a subset where the elements are greater or equal to
+ * <code>start</code> and less than <code>end</code>
+ *
+ * @exception ClassCastException
+ * when the start or end object cannot be compared with the
+ * elements in this TreeSet
+ * @exception NullPointerException
+ * when the start or end object is null and the comparator
+ * cannot handle null
+ */
+ public SortedSet subSet(Object start, Object end) {
+ Comparator c = backingMap.comparator();
+ if (c == null) {
+ if (((Comparable) start).compareTo(end) <= 0)
+ return new SubSet(start, backingMap, end);
+ } else {
+ if (c.compare(start, end) <= 0)
+ return new SubSet(start, backingMap, end);
+ }
+ throw new IllegalArgumentException();
+ }
+
+ /**
+ * Answers a SortedSet of the specified portion of this TreeSet which
+ * contains elements greater or equal to the start element. The returned
+ * SortedSet is backed by this TreeSet so changes to one are reflected by
+ * the other.
+ *
+ * @param start
+ * the start element
+ * @return a subset where the elements are greater or equal to
+ * <code>start</code>
+ *
+ * @exception ClassCastException
+ * when the start object cannot be compared with the elements
+ * in this TreeSet
+ * @exception NullPointerException
+ * when the start object is null and the comparator cannot
+ * handle null
+ */
+ public SortedSet tailSet(Object start) {
+ // Check for errors
+ Comparator c = backingMap.comparator();
+ if (c == null)
+ ((Comparable) start).compareTo(start);
+ else
+ c.compare(start, start);
+ return new SubSet(start, backingMap);
+ }
+
+ private void writeObject(ObjectOutputStream stream) throws IOException {
+ stream.defaultWriteObject();
+ stream.writeObject(backingMap.comparator());
+ stream.writeInt(backingMap.size);
+ if (backingMap.size > 0) {
+ TreeMapEntry node = TreeMap.minimum(backingMap.root);
+ while (node != null) {
+ stream.writeObject(node.key);
+ node = TreeMap.successor(node);
+ }
+ }
+ }
+
+ private void readObject(ObjectInputStream stream) throws IOException,
+ ClassNotFoundException {
+ stream.defaultReadObject();
+ backingMap = new TreeMap((Comparator) stream.readObject());
+ backingMap.size = stream.readInt();
+ TreeMapEntry last = null;
+ for (int i = backingMap.size; --i >= 0;) {
+ TreeMapEntry node = new TreeMapEntry(stream.readObject());
+ node.value = this;
+ if (last == null)
+ backingMap.root = node;
+ else {
+ node.parent = last;
+ last.right = node;
+ backingMap.balance(node);
+ }
+ last = node;
+ }
+ }
+}
Added: incubator/harmony/enhanced/trunk/sandbox/contribs/ibm_core/java-src/luni/src/java/util/Vector.java
URL: http://svn.apache.org/viewcvs/incubator/harmony/enhanced/trunk/sandbox/contribs/ibm_core/java-src/luni/src/java/util/Vector.java?rev=350181&view=auto
==============================================================================
--- incubator/harmony/enhanced/trunk/sandbox/contribs/ibm_core/java-src/luni/src/java/util/Vector.java (added)
+++ incubator/harmony/enhanced/trunk/sandbox/contribs/ibm_core/java-src/luni/src/java/util/Vector.java Wed Nov 30 21:29:27 2005
@@ -0,0 +1,972 @@
+/* Copyright 1998, 2005 The Apache Software Foundation or its licensors, as applicable
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package java.util;
+
+
+import java.io.IOException;
+import java.io.ObjectOutputStream;
+import java.io.Serializable;
+import java.lang.reflect.Array;
+
+/**
+ * Vector is a variable size contiguous indexable array of Objects. The size of
+ * the Vector is the number of Objects it contains. The capacity of the Vector
+ * is the number of Objects it can hold.
+ * <p>
+ * Objects may be inserted at any position up to the size of the Vector,
+ * increasing the size of the Vector. Objects at any position in the Vector may
+ * be removed, shrinking the size of the Vector. Objects at any position in the
+ * Vector may be replaced, which does not affect the Vector size.
+ * <p>
+ * The capacity of a Vector may be specified when the Vector is created. If the
+ * capacity of the Vector is exceeded, the capacity is increased, doubling by
+ * default.
+ *
+ * @see java.lang.StringBuffer
+ */
+public class Vector extends AbstractList implements List, RandomAccess,
+ Cloneable, Serializable {
+
+ static final long serialVersionUID = -2767605614048989439L;
+
+ /**
+ * The number of elements or the size of the vector.
+ */
+ protected int elementCount;
+
+ /**
+ * The elements of the vector.
+ */
+ protected Object[] elementData;
+
+ /**
+ * How many elements should be added to the vector when it is detected that
+ * it needs to grow to accomodate extra entries.
+ */
+ protected int capacityIncrement;
+
+ private static final int DEFAULT_SIZE = 10;
+
+ /**
+ * Constructs a new Vector using the default capacity.
+ */
+ public Vector() {
+ this(DEFAULT_SIZE, 0);
+ }
+
+ /**
+ * Constructs a new Vector using the specified capacity.
+ *
+ * @param capacity
+ * the initial capacity of the new vector
+ */
+ public Vector(int capacity) {
+ this(capacity, 0);
+ }
+
+ /**
+ * Constructs a new Vector using the specified capacity and capacity
+ * increment.
+ *
+ * @param capacity
+ * the initial capacity of the new Vector
+ * @param capacityIncrement
+ * the amount to increase the capacity when this Vector is full
+ */
+ public Vector(int capacity, int capacityIncrement) {
+ elementCount = 0;
+ try {
+ elementData = new Object[capacity];
+ } catch (NegativeArraySizeException e) {
+ throw new IllegalArgumentException();
+ }
+ this.capacityIncrement = capacityIncrement;
+ }
+
+ /**
+ * Constructs a new instance of <code>Vector</code> containing the
+ * elements in <code>collection</code>. The order of the elements in the
+ * new <code>Vector</code> is dependent on the iteration order of the seed
+ * collection.
+ *
+ * @param collection
+ * the collection of elements to add
+ */
+ public Vector(Collection collection) {
+ this(collection.size(), 0);
+ Iterator it = collection.iterator();
+ while (it.hasNext())
+ elementData[elementCount++] = it.next();
+ }
+
+ /**
+ * Adds the specified object into this Vector at the specified location. The
+ * object is inserted before any previous element at the specified location.
+ * If the location is equal to the size of this Vector, the object is added
+ * at the end.
+ *
+ * @param location
+ * the index at which to insert the element
+ * @param object
+ * the object to insert in this Vector
+ *
+ * @exception ArrayIndexOutOfBoundsException
+ * when <code>location < 0 || > size()</code>
+ *
+ * @see #addElement
+ * @see #size
+ */
+ public void add(int location, Object object) {
+ insertElementAt(object, location);
+ }
+
+ /**
+ * Adds the specified object at the end of this Vector.
+ *
+ * @param object
+ * the object to add to the Vector
+ * @return true
+ */
+ public boolean add(Object object) {
+ addElement(object);
+ return true;
+ }
+
+ /**
+ * Inserts the objects in the specified Collection at the specified location
+ * in this Vector. The objects are inserted in the order in which they are
+ * returned from the Collection iterator.
+ *
+ * @param location
+ * the location to insert the objects
+ * @param collection
+ * the Collection of objects
+ * @return true if this Vector is modified, false otherwise
+ *
+ * @exception ArrayIndexOutOfBoundsException
+ * when <code>location < 0</code> or
+ * <code>location > size()</code>
+ */
+ public synchronized boolean addAll(int location, Collection collection) {
+ if (0 <= location && location <= elementCount) {
+ int size = collection.size();
+ if (size == 0)
+ return false;
+ int required = size - (elementData.length - elementCount);
+ if (required > 0)
+ growBy(required);
+ int count = elementCount - location;
+ if (count > 0)
+ System.arraycopy(elementData, location, elementData, location
+ + size, count);
+ Iterator it = collection.iterator();
+ while (it.hasNext())
+ elementData[location++] = it.next();
+ elementCount += size;
+ modCount++;
+ return true;
+ } else
+ throw new ArrayIndexOutOfBoundsException(location);
+ }
+
+ /**
+ * Adds the objects in the specified Collection to the end of this Vector.
+ *
+ * @param collection
+ * the Collection of objects
+ * @return true if this Vector is modified, false otherwise
+ */
+ public synchronized boolean addAll(Collection collection) {
+ return addAll(elementCount, collection);
+ }
+
+ /**
+ * Adds the specified object at the end of this Vector.
+ *
+ * @param object
+ * the object to add to the Vector
+ */
+ public synchronized void addElement(Object object) {
+ if (elementCount == elementData.length)
+ growByOne();
+ elementData[elementCount++] = object;
+ modCount++;
+ }
+
+ /**
+ * Answers the number of elements this Vector can hold without growing.
+ *
+ * @return the capacity of this Vector
+ *
+ * @see #ensureCapacity
+ * @see #size
+ */
+ public synchronized int capacity() {
+ return elementData.length;
+ }
+
+ /**
+ * Removes all elements from this Vector, leaving it empty.
+ *
+ * @see #isEmpty
+ * @see #size
+ */
+ public void clear() {
+ removeAllElements();
+ }
+
+ /**
+ * Answers a new Vector with the same elements, size, capacity and capacity
+ * increment as this Vector.
+ *
+ * @return a shallow copy of this Vector
+ *
+ * @see java.lang.Cloneable
+ */
+ public synchronized Object clone() {
+ try {
+ Vector vector = (Vector) super.clone();
+ vector.elementData = (Object[]) elementData.clone();
+ return vector;
+ } catch (CloneNotSupportedException e) {
+ return null;
+ }
+ }
+
+ /**
+ * Searches this Vector for the specified object.
+ *
+ * @param object
+ * the object to look for in this Vector
+ * @return true if object is an element of this Vector, false otherwise
+ *
+ * @see #indexOf(Object)
+ * @see #indexOf(Object, int)
+ * @see java.lang.Object#equals
+ */
+ public boolean contains(Object object) {
+ return indexOf(object, 0) != -1;
+ }
+
+ /**
+ * Searches this Vector for all objects in the specified Collection.
+ *
+ * @param collection
+ * the Collection of objects
+ * @return true if all objects in the specified Collection are elements of
+ * this Vector, false otherwise
+ */
+ public synchronized boolean containsAll(Collection collection) {
+ return super.containsAll(collection);
+ }
+
+ /**
+ * Attempts to copy elements contained by this <code>Vector</code> into
+ * the corresponding elements of the supplied <code>Object</code> array.
+ *
+ * @param elements
+ * the <code>Object</code> array into which the elements of
+ * this Vector are copied
+ *
+ * @see #clone
+ */
+ public synchronized void copyInto(Object[] elements) {
+ System.arraycopy(elementData, 0, elements, 0, elementCount);
+ }
+
+ /**
+ * Answers the element at the specified location in this Vector.
+ *
+ * @param location
+ * the index of the element to return in this Vector
+ * @return the element at the specified location
+ *
+ * @exception ArrayIndexOutOfBoundsException
+ * when <code>location < 0 || >= size()</code>
+ *
+ * @see #size
+ */
+ public synchronized Object elementAt(int location) {
+ if (location < elementCount) {
+ return elementData[location];
+ }
+ throw new ArrayIndexOutOfBoundsException(location);
+ }
+
+ /**
+ * Answers an Enumeration on the elements of this Vector. The results of the
+ * Enumeration may be affected if the contents of this Vector are modified.
+ *
+ * @return an Enumeration of the elements of this Vector
+ *
+ * @see #elementAt
+ * @see Enumeration
+ */
+ public Enumeration elements() {
+ return new Enumeration() {
+ int pos = 0;
+
+ public boolean hasMoreElements() {
+ return pos < elementCount;
+ }
+
+ public Object nextElement() {
+ synchronized (Vector.this) {
+ if (pos < elementCount) {
+ return elementData[pos++];
+ }
+ }
+ throw new NoSuchElementException();
+ }
+ };
+ }
+
+ /**
+ * Ensures that this Vector can hold the specified number of elements
+ * without growing.
+ *
+ * @param minimumCapacity
+ * the minimum number of elements that this vector will hold
+ * before growing
+ *
+ * @see #capacity
+ */
+ public synchronized void ensureCapacity(int minimumCapacity) {
+ if (elementData.length < minimumCapacity) {
+ int next = (capacityIncrement <= 0 ? elementData.length
+ : capacityIncrement)
+ + elementData.length;
+ grow(minimumCapacity > next ? minimumCapacity : next);
+ }
+ }
+
+ /**
+ * Compares the specified object to this Vector and answer if they are
+ * equal. The object must be a List which contains the same objects in the
+ * same order.
+ *
+ * @param object
+ * the object to compare with this object
+ * @return true if the specified object is equal to this Vector, false
+ * otherwise
+ *
+ * @see #hashCode
+ */
+ public synchronized boolean equals(Object object) {
+ if (this == object)
+ return true;
+ if (object instanceof List) {
+ List list = (List) object;
+ if (list.size() != size())
+ return false;
+
+ int index = 0;
+ Iterator it = list.iterator();
+ while (it.hasNext()) {
+ Object e1 = elementData[index++], e2 = it.next();
+ if (!(e1 == null ? e2 == null : e1.equals(e2)))
+ return false;
+ }
+ return true;
+ }
+ return false;
+ }
+
+ /**
+ * Answers the first element in this Vector.
+ *
+ * @return the element at the first position
+ *
+ * @exception NoSuchElementException
+ * when this vector is empty
+ *
+ * @see #elementAt
+ * @see #lastElement
+ * @see #size
+ */
+ public synchronized Object firstElement() {
+ if (elementCount > 0) {
+ return elementData[0];
+ }
+ throw new NoSuchElementException();
+ }
+
+ /**
+ * Answers the element at the specified location in this Vector.
+ *
+ * @param location
+ * the index of the element to return in this Vector
+ * @return the element at the specified location
+ *
+ * @exception ArrayIndexOutOfBoundsException
+ * when <code>location < 0 || >= size()</code>
+ *
+ * @see #size
+ */
+ public Object get(int location) {
+ return elementAt(location);
+ }
+
+ private void grow(int newCapacity) {
+ Object[] newData = new Object[newCapacity];
+ System.arraycopy(elementData, 0, newData, 0, elementCount); // assumes
+ // elementCount
+ // is <=
+ // newCapacity
+ elementData = newData;
+ }
+
+ /**
+ * jit optimization
+ */
+ private void growByOne() {
+ int adding = 0;
+ if (capacityIncrement <= 0) {
+ if ((adding = elementData.length) == 0)
+ adding = 1;
+ } else
+ adding = capacityIncrement;
+
+ Object[] newData = new Object[elementData.length + adding];
+ System.arraycopy(elementData, 0, newData, 0, elementCount);
+ elementData = newData;
+ }
+
+ private void growBy(int required) {
+ int adding = 0;
+ if (capacityIncrement <= 0) {
+ if ((adding = elementData.length) == 0)
+ adding = required;
+ while (adding < required)
+ adding += adding;
+ } else {
+ adding = (required / capacityIncrement) * capacityIncrement;
+ if (adding < required)
+ adding += capacityIncrement;
+ }
+ Object[] newData = new Object[elementData.length + adding];
+ System.arraycopy(elementData, 0, newData, 0, elementCount);
+ elementData = newData;
+ }
+
+ /**
+ * Answers an integer hash code for the receiver. Objects which are equal
+ * answer the same value for this method.
+ *
+ * @return the receiver's hash
+ *
+ * @see #equals
+ */
+ public synchronized int hashCode() {
+ int result = 1;
+ for (int i = 0; i < elementCount; i++)
+ result = (31 * result)
+ + (elementData[i] == null ? 0 : elementData[i].hashCode());
+ return result;
+ }
+
+ /**
+ * Searches in this Vector for the index of the specified object. The search
+ * for the object starts at the beginning and moves towards the end of this
+ * Vector.
+ *
+ * @param object
+ * the object to find in this Vector
+ * @return the index in this Vector of the specified element, -1 if the
+ * element isn't found
+ *
+ * @see #contains
+ * @see #lastIndexOf(Object)
+ * @see #lastIndexOf(Object, int)
+ */
+ public int indexOf(Object object) {
+ return indexOf(object, 0);
+ }
+
+ /**
+ * Searches in this Vector for the index of the specified object. The search
+ * for the object starts at the specified location and moves towards the end
+ * of this Vector.
+ *
+ * @param object
+ * the object to find in this Vector
+ * @param location
+ * the index at which to start searching
+ * @return the index in this Vector of the specified element, -1 if the
+ * element isn't found
+ *
+ * @exception ArrayIndexOutOfBoundsException
+ * when <code>location < 0</code>
+ *
+ * @see #contains
+ * @see #lastIndexOf(Object)
+ * @see #lastIndexOf(Object, int)
+ */
+ public synchronized int indexOf(Object object, int location) {
+ if (object != null) {
+ for (int i = location; i < elementCount; i++)
+ if (object.equals(elementData[i]))
+ return i;
+ } else {
+ for (int i = location; i < elementCount; i++)
+ if (elementData[i] == null)
+ return i;
+ }
+ return -1;
+ }
+
+ /**
+ * Inserts the specified object into this Vector at the specified location.
+ * This object is inserted before any previous element at the specified
+ * location. If the location is equal to the size of this Vector, the object
+ * is added at the end.
+ *
+ * @param object
+ * the object to insert in this Vector
+ * @param location
+ * the index at which to insert the element
+ *
+ * @exception ArrayIndexOutOfBoundsException
+ * when <code>location < 0 || > size()</code>
+ *
+ * @see #addElement
+ * @see #size
+ */
+ public synchronized void insertElementAt(Object object, int location) {
+ if (0 <= location && location <= elementCount) {
+ if (elementCount == elementData.length)
+ growByOne();
+ int count = elementCount - location;
+ if (count > 0)
+ System.arraycopy(elementData, location, elementData,
+ location + 1, count);
+ elementData[location] = object;
+ elementCount++;
+ modCount++;
+ } else
+ throw new ArrayIndexOutOfBoundsException(location);
+ }
+
+ /**
+ * Answers if this Vector has no elements, a size of zero.
+ *
+ * @return true if this Vector has no elements, false otherwise
+ *
+ * @see #size
+ */
+ public synchronized boolean isEmpty() {
+ return elementCount == 0;
+ }
+
+ /**
+ * Answers the last element in this Vector.
+ *
+ * @return the element at the last position
+ *
+ * @exception NoSuchElementException
+ * when this vector is empty
+ *
+ * @see #elementAt
+ * @see #firstElement
+ * @see #size
+ */
+ public synchronized Object lastElement() {
+ try {
+ return elementData[elementCount - 1];
+ } catch (IndexOutOfBoundsException e) {
+ throw new NoSuchElementException();
+ }
+ }
+
+ /**
+ * Searches in this Vector for the index of the specified object. The search
+ * for the object starts at the end and moves towards the start of this
+ * Vector.
+ *
+ * @param object
+ * the object to find in this Vector
+ * @return the index in this Vector of the specified element, -1 if the
+ * element isn't found
+ *
+ * @see #contains
+ * @see #indexOf(Object)
+ * @see #indexOf(Object, int)
+ */
+ public synchronized int lastIndexOf(Object object) {
+ return lastIndexOf(object, elementCount - 1);
+ }
+
+ /**
+ * Searches in this Vector for the index of the specified object. The search
+ * for the object starts at the specified location and moves towards the
+ * start of this Vector.
+ *
+ * @param object
+ * the object to find in this Vector
+ * @param location
+ * the index at which to start searching
+ * @return the index in this Vector of the specified element, -1 if the
+ * element isn't found
+ *
+ * @exception ArrayIndexOutOfBoundsException
+ * when <code>location >= size()</code>
+ *
+ * @see #contains
+ * @see #indexOf(Object)
+ * @see #indexOf(Object, int)
+ */
+ public synchronized int lastIndexOf(Object object, int location) {
+ if (location < elementCount) {
+ if (object != null) {
+ for (int i = location; i >= 0; i--)
+ if (object.equals(elementData[i]))
+ return i;
+ } else {
+ for (int i = location; i >= 0; i--)
+ if (elementData[i] == null)
+ return i;
+ }
+ return -1;
+ } else
+ throw new ArrayIndexOutOfBoundsException(location);
+ }
+
+ /*
+ * (non-Javadoc)
+ *
+ * @see java.util.List#remove(int)
+ */
+ public synchronized Object remove(int location) {
+ if (location < elementCount) {
+ Object result = elementData[location];
+ elementCount--;
+ int size = elementCount - location;
+ if (size > 0)
+ System.arraycopy(elementData, location + 1, elementData,
+ location, size);
+ elementData[elementCount] = null;
+ modCount++;
+ return result;
+ } else
+ throw new ArrayIndexOutOfBoundsException(location);
+ }
+
+ /**
+ * Removes the first occurrence, starting at the beginning and moving
+ * towards the end, of the specified object from this Vector.
+ *
+ * @param object
+ * the object to remove from this Vector
+ * @return true if the specified object was found, false otherwise
+ *
+ * @see #removeAllElements
+ * @see #removeElementAt
+ * @see #size
+ */
+ public boolean remove(Object object) {
+ return removeElement(object);
+ }
+
+ /**
+ * Removes all occurrences in this Vector of each object in the specified
+ * Collection.
+ *
+ * @param collection
+ * the Collection of objects to remove
+ * @return true if this Vector is modified, false otherwise
+ */
+ public synchronized boolean removeAll(Collection collection) {
+ return super.removeAll(collection);
+ }
+
+ /**
+ * Removes all elements from this Vector, leaving the size zero and the
+ * capacity unchanged.
+ *
+ * @see #isEmpty
+ * @see #size
+ */
+ public synchronized void removeAllElements() {
+ Arrays.fill(elementData, 0, elementCount, null);
+ modCount++;
+ elementCount = 0;
+ }
+
+ /**
+ * Removes the first occurrence, starting at the beginning and moving
+ * towards the end, of the specified object from this Vector.
+ *
+ * @param object
+ * the object to remove from this Vector
+ * @return true if the specified object was found, false otherwise
+ *
+ * @see #removeAllElements
+ * @see #removeElementAt
+ * @see #size
+ */
+ public synchronized boolean removeElement(Object object) {
+ int index;
+ if ((index = indexOf(object, 0)) == -1)
+ return false;
+ removeElementAt(index);
+ return true;
+ }
+
+ /**
+ * Removes the element found at index position <code>location</code> from
+ * this <code>Vector</code> and decrements the size accordingly.
+ *
+ * @param location
+ * the index of the element to remove
+ *
+ * @exception ArrayIndexOutOfBoundsException
+ * when <code>location < 0 || >= size()</code>
+ *
+ * @see #removeElement
+ * @see #removeAllElements
+ * @see #size
+ */
+ public synchronized void removeElementAt(int location) {
+ if (0 <= location && location < elementCount) {
+ elementCount--;
+ int size = elementCount - location;
+ if (size > 0)
+ System.arraycopy(elementData, location + 1, elementData,
+ location, size);
+ elementData[elementCount] = null;
+ modCount++;
+ } else
+ throw new ArrayIndexOutOfBoundsException(location);
+ }
+
+ /**
+ * Removes the objects in the specified range from the start to the, but not
+ * including, end index.
+ *
+ * @param start
+ * the index at which to start removing
+ * @param end
+ * the index one past the end of the range to remove
+ *
+ * @exception IndexOutOfBoundsException
+ * when <code>start < 0, start > end</code> or
+ * <code>end > size()</code>
+ */
+ protected void removeRange(int start, int end) {
+ if (start >= 0 && start <= end && end <= size()) {
+ if (start == end)
+ return;
+ if (end != elementCount) {
+ System.arraycopy(elementData, end, elementData, start,
+ elementCount - end);
+ int newCount = elementCount - (end - start);
+ Arrays.fill(elementData, newCount, elementCount, null);
+ elementCount = newCount;
+ } else {
+ Arrays.fill(elementData, start, elementCount, null);
+ elementCount = start;
+ }
+ modCount++;
+ } else
+ throw new IndexOutOfBoundsException();
+ }
+
+ /**
+ * Removes all objects from this Vector that are not contained in the
+ * specified Collection.
+ *
+ * @param collection
+ * the Collection of objects to retain
+ * @return true if this Vector is modified, false otherwise
+ */
+ public synchronized boolean retainAll(Collection collection) {
+ return super.retainAll(collection);
+ }
+
+ /**
+ * Replaces the element at the specified location in this Vector with the
+ * specified object.
+ *
+ * @param location
+ * the index at which to put the specified object
+ * @param object
+ * the object to add to this Vector
+ * @return the previous element at the location
+ *
+ * @exception ArrayIndexOutOfBoundsException
+ * when <code>location < 0 || >= size()</code>
+ *
+ * @see #size
+ */
+ public synchronized Object set(int location, Object object) {
+ if (location < elementCount) {
+ Object result = elementData[location];
+ elementData[location] = object;
+ return result;
+ } else
+ throw new ArrayIndexOutOfBoundsException(location);
+ }
+
+ /**
+ * Replaces the element at the specified location in this Vector with the
+ * specified object.
+ *
+ * @param object
+ * the object to add to this Vector
+ * @param location
+ * the index at which to put the specified object
+ *
+ * @exception ArrayIndexOutOfBoundsException
+ * when <code>location < 0 || >= size()</code>
+ *
+ * @see #size
+ */
+ public synchronized void setElementAt(Object object, int location) {
+ if (location < elementCount)
+ elementData[location] = object;
+ else
+ throw new ArrayIndexOutOfBoundsException(location);
+ }
+
+ /**
+ * Sets the size of this Vector to the specified size. If there are more
+ * than length elements in this Vector, the elements at end are lost. If
+ * there are less than length elements in the Vector, the additional
+ * elements contain null.
+ *
+ * @param length
+ * the new size of this Vector
+ *
+ * @see #size
+ */
+ public synchronized void setSize(int length) {
+ if (length == elementCount)
+ return;
+ ensureCapacity(length);
+ if (elementCount > length) {
+ Arrays.fill(elementData, length, elementCount, null);
+ }
+ elementCount = length;
+ modCount++;
+ }
+
+ /**
+ * Answers the number of elements in this Vector.
+ *
+ * @return the number of elements in this Vector
+ *
+ * @see #elementCount
+ * @see #lastElement
+ */
+ public synchronized int size() {
+ return elementCount;
+ }
+
+ /**
+ * Answers a List of the specified portion of this Vector from the start
+ * index to one less than the end index. The returned List is backed by this
+ * Vector so changes to one are reflected by the other.
+ *
+ * @param start
+ * the index at which to start the sublist
+ * @param end
+ * the index one past the end of the sublist
+ * @return a List of a portion of this Vector
+ *
+ * @exception IndexOutOfBoundsException
+ * when <code>start < 0 or <code>end > size()</code>
+ * @exception IllegalArgumentException when <code>start > end</code>
+ */
+ public synchronized List subList(int start, int end) {
+ return new Collections.SynchronizedRandomAccessList(super.subList(
+ start, end), this);
+ }
+
+ /**
+ * Answers a new array containing all elements contained in this Vector.
+ *
+ * @return an array of the elements from this Vector
+ */
+ public synchronized Object[] toArray() {
+ Object[] result = new Object[elementCount];
+ System.arraycopy(elementData, 0, result, 0, elementCount);
+ return result;
+ }
+
+ /**
+ * Answers an array containing all elements contained in this Vector. If the
+ * specified array is large enough to hold the elements, the specified array
+ * is used, otherwise an array of the same type is created. If the specified
+ * array is used and is larger than this Vector, the array element following
+ * the collection elements is set to null.
+ *
+ * @param contents
+ * the array
+ * @return an array of the elements from this Vector
+ *
+ * @exception ArrayStoreException
+ * when the type of an element in this Vector cannot be
+ * stored in the type of the specified array
+ */
+ public synchronized Object[] toArray(Object[] contents) {
+ if (elementCount > contents.length)
+ contents = (Object[]) Array.newInstance(contents.getClass()
+ .getComponentType(), elementCount);
+ System.arraycopy(elementData, 0, contents, 0, elementCount);
+ if (elementCount < contents.length)
+ contents[elementCount] = null;
+ return contents;
+ }
+
+ /**
+ * Answers the string representation of this Vector.
+ *
+ * @return the string representation of this Vector
+ *
+ * @see #elements
+ */
+ public synchronized String toString() {
+ if (elementCount == 0)
+ return "[]"; //$NON-NLS-1$
+ int length = elementCount - 1;
+ StringBuffer buffer = new StringBuffer(size() * 16);
+ buffer.append('[');
+ for (int i = 0; i < length; i++) {
+ buffer.append(elementData[i]);
+ buffer.append(", "); //$NON-NLS-1$
+ }
+ buffer.append(elementData[length]);
+ buffer.append(']');
+ return buffer.toString();
+ }
+
+ /**
+ * Sets the capacity of this Vector to be the same as the size.
+ *
+ * @see #capacity
+ * @see #ensureCapacity
+ * @see #size
+ */
+ public synchronized void trimToSize() {
+ if (elementData.length != elementCount)
+ grow(elementCount);
+ }
+
+ private synchronized void writeObject(ObjectOutputStream stream)
+ throws IOException {
+ stream.defaultWriteObject();
+ }
+}