001: /* Soot - a J*va Optimization Framework
002: * Copyright (C) 2002 Ondrej Lhotak
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: package soot.util;
021:
022: import java.util.*;
023:
024: /** Holds a set of Numberable objects.
025: *
026: * @author Ondrej Lhotak
027: */
028:
029: public final class NumberedSet {
030: public NumberedSet(ArrayNumberer universe) {
031: this .universe = universe;
032: }
033:
034: public boolean add(Numberable o) {
035: if (array != null) {
036: int pos = findPosition(o);
037: if (array[pos] == o)
038: return false;
039: size++;
040: if (size * 3 > array.length * 2) {
041: doubleSize();
042: if (array != null) {
043: pos = findPosition(o);
044: } else {
045: int number = o.getNumber();
046: if (number == 0)
047: throw new RuntimeException("unnumbered");
048: return bits.set(number);
049: }
050: }
051: array[pos] = o;
052: return true;
053: } else {
054: int number = o.getNumber();
055: if (number == 0)
056: throw new RuntimeException("unnumbered");
057: if (bits.set(number)) {
058: size++;
059: return true;
060: } else {
061: return false;
062: }
063: }
064: }
065:
066: public boolean contains(Numberable o) {
067: if (array != null) {
068: return array[findPosition(o)] != null;
069: } else {
070: int number = o.getNumber();
071: if (number == 0)
072: throw new RuntimeException("unnumbered");
073: return bits.get(number);
074: }
075: }
076:
077: /* Private stuff. */
078:
079: private final int findPosition(Numberable o) {
080: int number = o.getNumber();
081: if (number == 0)
082: throw new RuntimeException("unnumbered");
083: number = number & (array.length - 1);
084: while (true) {
085: if (array[number] == o)
086: return number;
087: if (array[number] == null)
088: return number;
089: number = (number + 1) & (array.length - 1);
090: }
091: }
092:
093: private final void doubleSize() {
094: int uniSize = universe.size();
095: if (array.length * 128 > uniSize) {
096: bits = new BitVector(uniSize);
097: Numberable[] oldArray = array;
098: array = null;
099: for (Numberable element : oldArray) {
100: if (element != null) {
101: bits.set(element.getNumber());
102: }
103: }
104: } else {
105: Numberable[] oldArray = array;
106: array = new Numberable[array.length * 2];
107: for (Numberable element : oldArray) {
108: if (element != null) {
109: array[findPosition(element)] = element;
110: }
111: }
112: }
113: }
114:
115: public Iterator iterator() {
116: if (array == null)
117: return new BitSetIterator(this );
118: else
119: return new NumberedSetIterator(this );
120: }
121:
122: class BitSetIterator implements Iterator {
123: soot.util.BitSetIterator iter;
124:
125: BitSetIterator(NumberedSet set) {
126: iter = set.bits.iterator();
127: }
128:
129: public final boolean hasNext() {
130: return iter.hasNext();
131: }
132:
133: public void remove() {
134: throw new RuntimeException("Not implemented.");
135: }
136:
137: public final Object next() {
138: return universe.get(iter.next());
139: }
140:
141: }
142:
143: class NumberedSetIterator implements Iterator {
144: NumberedSet set;
145: int cur = 0;
146:
147: NumberedSetIterator(NumberedSet set) {
148: this .set = set;
149: seekNext();
150: }
151:
152: protected final void seekNext() {
153: try {
154: while (set.array[cur] == null) {
155: cur++;
156: }
157: } catch (ArrayIndexOutOfBoundsException e) {
158: cur = -1;
159: }
160: }
161:
162: public final boolean hasNext() {
163: return cur != -1;
164: }
165:
166: public void remove() {
167: throw new RuntimeException("Not implemented.");
168: }
169:
170: public final Object next() {
171: Numberable ret = set.array[cur];
172: cur++;
173: seekNext();
174: return ret;
175: }
176: }
177:
178: public final int size() {
179: return size;
180: }
181:
182: private Numberable[] array = new Numberable[8];
183: private BitVector bits;
184: private int size = 0;
185: private ArrayNumberer universe;
186:
187: }
|