KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > edu > umd > cs > findbugs > gui2 > HashList


1 /*
2  * FindBugs - Find Bugs in Java programs
3  * Copyright (C) 2006, University of Maryland
4  *
5  * This library is free software; you can redistribute it and/or
6  * modify it under the terms of the GNU Lesser General Public
7  * License as published by the Free Software Foundation; either
8  * version 2.1 of the License, or (at your option) any later version.
9  *
10  * This library is distributed in the hope that it will be useful,
11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13  * Lesser General Public License for more details.
14  *
15  * You should have received a copy of the GNU Lesser General Public
16  * License along with this library; if not, write to the Free Software
17  * Foundation, Inc., 59 Temple Place, Suite 330, Boston MA 02111-1307, USA
18  */

19
20 package edu.umd.cs.findbugs.gui2;
21
22 import java.util.AbstractList JavaDoc;
23 import java.util.ArrayList JavaDoc;
24 import java.util.Arrays JavaDoc;
25 import java.util.Collection JavaDoc;
26 import java.util.Collections JavaDoc;
27 import java.util.HashMap JavaDoc;
28 import java.util.ListIterator JavaDoc;
29 import java.util.Map JavaDoc;
30 import java.util.NoSuchElementException JavaDoc;
31 import java.util.Set JavaDoc;
32 import java.util.TreeSet JavaDoc;
33
34 /**
35  * A list with ArrayList's fast add and set operations,
36  * and HashMap's fast contains and indexOf() operations. The
37  * tradeoff is an O(n) remove.
38  */

