1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
|
package org.eclipse.jdt.internal.core.builder.impl;
public class OrderedSet {
protected int elementCount;
protected Object [] elementKeys;
protected int [] elementIndexes;
protected Object [] orderedList;
protected float loadFactor;
private static final int DEFAULT_SIZE = 101;
/**
* Constructs a new OrderedSet using the default capacity
* and load factor.
*/
public OrderedSet() {
this (DEFAULT_SIZE);
}
/**
* Constructs a new OrderedSet using the specified capacity
* and the default load factor.
*
* @param capacity the initial capacity
*/
public OrderedSet (int capacity) {
this(capacity, 0.75f);
}
/**
* Constructs a new OrderedSet using the specified capacity
* and load factor.
*
* @param loadFactor the initial load factor
*/
public OrderedSet (int capacity, float loadFactor) {
if (capacity <= 0) throw new IllegalArgumentException();
elementCount = 0;
elementKeys = new Object [capacity];
int[] indexes = new int [capacity];
for (int i = capacity; --i >= 0; ) {
indexes[i] = -1;
}
elementIndexes = indexes;
orderedList = new Object[capacity];
this.loadFactor = loadFactor;
}
private int findIndex (Object object, Object [] array) {
Object key;
int length = array.length;
int index = (object.hashCode() & 0x7FFFFFFF) % length;
for (int i=index; i<length; i++) {
if (((key = array [i]) == null) || (key == object)) return i;
if (key.equals (object)) return i;
}
for (int i=0; i<index; i++) {
if (((key = array [i]) == null) || (key == object)) return i;
if (key.equals (object)) return i;
}
return -1; // unreacheable
}
/**
* Answers the object associated with the specified index in
* this OrderedSet.
*
* @param index the index to use
* @return the object associated with the specified index
* @throws ArrayIndexOutOfBoundsException if the index is out of range
*
* @see #put
*/
public Object get(int index) {
if (index >= elementCount) {
throw new ArrayIndexOutOfBoundsException();
}
return orderedList[index];
}
/**
* Answers whether the specified object is in
* this OrderedSet.
*
* @param obj the object, which must not be null
* @return true if the object is in the set, false otherwise
*
* @see #put
*/
public boolean includes(Object obj) {
if (obj == null) {
throw new NullPointerException();
}
int index = elementIndexes[findIndex (obj, elementKeys)];
return index != -1;
}
/**
* Answers the index associated with the specified object in
* this OrderedSet.
*
* @param obj the object, which must not be null
* @return the index associated with the object
* @throws IllegalArgumentException if the key is not in the pool
*
* @see #put
*/
public int index(Object obj) {
if (obj == null) {
throw new NullPointerException();
}
int findIndex = findIndex (obj, elementKeys);
int index = elementIndexes[findIndex];
if (index == -1) {
throw new IllegalArgumentException();
}
return index;
}
/**
* Associate the given object with the given index in this OrderedSet.
* The object's index is not retrievable using index(Object).
* But the object is retrievable using get(int index).
* The index must not yet have been assigned.
*
* @param index the index of the object
* @param obj the object to add
*
* @see #get
* @see java.lang.Object#equals
*/
public void put(int index, Object obj) {
if (obj == null) throw new NullPointerException ();
if (orderedList.length <= index) {
int[] newOrderedList = new int[orderedList.length*2];
System.arraycopy(orderedList, 0, newOrderedList, 0, elementCount);
}
if (orderedList[index] != null) {
throw new IllegalArgumentException();
}
orderedList[index] = obj;
if (index >= elementCount) {
elementCount = index + 1;
}
}
/**
* Associate the given object with the next index in this OrderedSet.
* If the object is already present, its index is unchanged. The object cannot be null.
*
* @param obj the object to add
* @return the index associated with the specified obj
*
* @see #index
* @see java.lang.Object#equals
*/
public int put (Object obj) {
if (obj == null) throw new NullPointerException ();
int index = findIndex (obj, elementKeys);
int resultIndex = elementIndexes [index];
if (resultIndex == -1) {
int size = (int)(elementKeys.length * loadFactor + 1);
if ((elementCount + 1) >= size) {
rehash ();
index = findIndex (obj, elementKeys);
}
orderedList [elementCount] = elementKeys [index] = obj;
return elementIndexes [index] = elementCount++;
}
else {
return resultIndex;
}
}
/**
* Increases the capacity of this OrderedSet. This method is sent when
* the size of this OrderedSet exceeds the load factor.
*/
protected void rehash () {
Object key;
int index, length = elementKeys.length<<1;
Object [] newKeys = new Object [length];
int [] newIndexes = new int [length];
for (int i = length; --i >= 0; ) {
newIndexes[i] = -1;
}
for (int i=0; i<elementKeys.length; i++) {
if ((key = elementKeys [i]) != null) {
index = findIndex (key, newKeys);
newKeys [index] = key;
newIndexes [index] = elementIndexes [i];
}
}
Object [] newOrdered = new Object[length];
System.arraycopy(orderedList, 0, newOrdered, 0, elementCount);
elementKeys = newKeys;
elementIndexes = newIndexes;
orderedList = newOrdered;
}
/**
* Answers the number of objects in this OrderedSet.
*
* @return the number of objects in this OrderedSet
*/
public int size () {
return elementCount;
}
/**
* Answers the string representation of this OrderedSet.
*
* @return the string representation of this OrderedSet
*/
public String toString () {
Object key;
StringBuffer buffer = new StringBuffer ();
buffer.append ('{');
for (int i=0; i<elementCount; i++) {
if (i != 0) buffer.append (',');
if (buffer.length() > 1000) {
buffer.append("...");
break;
}
buffer.append (orderedList[i]);
buffer.append ('=');
buffer.append (i);
}
buffer.append ('}');
return buffer.toString ();
}
}
|
