001: /*BEGIN_COPYRIGHT_BLOCK
002: *
003: * Copyright (c) 2001-2007, JavaPLT group at Rice University (javaplt@rice.edu)
004: * All rights reserved.
005: *
006: * Redistribution and use in source and binary forms, with or without
007: * modification, are permitted provided that the following conditions are met:
008: * * Redistributions of source code must retain the above copyright
009: * notice, this list of conditions and the following disclaimer.
010: * * Redistributions in binary form must reproduce the above copyright
011: * notice, this list of conditions and the following disclaimer in the
012: * documentation and/or other materials provided with the distribution.
013: * * Neither the names of DrJava, the JavaPLT group, Rice University, nor the
014: * names of its contributors may be used to endorse or promote products
015: * derived from this software without specific prior written permission.
016: *
017: * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
018: * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
019: * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
020: * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
021: * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
022: * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
023: * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
024: * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
025: * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
026: * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
027: * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
028: *
029: * This software is Open Source Initiative approved Open Source Software.
030: * Open Source Initative Approved is a trademark of the Open Source Initiative.
031: *
032: * This file is part of DrJava. Download the current version of this project
033: * from http://www.drjava.org/ or http://sourceforge.net/projects/drjava/
034: *
035: * END_COPYRIGHT_BLOCK*/
036:
037: package edu.rice.cs.util;
038:
039: import java.util.*;
040:
041: /** A set class patterned after HashSet except that the construction order for elements is scrupulously maintained
042: * for the sake of supporting obvious list operations based on construction order (addition to the set). */
043:
044: public class OrderedHashSet<Type> implements Collection<Type> {
045: private HashSet<Type> elements = new HashSet<Type>();
046: private ArrayList<Type> order = new ArrayList<Type>();
047:
048: /** Relying on standard 0-ary constructor */
049:
050: public boolean add(Type elt) {
051: boolean validAdd = elements.add(elt);
052: if (validAdd)
053: order.add(elt);
054: return validAdd;
055: }
056:
057: public boolean addAll(Collection<? extends Type> c) {
058: throw new UnsupportedOperationException(
059: "OrderedHashSet does not support this operation");
060: }
061:
062: public void clear() {
063: elements.clear();
064: order.clear();
065: }
066:
067: public boolean contains(Object elt) {
068: return elements.contains(elt);
069: }
070:
071: public boolean containsAll(Collection<?> c) {
072: throw new UnsupportedOperationException(
073: "OrderedHashSet does not support this operation");
074: }
075:
076: public boolean equals(Object o) {
077: if ((o == null) || o.getClass() != getClass())
078: return false;
079: return order.equals(elements());
080: }
081:
082: public int hashCode() {
083: return order.hashCode();
084: }
085:
086: public boolean isEmpty() {
087: return order.isEmpty();
088: }
089:
090: public Type get(int i) {
091: return order.get(i);
092: }
093:
094: public Iterator<Type> iterator() {
095: return new OHMIterator();
096: }
097:
098: /** @throws {@link IndexOutOfBoundsException */
099: public Type remove(int i) {
100: Type elt = order.remove(i); // O(n) operation
101: elements.remove(elt);
102: return elt;
103: }
104:
105: public boolean remove(Object elt) {
106: elements.remove(elt);
107: return order.remove(elt); // O(n) operation
108: }
109:
110: public boolean removeAll(Collection<?> elts) {
111: throw new UnsupportedOperationException(
112: "OrderedHashSet does not support this operation");
113: }
114:
115: public boolean retainAll(Collection<?> elts) {
116: throw new UnsupportedOperationException(
117: "OrderedHashSet does not support this operation");
118: }
119:
120: public int size() {
121: return order.size();
122: }
123:
124: public Object[] toArray() {
125: return order.toArray();
126: }
127:
128: public <T> T[] toArray(T[] a) {
129: return order.toArray(a);
130: }
131:
132: public Collection<Type> elements() {
133: return order;
134: }
135:
136: public String toString() {
137: return order.toString();
138: }
139:
140: /** Iterator class for OrderedHashSet */
141: class OHMIterator implements Iterator<Type> {
142:
143: Iterator<Type> it = order.iterator();
144:
145: /** Cached values of last elt visited */
146: Type lastElt = null;
147:
148: public boolean hasNext() {
149: return it.hasNext();
150: }
151:
152: public Type next() {
153: lastElt = it.next();
154: return lastElt;
155: }
156:
157: /** Removes last element returned by next(); throws IllegalStateException if no such element */
158: public void remove() {
159: it.remove(); /* throws exception if lastElt is null */
160: elements.remove(lastElt);
161: }
162: }
163: }
|