001: /*
002: * FindBugs - Find Bugs in Java programs
003: * Copyright (C) 2006, University of Maryland
004: *
005: * This library is free software; you can redistribute it and/or
006: * modify it under the terms of the GNU Lesser General Public
007: * License as published by the Free Software Foundation; either
008: * version 2.1 of the License, or (at your option) any later version.
009: *
010: * This library is distributed in the hope that it will be useful,
011: * but WITHOUT ANY WARRANTY; without even the implied warranty of
012: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
013: * Lesser General Public License for more details.
014: *
015: * You should have received a copy of the GNU Lesser General Public
016: * License along with this library; if not, write to the Free Software
017: * Foundation, Inc., 59 Temple Place, Suite 330, Boston MA 02111-1307, USA
018: */
019:
020: package edu.umd.cs.findbugs.gui2;
021:
022: import java.util.ArrayList;
023: import java.util.Collection;
024: import java.util.HashMap;
025: import java.util.Iterator;
026: import java.util.ListIterator;
027: import java.util.Map;
028: import java.util.NoSuchElementException;
029: import java.util.Set;
030: import java.util.TreeSet;
031:
032: /**
033: * A list with ArrayList's fast add and set operations,
034: * and HashMap's fast contains and indexOf() operations. The
035: * tradeoff is an O(n) remove.
036: */
037: public class HashList<E> extends ArrayList<E> {
038: private static final long serialVersionUID = 6710532766397389391L;
039:
040: // Map from hashcodes to sets of indices in the ArrayList
041: private HashMap<Integer, TreeSet<Integer>> map = new HashMap<Integer, TreeSet<Integer>>();
042:
043: public HashList() {
044: }
045:
046: public HashList(Collection<? extends E> c) {
047: addAll(c);
048: }
049:
050: @Override
051: public boolean add(E o) {
052: add(size(), o);
053: return true;
054: }
055:
056: @Override
057: public void add(int index, E element) {
058: addToMap(element, index);
059: super .add(index, element);
060: }
061:
062: @Override
063: public boolean addAll(Collection<? extends E> c) {
064: for (E i : c)
065: add(i);
066: return (c.size() > 0);
067: }
068:
069: @Override
070: public boolean addAll(int index, Collection<? extends E> c) {
071: int offset = 0;
072: for (E i : c) {
073: add(index + offset, i);
074: offset++;
075: }
076: return (c.size() > 0);
077: }
078:
079: @Override
080: public void clear() {
081: super .clear();
082: map.clear();
083: }
084:
085: @Override
086: public boolean contains(Object elem) {
087: return (indexOf(elem) != -1);
088: }
089:
090: @Override
091: public boolean containsAll(Collection<?> c) {
092: for (Object i : c)
093: if (!contains(i))
094: return false;
095: return true;
096: }
097:
098: @Override
099: public int indexOf(Object elem) {
100: Set<Integer> s = map.get(elem.hashCode());
101: if (s == null)
102: return -1;
103: for (Integer i : s)
104: if (get(i).equals(elem))
105: return i;
106: return -1;
107: }
108:
109: @Override
110: public int lastIndexOf(Object elem) {
111: int result = -1;
112: for (Integer i : map.get(elem.hashCode()))
113: if (get(i).equals(elem))
114: result = i;
115: return result;
116: }
117:
118: @Override
119: public E remove(int index) {
120: E result = super .remove(index);
121: removeFromMap(result, index);
122: return result;
123: }
124:
125: @Override
126: public boolean remove(Object o) {
127: if (super .remove(o)) {
128: removeFromMap((E) o, indexOf(o));
129: return true;
130: } else
131: return false;
132: }
133:
134: @Override
135: public boolean removeAll(Collection<?> c) {
136: boolean result = false;
137: for (Object i : c)
138: result |= remove(i);
139: return result;
140: }
141:
142: @Override
143: public boolean retainAll(Collection<?> c) {
144: boolean result = false;
145: for (Iterator<E> iterator = this .iterator(); iterator.hasNext();) {
146: E i = iterator.next();
147: if (!c.contains(i)) {
148: iterator.remove();
149: result = true;
150:
151: }
152: }
153:
154: return result;
155: }
156:
157: @Override
158: protected void removeRange(int fromIndex, int toIndex) {
159: throw new UnsupportedOperationException();
160: }
161:
162: @Override
163: public E set(int index, E element) {
164: E result = get(index);
165:
166: if (map.get(result.hashCode()).size() == 1)
167: map.remove(result.hashCode());
168: else
169: map.get(result.hashCode()).remove(index);
170:
171: if (!map.containsKey(element.hashCode()))
172: map.put(element.hashCode(), new TreeSet<Integer>());
173: map.get(element.hashCode()).add(index);
174:
175: super .set(index, element);
176: return result;
177: }
178:
179: private void addToMap(E o, int index) {
180: if (index < size())
181: for (Map.Entry<Integer, TreeSet<Integer>> i : map
182: .entrySet()) {
183: TreeSet<Integer> newSet = new TreeSet<Integer>();
184: for (Integer j : i.getValue())
185: if (j >= index)
186: newSet.add(j + 1);
187: else
188: newSet.add(j);
189: i.setValue(newSet);
190: }
191:
192: if (!map.containsKey(o.hashCode()))
193: map.put(o.hashCode(), new TreeSet<Integer>());
194: map.get(o.hashCode()).add(index);
195: }
196:
197: private void removeFromMap(E o, int index) {
198: if (map.get(o.hashCode()).size() == 1)
199: map.remove(o.hashCode());
200: else
201: map.get(o.hashCode()).remove(index);
202:
203: if (index < size() - 1)
204: for (Map.Entry<Integer, TreeSet<Integer>> i : map
205: .entrySet()) {
206: TreeSet<Integer> newSet = new TreeSet<Integer>();
207: for (Integer j : i.getValue())
208: if (j > index)
209: newSet.add(j - 1);
210: i.setValue(newSet);
211: }
212: }
213:
214: @Override
215: public ListIterator<E> listIterator() {
216: return new ListIterator<E>() {
217: int cursor = -1;
218: boolean removable = false;
219: boolean removed = false;
220:
221: public void add(E o) {
222: HashList.this .add(cursor++, o);
223: removable = false;
224: }
225:
226: public boolean hasNext() {
227: return (cursor < size() - 1);
228: }
229:
230: public boolean hasPrevious() {
231: return (cursor > 0);
232: }
233:
234: public E next() {
235: if (!hasNext())
236: throw new NoSuchElementException();
237:
238: if (removed) {
239: removable = true;
240: removed = false;
241: return get(cursor);
242: } else {
243: removable = true;
244: removed = false;
245: return get(++cursor);
246: }
247: }
248:
249: public int nextIndex() {
250: return (removed ? cursor : cursor + 1);
251: }
252:
253: public E previous() {
254: if (!hasPrevious())
255: throw new NoSuchElementException();
256:
257: removable = true;
258: removed = false;
259: return get(--cursor);
260: }
261:
262: public int previousIndex() {
263: if (hasPrevious())
264: return cursor - 1;
265: else
266: return -1;
267: }
268:
269: public void remove() {
270: if (!removable)
271: throw new IllegalStateException(
272: "next() and previous() have not been called since the last call to remove()");
273: removable = false;
274: removed = true;
275: HashList.this .remove(cursor);
276: }
277:
278: public void set(E o) {
279: HashList.this.set(cursor, o);
280: }
281: };
282: }
283: }
|