obtained gcc-4.6.4.tar.bz2 from upstream website;upstream

verified gcc-4.6.4.tar.bz2.sig;
imported gcc-4.6.4 source tree from verified upstream tarball.

downloading a git-generated archive based on the 'upstream' tag
should provide you with a source tree that is binary identical
to the one extracted from the above tarball.

if you have obtained the source via the command 'git clone',
however, do note that line-endings of files in your working
directory might differ from line-endings of the respective
files in the upstream repository.

1 files changed, 641 insertions, 0 deletions

diff --git a/libjava/classpath/java/util/TreeSet.java b/libjava/classpath/java/util/TreeSet.java
new file mode 100644
index 000000000..06f4fa5b3
--- /dev/null
+++ b/libjava/classpath/java/util/TreeSet.java
@@ -0,0 +1,641 @@
+/* TreeSet.java -- a class providing a TreeMap-backed SortedSet
+   Copyright (C) 1999, 2000, 2001, 2004, 2005 Free Software Foundation, Inc.
+
+This file is part of GNU Classpath.
+
+GNU Classpath is free software; you can redistribute it and/or modify
+it under the terms of the GNU General Public License as published by
+the Free Software Foundation; either version 2, or (at your option)
+any later version.
+
+GNU Classpath is distributed in the hope that it will be useful, but
+WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with GNU Classpath; see the file COPYING.  If not, write to the
+Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
+02110-1301 USA.
+
+Linking this library statically or dynamically with other modules is
+making a combined work based on this library.  Thus, the terms and
+conditions of the GNU General Public License cover the whole
+combination.
+
+As a special exception, the copyright holders of this library give you
+permission to link this library with independent modules to produce an
+executable, regardless of the license terms of these independent
+modules, and to copy and distribute the resulting executable under
+terms of your choice, provided that you also meet, for each linked
+independent module, the terms and conditions of the license of that
+module.  An independent module is a module which is not derived from
+or based on this library.  If you modify this library, you may extend
+this exception to your version of the library, but you are not
+obligated to do so.  If you do not wish to do so, delete this
+exception statement from your version. */
+
+
+package java.util;
+
+import java.io.IOException;
+import java.io.ObjectInputStream;
+import java.io.ObjectOutputStream;
+import java.io.Serializable;
+
+/**
+ * This class provides a TreeMap-backed implementation of the SortedSet
+ * interface. The elements will be sorted according to their <i>natural
+ * order</i>, or according to the provided <code>Comparator</code>.<p>
+ *
+ * Most operations are O(log n), but there is so much overhead that this
+ * makes small sets expensive. Note that the ordering must be <i>consistent
+ * with equals</i> to correctly implement the Set interface. If this
+ * condition is violated, the set is still well-behaved, but you may have
+ * suprising results when comparing it to other sets.<p>
+ *
+ * This implementation is not synchronized. If you need to share this between
+ * multiple threads, do something like:<br>
+ * <code>SortedSet s
+ *       = Collections.synchronizedSortedSet(new TreeSet(...));</code><p>
+ *
+ * The iterators are <i>fail-fast</i>, meaning that any structural
+ * modification, except for <code>remove()</code> called on the iterator
+ * itself, cause the iterator to throw a
+ * <code>ConcurrentModificationException</code> rather than exhibit
+ * non-deterministic behavior.
+ *
+ * @author Jon Zeppieri
+ * @author Bryce McKinlay
+ * @author Eric Blake (ebb9@email.byu.edu)
+ * @author Tom Tromey (tromey@redhat.com)
+ * @author Andrew John Hughes (gnu_andrew@member.fsf.org)
+ * @see Collection
+ * @see Set
+ * @see HashSet
+ * @see LinkedHashSet
+ * @see Comparable
+ * @see Comparator
+ * @see Collections#synchronizedSortedSet(SortedSet)
+ * @see TreeMap
+ * @since 1.2
+ * @status updated to 1.6
+ */
+public class TreeSet<T> extends AbstractSet<T>
+  implements NavigableSet<T>, Cloneable, Serializable
+{
+  /**
+   * Compatible with JDK 1.2.
+   */
+  private static final long serialVersionUID = -2479143000061671589L;
+
+  /**
+   * The NavigableMap which backs this Set.
+   */
+  // Not final because of readObject. This will always be one of TreeMap or
+  // TreeMap.SubMap, which both extend AbstractMap.
+  private transient NavigableMap<T, String> map;
+
+  /**
+   * Construct a new TreeSet whose backing TreeMap using the "natural"
+   * ordering of keys. Elements that are not mutually comparable will cause
+   * ClassCastExceptions down the road.
+   *
+   * @see Comparable
+   */
+  public TreeSet()
+  {
+    map = new TreeMap<T, String>();
+  }
+
+  /**
+   * Construct a new TreeSet whose backing TreeMap uses the supplied
+   * Comparator. Elements that are not mutually comparable will cause
+   * ClassCastExceptions down the road.
+   *
+   * @param comparator the Comparator this Set will use
+   */
+  public TreeSet(Comparator<? super T> comparator)
+  {
+    map = new TreeMap<T, String>(comparator);
+  }
+
+  /**
+   * Construct a new TreeSet whose backing TreeMap uses the "natural"
+   * orering of the keys and which contains all of the elements in the
+   * supplied Collection. This runs in n*log(n) time.
+   *
+   * @param collection the new Set will be initialized with all
+   *        of the elements in this Collection
+   * @throws ClassCastException if the elements of the collection are not
+   *         comparable
+   * @throws NullPointerException if the collection is null
+   * @see Comparable
+   */
+  public TreeSet(Collection<? extends T> collection)
+  {
+    map = new TreeMap<T, String>();
+    addAll(collection);
+  }
+
+  /**
+   * Construct a new TreeSet, using the same key ordering as the supplied
+   * SortedSet and containing all of the elements in the supplied SortedSet.
+   * This constructor runs in linear time.
+   *
+   * @param sortedSet the new TreeSet will use this SortedSet's comparator
+   *        and will initialize itself with all its elements
+   * @throws NullPointerException if sortedSet is null
+   */
+  public TreeSet(SortedSet<T> sortedSet)
+  {
+    Iterator<T> itr;
+
+    map = new TreeMap<T, String>
+      ((Comparator<? super T>)sortedSet.comparator());
+    itr = ((SortedSet<T>) sortedSet).iterator();
+    ((TreeMap<T, String>) map).putKeysLinear(itr, sortedSet.size());
+  }
+
+  /**
+   * This private constructor is used to implement the subSet() calls around
+   * a backing TreeMap.SubMap.
+   *
+   * @param backingMap the submap
+   */
+  private TreeSet(NavigableMap<T,String> backingMap)
+  {
+    map = backingMap;
+  }
+
+  /**
+   * Adds the spplied Object to the Set if it is not already in the Set;
+   * returns true if the element is added, false otherwise.
+   *
+   * @param obj the Object to be added to this Set
+   * @throws ClassCastException if the element cannot be compared with objects
+   *         already in the set
+   */
+  public boolean add(T obj)
+  {
+    return map.put(obj, "") == null;
+  }
+
+  /**
+   * Adds all of the elements in the supplied Collection to this TreeSet.
+   *
+   * @param c The collection to add
+   * @return true if the Set is altered, false otherwise
+   * @throws NullPointerException if c is null
+   * @throws ClassCastException if an element in c cannot be compared with
+   *         objects already in the set
+   */
+  public boolean addAll(Collection<? extends T> c)
+  {
+    boolean result = false;
+    int pos = c.size();
+    Iterator<? extends T> itr = c.iterator();
+    while (--pos >= 0)
+      result |= (map.put(itr.next(), "") == null);
+    return result;
+  }
+
+  /**
+   * Removes all elements in this Set.
+   */
+  public void clear()
+  {
+    map.clear();
+  }
+
+  /**
+   * Returns a shallow copy of this Set. The elements are not cloned.
+   *
+   * @return the cloned set
+   */
+  public Object clone()
+  {
+    TreeSet<T> copy = null;
+    try
+      {
+        copy = (TreeSet<T>) super.clone();
+        // Map may be either TreeMap or TreeMap.SubMap, hence the ugly casts.
+        copy.map = (NavigableMap<T, String>) ((AbstractMap<T, String>) map).clone();
+      }
+    catch (CloneNotSupportedException x)
+      {
+        // Impossible result.
+      }
+    return copy;
+  }
+
+  /**
+   * Returns this Set's comparator.
+   *
+   * @return the comparator, or null if the set uses natural ordering
+   */
+  public Comparator<? super T> comparator()
+  {
+    return map.comparator();
+  }
+
+  /**
+   * Returns true if this Set contains the supplied Object, false otherwise.
+   *
+   * @param obj the Object to check for
+   * @return true if it is in the set
+   * @throws ClassCastException if obj cannot be compared with objects
+   *         already in the set
+   */
+  public boolean contains(Object obj)
+  {
+    return map.containsKey(obj);
+  }
+
+  /**
+   * Returns the first (by order) element in this Set.
+   *
+   * @return the first element
+   * @throws NoSuchElementException if the set is empty
+   */
+  public T first()
+  {
+    return map.firstKey();
+  }
+
+  /**
+   * Returns a view of this Set including all elements less than
+   * <code>to</code>. The returned set is backed by the original, so changes
+   * in one appear in the other. The subset will throw an
+   * {@link IllegalArgumentException} for any attempt to access or add an
+   * element beyond the specified cutoff. The returned set does not include
+   * the endpoint; if you want inclusion, pass the successor element or
+   * call {@link #headSet(T,boolean)}.  This call is equivalent to
+   * <code>headSet(to, false)</code>.
+   *
+   * @param to the (exclusive) cutoff point
+   * @return a view of the set less than the cutoff
+   * @throws ClassCastException if <code>to</code> is not compatible with
+   *         the comparator (or is not Comparable, for natural ordering)
+   * @throws NullPointerException if to is null, but the comparator does not
+   *         tolerate null elements
+   */
+  public SortedSet<T> headSet(T to)
+  {
+    return headSet(to, false);
+  }
+
+  /**
+   * Returns a view of this Set including all elements less than
+   * (or equal to, if <code>inclusive</code> is true) <code>to</code>.
+   * The returned set is backed by the original, so changes
+   * in one appear in the other. The subset will throw an
+   * {@link IllegalArgumentException} for any attempt to access or add an
+   * element beyond the specified cutoff.
+   *
+   * @param to the cutoff point
+   * @param inclusive true if <code>to</code> should be included.
+   * @return a view of the set for the specified range.
+   * @throws ClassCastException if <code>to</code> is not compatible with
+   *         the comparator (or is not Comparable, for natural ordering)
+   * @throws NullPointerException if to is null, but the comparator does not
+   *         tolerate null elements
+   */
+  public NavigableSet<T> headSet(T to, boolean inclusive)
+  {
+    return new TreeSet<T>(map.headMap(to, inclusive));
+  }
+
+  /**
+   * Returns true if this Set has size 0, false otherwise.
+   *
+   * @return true if the set is empty
+   */
+  public boolean isEmpty()
+  {
+    return map.isEmpty();
+  }
+
+  /**
+   * Returns in Iterator over the elements in this TreeSet, which traverses
+   * in ascending order.
+   *
+   * @return an iterator
+   */
+  public Iterator<T> iterator()
+  {
+    return map.keySet().iterator();
+  }
+
+  /**
+   * Returns the last (by order) element in this Set.
+   *
+   * @return the last element
+   * @throws NoSuchElementException if the set is empty
+   */
+  public T last()
+  {
+    return map.lastKey();
+  }
+
+  /**
+   * If the supplied Object is in this Set, it is removed, and true is
+   * returned; otherwise, false is returned.
+   *
+   * @param obj the Object to remove from this Set
+   * @return true if the set was modified
+   * @throws ClassCastException if obj cannot be compared to set elements
+   */
+  public boolean remove(Object obj)
+  {
+    return map.remove(obj) != null;
+  }
+
+  /**
+   * Returns the number of elements in this Set
+   *
+   * @return the set size
+   */
+  public int size()
+  {
+    return map.size();
+  }
+
+  /**
+   * Returns a view of this Set including all elements greater or equal to
+   * <code>from</code> and less than <code>to</code> (a half-open interval).
+   * The returned set is backed by the original, so changes in one appear in
+   * the other. The subset will throw an {@link IllegalArgumentException}
+   * for any attempt to access or add an element beyond the specified cutoffs.
+   * The returned set includes the low endpoint but not the high; if you want
+   * to reverse this behavior on either end, pass in the successor element
+   * or call {@link #subSet(T,boolean,T,boolean)}.  This is equivalent to
+   * calling <code>subSet(from,true,to,false)</code>.
+   *
+   * @param from the (inclusive) low cutoff point
+   * @param to the (exclusive) high cutoff point
+   * @return a view of the set between the cutoffs
+   * @throws ClassCastException if either cutoff is not compatible with
+   *         the comparator (or is not Comparable, for natural ordering)
+   * @throws NullPointerException if from or to is null, but the comparator
+   *         does not tolerate null elements
+   * @throws IllegalArgumentException if from is greater than to
+   */
+  public SortedSet<T> subSet(T from, T to)
+  {
+    return subSet(from, true, to, false);
+  }
+
+  /**
+   * Returns a view of this Set including all elements greater than (or equal to,
+   * if <code>fromInclusive</code> is true</code> <code>from</code> and less than
+   * (or equal to, if <code>toInclusive</code> is true) <code>to</code>.
+   * The returned set is backed by the original, so changes in one appear in
+   * the other. The subset will throw an {@link IllegalArgumentException}
+   * for any attempt to access or add an element beyond the specified cutoffs.
+   *
+   * @param from the low cutoff point
+   * @param fromInclusive true if <code>from</code> should be included.
+   * @param to the high cutoff point
+   * @param toInclusive true if <code>to</code> should be included.
+   * @return a view of the set for the specified range.
+   * @throws ClassCastException if either cutoff is not compatible with
+   *         the comparator (or is not Comparable, for natural ordering)
+   * @throws NullPointerException if from or to is null, but the comparator
+   *         does not tolerate null elements
+   * @throws IllegalArgumentException if from is greater than to
+   */
+  public NavigableSet<T> subSet(T from, boolean fromInclusive,
+                                T to, boolean toInclusive)
+  {
+    return new TreeSet<T>(map.subMap(from, fromInclusive,
+                                     to, toInclusive));
+  }
+
+  /**
+   * Returns a view of this Set including all elements greater or equal to
+   * <code>from</code>. The returned set is backed by the original, so
+   * changes in one appear in the other. The subset will throw an
+   * {@link IllegalArgumentException} for any attempt to access or add an
+   * element beyond the specified cutoff. The returned set includes the
+   * endpoint; if you want to exclude it, pass in the successor element
+   * or call {@link #tailSet(T,boolean)}.  This is equivalent to calling
+   * <code>tailSet(from, true)</code>.
+   *
+   * @param from the (inclusive) low cutoff point
+   * @return a view of the set above the cutoff
+   * @throws ClassCastException if <code>from</code> is not compatible with
+   *         the comparator (or is not Comparable, for natural ordering)
+   * @throws NullPointerException if from is null, but the comparator
+   *         does not tolerate null elements
+   */
+  public SortedSet<T> tailSet(T from)
+  {
+    return tailSet(from, true);
+  }
+
+  /**
+   * Returns a view of this Set including all elements greater (or equal to,
+   * if <code>inclusive</code> is true) <code>from</code>. The returned set
+   * is backed by the original, so changes in one appear in the other. The
+   * subset will throw an {@link IllegalArgumentException} for any attempt
+   * to access or add an element beyond the specified cutoff.
+   *
+   * @param from the low cutoff point.
+   * @param inclusive true if <code>from</code> should be included.
+   * @return a view of the set for the specified range.
+   * @throws ClassCastException if <code>from</code> is not compatible with
+   *         the comparator (or is not Comparable, for natural ordering)
+   * @throws NullPointerException if from is null, but the comparator
+   *         does not tolerate null elements
+   */
+  public NavigableSet<T> tailSet(T from, boolean inclusive)
+  {
+    return new TreeSet<T>(map.tailMap(from, inclusive));
+  }
+
+  /**
+   * Serializes this object to the given stream.
+   *
+   * @param s the stream to write to
+   * @throws IOException if the underlying stream fails
+   * @serialData the <i>comparator</i> (Object), followed by the set size
+   *             (int), the the elements in sorted order (Object)
+   */
+  private void writeObject(ObjectOutputStream s) throws IOException
+  {
+    s.defaultWriteObject();
+    Iterator<T> itr = map.keySet().iterator();
+    int pos = map.size();
+    s.writeObject(map.comparator());
+    s.writeInt(pos);
+    while (--pos >= 0)
+      s.writeObject(itr.next());
+  }
+
+  /**
+   * Deserializes this object from the given stream.
+   *
+   * @param s the stream to read from
+   * @throws ClassNotFoundException if the underlying stream fails
+   * @throws IOException if the underlying stream fails
+   * @serialData the <i>comparator</i> (Object), followed by the set size
+   *             (int), the the elements in sorted order (Object)
+   */
+  private void readObject(ObjectInputStream s)
+    throws IOException, ClassNotFoundException
+  {
+    s.defaultReadObject();
+    Comparator<? super T> comparator = (Comparator<? super T>) s.readObject();
+    int size = s.readInt();
+    map = new TreeMap<T, String>(comparator);
+    ((TreeMap<T, String>) map).putFromObjStream(s, size, false);
+  }
+
+  /**
+   * Returns the least or lowest element in the set greater than or
+   * equal to the given element, or <code>null</code> if there is
+   * no such element.
+   *
+   * @param e the element relative to the returned element.
+   * @return the least element greater than or equal
+   *         to the given element, or <code>null</code> if there is
+   *         no such element.
+   * @throws ClassCastException if the specified element can not
+   *                            be compared with those in the map.
+   * @throws NullPointerException if the element is <code>null</code>
+   *                              and this set either uses natural
+   *                              ordering or a comparator that does
+   *                              not permit null elements.
+   * @since 1.6
+   */
+  public T ceiling(T e)
+  {
+    return map.ceilingKey(e);
+  }
+
+  /**
+   * Returns an iterator over the elements of this set in descending
+   * order.  This is equivalent to calling
+   * <code>descendingSet().iterator()</code>.
+   *
+   * @return an iterator over the elements in descending order.
+   * @since 1.6
+   */
+  public Iterator<T> descendingIterator()
+  {
+    return descendingSet().iterator();
+  }
+
+  /**
+   * Returns a view of the set in reverse order.  The descending set
+   * is backed by the original set, so that changes affect both sets.
+   * Any changes occurring to either set while an iteration is taking
+   * place (with the exception of a {@link Iterator#remove()} operation)
+   * result in undefined behaviour from the iteration.  The ordering
+   * of the descending set is the same as for a set with a
+   * {@link Comparator} given by {@link Collections#reverseOrder()},
+   * and calling {@link #descendingSet()} on the descending set itself
+   * results in a view equivalent to the original set.
+   *
+   * @return a reverse order view of the set.
+   * @since 1.6
+   */
+  public NavigableSet<T> descendingSet()
+  {
+    return map.descendingKeySet();
+  }
+
+  /**
+   * Returns the greatest or highest element in the set less than or
+   * equal to the given element, or <code>null</code> if there is
+   * no such element.
+   *
+   * @param e the element relative to the returned element.
+   * @return the greatest element less than or equal
+   *         to the given element, or <code>null</code> if there is
+   *         no such element.
+   * @throws ClassCastException if the specified element can not
+   *                            be compared with those in the map.
+   * @throws NullPointerException if the element is <code>null</code>
+   *                              and this set either uses natural
+   *                              ordering or a comparator that does
+   *                              not permit null elements.
+   * @since 1.6
+   */
+  public T floor(T e)
+  {
+    return map.floorKey(e);
+  }
+
+  /**
+   * Returns the least or lowest element in the set strictly greater
+   * than the given element, or <code>null</code> if there is
+   * no such element.
+   *
+   * @param e the element relative to the returned element.
+   * @return the least element greater than
+   *         the given element, or <code>null</code> if there is
+   *         no such element.
+   * @throws ClassCastException if the specified element can not
+   *                            be compared with those in the map.
+   * @throws NullPointerException if the element is <code>null</code>
+   *                              and this set either uses natural
+   *                              ordering or a comparator that does
+   *                              not permit null elements.
+   * @since 1.6
+   */
+  public T higher(T e)
+  {
+    return map.higherKey(e);
+  }
+
+  /**
+   * Returns the greatest or highest element in the set strictly less
+   * than the given element, or <code>null</code> if there is
+   * no such element.
+   *
+   * @param e the element relative to the returned element.
+   * @return the greatest element less than
+   *         the given element, or <code>null</code> if there is
+   *         no such element.
+   * @throws ClassCastException if the specified element can not
+   *                            be compared with those in the map.
+   * @throws NullPointerException if the element is <code>null</code>
+   *                              and this set either uses natural
+   *                              ordering or a comparator that does
+   *                              not permit null elements.
+   * @since 1.6
+   */
+  public T lower(T e)
+  {
+    return map.lowerKey(e);
+  }
+
+  /**
+   * Removes and returns the least or lowest element in the set,
+   * or <code>null</code> if the map is empty.
+   *
+   * @return the removed first element, or <code>null</code> if the
+   *         map is empty.
+   * @since 1.6
+   */
+  public T pollFirst()
+  {
+    return map.pollFirstEntry().getKey();
+  }
+
+  /**
+   * Removes and returns the greatest or highest element in the set,
+   * or <code>null</code> if the map is empty.
+   *
+   * @return the removed last element, or <code>null</code> if the
+   *         map is empty.
+   * @since 1.6
+   */
+  public T pollLast()
+  {
+    return map.pollLastEntry().getKey();
+  }
+
+}