1 19 20 package edu.umd.cs.findbugs.gui2; 21 22 import java.util.AbstractList ; 23 import java.util.ArrayList ; 24 import java.util.Arrays ; 25 import java.util.Collection ; 26 import java.util.Collections ; 27 import java.util.HashMap ; 28 import java.util.ListIterator ; 29 import java.util.Map ; 30 import java.util.NoSuchElementException ; 31 import java.util.Set ; 32 import java.util.TreeSet ; 33 34 39 public class HashList<E> extends ArrayList <E> 40 { 41 private static final long serialVersionUID = 6710532766397389391L; 42 43 private HashMap <Integer , TreeSet <Integer >> map = new HashMap <Integer , TreeSet <Integer >>(); 45 46 public HashList() 47 { 48 super(); 49 } 50 51 public HashList(Collection <? extends E> c) 52 { 53 super(); 54 addAll(c); 55 } 56 57 @Override 58 public boolean add(E o) 59 { 60 add(size(), o); 61 return true; 62 } 63 64 @Override 65 public void add(int index, E element) 66 { 67 addToMap(element, index); 68 super.add(index, element); 69 } 70 71 @Override 72 public boolean addAll(Collection <? extends E> c) 73 { 74 for (E i : c) 75 add(i); 76 return (c.size() > 0); 77 } 78 79 @Override 80 public boolean addAll(int index, Collection <? 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 92 public void clear() 93 { 94 super.clear(); 95 map.clear(); 96 } 97 98 @Override 99 public boolean contains(Object elem) 100 { 101 return (indexOf(elem) != -1); 102 } 103 104 @Override 105 public boolean containsAll(Collection <?> c) 106 { 107 for (Object i : c) 108 if (!contains(i)) 109 return false; 110 return true; 111 } 112 113 @Override 114 public int indexOf(Object elem) 115 { 116 Set <Integer > s=map.get(elem.hashCode()); 117 if (s==null) 118 return -1; 119 for (Integer i : s) 120 if (get(i).equals(elem)) 121 return i; 122 return -1; 123 } 124 125 @Override 126 public int lastIndexOf(Object elem) 127 { 128 int result = -1; 129 for (Integer i : map.get(elem.hashCode())) 130 if (get(i).equals(elem)) 131 result = i; 132 return result; 133 } 134 135 @Override 136 public E remove(int index) 137 { 138 E result = super.remove(index); 139 removeFromMap(result, index); 140 return result; 141 } 142 143 @Override 144 public boolean remove(Object 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 156 public boolean removeAll(Collection <?> c) 157 { 158 boolean result = false; 159 for (Object i : c) 160 result |= remove(i); 161 return result; 162 } 163 164 @Override 165 public boolean retainAll(Collection <?> 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 178 protected void removeRange(int fromIndex, int toIndex) 179 { 180 throw new UnsupportedOperationException (); 181 } 182 183 @Override 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 <Integer >()); 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 <Integer , TreeSet <Integer >> i : map.entrySet()) 205 { 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 if (!map.containsKey(o.hashCode())) 215 map.put(o.hashCode(), new TreeSet <Integer >()); 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 <Integer , TreeSet <Integer >> i : map.entrySet()) 228 { 229 TreeSet <Integer > newSet = new TreeSet <Integer >(); 230 for (Integer j : i.getValue()) 231 if (j > index) 232 newSet.add(j - 1); 233 i.setValue(newSet); 234 } 235 } 236 237 @Override 238 public ListIterator <E> listIterator() 239 { 240 return new ListIterator <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 (); 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 (); 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 ("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 |