|
1
19
20
25
26
27 package soot.util;
28
29 import java.util.*;
30 import soot.*;
31 import java.io.*;
32
33
35 public class HashChain extends AbstractCollection
36 implements Chain
37 {
38 private HashMap map = new HashMap();
39 private Object  firstItem;
40 private Object lastItem;
41 private long stateCount = 0;
42
43
44 public void clear()
45 {
46 stateCount++;
47 firstItem = lastItem = null;
48 map.clear();
49 }
50
51 public void swapWith(Object out, Object in)
52 {
53 insertBefore(in, out);
54 remove(out);
55 }
56
57
58 public boolean add(Object item)
59 {
60 addLast(item);
61 return true;
62 }
63
64
65 public static List toList(Chain c)
66 {
67 Iterator it = c.iterator();
68 List list = new ArrayList();
69
70 while(it.hasNext()) {
71 list.add(it.next());
72 }
73
74 return list;
75 }
76
77
78 public HashChain()
79 {
80 firstItem = lastItem = null;
81 }
82
83 public boolean follows(Object someObject, Object someReferenceObject)
84 {
85 Iterator it = iterator(someObject);
86 while(it.hasNext()) {
87
88 if(it.next() == someReferenceObject)
89 return false;
90 }
91 return true;
92 }
93
94 public boolean contains(Object o)
95 {
96 return map.containsKey(o);
97 }
98
99 public boolean containsAll(Collection c)
100 {
101 Iterator it = c.iterator();
102 while (it.hasNext())
103 if (!(map.containsKey(it.next())))
104 return false;
105
106 return true;
107 }
108
109 public void insertAfter(Object toInsert, Object point)
110 {
111 if (toInsert == null)
112 throw new RuntimeException ("Bad idea! You tried to insert "
113 + " a null object into a Chain!");
114
115 if(map.containsKey(toInsert))
116 throw new RuntimeException ("Chain already contains object.");
117 stateCount++;
118 Link temp = (Link) map.get(point);
119
120 Link newLink = temp.insertAfter(toInsert);
121 map.put(toInsert, newLink);
122 }
123
124 public void insertAfter(List toInsert, Object point)
125 {
126 if (toInsert == null)
128 throw new RuntimeException ("Warning! You tried to insert "
129 + "a null list into a Chain!");
130
131 Object previousPoint = point;
132 Iterator it = toInsert.iterator();
133 while (it.hasNext())
134 {
135 Object o = it.next();
136 insertAfter(o, previousPoint);
137 previousPoint = o;
138 }
139 }
140
141 public void insertAfter(Chain toInsert, Object point)
142 {
143 if (toInsert == null)
145 throw new RuntimeException ("Warning! You tried to insert "
146 + "a null list into a Chain!");
147
148 Object previousPoint = point;
149 Iterator it = toInsert.iterator();
150 while (it.hasNext())
151 {
152 Object o = it.next();
153 insertAfter(o, previousPoint);
154 previousPoint = o;
155 }
156 }
157
158 public void insertBefore(Object toInsert, Object point)
159 {
160 if (toInsert == null)
161 throw new RuntimeException ("Bad idea! You tried to insert "
162 + "a null object into a Chain!");
163
164 if(map.containsKey(toInsert))
165 throw new RuntimeException ("Chain already contains object.");
166 stateCount++;
167 Link temp = (Link) map.get(point);
168
169 Link newLink = temp.insertBefore(toInsert);
170 map.put(toInsert, newLink);
171 }
172
173 public void insertBefore(List toInsert, Object point)
174 {
175 if (toInsert == null)
177 throw new RuntimeException ("Warning! You tried to insert "
178 + "a null list into a Chain!");
179
180 Iterator it = toInsert.iterator();
181 while (it.hasNext())
182 {
183 Object o = it.next();
184 insertBefore(o, point);
185 }
186 }
187
188 public void insertBefore(Chain toInsert, Object point)
189 {
190 if (toInsert == null)
192 throw new RuntimeException ("Warning! You tried to insert "
193 + "a null list into a Chain!");
194
195 Iterator it = toInsert.iterator();
196 while (it.hasNext())
197 {
198 Object o = it.next();
199 insertBefore(o, point);
200 }
201 }
202
203 public static HashChain listToHashChain(List list) {
204 HashChain c = new HashChain();
205 Iterator it = list.iterator();
206 while (it.hasNext())
207 c.addLast(it.next());
208 return c;
209 }
210
211 public boolean remove(Object item)
212 {
213 if (item == null)
214 throw new RuntimeException ("Bad idea! You tried to remove "
215 + " a null object from a Chain!");
216
217 stateCount++;
218 Link link = (Link) map.get(item);
219
220 link.unlinkSelf();
221 map.remove(item);
222 return true;
223 }
224
225 public void addFirst(Object item)
226 {
227 if (item == null)
228 throw new RuntimeException ("Bad idea! You tried to insert "
229 + "a null object into a Chain!");
230
231 stateCount++;
232 Link newLink, temp;
233
234 if(map.containsKey(item))
235 throw new RuntimeException ("Chain already contains object.");
236
237 if(firstItem != null) {
238 temp = (Link) map.get(firstItem);
239 newLink = temp.insertBefore(item);
240 } else {
241 newLink = new Link(item);
242 firstItem = lastItem = item;
243 }
244 map.put(item, newLink);
245 }
246
247 public void addLast(Object item)
248 {
249 if (item == null)
250 throw new RuntimeException ("Bad idea! You tried to insert "
251 + " a null object into a Chain!");
252
253 stateCount++;
254 Link newLink, temp;
255 if(map.containsKey(item))
256 throw new RuntimeException ("Chain already contains object: "
257 + item);
258
259 if(lastItem != null) {
260 temp = (Link) map.get(lastItem);
261 newLink = temp.insertAfter(item);
262 } else {
263 newLink = new Link(item);
264 firstItem = lastItem = item;
265 }
266 map.put(item, newLink);
267 }
268
269 public void removeFirst()
270 {
271 stateCount++;
272 Object item = firstItem;
273 ((Link) map.get(firstItem)).unlinkSelf();
274 map.remove(item);
275 }
276
277 public void removeLast()
278 {
279 stateCount++;
280 Object item = lastItem;
281 ((Link) map.get(lastItem)).unlinkSelf();
282 map.remove(item);
283 }
284
285 public Object getFirst()
286 {
287 if(firstItem == null)
288 throw new NoSuchElementException();
289 return firstItem;
290 }
291
292 public Object getLast()
293 {
294 if(lastItem == null)
295 throw new NoSuchElementException();
296 return lastItem;
297 }
298
299 public Object getSuccOf(Object point)
300 throws NoSuchElementException
301 {
302 Link link = (Link) map.get(point);
303 try {
304 link = link.getNext();
305 }
306 catch (NullPointerException e) {
307 throw new NoSuchElementException();
308 }
309 if(link == null)
310 return null;
311
312 return link.getItem();
313 }
314
315 public Object getPredOf(Object point)
316 throws NoSuchElementException
317 {
318 Link link = (Link) map.get(point);
319 if(point == null)
320 throw new RuntimeException ("trying to hash null value.");
321
322 try {
323 link = link.getPrevious();
324 }
325 catch (NullPointerException e) {
326 throw new NoSuchElementException();
327 }
328
329 if(link == null)
330 return null;
331 else
332 return link.getItem();
333 }
334
335 public Iterator snapshotIterator()
336 {
337 List l = new ArrayList( map.size());
338
339 l.addAll(this);
340
341 return l.iterator();
342 }
343
344 public Iterator snapshotIterator( Object item)
345 {
346 List l = new ArrayList( map.size());
347
348 Iterator it = new LinkIterator( item);
349 while (it.hasNext())
350 l.add( it.next());
351
352 return l.iterator();
353 }
354
355 public Iterator iterator(){ return new LinkIterator(firstItem); }
356 public Iterator iterator(Object item)
357 {
358 return new LinkIterator(item);
359 }
360
361
376 public Iterator iterator(Object head, Object tail)
377 {
378 if (head != null && this.getPredOf(head) == tail) {
379 return new LinkIterator(null, null);
381 } else {
382 return new LinkIterator(head, tail);
383 }
384 }
385
386 public int size(){ return map.size(); }
387
388
389 public String toString()
390 {
391 StringBuffer strBuf = new StringBuffer ();
392 Iterator it = iterator();
393 boolean b = false;
394
395 strBuf.append("[");
396 while(it.hasNext()) {
397 if (!b) b = true; else strBuf.append(", ");
398 strBuf.append(it.next().toString());
399 }
400 strBuf.append("]");
401 return strBuf.toString();
402 }
403
404
405 class Link implements Serializable {
406 private Link nextLink;
407 private Link previousLink;
408 private Object item;
409 private int index;
410
411 public Link(Object item)
412 {
413 this.item = item;
414 nextLink = previousLink = null;
415 }
416
417 public Link getNext() { return nextLink;}
418 public Link getPrevious() { return previousLink;}
419
420 public void setNext(Link link) { this.nextLink = link;}
421 public void setPrevious(Link link) { this.previousLink = link;}
422
423
424 public void unlinkSelf()
425 {
426 bind(previousLink, nextLink);
427
428 }
429
430 public Link insertAfter(Object item)
431 {
432 Link newLink = new Link(item);
433
434 bind(newLink, nextLink);
435 bind(this, newLink);
436 return newLink;
437 }
438
439 public Link insertBefore(Object item)
440 {
441 Link newLink = new Link(item);
442
443 bind(previousLink, newLink);
444 bind(newLink, this);
445 return newLink;
446 }
447
448
449 private void bind(Link a, Link b)
450 {
451 if(a == null) {
452 if(b != null)
453 firstItem = b.getItem();
454 else
455 firstItem = null;
456 } else
457 a.setNext(b);
458
459 if(b == null){
460 if(a != null)
461 lastItem = a.getItem();
462 else
463 lastItem = null;
464 }
465 else
466 b.setPrevious(a);
467 }
468
469 public Object getItem() { return item; }
470
471
472 public String toString()
473 {
474 if(item != null)
475 return item.toString();
476 else
477 return "Link item is null" + super.toString();
478
479 }
480
481 }
482
483 class LinkIterator implements Iterator
484 {
485 private Link currentLink;
486 boolean state;
489 private Object destination;
490 private long iteratorStateCount;
491
492
493 public LinkIterator(Object item)
494 {
495 Link nextLink = (Link) map.get(item);
496 if (nextLink == null && item != null)
497 throw new NoSuchElementException("HashChain.LinkIterator(obj) with obj that is not in the chain: " + item.toString() );
498 currentLink = new Link(null);
499 currentLink.setNext(nextLink);
500 state = false;
501 destination = null;
502 iteratorStateCount = stateCount;
503 }
504
505 public LinkIterator(Object from, Object to)
506 {
507 this(from);
508 destination = to;
509 }
510
511
512 public boolean hasNext()
513 {
514 if(stateCount != iteratorStateCount) {
515 throw new ConcurrentModificationException();
516 }
517
518 if(destination == null)
519 return (currentLink.getNext() != null);
520 else
521 return (destination != currentLink.getItem());
525 }
526
527 public Object next()
528 throws NoSuchElementException
529 {
530 if(stateCount != iteratorStateCount)
531 throw new ConcurrentModificationException();
532
533 Link temp = currentLink.getNext();
534 if(temp == null) {
535 String exceptionMsg;
536 if(destination != null && destination != currentLink.getItem())
537 exceptionMsg = "HashChain.LinkIterator.next() reached end of chain without reaching specified tail unit";
538 else
539 exceptionMsg = "HashChain.LinkIterator.next() called past the end of the Chain";
540 throw new NoSuchElementException(exceptionMsg);
541 }
542 currentLink = temp;
543
544 state = true;
545 return currentLink.getItem();
546 }
547
548 public void remove()
549 throws IllegalStateException
550 {
551 if(stateCount != iteratorStateCount)
552 throw new ConcurrentModificationException();
553
554 stateCount++; iteratorStateCount++;
555 if(!state)
556 throw new IllegalStateException ();
557 else {
558 currentLink.unlinkSelf();
559 map.remove(currentLink.getItem());
560 state = false;
561 }
562
563 }
564
565 public String toString()
566 {
567 if(currentLink == null)
568 return "Current object under iterator is null"
569 + super.toString();
570 else
571 return currentLink.toString();
572 }
573 }
574 }
575
576 |
Popular Tags |
Java API By Example, From Geeks To Geeks.