39 public class HashList<E> extends ArrayList JavaDoc<E>
40 {
41     private static final long serialVersionUID = 6710532766397389391L;
42
43     // Map from hashcodes to sets of indices in the ArrayList
44
private HashMap JavaDoc<Integer JavaDoc, TreeSet JavaDoc<Integer JavaDoc>> map = new HashMap JavaDoc<Integer JavaDoc, TreeSet JavaDoc<Integer JavaDoc>>();
45     
46     public HashList()
47     {
48         super();
49     }
50     
51     public HashList(Collection JavaDoc<? extends E> c)
52     {
53         super();
54         addAll(c);
55     }
56
57     @Override JavaDoc
58     public boolean add(E o)
59     {
60         add(size(), o);
61         return true;
62     }
63     
64     @Override JavaDoc
65     public void add(int index, E element)
66     {
67         addToMap(element, index);
68         super.add(index, element);
69     }
70     
71     @Override JavaDoc
72     public boolean addAll(Collection JavaDoc<? extends E> c)
73     {
74         for (E i : c)
75             add(i);
76         return (c.size() > 0);
77     }
78     
79     @Override JavaDoc
80     public boolean addAll(int index, Collection JavaDoc<? extends E> c)
81     {
82         int offset = 0;
83         for (E i : c)
84         {
85             add(index + offset, i);
86             offset++;
87         }
88         return (c.size() > 0);
89     }
90     
91     @Override JavaDoc
92     public void clear()
93     {
94         super.clear();
95         map.clear();
96     }
97     
98     @Override JavaDoc
99     public boolean contains(Object JavaDoc elem)
100     {
101         return (indexOf(elem) != -1);
102     }
103     
104     @Override JavaDoc
105     public boolean containsAll(Collection JavaDoc<?> c)
106     {
107         for (Object JavaDoc i : c)
108             if (!contains(i))
109                 return false;
110         return true;
111     }
112     
113     @Override JavaDoc
114     public int indexOf(Object JavaDoc elem)
115     {
116         Set JavaDoc<Integer JavaDoc> s=map.get(elem.hashCode());
117         if (s==null)
118             return -1;
119         for (Integer JavaDoc i : s)
120             if (get(i).equals(elem))
121                 return i;
122         return -1;
123     }
124     
125     @Override JavaDoc
126     public int lastIndexOf(Object JavaDoc elem)
127     {
128         int result = -1;
129         for (Integer JavaDoc i : map.get(elem.hashCode()))
130             if (get(i).equals(elem))
131                 result = i;
132         return result;
133     }
134     
135     @Override JavaDoc
136     public E remove(int index)
137     {
138         E result = super.remove(index);
139         removeFromMap(result, index);
140         return result;
141     }
142     
143     @Override JavaDoc
144     public boolean remove(Object JavaDoc o)
145     {
146         if (super.remove(o))
147         {
148             removeFromMap((E) o, indexOf(o));
149             return true;
150         }
151         else
152             return false;
153     }
154     
155     @Override JavaDoc
156     public boolean removeAll(Collection JavaDoc<?> c)
157     {
158         boolean result = false;
159         for (Object JavaDoc i : c)
160             result |= remove(i);
161         return result;
162     }
163     
164     @Override JavaDoc
165     public boolean retainAll(Collection JavaDoc<?> c)
166     {
167         boolean result = false;
168         for (E i : this)
169             if (!c.contains(i))
170             {
171                 result |= remove(i);
172             }
173         
174         return result;
175     }
176     
177     @Override JavaDoc
178     protected void removeRange(int fromIndex, int toIndex)
179     {
180         throw new UnsupportedOperationException JavaDoc();
181     }
182     
183     @Override JavaDoc
184     public E set(int index, E element)
185     {
186         E result = get(index);
187         
188         if (map.get(result.hashCode()).size() == 1)
189             map.remove(result.hashCode());
190         else
191             map.get(result.hashCode()).remove(index);
192         
193         if (!map.containsKey(element.hashCode()))
194             map.put(element.hashCode(), new TreeSet JavaDoc<Integer JavaDoc>());
195         map.get(element.hashCode()).add(index);
196         
197         super.set(index, element);
198         return result;
199     }
200     
201     private void addToMap(E o, int index)
202     {
203         if (index < size())
204             for (Map.Entry JavaDoc<Integer JavaDoc, TreeSet JavaDoc<Integer JavaDoc>> i : map.entrySet())
205             {
206                 TreeSet JavaDoc<Integer JavaDoc> newSet = new TreeSet JavaDoc<Integer JavaDoc>();
207                 for (Integer JavaDoc j : i.getValue())
208                     if (j >= index)
209                         newSet.add(j + 1);
210                 i.setValue(newSet);
211             }
212                 
213         
214         if (!map.containsKey(o.hashCode()))
215             map.put(o.hashCode(), new TreeSet JavaDoc<Integer JavaDoc>());
216         map.get(o.hashCode()).add(index);
217     }
218     
219     private void removeFromMap(E o, int index)
220     {
221         if (map.get(o.hashCode()).size() == 1)
222             map.remove(o.hashCode());
223         else
224             map.get(o.hashCode()).remove(index);
225         
226         if (index < size() - 1)
227             for (Map.Entry JavaDoc<Integer JavaDoc, TreeSet JavaDoc<Integer JavaDoc>> i : map.entrySet())
228             {
229                 TreeSet JavaDoc<Integer JavaDoc> newSet = new TreeSet JavaDoc<Integer JavaDoc>();
230                 for (Integer JavaDoc j : i.getValue())
231                     if (j > index)
232                         newSet.add(j - 1);
233                 i.setValue(newSet);
234             }
235     }
236     
237     @Override JavaDoc
238     public ListIterator JavaDoc<E> listIterator()
239     {
240         return new ListIterator JavaDoc<E>()
241         {
242             int cursor = -1;
243             boolean removable = false;
244             boolean removed = false;
245             
246             public void add(E o)
247             {
248                 HashList.this.add(cursor++, o);
249                 removable = false;
250             }
251
252             public boolean hasNext()
253             {
254                 return (cursor < size() - 1);
255             }
256
257             public boolean hasPrevious()
258             {
259                 return (cursor > 0);
260             }
261
262             public E next()
263             {
264                 if (!hasNext())
265                     throw new NoSuchElementException JavaDoc();
266                 
267                 if (removed)
268                 {
269                     removable = true;
270                     removed = false;
271                     return get(cursor);
272                 }
273                 else
274                 {
275                     removable = true;
276                     removed = false;
277                     return get(++cursor);
278                 }
279             }
280
281             public int nextIndex()
282             {
283                 return (removed ? cursor : cursor + 1);
284             }
285
286             public E previous()
287             {
288                 if (!hasPrevious())
289                     throw new NoSuchElementException JavaDoc();
290                 
291                 removable = true;
292                 removed = false;
293                 return get(--cursor);
294             }
295
296             public int previousIndex()
297             {
298                 if (hasPrevious())
299                     return cursor - 1;
300                 else
301                     return -1;
302             }
303
304             public void remove()
305             {
306                 if (!removable)
307                     throw new IllegalStateException JavaDoc("next() and previous() have not been called since the last call to remove()");
308                 removable = false;
309                 removed = true;
310                 HashList.this.remove(cursor);
311             }
312
313             public void set(E o)
314             {
315                 HashList.this.set(cursor, o);
316             }
317         };
318     }
319 }
320
Popular Tags