001: /* Soot - a J*va Optimization Framework
002: * Copyright (C) 1999 Patrice Pominville
003: *
004: * This library is free software; you can redistribute it and/or
005: * modify it under the terms of the GNU Lesser General Public
006: * License as published by the Free Software Foundation; either
007: * version 2.1 of the License, or (at your option) any later version.
008: *
009: * This library is distributed in the hope that it will be useful,
010: * but WITHOUT ANY WARRANTY; without even the implied warranty of
011: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
012: * Lesser General Public License for more details.
013: *
014: * You should have received a copy of the GNU Lesser General Public
015: * License along with this library; if not, write to the
016: * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
017: * Boston, MA 02111-1307, USA.
018: */
019:
020: /*
021: * Modified by the Sable Research Group and others 1997-1999.
022: * See the 'credits' file distributed with Soot for the complete list of
023: * contributors. (Soot is distributed at http://www.sable.mcgill.ca/soot)
024: */
025:
026: package soot.util;
027:
028: import java.io.Serializable;
029: import java.util.AbstractCollection;
030: import java.util.ArrayList;
031: import java.util.Collection;
032: import java.util.ConcurrentModificationException;
033: import java.util.HashMap;
034: import java.util.Iterator;
035: import java.util.List;
036: import java.util.NoSuchElementException;
037:
038: /** Reference implementation of the Chain interface,
039: using a HashMap as the underlying structure. */
040: public class HashChain<E> extends AbstractCollection<E> implements
041: Chain<E> {
042: private final HashMap<E, Link> map = new HashMap<E, Link>();
043: private E firstItem;
044: private E lastItem;
045: private long stateCount = 0;
046:
047: /** Erases the contents of the current HashChain. */
048: public void clear() {
049: stateCount++;
050: firstItem = lastItem = null;
051: map.clear();
052: }
053:
054: public void swapWith(E out, E in) {
055: insertBefore(in, out);
056: remove(out);
057: }
058:
059: /** Adds the given object to this HashChain. */
060: public boolean add(E item) {
061: addLast(item);
062: return true;
063: }
064:
065: /** Returns an unbacked list containing the contents of the given Chain. */
066: public static List toList(Chain c) {
067: Iterator it = c.iterator();
068: List list = new ArrayList();
069:
070: while (it.hasNext()) {
071: list.add(it.next());
072: }
073:
074: return list;
075: }
076:
077: /** Constructs an empty HashChain. */
078: public HashChain() {
079: firstItem = lastItem = null;
080: }
081:
082: public boolean follows(E someObject, E someReferenceObject) {
083: Iterator it = iterator(someObject);
084: while (it.hasNext()) {
085:
086: if (it.next() == someReferenceObject)
087: return false;
088: }
089: return true;
090: }
091:
092: public boolean contains(Object o) {
093: return map.containsKey(o);
094: }
095:
096: public boolean containsAll(Collection c) {
097: Iterator it = c.iterator();
098: while (it.hasNext())
099: if (!(map.containsKey(it.next())))
100: return false;
101:
102: return true;
103: }
104:
105: public void insertAfter(E toInsert, E point) {
106: if (toInsert == null)
107: throw new RuntimeException("Bad idea! You tried to insert "
108: + " a null object into a Chain!");
109:
110: if (map.containsKey(toInsert))
111: throw new RuntimeException("Chain already contains object.");
112: stateCount++;
113: Link temp = map.get(point);
114:
115: Link newLink = temp.insertAfter(toInsert);
116: map.put(toInsert, newLink);
117: }
118:
119: public void insertAfter(List<E> toInsert, E point) {
120: // if the list is null, treat it as an empty list
121: if (toInsert == null)
122: throw new RuntimeException("Warning! You tried to insert "
123: + "a null list into a Chain!");
124:
125: E previousPoint = point;
126: Iterator<E> it = toInsert.iterator();
127: while (it.hasNext()) {
128: E o = it.next();
129: insertAfter(o, previousPoint);
130: previousPoint = o;
131: }
132: }
133:
134: public void insertAfter(Chain<E> toInsert, E point) {
135: // if the list is null, treat it as an empty list
136: if (toInsert == null)
137: throw new RuntimeException("Warning! You tried to insert "
138: + "a null list into a Chain!");
139:
140: E previousPoint = point;
141: Iterator<E> it = toInsert.iterator();
142: while (it.hasNext()) {
143: E o = it.next();
144: insertAfter(o, previousPoint);
145: previousPoint = o;
146: }
147: }
148:
149: public void insertBefore(E toInsert, E point) {
150: if (toInsert == null)
151: throw new RuntimeException("Bad idea! You tried to insert "
152: + "a null object into a Chain!");
153:
154: if (map.containsKey(toInsert))
155: throw new RuntimeException("Chain already contains object.");
156: stateCount++;
157: Link temp = map.get(point);
158:
159: Link newLink = temp.insertBefore(toInsert);
160: map.put(toInsert, newLink);
161: }
162:
163: public void insertBefore(List<E> toInsert, E point) {
164: // if the list is null, treat it as an empty list
165: if (toInsert == null)
166: throw new RuntimeException("Warning! You tried to insert "
167: + "a null list into a Chain!");
168:
169: Iterator<E> it = toInsert.iterator();
170: while (it.hasNext()) {
171: E o = it.next();
172: insertBefore(o, point);
173: }
174: }
175:
176: public void insertBefore(Chain<E> toInsert, E point) {
177: // if the list is null, treat it as an empty list
178: if (toInsert == null)
179: throw new RuntimeException("Warning! You tried to insert "
180: + "a null list into a Chain!");
181:
182: Iterator<E> it = toInsert.iterator();
183: while (it.hasNext()) {
184: E o = it.next();
185: insertBefore(o, point);
186: }
187: }
188:
189: public static HashChain listToHashChain(List list) {
190: HashChain c = new HashChain();
191: Iterator it = list.iterator();
192: while (it.hasNext())
193: c.addLast(it.next());
194: return c;
195: }
196:
197: public boolean remove(Object item) {
198: if (item == null)
199: throw new RuntimeException("Bad idea! You tried to remove "
200: + " a null object from a Chain!");
201:
202: stateCount++;
203: /*
204: * 4th April 2005 Nomair A Naeem
205: * map.get(obj) can return null
206: * only return true if this is non null
207: * else return false
208: */
209: if (map.get(item) != null) {
210: Link link = map.get(item);
211:
212: link.unlinkSelf();
213: map.remove(item);
214: return true;
215: }
216: return false;
217: }
218:
219: public void addFirst(E item) {
220: if (item == null)
221: throw new RuntimeException(
222: "Bad idea! You tried to insert "
223: + "a null object into a Chain!");
224:
225: stateCount++;
226: Link newLink, temp;
227:
228: if (map.containsKey(item))
229: throw new RuntimeException("Chain already contains object.");
230:
231: if (firstItem != null) {
232: temp = map.get(firstItem);
233: newLink = temp.insertBefore(item);
234: } else {
235: newLink = new Link(item);
236: firstItem = lastItem = item;
237: }
238: map.put(item, newLink);
239: }
240:
241: public void addLast(E item) {
242: if (item == null)
243: throw new RuntimeException("Bad idea! You tried to insert "
244: + " a null object into a Chain!");
245:
246: stateCount++;
247: Link newLink, temp;
248: if (map.containsKey(item))
249: throw new RuntimeException(
250: "Chain already contains object: " + item);
251:
252: if (lastItem != null) {
253: temp = map.get(lastItem);
254: newLink = temp.insertAfter(item);
255: } else {
256: newLink = new Link(item);
257: firstItem = lastItem = item;
258: }
259: map.put(item, newLink);
260: }
261:
262: public void removeFirst() {
263: stateCount++;
264: Object item = firstItem;
265: map.get(firstItem).unlinkSelf();
266: map.remove(item);
267: }
268:
269: public void removeLast() {
270: stateCount++;
271: Object item = lastItem;
272: map.get(lastItem).unlinkSelf();
273: map.remove(item);
274: }
275:
276: public E getFirst() {
277: if (firstItem == null)
278: throw new NoSuchElementException();
279: return firstItem;
280: }
281:
282: public E getLast() {
283: if (lastItem == null)
284: throw new NoSuchElementException();
285: return lastItem;
286: }
287:
288: public E getSuccOf(E point) throws NoSuchElementException {
289: Link<E> link = map.get(point);
290: try {
291: link = link.getNext();
292: } catch (NullPointerException e) {
293: throw new NoSuchElementException();
294: }
295: if (link == null)
296: return null;
297:
298: return link.getItem();
299: }
300:
301: public E getPredOf(E point) throws NoSuchElementException {
302: Link<E> link = map.get(point);
303: if (point == null)
304: throw new RuntimeException("trying to hash null value.");
305:
306: try {
307: link = link.getPrevious();
308: } catch (NullPointerException e) {
309: throw new NoSuchElementException();
310: }
311:
312: if (link == null)
313: return null;
314: else
315: return link.getItem();
316: }
317:
318: public Iterator<E> snapshotIterator() {
319: List l = new ArrayList(map.size());
320:
321: l.addAll(this );
322:
323: return l.iterator();
324: }
325:
326: public Iterator<E> snapshotIterator(Object item) {
327: List l = new ArrayList(map.size());
328:
329: Iterator it = new LinkIterator(item);
330: while (it.hasNext())
331: l.add(it.next());
332:
333: return l.iterator();
334: }
335:
336: public Iterator<E> iterator() {
337: return new LinkIterator(firstItem);
338: }
339:
340: public Iterator<E> iterator(E item) {
341: return new LinkIterator<E>(item);
342: }
343:
344: /** <p>Returns an iterator ranging from <code>head</code> to
345: * <code>tail</code>, inclusive.</p>
346:
347: <p>If <code>tail</code> is the element immediately preceding
348: <code>head</code> in this <code>HashChain</code>, the returned
349: iterator will iterate 0 times (a special case to allow the
350: specification of an empty range of elements). Otherwise if
351: <code>tail</code> is not one of the elements following
352: <code>head</code>, the returned iterator will iterate past the
353: end of the <code>HashChain</code>, provoking a
354: {@link NoSuchElementException}.</p>
355:
356: @throws NoSuchElementException if <code>head</code> is not
357: an element of the chain.
358: */
359: public Iterator<E> iterator(E head, E tail) {
360: if (head != null && this .getPredOf(head) == tail) {
361: // special case hack, so empty ranges iterate 0 times
362: return new LinkIterator(null, null);
363: } else {
364: return new LinkIterator(head, tail);
365: }
366: }
367:
368: public int size() {
369: return map.size();
370: }
371:
372: /** Returns a textual representation of the contents of this Chain. */
373: public String toString() {
374: StringBuffer strBuf = new StringBuffer();
375: Iterator it = iterator();
376: boolean b = false;
377:
378: strBuf.append("[");
379: while (it.hasNext()) {
380: if (!b)
381: b = true;
382: else
383: strBuf.append(", ");
384: strBuf.append(it.next().toString());
385: }
386: strBuf.append("]");
387: return strBuf.toString();
388: }
389:
390: class Link<X extends E> implements Serializable {
391: private Link<X> nextLink;
392: private Link<X> previousLink;
393: private X item;
394:
395: public Link(X item) {
396: this .item = item;
397: nextLink = previousLink = null;
398: }
399:
400: public Link<X> getNext() {
401: return nextLink;
402: }
403:
404: public Link<X> getPrevious() {
405: return previousLink;
406: }
407:
408: public void setNext(Link<X> link) {
409: this .nextLink = link;
410: }
411:
412: public void setPrevious(Link<X> link) {
413: this .previousLink = link;
414: }
415:
416: public void unlinkSelf() {
417: bind(previousLink, nextLink);
418:
419: }
420:
421: public Link<X> insertAfter(X item) {
422: Link newLink = new Link(item);
423:
424: bind(newLink, nextLink);
425: bind(this , newLink);
426: return newLink;
427: }
428:
429: public Link<X> insertBefore(X item) {
430: Link newLink = new Link(item);
431:
432: bind(previousLink, newLink);
433: bind(newLink, this );
434: return newLink;
435: }
436:
437: private void bind(Link<X> a, Link<X> b) {
438: if (a == null) {
439: if (b != null)
440: firstItem = b.getItem();
441: else
442: firstItem = null;
443: } else
444: a.setNext(b);
445:
446: if (b == null) {
447: if (a != null)
448: lastItem = a.getItem();
449: else
450: lastItem = null;
451: } else
452: b.setPrevious(a);
453: }
454:
455: public X getItem() {
456: return item;
457: }
458:
459: public String toString() {
460: if (item != null)
461: return item.toString();
462: else
463: return "Link item is null" + super .toString();
464:
465: }
466:
467: }
468:
469: class LinkIterator<X extends E> implements Iterator {
470: private Link<X> currentLink;
471: boolean state; // only when this is true can remove() be called
472: // (in accordance w/ iterator semantics)
473:
474: private X destination;
475: private long iteratorStateCount;
476:
477: public LinkIterator(X item) {
478: Link nextLink = map.get(item);
479: if (nextLink == null && item != null)
480: throw new NoSuchElementException(
481: "HashChain.LinkIterator(obj) with obj that is not in the chain: "
482: + item.toString());
483: currentLink = new Link(null);
484: currentLink.setNext(nextLink);
485: state = false;
486: destination = null;
487: iteratorStateCount = stateCount;
488: }
489:
490: public LinkIterator(X from, X to) {
491: this (from);
492: destination = to;
493: }
494:
495: public boolean hasNext() {
496: if (stateCount != iteratorStateCount) {
497: throw new ConcurrentModificationException();
498: }
499:
500: if (destination == null)
501: return (currentLink.getNext() != null);
502: else
503: // Ignore whether (currentLink.getNext() == null), so
504: // next() will produce a NoSuchElementException if
505: // destination is not in the chain.
506: return (destination != currentLink.getItem());
507: }
508:
509: public X next() throws NoSuchElementException {
510: if (stateCount != iteratorStateCount)
511: throw new ConcurrentModificationException();
512:
513: Link<X> temp = currentLink.getNext();
514: if (temp == null) {
515: String exceptionMsg;
516: if (destination != null
517: && destination != currentLink.getItem())
518: exceptionMsg = "HashChain.LinkIterator.next() reached end of chain without reaching specified tail unit";
519: else
520: exceptionMsg = "HashChain.LinkIterator.next() called past the end of the Chain";
521: throw new NoSuchElementException(exceptionMsg);
522: }
523: currentLink = temp;
524:
525: state = true;
526: return currentLink.getItem();
527: }
528:
529: public void remove() throws IllegalStateException {
530: if (stateCount != iteratorStateCount)
531: throw new ConcurrentModificationException();
532:
533: stateCount++;
534: iteratorStateCount++;
535: if (!state)
536: throw new IllegalStateException();
537: else {
538: currentLink.unlinkSelf();
539: map.remove(currentLink.getItem());
540: state = false;
541: }
542:
543: }
544:
545: public String toString() {
546: if (currentLink == null)
547: return "Current object under iterator is null"
548: + super.toString();
549: else
550: return currentLink.toString();
551: }
552: }
553: }
|