KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > edu > rice > cs > util > OrderedHashSet


1 /*BEGIN_COPYRIGHT_BLOCK
2  *
3  * This file is part of DrJava. Download the current version of this project from http://www.drjava.org/
4  * or http://sourceforge.net/projects/drjava/
5  *
6  * DrJava Open Source License
7  *
8  * Copyright (C) 2001-2006 JavaPLT group at Rice University (javaplt@rice.edu). All rights reserved.
9  *
10  * Developed by: Java Programming Languages Team, Rice University, http://www.cs.rice.edu/~javaplt/
11  *
12  * Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated
13  * documentation files (the "Software"), to deal with the Software without restriction, including without limitation
14  * the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and
15  * to permit persons to whom the Software is furnished to do so, subject to the following conditions:
16  *
17  * - Redistributions of source code must retain the above copyright notice, this list of conditions and the
18  * following disclaimers.
19  * - Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the
20  * following disclaimers in the documentation and/or other materials provided with the distribution.
21  * - Neither the names of DrJava, the JavaPLT, Rice University, nor the names of its contributors may be used to
22  * endorse or promote products derived from this Software without specific prior written permission.
23  * - Products derived from this software may not be called "DrJava" nor use the term "DrJava" as part of their
24  * names without prior written permission from the JavaPLT group. For permission, write to javaplt@rice.edu.
25  *
26  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO
27  * THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
28  * CONTRIBUTORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF
29  * CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
30  * WITH THE SOFTWARE.
31  *
32  *END_COPYRIGHT_BLOCK*/
33
34 package edu.rice.cs.util;
35 import java.util.*;
36
37 /** A set class patterned after HashSet except that the construction order for elements is scrupulously maintained
38  * for the sake of supporting obvious list operations based on construction order (addition to the set). */
39
40 public class OrderedHashSet<Type> implements Collection<Type> {
41   private HashSet<Type> elements = new HashSet<Type>();
42   private ArrayList<Type> order = new ArrayList<Type>();
43   
44   /** Relying on standard 0-ary constructor */
45   
46   public boolean add(Type elt) {
47     boolean validAdd = elements.add(elt);
48     if (validAdd) order.add(elt);
49     return validAdd;
50   }
51   
52   public boolean addAll(Collection<? extends Type> c) {
53     throw new UnsupportedOperationException JavaDoc("OrderedHashSet does not support this operation");
54   }
55   
56   public void clear() {
57     elements.clear();
58     order.clear();
59   }
60   
61   public boolean contains(Object JavaDoc elt) { return elements.contains(elt); }
62    
63   public boolean containsAll(Collection<?> c) {
64     throw new UnsupportedOperationException JavaDoc("OrderedHashSet does not support this operation");
65   }
66   
67   public boolean equals(Object JavaDoc o) {
68     if ((o == null) || o.getClass() != getClass()) return false;
69     return order.equals(elements());
70   }
71   
72   public int hashCode() { return order.hashCode(); }
73   
74   public boolean isEmpty() { return order.isEmpty(); }
75   
76   public Type get(int i) { return order.get(i); }
77   
78   public Iterator<Type> iterator() { return new OHMIterator(); }
79   
80   /** @throws {@link IndexOutOfBoundsException */
81   public Type remove(int i) {
82     Type elt = order.remove(i); // O(n) operation
83 elements.remove(elt);
84     return elt;
85   }
86   
87   public boolean remove(Object JavaDoc elt) {
88     elements.remove(elt);
89     return order.remove(elt); // O(n) operation
90 }
91   
92   public boolean removeAll(Collection<?> elts) {
93     throw new UnsupportedOperationException JavaDoc("OrderedHashSet does not support this operation");
94   }
95   
96   public boolean retainAll(Collection<?> elts) {
97     throw new UnsupportedOperationException JavaDoc("OrderedHashSet does not support this operation");
98   }
99   
100   public int size() { return order.size(); }
101   
102   public Object JavaDoc[] toArray() { return order.toArray(); }
103   
104   public <T> T[] toArray(T[] a) { return order.toArray(a); }
105  
106   public Collection<Type> elements() { return order; }
107   
108   public String JavaDoc toString() { return order.toString(); }
109   
110     /** Iterator class for OrderedHashSet */
111   class OHMIterator implements Iterator<Type> {
112     
113     Iterator<Type> it = order.iterator();
114     
115     /** Cached values of last elt visited */
116     Type lastElt = null;
117
118     public boolean hasNext() { return it.hasNext(); }
119     
120     public Type next() {
121       lastElt = it.next();
122       return lastElt;
123     }
124     
125     /** Removes last element returned by next(); throws IllegalStateException if no such element */
126     public void remove() {
127       it.remove(); /* throws exception if lastElt is null */
128       elements.remove(lastElt);
129     }
130   }
131 }
132
Popular Tags