|
1
19
20 package soot.util;
21 import java.util.*;
22
23
27
28 public final class NumberedSet {
29 public NumberedSet( ArrayNumberer universe ) {
30 this.universe = universe;
31 }
32 public boolean add( Numberable o ) {
33 if( array != null ) {
34 int pos = findPosition( o );
35 if( array[pos] == o ) return false;
36 size++;
37 if( size*3 > array.length*2 ) {
38 doubleSize();
39 if( array != null ) {
40 pos = findPosition( o );
41 } else {
42 int number = o.getNumber();
43 if( number == 0 ) throw new RuntimeException  ( "unnumbered" );
44 return bits.set( number );
45 }
46 }
47 array[pos] = o;
48 return true;
49 } else {
50 int number = o.getNumber();
51 if( number == 0 ) throw new RuntimeException ( "unnumbered" );
52 if( bits.set( number ) ) {
53 size++;
54 return true;
55 } else {
56 return false;
57 }
58 }
59 }
60 public boolean contains( Numberable o ) {
61 if( array != null ) {
62 return array[ findPosition(o) ] != null;
63 } else {
64 int number = o.getNumber();
65 if( number == 0 ) throw new RuntimeException ( "unnumbered" );
66 return bits.get( number );
67 }
68 }
69
70
71
72 private final int findPosition( Numberable o ) {
73 int number = o.getNumber();
74 if( number == 0 ) throw new RuntimeException ( "unnumbered" );
75 number = number & (array.length-1);
76 while(true) {
77 if( array[number] == o ) return number;
78 if( array[number] == null ) return number;
79 number = (number+1) & (array.length-1);
80 }
81 }
82 private final void doubleSize() {
83 int uniSize = universe.size();
84 if( array.length*128 > uniSize ) {
85 bits = new BitVector( uniSize );
86 Numberable[] oldArray = array;
87 array = null;
88 for( int i = 0; i < oldArray.length; i++ ) {
89 Numberable element = oldArray[i];
90 if( element != null ) {
91 bits.set( element.getNumber() );
92 }
93 }
94 } else {
95 Numberable[] oldArray = array;
96 array = new Numberable[array.length*2];
97 for( int i = 0; i < oldArray.length; i++ ) {
98 Numberable element = oldArray[i];
99 if( element != null ) {
100 array[findPosition(element)] = element;
101 }
102 }
103 }
104 }
105 public Iterator iterator() {
106 if( array == null ) return new BitSetIterator( this );
107 else return new NumberedSetIterator( this );
108 }
109
110 class BitSetIterator implements Iterator {
111 soot.util.BitSetIterator iter;
112 BitSetIterator( NumberedSet set ) {
113 iter = set.bits.iterator();
114 }
115 public final boolean hasNext() { return iter.hasNext(); }
116 public void remove() {
117 throw new RuntimeException ( "Not implemented." );
118 }
119 public final Object next() {
120 return universe.get( iter.next() );
121 }
122
123 }
124
125 class NumberedSetIterator implements Iterator {
126 NumberedSet set;
127 int cur = 0;
128 NumberedSetIterator( NumberedSet set ) {
129 this.set = set;
130 seekNext();
131 }
132 protected final void seekNext() {
133 try {
134 while( set.array[cur] == null ) {
135 cur++;
136 }
137 } catch( ArrayIndexOutOfBoundsException e ) {
138 cur = -1;
139 }
140 }
141 public final boolean hasNext() { return cur != -1; }
142 public void remove() {
143 throw new RuntimeException ( "Not implemented." );
144 }
145 public final Object next() {
146 Numberable ret = set.array[cur];
147 cur++;
148 seekNext();
149 return ret;
150 }
151 }
152 public final int size() { return size; }
153
154 private Numberable[] array = new Numberable[8];
155 private BitVector bits;
156 private int size = 0;
157 private ArrayNumberer universe;
158
159 }
160 |
Popular Tags |
Java API By Example, From Geeks To Geeks.