001    /* AbstractSet.java -- Abstract implementation of most of Set
002       Copyright (C) 1998, 2000, 2001, 2004, 2005
003       Free Software Foundation, Inc.
004    
005    This file is part of GNU Classpath.
006    
007    GNU Classpath is free software; you can redistribute it and/or modify
008    it under the terms of the GNU General Public License as published by
009    the Free Software Foundation; either version 2, or (at your option)
010    any later version.
011    
012    GNU Classpath is distributed in the hope that it will be useful, but
013    WITHOUT ANY WARRANTY; without even the implied warranty of
014    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
015    General Public License for more details.
016    
017    You should have received a copy of the GNU General Public License
018    along with GNU Classpath; see the file COPYING.  If not, write to the
019    Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
020    02110-1301 USA.
021    
022    Linking this library statically or dynamically with other modules is
023    making a combined work based on this library.  Thus, the terms and
024    conditions of the GNU General Public License cover the whole
025    combination.
026    
027    As a special exception, the copyright holders of this library give you
028    permission to link this library with independent modules to produce an
029    executable, regardless of the license terms of these independent
030    modules, and to copy and distribute the resulting executable under
031    terms of your choice, provided that you also meet, for each linked
032    independent module, the terms and conditions of the license of that
033    module.  An independent module is a module which is not derived from
034    or based on this library.  If you modify this library, you may extend
035    this exception to your version of the library, but you are not
036    obligated to do so.  If you do not wish to do so, delete this
037    exception statement from your version. */
038    
039    
040    package java.util;
041    
042    /**
043     * An abstract implementation of Set to make it easier to create your own
044     * implementations. In order to create a Set, subclass AbstractSet and
045     * implement the same methods that are required for AbstractCollection
046     * (although these methods must of course meet the requirements that Set puts
047     * on them - specifically, no element may be in the set more than once). This
048     * class simply provides implementations of equals() and hashCode() to fulfil
049     * the requirements placed on them by the Set interface.
050     *
051     * @author Original author unknown
052     * @author Eric Blake (ebb9@email.byu.edu)
053     * @see Collection
054     * @see AbstractCollection
055     * @see Set
056     * @see HashSet
057     * @see TreeSet
058     * @see LinkedHashSet
059     * @since 1.2
060     * @status updated to 1.4
061     */
062    public abstract class AbstractSet<E>
063      extends AbstractCollection<E>
064      implements Set<E>
065    {
066      /**
067       * The main constructor, for use by subclasses.
068       */
069      protected AbstractSet()
070      {
071      }
072    
073      /**
074       * Tests whether the given object is equal to this Set. This implementation
075       * first checks whether this set <em>is</em> the given object, and returns
076       * true if so. Otherwise, if o is a Set and is the same size as this one, it
077       * returns the result of calling containsAll on the given Set. Otherwise, it
078       * returns false.
079       *
080       * @param o the Object to be tested for equality with this Set
081       * @return true if the given object is equal to this Set
082       */
083      public boolean equals(Object o)
084      {
085        return (o == this
086                || (o instanceof Set && ((Set) o).size() == size()
087                    && containsAll((Collection) o)));
088      }
089    
090      /**
091       * Returns a hash code for this Set. The hash code of a Set is the sum of the
092       * hash codes of all its elements, except that the hash code of null is
093       * defined to be zero. This implementation obtains an Iterator over the Set,
094       * and sums the results.
095       *
096       * @return a hash code for this Set
097       */
098      public int hashCode()
099      {
100        Iterator<E> itr = iterator();
101        int hash = 0;
102        int pos = size();
103        while (--pos >= 0)
104          hash += hashCode(itr.next());
105        return hash;
106      }
107    
108      /**
109       * Removes from this set all elements in the given collection (optional
110       * operation). This implementation uses <code>size()</code> to determine
111       * the smaller collection.  Then, if this set is smaller, it iterates
112       * over the set, calling Iterator.remove if the collection contains
113       * the element.  If this set is larger, it iterates over the collection,
114       * calling Set.remove for all elements in the collection. Note that
115       * this operation will fail if a remove methods is not supported.
116       *
117       * @param c the collection of elements to remove
118       * @return true if the set was modified as a result
119       * @throws UnsupportedOperationException if remove is not supported
120       * @throws NullPointerException if the collection is null
121       * @see AbstractCollection#remove(Object)
122       * @see Collection#contains(Object)
123       * @see Iterator#remove()
124       */
125      public boolean removeAll(Collection<?> c)
126      {
127        int oldsize = size();
128        int count = c.size();
129        if (oldsize < count)
130          {
131            Iterator<E> i;
132            for (i = iterator(), count = oldsize; count > 0; count--)
133              {
134                if (c.contains(i.next()))
135                  i.remove();
136              }
137          }
138        else
139          {
140            Iterator<?> i;
141            for (i = c.iterator(); count > 0; count--)
142              remove(i.next());
143          }
144        return oldsize != size();
145      }
146    }